RESEARCH OF THE RECOGNITION PROCESS AND COMPARISON OF FINGER PRINTS

Full Text

Биометрические методы аутентификации и идентификации сегодня широко распространены во многих сферах жизни человека. Они обладают рядом преимуществ и недостатков по сравнению с традиционными методами, поэтому важно перед их внедрением всё продумать. Например, в отличии от обычных паролей биометрические данные невозможно потерять или забыть, однако для их считывания требуется дополнительная специальная аппаратура. Но на их считывании не заканчивается всё, их также необходимо преобразовать в вид, в котором их удобно представить в памяти компьютера для сравнения с эталоном или же для поиска по базе данных. К настоящему времени разработано большое число алгоритмов сравнения отпечатков пальцев, которые условно можно разбить на три класса [1]: корреляционное сравнение (вычисление взаимной корреляции двух изображений отпечатка [2]); сравнение минуций (точек обрыва и бифуркаций папиллярных линий); сравнение потоков папиллярных линий и папиллярных узоров [3]. Предлагаются и новые методы сравнения на основе вышеприведённых. Например, можно представить отпечаток как граф, вершины которого представляют собой минуции отпечатка, и свести решение задачи к классической задаче на графах [4], также можно поставить и совсем новую задачу [5]. Также предлагается разложение поля направлений отпечатка на полиномы Чебышева и дальнейшее вычисление хэшей на их основе [6]. Однако до сих пор одним из самых быстрых и надёжных считается алгоритм распознавания по особым точкам, рассмотренный в нашей статье [7]. Описание алгоритма Улучшение изображения. Построение поля направлений изображений, с использованием градиентов, вычисленных с помощью оператора Собеля. Вычисление поля частот изображения. Вычисление всех необходимых ядер фильтра Габора для данного изображения. Свёртка ядер с изображением. Подготовка изображения к работе алгоритма сравнения. Бинаризация изображения. Скелетизация изображения алгоритмом Зонга-Суня. Сравнение. Поиск особых точек. Фильтрация особых точек. Сравнение особых точек. Вынесение решения о совпадении или несовпадении отпечатков. Фильтр Габора - линейный электронный фильтр, импульсная переходная характеристика которого определяется в виде гармонической функции, помноженной на гауссиан. При цифровой обработке изображений этот фильтр применяется для распознавания границ объектов. Фильтр Габора эффективен при обработке изображений со структурной избыточностью, имеющих квазипериодическую структуру. Как раз таковыми и являются интересующие нас дактилоскопические изображения. Фильтр Габора является матричным фильтром. Такие фильтры основаны на работе с матрицей свёртки, которая также называется ядром фильтра. Таким образом, в фильтре Габора основным моментом, интересующим нас, является ядро фильтра. Для построения двумерного фильтра Габора применяется формула [1, c. 136]: G(x,y)=exp⁡(-1/2 [(x_θ^2)/σ^2 + (y_θ^2)/σ^2 ])cos⁡(2πfx), x_φ=xcos(φ)+ysin(φ), y_φ=-xsin(φ)+ycos(φ), где: σ - стандартные отклонения гауссова ядра, определяющие растянутость фильтра. f - частотная модуляция фильтра, θ - пространственная направленность фильтра, определяющая его ориентацию относительно главных осей. Если отбросить синусоидальную составляющую функции в фильтре Габора, он выродится в фильтр Гауссова размытия. Поэтому очевидно, что эти два фильтра имеют практически одинаковый алгоритм применения, различающийся в некоторых деталях. Из формулы Габора видно, что фильтр зависит от частоты и направления квазипериодической структуры изображения. Поэтому перед применением фильтра необходимо построить частотное и ориентационное поля для текущего изображения. Обычно для упрощения задачи рассчитывается средняя частота изображения, которая считается неизменной в каждой точке. Построение поля направлений изображения Для осуществления работы фильтра необходимо построить поле направлений, которое будет определять направление папиллярных линий в каждой точке изображения. Для этого используется оператор Собеля, который представляет собой двумерную свёртку окрестности точки (рис. 1) для нахождения градиента (по значениям интенсивности) со следующими матрицами (рис. 2): Рис. 1. Окрестность точки Рис. 2. Маски оператора Собеля Рассмотренные выше маски применяются для получения составляющих градиента G_x и G_y. Для вычисления величины градиента эти составляющие необходимо использовать совместно и вычислять по формулам [1, с. 104]: G_x=(z_7+〖2z〗_8+z_9 )-(z_1+〖2z〗_2+z_3 ), G_y=(z_3+〖2z〗_6+z_9 )-(z_1+〖2z〗_5+z_7 ), θ_ij=90°+1/2 atan2(2G_xy,G_xx-G_yy ), G_xy=∑_(h=-8)^8▒∑_(k=-8)^8▒〖∇_x (x_i+h,y_j+k)∙∇_y (x_i+h,y_j+k),〗 G_xx=∑_(h=-8)^8▒∑_(k=-8)^8▒〖〖∇_x (x_i+h,y_j+k)〗^2,〗 G_yy=∑_(h=-8)^8▒∑_(k=-8)^8▒〖〖∇_y (x_i+h,y_j+k)〗^2.〗 где: θ_ij - пространственная направленность фильтра в точке [i,j], ∇_x (x,y) - компонента x градиента в точке [x,y], ∇_y (x,y) - компонента y градиента в точке [x,y]. Касс и Виткин [1, c. 105] определяют когерентность как норму суммы векторов ориентации, делённых на сумму их индивидуальных норм; этот скаляр всегда лежит в [0, 1]: его значение равно 1, когда все ориентации параллельны друг другу (максимальная когерентность) и 0, если они указывают в противоположных направлениях (минимальная когерентность): r_ij=coherence(θ_ij )=√(〖(G_xx-G_yy)〗^2+〖4G〗_xy^2 )/(G_xx+G_yy ). Посчитанная таким образом карта когерентностей может послужить основой специальной маски, определяющей части изображения, в которых есть интересующие нас структуры, и помогающей отбросить те части, где их нет. Использование такой маски является очень удобным, так как вектора поля направления на краях изображения испытывают резкие изменения в своём направлении, которые могут негативно повлиять на работу фильтра (рис. 3). Построение частотного поля изображения Для определения частоты появления гребней на отпечатке пальца можно использовать следующий алгоритм (рис. 4) [1, c. 114]. В точку [x, y] помещается ориентированное по полю направлений в данной точке окно. Затем собираются значения, усреднённые по короткой стороне этого окна. Итогом является двумерный массив чисел. Частота определяется как число, обратное среднему расстоянию между максимумами в массиве, полученном в прошлом шаге. Результаты экспериментов На рис. 5 представлено исходное изображение, использовавшееся для создания иллюстраций в последующих разделах. В процессе исследования были обработаны и другие изображения, которые также подтверждают выводы, полученные в данной работе (рис. 6). Из полученных результатов можно сделать вывод, что оптимальным является значение отклонения равное 4. В дальнейшем именно такое значение и используется при применении фильтра (рис. 7). Рис. 3. Поле направлений отпечатка и пример наложения маски Рис. 4. Наложение ориентированного окна и гистограмма значений [1, c. 114] Рис. 5. Исходное изображение Рис. 6. Обработанные изображения с параметром отклонения равным 3, 4, 5, 6 Рис. 7. Обработанные изображения с параметром частоты равным 0.10, 0.125, 0.15, 0.20 Полученные результаты свидетельствуют о том, что искомое значение частоты колеблется около 0,11. Это значение помогло в настройке крайних границ значения частоты внутри одного изображения. Вариация порогового значения когерентности маски Для данного эксперимента было выбрано другое исходное изображение, обладающее обширной незаполненной областью вокруг отпечатка, для наиболее удобной оценки работы алгоритма (рис. 8). Видно, что пороговое значение 0 обеспечивает приемлемые результаты, которые также улучшают качество обработки изображения фильтра в областях пограничных пустым. При значении 0,1 уже перестают учитываться области, содержащие полезную информацию. Вариация областей усреднения В данном эксперименте предполагается вариация областей усреднения градиентов, необходимых для построения поля направлений. Полученные результаты свидетельствуют о том, что оптимальным является размер области усреднения градиентов равный 17×17, дальнейшее увеличение влечёт бессмысленную трату ресурсов без каких-либо значимых преимуществ и даже, напротив, вносит ошибки (рис. 9). Сравнение отпечатков Для начала надо разобраться, из чего состоит отпечаток пальца и что является его особыми точками. Отпечаток пальца состоит из хребтов и впадин, которые образуют папиллярный рисунок (рис. 10). Отпечаток имеет два вида признаков: глобальные и локальные. Глобальные признаки описывают общее положение папиллярных линий. Глобальные признаки обуславливают различные узоры отпечатков (рис. 11). Локальные признаки отпечатков пальцев описывают расположение линий в окрестности минуций. Минуция - такая точка отпечатка пальца, где папиллярная линия обрывается или разделяется на две. Минуции и являются особыми точками. Из этих двух типов могут быть составлены более сложные виды минуций (рис. 12). Особые точки на отпечатках пальца, которые относятся к глобальным признакам, бывают двух видов: точка ядра и точка дельты. Ядро - точка отпечатка пальца, которую огибает максимальное количество папиллярных линий (рис. 13 а). Рис. 8. Исходное изображение в данном эксперименте и исходное изображение с масками, наложенными на него при пороговых значениях когерентности 0, 0,1, 0,5 Рис. 9. Обработанные изображение с областью усреднения градиентов для поля направлений 3×3, 7×7, 13×13, 17×17, 31×31 Рис. 10. Отпечаток пальца с отмеченными папиллярными линиями [1, с. 97] Рис. 11. Различные узоры отпечатков пальцев [1, с. 98] Рис. 12. Основные виды минуций [1, с. 99] а б Рис. 13. Особые точки на отпечатках пальца: а - ядро, б - дельта Дельта - точка отпечатка пальца, вокруг которой папиллярные линии расходятся в трёх разных направлениях (рис. 13 б). Локальные признаки, в отличие от глобальных, у каждого человека являются уникальными. Именно поэтому для распознавания отпечатков пальцев сейчас повсеместно используется метод распознавания по минуциям. В нём сравнивается локальная структура отпечатка и даётся точный ответ, совпадают два отпечатка или нет. Метод имеет ряд значительных недостатков, таких как трудоёмкость, чувствительность к локальному растяжению и плохая масштабируемость. Поиск ядра Для нахождения точки начала координат, относительно которой будет происходить сравнение отпечатков пальцев, воспользуемся индексом Пуанкаре. Для кривой вокруг точки ядра индекс Пуанкаре принимает значение 2π или π(-π) для точки дельты, во всех остальных точ- ках - 0. Для нахождения индекса Пуанкаре поле направлений удваивается и после возводится в квадрат, вычисляется градиент от поля направлений, удвоенного и возведённого в квадрат. Далее находятся частные производные по x и y от значений предыдущего шага, их разность и представляет собой индекс Пуанкаре в данной точке. Точка, в которой индекс будет максимален, является ядром (первый способ). Также индекс Пуанкаре для конкретной точки можно вычислить другим способом как сумму разностей значений поля направления соседних точек в окрестности данной точки (рис. 14). Скелетизация Для скелетизации отфильтрованного изображения отпечатка пальца используется алгоритм Зонга-Суня (рис. 15 а и б). Скелетизация проходит в две подитерации: I. Для точки чёрного цвета проверяются условия, но основе которых принимается решение закрасить чёрную точку в белый цвет. Условия: количество чёрных точек в окрестности данной точки ≥ 2 и ≤ 6; если представить окрестность точки как последовательность 1 и 0, где 1 - чёрная точка, 0 - белая, то в данной последовательности должен содержаться только один переход 0-1-0; хотя бы одна из точек z_2, z_6, z_8 (рис. 1) равна 0; хотя бы одна из точек z_6, z_8, z_4 (рис. 1) равна 0; II. Для точки чёрного цвета проверяются условия, но основе которых принимается решение закрасить чёрную точку в белый цвет. Рис. 14. Окрестность точки для нахождения индекса Пуанкаре [1, с. 121] а б Рис. 15. Отпечаток до (а) и после (б) скелетизации и обработки фильтрами соответственно Условия: количество чёрных точек в окрестности данной точки ≥ 2 и ≤ 6; если представить окрестность точки, как последовательность 1 и 0, где 1 -чёрная точка, 0 - белая, то в данной последовательности должен содержаться только один переход 0-1-0; хотя бы одна из точек z_2, z_4, z_6 (рис. 1) равна 0; хотя бы одна из точек z_2, z_4, z_8 (рис. 1) равна 0. Данные подитерации выполняются для каждой точки изображения опечатка пальца до тех пор, пока изображение не перестанет изменяться. Поиск особых точек Для нахождения особых точек (минуций) определяется количество 1 и 0 в окрестности точки (рис. 1), где 1 соответствует черной точке, а 0- белой. Если количество чёрных точек в окрестности равно 1, то это точка - «конец» хребта. Если количество чёрных точек в окрестности равно 3 и количество переходов 0-1-0 при представлении окрестности в виде последовательности равно 3, то это точка «раздвоение». Если количество чёрных точек в окрестности отлично от 1 и 3, то эта точка не является особой (рис. 16). Фильтрация особых точек На практике получается, что большинство распознанных особых точек является шумом, который ухудшает качество работы программы. Для устранения этой проблемы в окрестности каждой особой точки находятся другие особые точки, удаление лишних производится по принципу, указанному на рис. 17. Сравнение особых точек Сравнение особых точек двух отпечатков пальцев производится посредством сдвига и поворота особых точек одного из отпечатков. Рис. 16. Примеры видов окрестностей точки Рис. 17. Возможные «ложные» расположения особых точек и соответствующие им разрешения проблемы [1, с. 158] Для каждой особой точки новые координаты находятся с помощью умножения вектора текущих координат на матрицу поворота и с помощью последующего сдвига: Для каждого из значений угла и значений сдвига производится сравнение соответствующих точек с допустимыми погрешностями (r_0 и θ_0), которые определяются экспериментальным образом: На каждой i-ой итерации сдвига и поворота находится число совпавших точек k_i и ищется максимальное число совпадений k. Оценка соответствия двух отпечатков пальцев друг другу производится по следующей формуле: score=k/((n+m)/2), где n и m - общее количество особых точек первого и второго отпечатка соответственно. Исследование алгоритма Так как алгоритм сравнения отпечатков пальцев, представленный в данной программе, содержит множество констант, то необходимо экспериментально установить, с какими значениями этих констант работа алгоритма будет более эффективной и точной. В качестве эксперимента приводились сравнения отпечатков пальцев заведомо одинаковых, с разными параметрами, и находился средний процент совпадений отпечатков. Для начала проведём исследование для радиуса фильтрации особых точек (рис. 18). Так как от радиуса фильтрации очень сильно зависит время сравнения, то константа была выбрана с учётом и этого параметра. Радиус фильтрации особых точек равен семи, поскольку при меньших значениях данного параметра сильно ухудшается показатель быстродействия алгоритма, а при больших - уменьшается точность. Для допустимой погрешности по сдвигу при сравнении особых точек процент совпадения изменяется по следующему графику (рис. 19). Из-за того, что в качестве погрешности по сдвигу можно взять бесконечно большое число, то выберем то, после которого изменения стали незначительными. Допустимая погрешность по сдвигу равна 20. Для допустимой погрешности по направлению при сравнении особых точек зависимость определяется следующим графиком (рис. 20). Поскольку в качестве погрешности по сдвигу можно взять число до 360-ти градусов, то выберем то, после которого изменения стали незначительными. Допустимая погрешность по сдвигу в этом случае равна 15-ти. При работе алгоритма сравнения с выбранными параметрами средний процент совпадения различных реализаций одного и того же отпечатка составляет 64 %. Рис. 18. Точность совпадения алгоритма сравнения отпечатков пальцев в зависимости от радиуса фильтрации особых точек Рис. 19. Точность совпадения алгоритма сравнения отпечатков пальцев в зависимости от допустимой погрешности по сдвигу Рис. 20. Точность совпадения алгоритма сравнения отпечатков пальцев в зависимости от допустимой погрешности по направлению Работоспособность данного алгоритма была проверена на базе отпечатков пальцев. Точность сравнения данного алгоритма составила 81,25 %, при этом не было замечено ложных срабатываний, когда два различных отпечатка принимались за одинаковые. Заключение Итогом данного исследования является полученные в результате экспериментов различные значения параметров фильтра и алгоритма. Все их значения приведены выше. При использовании данных параметров можно оптимальным образом удалять посторонние шумы с дактилоскопических изображений и восстанавливать квазипериодическую структуру, если она была утеряна. Результат такой обработки можно использовать для сравнения отпечатков в задачах биометрии и дактилоскопии. Важно также отметить то, что качество фильтрации можно и увеличить, например, посчитав значение частоты для каждой точки изображения, и другими способами, однако это увеличит алгоритмическую сложность во много раз. Поэтому наиболее разумно использовать значения, полученные эмпирически в эксперименте. Таким образом, результаты исследования можно применить как для дальнейшего более глубокого исследования фильтра и его последующего улучшения, так и для использования в качестве промежуточного звена для алгоритмов распознавания и сравнения отпечатков пальцев. Точность алгоритма сравнения во многом зависит от качества обработки изначального изображения отпечатка пальца, которая позволяет убрать лишние шумы и акцентировать всё внимание непосредственно на особых точках отпечатка, а не на особенностях конкретного изображения. Алгоритм сравнения наборов особых точек относительно ядра отпечатка позволяет учитывать, как линейные, так и нелинейные искажения изображения. Конечно, точность сравнения можно улучшить, подобрав соответствующие входные параметры, но это отрицательно скажется на скорости работы алгоритма, поэтому эмпирическим путём были подобраны такие параметры, значения которых обеспечивает оптимальное соотношение точности и быстродействия. В итоге, результаты исследования представленного алгоритма могут понадобиться для дальнейшей оптимизации его работы при реализации конкретной задачи, выбора таких входных параметров, которые обеспечат допустимые погрешности и требуемую скорость работы. А использование представленного способа фильтрации позволит значительно улучшить эффективность распознавания и сравнения отпечатков пальцев.

About the authors

Daniil Aleksandrovich Kozlov

Samara University

Email: djoade100@gmail.com
Samara, Russia

Dmitry Denisovich Karnaukhov

Samara University

Email: darzy1997@gmail.com
Samara, Russia

References

Supplementary files