СПОСОБ ФОРМИРОВАНИЯ ПРЕДСТАВЛЕНИЯ (ШАБЛОНА) ОТПЕЧАТКА ПАЛЬЦА ЧЕЛОВЕКА
METHOD OF CREATION OF VIEW (TEMPLATE) OF FINGERPRINT

Настоящее изобретение относится к цифровой обработке изображений и может быть использовано в устройствах, осуществляющих автоматическую верификацию или идентификацию личности с использованием отпечатков пальцев.
В настоящее время существуют способы распознавания личности по отпечаткам пальцев, основанные на использовании шаблонов, состоящих из характерных деталей папиллярного узора (окончаний и ветвлений папиллярных линий отпечатков пальцев) [1, 2]. Эффективность указанных способов распознавания личности зависит от точности представления (шаблона) отпечатка пальца человека. Шаблон отпечатка пальца формируется на основе выделенных на цифровом изображении характерных деталей.
Известен способ выделения характерных деталей отпечатков пальцев, включающий определение направлений линий папиллярного узора в каждом блоке изображения для последующих этапов обработки, выделение областей объекта (области рисунка папиллярного узора) и фона, пороговое разделение области рисунка папиллярного узора на линии и промежутки между ними, операцию формирования скелета линий (получение линий шириной в 1 пиксель) и выделение характерных деталей с помощью полученного на предыдущем этапе скелета линий обрабатываемого изображения [3]. При этом возможно включение в шаблон ложно выделенных характерных деталей, что обусловлено наличием шумов на изображении и используемыми алгоритмами извлечения. Для устранения указанного недостатка применяются дополнительные этапы, направленные на удаление таких ложно выделенных характерных деталей.
Наиболее близким к заявляемому изобретению является способ формирования шаблона отпечатка пальца [4], включающий в себя следующие этапы:
- получение цифрового изображения отпечатка пальца,
- сглаживание цифрового изображения отпечатка для устранения шума,
- формирование бинарного изображения отпечатка,
- скелетизация бинарного изображения отпечатка для приведения ширины линий папиллярного узора к одному пикселю,
- выделение характерных деталей (минюций) путем анализа полученного скелета папиллярного узора отпечатка,
- создание шаблона, описывающего характерные детали (минюции).
На фиг.1 приведена схема алгоритма, реализующего способ, используемый в прототипе [4].
Анализ этапов способа-прототипа показывает, что он также не лишен недостатков. Так, в указанном способе отсутствует этап выделения области папиллярного узора отпечатка пальца от области фона, который, как правило, содержит шум, что увеличивает вычислительные затраты на последующих этапах обработки изображений отпечатков и может приводить к выделению ложных характерных деталей.
Кроме того, используемое в способе-прототипе сглаживание изображения отпечатка на этапе (2) направлено лишь на устранение шума, что не позволяет осуществлять восстановление рисунка нечетких областей папиллярного узора отпечатка.
Используемая при пороговом разделении пикселей изображения на этапе (3) бинаризация может приводить к уменьшению информации, которую можно использовать для удаления ложных характерных деталей на следующих этапах распознавания.
Кроме того, возможно формирование ложных характерных деталей, вносимых используемыми алгоритмами скелетизации (утоньшения) на этапе (4).
Помимо этого, при выделении характерных деталей на этапе (5) не проводится анализ наличия и параметров характерных деталей, находящихся в заданной окрестности от исследуемой характерной детали. Это также может приводить к увеличению числа ложно выделенных деталей, а следовательно, и к формированию некорректного представления отпечатка.
Задачей способа является получение технического результата, заключающегося в уменьшении числа ложно выделенных характерных деталей изображения для построения более точного представления (шаблона) отпечатка в результате добавления этапов, обеспечивающих технический результат: нормализации цифрового изображения отпечатка, выравнивания гистограммы цифрового изображения отпечатка, выделения области папиллярного узора отпечатка, построения поля направлений для выделенной области папиллярного узора отпечатка, частотной и направленной фильтрации цифрового изображения отпечатка, порогового разделения пикселей цифрового изображения отпечатка на три непересекающиеся группы, скелетизации выделенной области папиллярного узора отпечатка с использованием волнового метода и выделения характерных деталей путем трассировки скелета выделенной области папиллярного узора отпечатка.
Указанный результат достигается за счет того, что в известный способ формирования шаблона отпечатка пальца человека [4], включающий:
- получение цифрового изображения отпечатка пальца,
- сглаживание цифрового изображения отпечатка для устранения шума,
- создание шаблона, описывающего характерные детали (минюции),
добавляют следующие этапы, являющиеся отличительными признаками предлагаемого способа:
- перед сглаживанием цифрового изображения отпечатка проводят нормализацию цифрового изображения отпечатка,
- после сглаживания цифрового изображения отпечатка проводят выравнивание гистограммы цифрового изображения отпечатка,
- причем одновременно с выравниванием гистограммы цифрового изображения отпечатка осуществляют выделение области папиллярного узора отпечатка с последующим построением поля направлений для выделенной области папиллярного узора отпечатка,
- после выравнивания гистограммы цифрового изображения отпечатка и построения поля направлений для выделенной области папиллярного узора отпечатка выполняют частотную и направленную фильтрацию цифрового изображения отпечатка,
- после частотной и направленной фильтрации цифрового изображения отпечатка и выделения области папиллярного узора отпечатка осуществляют пороговое разделение пикселей цифрового изображения отпечатка на три непересекающиеся группы,
- проводят скелетизацию выделенной области папиллярного узора отпечатка с использованием волнового метода,
- перед созданием шаблона, описывающего характерные детали (минюции), проводят выделение характерных деталей путем трассировки скелета выделенной области папиллярного узора отпечатка.
Проведенные патентные исследования показали, что совокупность отличительных признаков предлагаемого изобретения является новой, что доказывает новизну заявляемого способа. Кроме того, патентные исследования показали, что в литературе отсутствуют данные, показывающие влияние отличительных признаков заявляемого способа на достижение технического результата, что подтверждает изобретательский уровень предлагаемого способа.
На фиг.2 изображена схема алгоритма, реализующего предлагаемый способ.
На этапе (1) предлагаемого способа выполняют процедуру получения полутонового цифрового изображения отпечатка пальца человека, например, с использованием компактного считывателя отпечатков пальцев, подключаемого к ЭВМ.
i,j
Обозначим через Р полученное на данном этапе полутоновое цифровое изображение отпечатка, которое имеет размеры Н×W. Этапы по обработке полутонового изображения модифицируют значения p∈[0;255], i=0,…,H-1, j=0,…,W-1 каждого пикселя цифрового изображения Р.
Затем на следующем этапе (7) выполняют нормализацию полученного на предыдущем этапе изображения отпечатка Р, которая заключается в приведении среднего значения интенсивности обрабатываемого изображения и дисперсии интенсивности к заданным значениям в соответствии со следующим выражением
i,j
где , p - нормализованное и исходное значения интенсивности каждого пикселя цифрового изображения соответственно; mean - заданное значение величины средней интенсивности пикселей изображения; variance - заданное значение дисперсии интенсивности пикселей изображения; img_mean - фактическая величина среднего значения интенсивности изображения; img_variance - фактическая величина дисперсии интенсивности изображения.
После этого применяют этап (2) - сглаживание цифрового изображения отпечатка - для удаления шумов, специфичных для изображений, получаемых с конкретного сканирующего устройства [5, 6].
Следующий этап (9) - выравнивание гистограммы цифрового изображения отпечатка - применяют для восстановления рисунка нечетких областей папиллярного узора отпечатка. На данном этапе проводят выравнивание гистограмм блоков значений интенсивности изображения путем отображения значений интенсивности блока вокруг каждого пикселя изображения так, чтобы распределение значений интенсивности по блоку было равномерным [5, 6].
Одновременно с этапом (9) проводят этап (8) для выделения области папиллярного узора отпечатка и области фона, а также этап (10) для построения поля направлений для выделенной области папиллярного узора отпечатка. Выделение области папиллярного узора отпечатка на этапе (8) включает вычисление значений модулей градиентов (изменение) интенсивности для каждого пикселя изображения по двум направлениям gx (0°) и gy (90°), например, с помощью операторов Собеля
.
Вычисление значений модулей градиентов по двум направлениям представляет собой свертку блока значений интенсивности изображения относительно каждого пикселя размером 3×3 с указанными масками.
Вычисленные значения модулей градиентов интенсивности позволяют осуществить разделение пикселей изображения на пиксели, принадлежащие области папиллярного узора отпечатка (объекта), и пиксели фона изображения с использованием следующего правила
,
f
b
где G, G - группы пикселей изображения, принадлежащие области папиллярного узора отпечатка и области фона соответственно;
i,j
grd_mean - среднее значение модулей градиентов по блоку размером (2×h+1)×(2×h+1) относительно (i, j) пикселя изображения
;
h=k×INTER_RIDGE_DISTANCE - часть от среднего расстояния между линиями отпечатка (INTER_RIDGE_DISTANCE∈{3,…,25} пикселей при разрешении 500 точек на дюйм);
k,l
g - значение модуля градиента каждого пикселя изображения, определяется как значение модуля суммарного вектора градиентов по двум направлениям gx (0°) и gy (90°)
img_grd_mean - среднее значение модулей градиентов по всем блокам размером (2×h+1)×(2×h+1) относительно каждого пикселя изображения
;
K - весовой коэффициент;
i,j
count - количество однотипных пикселей в заданной окрестности, определяет количество соседей-пикселей, отнесенных к области папиллярного узора отпечатка согласно условию (grd_mean≥K×img_grd__mean);
t - пороговое значение, определяет минимальное количество однотипных соседей -пикселей, принадлежащих области папиллярного узора отпечатка.
В процессе построчной обработки изображения проводят пометку областей объекта и фона, а также определяют их размеры (число пикселей изображения, отнесенных к помеченным областям). Затем формируют связные области путем объединения помеченных областей и определяют их размеры как сумму размеров объединяемых областей, а также определяют пороговое значение размера для связных областей объекта как среднее значение числа пикселей, вычисленное по всем связным областям объекта, и определяют пороговое значение размера для связных областей фона как среднее значение числа пикселей, вычисленное по всем связным областям фона. В результате проводят удаление областей объекта и фона с размерами, меньшими произведения полученных пороговых значений на соответствующие весовые коэффициенты.
f
b
Результатом выполнения выделения области папиллярного узора отпечатка на этапе (8) является изображение, разделенное на группы пикселей G и G, которое может выступать в качестве маски при последующей обработке полутонового изображения, а также значения модулей градиентов (изменение) интенсивности для каждого пикселя изображения по двум направлениям gx (0°) и gy (90°).
i,j
Построение поля направлений на этапе (10) выполняют для определения направлений линий в локальных областях в виде неперекрывающихся блоков. Направление линий в блоке задается направлением, ортогональным направлению градиентов (изменению) интенсивности. Построение поля направлений включает вычисление значений углов градиентов θ по каждому блоку с использованием значений модулей градиентов по двум направлениям gx (0°) и gy (90°) для каждого пикселя
,
где h=k×INTER_RIDGE_DISTANCE - часть от среднего расстояния между линиями отпечатка (INTER_RIDGE_DISTANCE∈{3,…25}).
Вычисленные значения углов градиентов по каждому блоку подвергают фильтрации с использованием, например, функции Гаусса. Фильтрация представляет собой свертку блока значений углов размером (2×h+1)×(2×h+1),
где h=k×INTER_RIDGE_DISTANCE - часть от среднего расстояния между линиями отпечатка (INTER_RIDGE_DISTANCE∈{3,…,15} пикселей при разрешении 500 точек на дюйм), с константной маской G (x, y)
где fx, fy - две составляющие непрерывного векторного поля для каждого блока
k,l
k,l
fx=cos(2θ),
k,l
k,l
fy=sin (2θ),
и вычисление значений углов направления линий
.
Затем, используя результаты, полученные на этапах (9) и (10), проводят частотную и направленную фильтрацию (этап 11), которая заключается в удалении дефектов изображения (восстановление линий нечетких областей изображения (удаление разрывов), удаление пятен и пустот). Указанный этап может быть выполнен путем применения направленных фильтров (функция Габора) к полутоновому изображению отпечатка и/или преобразованиями изображения в частотной области [5, 6].
После этапа (11), с использованием результата этапа (8), выполняют пороговое разделение пикселей отфильтрованного изображения отпечатка на три непересекающиеся группы (этап 12). При этом при последовательном просмотре изображения рассматриваемый пиксель относят к группе 1, если значение его интенсивности меньше или равно значению первого порогового коэффициента; в противном случае рассматриваемый пиксель относят к группе 2, если значение его интенсивности меньше или равно значению второго порогового коэффициента. В случае невыполнения указанных двух условий рассматриваемый пиксель относят к группе 3. Необходимо заметить, что первый пороговый коэффициент должен быть меньше второго порогового коэффициента.
Затем на этапе (13) проводят скелетизацию, которая заключается в использовании волнового метода формирования скелета. При этом при последовательном просмотре изображения находят пиксель, принадлежащий группе 1, а также обнуляют счетчик шагов, первый и второй массивы координат пикселей. Удаляют найденный пиксель из группы 1 и сохраняют его координаты в первом массиве координат пикселей. Проводят процесс непосредственного формирования скелета объектов обрабатываемого изображения: при последовательном просмотре пикселей, координаты которых сохранены в первом массиве координат пикселей, просматривают все соседние пиксели изображения, и если среди них находятся пиксели, отнесенные к группе 1, то их удаляют из группы 1 и добавляют координаты этих пикселей во второй массив координат пикселей. Если второй массив координат пикселей пуст, то просматривают соседние пиксели всех пикселей, координаты которых сохранены в первом массиве координат пикселей, и если среди соседних пикселей находят пиксели, отнесенные к группе 2, то их удаляют из группы 2, a иx координаты сохраняют во втором массиве координат пикселей. Если второй массив координат пикселей пуст, то вычисляют координаты центрального пикселя для обрабатываемого массива координат пикселей как среднее арифметическое соответствующих координат пикселей, хранящихся в первом массиве координат пикселей, помечают его как последний центральный пиксель и сохраняют координаты этого и предыдущего центральных пикселей в массив ребер скелета объектов обрабатываемого изображения; завершают процесс формирования скелета объектов обрабатываемого изображения для рассматриваемого первого массива координат пикселей. Сохраняют координаты этого и предыдущего центрального пикселя в массив ребер скелета объектов обрабатываемого изображения.
Первый массив координат пикселей заменяют вторым массивом координат пикселей; после чего во втором массиве координат пикселей удаляются все элементы. Если значение счетчика шагов кратно значению частоты дискретизации скелета объектов обрабатываемого изображения, то вычисляют координаты центрального пикселя как среднее арифметическое соответствующих координат пикселей, хранящихся в первом массиве координат пикселей, центральный пиксель помечают как последний центральный пиксель и сохраняют координаты этого и предыдущего центральных пикселей в массив ребер скелета объектов обрабатываемого изображения, при этом если значение счетчика шагов равно нулю, то ребро не добавляют, а только сохраняют значение последнего центрального пикселя для обрабатываемого массива координат пикселей. Увеличивают счетчик шагов на 1.
В процессе последовательного просмотра пикселей, координаты которых сохранены в первом массиве координат пикселей, формируют из них связные области пикселей.
Создают массивы для хранения координат пикселей, по числу связанных областей, и переносят координаты пикселей, составляющих каждую связную область, в отдельный массив координат пикселей связной области, для каждого из созданных массивов запоминается отдельно значение координат последнего центрального пикселя. Последовательно для каждого из созданных массивов координат связных областей проводят процесс формирования скелета объектов обрабатываемого изображения, описанный выше. При этом в качестве первого массива координат пикселей выступает соответствующий массив координат пикселей очередной обрабатываемой связной области, а в качестве последнего центрального пикселя выбирают последний центральный пиксель этого массива, проверяют критерий окончания процесса формирования скелета объектов обрабатываемого изображения для сформированных связных областей пикселей: отсутствие элементов во всех массивах координат пикселей связных областей.
Если вышеуказанный критерий окончания процесса формирования скелета объектов обрабатываемого изображения не удовлетворяется, продолжают последовательный просмотр пикселей изображения, если среди них находятся пиксели группы 1, повторяют описанный выше процесс формирования скелета объектов обрабатываемого изображения.
Далее преобразуют полученный массив ребер скелета объектов обрабатываемого изображения к его растровому представлению путем рисования ребер скелета на изображении.
После этого выполняют этап (14) для выделения характерных деталей скелета объектов обрабатываемого изображения путем трассировки скелета. При этом при последовательном просмотре пикселей растрового представления скелета объектов обрабатываемого изображения для каждого пикселя подсчитывают число соседних пикселей, принадлежащих растровому скелету объектов обрабатываемого изображения, если число соседних пикселей равно одному, то пиксель помечается как пиксель-кандидат окончания линии, если число соседних пикселей равно трем или более, то пиксель помечается как пиксель-кандидат ветвления линии, пиксели окончания и ветвления линии считают характерными деталями скелета обрабатываемого изображения.
При последовательном просмотре для очередного пикселя-кандидата растрового представления скелета объектов обрабатываемого изображения проводят трассировку с заданным числом шагов, в результате трассировки определяют количество скелетных линий, отходящих от рассматриваемого пикселя-кандидата, а также их длину. Если от рассматриваемого пикселя отходит одна скелетная линия, длина которой в пикселях не меньше, чем заданное число шагов трассировки, то данный пиксель помечают как окончание линии.
Если от рассматриваемого пикселя-кандидата отходит три или более скелетных линий, длина которых в пикселях не меньше, чем заданное число шагов трассировки, то определяют углы между соседними отходящими от рассматриваемого пикселя-кандидата скелетными линиями, затем при последовательном просмотре углов между соседними линиями выбирают минимальный угол, выбирают максимальный угол; если выбранный минимальный угол оказался меньше первого порогового коэффициента угла, а выбранный максимальный угол оказался меньше второго порогового коэффициента угла; то рассматриваемый пиксель-кандидат помечают как ветвление линии.
Затем на завершающем этапе (6) формируют представление (шаблон) отпечатка, описывающее количественные характеристики выделенных на предыдущем этапе характерных деталей (минюций): координаты, связанное с минюцией направление папиллярных линий, тип и др.
Таким образом, в результате включения новых этапов (7), (8), (9), (10), (11), (12), (13) и (14) в предлагаемом способе устраняются недостатки, присущие способу-прототипу, указанные при анализе способа [4] на этапах (2), (3), (4) и (5), что уменьшает число ложно выделенных характерных деталей (минюций) и обеспечивает построение более точного представления (шаблона) отпечатка пальца в предлагаемом изобретении.
Литература
1. Ratha N.K., Kаru K., Chen S., Jain A.K. A Real-Time Matching System for Large Fingerprint Databases // IЕЕЕ Trans. on Pattern Analysis and Machine Intelligence, 1996, vol.18, no.8, pp.799-813.
2. Jain A.K., Hong L., Bolle R. On-line Fingerprint Verification // IEЕЕ Trans. on Pattern Analysis and Machine Intelligence, 1997, vol.19, no.4, pp.302-313.
3. Ratha N.K., Chen S., Jain A.K. Adaptive feow orientation based feature extraction in fingerprint images // Pattern Recognition, 1995, no.28, pp.1657-1672.
4. Патент 7120280 В2 США, МКП G06K 9/00. Fingerprint template generation, verification and identification system.
5. Методы компьютерной обработки изображений / под ред. Сойфера В.А. - М.: ФИЗМАТЛИТ, 2003. - 784 с.
6. Гонсалез Р., Вудс Р. Цифровая обработка изображений. / Пер. с англ. - М.: Техносфера, 2005. - 1072 с.