Книги по разным темам Pages:     | 1 | 2 | 3 |

а) P3(t) lj t а) То, что затраты действительно li 0 L минимальны следует из утверждения, Узел которое несложно доказать: для Ri Rj любой функции ft, t [0, L], удовлетворяющей граничным L условиям (3), величина f t 2dt не б) P3(t) Rj L Ri t Узел Рис. 3. Восстановление траектории в узле Электронный журнал ИССЛЕДОВАНО В РОССИИ 1442 htttp://zhurnal.ape.relarn.ru/articles/2003/120.pdf L превышает значения полученного интеграла I = dt, где st = P3(t).

t s Значение признака kij определяется следующим образом:

I (1 + 12 + 2 ) если <, < то kij = =, иначе kij = + (6) 2 2 4L LЕсли L достаточно мало, то использование признака kij может Rприводить к неверным k12 = = 0;

70, Lрезультатам, поэтому, если 1.значение L меньше заданной k13 = 10.L13 константы Lmin, то начальная и Lконечная точки смещаются внутрь 2.R1 R2 k23 = 21.регулярных областей на равные Lрасстояния. Значение Lmin Lопределяется экспериментально.

В некоторых случаях, о Рис. 4. Различные значения признака kij.

которых будет сказано ниже, значение kij вычисляется не по средним линиям областей Ri, Rj а по граничным линиям этих областей.

4.3.2. Признак di Для каждой области Ri, i=1..m определим di как отношение длины линии li соприкосновения узла и области Ri (см. рис. 3) к средней ширине штриха символа dср, т.е.

di = li /dср. Обычно величина di для дуплетов больше чем для других регулярных областей так как через линию li проходит два штриха.

4.3.3. Вычисления признаков kij для дуплетов Если две регулярные области Ri, Rj (см. рис. 5) образуют штрих, причем обе области не являются дуплетами, то границами образованного штриха будут ломаные BilAilAjrBjr и BirAirAjlBjl (например, рис. 5(б), пары регулярных областей {R1, R3} и {R2, R4}, рис. 5(в) пара областей {R1, R3}). В этом случае траектория штриха внутри областей Ri, Rj совпадает с их средними линиями и признак kij определяются именно по средним линиям областей Ri, Rj.

Если же регулярная область Ri является дуплетом и пары областей {Ri, Rj}, {Ri, Rk} образуют штрихи, то невозможно однозначно решить, которой из границ штрихов {Ri, Rj}, {Ri, Rk} принадлежит каждая из двух границ области Ri так как имеет место наложение штрихов друг на друга. Таким образом, из четырех возможных границ двух штрихов BilAilAjrBjr, BilAilAkrBkr, BirAirAklBkl, BirAirAjlBjl лишь две границы наблюдаются на B1r B1l B1r B1l B1r B1l RR1 RA1r A1l A1r A1l A1r A1l RA2l R4 RA3l A3r A3l A3r RB2l R2 A2r RRB3l B3r B3l B2r (а) (б) (в) B3r Рис. 5. Примеры узловых областей. Ri - регулярная область; Ломанные BilAil, BirAir - левая и правая границы области; AilAir - отрезок соединения узла и области Ri.

Электронный журнал ИССЛЕДОВАНО В РОССИИ 1443 htttp://zhurnal.ape.relarn.ru/articles/2003/120.pdf изображении (см. рис. 5а, область R1 - дуплет, штрихи {R1, R2}, {R1, R3}). Траектории штрихов {Ri, Rj}, {Ri, Rk} внутри области Ri не совпадает со средней линией, поэтому признаки kij, kik определяются не по двум средним линиям, а по двум границам.

Рассматривается два возможных варианта: kij определяется по BilAilAjrBjr, kik определяется по BirAirAklBkl, либо kij, определяется по BilAilAkrBkr, kik определяется по BirAirAjlBjl. Для определения kij, kik рассматриваются оба варианта, и выбирается тот, в котором значение p(kij | cij =1) p(kik | cik =1) максимально (см. формулу 8).

Информацию об окрестности узла представим в виде X = { kij mm, d1,..,dm}, с учетом kij = k i, j 1..m. Метод восстановления штрихов в узле основывается на следующих ji предположениях: траектория и границы внутри узла имеют малую кривизну (признак kij );

ширина дуплетов в окрестности узла больше чем ширина обычного штриха (признак di).

Для нахождения p(X | C) воспользуемся следующими предположениями. Будем считать, признаки kij и di статистически не коррелированны, т.е.

p(X | C) = p( kij mm, d1,..,dm | C) = p( kij mm | C) p(d1,..,dm | C) (7) Также, будем считать, что плотность распределения признака kij зависят только от факта, образует ли штрих пара Ri, Rj, т.е. зависит только от значения cij. Таким образом m m p( kij mm | C) = p(kij | cij ) (8) i=1 j=i+Если области Ri, Rj не являются дуплетами, то kij вычисляются по средним линиям, в противном случае вычисления производятся с использованием границ областей как описано выше.

