критических точек, который, строго говоря, является избыточным. В зависимости от параметров программы количество полученных точек в 2-2,5 раза превышает количество окончательно найденных экстремальных точек. Поэтому следующим шагом является удаление лишних точек, а также добавление новых, более точно характеризующих форму траектории. В частности, все точки перегиба подлежат удалению, т.к. располагаются, как правило, в середине «прямых» участков, что снижает их информационную значимость. Вместо этого мы добавляем в набор экстремальные точки, условно называемые экстремумами по кривизне, хотя само значение кривизны в этих точках может быть и не очень велико. В основу процедуры фильтрации положено следующее простое Утверждение. Критические точки, характеризующие горизонтальное плато, выделяются парами.

Доказательство. Рассмотрим величины dyprev = _ Pyx и dynext = P+1 _ P-y . i-я точка

принадлежат плато тогда и только тогда, когда dyprev = 0 или dynext = 0. Пусть при

последовательном просмотре точек кривой для i-той точки dynext = 0, тогда для i+1 точки

dyprev = 0. Значит i-тая и (+1)-ая точки принадлежат одному и тому же плато, что и

требовалось доказать. ■

Данное утверждение позволяет сформулировать правила отбора для точек плато Pu и Pd, где символ Pd означает, что точка может являться локальным минимумом, а символ

Рис.9. Пример подписи с горизонтальным штрихом.

Pu соответственно означает, что точка может являться локальным максимумом. В этих обозначениях на рис.8 представлены варианты плато {Pu,Pu} и {Pu,Pd}. Если обозначить буквой V вертикальный экстремум, а буквой C - экстремум по кривизне, то правила отбора запишутся в следующем виде:

{Pu,Pu}—{Vu} либо {Pd,Pd}—{Vd}, если размер плато меньше порогового; {Pu,Pu}—{C,Vu,C} либо {Pd,Pd}—{C,Vd,C}, если размер плато больше порогового; {Pd,Pu}^{0} либо {Pu,Pd}^{0}, если размер плато меньше порогового; {Pd,Pu}—{C,C} либо {Pd,Pu}—{C,C}, если размер плато больше порогового; аналогичные правила можно сформулировать и для случая горизонтальных экстремумов.

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

Рис. 10. Пример обработанной подписи, взятой из базы данных SVC 2004.

соответствия между вертикальными экстремальными точками. Приведенный выше алгоритм нахождения экстремальных точек вполне корректен, но он опирается на локальные особенности кривой, что может приводить к потере важной информации. На рис.9. приведен пример подписи, для которой сформированное представление является не точным, т. к. граничные точки горизонтального Т-штриха не указывают на наличие вертикального экстремума или плато (хотя это и не является ошибкой работы программы). Произошло это вследствие дрожания пера при исполнении данного штриха, а также в силу указанного локального рассмотрения окрестностей критических точек. Но это может привести к ошибке, поскольку применяемый алгоритм сопоставления ориентирован на нахождение пар вертикальных экстремумов противоположного типа. Вообще говоря, при другом исполнении этой же подписи данный горизонтальный штрих может быть классифицирован и обработан по правилу {Pu,Pu}—{C,Vu,C} (см. выше). Тем не менее, с целью избежать непредвиденных ошибок, последним этапом разметки подписи с помощью экстремальных точек является выделение горизонтальных участков. На этом же этапе помечались и заключительные горизонтальные штрихи (росчерки), если таковые в подписи присутствовали.

Заключение

Описанный метод нахождения экстремальных точек был использован для быстрого сопоставления динамических кривых. В отличие от альтернативных существующих подходов предложенный алгоритм позволяет более качественно учитывать особенности формы траектории (см. рис. 5,6). Собственно сам метод сопоставления кривых будет описан в следующей статье: «Быстрое сопоставление рукописных динамических подписей в биометрической системе контроля доступа».

Литература

1.R. Plamondon, G. Lorette. Automatic signature verification and writer identification - the state of the art. // Pattern Recognition, 1989, vol. 22, no. 2, pp. 107 -131

2.Д.В.Колядин. Анализ динамических кривых применительно к задаче верификации рукописной подписи // Математические методы распознавания образов (ММРО-11), 2003, с. 330-332

3.M. E. Munich, P.Perona. Visual Signature Verification using Affine Arc-length // Conference on Computer Vision and Pattern Recognition CVPR, 1999, pp. 2180-2186

4.V. S. Nalwa. Automatic On-Line Signature Verification. // Proceedings of the IEEE, 1997, vol. 85, no. 2, pp.215-239

5.T. Starner, J. Makhoul, R. Schwartz, G. Chou. On-line cursive handwriting recognition using speech recognition methods // IEEE Conference on Acoustics, Speech, and Signal Processing, 1994, vol. 5,

pp. 125-128

6.L. Yang, B.K. Widjaja, R. Prasad. Application of Hidden Markov Models for Signature Verification. // Pattern recognition, 1995, vol. 28, no.2, pp. 161-170

7.G. Seni, J. Seybold. Diacritical processing for unconstrained on-line handwriting recognition using forward search // International Journal on Document Analysis and Recognition, 1999, no. 1, pp. 2429

8.T. Hastie, E. Kishon. A Model for Signature Verification. // IEEE International Conference on Decision Aiding for Complex Systems, 1991, pp. 191-196

9.M.E. Munich, P.Perona. Continuous Dynamic Time Warping for translation-invariant curve alignment with applications to signature verification // California Institute of Technology International Conference on Computer Vision, 1999

10.E. Keogh, M. Pazzani. Scaling up Dynamic Time Warping for Datamining Applications. // The 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2000

11.S.Chu, E.Keogh, D.Hart, M.Pazzani. Iterative Deepening Dynamic Time Warping for Time Series // IEEE International Conference on Data Mining, Maebashi City, Japan, 2002

12.A. K. Jain, F. D. Griess, S. D. Connell. On-line Signature Verification. // Pattern Recognition, vol. 35,

no. 12, pp. 2963-2972, 2002

13.S.D. Connell, A.K. Jain. Template-based Online Character Recognition. // Pattern Recognition, 2001, vol. 34, no. 1, pp.1-14

14.F. Hao, C. W. Chan. Online Signature Verification Using a New Extreme Points Warping Technique // Pattern Recognition Letters, 2003, vol. 24, no. 16, pp. 2943-2951

15.Д.В.Колядин, А.А.Савин. О проблеме верификации подписи в системах контроля доступа // Обработка информации и моделирование. - М.: МФТИ, 2002, с.81-89

16.Р.М.Ланцман. Кибернетика и криминалистическая экспертиза почерка. - М.: Наука, 1968, 94 с.

17.X. Li, M. Parizeau, R. Plamondon. Detection of Extreme Points of On-line Handwritten Scripts // Pattern Recognition Progress in Handwriting Recognition, A. C.Downton (ed.), S. Impedovo (ed.), 1997