Проверка устойчивости угловых коэффициентов, образованных линейными элементами подписи (предположение Локара)

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

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

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

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

Предположение Локара

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

Рис. 1. Главные линейные элементы подписи

Для проверки этого предположения нами рассматривалось десять серий изображений подписей по 50 подписей в каждой серии [2]. Изображения в пределах одной серии принадлежат одному и тому же человеку. Изображения подвергались предварительной обработке – выделялась прямоугольная область, содержащая один экземпляр подписи. Затем изображение в этой области преобразовывалось в монохромное (двухцветное). Далее к изображению применялся алгоритм выделения линейных элементов.

Алгоритм выделения линейных элементов

Алгоритм работает следующим образом. Последовательно проходятся все точки изображения. Если находится пиксель черного цвета (принадлежащий изображению подписи), то рассматривается область изображения вокруг этого пикселя диаметром δ . Если количество пикселей в этой области превышает некую пороговую величину (рассматриваемый пиксель принадлежит изображению подписи, т. е. не является шумом), то текущий пиксель считается предполагаемым началом линейного элемента (рис. 2а, точка N). Затем уточняется начало предполагаемого линейного элемента (точка X)

• а)                             б)

Рис. 2. Выделение линейного элемента подписи

После того, как будет найдено начало линейного элемента, алгоритм пытается провести вдоль изображения подписи линейный элемент в направлении α . Для этого с шагом d /2 ( d – ширина линии подписи в пикселях, она предполагается известной). Алгоритм продвигается по изображению и подсчитывает число черных и белых пикселей в квадрате со стороной d (рис. 2 б ). Пока отношение числа черных пикселей к числу белых больше определенного значения (т. е. этот квадрат принадлежит изображению подписи), алгоритм продвигается дальше вдоль направления α с шагом d /2 . Если же отношение количества черных и белых пикселей в квадрате меньше граничного значения, то алгоритм считает, что линейный элемент найден, полученных элемент запоминается. Затем определенным образом выбирается новое направление α , и процесс повторяется (число различных α для поиска линейного элемента из одной точки является параметром алгоритма, влияет на точность получаемого результата). После того, как найден элемент максимальной длины, который можно провести из этой точки, он запоминается и стирается из исходного изображения (т. е. заполняется белыми пикселями). Стирание производится с целью увеличения быстродействия алгоритма.

«Склейка» линейных элементов

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

Алгоритм «склейки» линейных элементов перебирает элементы, содержащиеся в структуре данных S , находит среди них близкую в определенном смысле пару элементов и «склеивает» их: удаляет оба элемента из структуры данных S и добавляет новый элемент, сформированный на основе ранее найденной пары. Операции со структурой данных S производятся таким образом, что содержимое этой структуры всегда упорядочено по длине линейных элементов. Элементы считаются «близкими», если начало одного элемента близко к концу другого или наоборот, и углы, образованные линейными элементами с осью абсцисс, также близки. Степень близости углов и точек определяется параметрами алгоритма.

Результаты применения алгоритмов к сериям подписей

Рассмотрим серии подписей по 50 в каждой. Каждое изображение имело размер порядка 600 × 600 пикселей. Параметры алгоритмов различны в каждой серии. Полученные углы и длины элементов рассматривались как случайные величины.

Предполагалось, что последовательности имеют нормальное распределение, для каждой последовательности вычислялось математическое ожидание и дисперсия. Далее к результатам применялся критерий Колмогорова-Смирнова: K ⁺ , K ^- – результаты критерия. Если K < 5%, то последовательность считается слишком близкой к предполагаемому распределению и не является случайной. K >95% означает, что последовательность сильно отклоняется от предполагаемого распределения.

а)

б)

Рис. 3. «Склейка» линейных элементов

Следует отметить, что признак Локара проявляется не в каждой подписи. В подписях, у которых нет достаточно длинных прямолинейных элементов, такая закономерность не наблюдается.

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

Для выделения отрезков прямых может использоваться и преобразование Радона [1]. Оказалось, что по сравнению с предложенным алгоритмом

Таблица 1. Характеристики полученных последовательностей случайных величин

Сл. вел. Мат. ожидание Дисперсия К+ % К-% ξ12 67,68 9,06 47 41 ξ23 56,91 13,73 56 94 ξ34 33,48 22,72 87 84 η12 53,67 5,92 36 71 η23 37,15 11,51 47 70 η34 21,67 11,68 62 28 ψa 59,63 6,59 56 90 ψb 57,76 6,65 46 60 преобразование Радона более трудоемко, т. к. в ходе преобразования вычисляются интегралы вдоль всех возможных прямых, проходящих через изображение (с определенным шагом дискретизации). Кроме того, результат этого преобразования обладает избыточной информацией, которая не используется при проверке гипотезы Локара. Если же в подписи имеются два линейных элемента, лежащих примерно на одной линии, то для преобразования Радона они будут являться одной прямой. Предложенный алгоритм позволяет различать такие линейные элементы.

На рис. 4 а приведено исходное изображение, а на рис. 4 б – результат преобразования Радона. Цифрами на рисунках отмечены прямые и соответствующие им точки в области результата преобразования Радона. На рис. 4 б видно, что с помощью преобразования Радона сложно различить отмеченные на рис. 4 а прямые.

а)                            б)

Рис. 4. Преобразование Радона

Заключение.Возможные применения алгоритма

Углы, образованные одними и теми же линейными элементами в серии подписей в случае, если подпись содержит достаточно длинные линейные элементы, распределены нормально и имеют сравнительно небольшую дисперсию.

Алгоритмы G и L формируют линейный образ подписи, который может быть использован для проверки других признаков.

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

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