Offline Signature Verification using GED on Labelled Graphs

Abstract

Grafer er kraftige representasjonsverktøy som kan brukes til oppgaver som offline signaturverifisering. Selv om grafer har vært tidlig introdusert, er det bare noen få av de nyeste systemene som tar i bruk grafer, og ingen av dem tar i bruk grafer med vektet kanter. Mens de fleste moderne systemer bruker statistisk mønstergjenkjenning for signaturverifisering, er grafer fleksible ettersom de tillater modellering av lokale funksjoner, i tillegg til den globale strukturen til signaturen. Målet for denne oppgaven er å lage et grafbasert offline signaturverifiseringssystem ved å ta i bruk grafer med vektet kanter og GED. Vektene vil gi mulighet til å lagre ekstra informasjon i grafen som vanligvis ikke ville vært mulig, et eksempel på dette kan være lengden på linjene i signaturen. Grafene blir laget fra forhåndsbehandlet signaturbilder, og sammenlignet med GED. GED er en måte å sammenligne to grafer, og vil i denne oppgaven brukes til å måle likhetene mellom to signaturer. Den nøyaktige beregningen av GED er en del av NP-harde problemer, og derfor vil jeg i denne oppgaven bruke en kubikk-tid bipartite tilnærming til GED, tilpasset til å håndtere grafer med vektet kanter. Denne oppgaven vil presentere måter å teste, samt optimalisere forskjellige parametere for dette systemet, og undersøke dets ytelse på datasettet MCYT-75. Resultatene sammenlignes med andre toppmoderne systemer som bruker samme datasett. Eksperimentene viser at det foreslåtte systemet ikke gir noen lovende resultater når det sammenlignes med de nyeste systemene. Oppgaven forklarer imidlertid hvorfor dette kan være, og foreslår forbedringer som kan gjøres.

Graphs are powerful representation tools that can be used to benefit tasks like offline signature verification. Although introduced early on, only a few of the current state-of-the-art systems rely on graph-based representation, and none of them uses graphs with labelled edges. While most state-of-the-art approaches to signature verification rely on statistical pattern recognition, graphs are flexible as they allow modelling of local features, as well as the global structure of the signature. This thesis aims to create a graph-based offline signature verification system with the use of graphs with labelled edges and GED. The edge labels used will allow additional information of the signatures, such as the length of a line to be shown in the graph. The graphs will be extracted from pre-processed signature images, and compared using GED. GED is a way to error-tolerantly compare two graphs and will in this thesis be used to measure the similarities of two signatures. The computational complexity of the exact computation of GED is high, therefore in this thesis the cubic-time bipartite approximation of GED will be used and adapted to handle edge labels. This thesis will put forward ways of testing, as well as optimising different parameters of this system, and investigate its performance on the data-set MCYT-75. The results is compared to other state-of-the-art systems using the same data-set. The experiments displays that the proposed system does not yield any promising results when compared with the state-of-the-art. However, the thesis explains why this is and suggests improvements that can be made.