Книги по разным темам Pages:     | 1 | 2 | 3 | Электронный журнал ИССЛЕДОВАНО В РОССИИ 1437 htttp://zhurnal.ape.relarn.ru/articles/2003/120.pdf Восстановление траекторий написания символов по их изображениям Поцепаев Р.В. (roman575@mail.ru ) Московский Физико-Технический Институт 1. Введение Большинство существующих методов решения лоффлайн1 задачи распознавания символов включает три основных этапа обработки: предобработка, формирование набора признаков и классификация. Набор признаков формируется по следующим видам информации, полученным на этапе предобработки [3]: бинарная матрица, сглаженный граничный контур и скелет изображения. Такой подход позволил достичь высокой точности распознавания печатных и аккуратно написанных символов.

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

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

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

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

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

Электронный журнал ИССЛЕДОВАНО В РОССИИ 1438 htttp://zhurnal.ape.relarn.ru/articles/2003/120.pdf В последнее время задаче восстановления траектории посвящено большое количество публикаций [4-13]. Кратко рассмотрим основные результаты в данной области.

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

Восстановление траектории по скелету изображения имеет существенный недостаток:

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

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

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

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

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

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

3. Предобработка и постановка задачи восстановления траектории Обычно траектория символа имеет разрывы, соответствующие отрыву пера от бумаги.

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

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

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

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

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

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

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

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

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

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

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

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

0 0 1 0 1 1 0 0 0 0 0 1 0 С3 = 0 0, С4 =, С3 =0.

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

будем говорить, что в узел входят регулярные области с номерами 1..m, хотя, конечно, это не всегда так.

Для нахождения правильной конфигурации используется байесовское решающее правило [16]. Если узел X имеет конфигурацию, то математическое ожидание потерь связанное с выбором неверной конфигурации есть r (X ) = p(C | X )L(C,), где p(C | X ) - апостериорная вероятность конфигурации C ;

CTm L(C,) - стандартная функция потерь выбора конфигурации C при верной конфигурации.

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

C* = arg min rC (X ) = arg max p(C | X ) (1) CTm CTm Согласно формуле Байеса выражение (1.1) можно представить в следующем виде:

p(X | C) p(C) C* = arg max = arg maxln(X | C) + ln p(C) - const, (2) CTm p(X | C) p(C) CTm CTm где p(X | C) - функция правдоподобия для конфигурации С;

Класс 3.p(C) - априорная вероятность возникновения конфигурации С;

const = ln p(X | C) p(C).

Класс 3. CTm 4.2. Определение значения априорной Класс 3.вероятности p(C).

На множестве всевозможных матриц Tm для узла кратности m рассмотрим Класс 3.следующее бинарное отношение. Пара Рис.2 Всевозможные конфигурации для узла кратности m=3. Конфигурации разбиты на классы эквивалентности Электронный журнал ИССЛЕДОВАНО В РОССИИ 1441 htttp://zhurnal.ape.relarn.ru/articles/2003/120.pdf матриц < C1,C > принадлежит, если существует циклическая перестановка со следующим свойством: матрица C1 переходит в матрицу C если переставить столбцы и строки матрицы C1 согласно этой перестановке. Легко показать, что данное отношения есть отношение эквивалентности и конфигурации из одного класса эквивалентности имеют одинаковую структуру и отличаются лишь нумерацией регулярных областей входящих в узел (см. рис. 2). В каждый класс входят не более m конфигураций, так как существует только m циклических сдвигов. В дальнейшем будем предполагать, что конфигурации из одного класса имеют одинаковую вероятность появления на изображениях символов.

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

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

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

1 = tg, 2 = tg; P3(0) = 0; P3(L) = 0; P3'(0) = 1; P3' (L) = 2; (3) Значения коэффициентов полинома определяются единственным образом 1 + 2 - 21 - 2 P3(t) = t3 + t + 1t; (4) L2 L В качестве одного из признаков удобно было бы принять интеграл кривизны, однако определение значения интеграла кривизны затруднительно с вычислительной точки L '' зрения. На практике применяется интеграл I = (t))2 dt. В нашем случае, его значение (P может быть найдено аналитически: I = (1 + 12 + 2 ) ; (5) L Следует сказать о важной физической интерпретации полученных результатов: пусть заданы граничные условия - начальное и конечное положение пишущего инструмента, а также начальный и конечный вектор его скорости. Полученный интеграл пропорционален минимальным затратам мышечной энергии (ускорение в каждой точке), необходимым для перемещения пишущего инструмента с сохранением граничных условий.

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