Распознавание символов
Распознаватели символов можно разделить на следующие основные группы по типу принимаемых ими данных:
Растровое изображение. Такие распознаватели часто называют шаблонными, т.к. в них скрыто сравнение с шаблонами символов, характеризующих соответствующие классы. Подобные распознаватели наиболее применимы в ситуациях, когда заранее известны шрифты и границы символов выделены с достаточной точностью. Такие методы отличаются наибольшей простотой и скоростью работы. Кроме того, в отличие от большинства других способов распознавания, такие методы менее чувствительны к ошибкам печати, таким как пропущенная строка точек: в случае если рамка символа определена корректно, он будет распознан с высокой точностью.
Вектор признаков. Наиболее распространены распознаватели, работающие не с непосредственно изображением, а с заранее выделенными признаками – такими как, например, количество и расположение пересечений линий на изображении, количество замкнутых контуров и пр. Обычно в качестве признаков выбирают инварианты для символов. За счет этого распознаватель становится устойчивым к незначительным ошибкам в выделении границ и качеству входного изображения. Кроме того, использование вектора свойств вместо растрового изображения допускает использование различных способов написания символа (шрифтов), в том числе и рукописный ввод.
Модельное представление. Оно применяется достаточно редко и в основном в online-распознавателях. Изображение разбивается на некоторые примитивы: например, окружности и отрезки, по взаимному расположению которых распознаватель классифицирует входное изображение.
В задаче распознавания чека можно применить любой из первых двух подходов – классифицировать растровое изображение или строить вектор признаков.
Несмотря на то, что в данной задаче заранее доступны шрифты7, за счет невысокого качества изображения, трудно достичь точности выделения границ символа, достаточной для работы непосредственно с растровыми изображениями. Кроме того, при реализации такого шаблонного распознавателя было обнаружено, что у некоторых символов на кассовом чеке большинство точек совпадают. Так, например, “3” и “9” с достаточной частотой распознавались неправильно, а точность распознавания чисел критична для разрабатываемой системы: ошибка в наименовании товара8 не так страшна, как в итоговой стоимости, которая оказывает существенное влияние на статистику. По этой причине был разработан алгоритм, принимающий во входе вектор признаков изображения.
В качестве вектора признаков выделялись следующие характеристики изображения:
Отношение числа точек символа к числу точек в занимаемом им прямоугольнике (степень заполнения области)
Отношение числа точек в нижней половине символа к общему числу точек символа
Отношение числа точек в левой половине символа к общему числу точек символа
Соотношение высоты символа к его ширине
Количество замкнутых областей
Количество точек пересечений
Количество концевых точек
Среднеквадратичное расстояние между точками пересечений
Среднеквадратичное расстояние между точками пересечений и концевыми точками
Построение вектора признаков
На входе модуля, заполняющего вектор признаков данного символа, имеется бинарное изображение, полученное после разбиения некоторой строки на символы. Это изображение не пусто по построению и не имеет вертикальных разделителей9.
Вычисление количества замкнутых областей
Замкнутой областью будем называть связную область нулевых точек, не содержащую точек, лежащих на границе изображения символа.
Рис.6 Замкнутые области изображения
Для подсчета таких областей выполняется итеративная заливка изображения до полностью ненулевого. Число встреченных связных областей, не лежащих на границе изображения, есть число замкнутых областей.
Скелетизация изображения
Для исследования точек пересечений изображения строится так называемый каркас изображения. В различных источниках понятие каркаса изображения определяют немного по-разному. Канонична лишь его фундаментальная идея – обнаружение внутри изображения линий, сохраняющих топологическую структуру объекта.
Рис.7 Скелетизация изображения. Слева направо: исходное изображение, идеальный скелет и альтернативный скелет
Для построения каркаса изображения используется процесс «выжигания». Он заключается в том, что все граничные точки изображения удаляются до тех пор, пока это не будет приводить к разрыву фигуры. Существуют различные подходы к реализации процесса выжигания. Так как в данной работе скелет изображения необходим для определения точек пересечения, необходимо, чтобы в процессе выжигания не образовывались такие точки там, где они интуитивно быть не должны – чтобы не было нарушения топологии фигуры. Для достижения этого эффекта необходимо, чтобы процесс осуществлялся равномерно по всему контуру изображения.
Для обеспечения равномерности на каждой итерации сначала выделяется граница изображения, а потом из этой границы поочередно удаляются все точки, все соседи10 которых связны между собой даже в условии отсутствия других точек.
Точки скелета, имеющие более двух соседей, являются точками пересечения. Такие точки ввиду специфики построения скелета образуют связные области. При построении вектора признаков учитывается именно количество таких связных областей.
Точки скелета, имеющие ровно одного соседа, являются концевыми.
Распознавание символа по вектору признаков
Задача распознавания символа может рассматриваться как задача классификации11.
На входе имеется m-мерный вектор свойств изображения, его необходимо отнести к некоторому классу – символу. Все классы заранее известны:
33 строчные и 33 заглавные буквы русского языка12
Латинские символы, не присутствующие в предыдущем наборе символов: d D f F g G h i j J L m n N q Q r R s S t U v V w W z Z
Другие символы: . = ≡ *
Символы русского и английского языков, имеющие идентичное написание относятся к одному классу, т.к. распознаватель не обладает сведениями о принадлежности распознаваемого символа к тому или иному языку. Задача распознавателя – определить, на какой из имеющихся символов наиболее похоже входное изображение, описываемое данным вектором признаков.
Для решения этой задачи строится самообучающаяся система. В качестве алгоритма самообучения взят алгоритм SPSA. В качестве изначального приближения кластеров берутся векторы признаков некоторых изображений соответствующих символов13.
Алгоритм распознавания на основе SPSA
SPSA – Simultaneous Perturbation Stochastic Approximation – рандомизированный алгоритм типа стохастической оптимизации. Он активно разрабатывался на математико-механическом факультете СПбГУ [1,2,3,4,5]. Алгоритм хорошо показал себя в задаче самообучения, была теоретически обоснована его состоятельность [2].
Суть алгоритма заключается во внесении случайного независимого возмущения для приближения градиента Функционала качества.
Введем систему обозначений, аналогичную введенной в [2].
Входной вектор признаков x n ϵ Rm. Оценка векторов центров кластеров – матрица ηn ϵ Rr x m. Строки этой матрицы – векторы центров r кластеров.
В основе рассматриваемого рандомизированного алгоритма - использование случайного пробного возмущения. Δn ϵ Rr – вектор, состоящий из ±1, независимая случайная величина с распределением Бернулли по каждой из координат.
{αn} {βn} – бесконечно малые последовательности, ряд из которых расходится:
В качестве начального приближения центров кластеров  взяты вектора признаков вручную размеченных символов.
Правило итеративного построения приближения центров кластеров:
Здесь  – r-мерный вектор, составленный из значений характеристических функций  , k = 1, 2,…,r, определяющих принадлежность xn кластеру k. В данной задаче, он состоит из одной единицы на позиции соответствующей кластеру с центром, ближайшим к xn и нулей на остальных позициях.
Y( ) = Q() +  - r-мерные векторы, составленные из измеренных с помехами в соответствующих точках значений функций потерь; - соответствующие вектора из ошибок наблюдений. В данной задаче это квадраты расстояний до центров кластеров.
Подаваемая на вход распознавателя точка (вектор признаков) относится алгоритмом к кластеру с ближайшим центром, выдавая в качестве результата распознавания символ, определяемый этим кластером. Центр кластера изменяется с учетом случайного пробного возмущения. Это изменение является аппроксимацией градиента функции качества. Подробнее алгоритм рассмотрен в статье [2], в ней же приведено теоретическое обоснование состоятельности предлагаемых оценок.
Алгоритм SPSA отличается:
устойчивостью к почти произвольным помехам14, что компенсирует погрешность при построении вектора признаков;
устойчивостью к увеличению размерности пространства входов, что позволяет в дальнейшем изменять (увеличивать) структуру вектора признаков, например, добавляя в него дополнительные характеристики изображения, что позволит при необходимости увеличить точность распознавания;
простотой реализации, что особенно актуально в мобильных устройствах.
Одно из основных преимуществ данного подхода заключается в адаптивности алгоритма: при изменении со временем центров кластеров алгоритм сам подстроится под это изменение. Это обеспечивается за счет расходимости рядов {αn} и {βn}. Причиной изменения центров кластеров может быть как особенность фотокамеры, изменение типа бумаги или же изменение шрифта. Данный алгоритм не нуждается в переобучении.
К недостаткам алгоритма можно отнести зависимость от порядка поступления данных и тот факт, что на i-м шаге изменяется только тот кластер, к которому был отнесен входной вектор. Таким образом при некотором изначальном приближении центров кластеров15 возможна ситуация, когда все входящие элементы будут относиться к неправильным кластерам, а значит на каждом шаге будут изменяться центры не связанных с данным входом кластеров. Это теоретически может в редком случае привести к непредсказуемому изменению центров кластеров или, что более вероятно, к изменению значений кластеров – кластеры могут поменяться местами, вследствие чего классификатор вместо одного символа будет стабильно выдавать другой. Эту проблему можно решить, корректно выбрав изначальное приближение центров кластеров, а также с использованием словаря: при обнаружении постоянной замены одного символа на другой переименовывая соответствующий кластер.
Также недостатком подхода является невозможность введения «нераспознанного» символа. Любой входной вектор признаков будет отнесен к некоторому кластеру и повлияет на его центр. Таким образом, если на документах (чеках) будут присутствовать символы, не учтенные в системе, их появление на изображении будет изменять представление о других кластерах. Это связано с тем, что количество кластеров фиксировано.
|
