Книги по разным темам Pages:     | 1 | 2 | Электронный журнал ИССЛЕДОВАНО В РОССИИ 181 Эффективный алгоритм предобработки изображений для структурных методов распознавания рукописных символов Поцепаев Р.В. (roman575@mail.ru ), Петров И.Б.

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

входными данными для задачи являются траектории движения пера, представляющие собой последовательности координат пера. Такая задача называется задачей лонлайн распознавания [2].

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

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

Существующие методы восстановления траектории пишущего инструмента в качестве входной информации используют либо скелет изображения [4-6], либо контур изображения [3]. Несмотря на большую эффективность использования скелетизации в других методах распознавания [7,8], восстановление траектории по скелету изображения имеет существенный недостаток: критически важной информацией при восстановлении траектории является форма граничного конура в окрестности областей пересечения штрихов. Из скелета изображения эта информация недоступна (см. рис. 1). К недостаткам Термины лоффлайн и лонлайн распознавание заимствованы из англоязычной литературы, которые в оригинале звучат как off-line handwritten recognition и on-line handwritten recognition Электронный журнал ИССЛЕДОВАНО В РОССИИ 182 скелетизации можно отнести также большую чувствительность к шуму на границе изображения и, как следствие, возникновение случайных лотростков в скелете изображения. Поэтому методы восстановления траектории, основанные на получении скелета, приводят к ошибкам при обработке изображений c достаточно сложной траекторией.

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

Искажение области пересечения траекторий Необходимо восстановлени е траекторий по форме границ в окрестности узловой Рис. 1. Изображение символа и его скелет Существующие алгоритмы выделения регулярных областей основываются на точечной обработке изображений [3,9]. В данной работе предлагается алгоритм, построенный только на использовании ломаной, аппроксимирующей контур изображения.

Основными особенностями предлагаемого метода являются:

Х высокая скорость обработки изображений, которая достигается за счет отсутствия точечной обработки;

Х отсеивание изображений, для которых метод выделения траекторий неприемлем (изображения с пятнами и заплывами) уже на этапе предобработки.

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

2. Модель изображения символа и постановка задачи Как уже было сказано, рукописному символу соответствует набор траекторий движения пера T1,Е Tn. Каждую траекторию Ti представим в параметрическом виде {x=xi(t), y=yi(t), t[0,1]}. Будем считать, что область соприкосновения пишущего инструмента с бумагой представляет собой круг с некоторым радиусом, зависящим от давления пера на бумагу: {r=ri(t), t [0,1]}, причем скорость изменения радиуса вдоль траектории ограничена, т.е. dr / dl < const, где l(t) - длина траектории.

Электронный журнал ИССЛЕДОВАНО В РОССИИ 183 Штрихом траектории Ti назовем область черных точек Hi = {(x, y) | t [0,1] (x - xi (t))2 + (y - yi (t))2 (ri (t))2}. (1) Область всех черных точек G на изображении представляет собой в точности объединение множества штрихов всех траекторий, т.е. G = H1... Hn. В описанных терминах, общая задача восстановления траектории движения пера формулируется следующим образом: по известному изображению символа G необходимо восстановить множество траекторий {T1,Е Tn}.

Под огибающей семейства окружностей {(x - xi (t))2 + (y - yi (t))2 = (ri (t))2, t [0,1]} понимается кривая, которая в каждой своей точке касается некоторой окружности из заданного семейства (см. рис. 2). В случае если штрихи перекрываются, а также, если кривизна штриха больше некоторого значения (для штрихов с постоянным радиусом r это значение равно (t) = 1/ r, см. рис. 3), отрезки огибающей оказываются внутри области G, т.е. не принадлежат границе.

Под регулярной областью будем понимать отрезок штриха {(x, y) | t [a,b], 0 a < b 1, (x - xi (t))2 + (y - yi (t))2 (ri (t))2}, для которого пара принадлежащих ему отрезков огибающей принадлежит G, другими словами, обе границы которого видны на изображении.

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

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

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

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

3. Выделение прямолинейных участков траектории Будем говорить, что отрезки s и t, принадлежащие одному или различным граничным контурам, находятся в отношении R, если возможно построить равностороннюю Электронный журнал ИССЛЕДОВАНО В РОССИИ 184 трапецию, со сторонами на отрезках s и t, удовлетворяющую следующим условиям (см.

рис. 4):

1. Основания трапеции d1, d2 соединяющие точки отрезков s и t полностью лежат внутри области черных точек;

2. Углы, у оснований трапеции отличаются от прямого угла не более чем на заданную величину max ;

d1 d3. Значения, не превосходят заданной величины dmax ;

