Популярное

Мифы о звукоизоляции



Как построить дом из пеноблоков



Как построить лестницы на садовом участке



Подбираем краску для ремонта



Каркасные дома из дерева


Главная » Восстановление траекторий написания

1 2

Восстановление траекторий написания символов по их

изображениям

Поцепаев Р.В. (roman575@mail.ru )

Московский Физико-Технический Институт

1. Введение

Большинство существующих методов решения оффлайн1 задачи распознавания символов включает три основных этапа обработки: предобработка, формирование набора признаков и классификация. Набор признаков формируется по следующим видам информации, полученным на этапе предобработки [3]: бинарная матрица, сглаженный граничный контур и скелет изображения. Такой подход позволил достичь высокой точности распознавания печатных и аккуратно написанных символов.

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

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

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

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

2. Предшествующие работы

Существуют две различные постановки задачи распознавания символов. В оффлайн задаче [1] изображение символа получается при сканировании документа, содержащего рукописный текст - входными данными являются матрицы точек. Другой способ получения изображения - это использование специальных устройств, таких, как графический планшет; входными данными для задачи являются траектории движения пера, представляющие собой последовательности координат пера полученных в процессе написания символа. Такая задача называется задачей онлайн распознавания [2]. Термины оффлайн и онлайн распознавание заимствованы из англоязычной литературы, которые в оригинале звучат как off-line handwritten recognition и online handwritten recognition.



В последнее время задаче восстановления траектории посвящено большое количество публикаций [4-13]. Кратко рассмотрим основные результаты в данной области.

В работе [4] С. Ли и Дж. Пен предложили метод восстановления траектории подписи, основанный на применение набора эвристик к скелету изображения. В работах Говиндараджи и др. [5,6] описано восстановление траектории написания слов путем нахождения наиболее гладкого пути в каждой окрестности пересечения. В дальнейшем, разными авторами был предложен ряд методов, также основанных на использовании скелета и набора эвристических правил для восстановления траектории в точках пересечения линий скелета [7-9].

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

Д. Доэрманн и А. Розенфельд [10,11] предложили решение задачи восстановления штрихов для изображений с градацией серого, написанных с использованием определенного пишущего инструмента. В этом подходе вместо скелета изображения используется совокупность: матрица изображения, граничный контур и некоторое дополнительное представление изображения.

Одна из наиболее универсальных моделей восстановления штрихов в окрестности их пересечений предложена Э. Л'Омером [12]. В модели используются следующие идеи: разделение изображения на отрезки штрихов и области их пересечения, аппроксимация границ штрихов в окрестности узлов полиномами четвертого порядка, статистический подход к принятью решений. Точность восстановления узлов в этом методе выше, чем в методах, опирающихся на скелет изображения. Модель имеет недостатки: высокая вычислительная сложность, отсутствует восстановление всей траектории.

Вероятно, по локальному изображению узловой области невозможно восстановить траекторию в узле, а следовательно, и всю траекторию с высокой точностью. Об этом свидетельствует анализ предшествующих работ. Для дальнейшего увеличения точности требуется дополнительная информация или дополнительные ограничения на вид возможных траекторий. В работе [13] Йо. Като и М. Ясухара предложили метод, который с очень высокой точностью восстанавливает траекторию символа, однако при этом на траекторию накладываются существенные ограничения, в частности, отсутствие отрывов пера от бумаги при написании.

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

3. Предобработка и постановка задачи восстановления траектории

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



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

Описываемый здесь подход базируется на этапе предобработки, который состоит в следующем: изображение символа разбивается на полосы черных точек, соответствующие непересекающимся отрезкам штрихов - регулярные области, и области пересечения штрихов - узловые области. Подобные алгоритмы предобработки описаны в работах различных авторов [12, 14, 15]. Здесь используется метод, предложенный Р. Поцепаевым, И. Петровым [15] в котором регулярные и узловые области строятся на основе граничного контура изображения сглаженного с помощью линейной аппроксимации.

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

Условие 1. Регулярная область либо принадлежит одному штриху и входит в этот штрих как его часть не более двух раз либо принадлежит двум разным штрихам и входит в каждый из них строго по одному разу.

Каждый штрих из набора штрихов можно представить в виде последовательности

регулярных областей

соединенных в узлах и

разрывах. средних линий из

последовательности можно получить каждую траекторию из набора.

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

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


.........l


Рис. 1. Изображение на каждом этапе обработки:

а) начальное изображение, б) набор регулярных областей,

в) восстановленная траектория

случайных

Соединением

областей

4. Восстановление штрихов в узлах и разрывах

4.1 Байесовская модель принятия решений



Рассмотрим некоторый узел и концы средних линий всех регулярных областей, входящих в него. Одна и та же область может входить в узел обоими концами. Начиная с произвольной точки, произведем обход границы узла по часовой стрелке и пронумеруем концы регулярных областей в той последовательности, в которой они входят в узел числами от 1 до т. Решение задачи восстановления штрихов в узле, иначе говоря, конфигурацию узла можно представить в виде симметричной бинарной матрицы Cm, причем ci j = 1, если концы регулярных областей с номерами i и j образуют часть штриха.

