Например, Бобцов

АЛГОРИТМ ИНВАРИАНТНОГО РАСПОЗНАВАНИЯ ОТПЕЧАТКОВ ПАЛЬЦЕВ ПО КЛЮЧЕВЫМ ТОЧКАМ

Алгоритм инвариантного распознавания отпечатков пальцев по ключевым точкам

31

УДК 621.518.2

А. В. ОГНЕВ, А. П. ТИПИКИН
АЛГОРИТМ ИНВАРИАНТНОГО РАСПОЗНАВАНИЯ ОТПЕЧАТКОВ ПАЛЬЦЕВ ПО КЛЮЧЕВЫМ ТОЧКАМ
Рассматривается алгоритм, позволяющий существенно снизить зависимость вероятности распознавания отпечатков пальцев (ОП) от смещений, поворотов, фрагментации и дефектов поверхности папиллярного узора. Скорость распознавания увеличивается за счет введения этапа центрирования ОП с поиском наиболее достоверных пар базовых отрезков в сопоставляемых ОП, а также за счет сравнительной простоты распараллеливания алгоритмов распознавания, основанных на метрике Хаусдорфа, позволяющей находить расстояния между неравномощными множествами признаков.
Ключевые слова: идентификация отпечатка пальца, инвариантность, оцифровка, центрирование.
В современной криминалистике широко используются программы распознавания отпечатков пальцев (ОП). Для достижения высокой степени вероятности распознавания как на начальных, так и на завершающих стадиях работы программы требуется участие человека, и чем больше база данных ОП и выше вероятность повреждения отпечатков, тем чаще. Рассматриваемый алгоритм позволяет повысить степень автоматизации процесса распознавания, а также скорость распознавания на основе привлечения больших вычислительных ресурсов и ускорения отдельных процедур путем параллельной обработки информации.
Разработка алгоритмов распознавания ОП идет очень активно [1], но любой из существующих имеет свои недостатки: возможны ошибки false-reject rate (ошибочный отказ) и falsealarm rate (ошибочное подтверждение), возникающие из-за образующихся при сканировании смещений, поворотов, фрагментации, а также дефектов поверхности папиллярного узора. Избежать этих недостатков можно, если применять алгоритмы, инвариантные к названным негативным факторам. При решении задачи верификации (подтверждения личности) требуются мобильные датчики и вычислительные устройства (ВУ) со сравнительно небольшой тактовой частотой процессоров и объемом памяти. При решении задачи идентификации (определения личности) используются большие базы данных (БД), содержащие информацию об ОП и их обладателях, многократно повторяется процедура распознавания, поэтому возрастают требования к повышению производительности ВУ. В последнем случае целесообразно использовать параллельные алгоритмы сравнения и выполнять их на многопроцессорных ВУ. Так как в обоих случаях время принятия решения ограничено, вычислительная сложность инвариантного алгоритма не должна быть слишком большой, а для снижения требуемой емкости памяти желательно не хранить полное описание изображения ОП, а оперировать только с его моделями (множествами ключевых точек). Этого требуют соображения безопасности для того, чтобы при хищении из БД отпечатков ими нельзя было воспользоваться.
Известны два основополагающих алгоритма распознавания отпечатков пальцев: по отдельным деталям (ключевым точкам, КТ — развилкам и окончаниям, называемым минуциями) и по рельефу всей поверхности пальца [2]. В первом случае устройство регистрирует только некоторые точки, уникальные, свойственные конкретному отпечатку, и определяет их взаимное расположение. Во втором случае обрабатывается изображение всего отпечатка.
Алгоритм инвариантного распознавания отпечатков пальцев по ключевым точкам состоит из трех этапов: предварительная обработка изображения, центрирование, распознавание.

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2

32 А. В. Огнев, А. П. Типикин

На этапе предварительной обработки каждое изображение ОП должно быть бинаризо-

вано и отфильтровано. На этом этапе в черно-белом пиксельном изображении ОП устраняет-

ся часть ложных пропечаток, папиллярные линии утончаются до значения в один пиксел, ло-

гически устраняются некоторые их короткие ложные ответвления и небольшие разрывы.

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

мативной области ОП, его центр, а также выделены и описаны КТ в первичной (декартовой)

системе координат относительно центра.

