Методы распознавания грубых объектов О. А. Славин, Г. В. Корольков, П. В. Болотин

Методы распознавания грубых объектов
О.А. Славин, Г.В. Корольков, П.В. Болотин
Аннотация
В настоящей работе рассматриваются причины, механизмы и результаты применения алгоритмов распознавания, использующих упрощенные представления образов символов. Приведены примеры трех методов распознавания грубых объектов и схема их композиции. Описаны процедуры оптимизации и даны рекомендации по использованию описанных алгоритмов.
1. Введение
Важнейшей процедурой, предшествующей распознаванию образа символа, является нормализация образа по различным параметрам, например, углу наклона, толщине линий . Наиболее часто производят нормализацию по размерам или масштабирование, решая при этом ряд задач, таких как унификацию эталонов распознавания, уменьшение размеров объекта распознавания. Последнее обстоятельство может снижать вариативность образов символов, за счет чего повышается качество распознавания на одних и тех же эталонных наборах, что особенно важно для омнифонтовых систем распознавания текстов OCR [1] и систем распознавания рукописных и рукопечатных символов ICR. Очень часто перед распознаванием образы кириллицы или латиницы масштбируют до размеров 16 на 16 [2]. Возникает вопрос : до каких пор можно увеличивать масштаб, не теряя работоспособности последующих алгоритмов распознавания.

В системе ввода в компьютер печатных текстов Cuneiform [1] используется несколько алгоритмов, базирующихся на масштабных сетках 3 на 5 и 5 на 3. Далее будет рассказано о свойствах такого масштабирования и месте алгоритмов распознавания грубых объектов в реально работающих системах ввода документов.

2. Обоснование выбора параметров 3 и 5
Конфигурация 3 на 5 известна достаточно давно. Так в [3] словарь, в котором комментируется смысл бинома 3х5, датирован 100 г. н.э., а самой паре 3 и 5 дано обозначение “САНЬ У”. Там же приведены схемы созвездий, сопоставленные с сетками 3х5 и 5х5 (см. рис. 1). Как видно из него созвездия обладают достаточно простой структурой, допускающей разнесение по клеткам 3х5.

Рис 1. Примеры созвездий в китайской схеме САНЬ У

Рис 2. Русские буквы с пятичленной вертикальной (Е) и горизонтальной (Н,П,Ш) структурой

На рис. 2. можно усмотреть, что четко напечатанные русские буквы серифного шрифта имеют до пяти вертикальных элементов и горизонтальных элементов. Например, заглавная буква ‘Е’ обладает тремя горизонтальными линиями и двумя промежутками между ними, а заглавная буква ‘Ш’ – тремя вертикальными линиями и двумя промежутками. У многих букв таких элементов не более трех, как, например у ‘Н’ и ‘П’. Иными словами, можно было бы нарисовать шрифт с постоянным размером букв 5 на 5, и эти буквы можно было бы легко читать и распознавать, несмотря на их низкое качество прорисовки (см. рис. 3). Если же рассматривать не буквы двухцветного шрифта, а серые (полутоновые) образы размеров меньших 5, то есть шанс сохранить информацию для различия как трехэлементных, так и пятиэлементных букв.

Рис 3. Начертания русских букв на сетке 5х5

Проведем ряд экспериментов, связанных с алгоритмами обучения и распознавания сильно сжатых образов. Прежде всего, дадим определение сжатия бинарного (черно-белого) изображения произвольного размера к серому (полутоновому) образу меньшего размера. Пусть B(m,n) – матрица исходного бинарного растра с размерами m на n. Тогда преобразование растра B в полутоновой растр G(M,N) назовем сжатием. Формально определим сжатие следующей процедурой. Сначала выполним преобразование матрицы B в матрицу B¹(mM,nN) по следующему правилу

B¹_pq = B_lk , где m( l -1 )  ml и n( k -1 )  nk.

Затем определим

mi nj

||G_ij|| =   B¹_pq

p=m(i-1)+1 q=n(j-1)+1

После этой операции отнормируем матрицу серого растра G. Полученный сжатый растр мы будем использовать в качестве вектора, получаемого из матрицы ||G_ij|| следующим образом

(G_1,1; G_1,2; … G_1,M; G_2,1; G_2,2; … G_2,M; ••• G_N,1; G_N,2; … G_N,M ).

