В данной работе сделана попытка дать подробное описание проблемы адаптации алгоритмов распознавания к входным символам на основе ана - polpoz.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
В данной работе сделана попытка дать подробное описание проблемы адаптации алгоритмов - страница №1/1

Адаптивное распознавание символов
В. Л. Арлазаров
В.В. Троянкер
Н.В. Котович

Содержание



Аннотация 1

Обзор подходов к распознаванию символов 1

Синтез двух подходов - путь к существенному увеличению качества распознавания
4

Математическая модель адаптивного распознавания 6

Схема работы адаптивного распознавания 9

Кластеризация 11

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

Дораспознавание 15

Литература 18


Аннотация


В данной работе сделана попытка дать подробное описание проблемы адаптации алгоритмов распознавания к входным символам на основе анализа статистики. Обоснована целесообразность применения адаптивной технологии, как подхода обеспечивающего существенное увеличение качества распознавания. Приведена математическая модель адаптивного распознавания. Предложена схема синтеза традиционных и адаптивных алгоритмов распознавания. Затронут широкий круг вопросов связанных с техническими проблемами возникающими при реализации.
Обзор подходов к распознаванию символов
В случае, когда речь идет о распознавании печатных символов следует упомянуть, что почти бесконечное разнообразие печатной продукции изготавливается при помощью ограниченного набора оригиналов символов, которые группируются по стилю (набору художественных решений), который отличает данную группу от других. Одна группа, включающая все алфавитные знаки, цифры и стандартный набор служебных символов, называется гарнитурой. Однако в широком кругу людей, имеющих дело с производством различного рода документации, утвердилось другое название гарнитуры - шрифт; этого термина мы и будем придерживаться в дальнейшем.
Итак любой печатный текст имеет первичное свойство - шрифты, которыми он напечатан. С этой точки зрения существуют два класса алгоритмов распознавания печатных символов: шрифтовой и безшрифтовый (omnifont). Шрифтовые или шрифтозависимые алгоритмы используют априорную информацию о шрифте, которым напечатаны буквы. Это означает, что программе ОРС должна быть предъявлена полноценная выборка текста, напечатанного данным шрифтом. Программа измеряет и анализирует различные характеристики шрифта и заносит их в свою базу эталонных характеристик. По окончании этого процесса шрифтовая программа оптического распознавания символов (ОРС) готова к распознаванию данного конкретного шрифта. ( В последнее время, задачи при решении которых требуется обучение стали ассоциироваться с применением нейронных сетей [6], однако здесь развивается технология не использующая НС). Этот процесс условно можно назвать обучением программы. Далее обучение повторяется для некоторого множества шрифтов, которое зависит от области применения программы.
К недостаткам данного подхода следует отнести следующие факторы:



  • Алгоритм должен заранее знать шрифт, который ему представляют для распознавания, т.е. он должен хранить в базе различные характеристики этого шрифта. Качество распознавания текста, напечатанного произвольным шрифтом, будет прямо пропорционально корреляции характеристик этого шрифта со шрифтами, имеющимися в базе программы. При существующем богатстве печатной продукции в процессе обучения невозможно охватить все шрифты и их модификации. К примеру, Полиграфбуммаш СССР в свое время стандартизировал около 15-20 различных шрифтов, в современных компьютерных системах верстки документов используется более 100 шрифтов. Другими словами, этот фактор ограничивает универсальность таких алгоритмов.




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



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

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


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


  • Реально достижимое качество распознавания ниже, чем у шрифтовых алгоритмов. Это связано с тем, что уровень обобщения при измерениях характеристик символов гораздо более высокий, чем в случае шрифтозависимых алгоритмов. Фактически это означает, что различные допуски и огрубления при измерениях характеристик символов для работы безшрифтовых алгоритмов могут быть в 2-20 раз больше по сравнению с шрифтовыми.




  • Следует считать большой удачей, если безшрифтовый алгоритм обладает адекватным и физически обоснованным, т.е. естественно проистекающим из основной процедуры алгоритма, коэффициентом надежности распознавания. Часто приходится мириться с тем, что оценка точности либо отсутствует, либо является искусственной. Под искусственной оценкой подразумевается то, что она существенно не совпадает с вероятностью правильного распознавания, которую обеспечивает данный алгоритм.

