Славин Олег Анатольевич

Вид материала

Автореферат

Содержание В третьей главе Рисунок 1 – Распределение вероятности p Cl, состоящие из одного или нескольких элементов S Рисунок 2 – Примеры оцифровки образа при различном наложении на сетку сканера Cl, причем положение каждого из элементов S Четвертая глава В пятой главе R и образом кластера P Z – ограничения на число слоев,  I)= . Повторная сегментация образа I

Подобный материал:

• Олег Анатольевич Усов подпись Контактное лицо: Усов Олег Анатольевич, конкурс, 1883.42kb.
• Милевский Олег Анатольевич, кандидат исторических наук, доцент кафедры регионологии, 384.42kb.
• Макушников Олег Анатольевич, доцент кафедры истории славян и специальных исторических, 209.21kb.
• Рецепция римского права: вопросы теории и истории, 249.57kb.
• Павлов Олег Анатольевич, старший преподаватель кафедры экономики и управления предприятиями, 390.93kb.
• Аналитические материалы краткий анализ деятельности горнодобывающих предприятий Камчатского, 356.1kb.
• Уважаемые отец Олег, Олег Александрович, Михаил Иванович, представители духовенства, 120.22kb.
• Синько Олег Анатольевич Архаическая парадигма мышления и внутренний Фен-Шуй доклад, 226.5kb.
• Факторы повышения конкурентоспособности пермского края, 581.94kb.
• Гревцева Людмила Германовна, кандидат юридических наук, доцент кафедры предпринимательского, 2451.72kb.

=0,01, M₂₅₅=0).

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

• образами символов;
  
• частями символов;
  
• объединениями символов и их частей;
  
• образами, не имеющими отношения к символам текста.
  

Сегментация (поиск границ, локализация) символов печатного текста, вследствие возможности объединения нескольких компонент связности в условиях искажения образа страницы, предполагает несколько взаимосвязанных процедур:

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

Пусть для зоны сегментации известен массив возможных координат, называемых точками сегментации x₀, x₁,…,x_n по горизонтальной оси (x₀ и x_n - границы зоны). В общем случае точка x_j определяет отрезок, располагающийся между верхней и нижней границей.

Выбор пары точек сегментации (x_i,x_j) определяет компоненту, то есть образ s(i,j_j), извлекаемый из исходного и расположенный между этими точками сегментации и который не обязан быть связным множеством. Задача сегментации базируется на некотором алгоритме распознавания символов R, который позволяет получить коллекцию альтернатив распознавания образов s(i,j_j). Ведущая альтернатива коллекции и ее оценка p₁ определяет оценку пары (x_i,x_j) точек разрезания и обозначается (i,j)=p₁. Путем сегментации длины k для образа s(p,q) называется набор точек



Алгоритмы сегментации, рассматриваемые в диссертационной работе, опираются на некоторую аддитивную функцию, которая каждому пути t ставит в соответствие неотрицательное число (t). Для такой функции (меры) для любого пути t, являющегося суммой двух других путей t=u+v, справедливо равенство (u+v)=(u)+ (v).

В процессе определения оптимального пути используется принцип Беллмана, основанный на следующей гипотезе: если путь является оптимальным для своей компоненты s(p,q), то любой подпуть (траектория) этого пути также является оптимальным для своей компоненты.

При оценке пути в случае, когда в точку x_n ведут n путей, используются оценки путей в предыдущие точки, и путь оценивается на основе вычисленных ранее оценок путей:

m(a_n)=max(r(0,x_n), m(a₁,x₁),…, m(a_n,x_n)).

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

Одним из критериев, используемых в алгоритмах сегментации, является механизм, манипулирующий символами, собранными в строки, для нахождения четырех базовых линий: b₁ – верх заглавных букв, b₂ – верх обычных, b₃ – низ обычных и b₄ – низ опущенных букв. Получены оценки вероятностей нахождения базовых линий. Например, вероятность второй базовой линии равняется



где n_i – число символов, начинающихся на b_i, P₁ (P₂) - вероятность того, что символ начинается с первой (второй) линии в строке из N символов.

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

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

