Nowe numeryczne metody rozpoznawania odcisków palców, oparte na matematycznym opisie przebiegu linii papilarnych i powstawania minucji
Wzory linii papilarnych od dawna były obiektem zainteresowania ludzi, dzięki czemu w dużej mierze zostały zbadane i opisane. Niestety, ujęcie tego tematu wypracowane przez daktyloskopię dla potrzeb głównie kryminalistyki nie daje się łatwo sformalizować matematycznie. W praktyce oznacza to, że klasyczne metody rozpoznawania palców nie nadają się bezpośrednio do implementacji w postaci algorytmów komputerowych. Pomimo tego oczywistego faktu autorzy wielu istniejących rozwiązań - znanych i opisywanych w literaturze sposobów numerycznej obróbki odcisków palców, próbowali najczęściej wprost, ewentualnie z małymi odstępstwami, zastosować klasyczne formuły daktyloskopijne. Postępowanie takie doprowadziło do powstania bardzo skomplikowanych programów, które analizują obraz palca przy użyciu wyrafinowanych metod, przede wszystkim tzw. morfologii matematycznej. Tak skomplikowane rozwiązanie zagadnienia uniemożliwia tworzenie prostych programów, niewrażliwych na błędy danych wejściowych (patrz [1]).Wydaje się, że jednym z podstawowych problemów utrudniających konstruowanie algorytmów analizy obrazów odcisków był brak dobrego modelu matematycznego struktur linii papilarnych. Aby stworzyć taki model należy z jednej strony zrozumieć istotę zjawiska, z drugiej natomiast opracować metody jego niezawodnej i łatwej algorytmizacji. Za punkt startowy do naszych prób stworzenia takiego modelu wybraliśmy zagadnienie syntezy wzoru linii papilarnych - głównie minucji. Wszystko wskazywało bowiem na to, że to jego opanowanie będzie kluczem do rozwiązania pozostałych problemów.
W ciągu kilku lat przeprowadziliśmy wiele doświadczeń numerycznych, co ostatecznie zaowocowało stworzeniem odpowiedniego modelu palca. Na jego podstawie powstał oryginalny algorytm syntezy obrazów linii papilarnych, a zwłaszcza wszelkich możliwych układów tzw. minucji. Model ten pozwala w nowy sposób spojrzeć na cyfrowy zapis odcisku palca, który nie jest w nim tylko zbiorem piksli, lecz pewną (dość prostą) dwuwymiarową funkcją o bardzo ciekawych własnościach. Umożliwia on też matematyczne skatalogowanie minucji i typów wzorów, a to oznacza rewolucję w metodach analizy, przetwarzania i kompresji obrazu odcisków palców. Poniżej przedstawiono syntetyczne obrazy najczęściej spotykanych minucji (według [2]), wraz z tabelą pokazującą naszą umowną klasyfikację numeryczną (liczba i rodzaj bifurkacji):
 |
 |
 |
 |
Rys. 1 Rys. 2 Rys. 3 Rys. 4
 |
 |
 |
 |
Rys. 5 Rys. 6 Rys. 7 Rys.8
 |
 |
 |
 |