Достоинства этого подхода тесно связаны с его недостатками. Основными достоинствами являются следующие:




  • Универсальность. Это означает с одной стороны применимость этого подхода в случаях, когда потенциальное разнообразие символов, которые могут поступить на вход системы, велико. С другой стороны, за счет заложенной в них способности обобщать, такие алгоритмы могут экстраполировать накопленные знания за пределы обучающей выборки, т.е. устойчиво распознавать символы, по виду далекие от тех, которые присутствовали в обучающей выборке.




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




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

Синтез двух подходов - путь к существенному увеличению качества распознавания

Выше рассматривались особенности, достоинства и недостатки двух подходов к созданию алгоритмов ОРС. Из обзора следует, что достоинства и недостатки обоих подходов определяются одними и теми же свойствами алгоритмов: большей либо меньшей степенью универсальности, степенью достижимой точности распознавания и т.п. Сравнительные недостатки и достоинства обоих подходов сведены в таблицу.


Свойства

Шрифтовые алгоритмы

Безшрифтовые алгоритмы










Универсальность

Малая степень универсальности, обусловленная необходимостью предварительного обучения всему, что предъявляется для распознавания

Большая степень универсальности, обусловленная независимостью обучающей выборки от какой-либо системы априорной классификации символов

Точность распознавания

Высокая, обусловлена детальной классификацией символов в процессе обучения. А также тем, что материал распознавания находится строго в рамках классов, созданных в процессе обучения

Низкая (в сравнении с шрифтовыми алгоритмами), что обусловлено высокой степенью обобщения и огрубленными измерениями характеристик символов

Технологичность

Низкая (в сравнении с безшрифтовыми алгоритмами), обусловлена различными накладными расходами, связанными с поддержкой классификации символов

Высокая, обусловлена отсутствием какой-либо априорной системы классификации символов

Поддержка процесса распознавания со стороны пользователя

Необходима:
- на этапе обучения для задания системы классификации;

- на этапе распознавания для указания конкретных классов символов



Не требуется

Рассмотрение обоих подходов в сравнении друг с другом приводит к целесообразности их объединения. Цель объединения очевидна - получить метод, совмещающий одновременно универсальность и технологичность безшрифтового подхода и высокую точность распознавания шрифтового. Предпосылками для исследования в этом направлении послужил следующий круг идей и фактов. Любой алгоритм распознавания символов становится применим на практике при качестве распознавания 94-99%. “Дожимание” последних процентов, т.е. окончательная доводка алгоритма всегда является трудоемкой и дорогостоящей работой. Внутри сферы распознавания символов любой алгоритм имеет свою специфичную область действия, для которой он разработан и в которой проявляет себя наилучшим образом. В целом, путь увеличения качества распознавания лежит не в изобретении сверхинтеллектуального алгоритма, который заменит собой все остальные, а в комбинировании нескольких алгоритмов, каждый из которых сам по себе прост и обладает эффективной вычислительной процедурой. При комбинировании различных алгоритмов важно, чтобы они опирались на независимые источники информации о символах. В случае, если два алгоритма работают над сильно коррелированными между собой данными, то вместо увеличения качества распознавания будет увеличиваться суммарная ошибка. С другой стороны, знания о распознанных символах должны накапливаться и использоваться в последующих шагах процесса распознавания. Более того, как окончательный критерий можно использовать точный шрифтозависимый алгоритм, база характеристик которого построена прямо в процессе работы (“на лету”) по результатам предыдущих шагов распознавания. Метод, обладающий указанным выше свойством, будем называть адаптивным распознаванием, т.к. он использует динамическую настройку (адаптацию) на конкретные входные символы.