Некоторые из этих проблем могут быть разрешены только применением лингвистических или словарных механизмов, базирующихся на представительном корпусе слов (словоформ) или представительном наборе сочетаний символов в общеупотребительных текстах определенного языка. По исходному представлению слова W₀=C₁,…,C_n словарный механизм генерирует несколько последовательностей символов W_i=, близость к которым оценивается с помощью некоторой функции расстояния d(W₀, W_i). В зависимости от степени трансформации исходного слова (количество инверсий символов, количество замен одних групп символов на другие) возможны различные стратегии использования словаря:

• подтверждение - при выполнении условия d(W₀, W_i)=0;
  
• ограниченная замена, в которой происходит замена кода ведущей альтернативы W₀ на код других альтернатив распознавания;
  
• агрессивная замена - символы могут быть заменены иными символами, даже отсутствующими среди альтернатив.
  

Рассмотренные во второй главе алгоритмы позволяют для произвольного набора строк в отсканированном тексте:

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

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

В третьей главе описаны основные понятия и алгоритмы адаптивного распознавания.

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

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

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

Таблица 1 – Оценки монотонности алгоритмов

распознавания печатных образов

Метод Оценка	1		
M240	0,483917%	0,002030%	0,004792%
M255	0,068213%	0,00%	0,003062%

Формирование обучающей последовательности производится на основании монотонности оценок надежности, порождаемых алгоритмами распознавания образов. Рассмотрим три шрифтонезависимых алгоритма: комбинированный алгоритм ₁, нейронную сеть  и метод полиномиальной регрессии . Из данных таблицы 1, полученных для различных тестовых последовательностей следует, что наибольшей монотонностью обладает алгоритм , который имеет наибольшую оценку точности распознавания (более 99%). Однако график распределения ошибок v_E(W) является монотонным только для метода  при оценках, превышающих W_max/2, но при этом график распределения оценок  растет в диапазоне [W_max/2, W_max] медленнее, чем график .

Модификация алгоритма ₁, состоящая в переоценке полученных альтернатив с помощью метода  или , обеспечивает высокую надежность оценок распознавания, характеризуемая M₂₄₀ и M₂₅₅.

Таблица 2 – Вероятности ошибок распознавания

si

sj

pij

si

sj

pij

si

sj

pij

si

sj

pij

si

sj

pij

д

А

0,028

й

и

0,018

Ы

м

0,032

я

п

0,008

щ

Ш

0,009

й

А

0,016

н

и

0,076

В

н

0,006

ч

ц

0,010

ъ

Ь

0,006

л

А

0,008

п

и

0,006

И

н

0,047

м

ч

0,013

з

Э

0,021

в

Б

0,018

д

л

0,016

Я

н

0,008

ц

ч

0,014

й

Ю

0,034

ф

Е

0,010

п

л

0,052

Й

п

0,010

щ

ч

0,005

ыо

Ью

0,02

э

З

0,014

я

л

0,008

Л

п

0,011

й

ш

0,009

кж

Кю

0,015

Надежность оценок распознавания символов может быть повышена с помощью механизма словарного подтверждения. Для слова w, состоящего из последовательности символов a₁a₂…a_k, распознанных алгоритмом с известным распределением ошибок (s_i, s_j, p_ij=p(s_i,s_j)), осуществляется проверка наличия слова в корпусе словарных слов некоторого языка. Было проведено численное моделирование оценки вероятности ошибки словарного подтверждения одного словарного слова другим словарным словом, при этом использовалось распределение ошибок алгоритмов распознавания, описанных в главах 2 и 3, которое приведено в таблице 2.



Рисунок 1 – Распределение вероятности p_k ошибки подтверждения в слове длины k при игнорировании ошибок в окончаниях


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

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

Описанный способ словарного подтверждения при комбинировании с монотонными оценками алгоритма распознавания делает ошибку словарного подтверждения практически невозможным событием. Результаты подсчета ошибок словарного подтверждения слов из двух тестовых последовательностей TS₄, TS₅, содержащих как словарные так и несловарные слова, приведены в таблице 3.

Таблица 3 – Ошибки подтверждения слов

Тестовая последовательность	Количество слов	Количество ошибок	Частоты ошибки подтверждения слов длиной k
			k=4	k=5	k=6	k=7	k=8	k=9	k>9
TS4	13984	16	7	4	2	1	2	0	0
TS5	11036	3	1	0	1	1	0	0	0

