Скоростная обработка изображения отпечатка пальца

СКОРОСТНАЯ ОБРАБОТКА ИЗОБРАЖЕНИЯ ОТПЕЧАТКА ПАЛЬЦА

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

Ключевые слова: отпечаток пальца, частный признак, тензор, градиент, поле потоков, обработка изображений.

Введение

Исследования в области биометрии начались более ста лет назад с разработки методов сравнения отпечатков пальцев. С развитием вычислительной техники появилась возможность учета лиц в электронных системах, обеспечивающих контроль преступности и терроризма. Функционирование электронных систем подобно деятельности эксперта-криминалиста и опирается на модель дактилоскопического изображения (ДИ) в виде частных признаков и отношений между ними [8]. Среди электронных систем наиболее известны системы криминального и гражданского назначения. Если для первых систем основным показателем эффективности служит величина ошибки идентификации подозреваемого лица, то для вторых наравне с величиной ошибки аутентификации пользователя не менее важна и производительность системы [7]. Это оказывает сильное влияние на выбор методов обработки ДИ, например, в системах контроля и управления доступом к объекту. На рис. 1 на узоре левой петли выделены частные признаки в виде окончания и разветвления, распознавание которых простыми методами неэффективно [2; 8]. Поэтому скоростная обработка ДИ реализуется в виде последовательности методов измерения, анализа и синтеза параметров изображения, настройка или обучение которых минимизирует влияние дефектов изображения (рис. 1). Тем не менее, жесткие ограничения по времени сужают класс ДИ, пригодных для такой обработки, преимущественно до изображений среднего качества и выше.

1. Постановка задачи

Обычно для упрощения задачи распознавания частных признаков вводятся этапы предварительной обработки и повышения качества ДИ. Для этого оно представляется в прямоугольной области О мощностью |О| = х0у0 в виде ^ = {/(х, у) € 0..2Ь — 1 | (х, у) € X х У}, где Ь — глубина изображения; X = 0..хо — 1 и У = у0 — 1.

Рис. 1. Изображение отпечатка пальца

Обработка изображения структурно представляется в виде пирамиды Я взаимосвязанных иерархий [1-2; 6], для которых сегментация изображения выполняется для любого слоя произвольной иерархии. Например, /-й слой к-й иерархии ^2 разбивается на х^уь, квадратных сегментов £2 (х,у) с длиной стороны 2к-к и вершинами (х, у) Є Х^ х У^, где к < к и к — номер иерархии; Х^ = 0..х^ — 1 и У. = уь. — 1.

Доступ к каждой точке сегмента (х,у) записывается в координатах

(и, V) Є Xн х У

Xн = (и + х2^-2 | х Є Х^ Л и Є 0..2^-к — 1} , -1.