Математическая модель адаптивного распознавания
В модели приняты следующие допущения:


  • Символы обучающей выборки и материала распознавания принадлежат единственному шрифту. Обобщение этой модели на случай произвольного количества шрифтов требует отдельного исследования.




  • Все символы внутри одного цикла адаптивного распознавания имеют одинаковую степень искажений, вносимых процессами печати и сканирования. Это предположение отвечает ситуации, когда единицей цикла является одна страница текста.




  • Имеется некий готовый шрифтонезависимый алгоритм с определенным качеством распознавания. В данном случае не важно, откуда взялся этот алгоритм, каким образом он анализирует символы, его особенности и детали реализации.




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

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


P- качество распознавания, полученное на этапе первичного распознавания
- мера искаженности символов, дает числовое выражение количеству случайных изменений в конфигурации пикселов среди экземпляров символов, обозначающих одну и ту же букву алфавита.
F- финальное качество распознавания достижимое с помощью шрифтозависимого алгоритма адаптированного к данной выборке символов.
V- надежность распознавания символа; , где x-расстояние от данного символа до центра кластера(идеального символа). Функция f является частью конкретного алгоритма вычисления расстояния между символом и кластером. Зависимость надежности от расстояния до идеала указывает на интуитивно очевидную связь между надежностью и отличием символа от идеала. Зависимость надежности от качества первичного распознавания отражает тот факт, что при зафиксированном х надежность может быть различной в зависимости от качества материала из которого составлен кластер.
Предположим выбрана метрика, т.е. функция отображающая отличия между символом и кластером в действительное положительное число (расстояние). Основное положение модели заключается в том, что расстояние от символа пришедшего на распознавание до кластера есть нормально распределенная случайная величина с плотностью вероятности.


Тогда по заданной минимальной допустимой надежности Vmin вычислим максимальное расстояние Xm на которое символ может отклониться от кластера и при котором


Далее по определению функции распределения [2] получаем


Это равенство дает ответ на вопрос каким будет качество распознавания при заданных надежности и мере искаженности символов. Наоборот, измерив на представительной выборке качество распознавания, можно по таблице [5] выяснить с какой надежностью получен этот результат.
Большой практический интерес представляет измерение величины  - среднеквадратичного отклонения; т.к. она придает числовое выражение важному понятию - “качество текста”. В этой модели  обретает конкретный физический смысл - описывает вариации которые возникают в конфигурации пикселов, описывающих оригинал символа, в процессах печати и сканирования. Применение шкалы основанной на мерах рассеяния подобной вышеупомянутой найдет применение в различных аспектах распознавания символов. Перечислим наиболее важные:


  • Верификация результатов кластеризации. Имеется ввиду, что кластер с рассеянием существенно отличным от среднего по выборке должен вызывать подозрение и являться кандидатом на дополнительную проверку.




  • Динамическая настройка различных пороговых констант, управляющих распознаванием.




  • Экстремальные значения  могут указывать на ситуацию в которой сама адаптация к данной выборке является не выгодной ибо необходимая статистическая информация в ней отсутствует.




  • Автоматическая селекция документов для дальнейшей обработки.

Интересным с практической точки зрения является вопрос о том, насколько близки параметры реального кластера к параметрам разработанной здесь модели. Ниже приводится оценка, позволяющая определить как с ростом количества символов параметры кластера сходятся к теоретическим.


Возьмем произвольную ячейку кластера. Пусть p - вероятность появления здесь черного пиксела при очередном добавлении символа в этот кластер. Очевидно, что эта вероятность фиксирована самой моделью и зависит только от положения ячейки внутри сетки. Таким образом процесс появления черных пикселов в данной ячейке удовлетворяет схеме испытаний Бернулли. В процессе физической реализации попадания символов в кластер в этой ячейке существует  - частота попадания сюда черного пиксела. Это случайная величина, сосредоточенная около p и по центральной предельной теореме[2] отклоняющаяся от нее согласно нормальному закону распределения, следовательно

где
- квантиль уровня 


 - уровень значимости
N - количество символов в кластере

Это неравенство выполняется с вероятностью . Упростим неравенство, учитывая что .




