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

Аналогичный способ сопоставления кривых был ранее предложен в работе [15]. Однако невозможность учесть некоторые вариативные особенности почерков, а также накопление ошибок в ходе последовательного сопоставления хорд, образуемых соответствующими экстремальными точками, потребовало пересмотреть процедуру отбора и сопоставления экстремальных точек. Ниже мы излагаем улучшенный вариант нахождения экстремальных точек по сравнению с работами [4,14,15].

Выделение экстремальных точек

В той или иной степени многие подходы к верификации рукописной подписи основываются на процедуре нахождения характерных или экстремальных точек. Одной из первых работ в области верификации статической рукописной подписи в Советском Союзе была проделана совместно сотрудниками Вычислительного центра Ленинградского университета и Литовского института судебных экспертиз [16]. В этой работе точки выбирались вручную, после чего их координаты вводились в ЭВМ для обработки. Применение сенсорных панелей и графических планшетов позволяет автоматизировать данную процедуру. Но какие точки кривой являются наиболее информативными? Как правило, выбор падает на точки со значением кривизны больше некоторого порогового значения. Вычисление кривизны по формуле дифференциальной геометрии требует существования второй производной по времени, что накладывает ограничение на гладкость исследуемой траектории.

Поэтому на практике кривизну определяют по скорости пера (для этого требуется только первая производная) как коррелированной величины [8], при этом в качестве порогового значения выбирается значение, составляющее 15-18% от средней скорости

написания (см. рис.4). Либо заменяют предел c = lim Да, где Да- изменение угла

Дл—0 Д

Рис.4. Зависимости кривизны траектории и значения модуля скорости от времени [8].

наклона касательной на протяжении участка траектории от s до Д^, на конечную разность. Кривизна траектории в i-той точке семейства точек Pi _ 2, Pi-1, Pi, Pi+1, Pi+2 определяется по

углу между векторами Pi_2, Pi и Pi, Pi+2. Как вариант, допустимо заменить функцию кривизны ее дискретным аналогом в виде временной последовательности изменения углов [17].

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

Определение 1. Вертикальным экстремумом называется точка {x(t*),y(t*)}, для

которой

dy(t)

dt

t=t *

0 .■

Определение 2. Горизонтальным экстремумом называется точка {x(t*),y(t*)}, для

которой

dx(t)

dt

t=t *

0 .■

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

утверждать, нахождения оптимальны, подходу и очень часто

Рис.5. Русские буквы «Я».

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

приводится пример двух русских букв «Я» отличающихся формой траектории. Из-за пропуска точки, характеризующей выпуклость на ниспадающем участке, первая буква может быть ошибочно классифицирована как буква «е». Разработанный способ нахождения экстремальных точек позволяет отслеживать изменения траектории указанного типа, что особенно важно при распознавании рукописных букв и слов, например, при графическом вводе текста на карманных компьютерах. На рис. 6. мы приводим «скелетное» представление тех же самых букв, полученное путем соединения экстремальных точек. Из этого рисунка видно, что вся необходимая информация о структуре букв была сохранена и передана гораздо меньшим количеством точек. Как было установлено в работе [15] сопоставление всех точек сегментов по евклидовой мере с последующим суммирование всех локальных штрафов может приводить к ошибкам распознавания, когда рукописное слово «Лена» сопоставляется со словом «Леша», т.к. штраф за пропуск лишнего элемента оказывается меньше итогового штрафа за несоответствие двух вариантов слова «Лена».

На рис.7. приведена последовательность шагов, выполняемых для получения набора экстремальных точек. Первые две процедуры относятся к этапу предобработки,

Рис.6.

Пример нахождения экстремальных точек.

когда исходная траектория сглаживается и производится повторная выборка точек методом интерполяции (resampling) для получения эквидистантного представления кривой. Поскольку вследствие шумов в оцифровке, а также дрожания пера точки располагаются неровно вдоль траектории, то желательно производить сглаживание кривой. Для этой цели был использован достаточно простой, но эффективный метод сглаживания по координатам соседних точек. По сравнению с более распространенным методом сглаживания «по Гауссу» он обладает меньшей вычислительной стоимостью при практически тех же результатах. Усреднение проводилось по двум соседям, отдельно для каждой из координат, по формулам:

X smoothed (i) = X X (i _ 1) + Уг X (i) + X X (i +1)

Ysmoothed (i) = % Y(i _ 1) + )2 Y(i) + У4 Y(i + 1)

Полученное представление кривой использовалось для нахождения критических точек. Здесь и далее условимся использовать термин «критические точки» для обозначения предварительно найденных экстремальных точек, т. к. затем часть из этих точек будет отфильтрована (см. рис.7). В отличие от работы [6] мы не исключали из рассмотрения критические точки с малым перепадом по высоте, поскольку последовательность таких точек может образовывать так называемое «плато» (см. рис.8). Аналогичная ситуация возможна и с нахождением горизонтальных критических точек. Поэтому на шаге

Повторная выборка

Выделение экстремальных точек

Выделение росчерков

Рис.7. Последовательность этапов поиска экстремальных точек.

нахождения критических точек выделялись следующие типы точек: концевые точки сегментов кривой, вертикальные и горизонтальные экстремумы, граничные точки вертикального плато, а также точки перегиба. При этом для нахождения вертикальных экстремумов применялось простое эвристическое правило: точка Pi является экстремальной, если выполнено условие: (P_1 _ P/ )(Py _ P+1) < 0.

Если для некоторой i-той точки приведенное выражение обращается в ноль, причем ординаты трех последовательных точек не совпадают, то такая точка добавлялась в набор как граничная точка плато. Аналогично находились и горизонтальные экстремумы (критические точки). Поскольку особое внимание уделялось быстроте и эффективности алгоритма, точки перегиба находились не из равенства нулю второй производной, а путем анализа знака векторного произведения sign\Pi_2Pi х Pi+2Pi]. Последнее выражение в нашем случае можно заменить на упрощенную координатную запись для плоского случая:

sign((P_2 _ PiX )(Pf+2 _ Piy ) _ (P^_2 _ Piy )(Pi+2 _ P

Таким образом, после выполнения данного шага мы получаем набор

Рис.8. Горизонтальные плато.