УЛ = (V + у2^-2 | у Є УЛ Л V Є 0..2^-2 — 1} . ( 1

Доступ к центральной точке сегмента 5^(х,у) записывается в координатах (и, V) € Х^ х ^

ХЛ = {2^-к-1 + х2^-к | х € Х4 ,

Ул = {2^-1 + у2^-к | у € У4 .

Размер области Л-й иерархии: х^ = [|0] и у^ = [|0], где [а] — наименьшее целое число, превышающее вещественную величину а.

При иерархической сегментации сегменты слоя отображаются на вершины сегментов слоя ^ пирамиды Д, где к < Л. Соответственно, вершины сегментов отображаются на сегменты, расположенные ближе к основанию пирамиды [2]. Размер сегмента заметно влияет на время и качество обработки. Далее положим (х,у) = 5^о(х,у) и вершины 5^(х,у) = ^.

Слои пирамиды можно представить множеством действительных чисел, а исходное изображение — множеством неотрицательных действительных чисел [1; 6]. Это снимает необходимость утомительного целочисленного представления сигнала и упрощает выражения, однако дискретизация изображения (слоев пирамиды Д) в пространстве сохраняется.

Для компактной математической формализации методов классификационного анализа (КА) широко применяется аппарат апертур. Ключевую роль при этом играют прямолинейные щелевые А^(х,у,а,и>) и А-(х, у, а, ад), круговая А^(х,у, ад) апертуры, представляемые множеством точек слоя данных Л-й иерархии и связанными с ними углами в виде элементов упорядоченных троек (и, V, в). Эти апертуры определяются по формулам

Г А^(х,у,а,^) = {(и,г>,в) = (х + ]ад сов(а)[, у + ]ад в1п(а)[, в) | ^„

[ А-(х, у, а, ад) = {(и, V, в) = (х + ]ад сов(а)[, у + ]ад вт(а)[, в) | ш € Я-} ,

где (х,у) Є Х^ х У/і — центр апертуры; (и,г>) Є Х^ х У, — точка апертуры; т — размер апертуры; = 1..т; = —т.. — 1 и 1..т; а — угол направления аперту-

ры; ]а[ — ближайшая целая часть вещественного числа а. Угол, определяющий направление из центра апертуры (х,у) в точку (и,г>), находится в виде

Для задачи распознавания частных признаков этапы предварительной обработки и повышения качества ДИ должны удовлетворять требованию ограничения по времени. При этом алгоритм должен обеспечивать приемлемое качество распознавания частных признаков, которое проверяется на тестовой базе ДИ. Задачей является построение списка частных признаков в виде

где Мг — частный признак и мощность |Ьт| = п1; г — индекс как номер частного признака; (хг, уг), аг, ^ — координаты, направление как угол и тип частного признака. Компромиссным решением поставленной задачи и устранения противоречия «качество — скорость» может служить реализация шести этапов обработки ДИ: 1 — построение матрицы потоков; 2 — сглаживание линий; 3 — построение матрицы плотности линий; 4 — сегментация; 5 — бинаризация; 6 — скелетизация и распознавание частных признаков.

2. Скоростная обработка

Большинство алгоритмов КА отпечатков пальцев нацелены на распознавание частных признаков [8], которые могут использоваться для вычисления отношений между ними. Решение задачи скоростной обработки продемонстрируем на примере исходного изображения ^0° = |/о0)(х,у)| (рис. 1).

2.1. Интегральное изображение

Интегральное изображение I позволяет вычислить сумму элементов прямоугольной области изображения с постоянным количеством операций независимо

= {Мі = |(хі,уі),аі,іі} | і Є 1..п} ,

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

1 (х.у) = /(х.У) + 1 (х - 1.У) + 1 (*.!/ - 1) - 1 (я - 1,у - 1).

Рис. 2 илюстрирует вычисление интегрального изображения. Однажды вычислив интегральное изображение, мы можем найти сумму элементов любой прямоугольной области изображения с левым верхним углом (ж1,у1) и правым нижним углом (ж2,у2) за постояное время по формуле

Х2 У2

X! X! /

Х=Х1 У=У1

Рис. 2. Слева: прямоугольная область изображения. Справа: интегральное

изображение

2.2. Построение матрицы потоков

Это базовый этап обработки, от которого зависит точность распознавания частных признаков. Он состоит из двух последовательно выполняемых процедур обработки ДИ. Самый простой подход для вычисления матрицы потоков основан на вычислении градиента.

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

5, = (ж, у) иерархии к = 3(8 х 8) угла 0 < ^|г0)(х,у) < 180 как элемента матрицы потоков Л(0) по формуле

Л

40)

2Л2

п 1

—I— агсіап . т . . т . .

2 2 V ^22

где ^12(ж,у) = УжУу; ^П(ж,у) = УхУж;

^22 (ж,уНЕ („, ^)е5^(ж у) . Компоненты градиента в отсчетах (и, V) € X^ хУ^

по (1) основания сегмента 5^(ж,у) вычисляются в виде = Нх * */0(0)(и,г') и = Ну * */0°)(и,г'), где ядра двумерной свертки как оптимизированные по величине ошибки угла ориентации операторы Собела [6] находятся в виде

1 - со 0 1 00 1 - со 0 1 - -3

Н = о 1 - 0 10 = 0 0 0

1 - со 0 3 1 3 10 1 3

П

Таким образом, первоначально необходимо вычислить интегральные изображения ЮХу(ж, у), Юхх(ж, у) и Юуу(ж, у) по (6) для определения тензоров ^12(ж, у), Зц(ж, у), 322(ж, у) соответственно и расчета потока независимо от размера апертуры. Здесь

ЮХу(ж, у) = Сху (ж, у) + /Сху(ж — 1) у) + /Сху(ж) у — 1) — /Сху(ж — 1) у — 1)) где Сху (ж, у) = Ух (ж, у) У у (ж, у).

