Алгоритм сравнения отпечатков пальцев: комбинация классических алгоритмов / forpes.ru

Главная
Алгоритм сравнения отпечатков пальцев: комбинация классических алгоритмов

Алгоритм сравнения отпечатков пальцев: комбинация классических алгоритмов +17

11.09.2024 19:10

AlexAproner 2 2800 Источник

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

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

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

Рисунок 1. Характерные точки (минюции), выделяемые на изображениях отпечатков пальцев человека.

Примером алгоритма выделения минюций на изображениях отпечатков пальцев является алгоритм MINDTCT, реализация которого включена в пакет программ NIST Biometric Image Software (NBIS)[3]. Исходный код NBIS доступен по ссылке [4].

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

- координаты минюции (x, y) по отношению к системе координат, связанной с изображением отпечатка (центр координат - левый верхний угол изображения, ось ординат направлена вниз);

- её направление $\theta = [0^0; 360^0)$ , которое определяется значением угла касательной к папиллярной линии в точке по отношению к горизонтальной оси;

- тип минюции (окончание или ветвление);

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

Рисунок 2. Параметры минюции: а) окончания, б) ветвления.

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

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

В случае описания отпечатка набором минюций нам необходимо посчитать число совпадающих минюций после компенсации сдвига и поворота отпечатка по отношению к отпечатку с учётом локальных нелинейных деформаций (Рис. 3). Примеры отпечатков взяты из датасетов, размещённых на сайтах международного конкурса Fingerprint Verification Competition [2].

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

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

Приведённый выше рисунок хорошо иллюстрирует основные проблемы, возникающие при сравнении отпечатков с использованием минюций:

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

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

Для решения последней из указанных проблем, вводят следующее правило: две минюции $t \in T, t = (x_t, y_t, \theta_t)$ и $p \in P, p = (x_p, y_p, \theta_p)$ будут образовывать пару в том случае, если выполняются следующие условия:

$\sqrt{(x_t - x_p)^2 + (y_t - y_p)^2} \leq d_{thr},$ $\min(|\theta_t - \theta_p|, 360^0 - |\theta_t - \theta_p|) \leq \theta_{thr}.$

В последнем выражении выбирается минимум из двух величин: $|\theta_t - \theta_p|$ и $360^0 - |\theta_t - \theta_p|$ из-за цикличности значения разности углов (разность между углами и составляет всего лишь ).

Пороговые значения $d_{thr}$ и $\theta_{thr}$ задают пространство допусков (tolerance box): чтобы минюции образовали пару, необходимо, чтобы после взаимного совмещения отпечатков они находились достаточно близко к друг другу, а их направления не слишком сильно различались. Пример образования пар минюций для двух сравниваемых отпечатков после компенсации взаимного сдвига и поворота представлен на рисунке ниже.

Рисунок 4. Пример образования пар минюций при сравнении.

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

Для решения задачи сравнения отпечатков рассмотрим алгоритм, описанный в статье [5]. Алгоритм включает в себя следующие этапы:

подготовка промежуточного представления отпечатков (representation), необходимого для применения алгоритма сравнения;
сравнение промежуточных представлений отпечатков, которое включает в себя
- сравнение локальных структур минюций (local structure matching), которые имеют параметры, инвариантные относительно глобальных преобразований. Что такое "локальная структура минюций", мы рассмотрим немного позднее;
- объединение результатов сравнения локальных структур минюций (consolidation), цель которого проверить правильность гипотезы о совпадении отпечатков на глобальном уровне.

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

Теперь пройдёмся по каждому из описанных выше этапов.

Подготовка промежуточного представления отпечатка

Входными данными для этого шага является список выделенных на отпечатке минюций: $\overline{T} = \{ t_0, t_1, ..., T_{N-1} \}, t = (x_i, y_i, \theta_i), i = 0,...,N-1$ . Здесь $\theta_i \in [0^0; 360^0)$ .

Для получения промежуточного представления отпечатка выполним следующие шаги:

Шаг 1. Вычисляем координаты центра тяжести для списка минюций, полагая, что "масса" каждой из минюций равна 1:

$x_{cm}=\frac{1}{N}\sum_{i=0}^{N-1}x_i; y_{cm}=\frac{1}{N}\sum_{i=0}^{N-1}y_i.$

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