Предложенный способ словарного подтверждения надежности распознанных символов обеспечивает с избытком потребности адаптивного распознавания в классах документов с хорошим и средним качеством печати, обеспечивая вероятность правильного подтверждения 0,9999.

На этапе кластеризации происходит объединение распознанных символов бинарных образов в группы Cl, состоящие из одного или нескольких элементов S₁,…,S_n. Целью кластеризации является разбиение обучающей последовательности на кластеры, соответствующие символам некоторого шрифта для последующего построения эталонов и повторного распознавания с использованием построенных эталонов. Для обеспечения кластеризации необходимо решить несколько проблем:

• построение функции для оценки близости отсканированных (искаженных) образов;
  
• стабильное определение образа кластера;
  
• определение идеальных образов кластера.
  

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

• метод ближайшего соседа;
  
• метод цепной развертки, базирующийся на цепном расстоянии d_C(X, Y)<, для которого справедливо неравенство
  

d_C(X_i, X_k)d_C(X_i, X_j), d_C(X_j, X_k)} "X_i,X_j, X_k

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

Функция сравнения двух бинарных образов должна удовлетворять следующим условиям:

• d(A,A)³0 "A;
  
• рефлективность - d(A,A)=0 "A;
  
• симметричность - d(A,B)= d(B, A) "A,B.
  

Таким условиям удовлетворяет метрика Хэмминга , а также псевдометрика, которая вычисляется следующим образом: для каждого образа символа строится изображение его единичной окрестности, то есть множества всех точек, находящихся на расстоянии не больше 1 от S. Обозначим единичную окрестность множества S через N⁽¹⁾(S), тогда расстояние между образами A={a_ij} и B={b_ij} вычисляется по формуле

.

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



Рисунок 2 – Примеры оцифровки образа при различном наложении на сетку сканера

Для учета эффектов оцифровки образы подвергаются центрированию, то есть помещению в центр некоторой выпуклой фигуры. При сравнении центрированных образов A и B будем производить несколько сдвигов образа A=||a_ij|| в разных направлениях, выбирая в качестве расстояния между центрированными образами A и B минимальную величину из полученных значений

d₀(A,B) = min(₀(A^(HV), B)) или d₁(A,B) = min(₁(A^(HV), B)),

где H,V S_p(z) ={-z, -z+1, … , -1,0,1, …, z-1, z}.

Эксперименты показывают, что для симметрики ₁ при сравнении бинарных образов всегда достаточно сдвигов на 1, а для метрики ₀ менее, чем для 0,8% исследуемых образов требуется сдвиг на 2, тогда как для оставшейся доли образов – сдвиг на 1. В работе была решена задача поиска параллельного переноса эталонного изображения, при котором его совпадение с тестируемым изображением максимально. В диссертации доказано, что для достижения оптимального наложения двух фигур достаточно малых сдвигов в том случае, когда мера несовпадения при малых сдвигах незначительна. Была доказана следующая теорема о малых сдвигах при наложении двух фигур:

Теорема. Зафиксируем вeктoр единичной длины. Пусть - минимальное число такое, чтo для вeктoрa , при выnoлнeнo неравенствo . Тогда при сnрaвeдливo нeрaвeнствo

.

В частности, для минимизации дoстaтoчнo рассматривать лишь вектoры , для кoтoрыx .

Выберем опорный элемент S₀ кластера как образ с лучшей оценкой распознавания среди подтвержденных словарем образов. Произведем дополнительные сдвиги для всех элементов кластера. Для поиска оптимального положения по отношению к опорному элементу положение любого элемента S_X, отличного от опорного элемента S₀, изменяется таким образом, чтобы расстояние d(,S₀) между образами этими элементами было наименьшим.

Выбор опорного элемента S₀ и симметрики d позволяет определить образ кластера P(Cl)=||p_ij||, как сумму бинарных центрированных образов всех элементов S_X, составивших кластер Cl, причем положение каждого из элементов S_X оптимизировано по отношению к опорному элементу:

d(S_X, S₀)min. (1)

Возможны другие способы суммирования. Например, следующая процедура обеспечивает выбор оптимального положения по отношению к уже существующей сумме. На первом шаге в качестве суммы ₀ берется образ опорного элемента S₀. На последующих шагах положение образа R=||r_ij|| очередного элемента модифицируется с целью максимизации наложения на сумму _q=||r_ij||, подготовленную на предыдущем шаге

 r_ij mах, (2)

