Способ распознавания отпечатков папиллярных узоров

 

Изобретение относится к методу распознования и кодирования отпечатков папиллярных узоров. Повышение достоверности идентификации отпечатков пальцев достигается за счет последовательного вычленения потоков особенностей из общей структуры потоков папиллярных линий. 5 з. п. ф-лы, 16 ил.

Изобретение относится к методам распознавания и кодирования отпечатков папиллярных узоров, применяемым в автоматизированных дактилоскопических информационных системах системах идентификации личности, сравнения отпечатков и системах ограничения доступа.

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

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

Существует два основных подхода для определения папиллярного узора.

1. Методы, основанные на анализе трассировки кода линий (см. Pattern Recognition, vol. 25, N 2, р.р. 139-153, 1992). В этих методах отпечаток представляется набором непрерывных тонких линий. Недостатком этих методов является высокая чувствительность к качеству изображения из-за того, что в неясных местах линии либо имеют прерывистый характер, либо вообще не просматриваются и невозможно надежно проследить ход линий.

2. Методы, основанные на анализе потоков папиллярных линий (Pattern Recognition, vol. 17, N 3, р.р. 295-303, 1984). В этих методах отпечаток представляется непрерывным полем касательных к потоку папиллярных линий. Слабостью этих методов является наличие ложно определенных особенностей из-за того, что в неясных местах случайным образом реализуются структуры потоков, напоминающие структуры потоков вблизи особенностей. Ослабить влияние шумов можно увеличением размера области, которая определяет направление потока в точках разбиения, но тогда проявляется эффект взаимного экранирования близкорасположенных особенностей, приводящий к пропуску указанных особенностей.

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

Известен способ формирования признаков для распознавания сегментированных текстурных изображений, заключающийся в выделении на изображении с помощью бинарной маски структурных фрагментов изображения, формировании пространственного фильтра с помощью первого преобразования Фурье, фильтрации сформированного изображения однородной мелкой структуры с выделением фрагментов изображения, выполнении второго преобразования Фурье, измерении координат всех зарегистрированных сигналов взаимной корреляции относительно сигнала автокорреляции и формировании из них последовательности признаков (авт. св. СССР N 1374260, кл. G 06 K 9/00, опублик. 1988).

Наиболее близким к предлагаемому является способ сравнительного исследования дактилоскопических отпечатков, заключающийся в кодировке участков с характерными признаками и сравнении кодов исследуемого отпечатка с кодами эталонного отпечатка (авт. св. СССР N 114460, кл. G 06 K 9/46, опублик. 1958).

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

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

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

Изображение папиллярного узора сканируется при помощи цифровой камеры или сканера. Разрешение сканирования подбирается таким образом, чтобы самые тонкие папиллярные линии содержали не менее трех отпечатков. Количество уровней серого определяется требованием различности изображения во всех местах, т. е. определяется качеством изображения. Сканирующее устройство формирует массив элементов изображения i строк, j столбцов.

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

Вблизи особенностей направление потока изменяется на расстоянии одного межгребневого расстояния, поэтому направление потока в каждой точке отпечатка должно определяться в окрестности точки размером, соизмеримым с межгребневым расстоянием. Большой размер окрестности приводит к неопределенности направления потока вблизи особенностей, а меньший размер увеличивает разброс в определении направления, обусловленный наличием на изображении дефектов и шумов различного характера. В целях сокращения объема вычислений направление потока определяется не в каждой точке, а с шагом по i и по j, равным n, что определяет максимальную ошибку в определении координат особенностей в пределах n/2 (половина папиллярной линии). Такая ошибка является приемлемой, поскольку всегда существует неопределенность в положении особенности такого же порядка.

В каждой точке изображения определяется градиент яркости В; G(i, j)=grad B=(Bx(i, j), Bj(i, j)) i=1.500 Bx(i, j)=B(i, j+1)-B(i, j-1) j=1.500 By(i, j)=B(i-1, j)-B(i+1, j) Индекс i увеличивается сверху изображения вниз (строка изображения), индекс j слева направо (столбец изображения).