Интегральные изображения Юхх (ж, у) и Юуу (ж, у) вычисляются аналогично Юху(ж, у). Затем определяем 712(ж, у), 711 (ж, у) и 722(ж, у) по следующим формулам:

712(ж, у) = /Сху(ж2, у2) — /Сху(ж1 — 1, у2) — /Сху(ж2, у1 — 1) + /Сху(ж1 — 1 у1 — l),

711 (ж, у) = /Схх(ж2, у2) — /Схх(ж1 — 1, у2) — /Схх(ж2, у1 — 1) + /Схх(ж1 — 1, у1 — l),

722(ж у) = /Суу(ж2, у2) — /Суу(ж1 — 1, у2) — /Суу(ж2, у1 — 1) + /Суу(ж1 — 1, у1 — l),

где точка (ж1, у1) — левый верхний угол сегмента изображения, а точка (ж2, у2) —

его правый нижний угол.

Фактически элементы из Л ^ вычисляются сглаживанием в сегментах {5^(ж, у)} компонент поточечного структурного тензорного оператора [6], записываемого в виде

711 + 722

3 =

322 - 3

11

23

12

Анализ и коррекция матрицы потоков. В иерархии к = 3 на основе (9) для (ж, у) € х рассчитывается когерентность потоков по формуле

мГ

У

Когерентность для идеальных линий равна единице, а для изотропной структуры - нулю [6]. Благодаря ранее вычисленным интегральным изображени-

ям мы находим Л(0), Л(1), Л(2), Л(3) и М^, М^±;, М^1, М^°1 при Н = 3 и апертурах Аь(я, у, 8), А ь(я, у, 24), А ь(я, у, 40), А ь(я, у, 56) по (4) соответственно. Результаты этих вычислений представлены на рис. 3.

[1 і

Рис. 3. Справа налево, сверху вниз: Л(0), Л(1), Л(2), Л(3) и соответствующие им

м<0), м<1), а/<2), м<3)

Далее выполняется анализ полученных матриц потоков Л(0), Л(1), Л(2), Л(3) и матриц когерентности М^0), М^, М^2), М^3). Для этого рассчитываем матрицу

лг

производных N ь и матрицу потоков О^ в виде

^0) =

где с = а^ шах(^(1)(ж, у)); п — количество слоев, в данном случае п = 4. Следовательно, Ж^0) отображает изменение когерентности потоков, а в О (0) находят лучший поток.

Матрицы ^0) и О (0) анализируют и находят матрицу потока Л(4):

ЕГ=-1!

о(0) =

о

Л

= {«I1’

^ ^ I о ь (я, у), иначе,

где Т — некий порог, для данной реализации Т = -0,1.

Элементы из Л(1) как элементы векторного пространства корректируются по формуле

Л(5) = {(я,у^ = | ^агсіап

гш

ге

где

ге^)

и гш(0) (ж, у) = Ек=-1 Ет=-1 М(0) (ж + к, у + т) 8т(25(4) (ж + к, у + т)). Таким образом, полученная матрица Л(5) надежнее. На рис. 4 показана результирующая матрица потоков.

Рис. 4. Результирующая матрица потока

/г

п

2.3. Сглаживание

Сглаживающий фильтр устраняет микроразрывы и микрозалипания линий. Перед сглаживанием необходимо вычислить матрицу регулярности потока /Д(0), к = 3, используя следующую формулу [8]:

гг

1-

не т=-1 еп=-1 гі

Ет=-^ЕП=-1 + п у + ш)

л.

где d(x,y) = [cos 2£(5)(x, y), sin2£(5)(x,y)] ; ||x|| — норма L2.

Затем применяем сглаживающий фильтр для каждого сегмента Sh(x,y) изображения. Величины отсчетов в основании каждого сегмента Sh(x,y) сглаживаются по формуле

H1 * S0a) (x, y), если ir(0) (x, y) > t,