Сумма элементов в строке не превосходит двух, что следует из условия 1. Например, правильным решениями для узлов на рисунке 5 будут матрицы (номера концов средних линий областей совпадают с номерами областей):

( 0 1 1

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

Для нахождения правильной конфигурации используется байесовское решающее правило [16]. Если узел X имеет конфигурацию С, то математическое ожидание потерь связанное с выбором неверной конфигурации есть

rC( X) = x PCIX) L(C, С), где p(C X) - апостериорная вероятность конфигурации С ;

стандартная функция потерь выбора конфигурации при верной конфигурации

L(C, С)

В качестве решения выберем конфигурацию С * минимизирующую математическое ожидание общих потерь:

С * = arg min гС (X) = arg max р(С X) (1)

СеТт СеТт

Согласно формуле Байеса выражение (1.1) можно представить в следующем виде: С * = arg max ( X1 С) р(С)- = arg max ln( X С) + ln р(С) - const

СеТт P(X С)р(С) СеТт


Класс 3.4

где p(X С) - функция правдоподобия для конфигурации С; р(С) - априорная вероятность возникновения конфигурации С; const = ln x р(X С) р(С).

4.2. Определение значения априорной вероятности р(С).

На множестве всевозможных матриц Тт для узла кратности т рассмотрим следующее бинарное отношение р. Пара

Рис.2 Всевозможные конфигурации для узла кратности т=3. Конфигурации разбиты на классы эквивалентности



C1, C:

принадлежит p, если существует циклическая перестановка со

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

4.3. Определение функции правдоподобия p(X C).

Величина p(X C) вычисляется на основе двух признаков, первый признак kj определяются для каждой пары регулярных областей Rt, Rj входящих в узел, второй признак dt определяется для каждой регулярной области Rt, t=1..m. Рассмотрим признаки более подробно.

4.3.1. Признак kj

Рассмотрим регулярные области Rt, Rj в окрестности узла. Возможную траекторию, соединяющую Rt, Rj внутри узла представим в виде полинома третьей степени P3(t) для которого выполнены следующие условия (рис. 3):

X = tga, X2 = tge; Р,(0) = 0; РЪ(Ь) = 0; P,(0) = X; P±(L) = X; (3)

Значения коэффициентов полинома определяются единственным образом

P3(t):

X + Л2 3 - 2/lj - X

2 Л

-г +-1-2-1

LL L

+Xt;

В качестве одного из признаков удобно было бы принять интеграл кривизны, однако определение значения интеграла кривизны затруднительно с вычислительной точки

зрения. На практике применяется интеграл I = j*(P3 (t))2dt. В нашем случае, его значение

может быть найдено аналитически: I

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

перемещения пишущего инструмента с сохранением граничных условий.

То, что затраты действительно минимальны следует из утверждения, которое несложно доказать: для любой функции ft, te [0,L], удовлетворяющей граничным


условиям (3), величина Jft2dt

Рис. 3. Восстановление траектории в узле

>



превышает значения полученного интеграла I = j*st2 dt.

где st

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

I (А2 + А1А2 + Л2.)

если а < - ,р< - то k 2 2

иначе

kj =+<*>

L13

к13 =

k23 =

1.132 2.04

10.4

= 21.8

Рис. 4. Различные значения признака kj.

j

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

Если L достаточно мало, то использование признака kj может приводить к неверным результатам, поэтому, если значение L меньше заданной константы Lmin, то начальная и конечная точки смещаются внутрь регулярных областей на равные расстояния. Значение Lmin определяется экспериментально.

В некоторых случаях, о которых будет сказано ниже, значение kj вычисляется не по

4.3.2. Признак di

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

4.3.3. Вычисления признаков kj для дуплетов

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

Если же регулярная область Ri является дуплетом и пары областей {Ri, Rj}, { Ri, Rk} образуют штрихи, то невозможно однозначно решить, которой из границ штрихов { Ri, Rj}, { Ri, Rk} принадлежит каждая из двух границ области Ri так как имеет место наложение штрихов друг на друга. Таким образом, из четырех возможных границ двух штрихов BiiAiiAjrBjr, BiiAiiAkrBkr, BirAirAkiBki, BirAirAjiBji лишь две границы наблюдаются

B1r B1l


B1r,


B1r B1i


A1rl A3l

(а) (б)

Рис. 5. Примеры узловых областей. Ri - регулярная область; Ломанные BilAil, BirAir левая и правая границы области; AilAir - отрезок соединения узла и области Ri.