В настоящее время при использовании многих известных алгоритмов сравнения ОП

сталкиваются с проблемой не вполне точного центрирования отпечатков [3]. Центрирование

необходимо для ускорения процесса сравнения. Известно множество методов центрирования,

но все они уязвимы к аффинным трансформациям (поворотам и смещениям) и дефектам па-

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

кой точности [4]. Можно выделить два основных подхода: нахождение пиксельного центра

тяжести и определение центра информативной области ОП. Если за центры сравниваемых

ОП принимаются центры тяжести всех пикселов папилляров каждого отпечатка, то вследст-

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

возникают неточности при фрагментации ОП.

Выделение КТ и вычисление их координат выполняется в первичной системе координат

относительно неточного центра ОП путем просмотра каждого пиксела отпечатка и его бли-

жайшей окрестности. Если в этом пикселе папилляр разветвляется или оканчивается, он при-

нимается за КТ.

Широко применяемым инвариантным алгоритмом распознавания ОП является метод

корреляционного сравнения [4]. Сопоставление двух ОП основано на многократных сравне-

ниях множеств КТ и выполняется со скоростью 200—3000 сравнений в секунду [5], что при-

водит к значительным затратам времени. При сопоставлении перебираются пары КТ по

принципу „каждая с каждой“. В окрестности каждой КТ проводится поиск ближайшей КТ

другого отпечатка. Если она расположена на допустимом удалении, то эти две точки счи-

таются совпавшими. В качестве меры близости двух ОП принимается число пар их КТ, при-

знанных совпавшими. При сопоставлении двух ОП за достоверный центр одного из ОП при-

нимается поочередно каждый пиксел его центральной области [6], размер которой опреде-

ляется величиной возможного смещения ОП при сканировании и может составить до 10 % от

длины рамки изображения ОП.

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

смещение его центра в другой пиксел центральной области и вновь вычисляется мера близо-

сти двух ОП. Повторные сопоставления двух ОП продолжаются до тех пор, пока не будут пе-

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

рота одного из ОП, например, с шагом в 1° в диапазоне ±15°. Решение об идентификации

принимается по наибольшему значению меры близости из всех вариантов сопоставлений, ес-

ли оно не меньше заданного порога. Число парных сравнений КТ двух ОП, требуемое для

принятия решения, равно

Nср = NdNЦОN2КТ,

где Nd — число шагов поворота одного из ОП; NЦО — число пикселов центральной области; NКТ — число КТ в одном из ОП. Nd = 30 при шаге 1° и диапазоне ±15°; NЦО = 60·40 = 2400

пикселов при растре 600×400 пикселов; NКТ = 70 точек. Поэтому требуемое число парных сравнений точек Nср ≈ 3,5·108. Это приводит к большим затратам времени при реализации данного способа сопоставления на современных компьютерах.

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

распознавания ОП от смещений, поворотов, фрагментации и дефектов поверхности папил-

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

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2

Алгоритм инвариантного распознавания отпечатков пальцев по ключевым точкам

33

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

торных описаний изображения ОП и параллельного их сопоставления позволяют автомати-

зировать формирование БД эталонов ОП и повысить вероятность их инвариантного распо-

знавания. Инвариантность по отношению к смещениям, поворотам, фрагментации и наиболее

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

использованием метрики Хаусдорфа [1] их избыточных векторных описаний в полярной сис-

теме координат относительно базовых отрезков (БО).

Скорость инвариантного распознавания ОП увеличивается за счет дополнительного

предварительного этапа поиска наиболее достоверных пар базовых отрезков в сопоставляе-

мых отпечатках. После ранжирования пар базовых отрезков можно сократить требуемое чис-

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

попарной обработки минуций двух отпечатков — до 104—105 [6]. Дополнительным резервом

повышения скорости является сравнительная простота распараллеливания алгоритмов распо-

знавания, основанных на метрике Хаусдорфа, позволяющей находить расстояния между не-

равномощными множествами признаков [7].

Требуемое число вариантов сравнения ОП по ключевым точкам может быть уменьшено

на основе следующей методики центрирования [6]. Для достижения желаемой инвариантно-

сти необходимо перейти от „грубой“ (декартовой) к „новой“ (полярной) системе координат,

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

фективности работы алгоритма из рассмотрения исключаются КТ, близкие к границе инфор-

