1. ВВЕДЕНИЕ

2. УЛУЧШЕНИЕ ОТПЕЧАТКА ПАЛЬЦА

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

2.1. Обозначения

Полутоновое изображение отпечатка пальца – I, определяется как матрица размерности N x N, где I(i, j) представляет яркость пикселей в i-той строке и j-том столбце. Мы допускаем, что все изображения отсканированы с разрешением 500 точек на дюйм (dpi), поскольку это разрешение рекомендовано ФБР. Средняя величина и расхождение полутонового изображения отпечатка пальца, I, определяется как:

Ориентационное изображение, O, определяется как N x N изображение, где O(i, j) представляет локальную ориентацию выступов на пикселе (i, j). Локальная ориентация выступов обычно определяется для блока лучше и точнее, чем в каждом пикселе; изображение разделяется на набор непересекающихся блоков размерности w x w и единственная локальная ориентация выступов определяется для каждого блока. Заметим, что в изображении отпечатка пальца отсутствует различие между локальной ориентацией выступов на 90 или 270, так как выступы, ориентированные на 90, и выступы, ориентированные на 270, в локальном соседстве не могут быть различены друг от друга.

Частотное изображение, F, представляет собой изображение размерности N x N, где F(i, j) представляет локальную частоту выступа, которая определяется как частота структур выступов и впадин в локальном соседстве вдоль (параллельно) направления нормали к локальной ориентации выступа. Структуры выступов и впадин в локальном соседстве (рисунок 4), где детали или особые точки не формируют четко определяемую синусоидально-очерченную волну. В таких ситуациях, частота определяется как средняя величина частоты в соседстве от блока (i, j). Подобно ориентационному изображению, частотное изображение определяется поблочно.

Рисунок 4 – Структуры выступов и впадин в локальном соседстве от детали

Областная маска, R, определяется как N x N изображение, где R(i, j) показывает категорию пикселя. Пиксель может быть:

1. не выступовым и не впадинным (необратимым) пикселем (со значением 0);
2. пиксели выступов и впадин (обратимые)(со значением 1).

Областная маска также определяется поблочно.

2.2. Алгоритм

Структурная схема алгоритма улучшения отпечатка пальца показана на рисунке 5.

Рисунок 5 - Структурная схема предложенного алгоритма улучшения отпечатка пальца

Основные шаги алгоритма включают в себя:

1. Нормализация: Входное изображение отпечатка пальца нормализуется для того, чтобы оно имело предварительно заданные средние значения и отклонения (колебания);
2. Оценка локальной ориентации: Ориентационное изображение рассчитывается из нормализованного входного изображения отпечатка пальца;
3. Оценка частотной ориентации: Частотное изображение вычисляется из нормализованного входного изображения и рассчитанного ориентационного изображения;
4. Расчет областной маски: Областная маска получается путем классификации каждого блока в нормализованном входном изображении в обратимый или необратимый блок;
5. Фильтрация: Набор фильтров Габора, который настраивается на локальную ориентацию выступов и частоту выступов, применяется к пикселям выступов и впадин в нормализованном входном изображении для получения улучшенного изображения отпечатка пальца.

2.3. Нормализация

Пусть I(i, j) обозначает полутоновое значение (уровня яркости) пикселя (i, j), M и VAR обозначают оценочное среднее значение и изменение изображения I соответственно, а G(i, j) обозначает нормализованное полутоновое значение пикселя (i, j). Нормализованное изображение определяется как:

где M₀ и VAR₀ заданное (желательное) среднее значение и значение изменения соответственно.

Нормализация – это операция над пикселями. Она не меняет четкость структур выступов и впадин. Главное назначение нормализации - уменьшить изменения (колебания) в полутоновых значениях вдоль выступов и впадин, что облегчает последующие шаги обработки. Рисунок 6 показывает пример нормализации изображения.

Рисунок 6 – Результат нормализации. (a) Входное изображение. (b) Нормализованное изображение (M₀ = 100, VAR₀ = 100).

2.4. Ориентационное изображение

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

Дано нормализованное изображение, G, главные шаги алгоритма следующие:

1. Разделить G на блоки размером w x w (16 x 16);
2. Вычислить градиенты dx(i, j) и dy(i, j) в каждом пикселе (i, j). В зависимости от вычислительных условий (требований), градиентный оператор может варьировать от простого оператора Собеля до составного оператора Мар-Хилдрет;
3. Оценка локальной ориентации каждого блока расположенного симметрично относительно пикселя (i, j), используя следующие уравнения:

   

   где (i,j) – оценка методом наименьших квадратов локальной ориентации выступа в блоке, расположенном симметрично относительно пикселя (i, j). Математически она представляет направление, которое является ортогональным к доминантному направлению спектра Фурье окна размерности w x w.

4. Вследствие наличия шума, искаженных структур выступов и впадин, деталей и т.д. во входном изображении, рассчитанная локальная ориентация выступа, ?(i, j), не всегда корректна. Так как локальная ориентация выступа изменяется медленно в локальном соседстве, где не обнаруживаются особые точки, может быть использован низкочастотный фильтр для корректировки неправильной локальной ориентации выступа. Чтобы выполнить низкочастотную фильтрацию, ориентационное изображение необходимо преобразовать в непрерывное векторное поле, которое определяется следующим образом:

   Ф_x(i, j) = cos(2(i, j))               (8)
   Ф_y(i, j) = sin(2(i, j))                (9)

   где Ф_x и Ф_y – компоненты x и y векторного поля, соответственно. На основании полученного в результате векторного поля, низкочастотная фильтрация выполняется следующим образом:

   

   где W – двумерный низкочастотный фильтр и w_Ф x w_Ф определяет размер фильтра. Заметим, что операция сглаживания выполняется на блоковом уровне. По умолчанию размер фильтра 5 x 5.

5. Вычисление локальной ориентации выступа в пикселе (i, j), используя:

   

С этим алгоритмом может быть получена довольно ровная (сглаженная) оценка ориентационного поля. Рисунок 7 показывает пример ориентационного изображения, вычисленного нашим алгоритмом.

Рисунок 7 – Пример ориентационного поля, полученного данным методом w=16 и w_ф=5

2.5 Частотное изображение выступа

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

Рисунок 8 – Ориентационное окно и х -сигнатура

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

1. Разделить G на блоки размером w x w (16 x 16);
2. Для каждого блока центрированного в пикселе (i, j), вычислить ориентационное окно размером l x w (32 x 16), которое определяется в координатной системе выступа (рисунок 8);
3. Для каждого блока центрированного в пикселе (i, j) вычислить x-сигнатуру X[0], X[1], ... X[l-1] выступов и впадин в пределах ориентационного окна, где:

   

   Если не обнаружено деталей и особых точек в ориентационном окне, х-сигнатура формирует дискретную синусоидально-очерченную волну, которая имеет такую же частоту как выступы и впадины в ориентационном окне. Поэтому частота выступов и впадин может быть оценена из х-сигнатуры. Пусть T(i, j) - среднее число пикселей между двумя следующими друг за другом вершинами в х-сигнатуре, тогда частота, , вычисляется как: = 1 / T(i, j). Если не обнаружено следующих друг за другом вершин из х-сигнатуры, тогда частота устанавливается в значение -1, чтобы отличить ее от действительных частотных значений;

4. Для изображения отпечатка пальца, отсканированного с постоянным разрешением, значение частоты выступов и впадин в локальном соседстве лежит в определенном диапазоне. Для изображения 500 dpi этот диапазон есть [1/3, 1/25]. Поэтому, если вычисленное значение частоты выходит за пределы этого диапазона, тогда частота, заданная значением –1, показывает, что действительная частота не может быть получена;
5. Блоки, в которых детали и/или особые точки обнаружены и/или выступы и впадины испорчены (искажены), не формируют хорошо определенную синусоидально-очерченную волну. Частотные значения для этих блоков должны быть интерполированы из частоты соседних блоков, которые имеют хорошо определяемую частоту. Интерполяция выполняется следующим образом:

   (I) для каждого блока, расположенного симметрично относительно (i, j):

   

   Wg - дискретное ядро Гаусса со средней величиной 0 и изменением 9, а W = 7 – это размер ядра.

   (II) Если существует по крайней мере один блок с частотным значением –1, то меняем местами и ^', и возвращаемся к шагу (I).