с вероятностью не меньшей чем . Зададимся количеством символов N=121(смотри оценку количества букв на странице текста) и предположим , тогда это соответствует уровню значимости 0.0618 и в итоге получаем, что наше предположение выполняется с вероятностью не меньшей чем . В этом рассуждении не накладывалось никаких специфичных условий на ячейку, следовательно вывод справедлив для всех ячеек данного кластера. Таким образом можно утверждать, что при указанном объеме кластера в почти 90% его ячеек абсолютная погрешность отклонения от модели составит не более 0.07. Фактически вероятность будет даже больше, т.к. благодаря упрощению неравенства мы получили лишь оценку снизу. При разработке конкретной процедуры вычисления расстояния до кластера или надежности встает вопрос о корректности сравнения физически получаемых значений с константами выработанными посредством мат. модели. Обладая подобным механизмом, можно измерить и компенсировать некорректность такого сравнения.
Схема работы адаптивного распознавания

Рассмотрим подробнее схему, объединяющую оба подхода. Функционирование схемы разделяется на несколько этапов: первичное распознавание, сбор статистики, кластеризация собранной статистики, формирование эталонов (базы характеристик), дораспознавание.


Кратко определим каждый из названных этапов.
- Первичное распознавание означает распознавание всей страницы с помощью шрифтонезависимого алгоритма.
- Сбор статистики подразумевает процесс отбора надежно распознанных символов, которые впоследствии составят обучающую выборку для шрифтозависимого алгоритма.
- Кластеризация - разбиение обучающей выборки на кластеры(классы). С помощью такого разбиения уточняются результаты распознавания, полученные на этапе первичного распознавания, будет выявлена статистическая структура страницы, т.е. получен ответ на вопрос: группируются ли одинаковые символы на данной странице, подготовлен исходный материал для обучения шрифтозависимого алгоритма.
- Формирование эталонов это создание окончательных, двоичных наборов данных (базы характеристик), по которым будет производиться дораспознавание.
- Дораспознавание - второй проход распознавания по всей странице с целью уточнить результаты первичного распознавания, выставить адекватные оценки точности, дораспознать то, что было не распознано ранее, отметить ненадежно распознанные символы.
При разработке объединенного метода распознавания прежде всего необходимо определить объем информационной единицы, над которой должен работать метод. Имеется в виду количественная иерархия, а именно: символ, группа символов, слово, строка символов, страница текста, пакет страниц. По следующим причинам был выбран уровень одной страницы текста:
- это естественная единица информации, которая существует безотносительно проблематики ОРС;
- это достаточно крупная единица, для того чтобы собранная статистика была вполне представительна. Например, количество символов на обычной машинописной странице - 2000, относительная частота буквы “н” в русском языке 0.053; таким образом на странице текста количество букв “н” в среднем составляет 2000 х 0.053 = 106. Этого вполне достаточно для оценки статистических параметров выборки по данной букве, разбиения на классы (кластеризации) и построения двоичных эталонов для дораспознавания.
Рассмотрим подробнее этапы, из которых состоит алгоритм адаптивного распознавания символов. Итак, первым этапом является распознавание всей страницы с помощью шрифтонезависимого алгоритма (первичное распознавание). В данном случае не важно, откуда взялся этот алгоритм, каким образом он анализирует символы, его особенности и детали реализации. Предположим, имеется некий готовый шрифтонезависимый алгоритм с заданным качеством распознавания. Все символы, распознанные с надежностью, превышающей заданный порог, считаются материалом для обучения базы характеристик. Важно отметить, что на этапе первичного распознавания нет необходимости добиваться повышения качества распознавания, например за счет усложнения самого алгоритма или отдельного кодирования всех специальных случаев (в которых основной алгоритм работает неудовлетворительно); простота и эффективность основной процедуры алгоритма важнее, чем высокий процент качества или проработка спецслучаев.
На практике чрезвычайно полезной является верификация символов-кандидатов в обучающую выборку, т.е. проверка правильности распознавания с помощью независимого метода. Например словарный контроль, частотные двухбуквенные и трехбуквенные сочетания (диады и триады) и т.п. Верификация необходима для того, чтобы снизить количество ошибок в символах, на которых впоследствии будет проводиться обучение. Отсутствие ошибок в обучающей выборке важно, т.к. любая ошибка может привести к формированию ложного эталона распознавания, что в свою очередь приведет к систематической ошибке на этапе дораспознавания. Выше, при перечислении этапов, на которые делится метод адаптивного распознавания, верификация не была выделена в отдельный этап, т.к. в этом методе она не играет принципиальной роли.
Кластеризация
Необходимость разбиения совокупности объектов на несколько групп нередко возникает в самых разных областях знаний - как, например, классификация различных видов бабочек в биологии или классификация языков Новой Гвинеи в лингвистике. Задачей кластеризации и называется задача расклассификации предъявленных объектов по нескольким группам, причем число групп не обязательно известно. Каждую полученную группу часто называют кластером. Существуют разные математические методы и подходы к решению задачи кластеризации [1].
Одним из методов является метод цепной развертки, кратко опишем его. В этом методе в качестве исходного берется любой объект из предъявленной совокупности , ему приписывается номер 1 и расстояние 0. Затем просматриваются все оставшиеся объекты. Выбирается объект, расстояние от которого до исходного элемента минимально. Ему присваивается номер 2 и расстояние, равное расстоянию до исходного объекта. Затем среди оставшихся ищется объект, расстояние от которого до уже отмеченного множества объектов из двух элементов минимально, и т.д. - всегда на очередном шаге выбирается объект, расстояние от которого до уже пронумерованных объектов ( как расстояние до множества ) минимально, ему приписывается очередной номер и это расстояние. Процедура повторяется пока все объекты не будут пронумерованы. В результате все объекты будут выстроены в некотором порядке, и каждому объекту приписано некоторое число - расстояние до предшествующего множества.

