Быстрое сопоставление рукописных динамических подписей в биометрической системе контроля доступа

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

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

Введение

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

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

Скелетное представление рукописной кривой

В основе описываемого метода анализа динамических кривых лежит идея выделения характерных или экстремальных точек [1]. При этом ключевое значение имеют так называемые «вертикальные» экстремумы, характеризующие изменение направления

движения пера в вертикальной плоскости. На рис. 1 приводится пример «скелетного» представления рукописной подписи, полученный путем соединения экстремальных точек кривой. Здесь и далее в качествепримеровбудут

использоваться образцы подписей из общедоступной базы данных первого международного конкурса программ по верификации рукописной подписи: SVC 2004: First International Signature Verification Competition, который проводился в 2004 году [2]. В рамках конкурса проводились два Рис. 1. Образец построения скелетногонезависимых соревнования: проверка

представления подписи (Task2\User5).подписей только на основе временной

последовательности точек, и проверка подписи с учетом данных о нажиме на перо и угле наклона ручки. Условно будем называть первую часть базы данных «Task1», а вторую часть - «Task2», при этом для полной ссылки будем указывать тип подписи и номер образца (номера от 1 до 20 соответствуют оригинальным экземплярам подписи, а номера от 21 до 40 соответствуют поддельным подписям).

Замена исходной кривой ломаной линией достаточно точно описывающей поведение траектории позволяет формализовать процедуру сопоставления двух кривых.

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

Вариативность почерка

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

Определение 1. Вариативным изменением 1-го рода некоторой рукописной кривой будем называть такую вариацию траектории, при которой происходит локальное изменение ее формы. ■

Определение 2. Вариативным изменением 2-го рода некоторой рукописной кривой будем называть такую вариацию траектории, при которой происходит добавление и удаление ее элементов. ■

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

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

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

Лемма 1. Для случая ломаной состоящей из четырех вертикальных экстремумов возможны только два структурно различных варианта ее поведения. Доказательство.

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

Замечание 1: На рис.2 представлены возможные трансформации ломанной, ведущие к исчезновению промежуточных вертикальныхэкстремумов.

Условимся называть первый тип трансформации бифуркационной вариацией, а второй тип непрерывной вариацией. Замечание 2: На практике подписи выполняются не

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

На рис.3 приведены примеры трансформаций 1-го рода, когда экстремальные точки или исчезают как в случае буквы «В» или в результате трансформации перестают быть

Рис.2. Два принципиально разных случая трансформации ломаной состоящей из четырех точек.

Рис.3. Примеры вариативных трансформаций 1-го рода.

вертикальными экстремумами. Вариативные изменения 2-го рода встречаются гораздо реже, что в прочем, вполне естественно. На рис.4 приводится пример, когда в верхней кривой присутствует «лишний» элемент. Заметим, что в случае вариативных изменений второго рода необходимо вводить в рассмотрение сопоставления вида один-к-двум, что видно из рис.4, в то время как известные в литературе методы эластичного сопоставления (dynamic time warping) позволяют находить только поточечные соответствия вида один-к-одному [3,4,5].

Сопоставление траекторий

Введенные в рассмотрение в предыдущем разделе вариативные изменения траекторий могут быть учтены алгоритмами Рис.4. Вариативное изменение 2-го рода. «string matching», применяемыми для

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

Таким образом, на вход алгоритма сопоставления двух динамических кривых поступает упорядоченный набор хорд, являющийся допустимым набором пар вертикальных экстремумов (связи вида «min-min» или «max-max»). При этом задачей алгоритма является нахождение оптимального соответствия между экстремальными точками, представляющими концы хорд.

В качестве метода решения поставленной задачи было применено динамическое программирование. Первым этапом предлагаемого алгоритма является заполнение таблицы штрафов, в которой на пересечении строк и столбцов находятся величины, характеризующие степень отличия соответствующих элементов рукописных кривых. При этом применялись две метрики: «манхэттенская» (в англоязычной литературе известная так же как «city block») и «по Журавлеву». Первая метрика учитывала положение пары хорд относительно друг друга и относительно места в кривой (1),(2), а также относительные размеры хорд (3),(4):

Сопоставление по указанной мере производилось из соображений, чтобы различие по одной из координат не приводило к неверному решению, что, вообще говоря, не исключено при сравнении по евклидовой мере. Формулы (1)-(4) не учитывают поведение кривой на участке, заключенном между парой вертикальных экстремумов. Поэтому