Rys. 9 Rys. 10 Rys. 11 Rys. 12
Rys. 13 Rys. 14 Rys. 15 Rys. 16
| Rys.1 | początek lub zakończenie | L | Rys.9 | oczko pdwójne | RLRL |
| Rys.2 | rozwidlenie pojedyncze | L | Rys.10 | mostek pojedynczy | RL |
| Rys.3 | rozwidlenie podwójne | LL | Rys.11 | mostek bliźniaczy | RLLR |
| Rys.4 | rozwidlenie potrójne typ 1 | LLL | Rys.12 | odcinek | RL |
| Rys.5 | rozwidlenie potrójne typ 2 | LLL | Rys.13 | punkt | RL |
| Rys.6 | rozwidlenie potrójne typ 3 | LLL | Rys.14 | linia przechdząca | LR |
| Rys.7 | haczyk | RL | Rys.15 | skrzyżowanie | LR |
| Rys.8 | oczko pojedyncze | RL | Rys.16 | styk boczny | RL |
Ze względu na komercyjny potencjał metody nie możemy dzisiaj jeszcze opisać szczegółowo metod syntezy, ale dla pokazania jej możliwości udostępniamy program demonstracyjny Fingerprint Creator (wersja dla DOS; wersja dla Windows) generujący szeroką gamy wzorów linii papilarnych. Użytkownik tego programu może sam ustawiać m.in. takie parametry syntezy jak:
- typ wzoru (koncentryczny, łukowaty, pętlicowy)
- ilość minucji
- gęstość linii papilarnych
- szerokości linii papilarnych
- przesunięcie i rotacja centrum wzoru
Program w wersji dla DOS'a umożliwia zapis wygenerowanego wzoru w jednym z trzech formatów (a dwóch w wersji dla Windows):
| Format danych |
Wielkość danych (bajty) |
Rozszerzenie pliku danych |
| bitmap jednobitowy |
8222 |
*.bmp |
| macierz "gołych" bajtów |
65536 |
*.fin |
| zbiór parametrów syntezy |
6 |
*.par (*.fpp dla Windows) |
Na uwagę zasługuje ostatni format, a konkretnie wielkość zbioru, jaki przy tym powstaje. Stworzona przez nas metoda syntezy potrzebuje zaledwie 6 bajtów, aby wygenerować jeden z kilku milionów obrazów linii papilarnych! Co prawda ta wersja programu nie potrafi generować wszystkich możliwych wzorów, ale sądzimy, że wkrótce uda się to osiągnąć. Zakładając (z nadmiarem), że liczba możliwych odcisków ludzkich palców może osiągnąć 100 bilionów, można łatwo wyliczyć, że minimalna ilość bajtów potrzebna do ponumerowania wszystkich tych wzorów nie przekroczy 6, ponieważ 100 bilionów = 1014 < 2566 = 6 bajtów. Jak łatwo zauważyć, stworzenie katalogu ze wszystkimi możliwymi wzorami i odwoływanie się do takiej klasyfikacji w praktyce jest nie realizowalne. Możliwe jest natomiast użycie numeru palca, jeśli będzie on jednoznacznym parametrem algorytmu syntezy. Poniżej przedstawiono przykładowe, syntetyczne obrazy palców wygenerowane przez program Fingerprint Creator:
Podstawowym celem tworzenia modelu palca była jednak konieczność wypracowania nowych, lepszych algorytmów analizy. I rzeczywiście - znając opis matematyczny sztucznych wzorów - udało się stworzyć metodę przetwarzania i analizy obrazów prawdziwych odcisków palców. Zawiera ona algorytmy rozpoznawania minucji (w tym ich rodzaju i kierunku) wprost na nie filtrowanym, pełno dynamicznym (full gray level) obrazie palca. Ponieważ nie stosujemy binaryzacji, szkieletyzacji i tym podobnych metod, nie mamy problemów z utratą informacji zachodzącą w tych procesach, a minucje, które zostają rozpoznane, są nimi rzeczywiście w prawie 100% (klasyczne algorytmy wykrywają często dużą ilość fałszywych minucji, zdarza się że nawet znacznie ponad 50%). Dodatkowym atutem stosowanych przez nas metod analizy jest możliwość ich implementacji w postaci bardzo szybkich algorytmów. W oparciu o nie udało nam się też stworzyć bardzo efektywne metody filtracji, pozwalające na oczyszczenie linii papilarnych z wszelkich "defektów". Zastosowanie ich zmniejsza naturalną redundancję obrazu powodując, że obraz rzeczywistego palca wygląda nieco "syntetycznie", lecz nadal posiada wszystkie istotne dla jego rozpoznania topologiczne cechy oryginału.
Metoda nasza pozwala też na szeroko pojętą "inżynierię palca" na dowolne ingerowanie w strukturę obrazu. Przy jej pomocy można przykładowo umieścić dodatkowe minucje czy też linie w dowolnym miejscu w prawdziwym obrazie palca bez zmian pozostałej struktury. Można również - odwrotnie, pozbawić obraz palca kilku, lub wszystkich prawdziwych minucji. Poniżej przedstawiono przykładowy efekt działania naszego algorytmu poszukiwania minucji na ultradźwiękowym obrazie linii papilarnych. Pokazany obraz pochodzi z naszej holograficznej kamery ultradźwiękowej
Należy zaznaczyć, że stworzone przez nas metody przetwarzania działają bardzo dobrze również na innych typach obrazów i są stosunkowo mało czułe na charakter danych wejściowych. Dotychczas testowaliśmy je z dobrym skutkiem na:
- obrazach ultradźwiękowych z naszej własnej głowicy (kamery holograficznej);
- obrazach ultradźwiękowych uzyskanych przy pomocy metody mikroskopowej (skanowanie wiązką zogniskowaną);
- obrazach optycznych z wielu różnych urządzeń wykorzystujących efekt całkowitego wewnętrznego odbicia lub rozproszenia światła na powierzchni kontaktu z palcem;
- obrazach optycznych z urządzeń typu "touchless" widzących bezpośrednio powierzchnię palca;
- zeskanowanych obrazach tuszowych;
- obrazach z czytnika piroelektrycznego firmy Thomson-CSF;
- syntetycznych wzorach programu "Fingerprint Creator"
Ze względu na szczególnie efektywny sposób analizy linii papilarnych a przede wszystkim systematyczne podejście do tego zagadnienia, jesteśmy w stanie zaproponować dużo więcej niż producenci klasycznych programów do rozpoznawania palców. Jesteśmy też gotowi przystosować nasze algorytmy w przypadku innych czytników palców o szczególnym charakterze danych. W razie zainteresowania, prosimy o kontakt.
Literatura
[1] R.H. Andersen, P. Jürgensen, Fingerprint verification - For Use in Identity Verification Systems, Aalborg University, (1993)
[2] Cz.Grzeszyk, Daktyloskopia, PWN Warszawa (1992)