автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Информационные технологии анализа и синтеза деформаций дактилоскопических изображений

004603158

На правах рукописи

Арутюнян Артем Рафаэлевич

Информационные технологии анализа и синтеза деформаций дактилоскопических изображений

Специальность 05.13.17 - Теоретические основы информатики

Автореферат

диссертации на соискание ученой степени кандидата технических наук

1 6 СЕН ?0Ю

Москва 2010

004608158

Диссертация выполнена в Учреждении Российской академии наук Институт проблем информатики РАН.

Научный руководитель

- доктор технических наук Ушмаев Олег Станиславович Официальные оппоненты:

- доктор физико-математических наук Крылов Андрей Серджевич

- кандидат технических наук Мурашов Дмитрий Михайлович

Ведущая организация - ФГУП «ГосНИИАС»

Защита состоится «29» сентября 2010 г. в 15°° часов на заседании диссертационного совета Д002.073.01 при Учреждении Российской академии наук Институт проблем информатики РАН по адресу: 119333, Москва, ул. Вавилова, д.44, к. 2.

С диссертацией можно ознакомиться в библиотеке Института проблем информатики

Отзывы в одном экземпляре, с заверенной подписью, просим направлять по адресу: 119333, Москва, ул. Вавилова, 44, к.2, в диссертационный совет.

Автореферат разослан «26» августа 2010 г.

Ученый секретарь диссертационного Совета, доктор технических наук,

РАН.

профессор

С.Н. Гринченко

Общая характеристика работы

Актуальность работы.

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

Наиболее распространенным методом биометрической идентификации является идентификация по отпечаткам пальцев. Несмотря на многочисленные исследования в области дактилоскопии, проводимыми такими учеными как В.Ю. Гудков, С.О. Новиков, О.В. Черномордик, A. Bazen, R. Cappelli, S. Dass, M. Elección, A. Erol, S. Gerez, U. Halici, A.K. Jain, M. Kucken, D. Maio, D. Maltoni, D. Monro, S. Pankanti, S. Prabhakar, N. Ratha, A.Ross, B. Sherlock, M. Trauring, P. Vizcaya, J. Wegstein и др., точность дактилоскопической идентификации не достигла своего потенциала. Основной причиной является сложность моделирования, учета и компенсации многочисленных искажающих факторов, среди которых следует выделить шумы, малые области пересечения предъявляемых к сравнению отпечатков пальцев, эластичные деформации. Деформации являются одним из самых сильных и наименее изученных факторов. В этой связи тематика, связанная с исследованием деформаций отпечатков пальцев является актуальной.

Наиболее важными применениями моделей деформаций отпечатков пальцев являются: (1) синтез искусственных приложений пальца для имитации технологических испытаний в системах гражданской идентификации; (2) априорное устранение деформации за счет вычисления «недеформированного» состояния отпечатка пальца по множеству приложений на этапе регистрации.

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

Для достижения поставленной цели необходимо решение следующих задач:

1. Разработка математической модели процесса деформации отпечатка пальца.

2. Разработка методов анализа деформаций дактилоскопических изображений.

3. Статистический анализ характера и структуры деформаций.

4. Разработка методов синтеза деформаций дактилоскопических изображений.

5. Разработка алгоритма моделирования деформации отпечатка пальца.

6. Разработка алгоритма априорного учета деформации отпечатка пальца.

Методы исследования. В работе использованы современные методы обработки изображений и распознавания образов, теории вероятностей и математической статистики, теории упругости, методы программирования и моделирования на ЭВМ. На защиту выносятся следующие результаты:

1. Модель деформаций изображений отпечатков пальцев.

2. Метод вычисления деформаций изображений отпечатков пальцев.

3. Система количественных признаков структуры деформаций.

4. Методы анализа и синтеза деформаций на основе разложения по базисным деформациям.

5. Информационная технология синтеза искусственных деформаций.

6. Информационная технология априорного учета деформаций отпечатков пальцев.

Научная новизна работы состоит в разработке информационных технологий анализа и синтеза деформаций дактилоскопических изображений.

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

Реализация результатов работы. Результаты диссертации реализованы в Программе фундаментальных исследований ОНИТ РАН (проект 1.5), Проектах РФФИ (№07-07-00031), в работах НОЦ ИПИ РАН - ВМК МГУ «Биометрическая информатика», в продуктах компании «Биолинк Солюшенс».