Будем предполагать, что ширина штриха зависит только от того, является ли штрих дуплетом:

m p(d1,.., dm | C) = p(di | si ), (9) i=m где si = 1 если = 2, т.е. Ri - дуплет, иначе si = 0.

cij j=Окончательно, подставляя (8), (9) в (7) имеем m m p(X | C) = p(di | si ) p(kij | cij ) (10) i=1 j=i+Таким образом, среди множества возможных конфигураций Tm выбирается конфигурация, имеющая максимальную меру, согласно формулам (2), (10). На большой выборке различных узлов делается статистическая непараметрическая оценка плотностей распределения p(k | c = 0), p(k | c = 1), p(d | s = 0), p(d | s = 1) Также делается статистическая оценка априорной вероятности p(C) возникновения конфигурации из каждого класса эквивалентности. Как уже было сказано, мы предполагаем, что величина p(C) для различных матриц из одного класса принимает одинаковые значения.

4.4 Поиск и восстановление случайных разрывов Из-за использования тонких пишущих инструментов и недостатков сканирования на изображении могут возникать случайные разрывы штрихов. Для некоторых типов Электронный журнал ИССЛЕДОВАНО В РОССИИ 1444 htttp://zhurnal.ape.relarn.ru/articles/2003/120.pdf отсканированных документов низкого качества разрывы являются серьезным препятствием для корректного распознавания.

После процедуры выделения регулярных областей, задача поиска разрывов траектории сводится к поиску пар точек, являющихся концами средних линий регулярных областей, которые образуют разрыв. Пусть Ri, Rj - регулярные области, точки Pi d, Pjs, d, s {0,1} - концы средних линий этих областей, для которых решается задача о разрыве. Признаками для получения функций правдоподобия служат: расстояние между точками r и уже известные признак k, который вычисляются по средним линиям пары областей Ri, Rj между точками Pi d, Pjs так же, как в задаче восстановления узлов. Если значения r, k превышают порог, пара Pi d, Pjs как возможный разрыв не рассматривается.

Пусть p(b =1| k,r), p(b = 0 | k,r) = 1- p(b = 0 | k,r) - апостериорные вероятности того, что пара (Pi, Pj) со значениями признаков k и расстоянием между точками r образует (b=1) или не образует (b=0) разрыв. По формуле Байеса p(k,r | b = 1) p(b = 1) p(b = 1| k,r) = ; (11) p(k,r | b = 1) p(b = 1) + p(k,r | b = 0)(1- p(b =1)) Пара ( Pi d, Pjs ) определяется как разрыв, только если p(b = 1| k,r) > 0.5.

На большой выборке различных пар делается статистическая оценка плотностей распределения p(k,r | b =1), p(k,r | b = 0) и априорной вероятности возникновения разрыва p(b = 1).

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

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

Пусть на изображении имеется p узлов и q возможных разрывов. Выберем p конфигурации узлов C1,Е,C и разрывов b1,Е,bq, причем bi =1, если некоторая пара ( Pid, Pjs ) концов регулярных областей рассматривается как разрыв, иначе bi = 0. Пары ( Pid, Pjs ), для которых значения параметров превышает некоторый порог, как возможные разрывы не рассматриваются и не входят в набор b1,Е,bq.

Из формул (2), (11) следует, что вероятность возникновения траектории равна p q p 1 p q i i i P(T | I) = P(C1,Е,C,b1,Е,bq | X,...X,r1,k1,...rq,k ) = P(C | X ) P(b | ri,ki ), (12) i=1 i=где T - траектория, I - информация об изображении.

Очевидно, что P(T | I ) принимает максимальное значение для конфигураций, i имеющих максимальную меру P(Ci | X ) и для возможных разрывов со значением i P(bi | ri,k ) > 0.5.

Электронный журнал ИССЛЕДОВАНО В РОССИИ 1445 htttp://zhurnal.ape.relarn.ru/articles/2003/120.pdf Однако экспериментальная проверка методов определения конфигураций узлов и поиска разрывов показала, что достоверность методов (см. параграф 6) ниже точности, необходимой для распознавания. Следовательно, достоверность того, что по набору p i C1,Е,C,b1,Е,bq для которого P(Ci | X ), P(bi | ri,ki ) максимальны, будет построена действительная траектория изображения также меньше точности, необходимой для распознавания.

Данная проблема может быть решена следующим образом: отсортируем всевозможные p наборы C1,Е,C,b1,Е,bq по убыванию величины P(T | I). Для построения гипотез о наборе траекторий отбирается только часть полученного списка. Длина списка N может быть фиксирована - выбираются первые N наборов, либо фиксируется вероятность P попадания верной траектории в список, и длина списка N выбирается так, чтобы сумма вероятностей траекторий из списка превосходила P.