$x_{cm}=\frac{\sum_{i=0}^{N-1}q_i*x_i}{\sum_{i=0}^{N-1}q_i}; y_{cm}=\frac{\sum_{i=0}^{N-1}q_i*y_i}{\sum_{i=0}^{N-1}q_i}.$

Шаг 2. Отсортируем список минюций по возрастанию их взаимного расстояния от центра тяжести $(x_{cm}, y_{cm})$ .

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

Шаг 3. Для каждой минюции формируют локальную структуру, которую авторы алгоритма [5] назвали "K-plet". "K-plet" строится таким образом, чтобы быть инвариантным к возможному взаимному сдвигу и повороту, который может присутствовать на сравниваемых отпечатках.

"K-plet" состоит из центральной минюции $t_i = (x_i, y_i, \theta_i), i = 0,...,N-1$ и других минюций отпечатка $\{t_j, j = 0,...,K-1 | j \neq i\}$ . К тому, как выбрать эти минюций, мы вернёмся позднее.

Каждая минюция представляется тройкой чисел $(r_{ij}, \alpha_{ij}, \theta_{ij})$ . Здесь $r_{ij}$ - Евклидово расстояние между минюциями и ; $\alpha_{ij}$ - угол, который образует отрезок, соединяющий минюции и ; $\theta_{ij}$ - направление минюции относительно направления центральной минюции .

Звучит не очень понятно, но если посмотреть на рисунок, то всё встаёт на свои места.

Рисунок 5. Параметры минюций, формирующих "K-plet".

Ниже приведены формулы расчёта параметров $(r_{ij}, \alpha_{ij}, \theta_{ij})$ для минюции $t_j = (x_j, y_j, \theta_j), j \neq i$ в случае, если центральная минюция $t_i = (x_i, y_i, \theta_i)$ :

$r_{ij} = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$ $\beta_{ij} = \begin{cases} 360^0 + atan2(\frac{y_j - y_i}{x_j - x_i}), если\ atan2(\frac{y_j - y_i}{x_j - x_i}) < 0; \\ atan2(\frac{y_j - y_i}{x_j - x_i}), в\ противном\ случае. \end{cases}$ $\alpha_{ij} = \begin{cases} 360^0 + \beta_{ij} - \theta_i, если\ \beta_{ij} - \theta_i < 0; \\ \beta_{ij} - \theta_i, в\ противном\ случае. \end{cases}$ $\theta_{ij} = \begin{cases} 360^0 + \theta_j - \theta_i, если\ \theta_j - \theta_i < 0 \\ \theta_j - \theta_i, в\ противном\ случае.\end{cases}$

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

Теперь рассмотрим подробнее процедуру формирования "K-plet" для очередной минюции в предположении, что для всех других минюций $\{t_j, j = 0,..., N-1 | j \neq i\}$ мы уже вычислили значения $(r_{ij}, \alpha_{ij}, \theta_{ij})$ .

Шаг 3.1. Разделим множество минюции $\{t_j = (r_{ij}, \alpha_{ij}, \theta_{ij})\}$ на четыре непересекающиеся группы, соответствующие квадрантам, на основании значений $\alpha_{ij}$ :

Рисунок 6. Разделение минюций по квадрантам.

При этом в какой-то группе может и не быть минюций (как например в группе III).

Шаг 3.2. Для каждой из сформированных на предыдущем шаге групп проводят сортировку минюций внутри группы в порядке неубывания значений $r_{ij}$ .

Шаг 3.3. Сформируем пустой список минюций, который будет описывать "K-plet".

Совершаем последовательный циклический обход сформированных групп (I группа -> II группа -> III группа -> IV группа -> I группа -> ...).

При каждом посещении какой-либо группы выбираем очередную минюцию и добавляем её в "K-plet". При этом одновременно удаляем выбранную минюцию из рассматриваемой группы и переходим к следующей группе.

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

Циклический обход групп завершается, если из всех четырёх групп суммарно было выбрано минюций или если выбраны все минюции.

Пример, иллюстрирующий шаг 3.3. для случая представлен на рисунке ниже:

Рисунок 7. Пример выбора минюций при формировании "K-plet".