Теперь для того, чтобы разделить исходное множество на несколько кластеров таким образом, чтобы расстояние между любыми объектами, входящими в разные кластеры, было больше заданного расстояния d0, а для любых объектов из одного кластера (p1,p2) можно было найти объекты из того же кластера (обозначим их o[1],o[2],..,o[n]) , такие что o[1]=p1, o[n]=p2, и для любого i, i < n расстояние между соседними объектами d(o[i],o[i+1]) не больше d0, достаточно просто просмотреть все приписанные объектам расстояния и пометить те из них, которые больше d0. Пусть это будут номера N1,N2,...,Nk. Тогда к первому кластеру следует отнести все объекты с номерами меньше N1, ко второму все объекты с номерами от N1 до N2 и т.д. После процедуры цепной развертки также легко проводить анализ - при каких значениях порога d0 возникают разные варианты кластеризации, как эти варианты соотносятся между собой и многое другое. Но как легко видеть, данная процедура требует N*(N-1)/2 процедур вычисления расстояния между объектами, если всего имеется N объектов, поэтому бывает необходимо в связи с повышением быстродействия использовать иные приемы. Примером как правило более быстрого варианта кластеризации можно привести модификацию описанного выше метода - кластеризацию с фиксированным порогом. В качестве исходного берется любой символ, ему присваивается принадлежность к первому кластеру. К данному первому кластеру присоединяются все символы, принадлежность которых к какому-либо кластеру еще не установлена, и расстояние от которых до исходного символа меньше порога d0. Затем для каждого из вновь присоединенных символов данная процедура повторяется . После того как к первому кластеру никто не может быть больше отнесен, среди символов, которые остались, берется произвольный символ в качестве затравочного для второго кластера и т.д. пока не будут исчерпаны все символы. В худшем случае и здесь при наличии N символов надо N*(N-1)/2 процедур вычисления расстояния, но в лучшем случае всего N процедур.