мативной области („зашумленность“ изображения ОП при приближении к его краям повы-

шается), и к центру ОП (из-за неточности расположения центра ОП). БО формируется только

из оставшихся внутренних точек окончаний и разветвлений папилляров.

Минимального числа БО с сохранением единообразия их выбора в паре сравниваемых

ОП можно достичь по следующему правилу обхода точек. Вращая по часовой стрелке радиус-

вектор из центра первичной системы координат, последовательно соединить отрезками пря-

мых встречающиеся КТ. Если несколько КТ встречаются в одном направлении радиуса-

вектора, то предыдущая точка соединяется с самой удаленной от центра. При этом остальные

КТ соединяются между собой последовательно по мере приближения к центру. Таким обра-

зом, формируется замкнутый контур БО, представляющий собой ломаную с вершинами в КТ.

После составления контуров БО необходимо в обоих ОП выделить пары БО, близкие по

длине и взаимной ориентации. Последняя определяется значениями углов с четырьмя сосед-

ними БО в контуре (см. рисунок). Так как могут выпадать соседние БО или появляться лож-

ные отрезки, то определить достоверную пару БО можно следующим образом. Сначала опре-

делим, в каком из ОП имеется меньшее число БО, входящих в ломаные. Этот отпечаток А ис-

пользуется для минимизации числа проверяемых пар БО. Для каждого БО отпечатка А необ-

ходимо выбрать такой парный ему БО из второго отпечатка В, для которого будет минималь-

ной мера С:

С1=

l

A

−lB L

+ aA1 −aB1 Λ

,

С2=

lA

−lB L

+

aA2

− aB2 Λ

,

С3=

l

A

−lB L

+ aA3 −aB3 Λ

,

С4=

lA

−lB L

+

aA4

− aB4 Λ

,

С = min{С1, С2, С3, С4},

(1)

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2

34 А. В. Огнев, А. П. Типикин

где l — длина БО; а — угол с соседним БО в пределах одного и того же ОП; L — максималь-

ная длина БО в обоих ОП; Λ — максимально возможная величина угла, равная 2π.

В качестве центра О новой полярной системы координат в одном из ОП принимается

центр достоверного БО (см. рисунок) той пары БО, для которой будет значение С наимень-

шим. Достоверная пара БО выбирается по следующей формуле:

{ }{ }Cmin

= min
i

⎨⎪⎪⎩⎧mjin

min
K

C

K =4 K =1

j=NB

⎪⎫i=N A ⎬

,

j=1 ⎪⎭i=1

где NA, NB — число БО в отпечатках А и В соответственно; K — число соседних БО, используемых при нахождении меры С (1), где K = 4.

Т
О О1
БО K α2 α3 α4

КТ

α1
Учитывая возможную близость между собой по значению С нескольких первых проранжированных пар БО, в дальнейшем величины метрики Хаусдорфа целесообразно вычислять для первых трех пар БО, а расстояния между ними выбирать минимальными.
Векторные описания множеств КТ формируются в полярной системе координат с учетом расстояния от центра О достоверного БО до данной КТ, например до точки Т (см. рисунок), и угла между лучом, проведенным из центра О в первый (K) конец БО, и лучом, проведенным из центра БО в данную КТ. Перевод из первичной (декартовой, О1 — ее центр) в новую полярную систему координат осуществляется по следующим формулам:
L= ( XT − XO )2 +(YT −YO )2 ,
α = arccos ( XT − XO )2 +(YT −YO )2 +( X K − XO )2 +(YK −YO )2 −( X K − XT )2 −(YK −YT )2 , 2 ( XT − XO )2 +(YT −YO )2 ( X K − XO )2 +(YK −YO )2
где ХТ, YТ — абсцисса и ордината данной КТ в первичной системе координат; ХО, YО — абсцисса и ордината центра достоверного БО в первичной системе координат.

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2

Алгоритм инвариантного распознавания отпечатков пальцев по ключевым точкам

35

После того как сформированы описания множеств КТ относительно центров достовер-

ных БО в обоих ОП, для каждого элемента множеств КТ, соответствующих отпечаткам А и В,

вычисляются минимальные расстояния от всех элементов другого множества:

{ (( ) ( ))}ekA = mint d αkA, lkA , αtB , ltB t=NB , k =1, ..., NA , t =1