Направление вектора изображения определяет направление папиллярной линии, а именно направление папиллярной линии U(i,j) определяется следующим образом: u(i,j) arctg +90° -90° ≅ arctg ≅ 90° 0<U(i,j) ≅ 180^o Также определяется величина градиента А(i,j), как сумма абсолютных значений Вх(i,j) и Вy(i,j) A(i,j)=mod Bx(i,j)+mod By(i,j) i=1,500, j=1, 500
В точках разбиения k, l (k=1,100, l=1,100) определяется направление папиллярных линий, для чего для каждой точки разбиения k, l в ее расширенной окрестности 9х9 строится гистограмма Нk,l распределения направлений U(i, j) с учетом величины градиента А(i, j). Гистограмма определяется с учетом величины градиента для того, чтобы исключить влияние той части изображения, которая не относится к границам папиллярных линий и не содержит полезной информации.

9 9
Нk,l=i=1 j=1 A*(i,j) n=0,35 (с шагом 5^о)
А*(i,j) это те А(i,j), для которых U(i,j)/5=n.

Направление U(k,l) в точках разбиения k, l определяется по максимальной сумме в пяти соседних разрядах гистограммы,
Q(k,l)=max(H_k,l(n-2)+H_k,l(n-1)+H_k,l(n)+
+H_k,l(n+1)+H_k,l(n+2))
n=0,35
Индекс n закольцован, так как направление 185^о идентично направлению 5^о, и поэтому:
Н_k,l(-2)=H_k,l(34)
Hk,l(-1)=H_k,l(35)
H_k,l(36)=H_k,l(0)
H_k,l(37)=H_k,l(1)
Полученная картина потоков (фиг. 3) искажена шумами, обусловленными дефектами исходного изображения различного характера (фиг. 2). Для уменьшения влияния шумов используется метод релаксации потоков, состоящий в том, что направление потока в каждой точке заменяется на значение, подсчитанное из значений соседей.

В точках разбиения k, l (по прежнему k, l=1,100) вычисляется весовой коэффициент W(k,l) направления в каждой точке из среднего отклонения направления в этой точке от направлений соседей:
W(k,l) 90- abs(Q(i)-Q(o))
В качестве Q(i) выбирается такое значение, чтобы abs(Q(i)-Q(0)) было меньше 90^о, т.е.

если Q(i)-Q(O)>90^о, то Q(i)=Q(i)-180^o
если Q(i)-Q(O)<90, то Q(i)=Q(i)+180^o
В качестве нового направления берется такое направление, чтобы сумма квадратов отклонений нового направления от направлений соседей, с учетом веса соседей, была минимальна, т.е. производная равнялась нулю:
(W(i)·Q(i)-Q(c))² 0 (1)
Здесь Q(i) такое, что
если Q(i)-Q(c)>90^о, то Q(i)=Q(i)-180^o
если Q(i)-Q(c)<90<SUP>оо
Q(c) это Q(i) с максимальным Q(i), i=0,B.

Из (1) следует, что новое значение Q*(k,l) равно:
Q^*(k,l)
Номер элемента 0 относится к текущему индексу (k,l)
I к индексу (k-1, l-1)
2 к индексу (k-1, l)
3 (k-1, l+1)
4 (k, l+1) и т.д. (см. фиг. 4).

Эта процедура применяется к направлению потоков два раза, позволяя уменьшить влияние шумов (фиг. 5). Большее количество итераций нежелательно, поскольку наряду со сглаживанием шумов произойдет небольшое изменение картины потоков и точность алгоритма снизится.

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

W(k,l) 90 abs(Q(i)-Q(o)),
Номер элемента О относится к текущему индексу (k,l)
1 к индексу (k-2, l-2)
2 (k-2, l-1)
3 (k-2, l)
4 (k-2, l+1) и т.д. (см. фиг. 6).

Полученные значения весов усредняются по соседям в области 5х5.

W(k,l) W(K-2+i,l-2+j)
Устанавливается порог W1=70, превышение которого величиной W(k,l) указывает на то, что текущая точка относится к области ровного потока, и, следовательно, не может быть особой точкой. Все остальные точки потенциально могут быть особыми. На фиг. 7 потенциально особые точки объединены в области с черным цветом. Все дальнейшие операции производятся только с точками из этих областей. Для отпечатков высокого качества такие области состоят из близких окрестностей особых точек, что определяет высокую вычислительную эффективность метода. Для отпечатков плохого качества указанная область распространяется на весь отпечаток, что также естественно, поскольку не существует простых решений для сложной задачи.

