АДАПТИВНОЕ РАСПОЗНАВАНИЕ СИМВОЛОВ. (В. Л. Арлазаров, В.В. Троянкер, Н.В. Котович). ПРОДОЛЖЕНИЕ

Создание эталонов, формат, свойства, быстрый поиск эталонов

Рассмотрим этап создания базы эталонных характеристик. Эталонными характеристиками называются различные признаки символов, которые измеряются и/или вычисляются по символам из обучающей выборки. Базой характеристик называется список всех характеристик в виде готовом к распознаванию (обычно это двоичное представление), плюс система адресации или быстрого поиска в этом списке. Конкретный набор характеристик и способы их вычисления собственно и определяют некий алгоритм распознавания. Однако в данном случае нас не интересует какой-либо конкретный алгоритм.

Ниже следует подробное описание формы, в которой эталоны хранятся в базе характеристик. Один эталон соответствует одному кластеру, получившемуся в процессе кластеризации. Напомним, что кластер состоит из набора битовых растров символов, которые попали в этот кластер. Будем называть пиксел растра черным, если он принадлежит символу и белым, если фону изображения. Итак, на растровую сетку фиксированного размера Wmax x Hmax положим все растры символов (соответственно отцентрированные) и просуммируем внутри каждой ячейки. В соответствующую ячейку кластера запишем сумму (количество раз, которое в этой ячейке встретился черный пиксел). Очевидно, что это число является частотой или, если его нормировать на количество символов в кластере, вероятностью появления пиксела в этой ячейке. Ячейки, в которых вероятность равна нулю, заполняются по другому. Туда записывается расстояние до ближайшей точки с ненулевой вероятностью. Это расстояние будет трактоваться как "отрицательная вероятность" появления пиксела в этой ячейке. Таким решением модели придается симметричность, что, как будет показано впоследствии, упростит вычисление оценки точности распознавания. Кроме того это позволяет избежать напрасного расхода компьютерной памяти, которая выделена под все ячейки вне зависимости попадает в них что либо или нет. Само расстояние можно считать в различных метрических системах, например, как расстояние в евклидовом пространстве. Однако в последнем случае присутствует извлечение квадратного корня, что накладывает дополнительные условия: операции с числами в формате плавающей запятой и, что гораздо существенней, многократный вызов самой процедуры вычисления корня. Для ускорения операции вычисления расстояния допустимо использовать метрики пространства L1 , например, D(x,y) = x+y или D(x,y) = Max(x,y). Оба способа целочисленны и просты, а их отличия от евклидовой метрики для данной задачи не существенны.

Отвлекаясь от деталей, можно сказать, что эталон представляет собой центрированное в некоторой области двухмерное распределение вероятностей появления черных пикселов. Это распределение полностью описывает вероятностную природу класса символов(кластера). Именно эта информация является априорным знанием для этапа дораспознавания. В терминах описанной модели собственно процесс распознавания заключается в получении ответа на вопрос, насколько хорошо конфигурация черных пикселов символа совпадает с распределением данного кластера. Ответ будет получен в виде числа, означающего вероятность того, что поступивший на распознавание символ принадлежит кластеру, по эталону которого ведется распознавание.

База характеристик может содержать большое количество информации. Оценим его для средних значений всех параметров: Wmax = 128; Hmax = 64; N - среднее количество кластеров N = 50; Получаем 128 * 64 * 8 * 50 = 3276800 бит = 409600 байт. Как в случае любого крупного массива информации, встает вопрос быстрого поиска нужных данных. Практически это задача построения индекса - одна из основных, возникающих при создании любой СУБД. Точнее говоря, речь идет о создании специальной служебной информации (индекса), которая определяет эффективный способ поиска данных внутри некоторого множества. Эта задача в общем случае (когда природа данных неизвестна) не решена.

Применительно к теме работы необходимо сравнивать пришедший для распознавания символ не со всеми имеющимися кластерами, что было бы неэффективно, а с небольшим подмножеством наиболее близких. Наметим только возможные подходы к решению проблемы. Прежде всего ответим на вопрос, каким критериям должен удовлетворять индекс. Очевидно, что основным требованием является эффективное уменьшение количества операций, требуемых для нахождения элемента данных. Затем следует указать компактность (т.е. объем индекса должен быть настолько мал, насколько это возможно) и легкость модификации ( т.е. легкость перестройки индекса при очередном изменении множества данных). Последним критерием можно пренебречь в случае, когда известно, что исходное множество впоследствии не будет подвергаться модификации.

Наиболее очевидный способ - исследовать корреляцию между эталонами и по результатам сравнения символа с одним из эталонов принимать решение следует или не следует сравнивать этот символ со следующим эталоном. Другой путь состоит в том, чтобы на этапе обучения вычислять какой-либо признак или набор признаков у всех символов из обучающей выборки. Значение этого признака полагать адресом кластера, в который попал символ с данным значением признака. Далее в процессе распознавания вычислять этот признак у символа, поступившего на распознавание, и сравнивать его только с теми эталонами, которые этот признак адресует. Безусловно, что такой способ выбора подходящих кластеров будет ошибаться, и тем не менее, если процент ошибок не велик, то указанный способ может быть использован, например, в качестве начального шага. При этом в случае неудачи запускается линейный поиск по всем кластерам.