В качестве материала для обучения и тестирования для простоты возьмем 2000 образов русских букв серифного шрифта TimesNewRoman одного кегля, половина из которых будет использована для обучения, а половина для тестирования, и поместим их в графическую базу данных, хранящую как собственно изображения, так и коды назначенных им символов. В процессе обучения каждый образ, соответствующий какой-то из букв C, будем сжимать до определенного размера, а сжатые образы E_i(C) одной буквы, рассматриваемые как векторы, просуммируем между собой. Тем самым к концу обучения мы сможем вычислить средний вектор E(C) для каждой буквы и отнормировать его на единичную длину, то есть создать массив эталонов по числу различных букв в базе данных. Прописные и строчные начертания для всех букв, кроме ‘А’, ’Б’ и ’Е’, после сжатия становятся одинаковыми, поэтому мы не будем для них заводить раздельных эталонов. По массиву {E₁ , E₂ , … , E_m} эталонов и исследуемому сжатому образу X , одной размерности с эталонами и отнормированного на единичную длину, мы перебором определим один или несколько эталонов (в наших экспериментах будем определять четыре ближайших эталона), расстояние до которых от X меньше, чем до любого другого эталона (технически удобно искать эталоны с максимальным скалярным произведением (X,E_i) ). Соответствующие этим ближайшим эталонам коды C_i, породивших их символов, и расстояния P_i до них образуют коллекцию

{(C₁,P₁), … , (C_k,P_k)}

альтернатив распознавания. Назовем точностью распознавания (на конкретной базе графических образов) процент совпадений известного кода символа из базы данных с кодом C₁ ведущей альтернативы коллекции по отношению к общему числу символов в базе, а полнотой коллекции - процент совпадений кода символа из базы с кодом C_i какой-нибудь альтернативы коллекции. Определим точность, полноту коллекции и быстродействие (среднее количество распознанных символов в секунду) для различных конфигураций сжатого изображения (см. таб.1). Все вычислительные эксперименты для этой работы проводились на персональном компьютере с процессором Intel Pentium MMX с частотой 200 мегагерц, объемом оперативной памяти типа EDO 64 мегабайт и объемом кэш-памяти 512 килобайт. Программы обучения и тестирования представляют собой 32-разрядные приложения, созданные в среде Microsoft Developer Studio 97 (далее MDS 97).

Сетка	Точность распознавания (%)	Полнота коллекции (%)	Быстродействие (символов в секунду)
3 х 3	95	98.5	33.5
3 х 5	99.1	99.7	25.1
5 х 5	99.5	99.7	17.6

Таб.1. Характеристики распознавания сжатых растров для различных степеней сжатия.

Из таб. 1. видно, что, несмотря на повышение скорости работы на сетке 3х3, точность и полнота коллекции этого алгоритма резко снижаются по отношению к конфигурации 3х5. В то же время, распознавание растров, сжатых до размеров 3х5 и 5х5, приводит почти к одинаковой полноте коллекции, в то время как быстродействие алгоритма 3х5 выше быстродействия 5х5. Точность распознавания алгоритма 5х5 почти вдвое больше точности 3х5, однако, детальный анализ ошибок показывает, что повышение точности достигнуто на реально близких свертках 3х5, таких как свертки символов ‘И’, ‘Н’, для которых необходимы дополнительные исследования, о которых будет сказано ниже в части 4 настоящей работы. Одновременное использование грубых алгоритмов и анализаторов геометрии образа символа приводит к тому, что системные ошибки, связанные с объективной близостью сверток различных символов устраняются почти полностью, и точности методов 3х и 5х5 скомбинированных с геометрическими анализаторами сближаются. Иными словами, с учетом геометрических анализаторов точность 3х5 равна точности 5х5. Соотношения между характеристиками таб. 1. сохраняются качественно и в более сложных экспериментах, что позволяет сделать вывод о приемлемости использования сетки 3х5 для распознавания символов. Эталоны 5х3 могут использоваться для уточнения результатов распознавания по основному набору эталонов 3х5.

Выше был рассмотрен случай упрощенного обучения на одном шрифте, при котором образовывалось ровно по одному эталону на каждый символ. Реально приходится вести систему кластеров типа ‘шарообразное скопление’ [4], каждый из которых порождает усреднением своих элементов один эталон. Целесообразно объединять эталоны по буквам и по геометрическому сходству эталонов различных букв. Этим обеспечивается гибкость доступа к эталонам разного начертания одного символа и эталонам одного начертания различных символов.