после чего полагаем  _q+1 = _q + R.

Определим понятие порогового образа кластера Tr(T), получаемого из образа кластера бинаризацией с порогом Т. Пороговый образ Tr((Cl)) будем называть общей областью кластера, причем пороговый образ Tr(0) совпадает с образом кластера.

Полученный суммированием образ кластера представим в виде мультимножества точек {(i,j) · p_ij}, где p_ij – значение накопленной суммы в точке (i,j).

Образ кластера описывается моделью, состоящей из совокупности равноудаленных слоев L₁, L₂…, каждый из которых содержит точки образа кластера P(Cl) с одинаковым расстоянием Хаусдорфа d_H до общей области:

L_q = { r_ij | r_ij P(Cl), [d_H (r_ij, A_C)] = q },

где d_H(x,Y) = min d₂(x, y), yY;

[ ] – операция взятия целой части от действительного числа;

d₂ – некоторая функция расстояния в R².

Тогда образ кластера можно представить в следующем виде:

P(Cl) = A_C  L₁  L₂  …

Для избавления от влияния случайных искажений используется другая модель образа, содержащая два параметра k_E<½ и k_S>½, и два соответствующих им порога L_E = k_E  (Cl) и L_S = k_S  (Cl). Порог L_E призван избавиться от искажений индивидуальных образов символов в P(Cl), а порог L_S позволяет расширить общую область. Образ кластера в этой модели представим следующим образом:

P*(Cl, L_E, L_S) = Tr (L_S)  l₁  l₂  … , (3)

где слои l₁, l₂,…, содержат точки порогового образа Tr(L_E), находящиеся на одинаковом расстоянии от Tr(L_S).

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

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

Четвертая глава диссертации посвящена моделированию процессов оцифровки для проверки адекватности модели образа кластера (3) и модели оцифровки.

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

• различные гарнитуры (шрифты Arial, Courier New, Times New Roman),
  
• различные атрибуты шрифтов (Normal, Bold, Italic),
  
• различные символы и графемы (символы кириллицы и латиницы),
  
• различные углы наклона (от 0до 6 включительно).
  

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

В проведенных экспериментах были использованы следующие последовательности:

• 4312 имитационных последовательности без случайных искажений S_D(c, L, Q, m, n, , T_B);
  
• 2548 имитационных последовательностей S_I(c, L, Q, , m, n, , T_B) со случайными искажениями;
  
• 2989 последовательностей отсканированных образов высокого и среднего качества S_S(c, m, );
  
• 60 последовательностей отсканированных образов низкого качества S_N(c, ).
  

Целями проведения экспериментов являлись:

• оценка возможностей симметрик d₀ и d₁ при кластеризации, эффективность применения симметрики оценивалась с точки зрения попадания в один кластер элементов последовательности образов, соответствующих одному прообразу;
  
• оценка возможностей способов суммирования (1) и (2) при суммировании элементов одной последовательности с точки зрения плотности кортежей укладки, при этом оценивается зависимость от выбора опорного элемента;
  
• оценка плотности кортежей укладки при различных значениях коэффициентов k_E и k_S, а также выбор диапазонов k_E и k_S для приемлемых значений укладки, при этом оценивается зависимость от выбора опорного элемента;
  
• оценка влияния случайных искажений и эффектов оцифровки на формирование стабильной модели образа кластера.
  

Проведенное моделирование позволило сделать следующие выводы:

• функция расстояния d₁ является пригодной для кластеризации последовательностей отсканированных образов, обладающих одним прообразом;
  
• функция расстояния d₀ пригодна для дополнительного разбиения кластера на подкластеры;
  
• способ суммирования (1), состоящий в оптимальном наложении каждого из образов элементов кластера на образ опорного элемента, является предпочтительным по отношению к способу (2) при формировании образа кластера как суммы образов составляющих его элементов;
  
• способ формирования эталона, состоящий в игнорировании точек образа кластера (3) при значениях, меньших k_E(Cl), и в расширении нулевого слоя до значений, больших k_S(Cl), позволяет получить разбиение на слои, слабо зависящие от выбора опорного элемента;
  
• оптимальными являются диапазоны параметров k_E[0,2; 0,3] и k_S[0,6; 0,9];
  
