Вдохновленный статьей «Решение MintEye CAPTCHA в 23 строки кода», а также горя желанием глубже разобраться в методах выделения краев изображения, таких как оператор Собеля и оператор Кэнни, я решил попытаться самостоятельно повторить описанный в статье алгоритм.
Быстренько набросав скрипт, загружающий с сайта MintEye набор «подопытных» изображений, я было приготовился открыть любимую IDE, чтобы приступить к экспериментам с «высокими технологиями», но заглянув в каталог со скачанными картинками, обнаружил одну очень любопытную закономерность.
Все изображения (в формате JPEG, что очень важно), относящиеся к одной капче, имели одиннаковый размер в байтах!
«А ведь это невозможно!» — подумал я. Чтобы пояснить почему невозможно, вкратце напомню вам основные идеи, лежащие в основе алгоритма сжатия JPEG. За более детальным описанием добро пожаловать в Википедию.
Алгоритм JPEG сжимает исходное изображение в такой последовательности:
- Выполняется преобразование цветовой модели: перевод исходного изображения из цветового пространства RGB в цветовое пространство YCbCr. После этого шага изображение оказываеся разделенным на канал яркости (Y) и два «цветоразностных канала» — Cb и Cr;
- Производится децимация (downsampling) цветовых каналов Cb и Cr. Как правило, простым уменьшением их размеров вдвое. За счет того, что человеческий глаз более чувствителен к изменению яркости, чем цвета, уже на данном достигается ощутимое уменьшение размера изображения при весьма незначительных потерях качества;
- Каждый канал разбивается на так называемые «блоки кодирования». В наиболее распространенном случае, «блок кодирования» — это линейный массив из 64 байт, получаеый из блока изображения размером 8x8 пикселов путем обхода его по вот такой хитрой траектории, напоминающей «змейку»;
- К «блокам кодирования» применяется дискретное косинусное преобразование. Не буду вдаваться в подробности, но после данного преобразования «блок кодирования» превращается, грубо говоря, в некий набор коэффициентов, тесно связанных с количеством мелких деталей и плавных цветовых переходов в исходном изображении.
- Выполняется квантование (quantization). На этом этапе в игру вступает параметр «степень сжатия» или «желаемое качество изображения». Опять таки, очень грубо говоря, идея тут в том, что все коэффициенты меньше определенного порогового значения (определяемого желаемой степенью сжатия), тупо обнуляются. Оставшиеся коэффициенты все же позволяют с некоторой точностью восстановить исходное изображение. Именно этот этап «порождает» так хорошо известные всем артефакты сжатия;
- И наконец, все то, что осталось от нашей бедной исходной картинки, окончательно «дожимается» алгоритмом сжатия без потерь. Для JPEG практически всегда это алгоритм Хаффмана.
Чем же знание «внутренней кухни» алгоритма JPEG может быть нам полезным в разгадывании MintEye CAPTCHA? А тем, что зная все это, становится очевидно, что две отличающиеся картинки, имеющие одиннаковые размеры (в пикселах) и сжатые с одинаковыми настройками качества, с вероятностью практически 100% будут иметь различный размер в байтах! Причем, наибольший размер будет иметь та картинка, на которой больше мелких деталей, и меньше плавных цветовых переходов.
Чтобы доказать это, берем старушку-Лену и проводим следующий эксперимент (все три изображения сжаты стандартным Photoshop-овским «Save for Web», с качеством 40):
 |
 |
 |
| Gaussian Noise 5% Размер: 10342 байта |
Оригинал Размер: 7184 байта |
Gaussian Blur 1,5px Размер: 4580 байт |
Ну вот, что и требовалось доказать: при прочих равных условиях, чем больше шумов — тем больше размер файла, чем больше размытие — тем размер меньше.
Почему тогда все картинки MintEye CAPTCHA имеют одиннаковый размер? Секрет фокуса оказался примитивен до невозможности: файлы просто дополняются нулями до размера самого большого из них!
Обнаружив это, почти сразу же в голове у меня родилось в некотором роде «наглое», но крайне простое и эффективное решение по распознаванию этой, с позволения сказать «капчи». Взгляните на эти две картинки:
Слева — слегка искаженное изображение, находящееся на одну позицию левее, чем «правильное». Справа — неискаженное изображение, являющееся правильным ответом.
Левая картинка на первый взгляд искривлена совсем незначительно. Но на самом деле такое «скручивание» на небольшой угол сильно «размывает» резкие границы и мелкие детали. А значит, исходя из известных нам особенностей сжатия JPEG, такая слегка искаженная картинка должна отличаться по размеру от правильной, причем отличаться резко в меньшую сторону!
Дабы проверить столь смелое предположение, открываю IDE и буквально за 10 минут пишу следующее:
import java.io.IOException; import java.io.RandomAccessFile; public class MintEye { public static void main(String[] args) throws IOException { int maxDelta = 0; int correctNum = 0; int zeroes = 0; int prevZeroes = 0; for (int n = 0; n < 30; n++) { if (n > 0) prevZeroes = zeroes; zeroes = 0; RandomAccessFile raf = new RandomAccessFile( String.format("images/%1$02d.jpg", n + 1), "r"); long fileLen = raf.length(); for (int i = (int) fileLen - 1; i >= 0; i--) { raf.seek(i); if (raf.read() != 0) break; zeroes++; } int delta = prevZeroes - zeroes; if (delta > maxDelta) { maxDelta = delta; correctNum = n; } raf.close(); } System.out.printf("Correct image: %d%n", correctNum + 1); } }
В двух словах: мы проходим по нашим картинкам (у MintEye их будет 30 штук), считая количество нулей в конце текущего файла и сравнивая его с количеством нулей в конце предыдущего. Файл, для которого это отличие будет максимальным, предположительно и будет исходной, неискаженной картинкой, то есть правильным ответом.
Идея оказалась абсолютно верной: 100%! 10 из 10! Все скачанные наборы картинок были распознаны безошибочно. При этом не используя совершенно никаких библиотек обработки изображений, и даже не загружая картинок в память!
В итоге я в очередной раз убедился, что на каждую хитрую капчу рано или поздно найдется свой «распознаватель», а мою персональную «коллекцию скальпов», пополнил MintEye (которые теперь уже совершенно смело могут сворачивать свой стартап
Ну а Хабрахабр пополнился этой статьей.
P.S. Знаю, что приведенный код далеко не идеален, в частности, не сработает в случае если самая первая картинка является правильной. Но я не стремился к идеалу, а просто хотел как можно более кратко проиллюстрировать идею.