Если достаточно большой объем различных печатных образов кластеризовать в две таблицы форматов 3х5 и 5х3 и объединить их, то такую таблицу можно использовать для реального омнифонтового распознавания печатных символов. Метод 3х5, обученный на одном миллионе образов, порождает набор D примерно из 1000 эталонов, обеспечивает точность 96 % и полноту коллекции 99.8% на тестовой базе BT в 10000 образов, составленную из символов печатных шрифтов типа Академический, Times и Courier. Оценки этим характеристикам будут даны ниже. Дальнейшие эксперименты будут производиться на этом наборе эталонов D и на этой тестовой базе BT.

3. Свойства метода 3х5
Выше были даны определения точности распознавания, полноты коллекции и быстродействию. Остановимся на этих свойствах подробнее и выявим еще несколько характеристик методов распознавания.
Точность метода 3х5, как это было указано выше, составляет 95-97 процентов для омнифонтового и 98-99 процентов для шрифтового распознавания печатных символов. В первом случае метод нуждается в комбинировании с другими методами для улучшения результатов, о чем будет написано ниже, а во втором случае точность вполне приемлема. В адаптивных многопроходных системах распознавания с обучением [5], улучшающих результаты первичных алгоритмов, точность, равная 99 процентам, является достаточной для процесса обучения по странице.
Быстродействие метода 3х5 даже для описанной омнифонтовой таблицы из 1000 эталонов является достаточно высоким (700 распознаваний в секунду). Увы, с ростом числа эталонов быстродействие падает пропорционально этому росту. Однако, не следует забывать и о выигрышных ситуациях, когда метод 3х5 работает на сильно ограниченных алфавитах в случаях комбинирования с другими методами или на заведомо малых таблицах эталонов в шрифтовых или адаптивных многопроходных системах.
Полнота коллекции является очень важной характеристикой любого метода распознавания. Во-первых, многие словарные и лингвистические механизмы дораспознавания и коррекции основного распознавания ориентируются именно на полноту коллекции, предполагая наличие правильных альтернатив в ошибочных по первой альтернативе коллекциях. Во-вторых, в условиях нескольких методов, отрабатывающих последовательно, возможно постепенное улучшение результирующей коллекции, и для этого важны промежуточные альтернативы. Характеристика полноты допускает интуитивные обобщения, связанные величиной оценок правильных не первых альтернатив в коллекциях с неправильными первыми альтернативами. Во всех случаях полнота коллекций метода 3х5 является очень хорошей для последующего комбинирования с чужими коллекциями и коррекции лингвистическими средствами.

Информативность оценок состоит в возможности сопоставления величиные оценки надежности распознавания. Критическими являются случаи, когда распознаванию доверять нельзя, и когда можно доверять без дальнейших дораспознаваний и проверок операторами. Для метода 3х5 в силу его природа (наложение образов друг на друга) оценки при распознавании символов, сходных с эталонными, являются информативными. Действительно, максимальную оценку могут получить лишь те образы, свертки 3х5 которых взяты в качестве эталонов, меньшие оценки характеризуют степень отклонения распознаваемого грубого растра от ближайших к нему эталонов в евклидовом 15-мерном пространстве.

Исследуем более подробно свойства оценок распознавания сверток 3х5 на наборе эталонов D и тестовой базе BT. Ограничим разрядность вычисляемых расстояний от объекта распознавания до очередного эталона 16-ю градациями. Распознаем тестовые символы, подсчитывая количество ошибок и удачных исходов, допущенных на каждой из возможных 16 оценок. Оказывается, что значений расстояний менее 12 не бывает, а 95 % всех реализованных оценок приходится на оценку 15. Это объясняется тем обстоятельством, что свертки 3х5 печатных букв находятся друг от друга на близком расстоянии из-за достаточно равномерного заполнения клеток сетки 3х5 при сжатии. Целесообразно преобразовывать экспоненциально получаемые оценки для равномерного заполнения интервала оценок. Заново распознаем тестовую базу, преобразуя оценки, ограничивая их 16-ю градациями и подсчитывая процент неудачных распознаваний по отношению к общему числу реализаций в каждой из градаций. Для экспоненциальной шкалы оценок 95 % исходов падают на интервал [10,15]. Результаты сведены в таб. 2, из которой видно, что надежность уменьшается монотонно вместе с величиной оценки.

