Weryfikacja autentyczności podpisu odręcznego
Autor: Konrad Ćwiąkała
Raport z projektu: Metody i algorytmy sztucznej inteligencji
Prowadzący: dr inż. Witold Paluszyński
Data: 9 czerwca 2008r.
Cel projektu
Celem projektu było stworzenie systemu weryfikacji autentyczności podpisu odręcznego. Stworzony system miał za zadanie stwierdzić czy podany podpis w formie mapy bitowej, jest autentycznym podpisem jednej z osób znajdujących się w stworzonej bazie podpisów.
Zbieranie podpisów
Pierwszym etapem realizacji projektu było zebranie odpowiedniej ilości wzorcowych podpisów. W tym celu stworzono formularze zawierające 16 prostokątnych pól o rozmiarach 1,5 x 4 cm, w których miały zostać umieszczone podpisy. W sumie do badań wykorzystano 5 uzupełnionych formularzy. Poniżej jeden z formularzy.
Rysunek 1. Formularz po zeskanowaniu.
Wszystkie formularze zostały zeskanowane z rozdzielczością 600dpi w trybie 8-bitowej skali szarości (256 odcieni szarości). Przed przystąpieniem do wydzielenia z obrazów poszczególnych podpisów przeprowadzono operację zwiększenia kontrastu, aby podpisy były lepiej widoczne.
Rysunek 2. Formularz po zwiększeniu kontrastu.
Tak przygotowane formularze zostały następnie poddane operacjom mającym na celu wyodrębnienie z nich poszczególnych podpisów.
Przygotowanie podpisu
Znając rozkład ramek na formularzu z podpisami oraz zakładając, że podpis zawsze znajduje się wewnątrz ramki wyodrębnianie poszczególnych podpisów można było zautomatyzować. W tym celu napisano specjalną aplikację w środowisku Borland C++ Builder. Pierwszą operacją którą należało wykonać było wyodrębnienie z formularza poszczególnych pół zawierających podpisy. W praktyce wystarczyło znaleźć na zeskanowanym obrazie lewy górny róg pierwszej ramki , a ze względu na stały rozmiar ramek, oraz znane odstępy pomiędzy kolejnymi ramkami położenie kolejnych było łatwe do określenia.
Kadrowanie podpisu
Uzyskane podpisy przeważnie nie zajmowały całego obszaru przeznaczonego na podpis, co więcej mogły one znajdować się w różnych jego częściach. Dlatego też kolejnym krokiem przygotowania podpisu jego wykadrowanie. Kadrowanie podpisu ma na celu zlokalizowanie najmniejszego prostokąta zawierającego cały podpis. Cały proces prowadzono przy założeniu, że tło prostokąta jest białe, a każdy zaciemniony piksel należy do podpisu. Algorytm kadrowania wyszukiwał wewnątrz ramki najbardziej wysunięte punkty podpisu i na podstawie ich współrzędnych wyznaczał prostokąt zawierający sam podpis.
Rysunek 3. Procedura kadrowania podpisu
Normalizacja podpisu
Wykadrowane podpisy miały różne rozmiary, dlatego też zdecydowano się na znormalizowanie rozmiaru podpisu. Normalizacji dokonano przez standardowe skalowanie bitmapy do zadanego rozmiaru bez zachowywania proporcji. Wybrano rozmiar 100x100 pikseli.
Rysunek 4. Procedura normalizacji podpisu
Reprezentacja podpisu dla algorytmu weryfikacyjnego
Bitmapa o rozmiarach 100x100 pikseli zawiera zbyt wiele danych, aby móc bezpośrednio na ich podstawie zrealizować wydajny algorytm weryfikacyjny. Istnieje wiele możliwości ekstrakcji cech z obrazu. W projekcie przyjęto dwie metody statystyczne:
· Zaczernienie sektorów
· Projekcja obrazu
W pierwszej metodzie obraz należy podzielić na wybraną liczbę sektorów, a następnie dla każdego sektora wyznaczane jest średnia wartość pikseli w jego obrębie. W przypadku podpisów zdecydowano się podzielić bitmapę na 100 kwadratowych sektorów o wymiarach 10x10 pikseli. Wartości poszczególnych sektorów wpisane w jeden wektor stanowiły pierwszą cyfrową reprezentację podpisu w systemie weryfikacyjnym.
Rysunek 5. Podział podpisu na sektory i przypisanie im odpowiednich wartości
Druga metoda wykorzystuje projekcje (sygnatury) obrazu na płaszczyznę poziomą oraz pionową. Projekcja pozioma jest wektorem zawierającym sumę wartości pikseli w kolejnych kolumnach obrazu. Projekcja pionowa jest analogicznie wektorem sum wartości pikseli w kolejnych wierszach obrazu. Zarówno projekcja pozioma jak i pionowa wszystkich podpisów zapamiętane zostały w postaci cyfrowej i stanowiły kolejne reprezentacje cech danego podpisu w systemie weryfikacyjnym.
Rysunek 6. Projekcje podpisu
Obydwie metody generowały dane w postaci liczb 8-bitowych (z zakresu 0-255). Przed podaniem ich na wejście sztucznej sieci neuronowej należało je przeskalować do przedziału wartości od 0 do 1.
Uczenie sztucznej sieci neuronowej
Zarówno metoda liczenia zaciemnienia sektorów jak i poszczególne projekcje przedstawiały każdy podpis w postaci wektora 100 liczb. Dla każdej z tych trzech reprezentacji stworzono osobną sztuczną sieć neuronową. Do realizacji tego zadania wybrano sieci jednokierunkowe o sigmoidalnych funkcjach przejścia. Wszystkie trzy sieci miały identyczną architekturę tzn. posiadały po 100 neuronów wejściowych oraz po 5 neuronów wyjściowych. Pojawienie się sygnału na jednym z neuronów wyjściowych miało oznaczać przynależność podpisu do danej osoby (A..E).
Rysunek 7. Przykładowe podpisy osób biorących udział w testowaniu systemu (A..E)
Przyjęto a priori, że podpis zostaje zaklasyfikowany do danej klasy jeżeli na jednym z wyjść sieci wartość sygnału przekroczy 0,9 natomiast na wszystkich pozostałych wyjściach pozostanie mniejsza od 0,1. Poprawnie działająca sieć powinna zaklasyfikować do odpowiednich klas podpisy prawdziwe i nie klasyfikować w ogóle podpisów podrobionych.
Wyniki badań
Sieć nr 1
Pierwsza sieć uczyła się rozpoznawania podpisów na podstawie reprezentacji uzyskanej przez średnie zaciemnienie sektorów obrazu. Szereg uczący składał się z 60 wektorów (12 losowo wybranych podpisów z każdego formularza). Testowanie sieci przeprowadzono dla zestawu 20 wektorów z oryginalnymi podpisami (4 pozostałe podpisy z każdego formularza) oraz dla zestawu 20 podpisów podrobionych.
|
Podpisy oryginalne |
|||||||||||||||||||||
|
Osoba |
A |
B |
C |
D |
E |
||||||||||||||||
|
Wyjścia |
A |
0,92 |
1 |
1 |
0,98 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
B |
0 |
0 |
0 |
0 |
0,99 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
C |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0,13 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
D |
0,09 |
0 |
0,01 |
0 |
0 |
0 |
0,01 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
|
E |
0 |
0 |
0 |
0 |
0 |
0 |
0,01 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0,74 |
1 |
1 |
1 |
|
|
Podpisy podrobione |
|||||||||||||||||||||
|
Osoba |
A |
B |
C |
D |
E |
||||||||||||||||
|
Wyjścia |
A |
0,94 |
0,91 |
0 |
0,04 |
0,03 |
0,03 |
0 |
0 |
0 |
0 |
0,02 |
0 |
0 |
0 |
0 |
0 |
0 |
0,03 |
0 |
0 |
|
B |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0,01 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
C |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0,98 |
0,23 |
1 |
0,11 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
D |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0,02 |
0,99 |
0,52 |
0,98 |
0 |
0 |
0 |
0 |
|
|
E |
0,52 |
0,03 |
0,01 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0,14 |
0,89 |
0,41 |
0 |
|
Jak widać nauczona sieć bardzo dobrze poradziła sobie z zaklasyfikowaniem podpisów oryginalnych. Niestety udało się ją „oszukać” kilka razy podpisami sfałszowanymi.
Sieć nr 2
Druga sieć miała nauczyć się rozpoznawać podpisy na podstawie ich projekcji poziomej. Trenowanie i testowanie sieci przeprowadzono dla dokładnie tych samych podpisów, które wylosowano dla poprzedniej sieci.
|
Podpisy oryginalne |
|||||||||||||||||||||
|
Osoba |
A |
B |
C |
D |
E |
||||||||||||||||
|
Wyjścia |
A |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
B |
0 |
0 |
0 |
0 |
1 |
0 |
0,37 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
C |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
D |
0,56 |
0,06 |
0,74 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0,69 |
1 |
1 |
0 |
0 |
0 |
0 |
|
|
E |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0,98 |
0,92 |
1 |
1 |
|
|
Podpisy podrobione |
|||||||||||||||||||||
|
Osoba |
A |
B |
C |
D |
E |
||||||||||||||||
|
Wyjścia |
A |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
B |
0 |
0 |
0 |
0 |
0,3 |
0 |
0,04 |
0,85 |
0 |
0 |
0 |
0 |
0,9 |
0,39 |
0,97 |
0 |
0 |
0 |
0 |
0 |
|
|
C |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
D |
0,99 |
0,02 |
0 |
0,64 |
0 |
0 |
0 |
0,6 |
0,64 |
0,14 |
0 |
0,44 |
1 |
0,26 |
0,07 |
0,01 |
0 |
0 |
0 |
0 |
|
|
E |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0,31 |
0 |
1 |
|
Jak widać druga sieć radziła sobie nieco gorzej z rozpoznawaniem oryginalnych podpisów, lecz popełniła także mniej błędów przy weryfikacji podpisów sfałszowanych.
Sieć nr 3
Ostatnia sieć wykorzystywała do uczenia zestaw projekcji pionowych podpisów. Podobnie jak poprzednio trening i testowanie prowadzono przy zestawie tych samych podpisów.
|
Podpisy oryginalne |
|||||||||||||||||||||
|
Osoba |
A |
B |
C |
D |
E |
||||||||||||||||
|
Wyjścia |
A |
0 |
0,41 |
0 |
0,02 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0,08 |
0 |
0 |
|
B |
0 |
0 |
0 |
0 |
0,99 |
0,23 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
C |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
D |
0,04 |
0,02 |
0,21 |
0,37 |
0,43 |
0,98 |
0,01 |
0 |
0 |
0,01 |
0,01 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
|
E |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
|
Podpisy podrobione |
|||||||||||||||||||||
|
Osoba |
A |
B |
C |
D |
E |
||||||||||||||||
|
Wyjścia |
A |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0,01 |
0,86 |
0,16 |
0,77 |
0,44 |
|
B |
0 |
0,98 |
0 |
0,23 |
0,04 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0,05 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
C |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0,93 |
0 |
0 |
0 |
0 |
0 |
0,09 |
0 |
|
|
D |
0,02 |
0,69 |
0,89 |
0,08 |
0,16 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0,05 |
0,3 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
E |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0,99 |
0 |
0 |
0 |
0 |
0 |
0,99 |
0 |
0 |
|
Trzecia sieć zupełnie nie radziła sobie z rozpoznawaniem podpisów należących do osoby A, popełniła także wiele błędnych klasyfikacji w przypadku podpisów podrobionych.
Podsumowanie
W czasie prowadzenia testów zauważono również, że skuteczność rozpoznawania zależy w dużej mierze od powtarzalności podpisu danej osoby. Błędna klasyfikacja może być również wynikiem występowania podobieństwa pomiędzy podpisami dwóch różnych osób. Należy pamiętać, że zaprezentowane metody ekstrakcji cech obrazu nie są odwzorowaniami jednoznacznymi, i teoretycznie dwa różne obrazy mogą mieć identyczną reprezentację w systemie.
Na podstawie przeprowadzonych testów można stwierdzić, że najlepszą metodą reprezentacji podpisu odręcznego w celach weryfikacji oryginalności okazało się zaczernienie sektorów obrazu. Radziła sobie ona znacznie lepiej od metod wykorzystujących projekcje obrazu. Teoretycznie zwiększenie liczby sektorów lub mogłoby zwiększyć efektywność prezentowanej metody, jednak przeważnie sieć o większej liczbie neuronów wejściowych wymaga także większej liczby próbek uczących. W rzeczywistym systemie liczba próbek uczących (a co za tym idzie składanych podpisów) nie powinna być zbyt duża, aby nie zniechęcać ludzi do korzystania z takich rozwiązań.
Bibliografia
- R. Tadeusiewicz, "Sieci neuronowe", Warszawa, 1993;
- Diana Kalenova, “Personal Authentication Using Signature Recognition”
- J. Coetzer , “Offline Signature Verification Using the Discrete Radon Transform and a Hidden Markov Model”, 2003
- Robert Sabourin, “Off-Line Signature Verification by Local Granulometric Size Distributions”, 1997