Апробация работы. Материалы диссертации излагались и обсуждались в тематическом «биометрическом» выпуске журнала «Информатика и ее применения» (2010, вып.1), и на следующих научно-технических конференциях: Графикон-2009 (Москва, 2009 г.), «Распознавание-2010» (Курск, 2010 г.), «Кибернетика и высокие технологии XXI века» (Воронеж, 2010 г.), Школа молодых ученых ИБРАЭ РАН (г. Москва).

Публикации. Материалы диссертации содержатся в отчетах ИПИ РАН, использованы в работах по грантам РФФИ 07-07-00031, 10-07-00433, отчетах по проектам ОНИТ РАН, в тематических выпусках журнала «Информатика и ее применения» (№1, 2010). В открытой печати по теме диссертации опубликовано 6 работ, из них в изданиях, входящих в Перечень ВАК, 2 работы.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и приложения.

Краткое содержание работы

Во введении обоснована актуальность проблемы, дана краткая характеристика тематических публикаций.

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

Рисунок 2. Процесс деформации отпечатков пальцев (screencast).

Во второй главе рассматривается математическая модель процесса деформации отпечатка пальца.

Деформация изображения отпечатка пальца определяется картой смещений, которую можно интерпретировать, как отображение одного изображения на другое изображение:

/:Im1->Im2, (1)

где 1гП|, Im2 - изображения отпечатков пальцев.

Далее в работе используется представление отображения (1) в виде карты смещений и. Действие отображения /и, ассоциированного с смещениями и, можно представить следующим выражением:

1т1(х,>')=/71Г10т2(х,у)) =

1 . I , ч . / Л • (2)

detJu(x,y)

■*Ах>у)=

im2{x + их {х, у), у+ и у (х, у)} диг

1

1 + —-

дх

диу дх

1+-

ду ди,

ду)

В динамике (рис. 2) можно считать, что и зависит от времени. Предположим, что отпечаток пальца является упругим объектом. Тогда его динамика описывается следующей системой уравнений теории упругости:

8<тп, 8а„ , д2и - + —J2L + fs =р.

8v

дх

дих дх

да„ d2uv

дг дх dyJ> Эг

диу

V'

Sxy - £ух ~ 2

du. ди —- + —-

ду дх

(3)

(4)

где их и и - компоненты карты смещений по оси х и у соответственно, Г = {/х,/у) действующие внешние силы, е - тензор натяжений, а - тензор давлений, р - плотность. Компоненты тензоров £ и с связаны линейным соотношением (закон Гука):

(5)