Некоторое нарушение монотонности и подозрительные стопроцентные ошибки на низких оценках, объясняются ничтожно малым количеством (около 30) случаев реализации оценок в диапазоне [1;9] на тестовой базе. Эта зависимость сохраняется и с использованием логарифмической шкалы с 256-ю градациями, для такой шкалы в интервале [250,255] на тестируемой базе не было ни одной ошибки.

Градация (оценка)	Процент ошибок
0	-
1	-
2	50
3	100
4	100
5	100
6	100
7	100
8	100
9	50
10	64.7
11	19.35
12	18.18
13	6.4
14	4.83
15	2.7

Таб. 2 Распределение ошибок метода 3х5 с экспоенциальными оценками.

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

Устойчивость к вариациям образов в алгоритме 3х5 обеспечивается самой природой сжатия изображения. Внутренние разрывы и зашумления в изображениях оказывают малое влияние на точность распознавания, однако, налипания больших внешних компонент делают распознавание невозможным. Примеры игнорируемых и неблагоприятных дефектов для метода 3х5 букв приведены на рис. 4.

Р
ис. 4. Игнорируемые a) и неблагоприятные b) для алгоритма 3х5 дефекты символов

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

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

4. Принципы повышения точности
Проанализировав ошибки распознавания омнифонтовым методом 3х5 тестовой базы BT, мы обнаружим группу символов, состоящую из букв ‘И’, ’Н’, ’П’, которое часто путаются между собой, при этом в коллекции распознавания 3х5 присутствует правильный символ, конкурирующий с ведущей неверной альтернативой. Такие ошибки составляют более одной трети всех ошибок. Это связано с реальным сходством сверток 3х5 указанных символов, собранных из разных печатных шрифтов. Попробуем скомпенсировать эту ошибку с помощью исследований исходных образов, а не сжатых растров.

Р
ис. 5. Изображения символов ИНП идеального качества a), среднего качества b) и рассыпанного c) начертаний

Для изображений не курсивных букв ИНП не составляет труда достаточно точно (до одной точки) найти область между парой массивных вертикальных линий. Именно в этих областях находятся геометрические элементы (см. рис. 5), различные для достаточно большого числа образцов отсканированных букв ИНП различных шрифтов. Наклон перекладины должен различаться для букв ‘И’ и ‘Н’, а ее отсутствие свойственно только букве ‘П’. Для рассыпающихся изображений это простое правило требует уточнений, но и в этих случаях остатки перекладины могут быть зафиксированы и соотнесены с идеальными представлениями о буквах ИНП. Заметим, что для программирования описанного интуитивного правила требуется около 500 строк языка “C”, причем полученный код тестировался на более сложных образцах, нежели были приведены на рис. 5. Алгоритм соотнесения идеальных геометрических свойств с конкретным изображением символа назовем дискриминатором. Дискриминатор в конце своей работы может назначить штраф символу, описание которого не совпало с характеристиками изображения. Процедура дискриминации по перекладине коллекции, содержащей несколько представителей группы ИНП, изменяя порядок альтернатив, в большом числе случаев делает правильную альтернативу ведущей. После дискриминации полнота коллекции не теряется, однако свойства информативности оценок могут быть сильно нарушены. Этот недостаток искупается повышением точности распознавания. Достаточно сказать, что использование несложных дискриминаторов повышает точность 3х5 вдвое.

Кроме путаницы символов между собой на точность распознавания отсканированного текста влияет существенно ошибки распознавания “несимволов” – зашумленных букв и изображений порожденных комбинаторными алгоритмами разрезания и склеивания символов [1]. Существенную помощь в снятии таких ошибок могут оказать дискриминаторы по углам. Этот алгоритм анализирует контур изображения во всех четырех углах прямоугольника, его окаймляющего. Контуры классифицируются на простые (угол, сериф, скругление и т.п.) и составные (угол-скругление, угол-сериф), как показано на рис. 6. Организуется обучение, после которого получается таблица углов, невозможных для изображений некоторых символов, и за которые оценки этих символы могут штрафоваться. Таким образом, построенный регулярный дискриминатор снижает как число ошибок в распознавании несимволов, так и символов.

Р
ис. 6. Примеры типов идеальных и неопределенных угловых контуров
Приведенные примеры дискриминаторов, которые, работая параллельно с методом 3х5, поднимают его точность, указывают общий путь повышения точности грубых методов – их комбинирование с алгоритмами другой природы.
5. Событийный метод на сетке 3х5