Особые точки папиллярного узора отличаются от обычных тем, что при обходе особой точки по замкнутому контуру в направлении против часовой стрелки происходит разворот касательной к потоку папиллярных линий
D=sum(abs(Q(i)-Q(i-1)), i=0, 1, 8, Q(-1)= Q(8)
D=0^o неособая точка
D=180^o петля
D=-180^o дельта
D=360^o завиток (см. фиг. 8)
Для аппроксимации потоков папиллярных линий вблизи особой точки используется функция arg(Z), имеющая значение D=360.

aD=1е
Fz=arg(Z)+const, D=360^o,
Каждая из функций Fp, Fd, Fz определяет направление касательной к потоку папиллярных линий вблизи соответствующих особых точек. Вид этих функций приведен на фиг. 6.

Изменение const в функциях Fp, Fd, как видно из фиг. 9 приводит к развороту картинки вокруг оси, а изменение в функции Fz изменяет картинку таким образом, что реализуется весь возможный спектр конфигураций завитков (фиг. 9).

Сравнивая фиг. 1 и фиг. 9, можно видеть, что подбором значений const можно получить хорошее приближение реально существующих потоков папиллярных линий вблизи особых точек.

Описанное свойство функций Fp, Fd, Fz используется для поиска особых точек папиллярного узора. Если из направлений потоков вблизи особой точки вычесть соответствующую функцию из набора Fp, Fd, Fz, то в этой окрестности получится ровный поток, т.е.

Q(i)-F(i)=const, для всех точек окрестности особой точки.

Следующим шагом метода является нахождение областей, в которых расположены особые точки. Для каждой точки областей, которые могут потенциально содержать особые точки области, отмеченные на фиг. 7 черным цветом, вычисляется высокая функция Wp, Wd, Wz следующим образом:
Wp=sum(90^o-abs(Qp(i)-Q(i)))
Wd=sum(90^o-abs(Qd(i)-Q(i)))
Wz=sum(90^o-abs(Qz(i)-Q(i)))
i=0,1,2,L-1, L=l+1
Значение const, входящее в функции Qp, Qd, Qz выбирается из гистобраммы Н(n) отклонения Qp(i), Qd(i), Qz(i) от Q(i):
H(n) (Q^*(i)-Q(i)), n 0, 35
Q*(i) те Qt(i), для которых Qt(i)-Q(i))/5=n,
Qt одна из функций Qp, Qd, Qz.

Значение const определяется по максимальной сумме в пяти соседних разрядах гистограммы.

Здесь необходим разумный компромис при выборе размера l окрестности точки, в которой определяются функции Wp, Wd, Wz. Слишком большой размер приведет к плохой аппроксимации функциями Wp, Wd, Wz реально существующих потоков папиллярных линий, увеличит взаимное влияние близких особенностей, а слишком маленький подчеркнет влияние шума. Тем не менее существует оптимальный размер, который определяется природой папиллярных узоров. Две рядом расположенные особенности должны быть разделены, как минимум, одной папиллярной линией, т. е. максимальное расстояние составит около четырех n, поэтому хорошим выбором для l является 11.

На фиг. 10 черным цветом обозначены области, которые содержат петли, а на фиг. 11 области, которые содержат дельты. Аналогичная картина получается для случая, когда узор содержит завиток. Область черного цвета является областью высоких значений весовых функций Wp, Wd, Wz.

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

