В текущем семестре появился в расписании предмет «Методы и средства защиты компьютерной информации», частью которого являются лабораторная работа по биометрии, а точнее по распознаванию отпечатка пальца. Так же, недавно, на Хабре была статья про устройства предназначенные для сканирования. Решил написать здесь про алгоритмы распознавания.Передо мной, как перед студентом, стоит довольно стандартная задача: верификация отпечатка пальца(сравнение с эталоном). Так как лабораторная эта, появилась только в этом году, то методического пособия по ней еще нет. Но в виду интересности задачи, я отправился к Гуглу.
Как ни странно, наиболее содержательной оказалась вторая часть статьи, указанной в топике про сканеры. В ней описано, довольно понятно, несколько алгоритмов:
1. Корреляционное сравнение
Данный подход заключается в попиксельном сравнении двух изображений, для различных сдвигов и углов поворота, на основе получившихся результатов выносят решения о совпадении. (в современных условиях не применяется, из-за высокой трудоемкости)
2. Сравнения по узору
В зависимости от требуемой точности, изображение отпечатка разбивается на области. Далее узор в каждой из областей описывается синусоидальной волной, с параметрами:
- начальный сдвиг фазы
- длина волны
- направление распространения
Данный класс алгоритмов, не требует высокого разрешения при сканировании.
3. Сравнение по особы точкам
Особые точки — это конечные точки и точки ветвления. Эти точки выделяются на обоих изображения, а далее методом их корреляционного сравнения, выносится вердикт о соответствии отпечатков.
В виду своей относительно простой реализации и скорости работы, данные алгоритмы более распространены.
Данный тип алгоритма я выбрал для реализации в лабораторной работе. Поэтому остановимся на нем подробнее.
Так как статья дала только общее представление, я продолжил гуглить. Третьей строкой выдачи стала эта презентация.
В ней довольно подробно рассказаны шаги реализации выбранного подхода.
Итак, план действий:
- бинаризация полученного изображения
- скелетизация изображения
- выделение точек
- сравнение точек
Реализацию решено было сделать на Python. Соответственно, помимо самого Python(у меня версии 2.7.1), нужна PIL(Python Imaging Library), для разбора картинки на пиксели.
Шаг 1. Бинаризация
Тут я не стал изобретать, и сделал все довольно просто, в лоб.
def binary(img):
bImg=[]
for i in range(img.size[0]):
tmp=[]
for j in range(img.size[1]):
t=img.getpixel((i,j))
p=t[0]*0.3+t[1]*0.59+t[2]*0.11
if p>128:
p=1
else:
p=0
tmp.append(p)
bImg.append(tmp)
return bImg
Если же вам потребуется иной результат, следует посмотреть темы блога «Обработка изображений», там бинаризация затрагивается довольно часто.
Шаг 2. Скелетизация
Этот шаг вызвал самое большое затруднение, так как алгоритмы гуглились сложнее всего. В итоге найдено 4 алгоритма:
- Шаблонная скелетизация (набор шаблонов 1, набор 2)
- Волновой метод (подробнее)
- Алгоритм Зонга-Суня (подробнее)
- Алгоритм Щепина
Выбран был шаблонный метод, и первый набор, так как в отличии от второго набора шаблонов, он требует всего один обход изображения. Правда для снижения уровня неточностей используется часть шаблонов из второго набора.
Шаблоны соответствуют матрице 3*3, где центральный элемент является текущим пикселем в обходе изображения.
здесь серым обозначены пиксели, цвет которых не имеет значения
Восемь первых шаблонов, являются основной частью. Четыре снизу для устранения «шума», при чем эти четыре так же могут быть повернуты на 90, 180 и 270 градусов, и ищутся вторым обходом изображния.
Если мы натыкаемся на шаблон, то центральный пиксель окрашивается в белый цвет(не принадлежит скелету). Обход продолжается, пока остаются возможности удаления.
Код этого действа разбит на несколько функций:
def tmpDelete(img): #вызов процедуры скелетизации, на входе список списков(после бинаризации)
w=len(img)
h=len(img[0])
count=1
while count!=0: #повторять пок удалялся хотя бы один пиксель
count=delete(img,w,h)
if count:
delete2(img,w,h)
def delete(img,w,h): #удаление пикселя по основному набору, возврат кол-ва удаленных
count=0
for i in range(1,h-1):
for j in range(1,w-1):
if img[j][i]==0:
if deletable(img,j,i):
img[j][i]=1
count+=1
return count
def delete2(img,w,h): #удаление пикселя по шумовому набору
for i in range(1,h-1):
for j in range(1,w-1):
if img[j][i]==0:
if deletable2(img,j,i):
img[j][i]=1
def fringe(a): #определение принадлежности 3*3 к шумам
t=[[1,1,1,1,0,1,1,1,1],
[1,1,1,1,0,1,1,0,0],
[1,1,1,0,0,1,0,1,1],
[0,0,1,1,0,1,1,1,1],
[1,1,0,1,0,0,1,1,1],
[1,1,1,1,0,1,0,0,1],
[0,1,1,0,0,1,1,1,1],
[1,0,0,1,0,1,1,1,1],
[1,1,1,1,0,0,1,1,0],
[1,1,1,1,0,1,0,0,0],
[0,1,1,0,0,1,0,1,1],
[0,0,0,1,0,1,1,1,1],
[1,1,0,1,0,0,1,1,0]]
for i in t:
if a==i:
return True
def check(a): #определение принадлежности 3*3 к основным шаблонам
t123457=[1,1,0,0,1,0]
t013457=[1,1,1,0,0,0]
t134567=[0,1,0,0,1,1]
t134578=[0,0,0,1,1,1]
t0123457=[1,1,1,0,0,0,0]
t0134567=[1,0,1,0,0,1,0]
t1345678=[0,0,0,0,1,1,1]
t1234578=[0,1,0,0,1,0,1]
t=[a[1],a[2],a[3],a[4],a[5],a[7]]
if t == t123457:
return True
t=[a[0],a[1],a[3],a[4],a[5],a[7]]
if t == t013457:
return True
t=[a[1],a[3],a[4],a[5],a[6],a[7]]
if t == t134567:
return True
t=[a[1],a[3],a[4],a[5],a[7],a[8]]
if t == t134578:
return True
t=[a[0],a[1],a[2],a[3],a[4],a[5],a[7]]
if t == t0123457:
return True
t=[a[1],a[3],a[4],a[5],a[6],a[7],a[8]]
if t == t1345678:
return True
t=[a[0],a[1],a[3],a[4],a[5],a[6],a[7]]
if t == t0134567:
return True
t=[a[1],a[2],a[3],a[4],a[5],a[7],a[8]]
if t == t1234578:
return True
def deletable(img,x,y): #получение 3*3, передача на проверку для осн.
a=[]
for i in range(y-1,y+2):
for j in range(x-1,x+2):
a.append(img[j][i])
return check(a)
def deletable2(img,x,y): #получение 3*3, передача на проверку для шумов
a=[]
for i in range(y-1,y+2):
for j in range(x-1,x+2):
a.append(img[j][i])
return fringe(a)
Шаг 3. Выделение особых точек
Тут все тривиально. Если в окрестности из 8 точек, есть только одна черная, то это конечная точка. Если же их 2 то это просто точка линии. Три — точка ветвления.
def checkThisPoint(img, x, y): #подсчет количества черных в окрестности
c=0
for i in range(x-1,x+2):
for j in range(y-1,y+2):
if img[i][j]==0:
c+=1
return c-1
def findCheckPoint(img): #формирование списков точек ветвления и конечных
x=len(img)
y=len(img[0])
branchPoint=[]
endPoint=[]
for i in range(x):
for j in range(y):
if img[i][j]==0:
t=checkThisPoint(img, i, j)
if t==1:
endPoint.append((i,j))
if t==3:
branchPoint.append((i,j))
return (branchPoint, endPoint)
Единственной проблемой было не полное избавление от шумов, что приводило к появлению отростков, которые распознавались как особые точки. Для того, чтобы их не учитывать, делалась удаление близко стоящих (10*10) точек ветвления и конечных точек.
def __removeDouble(x,y): #возвращает список элементов, у которых нет одинакового в другом списке
z=[]
for i in x:
c=True
for j in y:
if i==j:
c=False
if c:
z.append(i)
for i in y:
c=True
for j in x:
if i==j:
c=False
if c:
z.append(i)
return z
def delNoisePoint(r): #на входе кортеж (ветвление, конечные)
tmp=[]
tmp2=[]
for i in r[1]:
x=range(i[0]-5,i[0]+5)
y=range(i[1]-5,i[1]+5)
for j in r[0]:
if j[0] in x and j[1] in y:
tmp.append(i)
tmp2.append(j)
return (__removeDouble(r[0],tmp2),__removeDouble(r[1],tmp))
Шаг 4. Сравнение точек
Простой поиск точки которая попадает в окрестность 30*30 и является точкой того же типа.
def matchingPoint(r, v): #вход: кортеж точек эталона и кортеж проверяемого; выход (совпало, всего)
all=0
match=0
for i in v[0]:
x=range(i[0]-15,i[0]+15)
y=range(i[1]-15,i[1]+15)
all+=1
for j in r[0]:
if j[0] in x and j[1] in y:
match+=1
break
for i in v[1]:
x=range(i[0]-15,i[0]+15)
y=range(i[1]-15,i[1]+15)
all+=1
for j in r[1]:
if j[0] in x and j[1] in y:
match+=1
break
return (match,all)
Дополнительно:
Весь код справедлив для изображений одинакового размера(хотя работать будет и на разных).
Выводы:
1. Данная реализация проста и топорна. Возможно, дополнить ее несколькими проверками, например, смотреть углы вхождения линий в особые точки. При проверке откидывать пары уже найденных, для тех случаев, когда в окрестность попадает много точек одного типа.
2. Реализация на Python довольно медленна: скорость выполнения на моей машине совершенно не пригодна для пунктов с большим человеческим трафиком. Возможно, что использование NumPy повысило бы производительность, да и я не лучший реализатор.
3. Полностью код брать тут. Тестировалось на этом наборе.
PS Хотелось бы замечаний по коду, так как в питоне ориентируюсь слабовато. Ну и мнения тех, кто серьезно занимается дактилоскопией.