Указанный способ выбора минюций для построения "K-plet" позволяет сохранить высокую связность между различными областями отпечатка, в отличие от простого выбора наиболее близких по расстоянию от центральной минюций. Как мы увидим в дальнейшем, высокая связность является важным свойством, используемым алгоритмом сравнения.

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

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

Рисунок 8. Визуализация промежуточных представлений отпечатков.

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

Рассматриваемый алгоритм сравнения основан на попарном сравнении локальных структур минюций ("K-plet") с последующим переходом к сравнению локальных структур для соседних минюций. Звучит опять не очень понятно.

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

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

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

$S(T,P) = \frac{m^2}{N_T * N_R},$

где - количество минюций, выделенных на отпечатке , а - количество минюций, выделенных на отпечатке .

Для обхода вершин графов мы можем воспользоваться либо алгоритмом обхода графа в ширину (breadth-first search, BFS), либо алгоритмом обхода графа в глубину (depth-first search, DFS) [6]. В данном конкретном случае нет абсолютно никакой разницы, какой алгоритм обхода (BFS или DFS) мы можем использовать. Авторы алгоритма [5] предлагают использовать алгоритм BFS. Мы же, чтобы было интереснее, будем использовать алгоритм DFS.

Хотелось бы напомнить, что разница между BFS и DFS заключается в порядке обхода вершин. Порядок обхода задаётся структурой данных, которая служит для хранения и последующей выборки посещённых, но не обработанных вершин. Для BFS такая структура - очередь (First In, First Out - FIFO). Для DFS - стек (Last In, First Out - LIFO).

Описание алгоритма DFS можно найти, например, в книгах [6,7] или в публикациях на Хабре (например, [8]).

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

Модификации заключаются в следующем:

Мы будем обходить графы и одновременно.

Вернёмся обратно к определению промежуточного представления отпечатка. Это массив, содержащий "K-plet" для каждой из минюций. В свою очередь "K-plet" представляет собой упорядоченный список смежных вершин. Фактически, сравниваемые графы задаются упорядоченными списками смежных вершин (adjucency-list representation). В этом случае алгоритм DFS при одновременном обходе двух графов для отпечатков одного и того же пальца будет одновременно посещать вершины, представляющие одну и ту же минюцию.

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

Тогда алгоритм сравнения будет выглядеть так:

Входные данные:

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

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

Непосредственно алгоритм сравнения:

Окрашиваем все вершины $v^t \in G_T$ и $v^p \in G_P$ в белый цвет;
Кладём в стек начальную пару вершин $({v^t}_i, {v^p}_j)$ и окрашиваем эти вершины в серый цвет;
Пока стек не пуст, извлекаем верхнюю пару вершин $({v^t}_k, {v^p}_l)$ :

4.1. Сравниваем два "K-plet" для вершин ${v^t}_k$ и ${v^p}_l$ ; результат сравнения - список пар смежных вершин, которые представляют одну и ту же минюцию (другими словами, образовали пары);

4.2. Из полученного списка пар смежных вершин кладём в стек только те пары, в которых вершины - белые; обозначим число таких пар ; вершины в этих парах перекрашиваем в серый цвет;

4.3.
Красим вершины ${v^t}_k$ и ${v^p}$ в чёрный цвет;
Получившееся число совпавших пар используем для вычисления коэффициент подобия.

Точность описанного выше алгоритма зависит от того, каким образом реализован шаг 4.1 - сравнение локальных структур минюций (двух "K-plet").

Сравнение локальных структур минюций

Итак, "K-plet" - это упорядоченный список смежных вершин. Результат сравнения двух "K-plet"- список пар смежных вершин, которые образовали пары (представляют одну и ту же минюцию). А значит, задачу сравнения двух "K-plet" можно представить как задачу о нахождении наибольшей общей подпоследовательности (Longest Common Subsequenbce - LCS)[7,9].

Задача LCS состоит в том, чтобы найти общую подпоследовательность наибольшей длины для двух последовательностей $X = {x_0, x_1, ..., x_m}$ и $Y = {y_0, y_1, ... , y_n}$ . Эта задача решается путём применения динамического программирования.

В этом случае алгоритм решения задачи LCS будет состоять из двух последовательных этапов:

Этап 1, который следуя [7] назовём "LCS-Length". Результат этого этапа - длина наибольшей общей подпоследовательности, а также данные, необходимые для построения наибольшей общей подпоследовательности;
Этап 2 ("Print-LCS"), в результате которого мы получим наибольшую общую подпоследовательность.

Следуя [7], приведём псевдокод для "LCS-Length" и "Print-LCS".

LCS-Length(X, Y)

for i ← 0 to m
    do c[i,0] ← 0
for j ← 0 to n
    do c[0,j] ← 0
for i ← 1 to m
    do for j ← 1 to n
           do if IsEqual(X[i-1], Y[j-1])
                 then c[i,j] ← c[i-1,j-1] + MatchingWeight(X[i-1], Y[j-1])
                      b[i,j] ← "↖"
                 else if c[i-1,j] ≥ c[i,j-1]
                         then c[i,j] ← c[i-1,j]
                              b[i,j] ← "↑"
                         else c[i,j] ← c[i,j-1]
                              b[i,j] ← "←"
return c,b

Здесь - двумерный массив для хранения стоимости формируемой наибольшей общей подпоследовательности, - двумерный массив, сохраняющий "происхождение" ; эта информация необходима для последующего построения наибольшей общей подпоследовательности:

Print-LCS(b, X, Y)

l ← {}
i ← m
j ← n
while i > 0 and j > 0
      do if b[i,j] = "↖"
            then l ← l + {(X[i-1],Y[j-1])}
                 i ← i-1
                 j ← j-1
            elseif b[i,j] = "↑"
                   then i ← i-1
            else j ← j-1
return l

Здесь - список пар смежных вершин, которые образовали пары.

Если бы сравниваемые последовательности и представляли собой обычные строки, то функция "IsEqual(x,y)", которая вызывается на строке 7 функции "LCS-Length", превратилась бы в простую проверку на равенство . А функция "MatchingWeight(x,y)", вызываемая на строке 8, возвращала бы всегда 1. В этом случае код функции "LCS-Length" полностью совпадёт с кодом, приведённым в книге [7].

В нашем случае мы сравниваем два "K-plet", где каждый "символ" - это тройка чисел (Евклидово расстояние от центральной минюции; угол, который образует прямая, проходящая через текущую минюцию и центральную минюцию; и направление текущей минюции относительно направления центральной минюции).

Тогда функция "IsEqual(x,y)" превратиться в проверку следующих условий:

$\Delta_r = |r_x - r_y|,$ $\Delta_{\alpha} = \min(|\alpha_x - \alpha_y|, 360^0 - |\alpha_x - \alpha_y|),$ $\Delta_{\theta} = \min(|\theta_x - \theta_y|, 360^0 - |\theta_x - \theta_y|),$ $\begin{cases}\Delta_r ≥ r_{thr}, \\ \Delta_{\alpha} \leq \alpha_{thr}, \\ \Delta_{\theta} \leq \theta_{thr}.\end{cases}$

Здесь $x = (r_x, \alpha_x, \theta_x)$ и $y = (r_y, \alpha_y, \theta_y)$ - две сравниваемые минюции. Пороговые значения $r_{thr}$ , $\alpha_{thr}$ и $\theta_{thr}$ подбираются на основе обучающей выборки и фактически задают пространство допусков (tolerance box), который упоминался в разделе, посвящённом простановке задачи сравнения отпечатков.

Функция "MatchingWeight(x,y)" должна отражать степень совпадения сравниваемых минюций и . Логичным решением будет вычислить вес , который должна возвращать функция "MatchingWeight(x,y)" так:

$W = a*\Delta_r + b*\Delta_{\alpha} + c*\Delta_{\theta} + d,$

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

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

Выделим два таких условия:

пары могут образовывать только вершины (минюции) белого цвета. Это условие становится понятным, если вернуться к описанию алгоритма сравнения в предыдущем разделе. На шаге 4.2 мы перекрашиваем все вершины, которые образовали пары в результате работы алгоритма сравнения двух "K-plet";
пару не могут образовать вершины (минюции), для которых функция "IsEqual" возращает значение .

В случае приведённых выше условий в заносим штрафное значение FALSE_WEIGHT, равное максимально возможному значению , взятому со знаком минус. В случае приведённой выше формуле для расчёта , FALSE_WEIGHT .