Вычленение начинается с особенности, имеющей максимальное значение весовой функции среды функций Wp, Wd, Wz. Из общей структуры потоков (фиг. 5) вычитается соответствующая функция потока папиллярных линий из набора Qp, Qd, Qz. В получившейся структуре потоков значение функций Wp, Wd, Wz изменяется, но изменяется только в окрестности той особенности, которую вычли из общей структуры потоков. Поэтому значение функций Wp, Wd, Wz в этой окрестности пересчитывается. Если в такой особенности была одна особенность, то после ее вычленения пересчитанные функции Wp, Wd, Wz будут иметь небольшие значения и, соответственно, других особенностей в этой области обнаружено не будет. Вышеописанная процедура продолжается до тех пор, пока хотя бы одна из функций Wp, Wd, Wz превышает установленный порог Ws. На фиг. 12, 13, 14, 15 показаны реализующиеся структуры потоков папиллярных линий в процессе вычленения особенностей узора фиг. 5, а на фиг. 16 показаны соответствующие особенности. Последним узором после вычленения особенностей всегда является классический дуговой узор, что указывает на то, что реальные папиллярные узоры могут быть представлены с хорошей точностью суммой классического дугового узора и функций Qp, Qd, Qz. Для дельт и завитков фиксируются координаты i, j, а для петель в дополнение к этому фиксируется направление f, указанное на фиг. 13. Направление определяется по значению const функции Qс, которая реализовалась при максимальном значении Wc
f=2 сonst.

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

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

Как уже было отмечено, реальный узор представляется суммой классического дугового узора и функций Fp, Fd, Fz. В дуговом узоре разворот потока происходит плавно, поэтому для аппроксимации поведения потока папиллярных линий в небольшой окрестности используется сумма функций Fp, Fd, Fz особенностей.

t ( ·arg(Z-Zp(i))+
Здесь: Np количество центров;
Nd количество дельт;
Nz количество завитков;
мнимая единица,
Zp(i) Xp(i)++Yp(i)
Хр(i) координата Х i-го центра;
Yp(i) координата Y i-го центра;
Zd(i) Xd(i)++Yd(i)
Хd(i) координата Х i-ой дельты;
Yd(i) координата Y i-ой дельты;
Zz(i) Xz(i)++Yz(i)
Хz(i) координата Х i-го завитка;
Yz(i) координата Y i-го завитка.

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

W(k,l) 90°- ·sum abs(Q_i-Q_o) i=1,2,80
По аналогии с тем, как делалось раньше, новое значение направления потока Q*(k,l) получается следующим образом:
Q
Как и прежде, значение индекса О относится к центральному элементу окрестности.

В качестве меры отличия отфильтрованной и исходной зашумленной структуры потоков используется следующая величина:
Wt 90°- abs(Q^*(i)-Q(i))
Здесь центральным элементом окрестности является особенность.

Q* относится к отфильтрованной структуре;
Q относится к изначальной структуре.

Величина Wt однозначно определяет надежность определения особенности.

Формула изобретения

1. СПОСОБ РАСПОЗНАВАНИЯ ОТПЕЧАТКОВ ПАПИЛЛЯРНЫХ УЗОРОВ, заключающийся в сканировании изображения папиллярного узора, выделении характерных признаков изображения с последующим их кодированием, формировании массива выделенных характерных признаков, сравнении их кодов с кодами выделенных характерных признаков сравниваемых отпечатков папиллярных линий, отличающийся тем, что при формировании массива выделенных характерных признаков определяют направление потока папиллярных линий в окрестности точки, соизмеримой с межгребневым расстоянием, производят сглаживание картины потоков заменой значения направления потока на среднее из значений направлений потоков соседних точек, определяют вероятное положение характерных признаков папиллярного узора, определяют функции характерных признаков папиллярного узора и производят последовательное вычленение характерных признаков папиллярного узора, начиная с признака с максимальным значением весовой функции.

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

3. Способ по п. 1, отличающийся тем, что при формировании массива выделенных характерных признаков измерения производят в участках папиллярных линий со средней толщиной.

4. Способ по п. 1, отличающийся тем, что при определении вероятного положения характерных признаков папиллярных узоров папиллярный узор разбивают на зоны с характерными признаками, вычисляют весовой коэффициент направления потока папиллярного узора в каждой точке разбиения по среднему отклонению направления потока этой точки от направлении потоков соседних точек, устанавливают порог весового коэффициента, выделяют особые точки, весовой коэффициент направления потока которых не превышает порогового значения.

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

6. Способ по п. 1, отличающийся тем, что при определении особой точки производят аппроксимацию направлений потоков папиллярных линий в окрестности этой точки, полученную структуру потоков сравнивают с исходным отпечатком папиллярных линий.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8, Рисунок 9, Рисунок 10, Рисунок 11, Рисунок 12, Рисунок 13, Рисунок 14, Рисунок 15, Рисунок 16