Алгоритм выделения экстремальных точек применительно к задаче биометрической верификации

рукописной подписи

Колядин Д.В. (dvkmail2000@mail.ru), Петров И.Б.

Московский физико-технический институт (государственный университет)

Введение

В научной литературе принято отсчитывать начало активных исследований в области верификации рукописной подписи с работы [1], в которой были сформулированные основные направления и подходы к решению данной проблемы. Хотя работы в области применения ЭВМ к криминалистической экспертизе почерка проводились и ранее, но развитие компьютерных технологий сделало возможным проведение анализа динамики начертательных движений возникающих при исполнении рукописной подписи. Специальные графические планшеты позволяют отслеживать траекторию движения пера, а также угол наклона ручки и оказываемое на перо давление. В англоязычной литературе этот подход носит название «on-line» метода распознавания, в отличие от анализа отсканированных изображений или «off-line» метода распознавания. Именно возможность измерения динамики делает привлекательным использование рукописной подписи как биометрического параметра, удобного для применения в широком спектре информационных систем. В настоящий момент проводятся исследования по данной проблематике различными исследовательскими группами. Первый международный конкурс программ по верификации рукописной подписи: SVC 2004: First International Signature Verification Competition состоялся в начале 2004 года. В этом конкурсе принимали участие команды из девяти стран: Австралии, Германии, Испании, Китая, Кореи, Сингапура, США, Турции, Франции.

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

Постановка задачи

Под динамической (или «on-line») кривой подразумевается параметрически заданная кривая Г : {x(t),y(t), t e [0, T]}. Информация, содержащаяся в данной временной последовательности, отражает динамику мускульных движений руки и поэтому может быть использована как биометрическая характеристика человека. В настоящее время общепринятой является такая схема построения систем доступа, в которых пользователь указывает свой идентификатор, подтверждаемый затем рукописной подписью. Предлагаемый подход позволяет пользователю предоставлять системе только свою подпись, по которой программа находит эталон (проводит идентификацию), а затем проверяет подлинность предъявленной подписи (осуществляет верификацию) [2]. Такой метод биометрической идентификации, очевидно, обладает большей функциональностью и имеет более широкую область применения. Для решения задачи поиска эталона в данной работе предлагается описывать динамическую кривую набором экстремальных точек. Строго говоря, динамические кривые могут быть параметризованы различными способами. Поскольку подавляющее большинство исследователей занимается только

задачей верификации, то наиболее распространенной является временная параметризация. Однако помимо временной параметризации, возможна параметризация по длине

траектории:

ds

= 1, что означает постоянство скорости перемещения вдоль траектории.

Также допустима аффинная параметризация по длине траектории, удовлетворяющая

условию:

дГ d2 Г

х

ds ds

= 1,

что

означает постоянство площади параллелограмма

дГ

построенного на векторах —и

ds

d2 Г

Ids2

где параметр s находится из условия:

s (t) = J

dГ d2 Г — х-

dr [3]. Вообще говоря, динамические кривые содержат информацию,

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

Г : {x(s),y(s), s e [0,SГ]}, где параметр s находится из условия: s(t) = J

dr\

dr.

Отметим, что скорость написания рукописных кривых (т.е. иными словами «динамика» движения руки) тесно связана с формой траектории. Действительно, при выполнении закруглений скорость пера ниже, чем при выполнении прямолинейных движений. Также темп выполнения элементов подписи варьируется от одного исполнения к другому, что иногда сильно осложняет проверку подлинности. Исходя из подобных соображений В. Налва в своей работе [4], одним из немногих отказался от параметризации по времени, и принципиально рассматривает только форму траектории, что приводит к отказу от рассмотрения таких характеристик как, например, нажим на перо или наклон пишущей ручки. Поэтому в силу специфичности постановки задачи и приведенных доводов мы отказались от временной параметризации, тем более что, как показано в работе [2], она не имеет явных преимуществ перед другими видами параметризации, а иногда и проигрывает им.

Сопоставление траекторий на основе экстремальных точек

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

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

разработанные методы из области распознавания речи к распознаванию рукописного текста [5,6]. Тем не менее, прямое применение этих методов к распознаванию слитного текста сопряжено с определенными трудностями, связанными с

Рис. 1.

Пример сопоставления двух рукописных цифр методом dynamic time warping [13].

подвергаются все точки траектории.

«пик»

«зубчики»

нахождением диакритических знаков [7]. В тоже время слова в письменной речи часто удается достаточно легко отделять одно от другого, в отличие от звуков в слитной речи.

Основными методами распознавания рукописной подписи являются: статистический подход, основанный на аппарате скрытых марковских моделей, подход с использованием нейронных сетей, а также сопоставление динамических кривых методом динамической трансформации временной шкалы (dynamic time warping). В зависимости от принципов сопоставления элементов траекторий в литературе встречаются различные вариации последнего метода:

•Symmetric Dynamic Time Warping [8],

•Continuous Dynamic Time Warping [9],

•Piecewise Aggregate Approximation Dynamic Time Warping [10],

•Iterative Deepening Dynamic Time Warping [11], и т. д.

В большинстве работ сопоставлению Например, в работе Ф. Грисса с коллегами [12] был применен метод сравнения траекторий, апробированный ранее в работах С. Коннелла при распознавании рукописных символов [13] (см. рис.1). Тем не менее, как было отмечено в работе [14], метод DTW обладает двумя основными недостатками: высокой вычислительной стоимостью и приведением поддельной подписи в соответствие с эталоном. Для устранения указанных недостатков в работе [14] был предложен метод сравнения подписей на основе поиска соответствия экстремальных точек (extreme points warping, EPW). Исходный сигнал авторы цитируемой работы представляют как череду «пиков» и «впадин» (см. рис. 2). Поскольку при таком подходе соответствие необходимо находить только между точками соответствующего типа, то процесс сравнения существенно ускоряется. На основе образцов подписей 25 пользователей Ф.Хао и К.Чан сделали эмпирическое обобщение, что ошибки сопоставления бывают трех типов: из-за пропуска сегмента в начале или в конце одной из подписей, а также из-за «зубчиков» - случайной пары «пик-впадина» с небольшим перепадом по высоте. Для исключения из рассмотрения подобных точек вводится эвристическое правило: точка помечается как экстремальная,есливыполнены

одновременно два условия:

r > h0, d > h0

где r - перепад высот между последовательными «впадиной» и «пиком», d - перепад высот между «пиком» и последующей «впадиной», h0 - пороговое значение (равное одному пикселю). Полученные экстремальные точки сопоставлялись методом динамического программирования [13,14]. На рис.3. показана схема прямого хода, когда путь из точки (ij) может быть продолжен в ту из трех точек (i+1j+1), (i+1j+3), (i+3j+1) которая дает минимальный штраф за несоответствие. Прямой проход позволяет найти

Рис. 2.

«впадины»

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

1 3 3 4 5 6 1 8 9 10 ]] 12 :3

Рис.3. Реализация EPW [6].