Graph Based Signature Verification

Abstract: Handwritten signatures are widely used and well-accepted biometrics for personal authentication. Based on only a few genuine specimens, signature verification is a challenging task even for humans. Automatic verification systems are still far from human performance but their accuracy has improved significantly in the past decade, making it possible to rely on machines in some restricted cases or to support human experts.
Most of the current methods for automatic signature verification are based on feature vector representation and statistical classification, either taking into account local or global features. Known limitations of this approach include the inability to capture the global structure of the signatures and the relations between their subparts in a standardized way. Graph based representation and structural matching can overcome this limitation by providing a more intuitive, powerful, and flexible mechanism for formally representing and comparing handwritten signatures.
However, one of the main challenges in graph based pattern recognition is the high computational complexity involved in structural matching. Recently, we have introduced a promising approximation framework for graph edit distance based on substructure assignment. This framework is able to compare arbitrary graphs efficiently with cubic or, more recently, even quadratic time complexity, which makes graph matching applicable to a wide range of real-world pattern recognition problems.
Based on this efficient graph matching framework, we propose in this project to explore the use of graphs and the potential benefits of structural pattern recognition methods for signature verification. First, we will derive graph models for signatures and adapt the matching framework to signature verification. In order to further improve the verification accuracy, we will also attempt to embed signature graphs in vector spaces, which allows statistical classification, and the combination of multiple classifiers profiting from the complementary properties of the statistical and structural approach.
A central aspect of the envisaged structural verification system will be to include a signature stability model that distinguishes stable from variable subparts based on the analysis of genuine reference samples. Besides potential improvements in the verification accuracy, such a stability model provides a novel graph based interpretation of signatures, which can be valuable for supporting human experts.