• малые случайные искажения образов при сканировании не влияют на результаты кластеризации и формирования эталонов в случае использования диапазона параметра k_E[0,2; 0,3].
  

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

В пятой главе рассмотрены вопросы определения шрифтов в найденных кластерах и формирования эталонов для последующего распознавания.

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

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

Пусть ={₁, …, _s} – алфавит распознавания и p={p₁,….p_s} – соответствующее распределение вероятностей появления символов алфавита, заданное с помощью частот встречаемости символов.

Рассмотрим шрифт ={n₁₁, …, n_s_s} в форме мультимножества символов  с кратностями {n₁, …, n_s}. Пусть n = n₁+…+n_s.

Тогда вычислим величину , где . В том случае, если , то расхождение между эмпирическим и теоретическим распределениями считается несущественным (критерий Романовского).

Если величина , то расхождение между распределениями существенно. Вычисляем индекс и удаляем его из шрифта, полагая . Определяем для алфавита  новое распределение  следующим образом:

.

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

Кластеры, вошедшие в построенные шрифты, в последующем используются для дополнительного распознавания символов и повторной сегментации ряда слов.

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

Автором был разработан метод _e сравнения с эталонами, который позволяет сравнивать образы символов более точно, чем шрифтонезависимые методы. Распознавание символа происходит на основе разбиения образа кластера на слои.

Из образа кластера P(Cl) извлекаются Tr(k_E(Cl)) следующие бинарные образы:

• общий образ GEN(Cl)=||g_ij||, определенный границами общей области Tr(k_S(Cl)) и ее единичной окрестности, то есть g_ij=1 при d_H(b^k_ij, Tr(k_S(Cl)))<2, в противном случае g_ij=0;
  
• образ k-ой окрестности (k>1) LAY_k(Cl)=||b^k_ij||, определенный границами l_k, то есть b^k_ij=1 при d_H(b^k_ij, Tr(k_S(Cl)))=k, в противном случае b^k_ij=0.
  

Рассмотрим способ вычисления расстояния между распознаваемым бинарным образом R и образом кластера P(Cl), в котором штрафуются точки образа R, не попавшие в общий образ кластера, а также точки, попавшие во второй и старшие слои:

Pen(R, Cl)=

где Z – ограничения на число слоев,

_k – штраф за попадание точки в слой k.

Степень сходства Conf(R,E) рассматриваемого образа R и эталона E вычисляется следующим образом:

Conf(R,E) = max(0, 255 - Pen(R,E)).

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

Conf_max(R,E)=max(Conf(R,E), Conf(R_h^(1),E), Conf(R_v^(1),E), Conf(R_hv^(1),E)).

Результаты проведенных экспериментов показывают стабильность точности распознавания при k_E[0.18, 0.36] и k_S[0.80, 0.88], рабочим приближением являются значения порогов k_E0.21 и k_S0.84. При этом в диапазоне k_E[0.18, 0.36] и k_S[0.80, 0.88] оценка монотонности M₂₅₅0.

Комбинирование способом _1с основывается на распределениях ошибок двух алгоритмов: используемого на первом проходе комбинированного алгоритма ₁ и алгоритма _c сравнения с эталонами, полученными в результате кластеризации. Другой способ комбинирования _2с ориентирован не на повышение точности распознавания, а на повышение монотонности оценок распознавания алгоритма с высокой точностью. В таблицах 4 и 5 приведены оценки точности и монотонности оценок для методов _1с и _2с.


Таблица 4 – Точность распознавания алгоритмов ₁ и _1с

стенд обучения стенд распознавания	TS3		TS6		TS9
TS3	-		1	99.25	1	99.25
			1с	99,77	1с	99,77
TS6	1	99.25	-		1	99.25
	1с	99,63			1с	99,60
TS9	1	99.59	1	99.59	-
	1с	99.78	1с	99.61

Таблица 5 – Монотонность оценок алгоритмов ₁ и _2с

алгоритм стенд	1		2с
	M240	M255	M240	M255
TS3	0.748%	0.313%	0.25%	0.0%
TS6	0.78%	0.161%	0.37%	0.0%
TS9	0.373%	0.0%	0.373%	0.0%

Объектом распознавания на втором проходе служит образ I, соответствующий последовательности из нескольких символов, которые были распознаны на первом проходе недостаточно надежно. Образу I ставится в соответствие один или несколько шрифтов (I)={F₁,…,F_n(I)}. Допустим случай, когда ( I)= .