Алгоритм распознавания сжатых растров 3х5 опирался на представление, игнорирующего детали исходного образа. Между тем хорошо известна группа так называемых структурных алгоритмов, использующих объекты, не изменяющиеся при непрерывных деформациях. Очевидно, что образы печатных и рукопечатных символов хорошо описываются такими объектами. Например, в образе символа «Н» есть две вертикальные линии и горизонтальная перекладина, а символ «И» отличается от символа «Н» наклонной перекладиной (рис. 5), и эти интуитивные описания не изменятся, если мы будем непрерывно деформировать образы с помощью таких преобразований как поворот на малый угол, изменение масштаба, движения свободных концов линий, утолщение линий и пр. Разбивая все множество образов символов на классы эквивалентности по признакам, инвариантным к малым непрерывным деформациям, мы получим модель, приводящую к некоторому методу распознавания.

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

черный интервал не имеет соседей в предыдущей строке растра (соседними считаются точки граничащие по одному из восьми направлений). Соответствует началу линии со свободным началом (интервалы 1,2 на рис. 7).
ч
ерный интервал не граничит ни с одним интервалом из следующей строки. Линия закончилась, и этот конец - свободный (интервалы 3,4 на рис. 7).

Рис 7. Пример свободных начал (1,2) , свободных концов (3,4) и линий с несвободными началами и концами (5)

черный интервал граничит с черным интервалом в предыдущей строке, и этот интервал первый из всех интервалов, граничащих с интервалом предыдущей строки. Интервал является продолжением линии (интервалы, продолжающие линии, заданные свободными концами 1,2, на рис. 7).
существует несколько интервалов, сцепленных с одним интервалом из предыдущей строки. Первый (самый левый) из них относится к продолжению линии, а остальные являются началами новых линий с несвободными началами (пересечение линий 5 на рис. 7).
у двух или более линий имеется общий соседний интервал в следующей строке. Первая (самая левая) линия продолжается, а остальные имеют несвободные концы (пересечение линий 5 на рис. 7).

Данная процедура выделения интервалов и линий позволяет получить линейное представление образа символа (пример разбиения растра символа на линии см. на рис. 8), состоящее из набора линий

L₁ = {B₁, E₁, S₁, I¹₁, … , I¹_N1}

L₂ = {B₂, E₂, S₂, I²_1, … , I²_N2}

………….

L_k = {B_k, E_k, S_k, I^k₁, … , I^k_Nk}

Где k - число линий, описывающих растр

B_i , E_i - признак наличия свободного начала и свободного конца в i-ой линии

S_i - номер строки в растре первого интервала i-ой линии

Iⁱ_j - j-ый интервал i-ой линии, состоящий из начальной и конечной координат.

Огрубим линейное представление следующим образом. Для каждой линии L_i определим ее начало IN_i и конец OUT_i как координаты середин первого и последнего из интервалов линии, после чего отмасштабируем координаты начала и конца на сетке 3х5. Отмасштабированную линию со своими координатами и свойствами начал и концов назовем прямым событием.

Рис 8. Пример разбиения образа буквы «а» на линии.

Набор событий сохраняет информацию о структуре буквы (количество и свойства линий) и, в то же время, вариативность линий ограничивается грубостью сетки 3х5. Повернув растр на 90 по часовой стрелке и проделав процедуры выделения линий и определения событий с повернутым растром, получим набор событий, называемых поворотными.

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

Для обучения метода достаточно запустить метод на некоторой тестовой базе и пополнить существующую или создать новую базу эталонов событиями, которых в ней не было. База из одного миллиона образов порождает набор прямых и поворотных событий объемом около 400 КБайт событийных эталонов.

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

Алгоритм событий относится к так называемым генераторам, порождающим коллекции без оценок. Поэтому понятия точности распознавания и информативности оценок неприменимы для метода событий. Быстродействие метода событий является одним из самых высоких, на эталонной базе в миллион символов скорость составляет 2000 символов в секунду. Одним из важнейших свойств метода событий является способность к отказам. Полнота коллекции для метода событий неразрывно связана с предыдущим свойством – способностью к отказам, в случае отказа ни о какой коллекции говорить не приходится, но если же метод не отказался от данного образа, то в выданной им коллекции будет содержаться правильный символ с полнотою 99,9% на базе BT. Отметим также монотонную обучаемость метода событий, заключающуюся в том, что чем большим количеством образов мы пополняем событийные эталоны, тем выше полнота коллекции событийного распознавания.

