Обнаружение особых точек в изображении отпечатка пальца

    Авторы: Weiwei Zhang, Yangsheng Wang

    Автор перевода: Лебедев К.Е.

    Источник: http://www.aprs.org.au/accv2002/accv2002_proceedings/Zhang793.pdf

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

Идентификация на основе отпечатков пальцев используется уже давно. Из-за своей уникальности, сегодня, отпечатки пальцев, наиболее широко используемые биометрические признаки. Большинство автоматизированных систем идентификации отпечатков пальцев используют сопоставление отпечатков пальцев по особым точкам. Алгоритмы сопоставления отпечатков пальцев делятся на две группы (согласно зависимости от точки ядра): алгоритмы, которые основываются на использовании точки ядра, и которые не основываются. Алгоритмы, которые основываются на использовании точки ядра, зависят от того, как точка ядра выравнивает вектор признаков. Вторая группа алгоритмов зависит от другого метода выравнивания, такого как локальная структура. Следует отметить, что первая группа алгоритмов более эффективна, чем вторая. Но вместе с этим в первой группе имеется проблема – как точно обнаружить точку ядра.

Существует множество алгоритмов, которые решают эту проблему. В [1] V.S.Srinivasan представляет метод обнаружения особых точек, использующий гистограмму ориентаций, которая устойчива перед шумами, но точность результата мала. В [2] Marius Tico представляет волновой метод, использующий несколько разрешений, который может обнаружить особую точку в области размером 2х2 пикселя. Тем не менее, из-за использования волновой декомпозиции и распределения поля направления в пикселях, метод требовательный ко времени исполнения, и не подходит для приложений реального времени. В [3] Asker M. Baze представляет алгоритм обнаружения особой точки, основанный на поле направления высокого разрешения, который сначала рассчитывает поле направления высокого разрешения, а затем находит особую точку используя индекс Пуанкаре. Тем не менее, из-за расчета поля направления высокого разрешения, эффективность алгоритма достаточно низкая. В [4] Jain представляет метод локализации особой точки, основанный на индексе Пуанкаре. Этот алгоритм позволяет лишь обнаружить маленькое окно, которой содержит особую точку. Более того – большинство из алгоритмов обнаружения особых точек, описанных выше, могут эффективно обнаружить особую точку, когда качество изображения хорошее. А когда качество изображения плохое, эффективность алгоритма резко снижается.

Некоторые алгоритмы также включают шаг пост-обработки, для того чтобы удалить ложные особые точки, которые они обнаружили. В этой статье мы представляем новый алгоритм обнаружения особых точек, который может точно локализовать особые точки и не нуждается в шаге пост-обработки. Главным образом он состоит из двух шагов: первый – используя поле направления низкого разрешения, находим приблизительную область в которой находится особая точка; второй – используя поле направления высокого разрешения найденной на первом шаге области, точно локализовать особую точку. Оценка поля направления представлена в разделе 1, метод обнаружения особой точки представлен в разделе 2. И в разделе 3 представлены результаты эксперимента. Затем представлены выводы и планы на будущее.

Метод оценки поля направления представлен Jain в [4]. Алгоритм в основном состоит из четырех шагов:
1. разделить изображение на блоки размером W*W;
2. рассчитать значение градиента в каждом блоке;
3. Используя формулы (1), (2) и (3) найти оценки каждого блока. W – ширина блока.

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

Рисунок 1 – Поле направления возле особой точки

Как уже говорилось выше, мы нашли оценку поля направления на уровне блоков, по этой причине выбор ширины блока, является ключевым моментом. Если разделение производится на слишком маленькие блоки, то точность локализации высокая, но велико воздействие шумов, и эффективность алгоритма очень низкая. Если размер блока слишком большой, алгоритм устойчив перед шумами, но точность локализации низкая. По этой причине мы выбрали оптимальное соотношение между точностью и эффективностью алгоритма. Сначала мы использовали поле направления с низким разрешением, чтобы грубо локализовать область, в которой находится особая точка. Затем для точного определения положения точки, мы произвели пересчет, используя поле направления высокого разрешения найденной на первом шаге области. Ввиду того, что для обнаружения точки ядра и точки дельты, используется один и тот же метод, здесь мы лишь описываем, как локализовать точку ядра. Этот же метод может быть использован для обнаружения точки дельты.

2.1 Обнаружение точки ядра с помощью поля направления низкого разрешения

В [2] Marius Tico представляет алгоритм, который может обнаружить особую точку. Алгоритм рассчитывает направление рисунка на уровне пикселей, и затем выполняет расчет поля направления. Тем не менее эффективность и надежность алгоритма не очень хорошие. Здесь мы используем этот метод чтобы бегло локализовать область с особой точкой. Ниже описаны главные шаги алгоритма:
1. Рассчитать x и y градиенты ориентации (используя формулу 4).

2. Согласно теоремы Грина мы используем поверхностный интеграл чтобы заменить ближайшие интегральные линии (используя формулу 5).

Где А – интегральная область и ∂А – контур А. В алгоритме Asker M. Bazen индекс Пуанкаре рассчитывается при условиях, что интеграл около точки ядра равен π, около точки дельты –π и интеграл в остальной области рисунка равен 0. Следовательно, мы можем обнаружить область, которая, возможно, включает особую точку.