Z/(1)(x,y) = /i0)(x,y),

иначе,

где Н — ядро одномерной свертки; £ — некоторый порог (в реализации £ = 0, 5); набор Ц0а)(ж,у) = |£оа)(и>г’)| состоит из элементов, выбираемых из 3^0) прямолинейной щелевой апертурой по (3) в виде

{^0“)(и>^^ = {/00)(и,^) 1 (и,^) € А-(х,у,а,ад) и (ж,у^ ,

где а = $(5)(ж,у) € Л^; — направление апертуры, одинаковое для всех отсчетов основания сегмента 5!(ж, у); и — размер апертуры. Перенумеруем упорядоченные

отсчеты набора Ц0а)(ж,у) = |£0а)(и, V) |, сгенерированного щелевой апертурой

по (3), в виде к 1—> (ик, ), где к € 0..Х и N = 2и + 1. Тогда ядро свертки Н1

рассчитывается в виде

H1 = exp I —

(w — k)2

2а2

где а — среднеквадратичное отклонение, определяющее крутизну Гауссиана [8] (2-4 в реализации); к = и — отсчет центра окна, здесь равный размеру апертуры и .

Сглаживающий фильтр, по сути, является выделенным первым сомножителем разделимого фильтра Габора с меньшим количеством отсчетов в п/2 раз. Результат сглаживания представлен на рис. 5.

Рис. 5. Исходное и сглаженное изображение

2.4. Построение матрицы периодов

Это базовый этап обработки, влияющий на точность распознавания частных признаков. Он выполняется на той же иерархии к = 3 и состоит из двух последовательно выполняемых процедур обработки ДИ.

Измерение матрицы локальных периодов линий. Метод измерения опирается на применение автокорреляционной функции.

Определение 1. Под периодом линий понимается величина £ = ^, обратно пропорциональная среднему количеству п линий, умещающихся в окрестности размером и на прямой, проведенной перпендикулярно линиям.

Зададим отрезок С (ж, у) = А-(ж,у,а,и) и (ж, у), сгенерированный щелевой апертурой по (3), и перенумеруем отсчеты (и, г) € С (ж, у) в виде к I—> (м&, ), где

к € 0.^ и N = 2и+1. В отрезке С (ж, у) с центром к € {и} в отсчете (ж, у) € X хУ собираются упорядоченные по к величины яркости изображения. Ориентация щелевой апертуры определяется углом а, выбираемым перпендикулярно потоку по формуле а = П2 + $(5)(ж,у) при (ж, у) € X/ х У!, а ее длина определяется окрестностью размером и для отсчета (ж, у) € X х У (и =16 в реализации).

Для отрезка С (ж, у), центрированного в отсчете (ж, у) € Х/0 х У/о по (2) на сегменте 5/(ж,у), вводят автокорреляционную функцию в виде

1 N-1-1

ГМ = йЕ /01)

к=0

где /0(1) (к) = /01) (к) — / и / = N ^^=01 /(1) (к); N — количество отсчетов щелевой апертуры. Определим разность Дг(г) = г(г + 1) — г(г). Тогда элементы матрицы

локального периода линий Т^0) = |£(0)(ж,у) | вычисляют по формуле

£

г

Фактически для каждого сегмента иерархии к = 3 выделяется его центр, через который проводится отрезок перпендикулярно потоку. На рис. 6 величины яркости изображения собираются в отсчетах забеленного отрезка. Для них по (14) оценивается локальный период линий на основе автокорреляционной функции по (13), график которой показан на рис. 6. Выбор иерархии к = 3 сокращает количество оценок в 64 раза.