Конечно, важнейшую роль в кластеризации играет выбранная метрика, т.е. что понимается под расстоянием между объектами. При разном выборе метрики естественно возникают разные варианты кластеризации. Какую метрику использовать применительно к символам? Учитывая то, что к одному и тому же кластеру желательно отнести как хорошо пропечатанные и отсканированные , так и дефектные символы одинакового размера и начертания ( как это сделал бы человек ), кажется естественным прибегнуть к побитовому (поточечному) сравнению растров. Как видно из описания процедуры кластеризации, она может потребовать много операций вычисления расстояний между различными изображениями символов. Поэтому кроме того, что выбранная метрика должна по возможности быть устойчива к различным дефектам изображения ( как уже бывшим в исходном изображении, так и появившимся после сканирования ), метрика должна допускать быстрое вычисление.
Если просто подсчитывать число несовпадающих точек в двух разных растрах, то возникает проблема центрирования - смещение даже на один пиксел может вызвать большой скачок при вычислении расстояния. Кроме того, изменение жирности символа всего на один пиксел ( что нередко возникает при сканировании даже текстов хорошего качества, не говоря о текстах плохого качества ) также вызывает большое изменение при вычислении расстояния простым сравнением. Поэтому представляется разумным вычислять расстояние между символами, основываясь на метрике Хаусдорфа.
Кратко напомним определение метрики Хаусдорфа. Пусть в некотором пространстве определено расстояние между точками, обозначим его d(x,y). Тогда расстояние от точки x до множества Y d(x,Y) определяется как нижняя грань расстояний d(x,y) для y из Y. Расстояние от множества X до множества Y d1(X,Y) определяется как верхняя грань расстояний d(x,Y) для всех x из X. Расстояние Хаусдорфа между множествами X,Y d(X,Y) определяется как максимум расстояний от X до Y и от Y до X, т.е. d(X,Y)=max(d1(X,Y),d1(Y,X)). Таким образом, разные множества в метрике Хаусдорфа близки, если и только если для любой точки из одного множества в ее малой окрестности содержится хотя бы одна точка другого множества (и то же самое для другого множества).
В случае символов можно рассматривать расстояние между символами как расстояние Хаусдорфа между множествами точек, составляющих разные символы. Но необходимо заметить, что вычисление расстояния Хаусдорфа "в лоб" требует слишком много вычислений даже для проверки того, что это расстояние между символами больше или не больше единицы. Для того чтобы проверить все точки растра, надо проверить каждую точку - черная она или белая, т.е. принадлежит символу или нет, и если принадлежит, надо проверить до восьми ее соседей, т.е. при средней заполненности растров на четверть и при размерах растров m на n может потребоваться до 2*(m*n*3/4+m*n*9/4)=6*m*n элементарных операций.
Поэтому полезно использовать некоторые приемы для оценки расстояния Хаусдорфа. Для эффективного вычисления расстояния между символами используется следующий прием. Для каждого символа помимо собственно изображения создается растр, в котором кроме исходных точек содержатся также точки окрестности ("размазанное" изображение). После чего вычисление расстояния между символами сводится к простому выявлению пикселов одного растра, которые не вошли в "размазанное" изображение другого символа. Таким образом требуется одна операция для одного байта (для восьми пикселов) растра - исключающее "или", или две операции - если надо узнать и количество пикселов, выходящих за рамки единичной (или иной) окрестности. Следовательно надо не больше 2*(m*n*2/8)=m*n/2 элементарных операций.
Создание эталонов, формат, свойства, быстрый поиск эталонов

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