Экспериментально мы обнаружили, что индекс Пуанкаре не очень эффективен в нашей ситуации, поэтому мы модифицировали алгоритм. Вместо расчета индекса Пуанкаре, мы рассчитываем значение изменения градиента изображения и считаем точку, в которой значение изменения градиента максимальное – особой точкой. Измененный 2-й шаг алгоритма осуществляется по формуле 6:

Точка для которой значение М максимально – является особой точкой. В [1] V.S. Srinvasan представляет метод для выяснения различий между точкой ядра и точкой дельты, основанный на анализе характера направления около особой точки. Этот метод используется в данной статье.

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

В пункте 2.1 особая точка была обнаружена, однако, результат работы алгоритма лишь позиция около точки ядра. Для того чтобы точно локализовать точку ядра, используется поле направления высокого разрешения. Вокруг точки, которую мы получили в пункте 2.1, мы выбрали область размером 64*64, и использовали алгоритм из пункта 1, чтобы рассчитать поле направления этой области (при расчете W=2). Эксперименты показали, что использование алгоритма из пункта 2.1 для поля направления высокого разрешения дает не очень хороший результат. Поэтому необходимо найти новый алгоритм обнаружения особой точки для поля направления высокого разрешения.

Если учесть что направление возле точки ядра резко меняется, то можно использовать эту особенность чтобы найти особую точку. В настоящее время существует много алгоритмов обнаружения углов, которые могут быть использованы для обнаружения особой точки. В [5] ZhiQiang Zheng представляет много алгоритмов обнаружения углов, основанных на анализе уровней серого цвета. Алгоритмы имеют дело со значением изменения градиента, и по выбранному порогу выводят все максимальные точки. В нашем случае, учитывая то что мы нашли поле направления около точки ядра, мы можем использовать алгоритм для нахождения максимального изменения значения поля направления около точки ядра. Для этого алгоритм из [5] модифицирован для обнаружения точки ядра в поле направления.

Главные шаги алгоритма следующие:
1. Расчет поля направления O, состоящего из блоков 64*64 с окном 2*2;
2. Расчет градиента поля направления O_x(x, y), O_y(x, y), O_xx(x, y) и O_yy(x, y);
3. Расчет O²_x(x, y), O²_y(x, y), O²_xx(x, y) и O²_yy(x, y);
4. Расчет K(x, y) (по формуле 7):

    где Δ₀(x, y) расчитывается по формуле 8, а G(σ, x, y) – по формуле 9:

5. Рассчитываем меру того, что точка является точкой ядра (по формуле 10):

Точка, имеющая максимальное значение Δ является точкой ядра. Алгоритм довольно быстрый, из-за того, что он работает с блоком 64*64, взятым из изображения. Особенности алгоритма и его математическое обоснование приведено в [5].

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

Метод, представленный в этой статье, протестирован и сравнен с методом Asker. Изображения отпечатков пальцев, которые мы использовали, были получены с помощью чипа отпечатков пальцев фирмы veridicom, и размер изображения составлял 300*300 пикселей. В табл. 1 представлено сравнение общего времени поиска особой точки с помощью приведенного метода и метода Asker.

Таблица 1 – Временные затраты на обнаружение особой точки на процессоре Pentium 550MHz PC

В табл. 2 показано сравнение результатов обнаружения.

Таблица 2 – Сравнение результатов обнаружения

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

Рисунок 2 – Результаты обнаружения точек ядра на основе метода нескольких разрешений

Рисунок 3 – Результаты обнаружения точек ядра на основе метода одного разрешения

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

а)                                                        б)

Рисунок 4 – Результаты обнаружения на изображении низкого качества:
а) результаты представленного алгоритма; б) результаты алгоритма на основе одного разрешения

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

В данной статье представлен новый эффективный и высокоточный метод обнаружения особых точек. Этот метод вначале использует изображение низкого разрешения, чтобы обнаружить маленькую область, в которой содержится особая точка, а затем использует изображение этой области с высоким разрешением, чтобы точно найти местоположение особой точки. Результаты экспериментов показывают, что представленный метод высокоточный и устойчив к шумам. Более того, представленный алгоритм эффективный и подходит для использования в on-line системах.

[1] V.S. Srinvasan, N.N. Murthy Detection of singular points in fingerprint images Pattern Recognition, Vol 25, No. 2, 1992

[2] Marius Tico, Pauli Kuosmanen, A multiresolution method for singular points detection in fingerprint images, IEEE 1999

[3] Asker M. Bazen, Sabih H. Gerez Extraction of Singrlar Points from Directional Fields of Fingerprints, Mobile Communications in Perspective, Annual CTIT Workshop, Enschede, The Netherlands, February 2001.

[4] Kalle Karu, Anil Jian Fingerprint Classfication, Pattern Recognition, Vol.29, No.3 1996.

[5] ZhiQiang Zheng, Han Wang, Wam Khwang The Analysis of Gray Level Corner Detection, Pattern Recognition Letter, 20, 1999, 149-162