Отметим, что формула (14) определяет такой локальный период линий, который соответствует экстремуму отсчетов для положительных величин автокорреляционной функции во второй положительной полуволне. На рис. 6 период линий равен 9. Выбор экстремума «центрирует» маску фильтра, применяемого для фильтрации ДИ. Однако предположение о том, что оценка периода линий 40)(ж,у) может быть смещена, оставляет пространство для маневрирования параметрами фильтрации. На ровном фоне изображения элементы матрицы Т/[0) нулевые.

Рис. 6. Определение периода

Анализ и коррекция матрицы периодов линий. Исходя из того что отношение постоянной составляющей автокорреляционной функции r(0) и ее значения в точке первого максимума r(t(0)(x,y)) для функции sin равно 1, получим матрицу достоверности периода в виде

z

Известно, что для ДИ с разрешением 500 dpi 4 < tj0(x,y) < 17 [8]. Это позволяет удалить ошибки распознавания локального периода линий, задавая

t(0) (x,y) = 0.

Суть процедуры сводится к расчету матрицы периодов линий T^x) = jt(1)(x,y)j, которая в начальной итерации номером j = 0 инициализируется Т^х) = Т^0). Далее номер j итерации инкрементируется. В первой итерации для t(1) (x,y) / {0} период линий сглаживается по формуле

t

t h j

Er С 4u,v)

где условие суммирования R = t(1j-1 (u,v) > 0 элементов апертуры

(u, v) G Ah(x, y, 1) по (4); n = ^R 1 — количество ненулевых элементов в апертуре. В последующих итерациях для каждого отсчета с кодом пропуска t(1) (x, y) G {0} и для смежных с ним ненулевых элементов количеством n, если n > 4, период линий прогнозируется по (16). Количество итераций ограничивают величиной

2-3. Если ограничение снять, то большая часть элементов из Т/(1) определится.

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

\

ЭП

Рис. 7. Результирующая матрица периодов (слева) и матрица их достоверностей

2.5. Сегментация

Сегментация необходима для отделения информативных областей ДИ от неинформативных. Она выполняется на той же иерархии Н = 3 и заключается

в расчете матрицы меток С(0) = |с(0) (х, у)| по формуле

с

где £(1) (х, у) — величина достоверности периода по (15), сглаженная с помощью маски размером 3 х 3; д(1) (х, у) — когерентность потоков по (10), сглаженная

с помощью маски размером 3 х 3; к0, к1, к2 — обучаемые коэффициенты.

Фактически при выделении информативных областей опираются на два признака: корреляционную функцию и когерентность потоков. Эти признаки сами по себе комплексные, а их сочетание позволяет повысить точность сегментации.

При сегментации могут образовываться островки «разнородных» областей. К ним можно применить операции морфологической обработки изображения [1; 6], повышающие точность сегментации. Однако по причине ограничения по времени это нежелательно.

2.6. Бинаризация

Бинаризация опирается на ранее вычисленные данные, а именно на матрицу

периодов Т/(1) и матрицу меток С(0). Каждый элемент сегмента (х,у) изобра-

жения /0(1) (х,у) с меткой с(0) (х,у) Е {1} бинаризуется следующим образом: если значение элемента /0^ (х,у) меньше среднего значения т элементов в круговой апертуре Аь(х, у, ), умноженного на некоторый коэффициент к, то элементу присваивается значение 1, иначе 0 (в реализации к = 0, 98), т. е.

^2) (х ) Г 1 если /01) (х,у) < кт

0 \ 0, иначе.

Среднее значение рассчитывается с помощью интегральных изображений по формулам (6) и (7), что позволяет заметно ускорить процесс бинаризации. Размер апертуры для каждой точки изображения берется из матрицы периодов Т/(1). Результат бинаризации показан на рис. 8.

Рис. 8. Бинаризованное изображение

2.7. Скелетизация и распознавание частных признаков

На этом этапе линии бинарного ДИ (рис. 8) утончаются до скелета. Введем некоторые определения.