Свойства событийного метода позволяют использовать его в комбинации с другими алгоритмами распознавания символов, в частности с алгоритмом 3х5, запускаемым не на полном алфавите, а в режиме экспертизы, в котором метод 3х5 расставляет свои оценки кодам букв, сгенерированным методом событий. Такая схема сохраняет как высокую скорость событийного алгоритма, так и информативность оценок алгоритма 3х5. Ниже будет подробно рассмотрена более сложная схема комбинирования нескольких алгоритмов.

6. Нейронная сеть над образом 3х5

Объектом обучения и распознавания посредством метода нейронной сети может служить вектор фиксированной длины. Растр, приведенный к виду 3х5, подходит для этой цели.

Нейронная сеть с простой структурой содержит входной и выходной слои фиксированной длины, а также внутренние слои, длина которых подбирается экспериментальным путем в процессе обучения. На входе сети каждому нейрону соответствует один элемент вектора выборки (в нашем случае вектор 3х5). Каждый нейрон нижнего слоя связан со всеми нейронами последующего слоя набором связей с переменными весами. Прямой проход по сети делается следующим образом. Для каждого из узлов внутреннего уровня вычисляются величины
Y_i = sigm( _j (wf_ijX_j) ), 1in
где X_j – компоненты распознаваемого вектора, wf_ij - веса нейронной сети для внутреннего уровня, n – число нейронов на промежуточном уровне, а функция срабатывания sigm определяется так
sigm(x) = 1/(1+e^-x).
Далее аналогичные величины вычисляются для всех узлов сети выходного уровня:
Z_i = sigm( s_i+_j (ws_ijY_j) ), 1im
где ws_ij , s_i - веса нейронной сети для внешнего уровня, m – число нейронов выходного уровня, определяемое алфавитом распознавания.

Построим нейронную сеть простой структуры, с одним внутренним слоем. В качестве входных сигналов служит вектор, полученный сжатием графического растра до сетки 3х5. Каждая компонента вектора в процессе нормализации приводится к диапазону [ 0.0 – 1.0 ]. Целевым вектором (“выходом” нейронной сети) можно объявить весь алфавит, для которого строится сеть (см. Рис.7). Тогда после единственного прямого прохода по сети мы получим сравнительные оценки для всех букв алфавита. Вторым способом построения является создание отдельной (бинарной) сети на каждую отдельно взятую букву алфавита, где на выходе будет стоять оценка примера для одной конкретной буквы (см. Рис.7). В этом случае потребуется произвести отдельный проход по каждой сети, а затем выбрать из всех полученных результатов для различных букв несколько результатов с наибольшими оценками, образовывая коллекцию альтернатив распознавания.

Выбор общей или бинарной структуры зависит от конкретной задачи. Для алфавитов большой длины, то возникают большие сложности с построением общей сети. Это связано со свойствами структуры 3х5, поскольку значительная часть информации теряется во время сжатия растра. Поэтому отличить одну букву от всех остальных гораздо легче, чем произвести сразу их общее разделение. Если мы построим общую сеть над 3х5, то будем вынуждены сделать ее очень емкой, из-за увеличения числа нейронов на внутреннем слое и количества обучающих примеров. Это вызовет замедление метода, как при обучении, так и при его работе. Поэтому для сжатых до 3х5 растров больше подходит метод бинарных сетей, несмотря на трудоемкость процесса раздельного обучения нескольких сетей.

а) общая сеть 15-n-(объем алфавита)

б
) бинарная сеть 15-n-1

Рис 9. Структуры общей и бинарной нейронных сетей

Обучение производится традиционным методом обратного распространения ошибки (Back Propagation)[6]. Возьмем для примера две независимые омнифонтовые базы графических образов букв с алфавитом (А - Я), по 50 000 экземпляров в каждой. Первая будет служить источником для обучающей выборки, вторая – для контрольного тестирования. Обучение производится за несколько итераций. Для начала выберем из обучающей базы часть образов, стремясь сохранить для каждой буквы частоту ее появления буквы в реальных текстах. Обучим сеть до максимально возможной точности. Протестируем сеть по обучающей базе и добавим все неправильно распознанные символы в обучающую выборку. Также проверим полученную сеть на контрольной базе и зафиксируем результат. Будем повторять итерации до тех пор, пока результат тестирования на контрольной базе не ухудшится по сравнению с предыдущей итерацией. Для бинарных сетей эти операции проводятся с каждой конкретной сетью.