Тогда модифицированная функция "LCS-Length" (назовём её "LCS-Length-Mod") будет иметь следующий вид:

LCS-Length-Mod(X, Y)

for i ← 0 to m
    do c[i,0] ← 0
for j ← 0 to n
    do c[0,j] ← 0
for i ← 1 to m
    do for j ← 1 to n
           do if "X[i-1] белая" and "Y[i-1] белая" and IsEqual(X[i-1], Y[j-1])
                 then c[i,j] ← c[i-1,j-1] + MatchingWeight(X[i-1], Y[j-1])
              else c[i,j] ← c[i-1,j-1] + FALSE_WEIGHT

              if c[i,j] > c[i-1,j] and c[i,j] > c[i,j-1]
                 then b[i,j] ← "↖"
              elseif c[i-1,j] > c[i,j-1] and c[i-1,j] > c[i,j]
                     then c[i,j] ← c[i-1,j]
                          b[i,j] ← "↑"
              else c[i,j] ← c[i,j-1]
                   b[i,j] ← "←"
return c,b

Вернёмся обратно к описанию алгоритма сравнения в предыдущем разделе. На шаге 4.1 мы последовательно вызываем функции "LCS-Length-Mod" и "Print-LCS", чтобы получить список пар смежных вершин как результат сравнения двух "K-plet". А на шаге 4.2 нам необходимо пройти по полученному списку пар смежных вершин с тем, чтобы положить найденные пары в стек для последующей обработки, а также посчитать число таких пар для последующего определения коэффициента подобия для сравниваемых отпечатков.

Чтобы исключить необходимость повторного прохода по списку пар смежных вершин на шаге 4.2 мы можем выполнить действия шага 4.2 в процессе построения списка пар смежных вершин в функции "Print-LCS". Модифицированная функция "Print-LCS" (назовём её "Print-LCS-Mod"):

Print-LCS-Mod(b, X, Y)

q ← 0
i ← m
j ← n
while i > 0 and j > 0
      do if b[i,j] = "↖"
            then if "X[i-1] белая" and "Y[i-1] белая"
                    then "помещаем в стек пару (X[i-1],Y[j-1])"
                         "перекрашиваем вершины X[i-1] и Y[j-1] в серый цвет"
                         q ← q+1
                 i ← i-1
                 j ← j-1
         elseif b[i,j] = "↑"
                then i ← i-1
         else j ← j-1
return q

В соответствии с выкладками, приведёнными в статье [5], cложность получившегося алгоритма равна , где - число минюций.

Работа построенного алгоритма сравнения для нашего примера:

Рисунок 9. Пример работы алгоритма сравнения.

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

Будем рассматривать в качестве начальной пары вершин все возможные пары вершин сравниваемых графов. В этом случае описанный выше алгоритм сравнения будет запускаться $m \times n$ раз, а в качестве результирующего коэффициента подобия будет выбран максимальный из получившихся коэффициентов подобия. Таким образом, сложность работы такого алгоритма составит .
Одним из условий успешного сравнения отпечатков пальцев является достаточная область перекрытия: на сравниваемых отпечатках должна присутствовать одна и та же область пальца, достаточная для достоверного сравнения площади. Так как мы сравниваем отпeчатки на основе выделяемых на них минюций, то сформированное выше условие превращается в условие нахождения достаточного количества минюций на отпечатках. При этом для того, чтобы результату сравнения отпечатков можно было бы доверять, необходимо найти не менее 12 пар совпадающих минюций на сравниваемых отпечатках. Это правило носит название "правила 12 точек" (12-point guideline) [1].

В случае, если отпечатки принадлежат одному и тому же пальцу и, в то же время, имеют общую область перекрытия, то сортировка списка минюций по возрастанию их взаимного расстояния от центра тяжести для сравниваемых отпечатков (шаги 1 и 2 алгоритма формирования промежуточного представления отпечатка) приведёт к тому, что в начале списка окажутся минюции, которые присутствуют на обоих отпечатках. Тогда мы можем взять первых минюций из двух списков и рассматривать их в качестве начальных пар (т.е. мы будем запускать алгоритм сравнения $с \times с$ раз). В этом случае сложность работы такого алгоритма будет такой: .

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

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

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

Сначала введём следующие структуры данных:

#define MAX_RAY_AMOUNT    8