Ниже следует подробное описание формы, в которой эталоны хранятся в базе характеристик. Один эталон соответствует одному кластеру, получившемуся в процессе кластеризации. Напомним, что кластер состоит из набора битовых растров символов, которые попали в этот кластер. Будем называть пиксел растра черным, если он принадлежит символу и белым, если фону изображения. Итак, на растровую сетку фиксированного размера 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 байт. Как в случае любого крупного массива информации, встает вопрос быстрого поиска нужных данных. Практически это задача построения индекса - одна из основных, возникающих при создании любой СУБД. Точнее говоря, речь идет о создании специальной служебной информации (индекса), которая определяет эффективный способ поиска данных внутри некоторого множества. Эта задача в общем случае (когда природа данных неизвестна) не решена.
Применительно к теме работы необходимо сравнивать пришедший для распознавания символ не со всеми имеющимися кластерами, что было бы неэффективно, а с небольшим подмножеством наиболее близких. Наметим только возможные подходы к решению проблемы. Прежде всего ответим на вопрос, каким критериям должен удовлетворять индекс. Очевидно, что основным требованием является эффективное уменьшение количества операций, требуемых для нахождения элемента данных. Затем следует указать компактность (т.е. объем индекса должен быть настолько мал, насколько это возможно) и легкость модификации ( т.е. легкость перестройки индекса при очередном изменении множества данных). Последним критерием можно пренебречь в случае, когда известно, что исходное множество впоследствии не будет подвергаться модификации.
Наиболее очевидный способ - исследовать корреляцию между эталонами и по результатам сравнения символа с одним из эталонов принимать решение следует или не следует сравнивать этот символ со следующим эталоном. Другой путь состоит в том, чтобы на этапе обучения вычислять какой-либо признак или набор признаков у всех символов из обучающей выборки. Значение этого признака полагать адресом кластера, в который попал символ с данным значением признака. Далее в процессе распознавания вычислять этот признак у символа, поступившего на распознавание, и сравнивать его только с теми эталонами, которые этот признак адресует. Безусловно, что такой способ выбора подходящих кластеров будет ошибаться, и тем не менее, если процент ошибок не велик, то указанный способ может быть использован, например, в качестве начального шага. При этом в случае неудачи запускается линейный поиск по всем кластерам.
Дораспознавание
Дораспознавание есть повторный проход по всей странице с целью распознать все, что не распознано на первом проходе и получить для всех символов надежные оценки точности распознавания. При дораспознавании включается в работу шрифтозависимый алгоритм с базой характеристик, настроенной (адаптированной) к символам текущей страницы. Рассмотрим детально процедуру шрифтового распознавания, она очевидно привязана к формату эталона (см. предыдущий раздел). Итак, схема основной процедуры проста. На вход поступил очередной символ, требующий распознавания; он представлен в форме битового растра. Сравнивая этот символ с первым эталоном (кластером), получаем численную оценку сходства символа с эталоном. Повторяем сравнение со всеми остальными эталонами в базе. После этого выбираются несколько наилучших ответов в соответствии с полученными оценками.
Рассмотрим правила, по которым осуществляется само сравнение растра с эталоном. Сначала минимальный охватывающий прямоугольник символа центрируется относительно сетки эталона. Далее предполагается, что центр символа и центр эталона точно совмещены. Проблемы и ошибки, возникающие при центрировании, будут обсуждены ниже. Затем вычисляется сумма вероятностей по всем точкам эталона, соответствующим черным пикселам растра символа. Далее полученная сумма нормируется, (т.е. приводится к обычной шкале вероятностей от 0 до 1) и умножается на масштабный коэффициент. Математическая запись для процесса вычисления оценки сравнения растра с эталоном имеет следующий вид:

где
pi - вероятность в i-той ячейке эталона