sin sin а) б) в) Рис. 4. Трапеция, построенная на отрезках s и t. Стрелками показано направление Рис. 5. а, б) удаление трапеций, в) уменьшение обхода контура, при котором область высоты трапеций черных точек находится справа Область, ограниченная трапецией обладает всеми свойствами прямолинейного отрезка штриха с равномерно изменяющимся радиусом пера: линия, соединяющая середины оснований есть отрезок траектории, стороны трапеции - огибающие семейства окружностей. Условие 1 означают то, что отрезок штриха является областью черных точек (хотя допустимы белые пятна внутри штриха), условие 2 ограничивает скорость изменения диаметра пишущего инструмента, условие 3 определяет максимально возможный диаметр dmax пишущего инструмента.

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

Отметим некоторые особенности практической реализации Nпостроения трапеции на произвольных отрезках контуров s и t.

PВначале определяется максимально возможная трапеция с учетом только второго условия. Когда трапецию удается построить, если необходимо, она уменьшается до размеров, при которых O1 d Oвыполняется третье условие. Рассмотрим одно из оснований трапеции O1O2 и отрезки на контурах P1O1, O1N1, P2O2, O2N2, причем область черных точек находится справа при проходе по этим отрезкам в направлении второй точки (см. рис. 6).

P1 NНапомним, что если векторное произведение ab положительно, Рис. 6.

Электронный журнал ИССЛЕДОВАНО В РОССИИ 185 то кратчайший поворот вектора b совмещающий его направление с направлением вектора a происходит по часовой стрелке.

Первое условие принадлежности основания O1O2 к области черных точек равносильно следующему ряду условий, которые легко реализуемы в алгоритме: O1O2 P1O1 > 0 ;

O1O2 O1N1 > 0 ; O2O1 P2O2 > 0 ; O2O1 O2N2 > 0 ; отрезок O1O2 не пересекается ни с одним из отрезков контуров, кроме s и t.

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

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

Каждой трапеции поставим в соответствие меру валидности m = -a 2dср - d1 - d2 - b - + c h, (2) где dср - средняя толщина штриха, вычисленная по всем символам; a, b, c - коэффициенты, определяемые экспериментально. Очевидно, что чем больше трапеция похожа на прямолинейный отрезок штриха с постоянным диаметром равным dср, тем больше ее мера валидности m. Если две трапеции имеют общую область не нулевой площади, то трапеция с меньшей мерой валидности либо удаляется, либо уменьшается до размера, при котором трапеции не имеют общей области (см. рис. 5). Если внутри трапеции находится замкнутый контур, т.е. область белых точек, что не противоречит условиям 1Ц3, то в зависимости от меры валидности, либо контур удаляется, как случайный, либо удаляется трапеция, содержащая внутренний контур.

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

Х K = 0: в области не удалось выделить ни одной трапеции и в дальнейшем область рассматривается нераспознаваемое пятно;

Х K = 1: область является концом штриха если она удовлетворяет критерию регулярности (см. далее критерий регулярности узловых областей);

Х K = 2: область является отрезком траектории между двумя трапециями если она удовлетворяет критерию регулярности (см. далее критерий регулярности);

Х K > 2: найдена область пересечения штрихов.

3 а) б) в) г) д) Рис. 7. Числами обозначена кратность областей: а) пятно; б) концевая область; в) области для соединения; г) узел кратности 3; д) узел кратности Электронный журнал ИССЛЕДОВАНО В РОССИИ 186 4. Критерий регулярности узловых областей В большинстве случаев узловая область кратности 2, как и соседние с ней трапеции, представляет собой отрезок штриха (разница лишь в том, что трапеции образованы прямолинейными отрезками траектории, а узловая область кратности 2 - криволинейным отрезком). Это предположение выполняется в большинстве случаев, но не всегда. Для изображений, в которых толщина штриха сравнима с размерами символа, несоответствие наблюдается особенно часто (см. рис. 9аЦ9в), кроме того пятна на изображении могут также классифицироваться как узловые области (рис. 9б). Рассмотрим эвристический критерий для определения, является ли область кратности 2 отрезком одного штриха либо представляет собой нечто иное.

Разобьем стороны узловой области на равные dmax lотрезки длиной h = и соединим концы ll0 lотрезков, которые делят стороны приблизительно в равных отношениях как показано на рисунке 8.

l6 lКаждый из построенных отрезков, соединяющий l l4 противоположные стороны, рассматривается как диаметр окружности пера с центром в середине отрезка. Ломаная, соединяющие середины отрезков Рис. 8.

рассматривается как возможная траектория внутри узловой области.

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