typedef struct _ray_element
{
    int32_t neighbour_minutiae;
    int32_t rel_dist;
    int32_t rel_angle;
    int32_t rel_theta;
} RAY_ELEMENT, *P_RAY_ELEMENT;

typedef struct _minutiae_element
{
    uint32_t ray_amount;
    RAY_ELEMENT rays[MAX_RAY_AMOUNT];
} MINUTIA_ELEMENT, *P_MINUTIA_ELEMENT;

typedef struct _fp_feature_vector
{
    uint32_t minutiae_amount;
    MINUTIA_ELEMENT minutiae_data[1];
} FP_FEATURE_VECTOR, *P_FP_FEATURE_VECTOR;

Тогда мы можем выделить память под промежуточное представление отпечатка, на котором выделено minutiae_amount минюций:

P_FP_FEATURE_VECTOR p_feature_vector =
      (P_FP_FEATURE_VECTOR)calloc(sizeof(FP_FEATURE_VECTOR) + 
                                  (minutiae_amount-1) * sizeof(MINUTIA_ELEMENT), 
                                  sizeof(uint8_t));

Следующие массивы будут необходимы для работы алгоритма сравнения:

#define MAX_STAR_MINUTIAE_AMOUNT    50
#define LCS_MAX_RAY_SIZE            (MAX_RAY_AMOUNT+1)
#define LCS_MAX_RAY_AMOUNT          (LCS_MAX_RAY_SIZE*LCS_MAX_RAY_SIZE)

int32_t LeftColorArray[MAX_STAR_MINUTIAE_AMOUNT];
int32_t RightColorArray[MAX_STAR_MINUTIAE_AMOUNT];
int32_t LeftStack[MAX_STAR_MINUTIAE_AMOUNT];
int32_t RightStack[MAX_STAR_MINUTIAE_AMOUNT];

int32_t CostArray[LCS_MAX_RAY_AMOUNT];
int32_t DirArray[LCS_MAX_RAY_AMOUNT];

Здесь мы предполагаем, что максимальное число минюций, выделенных на отпечатке, не может превышать 50.

Функция, реализующая алгоритм сравнения:

// matching parameters
#define MIN_MINUTIAE_PAIR_THR 12

#define TRUE_WEIGHT       16
#define FALSE_WEIGHT     -16
   
#define STAR_DIST_THR    12
#define STAR_ALPHA_THR   20
#define STAR_THETA_THR   30

#define STAR_DIST_COEFF    2
#define STAR_ALPHA_COEFF   4
#define STAR_THETA_COEFF   6

// constants of DFS algorithm
#define WHITE_COLOR      0
#define GRAY_COLOR       1
#define BLACK_COLOR      2

#define STACK_EMPTY      (-1)

// for LCS algorithm
#define LEFT_TOP_DIR     0
#define LEFT_DIR         1
#define UP_DIR           2

// for search space dimension
#define SEARCH_SPACE_DIM    15