Повторная сегментация образа I проводится следующим образом: зафиксируем набор эталонов ={E₁,…,E_Q}, принадлежащих одному или нескольким построенным шрифтам. Для каждого эталона задана правая граница, которая будет использоваться для выделения части образа для сравнения с эталоном. В соответствии с размером и правой границей каждого из эталонов E_i из распознаваемого образа I выделяется левая часть L(I) так, чтобы размер L(I) соответствовал размеру эталона E_i. После этого образ L(I) сравнивается с эталоном E_i с помощью функции расстояния d. Процедура выделения части образа должна учитывать случаи невертикальных границ, что типично, например, в курсивном шрифте, но также встречается и в прямом шрифте при близком расположении символов.

Таким образом, получается некоторое количество вариантов образов левого начального символа L_j(I), таких, что расстояние d(L_j(I), E_i) меньше заданного порога. Для каждого варианта успешного распознавания левая часть удаляется из распознаваемого образа в соответствии с правой границей эталона, а с каждой из оставшихся частей операция повторяется до тех пор, пока весь образ не будет распознан, или не будет установлено, что приемлемых вариантов сегментации нет.

Таблица 6 – Точность сегментации после первого и второго прохода

Стенд Проход	TS1	TS2	TS3	TS4	TS5	TS6	TS7
первый	99,24%	99,83%	99,43%	99,76%	99,69%	99,40%	99,92%
второй	99,84%	99,92%	99,87%	99,76%	99,76%	99,68%	100%

Результаты, приведенные в таблице 6, иллюстрируют повышение точности сегментации при повторном распознавании с использованием алгоритма сравнения с эталонами, извлеченными из кластеров.

Описанный алгоритм поиска шрифтов позволяет реализовать алгоритм сжатия бинарных изображений, состоящий в распознавании образа страницы и замене образов отдельных символов I₁,…,I_k ссылками на образы кластеров соответствующего шрифта.

В результате проведенной кластеризации, использующей в качестве функции расстояния симметрику ₁, некоторые из образов I⁽¹⁾₁,…,I⁽¹⁾_p станут элементами, образовавшими несколько кластеров Cl₁, … , Cl_q. Другие образы I⁽²⁾₁,…,I⁽²⁾_k-p не войдут ни в один из кластеров. Образы I⁽¹⁾₁,…,I⁽¹⁾_p заменяются представлениями кластеров в форме пороговых идеальных образов, определяемых при максимизации выражения:


.


где k – количество элементов в кластере Cl, а SCl. В качестве функции близости μ может быть взята симметрика d₁

При выполнении условий

q << p и 2p <<k (3)

становится возможным уменьшение суммарного объема образов I₁,…,I_k за счет представлений образов кластеров Cl₁, … , Cl_q, заменяющих I⁽¹⁾₁,…,I⁽¹⁾_p.

Для изображения, удовлетворяющего условию (3), поиск шрифтов позволяет значительно уменьшить количество одноименных кластеров Cl₁, … , Cl_q, полученных из набора бинарных изображений I⁽¹⁾₁,…,I⁽¹⁾_p.

Различные сценарии сжатия позволяют реализовать различные режимы хранения и воспроизведения распознанных изображений:

• репринтом
  

с удалением случайных образов;

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

Таблица 7 – Улучшение характеристик качества распознавания символов

стенд характеристика	Точность (%)		Монотонность оценок				Скорость распознавания (изображений в сек)
			M240 (%)		M255 (%)
	без адаптивного распознавания	с использованием адаптивного распознавания	без адаптивного распознавания	с использованием адаптивного распознавания	с использованием адаптивного распознавания	с использованием адаптивного распознавания	без адаптивного распознавания	с использованием адаптивного распознавания
TS1	99,47	99,93	1,1	0,2	3,78	0,01	0,36	0,43
TS2	99,67	99,84					0,43	0,56
TS3	99,25	99,77					0,39	0,46
TS4	99,92	99,95					0,43	0,48
TS5	99,79	99,97					0,76	0,85
TS6	98,54	99,28					0,33	0,4
TS7	99,87	99,87					0,29	0,33
TS8	98,13	98,86					0,48	0,51
TS9	99,68	99,85					0,37	0,40