inż. Patryk Lijewski

inż. Szymon Knieć


Klasyfikacja odcisków palców





Projekt realizowany w ramach laboratorium z przedmiotu rozpoznawanie obrazów prowadzonego przez dr inż. Krzysztofa Krawca
  • Autorzy:

    Szymon Knieć, Patryk Lijewski są studentami czwartego roku informatyki (specjalność ISWD) na Politechnice Poznańskiej.

  • Cel projektu:

    • Ogólny cel:  Celem projektu jest stworzenie systemu klasyfikującego podany na wejsciu obraz odcisku palca do jednej z podstawowych kategorii.
    • Kryteria oceny:  Głównym kryterium będzie trafność klasyfikacji, przydzielenie odcisku do właściwej klasy.
    • Dane:  Dane stanowią dostepne bazy danych obrazów odcisków palców. W naszym projekcie wykorzystamy obrazy o rozmiarach 300x300.

  • Wprowadzenie:

               Odciski palców są charakterystyczną cechą każdego człowieka identyfikującą go w sposób jednoznaczny tak jak np. numer PESEL. Każdy człowiek ma unikalny wzór odcisków palców. Pondto ten wzór nie zmiena sie przez całe życie. Dlatego właśnie odciski palców są jedną z najbardziej wiarygodnych metod indentyfikacji ludzi. Pierwsze próby idenyfikacji ludzi na podstawie odcisków palców miały miejsce już na przełomie XIX i XX wieku. Taka identyfikacja może mieć zastosowanie przy weryfikacji dostępu (ang. access control) lub w trakcie czynności śledczych np. policji (ang. crime investigation). W zależności od podejścia wyróżnia się 5 lub 6 podstawowych klas odcisków palców:
    • left loop,
    • right loop,
    • twin-loop,
    • whorl,
    • arch,
    • tented arch.
    Co prawda sklasyfikowanie danego odcisku do jednej z klas nie jest równoważne z identyfikacją danej osoby, jednak może to w dużym stopinu ułatwić przeszukiwanie bazy danych osób zawężonej wtedy do jednej żądanej klasy.

  • Przykłady klas odcisków palców:

    ARCH
    TENTED ARCH

    LEFT LOOP
    RIGHT LOOP

    TWIN LOOP
    WHORL

  • Próba osadzenia projektu w dziedzinie rozpoznawania obrazów:

               Sądzimy, że rozsądne będzie podejście wykorzystujące metodę z klasy globalnych metod rozpoznawiania obrazu. Proponujemy to gdyż wymagane będzie przeglądanie całego obrazu w poszukiwaniu punktów charkterystycznych, a nie tylko jego fragmentu. Idąc dalej można stwierdzić, że nasze podejście będzie metodą wnioskującą/rozpoznającą na podstawie cech obliczonych z obrazu (ang. feature-based method). Sugeruje to również, że będzie ona działała w sposób pośredni. Analizowany obraz zostaje sprowadzony do pewnej postaci przejściowej, na podstawie której będzie prowadzone wnioskowanie. Tak więc konieczne będzie stworzenie modułu ekstrakcji cech stanowiących (niejawną) reprezentacje wewnętrzną naszego problemu. Niewątpilwą zaletą tego podejścia jest modułowa konstrukcja całej aplikacji. Pewną wadą proponowanego podejścia jest brak elementów uczenia.

  • Zastosowane podejście:

               Wiadomo, że w każdym odcisku można wykryć tzw. punkty core i delta. Wiele źródeł podaje, że każda z podstawowych klas posiada określoną liczbę tych punktów. I tak np. klasa arch posiada ani jednej pary tych punktów, gdy znajdujemy pare tych punktów to wiemy, że jest to klasa tented arch lub loop itd. Ostatecznie wątpliwości, do której klasy przydzielić badany odcisk rozwiązuje wzajemne położenie znalezionych punktów.

    Algorytm:

    • Preprocesing:
                 Dla każdego piksela obliczamy średnią jasność v w sąsiedztwie 5x5. Jeżeli wartość piksela jest mniejsza niż v to ustawiamy ją na 0. W przeciwnym wypadku wartość ta pozostaje bez zmian. W ten sposób otrzymujemy przetworzony obraz P.

    • Directional images:
                 W tym punkcie chcemy wyznaczyć kierunek każdego z pikseli z obrazu P. Obliczamy kierunek dla każdego piksela P(i,j) poruszając się maską 5x5, ze środkiem z punkcie c=P(i,j), po całym obrazie P. Sprawdzamy różnicę pomiędzy badanym pikselem P(i,j) a pikselami P(im,jm) dla m=1,2,3,4 gdzie im={i+2, i+2, i, i-2} oraz jm={j, j+2, j+2, j+2} tak jak to zaznaczono na masce poniżej:
      3    2    1
               
      0    c    0
               
      1    2    3

      Wyznaczamy minm|P(i,j)-P(im,jm)| i m dla, którego różnica jest najmniejsza przyjmujemy za kierunek naszego piksela. W ten sposób otrzymujemy obraz V reprezentujący kierunek każdego piksela P(i,j). Kolejnym krokiem jest podzielenie obrazu V na bloki q x q (u nas 5x5) i obliczenie histogramu dla każdego z bloków. Dominująca wartość odpowiada kierunkowi danego bloku. Tę wartość konwerujemy na 0, 1, 2 lub 3, które odpowiadają kątom 0o, 45o, 90o, 135o W ten sposób otrzymujemy obraz S ,będący zredukowanym obrazem V, o rozmiarach M/q x N/q. Dzięki temu zredukujemy złożoność dalszych obliczeń.

    • Punkty core i delta:
                 Punty core i delta znajdujemy sprawdzając prawdziwość odpowiednich nierówności.
      Jeżeli punkt spełnia poniższe nierówności to jest możliwym punktem delta.
      S(i-1,j+1)<= S(i,j)<S(i+1,j+1) , S(i-1,j+1)<90o oraz S(i+1,j+1)>90o

      Natomiast jeżeli punkt spełnia poniższą nierówności to jest możliwym punktem core.
      45o=<(S(i,j) – S(i,j-1)) <=135o

      Kolejnem krokiem jest weryfikacja punktów kandydatów na podstawie ich sąsiedztwa.
      Dla punktów delta sąsiedztwo punktu musi spełniać następujące warunki:
      S(i-1,j)<=90o , 90o <=S(i+1,j) , S(i,j+1)<45o oraz 45o<=S(i, j-1)<=135o

      Dla punktów core sąsiedztwo musi spełniać następujące nierówności:
      (S(i-1, j-1) – S(i,j-1))<45o , 90o<(S(i+1, j-1) – S(i, j-1))

    • Klasyfikacja: 
      • Jeżeli odcisk nie zawiera punktów core i delta to jest to klasa ARCH.
      • Jeżeli odcisk zawiera po jednym punkcie core i delta to jest to klasa TENTED ARCH, LEFT LOOP albo RIGTH LOOP.
      • Jeżeli odcisk zawiera dwie pary punktów core i delta to jest to klasa WHORL lub TWIN LOOP.
      • Klasy TENTED ARCH i LOOP odróżniamy poprzez sprawdzenie wzajemnego położenia znalezionych punktów core i delta. Jeżeli względem siebie umiejscowione są one horyzontalnie to jest to TENTED ARCH, a w przeciwnym razie LOOP.
      • LEFT LOOP odróżniamy od RIGHT LOOP poprzez badanie, po której stronie delty znajduje się core. Jeżeli core leży po prawej stronie punktu delta to jest to klasa RIGHT LOOP, a gdy po lewej stronie to jest to LEFT LOOP.
      • Klasy WHORL i TWIN LOOP odróżniamy badając wzajemne położenie punktów core orez delta. Jeżeli punkty core leżą względem siebie w poziomie oraz punkty delta leżą względem siebie także w poziomie to jest to klasa WHORL, a w przeciwnym razie klasa TWIN LOOP


  • Napotkane trudności, problemy:

    • Problemy:  Jak w większości projektów bazujących na danych obrazowych będzie wymagane odszumienie obrazów wejściowych. W przypadku naszego projektu tego typu wady wynikają zapewne z niedoskonałości procesu akwizycji odcisków palców.
    • Środki zaradcze:  Zastosowany przez nas preprocessing w postaci "wygładzania" i uśredniania obrazów powinnien dać zadowalające rezultaty.

  • Środowisko realizacji projektu:

    Projekt będzie realizowany w środowisku Microsoft Visual C++ z wykorzystaniem biblioteki CImage.

  • Możliwości rozbudowy:

               Nasz projekt można w przyszłości rozbudować o moduł współpracujący z bazą danych. Można także stworzyć moduł, który na podstawie zidentyfikowanych punktów charakterystycznych oblicza funkcję podobieństwa badanego odcisku z odciskami w bazie danych i idenftyfikuje właściciela badanego odcisku.

  • Bibliografia:

    • 1. Meltem Ballan, Brian L. Evans, F. Ayhan Sakarya; A Fingreprint Classification Technique Using Directional Images
    • 2. Anil Jain, Shatath Pankanti; Fingerprint Classification and Matching
    • 3. Lin Hong, Anil Jain; Integrating Faces and Fingerprints for Personal Identification
    • 4. Krzysztof Krawiec; Wykłady z przedmiotu Rozpozanwanie obrazów