double PerformMatching(P_MATCHER_HANDLE pHandle, P_FP_FEATURE_VECTOR pLeftFV, P_FP_FEATURE_VECTOR pRightFV)
{
    int top_of_stack;
    int index1, index2;
    int index3, index4;
    int max_score, cur_score;
    int cur_template_root_minutiae,
        cur_input_root_minutiae;
    P_MINUTIA_ELEMENT pTemplateMinutiae = NULL;
    P_MINUTIA_ELEMENT pInputMinutiae    = NULL;

    // LCS algorithm variables
    int left_cost, up_cost, left_up_cost;
    int delta_dist;
    int delta_alpha;
    int delta_theta;

    // full search
    max_score = 0;

    memset(CostArray, 0, LCS_MAX_RAY_AMOUNT*sizeof(int32_t));

    for (index1 = 0; index1 < (pLeftFV->minutiae_amount < SEARCH_SPACE_DIM ? pLeftFV->minutiae_amount : SEARCH_SPACE_DIM); ++index1)
    {
        for (index2 = 0; index2 < (pRightFV->minutiae_amount < SEARCH_SPACE_DIM ? pRightFV->minutiae_amount : SEARCH_SPACE_DIM); ++index2)
        {
            // DFS algorithm
            memset((void*)LeftColorArray,  WHITE_COLOR, MAX_STAR_MINUTIAE_AMOUNT*sizeof(int32_t));
            memset((void*)RightColorArray, WHITE_COLOR, MAX_STAR_MINUTIAE_AMOUNT*sizeof(int32_t));

            LeftColorArray[index1]  = GRAY_COLOR;
            RightColorArray[index2] = GRAY_COLOR;

            top_of_stack = 0;

            LeftStack[top_of_stack] = index1;
            RightStack[top_of_stack]    = index2;

            cur_score = 1;

            while (STACK_EMPTY < top_of_stack)
            {
                cur_template_root_minutiae = LeftStack[top_of_stack];
                cur_input_root_minutiae    = RightStack[top_of_stack];
                --top_of_stack;

                // LCS algorithm
                pTemplateMinutiae = &pLeftFV->minutiae_data[cur_template_root_minutiae];
                pInputMinutiae    = &pRightFV->minutiae_data[cur_input_root_minutiae];

                // LCS-LENGTH
                for (index3 = 1; index3 < pTemplateMinutiae ->ray_amount + 1; ++index3)
                {
                    for (index4 = 1; index4 < pInputMinutiae ->ray_amount + 1; ++index4)
                    {
                        up_cost   = CostArray[LCS_MAX_RAY_SIZE*(index3 - 1) + index4];
                        left_cost = CostArray[LCS_MAX_RAY_SIZE*index3 + index4 - 1];

                        if ( LeftColorArray[pTemplateMinutiae->rays[index3 - 1].neighbour_minutiae] != WHITE_COLOR ||
                             RightColorArray[pInputMinutiae->rays[index4 - 1].neighbour_minutiae]   != WHITE_COLOR )
                            left_up_cost = CostArray[LCS_MAX_RAY_SIZE*(index3 - 1) + index4 - 1] + FALSE_WEIGHT;
                        else
                        {
                            delta_dist  = abs(pTemplateMinutiae->rays[index3 - 1].rel_dist   - pInputMinutiae->rays[index4 - 1].rel_dist);
                            delta_alpha =  abs(pTemplateMinutiae->rays[index3 - 1].rel_angle - pInputMinutiae->rays[index4 - 1].rel_angle);
                            delta_alpha = delta_alpha > 180 ? 360 - delta_alpha : delta_alpha;
                            delta_theta = abs(pTemplateMinutiae->rays[index3 - 1].rel_theta  - pInputMinutiae->rays[index4 - 1].rel_theta );
                            delta_theta = delta_theta > 180 ? 360 - delta_theta : delta_theta;

                            if ( delta_dist <= STAR_DIST_THR && delta_alpha <= STAR_ALPHA_THR && delta_theta <= STAR_THETA_THR )
                                left_up_cost = CostArray[LCS_MAX_RAY_SIZE*(index3 - 1) + index4 - 1]   +
                                               TRUE_WEIGHT - delta_dist/STAR_DIST_COEFF - delta_alpha/STAR_ALPHA_COEFF - delta_theta/STAR_THETA_COEFF;
                            else
                                left_up_cost = CostArray[LCS_MAX_RAY_SIZE*(index3 - 1) + index4 - 1] + FALSE_WEIGHT;
                        }

                        if ( left_up_cost > up_cost && left_up_cost > left_cost )
                        {
                            CostArray[LCS_MAX_RAY_SIZE*index3 + index4] = left_up_cost;
                            DirArray[LCS_MAX_RAY_SIZE*index3 + index4]  = LEFT_TOP_DIR;
                        }
                        else
                        {
                            if ( up_cost > left_cost && up_cost > left_up_cost )
                            {
                                CostArray[LCS_MAX_RAY_SIZE*index3 + index4] = up_cost;
                                DirArray[LCS_MAX_RAY_SIZE*index3 + index4]  = UP_DIR;
                            }
                            else
                            {
                                CostArray[LCS_MAX_RAY_SIZE*index3 + index4] = left_cost;
                                DirArray[LCS_MAX_RAY_SIZE*index3 + index4]  = LEFT_DIR;
                            }
                         }
                     }
                 }
 
                 // PRINT-LCS
                 --index3;
                 --index4;

                 while ( index3 > 0 && index4 > 0)
                 {
                     if ( LEFT_TOP_DIR == DirArray[LCS_MAX_RAY_SIZE*index3 + index4] )
                     {
                         // DFS algorithm part II
                         if (WHITE_COLOR == LeftColorArray[pTemplateMinutiae->rays[index3 - 1].neighbour_minutiae] &&
                             WHITE_COLOR == RightColorArray[pInputMinutiae->rays[index4 - 1].neighbour_minutiae] )
                         {
                             ++top_of_stack;
                             LeftStack[top_of_stack] = pTemplateMinutiae->rays[index3 - 1].neighbour_minutiae;
                             RightStack[top_of_stack]    = pInputMinutiae->rays[index4 - 1].neighbour_minutiae;
                             ++cur_score;
                         }

                         LeftColorArray[pTemplateMinutiae ->rays[index3 - 1].neighbour_minutiae] = GRAY_COLOR;
                         RightColorArray[pInputMinutiae ->rays[index4 - 1].neighbour_minutiae]   = GRAY_COLOR;

                         --index3;
                         --index4;
                         continue;
                     }

                     if ( UP_DIR == DirArray[LCS_MAX_RAY_SIZE*index3 + index4] )
                     {
                         --index3;
                         continue;
                     }

                     if ( LEFT_DIR == DirArray[LCS_MAX_RAY_SIZE*index3 + index4] )
                     {
                         --index4;
                         continue;
                     }
                 }

                 // DFS algorithm part III
                 LeftColorArray[cur_template_root_minutiae] = BLACK_COLOR;
                 RightColorArray[cur_input_root_minutiae]   = BLACK_COLOR;
            }
            // end of DFS algorithm

            if ( cur_score > max_score )
                max_score = cur_score;
        }
     }

     // calculate matching score
     if ( max_score > MIN_MINUTIAE_PAIR_THR )
         return (double)(max_score*max_score)/(pLeftFV->minutiae_amount*pRightFV->minutiae_amount);
     else
         return 0.0;
}

