Offline Signature Verification Using Graph Matching

In this paper, we present a simple and effective signature verification method that depends only on the raw binary pixel intensities and avoids using complex sets of features. The method looks at the signature verification problem as a graph matching problem. The method is tested using genuine and forgery signatures produced by five subjects. An equal error rate of 26.7% and 5.6% was achieved for skilled and random forgeries, respectively. A positive property of our algorithm is that the false acceptance rate of random forgeries vanishes at the point of equal false rejection and skilled forgery false acceptance rates. Keeping the normalization size at 32 x 64 pixels makes the verification time in the two seconds range.

Anahtar Kelimeler:

Offline Signature Verification, Graph Matching, Thinning, Normalization

Offline Signature Verification Using Graph Matching

Keywords:

Offline Signature Verification, Graph Matching, Thinning, Normalization,

PDF

___

J.P. Drouhard, R. Sabourin, M. Godbout, “Evaluation of a Training Method and of Various Rejection Criteria
for a Neural Network ClassiŞer Used for Oﬀ-Line Signature VeriŞcation,” IEEE Int’l Conf. Neural Networks,
Orlando, Fla., June 26-July 2, pp. 294-4,299, 1994.
R. Sabourin, J.P. Drouhard, “Oﬀ-Line Signature VeriŞcation Using Directional PDF and Neural Networks,”
Proc. of the 11thICPR, pp. 321-325, The Hague, The Netherlands, 1992.
H. Cardot, M. Revenu, B. Victorri, M.J. Revillet, “A static signature veriŞcation system based on a cooperative
neural network architecture,” International Journal of Pattern Recognition and ArtiŞcial Intelligence, 8(3), pp. 679–692, 1994.
R. Bajaj, S. Chaudhury, “Signature veriŞcation using multiple neural classiŞers,” Pattern Recognition, 30(1), pp. 1–7, 1997.
K. Huang, H. Yan, “Oﬀ-line signature veriŞcation based on geometric feature extraction and neural network
classiŞcation,” Pattern Recognition, 30(1), pp. 9–17, 1997.
J.P. Drouhard, R. Sabourin, M. Godbout, “A neural network approach to oﬀ-line signature veriŞcation using
directional PDF,” Pattern Recognition, 29(3), pp. 415–424, 1996.
L.L. Lee, “Neural approaches for human signature veriŞcation,” Third International Conference on Signal
Processing Proceedings, pp. 1346–1349, 1996.
M.C. Fairhurst, P. Brittan, “An Evaluation of Parallel Strategies for Feature Vector Construction in Automatic
Signature VeriŞcation Systems,” Int. J. Pattern Recognition and ArtiŞcial Intelligence, vol. 8, no. 3, pp. 661-678, 1994.
W.F. Nemcek, W.C. Lin, “Experimental Investigation of Automatic Signature VeriŞcation,” IEEE Trans.
Systems, Man and Cybernetics, pp. 121-126, 1974.
T.S. Wilkinson, J.W. Goodman, “Slope Histogram Detection of Forged Handwritten Signatures,” Proc. SPIE, pp. 293-304, Boston, 1990.
E.R. Brocklehurst, “Computer Methods of Signature VeriŞcation,” J. Forensic Science Society, pp. 445-457, 1985.
M. Ammar, Y. Yoshida, T. Fukumura, “Oﬀ-Line Preprocessing and VeriŞcation of Signatures,” Int’l J. Pattern Recognition and ArtiŞcial Intelligence, vol. 2, no. 4., pp. 589-602, 1988.
R. Sabourin, R. Plamondon, L. Beaumier, “Structural Interpretation of Handwritten Signature Images,” Int. J. on Pattern Recognition and ArtiŞcial Intelligence, vol.8, no. 3, pp. 709-748, 1994.
R.N. Nagel, A. Rosenfeld, “Computer Detection of Freehand Forgeries,” IEEE Trans. Computers, vol. 26, no. 9, pp. 895-905, 1977.
Y. Qi, B. R. Hunt, “Signature veriŞcation using global and grid features,” Pattern Recognition, 27(12), pp. 1621–1629, 1994.
R. Plamondon, G. Lorette, “Automatic signature veriŞcation and writer identiŞcation—the state of the art,” Pattern Recognition, 22, pp. 107–131, 1989.
R. Sabourin, M. Cheriet, G. Genest, “An Extended-Shadow-Code Based Approach for Oﬀ-Line Signature VeriŞcation,” Second IAPR Conf. Document Analysis and Recognition, pp. 1-5,Tsukuba, Japan, Oct. 1993.
M. Ammar, “Progress in veriŞcation of skillfully simulated handwritten signatures,” International Journal of Pattern Recognition and ArtiŞcial Intelligence, 5(1–2):337–351, 1991.
N.A. Murshed, R. Sabourin, F. Bortolozzi, “A cognitive approach to oﬀ-line signature veriŞcation,” International Journal of Pattern Recognition and ArtiŞcial Intelligence, 11(5), pp. 801–825, 1997.
G. Rigoli, A. Kosmala, “A Systematic Comparison Between on-line and oﬀ-line Methods for Signature Ver- iŞcation with Hidden Markov Models,” 14th International Conference on Pattern Recognition - vol. II, pp. 1755—1757, Australia, 1998.
G. Dimauro, S. Impedovo, G. Pirlo, A. Salizo, “A multi-expert signature veriŞcation system for bank check processing,” International Journal of Pattern Recognition and ArtiŞcial Intelligence, 11(5), pp. 827–844, 1997.
Q. Wu, S. Lee, I. Jou, “On-line signature veriŞcation based on split-and-merge matching mechanism,” Pattern Recognition Letters, 18(7), pp. 665-673, 1997.
M. Munich, P. Perona, “Visual signature veriŞcation using aﬃne arc-length,” Proc. IEEE Comput. Soc. Conf. Comput. Vision and Pattern Recogn., 1999.
R. Sabourin, G. Genest, F.J. Prˆeteux, “Oﬀ-Line Signature VeriŞcation by Local Granulometric Size Distribu- tions,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 19, No. 9, pp. 976-988, 1997.
S.N. Srihari, A. Xu, M.K. Kalera, “Learning strategies and classiŞcation methods for oﬀ-line signature veriŞca- tion,” Proc. of the 7th Int. Workshop on Frontiers in handwriting recognition (IWHR) , pp. 161–166, 2004.
C. Sansone, M. Vento, “Signature VeriŞcation:Increasing Performance by a Multi-Stage System,” Pattern Analysis & Applications, No. 3, pp. 169–181, 2000.
C. Allgrove, M. C. Fairhurst, “Majority Voting for Improved Signature VeriŞcation,” IEE Colloquium on Visual Biometrics, (Ref No. 2000/018), pp. 911-914, 2000.
G. Dimauro, S. Impedovo, G. Pirlo, “Component-Oriented Algorithms for Signature VeriŞcation,” Int. J. Pattern Recognition and ArtiŞcial Intelligence, vol. 8, no. 3, pp. 771-793, 1994.
N.A. Murshed, F. Bortolozzi, R. Sabourin, “Oﬀ-Line Signature VeriŞcation, Without a Priori Knowledge of Class w2. A New Approach, ”Proc. Third IAPR Conf. Document Analysis and Recognition, pp. 191-196, Aug. 14-16, Montr´eal, Canada, pp. 191-196, 1995.
F. Nouboud, R. Plamondon, “Global Parameters and Curves for Oﬀ-Line Signature VeriŞcation,” Proc. Int’l Workshop on Frontiers in Handwriting Recognition, Taiwan, pp. 145-155, 1994.
J. Mathyer, “The Expert Examination of Signatures,” J. Criminal Law, Criminology, and Police Science, vol. 5, no. 3, May-June, pp. 122-133, 1961.
R. Sabourin, R. Plamondon, G. Lorette, “Oﬀ-Line IdentiŞcation with Handwritten Signature Images:Survey and Perspectives,” Structured Document Image Analysis. New York:Springer-Verlag, pp. 219-234, 1992.
R. Sabourin, G. Genest, “An Extended-Shadow-Code Based Approach for Oﬀ-Line Signature VeriŞcation:Part 2—Evaluation of Several Multi-ClassiŞer Combination Strategies, ”Third IAPR Conf. Document Analysis and Recognition, pp. 197-201, Montr´eal, Canada, Aug. 14-16, 1995.
M. Ammar, Y. Yoshida, T. Fukumura, “A new eﬀective approach for oﬀ-line veriŞcation of signatures by using pressure features”. Proceedings of the 8th International Conference on Pattern Recognition, pages 566–569, 1986.
J.K. Guo, D. Doermann, A. Rosenfeld, “Local correspondence for detecting random forgeries,” Proceedings of the International Conference on Document Analysis and Recognition, pp. 319–323, 1997.
M.K. Kalera, B. Zhang, S.N. Srihari, “Oﬀ-line signature veriŞcation and identiŞcation using distance statistics,” Proceedings of the International Graphonomics Society Conference, Scottsdale, AZ, pp. 228–232, November 2003.
S. Lee, J.C. Pan, “Oﬀ-line tracing and representation of signatures,” IEEE Transactions on Systems, Man and Cybernetics, Vol. 22, pp. 755–771, 1992.
M.E. Munich, P. Perona, “Visual identiŞcation by signature tracking,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(2), pp. 200–217, 2003.
R. Plamondon, G. Lorette, “On-line and oﬀ-line handwriting recognition:A comprehensive survey,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(1), pp. 63–84, 2000.
R. Sabourin, R. Plamondon, “Preprocessing of handwritten signatures from image gradient analysis,” Proceed- ings of the 8th International Conference on Pattern Recognition, pp. 576–579, 1986.
R. Plamondon, F. Leclerc, ”Automatic signature veriŞcation:the state of the art 1989–1993,” International Journal of Pattern Recognition and ArtiŞcial Intelligence, 8(3), pp. 643–660, 1994.
L.L. Lee, M.G. Lizarraga, N.R. Gomes, A.L. Koerich, “A prototype for Brazilian bank check recognition,” International Journal of Pattern Recognition and ArtiŞcial Intelligence, 11(4), pp. 549–569, 1997.
Y. Qi, B.R. Hunt, “A multiresolution approach to computer veriŞcation of handwritten signatures,” IEEE Transactions on Image Processing, 4(6), pp. 870–874, 1995.
P.S. Deng, H.–Y. M. Liao, C.W. Ho, H.–R. Tyan, “Wavelet-based oﬀ-line signature veriŞcation,” Computer Vision and Image Understanding, 76, pp. 173–190, 1999.
B. Fang, C.H. Leung, Y.Y. Tang, K.W. Tse, P.C.K. Kwok, Y.K. Wong, “Oﬀ-line signature veriŞcation by the tracking of feature and stroke positions,” Pattern Recognition, 36, pp. 91–101, 2003.
T.J. Hastie, E. Kishon, M. Clark, J. Fan, “A model for signature veriŞcation,” in Proceedings of the IEEE Conference on Systems, Man, and Cybernetics, 1, pp. 191–196, 1991.
J.S. Lew, “Kinematic theory of signature veriŞcation measurements,” Mathematical Biosciences, 48, pp. 25–51, 1980.
T. Matsuura, H. Sakai, “On stochastic system representation of handwriting process and its application to signature veriŞcation,” Third International Conference on Signal Processing Proceedings, pp. 1330–1333, 1996.
R. Sabourin, J.–P. Drouhard, E.S. Wah, “Shape matrices as a mixed shape factor for oﬄine signature veriŞca- tion,” Proceedings of the Fourth International Conference on Document Analysis and Recognition, pp. 661–665, 1997.
R. Plamondon, “The Design of An On-Line Signature VeriŞcation System:From Theory to Practice,” Int. J. Pattern Recognition and ArtiŞcial Intelligence, vol. 8, no. 3, pp. 795-811, 1994.
R. Plamondon, S.N. Srihari, “On-Line and Oﬄine Handwriting Recognition:A Comprehensive Survey,” IEEE Transaction on Pattern Analysis and Machine Intelligence, vol. 22, no. 1, 2000.
V.S. Nalwa, “Automatic On-Line Signature VeriŞcation,” Proceedings of the IEEE, Vol. 85, No. 2, pp. 215-239, 1997.
L. Lee, T. Berger, E. Aviczer, “Reliable on-line Human Signature VeriŞcation Systems,” IEEE Trans. Pattern Analysis and Machine Intelligence, 18(6), pp. 643-647, 1996.
B. Kashi, J. Hu, W.L. Nelson, W. Turin, “Hidden Markov Model approach to online handwritten signature veriŞcation” International Journal on Document Analysis and Recognition, 1(2), pp. 319-330, 1998.
R.P. Grimaldi, Discrete and Combinatorial Mathematics, Addison-Wesley Longman Inc., forth edition, 1999.
N. ChristoŞdes, Graph Theory:An Algorithmic Approach, Academic Press Inc., 1977.
T. Zhang, C. Suen, “A fast parallel algorithm for thinning digital patterns,” Communications of the ACM, vol. 27, pp. 236-239, Mar., 1984.
G.X. Ritter, J.N. Wilson, Handbook of Computer Vision Algorithms in Image Algebra, CRC Press, 2ndedition, 2001.
Z. Xu, J. Luo, ”Face Recognition by Expression-Driven Sketch Graph Matching”, 18th International Conference on Pattern Recognition (ICPR’06), pp. 1119-1122, 2006.
N. Kela, A. Rattani, P. Gupta, ”Illumination Invariant Elastic Bunch Graph Matching for Eﬃcient Face Recognition”, 2006 Conference on Computer Vision and Pattern Recognition Workshop (CVPRW’06), p. 42, 2006.
R. Cesar, E. Bengoetxea, I. Bloch, ”Inexact Graph Matching Using Stochastic Optimization Techniques for Facial Feature Recognition”, 16th International Conference on Pattern Recognition (ICPR’02) - Volume 2, p. 20465, 2002.
A. Tefas, C. Kotropoulos, I. Pitas, ”Using Support Vector Machines to Enhance the Performance of Elastic Graph Matching for Frontal Face Authentication ”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 23, No. 7, pp. 735-746, 2001.
D.-Q. Zhang, S.-F Chang, ”Detecting image near-duplicate by stochastic attributed relational graph matching with learning”, Proceedings of the 12th annual ACM international conference on Multimedia, New York, NY, USA, pp. 877–884, 2004.
C. Maple, Y. Wang, ”A Three-dimensional Object Similarity Test Using Graph Matching Techniques”, Eighth International Conference on Information Visualisation (IV’04), pp. 363-369, 2004.
R. Baeza-Yates, G. Valiente, ” An Image Similarity Measure Based on Graph Matching”, Seventh International Symposium on String Processing Information Retrieval (SPIRE’00), p. 28, 2000.
H. Jiang, Chong-Wah Ngo, ”Graph Based Image Matching”, 17th International Conference on Pattern Recog- nition (ICPR’04) - Volume 3, pp. 658-661, 2004.
S. Tabbone, L. Wendling, ”Retrieving Images by Content from Strong Relational Graph Matching”, 17th International Conference on Pattern Recognition (ICPR’04) - Volume 2, pp. 951-954, 2004.
Hwann-Tzong Chen, Horng-Horng Lin, Tyng-Luh Liu, ”Multi-Object Tracking Using Dynamical Graph Match- ing”, 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’01) - Volume 2, p. 210, 2001.
L. Augusto C., R.M. Cesar-Jr., ” Quadtree-Based Inexact Graph Matching for Image Analysis”, XVIII Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI’05), pp. 205-212, 2005.
N. Rubanov, ”An eﬃcient subcircuit recognition using the nonlinear graph matching”, Proceedings of the 18th annual symposium on Integrated circuits and system design, Florianolpolis, Brazil, pp. 44-49, 2005.
R. Nagpal, Y.N. Srikant, ”A Graph Matching Based Integrated Scheduling Framework for Clustered VLIW Processors”, 2004 International Conference on Parallel Processing Workshops (ICPPW’04), pp. 530-537, 2004.
S. Soon, A. Pearce, M. Noble, ”Adaptive Teamwork Coordination Using Graph Matching over Hierarchical Intentional Structures”, Third International Joint Conference on Autonomous Agents and Multi-agent Systems - Volume 1 (AAMAS’04), pp. 294-301, 2004.
K. Sartipi, K. Kontogiannis, ”On Modeling Software Architecture Recovery as Graph Matching”, 19th IEEE International Conference on Software Maintenance (ICSM’03), p. 224, 2003.
L.P. Cordella, P. Foggia, C. Sansone, M. Vento, ” Fast Graph Matching for Detecting CAD Image Components”, 15th International Conference on Pattern Recognition (ICPR’00) - Volume 2, p. 6034, 2000.