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

D. Maltoni, D. Maio, A. K. Jain, S. Prabhakar.

Выдержки из раздела 4 "Сопоставление отпечатков пальцев" из книги «Handbook of fingerprint recognition».

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

Пусть T и I два изображения отпечатка пальца, соответствующие шаблонному и введенному изображениям соответственно. Тогда их разница- это сумма квадрата разности (SSD) между значениями яркости соответствующих пикселей.

SSD(T,I) = ||T-I||² = (T-I)^T*(T-I) = ||T||² + ||I||² - 2*T^T*I        (1)

где надстрочный индекс Т означает транспонирование вектора. Если термы ||T||² и ||I||² являются константами, то разница между двумя изображениями минимизируется, когда взаимная корреляция (СС) максимизируется:

CC(T,I)= T^T*I              (2)

CC(T,I) появляется как третий терм в уравнении 1. Взаимная корреляция (простая корреляция) – мера сходства изображений. Вследствие перемещения и ротации, которые неизбежно характеризуют два различных изображения отпечатка с одного пальца, их сходство не может быть легко вычислено путем наложения изображений T и I друг на друга и применением уравненя 2.

Пусть I⁽⁾ представляет ротацию входного изображения I под углом вокруг источника, в роли которого обычно выступает центр изображения, и сдвигается (перемещается) на x, y в направлении x и y соответственно. В этом случае сходство между двумя изображениями отпечатков пальцев I и T может быть рассчитано как:

S(T,I) = maxCC(T, I⁽⁾)            (3)

Непосредственное применение уравнения 3 редко приводит к приемлемым результатам по нижеприведенным причинам:

Прямое использование уравнения 3 обладает большой вычислительной сложностью. Например, рассмотрим два изображения размерности 400х400 пикселей, вычисление взаимной корреляции (уравнение 2) для отдельного значения () требует 16000 операций умножения и 16000 операций суммирования (при игнорировании граничного эффекта).Если оба значения x, y будут изменятся с шагом в 1 пиксель в пределах диапазона [-200;200] и - с шагом в 1⁰ в пределах диапазона [-30⁰;30⁰] мы должны будем вычислить 401х401х61 взаимных корреляций, что составляет примерно 1569 биллионов операций умножения и операций суммирования (боле одного часа вычислений на компьютере, выполняющем 500 MIPS (миллионов команд в секунду)).

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

Корреляционная теорема (Gonzales , Woods, 1992) гласит, что вычисление корреляции в пространственной области (оператор ) эквивалент выполнения поточечного умножения в распределении Фурье, в частности:

T I = F^-1(F^*(T) x F(I))            (4)

где F(.) - преобразование Фурье вышеуказанного изображения;

"*" - комплексное сопряжение;

"x" - поточечное умножение двух векторов.

Результатом уравнения 4 является корреляционное изображение, зачение которого в пикселе [x,y] соответствует корреляции между T и I, когда смещение x = x и y = y.