{ (( ) ( ))}etB = mink d αtB , ltB , αkA, lkA k=NA , t =1, ..., NB , k =1

(2)

где d(x, y) — расстояние между элементами множеств x и y; t, k — номер КТ в множествах А и

В соответственно.

Затем вычисляются максимальные значения из множеств полученных минимумов:

{ }emAax = mink ekA ,

{ }emBax = mint etB .

(3)

После этого вычисляются максимум и минимум из двух полученных величин (3):

( )emax i, j = max emAax , emBax ,

( )emin i, j = min emAax , emBax ,

(4)

где i, j — номера выбранных достоверных БО в А и В соответственно. Минимум (см. выражение (4)) находится для того, чтобы определить степень включения
одного множества в другое. Такая модификация алгоритма сопоставления неравномощных множеств на основе метрики Хаусдорфа позволяет численно определить степень идентичности фрагментов пары ОП.
Решение об идентичности ОП принимается на основе следующего анализа значений

emax i, j и emin i, j (4). Если emax i, j ≤ h и emin i, j ≤ h, то ОП идентичны. Если emax i, j > h и

emin i, j > h, то ОП принадлежат разным людям. Если emax i, j > h и emin i, j ≤ h, то фрагменты

сопоставляемых ОП близки. Величина порога h выбирается пропорциональной среднему значению меры С (1) и может быть подобрана опытным путем на тестовых парах сопоставляемых ОП. Вычислительная сложность описанного алгоритма инвариантного распознавания ОП определяется в основном необходимостью трехкратного повторения расчетов по формулам (2)—(4). Затраты времени на остальные описанные выше процедуры составляют не более 4 %. Сопоставление двух ОП выполняется примерно за 3,5·104 шагов, каждый из которых эквивалентен вычислению одного расстояния между двумя КТ и по длительности не превышает затрат времени на 10 парных сравнений КТ в корреляционном методе. Таким образом, скорость инвариантного распознавания возрастает практически в 1000 раз.
Преимуществами данного алгоритма являются повышение степени инвариантности к поворотам, смещениям, фрагментации и дефектам ОП, а также возможность ускорения процесса распознавания за счет сравнительной простоты распараллеливания вычислений при центрировании ОП (1) и нахождении расстояний между сравниваемыми ОП по формулам (2)—(4).

СПИСОК ЛИТЕРАТУРЫ
1. Биометрия. Отпечаток пальца [Электронный ресурс]: .
2. Рябов Г. В. Современные технологии идентификации личности по отпечатку пальца с использованием емкостных датчиков [Электронный ресурс]: .

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2

36 А. В. Огнев, А. П. Типикин

3. Яковлев А. В., Румянцев Р. В. Разработка алгоритма идентификации личности по изображению отпечатка пальца // Методы и системы обработки информации. Сб. науч. ст. Ч. 2 / Под ред. С. С. Садыкова, Д. Е. Андрианова. М.: Горячая линия – Телеком, 2004. С. 41—48.

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

5. Пат. № 2310910 РФ. Способ верификации и идентификации отпечатков папиллярных узоров / А. А. Борейшо, Д. А. Фокин, С. Я. Чакчир, А. Ю. Хозин, Е. М. Орлов. 16.05.2006.

6. Огнев А. В., Типикин А. П. Центрирование отпечатков пальцев при инвариантном распознавании на основе метрики Хаусдорфа // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации. Сб. мат. VIII Междунар. конф. „Распознавание – 2008“. Ч. 2. Курск: КурскГТУ, 2008. С. 34—35.

7. Ognev A. V., Tipikin A. P. Method of invariable recognition of fingerprints based on metric of Hausdorph // Proc. 6th Int. Conf. „Information and telecommunication technologies in intelligent systems“. Crete, Grece. June 2—6, 2008. P. 78—82.

Антон Вадимович Огнев Александр Петрович Типикин

Сведения об авторах — магистрант; Курский государственный технический университет, ка-
федра вычислительной техники; Е-mail: light@kursknet.ru — д-р техн. наук, профессор; Курский государственный технический
университет, кафедра вычислительной техники; Е-mail: cct@cafct.kstu.kursk.ru

Рекомендована кафедрой вычислительной техники

Поступила в редакцию 12.09.08 г.

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2