Решения уравнений определяется значениями матрицы упругости С(х,^'). Матрица является непостоянной, т.к. поверхность пальца является неоднородной по механическим свойствам. Неоднородность связана с различным механизмом деформаций под действием сил вдоль и поперек направления папиллярного узора (рис. 3).

В координатах, ассоциированных с локальным направлением папиллярного узора

матрица С имеет четыре степени свободы и равна1:

/ \ axx / \ sxx

= cM £>y

У

сМ=

ЕГ 0

vWzE? 0

0 0 G

-1.

-1.

(6)

1 Thtirston, R.N. Waves in Solids// Mechanics of Solids IV (Festkoerpermechanik IV). Berlin, Springer-Verlag

(Handbuch der Physik. Volume VIa/4), 1974, p. 109-308.

где Е-, Ew - модули Юнга вдоль и поперек поля направлений, v-^. и vw: - коэффициенты Пуассона, G - модуль сдвига.

При переходе к исходным глобальным координатам (6) элементы матрицы упругости вычисляются по следующим формулам:

с,, = cos4 аси + 2 eos2 «sin2 аси +sin4 ас22 + cos2 a sin2 ас]У ср = eos2 asín2 аси + (cos4 a + sin" + cos2 asín2 ac- eos2 asín2 ac„ c,y = eos' a sin acn + cosasina(cos2 ar-sin2 a)?l2 -

- cos a sin'1 ac22 -cos'a sin »с,,

c22 = sin4 acn +2cos2 asin2 act2 + cos4 ac22 + cos2 a sin2 ac¡, c23 = sin1 a cos aclt + cosasina(cos2 a - sin" a):,, -

- cos3 a sin ac,2 + cos1 a sin acu

c„ - cosasin3 ac¡¡ -2cos2 asin2 acl2 -cos3 asmac22 + cos4 are,,

(7)

Рисунок 3. Направление потока папиллярных линий

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

+ + 0;

ду дх

дсг„, да ——+ —^ + /„=0; дх ду

Система уравнений (8) и (4) определяет деформацию отпечатка. Отмечены следующие трудности ее непосредственного решения. Во-первых, не существует начального состояния отпечатка, с которого начинается деформация. Деформация является следствием процесса двумерного сканирования трехмерного объекта (рис. 1). Во-вторых, действующие силы неизвестны. Не существует инженерно реализуемого способа их измерения.

Из теории упругости известно, что решение уравнений (4) и (8) можно искать как минимум следующей функции энергии

£ = ~П(ихЛ +и,1у^у + \\\{еххахх+8пауу+£ху<7х)^у. (9)

х

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

Рисунок 4. Соответствие контрольных точек отпечатков пальцев

Наборы соответствующих друг другу пар точек обозначены через {р^}-", и {я,}-", соответственно. В качестве меры близости двух наборов контрольных точек используется среднеквадратическая невязка

¿2(и) = —1||р/ + "(р,)-4;||2- (10)

пг ы

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

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

ад—ХКр^и^-п^2, (11)

ты

где п - функционал взятия нормали к локальному потоку папиллярных линий.

С учетом (10) и (И) предложено искать приближенное решение (9) как минимум следующего функционала, состоящего из внутренней энергии деформации и регуляризирующих поправок на невязку:

/)(и) = ^(и)+а112(и)+«2^(и), (12)

где <2], ао - весовые коэффициенты, внутренняя энергия деформации вычисляется по формуле.

Еа =\\\(£*х<г&+еп.(Туг+е„о,я}Ыу. (13)

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

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

1тет=^(1т2 + /,,(1п11)). (14)

Примеры наложения с учетом оптимальной по (12) деформации в сравнении с оптимальным движением приведены на рис. 5. Контрастная часть результатов наложения указывает на резонанс папиллярных линий. Серая часть соответствует неточному наведению. Из рисунка видно, что предложенная модель позволяет с высокой точностью преобразовывать изображения отпечатков пальцев друг в друга. При этом отсутствуют краевые эффекты, характерные для эмпирических моделей деформаций на основе тонкой металлической пластины2 или модели СарреШ е1 а13. Также к достоинствам модели относится возможность вычисления относительной деформации для произвольных

2 Bazen A.M., Gerez S.H., Thin-Plate Spline Modelling of Elastic Deformation in Fingerprints // Proceedings of 3rd IEEE Benelux Signal Processing Symposium, 2002

3 Cappelli R., Maio D„ Maltoni D. Modelling Plastic Distortion in Fingerprint Images // ICAPR2001, p. 369-376

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

УЙ// Яр ШшШч 'ш ■тШш ш 1 Шт

яШ й® Щ |рЯ|

ШИШ Шт ¡р 9 ШШ тшж 'Ш/к ш

(а) (б) (в) (г)

Рисунок 5. Пример вычисления деформации (а), (б) - два изображения отпечатка, (в) -прямое наложение при подгонке жестким движением, (г) - прямое наложение после

подгонки деформации

Проведенный статистический анализ также подтверждает, что предложенная эластичная модель значительно улучшает точность наведения изображений по сравнению с известными моделями. В качестве объективного критерия точности моделирования процесса деформации отпечатков пальцев используется коэффициент прямого наложения (корреляции) для бинаризированных дактилоскопических изображений. БЕТ кривые коэффициента прямого наложения для базы РУС20020В1 (умеренные деформации) и

FVC2004DB1 (значительные деформации) представлены на рис. 6 b 7. Как видно из рисунка, предложенная эластичная модель значительно улучшает наложение изображений в сравнении с жестким движением и моделированием деформаций методом TPS.

— оптимальное движение -о- учет деформаций (эластичная модель)

-о- учет деформаций (модель TPS)

Рисунок 6. DET коэффициента прямого наложения (FVC2002DB1)

-оптимальное движение -о- учет деформаций (эластичная модель)

—о- учет деформаций (модель TPS)

Рисунок 7. DET коэффициента прямого наложения (FVC2004DB1)

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

и = Хс,Ь,+г, (15)

/=1

где Ь, - базисные деформации, с, - коэффициенты разложения по базису, г - остаток.

Базисные деформации могут вычисляться как из качественных соображений, так и путем формального статистического анализа. На основе разложения (15) разработана приближенная линейная модель. Коэффициенты С, вычисляются путем минимизации невязки (10)-(11).

В качестве базисных деформаций предложено использовать «главные» деформации, полученные методом главных компонент на эталонном массиве отпечатков пальцев. Для вычисления главных компонент использовались три базы данных РУС2002, содержащие изображения с оптических и емкостных сканеров отпечатков пальцев. Каждая база содержит 8 образцов для 100 человек, т.е. для анализа деформаций всего доступно три набора по 2800 естественных деформаций отпечатков пальцев.

На рис. 8 представлены первые четыре базисные деформации, полученные методом главных компонент. Они допускают физическую интерпретацию (два типа вращения и два сдвига, рис. 9). Такие деформации отвечают субъективному представлению об основных способах приложения пальца к сканеру. Помимо качественного анализа деформаций рассмотрен ряд формальных критериев точности приближения деформаций, который показал достаточно высокую точность линейной модели деформаций.

Рисунок 8. Карта смещений главных деформаций, полученных на различных массивах отпечатков пальцев (а,б - деформационные вращения, в, г - деформационные сдвиги)

(а)

(б)

(в)

(г)

Рисунок 9. Схематичное представления основных деформаций, «Н» - относительно неподвижная область, стрелкой указаны основные направления смещений (а,б -деформационные вращения, в, г - деформационные сдвиги)

Рисунок 10. Распределения проекций на базисные деформации для различных тестовых массивов (естественные отпечатки пальцев: а - 1ГУС20020В 1,6- РУС20040В1, искусственно сгенерированные отпечатки пальцев: РУС20020В4, г - РУС20040В4)

Первые 8-10 главных компонент обеспечивают достаточно точное приближение наблюдаемых деформаций для любого из перечисленных критериев точности. При этом полученные главные компоненты практически не зависят от выбранного для анализа массива отпечатков пальцев. Различия в характере деформаций заключаются в различных наблюдаемых распределениях коэффициентов с1 разложения (16). Эмпирически

наблюдаемые распределения представлены на рис. 10. Из полученных данных, в частности, были сделаны следующие выводы:

1. Статистические свойства естественных деформаций практически не зависит от типа модели сканера (случаи а и б).

2. Синтетические деформации, получаемые известными ранее методами, отличаются по своим характеристикам (в).

Также установлено количественное отличие деформаций при прокатке отпечатка и деформаций при электронном сканировании (livescan).

В четвертой главе рассмотрено применение разработанных методов анализа и синтеза деформаций к реальным задачам дактилоскопической идентификации: синтез искусственных деформаций отпечатков пальцев и синтез «недеформированного» отпечатка пальца для увеличения точности дактилоскопической идентификации.

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

Создание «недеформированного» усредненного изображения по нескольким отпечаткам пальцев является частным случаем синтеза искусственной деформации. Пусть есть к+1 изображений: Im0, Im,, ..., Imt. Относительные деформации Im, в Im0

обозначены далее через и;. Рассмотрены два подхода к синтезу средней деформации.

Первый заключается в формальном вычислении средней карты смещений и,,,,:

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

Получаемое таким образом «недеформированное» изображение применяется для увеличения точности идентификации. При регистрации на основе нескольких предъявлений отпечатка пальца вычисляется среднее состояние (рис.12).

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

(16)

>>

Среднее изображение определяется, как Imav = um.(lm0). Второй подход

Среднее по такому условию изображение определяется как Immin =um¡n(lm0).

ш ¡р

ж§ и 9/ШШ\ фтт

¡¡Ц ЙЗвЩ У// V ФШ ; \ „ \ Фш шит ■ШЬш

и ш

Рисунок 11. Примеры моделирования искусственных деформаций (крайнее слева - исходное состояние, слева направо - деформированное с возрастающим усилием)

Рисунок 12. Усредненное по деформациям изображение отпечатка 1т

-исходное изображение -о- недеформированное изображение

Рисунок 13. Изменение ошибок идентификации при использовании «недеформированного» изображения (база БУС20020В1)

На рис. 13 приведены DET-кривые ошибок идентификации алгоритма Biolink MST при использовании исходных и усредненных изображений. Как видно из графика, наблюдается значительное улучшение точности идентификации. Заключение содержит основные выводы из диссертации.

Основные результаты диссертации

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

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

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

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

5. Разработана информационная технология синтеза искусственных деформаций с статистическими свойствами наблюдаемых естественных деформаций.

6. Разработана информационная технология синтеза «недеформированного» шаблона отпечатка пальца для внедрения в системы дактилоскопической идентификации и верификации личности.

Основные публикации по теме диссертации

1. Ушмаев О.С., Лрутюнян А.Р. Влияние деформаций на качество биометрической идентификации по отпечаткам пальцев// Информатика и ее применения, 2009. Т.З. Вып. 4. С. 12-21 [Перечень ВАК]

2. Ушмаев О.С., Лрутюнян А.Р. Метод оценки качества биометрической идентификации в операционных условиях на примере дактилоскопической идентификации // ГрафиКон'2009: 19-я Международная конференция по компьютерной графике и зрению: Москва, МГУ им. М.В. Ломоносова, 5-9 октября 2009 г.: Труды конференции. - М.: МАКС ПРЕСС, 2009, с.232-235.

3. Лрутюнян А.Р., Уишаев О.С. Деформации изображений отпечатков пальцев // Труды XI международной научно-технической конференции. «Кибернетика и высокие технологии XXI века», Воронеж, 12-14 мая 2010, т.2, С.621-626.

4. Лрутюнян А.Р., Моделирование влияния деформаций отпечатков пальцев на точность дактилоскопической идентификации // Информатика и ее применения, 2010. Т.4. Вып.1. С.39-45. [Перечень ВАК]

5. Лрутюнян А.Р., Синицын КН., Уишаев О.С. Статистический анализ естественных деформаций изображений отпечатков пальцев // Труды IX международной научно-технической конференции. «Оптико-электронные приборы и устройства» (Распознавание-2010), Курск, 18-20 мая 2010. -Курск: 2010, С.181-183.

6. Лрутюнян А.Р. Моделирование деформаций отпечатков пальцев // Сборник трудов IX научной школы молодых ученых ИБРАЭ РАН, Москва, 2010, с. 15-18

Заказ № 78-а/08/10 Подписано в печать 24.08.2010 Тираж 100 экз. Усл. п.л. 1

ООО "Цифровичок", тел. (495) 649-83-30 www.cfr.ru; е-таИ:info@cfr.ru

Введение.

Глава 1. Анализ проблематики.

1.1 Автоматическая дактилоскопическая идентификация.

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

1.1.2 Критерии точности дактилоскопической идентификации.

1.1.3 Искажающие факторы.

1.1.4 Деформации отпечатков пальцев.

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

1.2.1 Модель тонкой металлической пластины и её варианты.

1.2.2 Глобальная модель деформаций.

1.2.3 Упругие модели.

1.3 План исследования.

Выводы из первой главы.

Глава 2. Математическая модель процесса деформаций отпечатков пальцев

2.1 Уравнения деформаций.

2.2 Решение уравнений деформации изображений отпечатков пальцев.

2.2.1 Метод решения уравнений деформации.

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

2.2.3 Вычислительная схема алгоритма решения уравнений деформации

2.2.4 Примеры решения уравнений деформации.

2.3 Критерии точности моделирования деформаций.

2.3.1 Статистические критерии идентичности отпечатков пальцев.

2.3.2 Проблема выбора нормализующих поправок.

2.3.3 Точность вычисления деформаций.

Выводы из второй главы.

Глава 3. Синтез деформаций отпечатков пальцев.

3.1 Главные компоненты деформаций.

3.2 Линейная модель деформаций.

3.3 Точность линейной модели деформаций.

3.3.1 Разница линейной и эластичной модели деформаций.

3.3.2 Точность приближения линейной модели деформаций.

3.4 Статистические свойства деформаций на различных массивах отпечатков пальцев.

Выводы из третьей главы.

Глава 4. Учет деформаций в задачах дактилоскопической идентификации.

4.1 Программное обеспечение анализа деформаций отпечатков пальцев.

4.2 Технология синтеза искусственных приложений отпечатка пальца.

4.2.1. Модель эксплуатационных условий.

4.2.2. Оценка силы естественных деформаций.

4.2.3. Эксперименты с синтезом искусственных деформаций.

4.3 Синтез «недеформированного» отпечатка пальцев.

4.3.1. Методы априорного вычисления деформации.

4.3.2. Эксперименты.

Выводы из четвертой главы.

Актуальность работы. В настоящее время биометрические (использующие физические и поведенческие характеристики человека) технологии идентификации личности и системы на их основе получили широкое распространение в различных областях: от допуска в помещения до электронной коммерции и государственных систем различного назначения.

Наиболее распространенным методом биометрической идентификации является идентификация по отпечаткам пальцев. Несмотря на многочисленные исследования в области дактилоскопии, проводимыми такими учеными как В.Ю. Гудков, С.О. Новиков, О.В. Черномордик, А. Bazen, R. Cappelli, S. Dass, M. Eleccion, A. Erol, S. Gerez, U. Halici, A.K. Jain, M. Kucken, D. Maio, D. Maltoni, D. Monro, S. Pankanti, S. Prabhakar, N. Ratha, A.Ross, B. Sherlock, C. Soutar, M. Trauring, P. Vizcaya, J. Wegstein и др., точность дактилоскопической идентификации не достигла своего потенциала. Основной причиной является сложность моделирования, учета и компенсации многочисленных искажающих факторов, среди которых следует выделить шумы, малые области пересечения предъявляемых к сравнению отпечатков пальцев, эластичные деформации. Деформации являются одним из самых сильных и наименее изученных факторов. В этой связи тематика, связанная с исследованием деформаций отпечатков пальцев является актуальной.

Наиболее важными применениями моделей деформаций отпечатков пальцев являются: (1) синтез искусственных приложений пальца для имитации технологических испытаний в системах гражданской идентификации; (2) априорное устранение деформации за счет вычисления «недеформированного» состояния отпечатка пальца по множеству приложений на этапе регистрации.

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

Для достижения поставленной цели необходимо решение следующих задач:

1. Разработка математической модели процесса деформации отпечатка пальца.

2. Разработка методов анализа деформаций дактилоскопических изображений.

3. Статистический анализ характера и структуры деформаций.

4. Разработка методов синтеза деформаций дактилоскопических изображений.

5. Разработка алгоритма моделирования деформации отпечатка пальца.

6. Разработка алгоритма априорного учета деформации отпечатка пальца. Методы исследования. В работе использованы современные методы обработки изображений и распознавания образов, теории вероятностей и математической статистики, теории упругости, методы программирования и моделирования на ЭВМ.

На защиту выносятся следующие результаты:

1. Модель деформаций изображений отпечатков пальцев.

2. Метод вычисления деформаций изображений отпечатков пальцев.

3. Система количественных признаков структуры деформаций.

4. Методы анализа и синтеза деформаций на основе разложения по базисным деформациям.

5. Информационная технология синтеза искусственных деформаций.

6. Информационная технология априорного учета деформаций отпечатков пальцев.

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

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

Реализация результатов работы. Результаты диссертации реализованы в Программе фундаментальных исследований ОНИТ РАН (проект 1.5), Проектах РФФИ (№07-07-00031), в работах НОЦ ИЛИ РАН -ВМК МГУ «Биометрическая информатика», в продуктах компании «Биолинк Солюшенс».

Апробация работы. Материалы диссертации излагались в тематическом «биометрическом» выпуске журнала «Информатика и ее применения» (2010, вып.1), и на следующих научно-технических конференциях: Графикон-2009 (Москва, 2009 г.), «Распознавание-2010» (Курск, 2010 г.), «Кибернетика и высокие технологии XXI века» (Воронеж, 2010 г.), Школа молодых ученых ИБРАЭ РАН (г. Москва).

Публикации. Материалы диссертации содержатся в отчетах ИЛИ РАН, использованы в работах по грантам РФФИ 07-07-00031, отчетах по проектам ОНИТ РАН, в тематических выпусках журнала «Информатика и ее применения» (№1, 2010). В открытой печати по теме диссертации опубликовано 6 работ, из них в изданиях, входящих в Перечень ВАК, 2 работы.

Выводы из четвертой главы

Разработано программное обеспечение анализа деформаций отпечатков пальцев, реализующее основные методы и алгоритмы глав 3 и глав 3. Разработана информационная технология синтеза искусственных деформаций отпечатков пальцев. На основе этой технологии разработана методика оценки чувствительности алгоритма распознавания отпечатков пальцев к силе деформаций. Разработана информационная технология синтеза «недеформированного отпечатка» пальцев, которая позволяет повысить точность идентификации за счет априорного подавления деформации на этапе создания шаблона. По точности идентификации априорное усреднение изображение относительно упругих деформаций практически эквивалентно апостериорному учету деформаций. Для технологии Biolink MST наблюдается практически двухкратное уменьшение ошибки первого рода.

Заключение

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

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

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

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

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

5. Разработана технология синтеза искусственных деформаций со статистическими свойствами естественных деформаций.

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

1. Арутюнян А.Р. Моделирование деформаций отпечатков пальцев, Труды школы молодых ученых ИБРАЭ РАН, с. 15-18.

2. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. М.: Наука.-2003.-632 с.

3. ГОСТ Р ИСО/МЭК 19794-2-2005 «Автоматическая идентификация. Идентификация биометрическая. Форматы обмена биометрическими данными. Часть 2. Данные изображения отпечатка пальца контрольные точки».

4. Ландау Л. Д., Лифшиц Е. М. Теоретическая физика. — Издание 5-е, стереотипное. — М.: Физматлит, 2001. — Т. VII. Теория упругости. — 259 с.

5. Кухарев Г.А. Биометрические системы: методы и средства идентификации личности человека. СПб.: Политехника, 2001.-240 с.

6. Насонов А.В., Крылов А.С., Ушмаев О.С., Применение метода суперразрешения для биометрических задач распознавания лиц в видеопотоке// Системы высокой доступности, №1, т.5, 2009, с. 26-34.

7. Насонов А.В., Крылов А. С., Ушмаев О.С. Развитие методов повышения качества лиц в видеопотоке// Информатика и ее применения, т.З, вып.1, 2009, С.19-29.

8. Пугачев B.C., Синицын И.Н. Теория стохастических систем: учеб. пособие. М.: Логос, 2004. - 1000 с.

9. Самищенко С.С. Атлас необычных папиллярных узоров. Москва: Юриспруденция, 2001. - 320 с.

10. Спиридонов И.Н. Особенности разработки биометрических стандартов //Электронные компоненты.- № 4, 2006, с. 37 40.

11. Ушмаев О.С. Адаптация биометрической системы к искажающим факторам на примере дактилоскопической идентификации // Информатика и ее применения, 2009. Т.З. Вып.2. С.25-33.

12. Уишаев О.С., Арутюнян А.Р. Влияние деформаций на качество биометрической идентификации по отпечаткам пальцев идентификации // Информатика и ее применения, 2009. Т.З. Вып.4. С. 12-21.

13. Хрулев А.А., Аполлонова И.А., Спиридонов И.Н. Разработка алгоритма формирования изображений пальцевых узоров // Биомедицинские технологии и радиоэлектроника. 2005. № 9. С. 61-66.

14. ANSI/NIST ITL 1-2000 Data Format for the Interchange of Fingerprint, Facial, & Scar Mark&Tattoo (SMT) Information

15. ANSI/NIST ITL 1-2007 Data Format for the Interchange of Fingerprint Facial, & Other Biometric Information Part 1

16. Arad, N., Reisfeld, D. Image warping using few anchor points and radial functions // Computer Graphics Forum. 14(1) (1995) 35-46.

17. Bazen A.M., Gerez S. Fingerprint Matching by Thin-Plate Spline Modeling of Elastic Deformations // Pattern Recognition, vol. 36, no. 8, pp. 1859-1867, Aug. 2003

18. Biometric System: Technology, Design and Performance Evaluation, Wayman, J.; Jain, A.; Maltoni, D.; Maio, D. (Eds.) Springer, 2005, XIV. -370 p.

19. Blanz V., Vetter T. A Morphable Model for Synthesis of 3D Faces // Computer Graphics Proceedings SIGGRAPH, 1999, P. 187-194.

20. Braggins D. Fingerprint sensing and analysis // Sensor Review, Vol. 21 Iss: 4, pp.272 277

21. Bolle R.M., Ratha N.K., Pankanti S. Error analysis of pattern recognition systems—the subsets bootstrap // Computer Vision and Image Understanding, Vol. 93, No. 1,2004, p. 1-33.

22. Bookstein F.L. Principal Warps: Thin-Plate Splines and the Decomposition of Deformations // IEEE Trans. Pattern Analysis and Machine Intelligence vol. 11, pp. 567-585, 1989

23. Burr D.J. A Dynamic Model for Image Registration // Computer Graphics and Image Processing Vol. 15 pp. 102-112, 1981

24. Cappelli R., Maio D. and Maltoni D. Modelling Plastic Distortion in Fingerprint Images // Proc. Second Int'l Conf. Advances in Pattern Recognition, Mar. 2001

25. Dalrymple B. Fingerprints (Dactyloscopy) Identification and Classification in Encyclopedia of Forensic Science, Siegel, J. et al., Eds., Academic Press, New York, 2000, 872p.

26. Daoudi M., Ballihi L., Samir C., Srivastava A. Three-dimensional face recognition using elastic deformations of facial surfaces // Proc. IEEE Intern. Conf. on Multimedia and Expo, 2008, p.97-100.

27. Daugman J. G. Biometric personal identification system based on iris analysis, US Patent #5,291,560 (1994).

28. Eleccion M. Automatic Fingerprint Identification// IEEE Spectrum, 1973, 10, P. 36-45.

29. Fornefett M., Rohr K. and Stiehl H.S. Radial Basis Functions with Compact Support for Elastic Registration of Medical Images // Image and Vision Computing, 19 (1-2), 2001, pp. 87-96.

30. Galton F. Finger Prints. New York: Williams Hein& C, 2002. 216 p.

31. Gudkov V.Yu. Mathematical Models of Fingerprint Image On the Basis of Lines Description // Proc. of The 19th International Conference on Computer

32. Graphics and Vision (GraphiCon'2009), October 5-9, 2009, Moscow, p. 223227.

33. Halici U., Jain L.C., Erol A. Introduction to Fingerprint Recognition, Intelligent Biometric Techniques in Fingerprint and Face Recognition, CRC Press, 1999.

34. The Henry classification system. 2003. (www.biometricgroup.com/HenryFingerprintClassification.pdf).

35. Jain A.K., Prabhakar S., Hong L. Filterbank-Based Fingerprint Matching // IEEE Trans. Image Processing, vol. 9, no.5, 2000, pp.846-859.

36. Jolliffe I. T. Principal Component Analysis, 2nd edition, Springer, 2002, 502 p.

37. Kass M. and Witkin A. Analyzing Oriented Patterns // Computer Vision, Graphics, and Image Processing, vol. 37, no. 3, pp. 362-385, Mar. 1987.

38. Kucken M., Newell A. C. Fingerprint Formation // Journal of Theoretical Biology, 235(2005), p.71-83.

39. Liang X., Asano, Т., Zhang H. A Combined Radial Basic Function Model for Fingerprint Distortion // Proc. ICIAR2006, LNCS, vol. 4142, p. 286-296.

40. Fingerprint Vendor Technology Evaluation, http://fpvte.nist.gov.

41. Maio D., Maltoni D., Cappelli R., Wayman J.L., Jain A.K. FVC2002: Second fingerprint verification competition // Proceedings of the 16th International Conference on Pattern Recognition, vol. 3, 2002, pp. 811- 814

42. Maio D., Maltoni D., Cappelli R., Wayman J.L., Jain A.K. FVC2004: Third fingerprint verification competition // Proceedings of the First International Conference on Biometric Authentication, vol. 3072,2004, pp. 1-7

43. MISTMINEX. http://www.nist.gov/itl/iad/ig/minex.cfin

44. Novikov S.O., Glushchenko G.N. Fingerprint ridge structure generation models// Proceedings of the SPIE, The International Society for Optical Engineering, 1998, vol. 3346, pp. 270-274

45. Ratha N., Chen S., Jain A.K. Adaptive Flow Orientation Based Feature Extraction in Fingerprint Images // Pattern Recognition, vol. 28, pp. 1657-1672, Nov. 1995.

46. Ross A., Dass S., Jain A. Fingerprint Warping Using Ridge Curve Correspondences // IEEE Trans. PAMI, vol. 28, no.l, 2006, p. 19-30.

47. SFinGe v.2.51. http://bias.csr.unibo.it/research/biolab/bio tree.html

48. Sparrow M.K. Pat. 5631971 USA, Int.Cl. G 06 К 9/00.

49. Thurston, R.N. Waves in Solids// Mechanics of Solids IV (Festkoerpermechanik IV). Berlin, Springer-Verlag (Handbuch der Physik. Volume VIa/4), 1974, p. 109-308.

50. NovikovPatent. U.S. Patent #6,282,304

51. Watson C. NIST Special Database 14: Mated Fingerprint Cards Pairs 2 Version 2

52. Watson C. NIST Special Database 29: Plain and Rolled Images from Paired Fingerprint Cards

53. Watson C., Wilson С., Indovina M., Cochran B. NISTIR 7249, Two Finger Matching With Vendor SDK Matchers, July 2005.

54. Wiskott L., Fellous J.-M., KrAuger N., and von der Malsburg C. Face recognition by elastic bunch graph matching // L. C. Jain, U. Halici, I.

55. Hayashi, and S. B. Lee, editors, Intelligent Biometric Techniques in Fingerprint and Face Recognition, chapter 11, pages 355-396. CRC Press, 1999.

56. Yanushkevich S.N., Stoica A., Shmerko V.P. Developmental Tools Synthetic Biometrics// IEEE Computational Intelligence Magazine, vol.2 (2) 2007. p.60-68.