изображении (см. рис. 5а, область R1 - дуплет, штрихи {R1, R2}, {R1, R3}). Траектории штрихов {Ri, Rj}; {Ri, Rk} внутри области Ri не совпадает со средней линией, поэтому признаки кц, ktk определяются не по двум средним линиям, а по двум границам. Рассматривается два возможных варианта: kj определяется по BilAnAjrBjr, kik определяется по BirAirAkiBki, либо kj, определяется по BiiAiiAkrBkr, kik определяется по BirAirAjiBji Для определения kj, kik рассматриваются оба варианта, и выбирается тот, в котором значение p(kij cij = 1) p(kik cik = 1) максимально (см. формулу 8).

Информацию об окрестности узла представим в виде X = { kJ , d,dm}, с учетом

II J llmxm

kj = kji i, j e 1 ..m. Метод восстановления штрихов в узле основывается на следующих предположениях: траектория и границы внутри узла имеют малую кривизну (признак kij.);

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

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

p( X C) = p(kJ x , ddm C) = p(kj x C)p(ddm C) (7)

mxm mxm

Также, будем считать, что плотность распределения признака kij зависят только от факта, образует ли штрих пара Ri, Rj, т.е. зависит только от значения cij. Таким образом

mm i=1 j=i+1

Если области Ri, Rj не являются дуплетами, то kj вычисляются по средним линиям, в противном случае вычисления производятся с использованием границ областей как описано выше.

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

p(d,dmC) = П p(diK), (9)

где si = 1 если cij. = 2, т. е. Ri - дуплет, иначе si = 0. Окончательно, подставляя (8), (9) в (7) имеем

p(X C) = П p(dii) П P(kjCj) (10)

i=1 j=i+1

Таким образом, среди множества возможных конфигураций 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 Поиск и восстановление случайных разрывов

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



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

После процедуры выделения регулярных областей, задача поиска разрывов траектории сводится к поиску пар точек, являющихся концами средних линий регулярных областей, которые образуют разрыв. Пусть Ri, Rj - регулярные области, точки Pid, Pj, d, s e {0,1} -

концы средних линий этих областей, для которых решается задача о разрыве. Признаками для получения функций правдоподобия служат: расстояние между точками r и уже известные признак k, который вычисляются по средним линиям пары областей Ri, Rj между точками Pid, Pj так же, как в задаче восстановления узлов. Если значения r, k

превышают порог, пара Pid, PJ как возможный разрыв не рассматривается.

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

р(Ь = 11 k, r) =-, rb =1) р(Ь =1)-; (и)

р( r Ь = 1)р(Ь = 1) + р( r Ь = 0)(1 - р(Ь = 1))

Пара (Pid, Pj) определяется как разрыв, только если р(Ь = 11 k, r) > 0.5.

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

5. Построение наборов траекторий

5.1. Построения списка гипотез об узлах и разрывах символа

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

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

Пусть на изображении имеется р узлов и q возможных разрывов. Выберем конфигурации узлов С1Сри разрывов Ь1Ьч, причем Ь = 1, если некоторая пара (Pid, Pj) концов регулярных областей рассматривается как разрыв, иначе Ь = 0. Пары ( Pid , Pjs ), для которых значения параметров превышает некоторый порог, как возможные

разрывы не рассматриваются и не входят в набор Ь1,..., Ьч.

Из формул (2), (11) следует, что вероятность возникновения траектории равна

P(I) = P(C1Ср, Ь1Ьq X1, r1, k1rq, kq) = П P(Gi) fl Pihr1, ki), (12)

i=1 i=1

где Т - траектория, I - информация об изображении.

Очевидно, что 11) принимает максимальное значение для конфигураций,

имеющих максимальную меру P(G X) и для возможных разрывов со значением P( r, k) > 0.5.



Однако экспериментальная проверка методов определения конфигураций узлов и поиска разрывов показала, что достоверность методов (см. параграф 6) ниже точности, необходимой для распознавания. Следовательно, достоверность того, что по набору C1Cp,b1bq для которого P(Ci X), P(bi r,k) максимальны, будет построена действительная траектория изображения также меньше точности, необходимой для распознавания.

Данная проблема может быть решена следующим образом: отсортируем всевозможные наборы C1Cp,b1bq по убыванию величины P(T11). Для построения гипотез о наборе траекторий отбирается только часть полученного списка. Длина списка N может быть фиксирована - выбираются первые N наборов, либо фиксируется вероятность Р попадания верной траектории в список, и длина списка N выбирается так, чтобы сумма вероятностей траекторий из списка превосходила Р.

5.2. Преобразование гипотезы об узлах и разрывах в гипотезу о наборе траекторий

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

На рисунке 6 представлены примеры работы алгоритма построения набора траекторий по известной набору C1Cp,b1bq который имеет максимальную меру P(T11). Во всех примерах на рисунке 6 по набору C1Cp,b1bq строится верная траектория.

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

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

6. Экспериментальные результаты

6.1. Метод проведения эксперимента

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

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



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

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





1 2
© 2017 РубинГудс.
Копирование запрещено.