Определение 2. Скелетом линии называется простая цепь (и, V) с вершинами и и V в 8-смежности, проходящая вблизи геометрического центра линии, причем для каждой вершины Е (и, V) существует ровно две смежные с ней вершины р2 и р3, при этом вершины р2 и р3 несмежные.

Определение 3. Окончанием называется такая вершина скелета, что для

вершины существует ровно одна смежная с ней вершина р2.

Определение 4. Разветвлением называется такая вершина скелета, что для вершины существует ровно три смежные с ней вершины р2, р3 и р4, при этом любые две вершины из множества {р2, р3, р4} попарно несмежные.

Скелетизация опирается на раскрашивание точек линий /^2) (х,у) Е {0} по правилам Р (£(х,у)), определяемым в специальной табличной форме на основе идентификатора окрестности точки в виде £(х, у) = ^ 1е1 /(г) • 2г, где /(г) принимает значение 1 для линии и 0 в противном случае; г Е I = 0..7 — номер сектора апертуры 3 х 3 по (4). Величина £(х, у) Е 0..255 и определяет ячейку в табличной форме. Согласно [3] итерационное применение правил из Р (£(х, у)) позволяет вычислить скелет линий, показанный на рис. 9. С вершин скелета как графа [4] считываются окончания и разветвления, располагающиеся в информативной области ДИ на расстоянии от границы области, не меньшем периода линий, и помещаются в список (5). Затем применяется структурная постобработка скелета [2; 8]. Частные признаки с их направлениями показаны на рис. 9, причем окончания закрашены черным цветом, а разветвления — серым.

Рис. 9. Исходное изображение, частные признаки и скелет изображения

3. Заключение

В работе предложена группа взаимосвязанных методов, обеспечивающая приемлемое качество распознавания частных признаков при жестких ограничениях на время обработки ДИ. К ним относятся: измерение и коррекция матриц

потоков, сглаживание изображения, измерение и коррекция матриц периодов линий, сегментация, бинаризация, скелетизация и считывание с вершин скелета частных признаков. Построение матриц потоков основано на тензорном анализе простых окрестностей, а матриц периодов линий — на автокорреляционной функции. Общее время обработки изображения составляет приблизительно 100 мс (Intel Pentium 4 CPU 3.0 ГГц).

Обработка опирается на операции свертки, что с учетом временных характеристик позволяет перенести ее на целевые платы TMS или процессоры DSP [5] и использовать встроенные в них операции свертки. Последнее позволяет реализовать простые портативные биометрические системы, работающие в реальном режиме времени.

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

Список литературы

1. Гонсалес, Р. Цифровая обработка изображений / Р. Гонсалес, Р. Вудс ; пер. с англ. под ред. П. А. Чочиа. — М. : Техносфера, 2006. — 1072 с.

2. Гудков, В. Ю. Методы первой и второй обработки дактилоскопических изображений : монография / В. Ю. Гудков. — Миасс : Геотур, 2009. — 237 с.

3. Гудков, В. Ю. Новая технология формирования скелетов дактилоскопических изображений / В. Ю. Гудков [и др.] // Методы, алгоритмы и программное обеспечение гибких информационных технологий для автоматизированных идентификационных систем : сб. науч. ст. — Минск : БГУ, 1999. — C. 71-82.

4. Новиков, Ф. А. Дискретная математика для программистов / Ф. А. Новиков. —

3-е изд., перераб. и доп. — СПб. : Питер, 2006. — 384 с.

5. Сергиенко, А. Б. Цифровая обработка сигналов / А. Б. Сергиенко. — СПб. : Питер, 2002. — 608 с.

6. Яне, Б. Цифровая обработка изображений ; пер. с англ. / Б. Яне. — М. : Техносфера, 2007. — 584 с.

7. Bolle, R. M. Guide to biometrics / R. M. Bolle [et al.]. — N.-Y. : Springer-Verlag, 2004. — 368 p.

8. Maltoni, D. Handbook of fingerprint recognition / D. Maltoni [et al.]. — N.-Y. : Springer-Verlag, 2009. — 494 p.