28 января 2013 в 14:09

Решение MintEye CAPTCHA в 31 строку кода, даже не открывая картинку из песочницы

image
Вдохновленный статьей «Решение 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. Знаю, что приведенный код далеко не идеален, в частности, не сработает в случае если самая первая картинка является правильной. Но я не стремился к идеалу, а просто хотел как можно более кратко проиллюстрировать идею.
+127
39347
77

комментарии (44)

0
Davidov, #
А можете показать пару графиков изменения «реального» размера файла? Ну или количества нулей, что то же самое.
+2
RolexStrider, #
Пожалуйста, вот график изменения количества нулей между картинками — Math.abs(delta), для капчи с футболистами из заголовка. Правильная картинка, очевидно, 15-я.
image
НЛО прилетело и опубликовало эту надпись здесь
+27
RolexStrider, #
Можно, я его и хотел было вставить, но какой-то он… мммм… неприличный, что ли выходит:
image
НЛО прилетело и опубликовало эту надпись здесь
–6
Shiz, #
смешной комментарий про график
–10
SegaZero, #
поучительный комментарий про карму
–1
SegaZero, #
image
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
+2
Weageoo, #
«Решение MintEye CAPTCHA без кода, китайцами»
0
Rastishka, #
Странно, я думал что наоборот сильно скрученная картинка (левая картинка из первой тройки) имеет больше плотность переходов между «кольцами» спирали => имеет больше градиентов => больше размер => меньше нулей в конце.

Или имеется ввиду сравнение количества нулей в последовательно идущих искаженных изображений?
0
RolexStrider, #
Именно, между двумя последовательными.
0
Rastishka, #
Да, по графику выше теперь все понятно. Хотя я все равно думал что крайние слева и справа столбцы должны быть выше центрального…
0
iCoderXXI, #
Не вдавался в нюансы формата JPG, но если в заголовке там указывается «размер тела», то не обязательно концовку нулями заполнять, можно просто мусором. Хотя если есть размер тела в заголовке, то нули в конце не обязательно подсчитывать. Можно просто размеры тела сравнивать.
–18
FZambia, #
Спасибо! А вот тут автор уложился в 23 строки
+3
DjPhoeniX, #
НЛО прилетело и опубликовало эту надпись здесь
+4
RolexStrider, #
Да, но используя при этом numpy и OpenCV.
–6
Error_403_Forbidden, #
с вероятностью практически 100% будут иметь различный размер в байтах

Вообще-то, если говорить строго, то есть вероятность больше нуля, что размеры изображения будут совпадать с точностью до байта. Даже если разброс в размерах JPEG-изображений одинакового размера будет колебаться от 1Кб до 1000Кб, то вероятность того, что следующая картинка будет такого же размера, что и предыдущая равна 1/1000. Что не так уж и мало.
А чем меньше изображение, тем этот разброс в размерах в байтах будет меньше.
–2
gasya, #
Вы такой умный.
+7
gasya, #
Для тех, кто не заценил мой острый комментарий:

а) то, что с некоторой вероятностью размеры могут и совпасть — очевидно, и нет большой заслуги в том, чтобы явно указывать на это.

б) то, что для разброса в n байт вероятность совпадения 1/n в общем случае не верно. Предположение о равномерном распределении ничем не подкреплено, и, как минимум, интуитивно понятно, что оно неверное. С таким же успехом можно утверждать, что вероятность совпадения 1/2 — ведь либо совпали, либо не совпали.

Так что не стоит оперировать понятиями теории вероятностей, не будучи знакомым с ней в какой-то минимальной степени.

Принимая во внимание два вышеуказанных тезиса, смело заявляю, что комментарий Error_403_Forbidden не содержательный, а частично и вовсе содержит неверные утверждения.
+5
Error_403_Forbidden, #
Вы такой умный.
+3
gasya, #
Знаю =)
НЛО прилетело и опубликовало эту надпись здесь
+2
samodum, #
Да, это так. Для примера — обе jpg-картинки имеют одинаковый размер и весят по 20304 байт каждая:

и
0
RolexStrider, #
Интересно, интересно… Правда сжаты они в Lossless-режиме, в хедере у обоих картинок: «CREATOR: gd-jpeg v1.0 (using IJG JPEG v80), quality = 100».
Но странно, почему после Хаффмана они все еще совпадают байт-в-байт? Впрочем, к этим картинкам подход совершенно другой нужен.
+5
samodum, #
Ничего странного нет. Обе картинки состоят из разных данных и после сжатия их размер непредсказуем. А раз так, то ничто не мешает им случайно совпасть.
Скажем, приведённые выше изображения в данном размере, таких же примерно насыщенности деталями и степени сжатия, будут примерно в пределах от 5000 байт до, например, 35000 байт.
Получается, что уникальных по объёму изображений может быть только 30000. Ведь и миллион таких картинок будет укладываться в этот диапазон объёма. Иначе были бы мегабайтные картинки, что невозможно при данных условиях сжатия JPEG.
0
masai, #
Более того, у некоторых алгоритмов сжатия (того же JPEG2000) можно кодеку прямо указать, сколько байт нужно получить на выходе.
0
Alexufo, #
Да и так как бе, тоже можно. Но байт в байт сомневаюсь.

0
RolexStrider, #
А разве это 2000?
0
Alexufo, #
Ну я потому так и пишу: как бы можно и с обычным jpg.
+1
RolexStrider, #
О, у JPEG2000 совсем другая, отдельная, очень интересная, достойная отдельного поста алгоритмическая база: вейвлеты.
0
masai, #
Ну, сжатием-то не вейвлеты сами по себе занимаются.
0
TiGR, #
Значит, нужно добавлять шум во все картинки. Это может помочь.
0
eugenius_nsk, #
Или наоборот слегка размывать — основную побольше, остальные поменьше.
0
Alexufo, #
Или просто в лосслесс выводить в bmp) Или его можно сжать в jpg и прогнать алгоритмом автора?)
0
RolexStrider, #
Безусловно, может. А тогда мы берем «Решение MintEye CAPTCHA в 23 строки кода» на Python.
+1
ayakovlev, #
Им нужно доработать алгоритм так, чтобы сжатие было с возрастающим «к краям гистограммы» уровнем качества. Тогда результирующий размер будет выравниваться и такой статистический подход перестанет работать.
0
UncleAndy, #
А почему нельзя концы картинок заполнить не нулями, а рандомным содержимым? Причем, разным у образца и у той картинки которая в списке.
+5
RolexStrider, #
Это не помогло бы: реальную длину JPEG-файла весьма несложно получить из служебной информации в заголовке.
0
UncleAndy, #
Да, верно. Не сообразил.
+4
Fil, #
...«блок кодирования» — это линейный массив из 64 байт, получаеый из блока изображения размером 8x8 пикселов путем обхода его по вот такой хитрой траектории, напоминающей «змейку»;
К «блокам кодирования» применяется дискретное косинусное преобразование...


Вы видимо решили, что к линейному массиву применяется DCT-II с N = 64? Нет, на самом деле, матрица 8x8 исходных значений (Y, Cb или Cr), подвергается DCT-II с N = 8 сначала по всем строкам (итого 8 раз DCT), а затем, по полученным коэффициэнтам еще 8 раз, но по столбцам. Можно наоборот, сначала по столбцам, затем по строкам, результат будет тот же.

Короче, у вас перепутаны этапы кодирования. Сначала блок 8x8 подвергается ДКП, результатом которого является матрица коэффициэнтов. Левое верхнее значение — самый значащий коэффициэнт — DC. И чем дальше от этого значения, тем более высокочастотны и менее значащи коэффициэнты. Затем квантование этой матрицы (вообще, там нет никакого порога, значения матрицы умножают на значения матрицы квантования) И поэтому, именно эти коэффициэнты, а не сами исходные значения, записывают в зигзагообразном порядке, чтобы обойти сначала более, а затем менее значащие. А длинный хвост обнуленных значений кодируется очень хорошо :)

Ну и справедливости ради отмечу, что согласно спецификации, преобразование в YCbCr не обязательно. Downsampling выполняется не всегда, и не обязательно 1:2. А вот разбиение на блоки именно 8x8 заданы спецификацией.
+1
RolexStrider, #
Абсолютно согласен. Просто, с одной стороны, не хотелось перегружать пост столь тонкими техническими подробностями, а с другой стороны — хотелось сохранить относительную легкость понимания не скатываясь в откровенную профанацию.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.