На хабре немало статей посвящено CAPTCHA. В одних статьях рассматриваются новые идеи для их генерации, в других – люди публикуют свои решения по распознаванию какой-либо. В третьих – показывают «как делать не надо». И еще куча статей на тему по тегу captcha. По моему мнению, самые интересные статьи именно на тему распознавания.
Эта статья – еще одна статья про распознавание CAPTCHA. Ранее уже были статьи про распознавание звуковых каптч и обычных, и картиночных. Не смотря на то, что в целом при распознавании любой каптчи можно выделить общие идеи, интерес представляет зачастую то, какие именно решения были использованы.
Я давно хотел написать распознавалку какой-нибудь каптчи, а также давно хотел изучить библиотеку OpenCV, так как меня интересует компьютерное зрение, обработка изображений, машинное обучение и все, что связано с этими областями. Основная цель этой работы состояла именно в самообучении. Требования к жертве я выдвинул следующие – любая не простая каптча с более-менее ценного ресурса. Требования к алгоритму – возможность распознавать несколько (больше 2) каптч в секунду с вероятностью более 50%.
В качестве жертвы была выбрана CAPTCHA с sms.beeline.ru.
Эта статья может быть интересна тем, кто хочет изучить основы OpenCV. Распознавалка была написана с помощью этой библиотеки и C++. Код получился не совсем кроссплатформенным, т.к. в паре мест пришлось использовать кусочек винапи. Но это обосновывается только лишь моей ленью, и код несложно заменяется на что-то нечто более кроссплатформенное.
Процесс создания распознавалки CAPTCHA можно представить в виде следующих этапов:
1. Сбор изображений
2. Анализ изображений с целью выделения уязвимостей
3. Разработка алгоритма устранения шума и искажений на изображении
4. Разработка алгоритма сегментации изображения на отдельные символы
5. Если есть искажения отдельных символов, то нужно разработать еще один алгоритм по их устранению + избавиться от остаточного мусора
6. Выбор системы признаков и классификатора
Основные приемы, которыми пользуются разработчики CAPTCHA направлены как раз на то, чтобы усложнить процесс выделения символов от фона и уточнения границ символов. Поэтому самые сложные этапы обычно 3 и 4. Но зачастую разработчики каптчи недостаточно осведомлены, какие алгоритмы уже с давних пор используются для обработки изображений с целью устранения шумов, выделения связных компонент и пр. Часто программист, вооруженный этими знаниями уже на этапе анализа начинает хитро улыбаться с мыслями: «Зачем они это сделали? Это же элементарно обходится и вообще бесполезно».
Лезем в исходный код страницы. Ссылка на изображение каптчи выглядит следующим образом: http://www.beeline.ru/mamimg.aspx?width=120&height=30. Меняя параметры width и height можно наблюдать, что меняются размеры букв, расстояния между ними, а также размер фонового шума. Путем подбора ищем такие параметры, при которых символы как можно реже слипаются, а шум имеет как можно меньший размер. В идеале – если получится сделать толщину точек и линий фона меньше толщины букв. Наиболее хорошим размером мне показался 200х40. Подставить новые размеры каптчи в код страницы можно легко с помощью того же Firebug.
Итак, собираем примерно 200 изображений размером 200х40 точек. Я сохранял изображения, а затем переименовывал их в вид ABCDE.gif, где ABCDE – то, что написано на изображении.
Свойства каптчи, которые были мною выделены:
1. Текст состоит из символов 0-9, ABCDEFKMP
2. Изображение формата gif, с несколькими индексированными цветами.
3. Используется только по одному начертанию каждого символа (один шрифт)
4. На изображении 4 основных цвета: серый, тёмно-синий, тёмно-зеленый, зеленый. Каждый основной цвет представляется в виде растра из 3 или 4 цветов отдельных точек.
5. Каждый символ нарисован одним из основных цветов
6. Шум на изображении состоит из точек, все точки имеют один основной цвет, и из ломаных линий, линии также имеют один основной цвет. Максимальная толщина точек и линий чаще всего меньше минимальной толщины символов.
7. Символы имеют незначительные искажения: небольшое смещение центра символа, небольшой поворот и небольшое изменение масштаба.
8. Возможны пересечения символов. Чаще всего из-за символа M
По ним можно выделить основные уязвимости:
1. Большинство шума устраняется путём фильтрации коротких горизонтальных и вертикальных однопиксельных штрихов. Это обеспечивается свойством 6.
2. Можно произвести фильтрацию по компонентам растра основных цветов, таким образом устранив на изображении пиксели, которые в результате anti-aliasing-а стали отличными от этих компонент. Такие «прозрачные» пиксели находятся на границах объектов (шум-символ-фон). Это обеспечивается свойством 4.
3. Сегментация изображения на символы тривиальна – просто делим изображение на 5 равных частей. В подавляющем большинстве случаев в каждой части будет находится практически полностью один символ. Иногда может попадать часть соседнего символа, но это незначительно. Это обеспечивается свойством 7.
4. Если удастся выделить изображения отдельных символов, очищенных от шума, то с ними справится большинство простейших классификаторов, т.к. у одного символа может быть только одно начертание (св-во 3) и множество символов сильно ограничено (св-во 1).
Используем уязвимости 1 и 2. Алгоритма фильтрации коротких штрихов на изображении в OpenCV мною не был обнаружен, так что пришлось написать самому. Фильтрацию по множеству цветов мне показалось легче написать вручную, чем искать какой-либо аналог в библиотеке.
Фильтрация вертикальных штрихов: внешний цикл по X, внутренний цикл по Y, проходим по всему изображению. Если находим вертикальных штрих (непрерывная последовательность точек с единой координатой X, цветом отличным от белого) длиной менее заданной, то заливаем этот штрих белым цветом. Фильтрация горизонтальных штрихов аналогична.
Итак, первый шаг устранения от шума – избавляемся сначала от вертикальных штрихов длиной YMax или менее, затем от горизонтальных штрихов длиной XMax или менее. Я остановился на значениях параметров YMax = 3, XMax = 2.
Второй шаг – фильтрация по растру. В любом графическом редакторе поводив по изображению можно выделить компоненты каждого основного цвета. Например, для серого цвета это 4 компоненты: RGB(153,153,153), RGB(153,102,153), RGB(153,102,102), RGB(102,102,102). Закрашиваем белым все точки, значения которых отличны от компонентов основных цветов.
Третий шаг – в результате предыдущего шага внутри символов могут образоваться редкие белые точки. Закрашиваем их чёрным цветом.
Четвертый шаг – повторно избавляемся от коротких вертикальных штрихов, с параметрами YMax = 1 и XMax = 3.
Пятый шаг – в дальнейшем информация о цвете нам не нужна, так что преобразовываем изображение из пространства RGB в одноканальное серое с помощью cvCvtColor( src, dst, CV_BGR2GRAY ).
На самом деле, для того, чтобы убедиться в уязвимости 3 пришлось сделать небольшое исследование. Для всех изображений в выборке были построены горизонтальные профили (проекции на ось X) этих изображений, прошедших этап устранения шума. Сложив все эти профили можно обнаружить локальные минимумы, которые находятся практически точно с шагом в 40 точек. В OpenCV мною не были обнаружены средства для построения профилей, так что пришлось написать собственную функцию.
Так что никакой умной науки на этом этапе нет. Тупо разбиваем изображение 200х40 на 5 изображений размером 40х40.
Т.к. в результате работы этапа устранения шума на всём изображении мы можем не избавиться от всего шума, а также может добавиться дополнительный мусор из-за того, что в изображение одного символа может заскочить часть другого, приходится сделать дополнительную очистку от мусора.
Основная идея – выделить на изображениях связные компоненты малой площади и закрасить их белым цветом.
Тут было потрачено довольно много времени на изучение учебника по OpenCV – про функцию cvPyrSegmentation, про то, что такое последовательности cvSeq, про то, как представляются контуры и пр. Самому изобретать велосипед не очень хотелось, а также поняв, что простой функции выделения связных компонент я не найду, пришлось залезть в гугл с запросом «connected component opencv», откуда первая ссылка ведет на библиотеку cvBlobsLib.
Эта библиотека делает как раз то, что мне нужно. С помощью нее в несколько строчек можно выделить связные компоненты, отсортировать их по площади и закрасить все компоненты, площадь которых менее заданной. Мною с потолка было взято число 80 — максимальная площадь мусора, фильтрация прошла практически идеально.
(отфильтрованные изображения – до и после)
Также в этот этап можно добавить приведение изображений символов к единому виду.
Т.к. размеры букв немного различны, то мы будем приводить их к единому размеру. Можно было бы попробовать исправлять поворот, но непонятно, сколько выигрыша это может дать, пока не будет готова хотя бы первая версия распознавалки.
Хотя у нас уже все изображения единого размера 40х40 точек, символы зачастую не касаются границ. Поэтому была написана функция удаления белых полей на изображении, то есть обрезание изображения по границам символа. Границы символа находятся с помощью построения горизонтального и вертикального профилей. По каждому из профилей находится центр масс, от которого циклом влево и вправо (вверх и вниз) находятся первые значения, равные 0 – это значение означает, что мы наткнулись на пустую вертикальную (горизонтальную) линию и символ тут закончился (предполагаем, что в результате устранения шумов таких вертикальных и горизонтальных дырок не может быть в символе).
Такое обрезанное изображение масштабируем обратно к размеру 40х40.
Теперь мы имеем множество из 1000 изображений отдельных символов, серых, с устраненными шумами и приведенными к единому размеру. Можно оставить обработку изображений в покое и подумать немного о машинном обучении. В принципе, можно было бы попробовать скормить эти изображения FineReader Engine-у, но мне хотелось изучить возможности модуля ml (machine learning) у OpenCV.
Большинство классификаторов, реализованных в ml, являются признаковыми: наивный Байесовский, бинарные деревья решений, случайный лес, максимизация ожидания, k ближайших соседей, многослойный персептрон, опорные векторы. Я решил ограничиться использованием простейших – наивный Байесовский классификатор и k ближайших соседей. Подробнее про эти классификаторы можно почитать например в Википедии.
Первое, что надо сделать – это выбрать признаки, которые будут описывать изображение. Решение «в лоб» — в качестве признаков использовать каждую точку изображения, то есть для серого изображения размером 40х40 это будет 1600 байтовых признаков. После того, как я запустил обучение Байесовского классификатора на 500 изображениях по 1600 признаков у каждого, моё приложение стало сотни-тысячи мегабайт памяти и я решил остановить его, пока не поздно.
Вторая идея «почти в лоб» — разделить изображение на 64 равных квадратов, сеткой 8х8, и посчитать количество чёрного в каждом квадрате. По результатам тестов выяснилось, что этих признаков оказалось достаточно для достижения хорошего качества распознавания.
Наивный Байесовский классификатор представлен в OpenCV классом CvNormalBayesClassifier. Нас интересуют в нем следующие методы: train( train_data, responses, …), predict( samples, … ), save и load. Первый метод принимает на вход матрицу train_data MxN, где M – количество признаков, N – количество изображений, и вектор responses размером N, где в виде чисел записаны классы соответствующих строчек в матрице. Второй метод принимает на вход аналогичную матрицу MxN, но нас интересует случай, когда ее размер Mx1, то есть просто вектор признаков. В этом случае predict просто возвращает наиболее вероятный класс. save и load соответственно сохраняют и загружают обученный классификатор в xml-файл.
K ближайших соседей – класс CvKNearest. Работа с ним аналогична CvNormalBayesClassifier, только почему-то отсутствуют методы save и load, а predict был переименован в find_nearest( samples, k, … ), где помимо samples есть обязательный параметр k – по скольким соседям искать ближайшего. Я рассматриваю простейший случай k = 1, то есть по самому ближайшему соседу.
Итак, мы получили полностью всё, что нужно, чтобы распознать данную каптчу. Делим пачку из 200 изображений на две части по 100. Одна часть будет обучающей выборкой, другая – тестовой. Из обучающей выборки выдираем изображения отдельных символов, которые получаются перед этапом получения, сохраняем в отдельную папку. Нужно удалить вручную среди них плохие для обучения изображения, то есть сильно испорченные неудалённым мусором, или наоборот испорченные излишним удалением. В итоге у меня получилась выборка из 486 изображений символов, то есть примерно по 25 изображений на символ. Этого вполне достаточно для того чтобы обучить наш классификатор.
На этой обучающей выборке изображений символов обучаем оба классификатора – Байесовский и kNN, при этом Байесовский сохраняем в файл, чтобы лишний раз его в будущем не обучать.
Результаты распознавания тестовой выборки:
Байесовский классификатор распознал правильно 78 изображений из 100
kNN распознал правильно 85 изображений из 100
Если поменять местами тестовую и обучающую выборку:
Байес: 81 из 100
kNN: 94 из 100 !
Скорость распознавания мною не замерялась (т.к. я делаю паузы для визуального контроля), но по ощущениям – скорость не менее 10 изображений в секунду. Память программа кушала порядка 10МБ. Никаких оптимизаций по скорости или памяти применено не было.
Основные ошибки происходили на парах символов 4-A, 8-B, 0-D, а также на буквах, сильно испорченных мусором, или сильно пострадавших от уборки мусора. К счастью, таких картинок было меньшинство, что позволило достичь такого высокого результата.
Таким образом, все требования были достигнуты и опережены с большим запасом.
Исходный код программы можно взять тут. Для ее работы нужно поставить OpenCV и cvBlobsLib и прописать к ним пути в проекте. Код старался хорошо задокументировать в комментариях, чтобы было понятно. Несколько функций, которые я планировал сделать ранее, так и не были реализованы, но и без них всё распознавание проходит отлично. Единственное, с чем я не разобрался – почему cvOpenImage не хотел открывать изображения .gif, сохраненные напрямую с сайта билайна. Пришлось конвертировать с помощью FastStone в .tif, который уже открывался без проблем. В процессе изучения OpenCV я руководствовался гуглом и книжкой Bradski, Kaehler — Learning OpenCV — O’Reilly, 2008.
В дальнейшем я планирую развивать эту работу в следующих направлениях:
1. Причесать код.
2. Распознать более сложные каптчи (яндекс, гугл, вконтакте – привет).
3. Попытаться использовать FineReader Engine, но я не ожидаю от него качества лучшего, чем от отдельной программы, настроенной на конкретную каптчу. Например, можно посмотреть вероятность правильного распознавания с помощью FRE на тех же выборках, что использовались при написании статьи.
4. Превратить написанный инструмент в отдельную библиотеку и automation-объект, который можно будет в дальнейшем вызывать из скриптовых языков.
5. Написать скрипт по автоматическому нахождению каптчи на странице, ее распознаванию и подстановкой распознанного значения в форму.
Для того, чтобы не мучила совесть – написал Билайну, что их каптча откровенно слабая, описал уязвимости и порекомендовал усложнить ее.
Если будет интересно, то в дальнейшем ждите продолжения моих статей про этот обучающий проект.
Эта статья – еще одна статья про распознавание CAPTCHA. Ранее уже были статьи про распознавание звуковых каптч и обычных, и картиночных. Не смотря на то, что в целом при распознавании любой каптчи можно выделить общие идеи, интерес представляет зачастую то, какие именно решения были использованы.
Я давно хотел написать распознавалку какой-нибудь каптчи, а также давно хотел изучить библиотеку OpenCV, так как меня интересует компьютерное зрение, обработка изображений, машинное обучение и все, что связано с этими областями. Основная цель этой работы состояла именно в самообучении. Требования к жертве я выдвинул следующие – любая не простая каптча с более-менее ценного ресурса. Требования к алгоритму – возможность распознавать несколько (больше 2) каптч в секунду с вероятностью более 50%.
В качестве жертвы была выбрана CAPTCHA с sms.beeline.ru.
Эта статья может быть интересна тем, кто хочет изучить основы OpenCV. Распознавалка была написана с помощью этой библиотеки и C++. Код получился не совсем кроссплатформенным, т.к. в паре мест пришлось использовать кусочек винапи. Но это обосновывается только лишь моей ленью, и код несложно заменяется на что-то нечто более кроссплатформенное.
Процесс создания распознавалки CAPTCHA можно представить в виде следующих этапов:
1. Сбор изображений
2. Анализ изображений с целью выделения уязвимостей
3. Разработка алгоритма устранения шума и искажений на изображении
4. Разработка алгоритма сегментации изображения на отдельные символы
5. Если есть искажения отдельных символов, то нужно разработать еще один алгоритм по их устранению + избавиться от остаточного мусора
6. Выбор системы признаков и классификатора
Основные приемы, которыми пользуются разработчики CAPTCHA направлены как раз на то, чтобы усложнить процесс выделения символов от фона и уточнения границ символов. Поэтому самые сложные этапы обычно 3 и 4. Но зачастую разработчики каптчи недостаточно осведомлены, какие алгоритмы уже с давних пор используются для обработки изображений с целью устранения шумов, выделения связных компонент и пр. Часто программист, вооруженный этими знаниями уже на этапе анализа начинает хитро улыбаться с мыслями: «Зачем они это сделали? Это же элементарно обходится и вообще бесполезно».
Анализ и выделение уязвимостей
Лезем в исходный код страницы. Ссылка на изображение каптчи выглядит следующим образом: http://www.beeline.ru/mamimg.aspx?width=120&height=30. Меняя параметры width и height можно наблюдать, что меняются размеры букв, расстояния между ними, а также размер фонового шума. Путем подбора ищем такие параметры, при которых символы как можно реже слипаются, а шум имеет как можно меньший размер. В идеале – если получится сделать толщину точек и линий фона меньше толщины букв. Наиболее хорошим размером мне показался 200х40. Подставить новые размеры каптчи в код страницы можно легко с помощью того же Firebug.
Итак, собираем примерно 200 изображений размером 200х40 точек. Я сохранял изображения, а затем переименовывал их в вид ABCDE.gif, где ABCDE – то, что написано на изображении.
Свойства каптчи, которые были мною выделены:
1. Текст состоит из символов 0-9, ABCDEFKMP
2. Изображение формата gif, с несколькими индексированными цветами.
3. Используется только по одному начертанию каждого символа (один шрифт)
4. На изображении 4 основных цвета: серый, тёмно-синий, тёмно-зеленый, зеленый. Каждый основной цвет представляется в виде растра из 3 или 4 цветов отдельных точек.
5. Каждый символ нарисован одним из основных цветов
6. Шум на изображении состоит из точек, все точки имеют один основной цвет, и из ломаных линий, линии также имеют один основной цвет. Максимальная толщина точек и линий чаще всего меньше минимальной толщины символов.
7. Символы имеют незначительные искажения: небольшое смещение центра символа, небольшой поворот и небольшое изменение масштаба.
8. Возможны пересечения символов. Чаще всего из-за символа M
По ним можно выделить основные уязвимости:
1. Большинство шума устраняется путём фильтрации коротких горизонтальных и вертикальных однопиксельных штрихов. Это обеспечивается свойством 6.
2. Можно произвести фильтрацию по компонентам растра основных цветов, таким образом устранив на изображении пиксели, которые в результате anti-aliasing-а стали отличными от этих компонент. Такие «прозрачные» пиксели находятся на границах объектов (шум-символ-фон). Это обеспечивается свойством 4.
3. Сегментация изображения на символы тривиальна – просто делим изображение на 5 равных частей. В подавляющем большинстве случаев в каждой части будет находится практически полностью один символ. Иногда может попадать часть соседнего символа, но это незначительно. Это обеспечивается свойством 7.
4. Если удастся выделить изображения отдельных символов, очищенных от шума, то с ними справится большинство простейших классификаторов, т.к. у одного символа может быть только одно начертание (св-во 3) и множество символов сильно ограничено (св-во 1).
Устранение шума и искажений на изображении
Используем уязвимости 1 и 2. Алгоритма фильтрации коротких штрихов на изображении в OpenCV мною не был обнаружен, так что пришлось написать самому. Фильтрацию по множеству цветов мне показалось легче написать вручную, чем искать какой-либо аналог в библиотеке.
Фильтрация вертикальных штрихов: внешний цикл по X, внутренний цикл по Y, проходим по всему изображению. Если находим вертикальных штрих (непрерывная последовательность точек с единой координатой X, цветом отличным от белого) длиной менее заданной, то заливаем этот штрих белым цветом. Фильтрация горизонтальных штрихов аналогична.
Итак, первый шаг устранения от шума – избавляемся сначала от вертикальных штрихов длиной YMax или менее, затем от горизонтальных штрихов длиной XMax или менее. Я остановился на значениях параметров YMax = 3, XMax = 2.
Второй шаг – фильтрация по растру. В любом графическом редакторе поводив по изображению можно выделить компоненты каждого основного цвета. Например, для серого цвета это 4 компоненты: RGB(153,153,153), RGB(153,102,153), RGB(153,102,102), RGB(102,102,102). Закрашиваем белым все точки, значения которых отличны от компонентов основных цветов.
Третий шаг – в результате предыдущего шага внутри символов могут образоваться редкие белые точки. Закрашиваем их чёрным цветом.
Четвертый шаг – повторно избавляемся от коротких вертикальных штрихов, с параметрами YMax = 1 и XMax = 3.
Пятый шаг – в дальнейшем информация о цвете нам не нужна, так что преобразовываем изображение из пространства RGB в одноканальное серое с помощью cvCvtColor( src, dst, CV_BGR2GRAY ).
Сегментация на изображения отдельных символов
На самом деле, для того, чтобы убедиться в уязвимости 3 пришлось сделать небольшое исследование. Для всех изображений в выборке были построены горизонтальные профили (проекции на ось X) этих изображений, прошедших этап устранения шума. Сложив все эти профили можно обнаружить локальные минимумы, которые находятся практически точно с шагом в 40 точек. В OpenCV мною не были обнаружены средства для построения профилей, так что пришлось написать собственную функцию.
Так что никакой умной науки на этом этапе нет. Тупо разбиваем изображение 200х40 на 5 изображений размером 40х40.
Устранение искажений и остаточного шума на изображениях отдельных символов
Т.к. в результате работы этапа устранения шума на всём изображении мы можем не избавиться от всего шума, а также может добавиться дополнительный мусор из-за того, что в изображение одного символа может заскочить часть другого, приходится сделать дополнительную очистку от мусора.
Основная идея – выделить на изображениях связные компоненты малой площади и закрасить их белым цветом.
Тут было потрачено довольно много времени на изучение учебника по OpenCV – про функцию cvPyrSegmentation, про то, что такое последовательности cvSeq, про то, как представляются контуры и пр. Самому изобретать велосипед не очень хотелось, а также поняв, что простой функции выделения связных компонент я не найду, пришлось залезть в гугл с запросом «connected component opencv», откуда первая ссылка ведет на библиотеку cvBlobsLib.
Эта библиотека делает как раз то, что мне нужно. С помощью нее в несколько строчек можно выделить связные компоненты, отсортировать их по площади и закрасить все компоненты, площадь которых менее заданной. Мною с потолка было взято число 80 — максимальная площадь мусора, фильтрация прошла практически идеально.
(отфильтрованные изображения – до и после)
Также в этот этап можно добавить приведение изображений символов к единому виду.
Т.к. размеры букв немного различны, то мы будем приводить их к единому размеру. Можно было бы попробовать исправлять поворот, но непонятно, сколько выигрыша это может дать, пока не будет готова хотя бы первая версия распознавалки.
Хотя у нас уже все изображения единого размера 40х40 точек, символы зачастую не касаются границ. Поэтому была написана функция удаления белых полей на изображении, то есть обрезание изображения по границам символа. Границы символа находятся с помощью построения горизонтального и вертикального профилей. По каждому из профилей находится центр масс, от которого циклом влево и вправо (вверх и вниз) находятся первые значения, равные 0 – это значение означает, что мы наткнулись на пустую вертикальную (горизонтальную) линию и символ тут закончился (предполагаем, что в результате устранения шумов таких вертикальных и горизонтальных дырок не может быть в символе).
Такое обрезанное изображение масштабируем обратно к размеру 40х40.
Выбор системы признаков и классификатора
Теперь мы имеем множество из 1000 изображений отдельных символов, серых, с устраненными шумами и приведенными к единому размеру. Можно оставить обработку изображений в покое и подумать немного о машинном обучении. В принципе, можно было бы попробовать скормить эти изображения FineReader Engine-у, но мне хотелось изучить возможности модуля ml (machine learning) у OpenCV.
Большинство классификаторов, реализованных в ml, являются признаковыми: наивный Байесовский, бинарные деревья решений, случайный лес, максимизация ожидания, k ближайших соседей, многослойный персептрон, опорные векторы. Я решил ограничиться использованием простейших – наивный Байесовский классификатор и k ближайших соседей. Подробнее про эти классификаторы можно почитать например в Википедии.
Первое, что надо сделать – это выбрать признаки, которые будут описывать изображение. Решение «в лоб» — в качестве признаков использовать каждую точку изображения, то есть для серого изображения размером 40х40 это будет 1600 байтовых признаков. После того, как я запустил обучение Байесовского классификатора на 500 изображениях по 1600 признаков у каждого, моё приложение стало сотни-тысячи мегабайт памяти и я решил остановить его, пока не поздно.
Вторая идея «почти в лоб» — разделить изображение на 64 равных квадратов, сеткой 8х8, и посчитать количество чёрного в каждом квадрате. По результатам тестов выяснилось, что этих признаков оказалось достаточно для достижения хорошего качества распознавания.
Наивный Байесовский классификатор представлен в OpenCV классом CvNormalBayesClassifier. Нас интересуют в нем следующие методы: train( train_data, responses, …), predict( samples, … ), save и load. Первый метод принимает на вход матрицу train_data MxN, где M – количество признаков, N – количество изображений, и вектор responses размером N, где в виде чисел записаны классы соответствующих строчек в матрице. Второй метод принимает на вход аналогичную матрицу MxN, но нас интересует случай, когда ее размер Mx1, то есть просто вектор признаков. В этом случае predict просто возвращает наиболее вероятный класс. save и load соответственно сохраняют и загружают обученный классификатор в xml-файл.
K ближайших соседей – класс CvKNearest. Работа с ним аналогична CvNormalBayesClassifier, только почему-то отсутствуют методы save и load, а predict был переименован в find_nearest( samples, k, … ), где помимо samples есть обязательный параметр k – по скольким соседям искать ближайшего. Я рассматриваю простейший случай k = 1, то есть по самому ближайшему соседу.
Тестирование и выводы
Итак, мы получили полностью всё, что нужно, чтобы распознать данную каптчу. Делим пачку из 200 изображений на две части по 100. Одна часть будет обучающей выборкой, другая – тестовой. Из обучающей выборки выдираем изображения отдельных символов, которые получаются перед этапом получения, сохраняем в отдельную папку. Нужно удалить вручную среди них плохие для обучения изображения, то есть сильно испорченные неудалённым мусором, или наоборот испорченные излишним удалением. В итоге у меня получилась выборка из 486 изображений символов, то есть примерно по 25 изображений на символ. Этого вполне достаточно для того чтобы обучить наш классификатор.
На этой обучающей выборке изображений символов обучаем оба классификатора – Байесовский и kNN, при этом Байесовский сохраняем в файл, чтобы лишний раз его в будущем не обучать.
Результаты распознавания тестовой выборки:
Байесовский классификатор распознал правильно 78 изображений из 100
kNN распознал правильно 85 изображений из 100
Если поменять местами тестовую и обучающую выборку:
Байес: 81 из 100
kNN: 94 из 100 !
Скорость распознавания мною не замерялась (т.к. я делаю паузы для визуального контроля), но по ощущениям – скорость не менее 10 изображений в секунду. Память программа кушала порядка 10МБ. Никаких оптимизаций по скорости или памяти применено не было.
Основные ошибки происходили на парах символов 4-A, 8-B, 0-D, а также на буквах, сильно испорченных мусором, или сильно пострадавших от уборки мусора. К счастью, таких картинок было меньшинство, что позволило достичь такого высокого результата.
Таким образом, все требования были достигнуты и опережены с большим запасом.
Прочее
Исходный код программы можно взять тут. Для ее работы нужно поставить OpenCV и cvBlobsLib и прописать к ним пути в проекте. Код старался хорошо задокументировать в комментариях, чтобы было понятно. Несколько функций, которые я планировал сделать ранее, так и не были реализованы, но и без них всё распознавание проходит отлично. Единственное, с чем я не разобрался – почему cvOpenImage не хотел открывать изображения .gif, сохраненные напрямую с сайта билайна. Пришлось конвертировать с помощью FastStone в .tif, который уже открывался без проблем. В процессе изучения OpenCV я руководствовался гуглом и книжкой Bradski, Kaehler — Learning OpenCV — O’Reilly, 2008.
В дальнейшем я планирую развивать эту работу в следующих направлениях:
1. Причесать код.
2. Распознать более сложные каптчи (яндекс, гугл, вконтакте – привет).
3. Попытаться использовать FineReader Engine, но я не ожидаю от него качества лучшего, чем от отдельной программы, настроенной на конкретную каптчу. Например, можно посмотреть вероятность правильного распознавания с помощью FRE на тех же выборках, что использовались при написании статьи.
4. Превратить написанный инструмент в отдельную библиотеку и automation-объект, который можно будет в дальнейшем вызывать из скриптовых языков.
5. Написать скрипт по автоматическому нахождению каптчи на странице, ее распознаванию и подстановкой распознанного значения в форму.
Для того, чтобы не мучила совесть – написал Билайну, что их каптча откровенно слабая, описал уязвимости и порекомендовал усложнить ее.
Если будет интересно, то в дальнейшем ждите продолжения моих статей про этот обучающий проект.