6. Расстояние между выступами меняется медленно в локальном соседстве. Низкочастотный фильтр может быть использован, чтобы устранить значения, лежащие за пределами, в f':

   

   где Wl – это двумерный низкочастотный фильтр с модульным интегралом и Wl = 7 – размер фильтра.

2.6. Областная маска

Как было упомянуто ранее, пиксель (или блок) во входном изображении отпечатка пальца может находиться в одной из двух областей: в обратимой области или в необратимой области. Классификация пикселей к обратимой или к необратимой категории может выполняться, основываясь на оценке формы (очертаний) волны, сформированной локальными выступами и впадинами. В нашем алгоритме используются три признака, чтобы охарактеризовать синусоидально-очерченную волну: амплитуда (), частота () и изменение (). Пусть X[1], X[2],... X[l] представляет х-сигнатуру блока, центрированного в (i, j). Три признака, соответствующие пикселю (блоку) (i, j), вычисляются следующим образом:

1. = (средняя высота вершин – средняя глубина впадин);
2. = 1 / T(i, j), где T(i, j) – среднее количество пикселей между двумя следующими друг за другом вершинами;
3. .

Мы выбрали несколько типичных изображений отпечатков пальцев, где обе обратимая и необратимая области были вручную помечены и вычислили три признака для этих областей. В итоге 2000 трехмерные образца были получены. Чтобы найти типичные образцы для двух классов, мы подали 2000 образцов в алгоритм группирования (кластеризации) с квадратичной ошибкой и определили шесть групп (кластеров). Четыре из этих групп соответствовали обратимым областям и оставшиеся две соответствовали необратимым областям. Шесть опытных образцов (соответствующие шести центрам кластеров) были использованы в классификаторе одного ближайшего соседа (1NN), чтобы классифицировать каждый w x w блок во входном изображении отпечатка пальца к обратимому или необратимому блоку. Если блок, центрированный в (i, j) является обратимым, то R(i,j)=1, иначе R(i,j)=0. После того, как получено изображение R, вычислен и процент обратимых областей. Если процент обратимых областей меньше, чем пороговая величина, Gобратимое = 40, то входное изображение отпечатка пальца бракуется (отклоняется). Допущенное изображение, затем проходит контроль через этап фильтрации.

2.7 Фильтрация

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

Ровно-симметричный фильтр Габора имеет общую формулу:

x_ф = x cos ф + y sin ф            (19)
y_ф = -x sin ф + y cos ф           (20)

где ф - ориентация фильтра Габора, f – частота синусоидальной плоскостной волны, а и – пространственные константы огибающей (оболочки) Гаусса вдоль осей x и y, соответственно. Модуляционно-передаточная функция (МПФ) фильтра Габора может быть представлена как:

u_ф = u cos ф + v sin ф            (22)
v_ф = -u sin ф + v cos ф           (23)

где и .

Для применения фильтров Габора к изображению необходимо задать три параметра:

1. частота синусоидальной плоскостной волны, f;
2. направление фильтра;
3. среднеквадратичные отклонения огибающей (оболочки) Гаусса, и .

Очевидно, что частотная характеристика фильтра, f, полностью определяется локальной частотой выступа, а направление определяется локальной ориентацией выступа. Выбор значений и содержит компромисс. Чем больше эти значения, тем фильтры более устойчивы к шумам, но при этом более вероятно, что фильтры будут создавать ложные выступы и впадины. С другой стороны, чем меньше значения и , тем менее вероятно, что фильтры будут создавать ложные выступы и впадины; следовательно, они будут менее эффективны в устранении шумов. Оба значения и были установлены в 4.0 на основе эмпирических данных. Пусть G будет нормализованным изображением отпечатка пальца, О – ориентационным изображением, F – частотным изображением, а R – восстанавливающей маской, тогда улучшенное изображение E находится следующим образом:

где wg = 11 определяет размер фильтров Габора.

3. ЭКСПЕРИМЕНТАЛЬНЫЕ РЕЗУЛЬТАТЫ И ОЦЕНКА ВЫПОЛНЕНИЯ