5.2. Преобразование гипотезы об узлах и разрывах в гипотезу о наборе траекторий p По известному набору C1,Е,C,b1,Е,bq может быть построен один или несколько p наборов траекторий. В некоторых случаях набор C1,Е,C,b1,Е,bq может быть признан некорректным, при этом он выбрасывается из рассмотрения.

На рисунке 6 представлены примеры работы алгоритма построения набора траекторий p по известной набору C1,Е,C,b1,Е,bq который имеет максимальную меру P(T | I). Во p всех примерах на рисунке 6 по набору C1,Е,C,b1,Е,bq строится верная траектория.

инией двойной толщины отмечены дуплеты, которые затем расщепляются на два отрезка траектории. Дуплеты делятся на две группы: первая группа - один конец дуплета соединен с двумя регулярными областями, второй конец не соединен ни с одной из регулярных областей (рис. 6 а)R1, в)R1,R2, д)R1); вторая группа - каждый из двух концов соединены с двумя регулярными областями (рис. 6 г)R1, д)R2, е)R1). Возможен также случай, когда один конец дуплета соединен с двумя областями, другой - только с одной областью, в этом случае, эта область также объявляется дуплетом, возникает цепочка дуплетов, которая обрабатывается как единый дуплет (рис. 6 б)R1, R2).

Дуплеты первой группы расщепляются однозначным образом, для дуплетов второй группы генерируется два варианта траектории (рис. 6 (г,е)).

6. Экспериментальные результаты 6.1. Метод проведения эксперимента Для исследований использовалась база, состоящая из 5200 изображений рукописных символов - 200 изображений каждой буквы английского алфавита (100 заглавных и строчных букв). Использовались изображения символов, полученные на различных сканирующих устройствах и написанные разными авторами, стили письма варьируются в самом широком диапазоне. База была разделена на две части - для настойки и тестирования системы.

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

Электронный журнал ИССЛЕДОВАНО В РОССИИ 1446 htttp://zhurnal.ape.relarn.ru/articles/2003/120.pdf В системе реализован полуавтоматический процесс создания верной траектории по изображению. Для каждого изображения базы после выделения регулярных и узловых областей, оператор с помощью мыши проводит линии, соединяющие регулярные области, которые образуют штрих в узле, или соединяющие случайные разрывы. Полученная информация записывается и хранится вместе с базой изображений.

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

Электронный журнал ИССЛЕДОВАНО В РОССИИ 1447 htttp://zhurnal.ape.relarn.ru/articles/2003/120.pdf а) RRб) RRв) Rг) Rд) RRе) RРис. 6. Восстановление траектории по изображению 6.2. Вычисление распределений для признаков Для расчета формул (2), (11) требуется знание следующих распределений:

Электронный журнал ИССЛЕДОВАНО В РОССИИ 1448 htttp://zhurnal.ape.relarn.ru/articles/2003/120.pdf p(k | c = 0), p(k | c = 1), p(d | s = 0), p(d | s = 1), p(C) для формулы (2) и p(k,r | b = 0), p(k,r | b =1), p(b =1) для формулы (11).

Для получения значений p(k | c = 0), p(k | c = 1) использовался метод гистограмм (см.

рис 7). Область значений k была разбита на 16 ячеек, для каждой ячейки было вычислено h(i) = N/Nобщ, где N - количество точек, попавших в ячейку (i), Nобщ - общее количество точек. Если в точке (i0) значение h(i0) меньше некоторого минимального порога, для его определения используется метод k ближайших соседей. Именно, берется множество Z = {z} из k непустых ячеек ближайших к (i0), включая (i0), и вычисляется на этом множестве значение h(i0 ) = h(z), где L - количество точек в минимальном отрезке с центром в L zZ (i0), который покрывает множество Z.

Распределения p(d | s = 0), p(d | s =1), p(k,r | b = 0), p(k,r | b =1) вычисляются аналогичным образом - 0.здесь также применяется метод гистограмм и метод p(k | c = k ближайших соседей.

0.В следующей таблице представлены 0.распределения априорной p(k | c = 0) вероятности классов 0.конфигураций p(C) для узлов размерности 3 (см.

рис. 2). Аналогичные 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 данные получены и для Рис. 7. Распределения p(k | c = 0), p(k | c = 1) полученные с узлов кратности 4. Всего помощью метода гистограмм 8 конфигураций кратности 3 разбивается на 4 класса и 41 конфигурация разбивается на 12 классов для m=4, при этом, отброшены 23 конфигурации кратности 4 не удовлетворяющие условию 1. Узлы кратности встречаются крайне редко, поэтому им присвоены равные значения p(C).

Таблица 1.

Pages:     | 1 | 2 | 3 |    Книги по разным темам