В процессе обучения можно экспериментальным путем оптимизировать топологическую структуру сети. В нашем случае - это длина внутреннего слоя n (см. рис. 9). Для бинарной сети над 3х5, то есть для каждой сети одной буквы, его оптимальная длина составляет 15 нейронов. Таким образом, структура данной сети будет выглядеть как [15 – 15 – 1].

Рассмотрим характеристики распознавания бинарной нейронной сети над 3х5 на тестовой базе BT. Точность распознавания составляет более 99 % и существенно превышает точность непосредственного алгоритма 3х5. Полнота коллекции 99.8 % сопоставима с полнотой алгоритма 3х5. Очевидно, что система бинарных сетей пригодна для использования сетевого распознавания в качестве эксперта, то есть для расстановки оценок в сгенерированной коллекции. Однако, несмотря на столь очевидные преимущества по отношению к методу 3х5 сетевой метод имеет ряд серьезных недостатков. Главный из них состоит в неинформативности оценок, из-за свойств функции срабатывания тяготеющих к наивысшей оценке 1.0 как при правильном, так и при ошибочном распознавании. Для обучения сетей, в особенности бинарных, требуется время в тысячи раз превышающее время обучения алгоритма 3х5 на аналогичном объеме.

7. Комбинирование методов 3х5
Рассмотрим основные характеристики описанных выше алгоритмов 3х5, нейронной сети 3х5 и событий 3х5, сведенные в таб. 3.

Алгоритм	3х5	Нейро 3х5	События 3х5
Точность (%)	95.3	99.17	-
Полнота коллекции (%)	99.9	99.81	94.5
Отказы (%)	-	-	5.4
Быстродействие (букв в сек)	800	400	2000
Информативность оценок	высокая	Низкая	-

Таб.3. Характеристики грубых алгоритмов, подсчитанные на базе BT
Очевидно, что достоинства и недостатки у всех трех алгоритмов различны. А именно, событийный метод обладает наибольшим быстродействием, но, являясь генератором, не может сформировать оценок. Нейронная сеть над 3х5 дает наибольшую точность, но обладает наименьшим быстродействием и низкой информативностью оценок. А метод 3х5, имея высокоинформативные оценки и наилучшую полноту коллекции, дает наименьшую точность, которая, как было показано выше, повышается дискриминационными методами. Построим схему комбинирования алгоритмов распознавания, призванную сохранить достоинства каждого из рассмотренных методов.

Комбинированное распознавание будем производить поэтапно:

генерация. Состоит в выработке гипотез событийным методом
экспертиза. Заключается в последовательной отработке методов 3х5 и нейронной сети 3х5 на суженном алфавите, определенным порожденными событийным методом гипотезами. Коллекции, порожденные двумя методами, объединяются таким образом, чтобы букве приписывалась наибольшая оценка, то есть алгоритмы 3х5 и нейронной сети 3х5 конкурировали между собой по точности. Оба этапа проходят достаточно быстро из-за скорости событийного метода и ограничения количества эталонов при экспертизе.
полное распознавание. Реализуется в случаях отказов при генерации или малой оценки экспертизы. Последний случай может свидетельствовать об ошибках генерации. При полном распознавании методы 3х5 и нейронной 3х5 запускаются на полном алфавите, их результаты объединяются аналогично этапу экспертизы.
дискриминация. Устраняет некоторые ошибки распознавания грубых методов за счет исследования оригинальных изображений символов, а не сжатых растров.
переоценка. Призвана придать оценкам коллекции, сформированным предыдущими этапами, большую информативность. Для этого используются уже подсчитанные оценки алгоритма 3х5.

Произведенное таким образом комбинирование для тестовой базы BT дает следующие характеристики распознавания: точность - 99.8 %, полнота коллекции - 99.91, быстродействие – 700 букв в секунду. Информативность оценок на базе BT нелегко оценить из-за малого числа ошибок. Тем не менее, отметим, что при 16-градационной шкале оценок, в наивысшей градации 15 происходят всего 2 ошибки в более чем 900-тах случая реализации этой градации, что свидетельствует о хорошей информативности оценок комбинированного метода.

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