Литература

1. D. Maio, D. Maltoni, A. K. Jain, and J. Feng. Handbook of Fingerprint Recognition. Springer Verlag, 2020.

2. Fingerprint Verification Competition. http://bias.csr.unibo.it/fvc2000/download.asp; http://bias.csr.unibo.it/fvc2002/download.asp

3. K. Ko, W. J. Salamon. NIST Biometric Image Software (NBIS). https://www.nist.gov/services-resources/software/nist-biometric-image-software-nbis - 2015.

4. https://nigos.nist.gov/nist/nbis/nbis_v5_0_0.zip

5. S. Chikkerur, A.N. Cartwright, and V. Govindaraju. K-plet and Coupled BFS: A Graph Based Fingerprint Representation and Matching Algorithm. In: Advances in Biometrics. ICB 2006. Lecture Notes in Computer Science, vol 3832. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11608288_42 - 2015.

6. Скиена, С.С. Алгоритмы. Руководство по разработке. - 3-е изд.: Пер. с англ. - СПб.: БХВ-Петербург, 2022.

7. Кормен, Т., Лейзерсон, Ч., Ривест, Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000.

8. Реализуем алгоритм поиска в глубину. Перевод Ксении Мосеенковой (kmoseenk). Блог компании OTUS. https://habr.com/ru/companies/otus/articles/660725/ - 2022.

9. Нахождение максимальной общей подпоследовательности. Автор: hamst. https://habr.com/ru/articles/142825/ - 2012.

Комментарии (2)

DoomeR18G
12.09.2024 04:27
#27280676
+1
Первую треть было интересно, потом просто формулами, которые мне не особо нужны закидал. Ну текст полезен однозначно, тому кто начинает работать с чем-то подобным.

Ilya_antheus
12.09.2024 04:27
#27285318
+2
Пример кода побудил меня сразу проверить точность алгоритма на реальных данных. База 15000 пар и 15000 без пары, экстрактор neuro, распеределение по nfiq почти как у базы для теста minex3 от NIST. Используются первые 50 минутий. Если использовать 120 минутий получается чуть оучше, но очень далеко от заявленной в pdf точности.

Сравнение алгоритмов appm и kplet

Алгоритм сравнения отпечатков пальцев: комбинация классических алгоритмов +17

Комментарии (2)

DoomeR18G

Ilya_antheus