W - нормирующий коэффициент
С - масштабный коэффициент
a - порог, управляющий точностью
Из формулы видно, что влияние точек с “отрицательными вероятностями” на результат усилено; т.е. точки символа, лежащие на расстоянии a и более от положительных, существенно уменьшают общую оценку. Таким образом, в случае, если символ существенно отличается от эталона он гарантированно не получит высокую оценку точности распознавания. Обратимся к функции порога а. Этот порог отмечает то значение вероятности, о котором можно уверенно сказать, что оно указывает на то, что в данную ячейку черные пикселы попадать не должны. Фактически порог нужно устанавливать на первое целое число, большее по модулю, чем суммарная погрешность, возникающая при создании эталона и совмещении эталона с символом. Например, в случае, если все операции проводятся с точностью 1-1,5 пиксела, то порог можно установить равным -2 (минус двум). Таким образом, манипулируя порогом, можно менять “строгость” формулы. В качестве нормирующего коэффициента следует брать сумму вероятностей по всем положительным ячейкам. Полученная таким нормированием оценка не является вероятностью в строгом смысле этого слова по нескольким причинам, в частности, потому что “отрицательные вероятности” в ячейках эталона являются искусственными. Однако такая оценка отвечает интуитивному представлению о мере близости и хорошо зарекомендовала себя на практике. Масштабный коэффициент присутствует в формуле для удобства работы с результатом. Он переводит результат в стандартный для системы числовой интервал. В общем случае он может быть опущен.
Вернемся к проблеме центровки символа при наложении его на сетку эталона. Наиболее широко употребляемым и самым простым способом центровки является совмещение геометрических центров сетки и охватывающего прямоугольника символа. Фактически такой способ сам по себе работает неудовлетворительно и при практическом использовании он дополняется возможностью накладывать объекты не только по центрам, но и по небольшим их окрестностям с последующим выбором наилучшего результата. Среди других способов совмещения следует упомянуть совмещение по центрам тяжести и совмещение по осям медианы. К сожалению оба способа также обладают недостатками. Вычисление центра тяжести дает большие погрешности по причине того, что в растре все пикселы имеют равные веса. Совмещение по осям медианы работает хорошо только на объектах типа “пятно”, т.е. на связных объектах, у которых нет различного рода сужений и перешейков. Для большинства букв это условие не выполняется, таким образом этот метод имеет весьма ограниченные возможности применения. Вообще, можно сказать, что проблема нахождения реперных точек, точно описывающих положение растра, еще только ожидает своего решения.
Существует еще один аспект, который следует отнести к области дораспознавания. Его можно определить как взаимодействие между двумя независимыми проходами распознавания. Проблема заключается в следующем: после первого прохода (первичного распознавания) страница некоторым образом распознана. Затем на этапе дораспознавания возникает ситуация, когда два алгоритма по разному распознают один и тот же символ. Проблема усугубляется в случа е разрезания/склеивания, когда оба алгоритма предлагают разные цепочки символов. Иными словами встает вопрос о схеме, которая разрешает конфликты между разными этапами распознавания. Очевидно, что основное требование к такой схеме заключается в том, что она с одной стороны не должна ухудшать результаты распознавания, полученные на первом проходе, а с другой стороны должна максимально использовать потенциал второго этапа. Детали функционирования такой схемы сильно зависят от особенностей алгоритмов, генерирующих распознанный текст. Однако в ней существуют части, не зависящие от конкретных внешних факторов. Фундаментом схемы является процедура разбиения входного потока символов на взаимно не перекрывающиеся (в геометрическом смысле) цепочки. Такая цепочка может содержать от одного символа до целого слова. В данном случае предполагается, что пробел всегда разделяет соседние слова. Разбиение на не перекрывающиеся и тем самым независимые цепочки (блоки) позволяет впоследствии однозначно разрешать все конфликты на уровне одной цепочки. Схема функционирует следующим образом: получает очередное слово, проверяет правильность распознавания и уточняет оценки. Если есть подозрение, что хотя бы одна буква распознана не верно - все слово отправляется на перераспознавание шрифтозависимым алгоритмом. Затем слово разбивается на цепочки, а это всегда можно сделать по определению цепочки. И на уровне каждой цепочки решается вопрос: результат какого из этапов, первичного распознавания или дораспознавания, лучше. Существует целый спектр различных подходов к проблеме выбора наилучшего результата [7]. В конкретных условиях данной задачи применяется простейшее сравнение с пороговыми константами. Далее из лучших цепочек формируется слово.

Литература


1. Сборник Классификация и кластер. М.: "Мир", 1980

2. Розанов Ю.А. Теория вероятностей, случайные процессы и математическая статистика. М.: “Наука”, 1989

3. Ян Д.Е., Анисимович К.В., Шамис А.Л. Новая технология распознавания символов. Теория, практическая реализация, перспективы. М.: Препринт, 1995

4. Промахина И.М., Коростелев А.П. Об одном классе вероятностных рекуррентных алгоритмов распознавания. М.: Препринт, 1984

5. Корн Г., Корн Т. Справочник по математике. М.: “Наука”, 1984

6. Y-H Pao Adaptive pattern recognition and neural network “Addison-Wesley” 1989



7 Журавлев Ю.И. Алгоритмы вычисления оценок и их применение Ташкент, “Фан” 1974



3/2/2015



izumzum.ru