8. Оптимизация быстродействия распознавания
Мы остановимся на оптимизации быстродействия методов на сетке 3х5 в 32-разрядных приложениях для персональных компьютеров с процессорами типа Intel Pentium с технологией MMX и Pentium II. Выбор этих платформ обусловлен как их широким распространением, так и особенностями, позволяющими существенно повысить скорость распознавания.

Прежде всего, поясним смысл оптимизации программ, создаваемых в конкретных системах разработки. Каждая из таких систем (мы рассматриваем, как и ранее, программирование на языке C в среде Microsoft Developer Studio 97) обладает ограничениями в оптимизации приложений, как из-за быстрого обновления аппаратного обеспечения, так и невозможности автоматического преобразования структур данных для оптимальных низкоуровневых машинных операций. Так при использовании MDS 97 на процессорах Intel Pentium MMX и Pentium II удается существенно ускорить алгоритмы 3х5 за счет изменения формата данных и непосредственного программирования инструкций MMX.

Легко понять, что значительные затраты времени в методе 3х5 и нейронной сети над 3х5 ложатся на вычисление большого числа скалярных произведений

Σ_j A_jB_j

с постоянной длиной N векторов A и B. Операция произведения одна из самых трудоемких для процессора Pentium. В то же время, архитектуру MMX, воплощая идею “одна инструкция над несколькими данными”(SIMD) , предоставляет в распоряжение программиста замечательную инструкцию “скалярного произведения” двух векторов длины 4, с компонентами длиной 16 бит. То есть одновременно выполняются 4 трудоемкие операции. Написав вручную функции вычисления скалярных произведений двух отнормированных векторов фиксированной длины с 16-разрядными компонентами и позаботившись о выравнивании данных, достигается ускорение (по отношению к обычной процедуре покомпонентного умножения и накопления суммы) в 4-5 раз для процессора Pentium. При этом полностью метод 3х5 ускоряется на 45-50 %, а метод нейронной сети над 3х5 – на 25-30 %. Дополнительный эффект достигается от применения для постоянного хранения информации -регистров. Применяя рекомендации разработчиков архитектуры Intel [7] удается дополнительно поднять производительность методов на сетке 3х5 на 5-10 % за счет выравнивания и унификации длин операндов. На процессоре PentiumII суммарная производительность алгоритмов, использующих скалярные произведения, возрастает не столь значительно, а именно, на 10-15 %.

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

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

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

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

простота обучения позволяет использовать алгоритмы над грубыми объектами в качестве адаптивных алгоритмов для дораспознавания документов, уже распознанных один раз более сложными методами. Это позволяет не только поднять качество распознавания документа в целом, но улучшить информативность оценок [5].

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

Таким образом, достоинства алгоритмов над грубыми объектами позволяют их применять в реальных системах ввода в компьютер печатных и рукописных документов. Реализации описанных в настоящей работе методов 3х5 и событийного распознавания внедрены в коммерческую всемирно известную систему Cuneiform различных версий [1].

Литература

[1] Арлазаров В.Л., Славин О.А. Алгоритмы распознавания и технологии ввода текстов в ЭВМ.

Информационные технологии и вычислительные системы 1996, No 1
[2] Simard P.Y, Cun Y.L., Denker J.S. Memory-Based Character Recognition Using a Transformation Invariant Metric, prec. IAPR International Conference on Pattern Recognition, Volume II, Jerusalem, 1994
[3] Кобзев А.И. Учение о символах и числах в китайской классической философии,

М.: изд. Восточная литература, 1994.

[4] Диде Э. Методы анализа данных. Подход, основанный на методе динамических сгущений, М.:

ФиС, 1985

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

“Интеллектуальные технологии ввода и обработки информации”, М.: Эдиториал УРСС, 1998

[6] Bishop C.M. Neural Networks for pattern Recongnition, Oxfrord, Oxfrord University Press, 1995
[7] Pentium ™ Processor User’s Manual. Vol. 3: Architecture and Programming Manual, Intel, Order No

241430, 1994

Рис 1. Примеры созвездий в китайской схеме САНЬ У

Рис 3. Начертания русских букв на сетке 5х5

Сетка

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

Полнота коллекции (%)

Быстродействие (символов в секунду)

3 х 3

95

98.5

33.5

3 х 5

99.1

99.7

25.1

5 х 5

99.5

99.7

17.6

Таб.1. Характеристики распознавания сжатых растров для различных степеней сжатия.

Рис 9. Структуры общей и бинарной нейронных сетей