Off-Line Signature Verification based on Ordered Grid Features: An Evaluation Konstantina Barkoula, George Economou Elias N. Zois, Evangelos Zervas Physics Department Electronics Engineering Department University of Patras Technological and Educational Institution of Athens Patras, Greece Egaleo, Greece email: kbarkoula@gmail.com, economou@upatras.gr e-mail: {ezois, ezervas}@teiath.gr Abstract— A novel offline signature modeling is introduced According to the experimental protocol followed, there are and evaluated which attempts to advance a grid based feature two major approaches which have been applied to off-line extraction method uniting it with the use of an ordered ASVS; writer dependent (WD) and writer-independent (WI). powerset. Specifically, this work represents the pixel The WD approach uses an atomic classifier for each writer. distribution of the signature trace by modeling specific The WI approach uses a classifier to match each input predetermined paths having Chebyshev distance of two, as questioned signature to one or more reference signatures, and being members of alphabet subsets-events. In addition, it is a single classifier is trained for all writers [9], [10]. proposed here that these events, partitioned in groups, are Feature extraction is considered to be one of the most further explored and processed within an ordered set context. challenging tasks when ASVS are designed. An important As a proof of concept, this study progresses by counting the events’ first order appearance (in respect to inclusion) at a feature extraction philosophy which attracts increasing specific powerset, along with their corresponding distribution. interest, exploits the signature using a coarse or fine detail These are considered to be the features which will be employed grid which is imposed upon the image. Among others, in a signature verification problem. The verification strategy examples of grid based feature extraction can be found in the relies on a support vector machine based classifier and the work provided by references [10], [11], [12], [13], [14], [15], equal error rate figure. Using the new scheme verification [16], [17], [18] and [19]. results were derived for both the GPDS300 and a proprietary In another work provided by Tselios, Zois, Nassiopoulos data set, while the proposed technique proved quite efficient in and Economou [20], a grid based feature extraction method the handling of skilled forgeries as well. was developed which represents the signature trace by taking into account the histogram of specific pixel path transitions Grid Features, Power Set, Ordering, Signature Verification along predefined paths within pre-confined Chebyshev distances of two (FCB2 feature). The feature extraction I. INTRODUCTION concepts have been advanced by describing these paths in a way in which they can be viewed as symbols transmitted by Automated handwritten signature verification systems a discrete space random source. The combination of the (ASVS) remain up to now an accepted way for humans to produced FCB2 symbols defines the message or event that the declare their identity in many application areas including random source sends out when a certain sequence of civilian ones [1], [2], [3], [4]. ASVS are separated into two signature pixels is accounted. They are treated according to major categories based on the method that the signature is the event concept, reported in standard set and information obtained. Both online and offline ASVS must cope with the theory and they are complemented along with their evidence that the process of creating handwritten signatures, corresponding probabilistic moments [21]. In this work and even when they originate from a well trained genuine writer, in order to further increase our signature discriminating will carry natural variations, defined as intra-writer capability the potential messages-events of the FCB2 paths are variability [5]. It is adopted that the online ASVS are organized in sub-groups of independent tetrads. Each tetrad generally more efficient when compared to offline. A is organized according to its ordered powerset with respect to commonly used figure of merit which is employed in order inclusion [22]. The outcome of this procedure provides an to characterize the efficiency of ASVS is the equal error rate attempt to model the handwriting process in concordance (EER) which is calculated from the ROC or DET plots of with basic elements of information and coding theory. both types of error rates. The distributions of the now ordered transition paths in The goal of an offline ASVS is to efficiently transform the new feature space are used to code the signature image. an image into a mathematical measurable space where it will In the case study presented here a WD verification scheme is be represented by means of its corresponding features [6]. followed which comprises of the training and testing phase. Next, the features are feeding computational intelligence Verification results have been drawn with the use of two techniques and pattern recognition classifiers which will databases, the GPDS300 and a proprietary one by means of decide, after appropriate training and testing procedures, if a the false acceptance, false rejection and the equal error rate signature under query belongs to a claimed writer [7], [8]. (EER) figure of merit. The rest of this work is organized as follows: Section 2 provides the database details and the Since, in offline signatures, signature-pixel ordering is description of the feature extraction algorithm. Section 3 unknown, the ordered sequence of the pixels cannot be presents the experimental verification protocol which has estimated. This note diminish the number of queried FCB2 been applied. Section 4 presents the comparative evaluation transition paths, in a 5x5 pixel grid window, with center results while section 5 draws the conclusions. pixel each black pixel of signature’s image, to the sixteen independent transition paths presented in Fig. 2. In this case II. DATABASE AND FEATURE EXTRACTION PROCEDURE study only the FCB2 paths have been taken into account. It is advantageous in our case to explicitly treat the notion of the A. Database Description signature pixels indexes (i,j) as a transformation of The proposed feature extraction modeling has been sequences produced by the source. As a consequence, the studied with the use of two databases of 8-bit grey scale feature extraction grid can be identified as a discrete space – signatures: a Greek signers’ database (CORPUS1) [20] and discrete alphabet source. GPDS-300 (CORPUS2) [12]. CORPUS1 comprises of a domestic Greek collection of 105 genuine and 21 simulated D. Ordered Event Modeling forgery signature samples for each of the 69 signers of the Let the triad (  , Β, P) indicate the probability space on database. Genuine samples were acquired in a one month which all the potential outcomes are identified. By definition time frame. CORPUS2 contains 24 genuine signatures and  is the sample space upon which a discrete digital source 30 simulated forgeries for each of the 300 signers of the transmits alphabet symbols. The source may transmit either database and is publicly available. During the experimental single symbols or sets of them (events) from a 16 symbol process, two schemes of randomly selected training and alphabet as figure 2 illustrates. Let B a sigma field (the event testing samples were used for comparison with the outcomes space) that encloses all potential occurrences of symbols of contemporary research in the field. In the first scheme, 12 combinations from the FCB2 alphabet. That is, B is the largest genuine and 12 simulated-forgery reference samples per possible  -field [23] which is the collection of all subsets of writer are used, while in the second scheme 5 genuine and 5  and is called the power set. Finally, let P be the simulated forgery reference samples are used. The remaining corresponding distributions of the  -field. samples are used for testing. In order to evade the problem of 216 space management  is grouped into T subsets {t }t 1,,T and we define the B. Preprocessing In order to produce the binary form of the acquired sub-s-fields Bt as the power sets for each t . In this work signatures the following preprocessing steps have been we choose to group the 16-FCB2(i) components into carried out: thresholding using Otsu’s method [6], ensembles of four tetrads (call it hereafter F4-collection) thus skeletonization, cropping and segmentation. This procedure resulting to an early set of 4  24=64 possible event is expected to reduce a number of side effects of the writing combinations. From the complete set of all the possible instruments variations. The result is the generation of the ensembles of the F4 collection only 87 orthogonal cases shall most informative window (MIW) of the image. The features be enabled along with their corresponding probabilities. are extracted either from the whole MIW of the signature or From a mathematical point of view the signature image is from segments of signature’s MIW with the use of the analyzed into four major subspaces where each of them is equimass sampling grid method [14]. Equimass sampling composed of 16 orthogonal dimensions. The term orthogonal grid segmentation provides strips of the signature with denotes that each symbol in a sub-alphabet space of a F4 uniform size of signature pixels instead of the trivial distance tetrad cannot be derived as any combination of the same grid segmentation which provides segments of equal area. subspace F4 symbols. This constraint provides each signature The result is depicted in Fig. 1. In this work the feature with 87 different F4 orthogonal tetrad event sets, found vector is generated from the ‘S2’ scheme used in [20]. through exhaustive search. Fig. 3 provides the FCB2 alphabet along with a F4 orthogonal collection. As a proof of concept, C. Alphabet Description the orthogonal F4 collection #44, selected randomly is Fig. 2 depicts the alphabet which is defined as a set of illustrated in figure 3. symbols, emerging from the FCB2 description according to [12]. To be more specific, FCB2 alphabet is the set of transition paths of three consecutive pixels under the constraint of having the first and third pixels restrained to a Chebyshev distance equal to two. Figure 1. Signature image with equimass made segments Figure 2. FCB2 alphabet set which forms the probability space  . Figure 3. One F4 collection of tetrads (#44). Each horizontal tetrad is considered to form a subspace in the original 16-dimnensional feature space and consequently generates a powerset of events Finally, each one of the four F4 power-sets of figure 3b is evaluated by ordering the elements of the powerset with respect to inclusion. Fig. 4 provides a graphical explanation of one powerset in line with the proposed modeling. In order Figure 4. Power set for one subspace (the first horizontal line of fig. 3) of to illustrate the method with clarity, figure 4 has been created the #44 F4 collection ordered with respect to inclusion which shows the powerset of the #44 F4 collection with respect to inclusion. The indexes x, y, z, w are associated phase of the WD verification scheme follows: for each with one tetrad’s elements of the F4 collection. For each writer, #nref reference samples of genuine along with an arrow in figure 4 there is a corresponding probability equal number of simulated-forgery signature samples are evaluated for every segmented image. Thus, the overall randomly chosen in order to train the classifier. The “S2” dimensionality of the feature vector for one F4 collection is image segmentation scheme combines the features calculated equal to 32 (4+12+12+4) for each image segment. on the whole signature image as well as the relevant 2x2 According to the exposed material, a discrete source, equimass segmentation grid [20]. These features supply the designated as Sn, can be defined by its transmitted set of classifier training section without assuming any additional symbols-events which are now members of an ordered F4 processing. The classifier used is a hard-margin two class collection. This novel modeling of the feature generation support vector machine (SVM) classifier using radial basis process is an evolution of the previous method as it was kernel. Selection of the training samples for the genuine class described in [20]. It attempts to model the distribution of the was accomplished using randomly chosen samples according signature pixel paths as an information source and to to the hold-out validation method. The remaining genuine associate events of ordered paths (arrows as seen in fig. 4) and simulated forgery signatures feature vectors, drawn along with their corresponding first order probabilities. using the same F4 collection, feed the SVM classifier directly for testing. The SVM output apart from the binary class E. Creation of the ordered feature vector decision provides a score value which is equal to the distance To make this work robust a short description is provided of the tested sample from the SVM separating hyperplane. for generating the ordered feature components. According to The operating parameters of the SVM have been determined the material exposed in sections IIC, IID, each one of the through exhaustive search. It is noted that there is a wide preprocessed image segments is scanned top-down and left- area of rbf sigma values that the system has the reported right to identify its signature pixels. Let us denote with the results. labels One (O) and Two (T) a conjugated pair of 5  5 Evaluation of the verification efficiency of the system is moving grids with the property that their topological centers accomplished with the use of a global threshold on the are distant by a Euclidean distance of one. Then for each overall SVM output score distribution. This is achieved by signature pixel the {O, T} grids are imposed. Next, detection providing the system’s False Acceptance Rate (FAR: of discrete events at both {O, T} grids is performed followed samples not belonging to genuine writers, yet assigned to by the evaluation of the corresponding ordered probabilities, them) and the False Rejection Rate (FRR: samples belonging as described in fig. 4. In addition, fig. 5 presents in a to genuine writers, yet not classified) functions. With these graphical manner the generation of a feature component two rates, the receiver operator characteristics (ROC) are namely the {X, XY}. In this work the overall feature drawn by means of their FAR/FRR plot. Then, classification dimensionality is 128 due to the selection of the performance is measured with the utilization of the system segmentation preprocessing steps. Equal Error Rate (EER: the point which FAR equals FRR). III. CLASSIFICATION PROTOCOL IV. RESULTS On the grounds of proofing the proposed concept and According to the discussion presented above, FAR, FRR according to the discussion exposed in section II the training and the relevant EER rates, are evaluated for (a) CORPUS 1 and and (b) CORPUS 2 with five and twelve reference Figure 6. ROC curves with the corresponding EER for corpuses 1, 2. literature. Since the approach described in this case study is Figure 5. (A) One set of the #44 F4 collection as depicted in fig. 3b. (B) preliminary it is anticipated that further exhaustive research left and right grids labeled as One (O) and Two (T) respectively imposed will unveil important conclusions with respect to the on a signature trace (mark with green shadowed pixels) and corresponding modeling of handwriting. However a number of various events activated. For illustration purposes the topological grids have a distance of 7 instead of 1 that is followed at the actual feature extraction other models and experimental setups including i.e. the method. (C) Ordered event detection is designated between the red circles dissimilarity framework [10] need to be examined in order to and feature component update along red line. verify the effectiveness of the proposed approach. samples for both genuine and forger class. The TABLE I. VERIFICATION EFFICIENCY (%) corresponding results are presented in Table I by means of Experimental Set FAR FRR EER the mean FAR, FRR and EER values. The letters G and F in CORPUS 1, #nref=5 (GF) 2.18 3.29 2.79 Table I designate the genuine and skilled forgery samples CORPUS 2, #nref=5 (GF) 13.03 5.23 9.04 respectively. In addition, the ROC curves are presented for CORPUS 1, #nref=12 (GF) 1.13 1.60 1.45 both databases in fig. 6 along with their corresponding EER CORPUS 2, #nref=12 (GF) 7.73 3.45 5.53 defined as the cross section of the ROC curves and the diagonal. TABLE II. COMPARING EER WITH APPROACH [20] Our results are compared to recently published relevant Experimental Set EER (%) figures. The reported results for CORPUS 1 are compared [20] #nref=5 (GF) 9.16 with the results relevant to those reported in [12] for feature Proposed #nref=5 (GF) 2.79 level simulated forgery verification tests using ‘S2’ scheme [20] #nref=12 (GF) 4.65 using (a) nref=5 and (b) the mean value of nref=10 and Proposed #nref=12 (GF) 1.45 nref=15 tests for comparison with our test using nref=12. The comparison results are presented in Table II. Concerning TABLE III. COMPARING EER WITH VARIOUS APPROACHES (%) CORPUS 2, we present in Table III, the results of recently Method EER EER reported research work using nref=5 and nref=12, along with [20] #nref=5 (GF) 12.32 Proposed 9.04 the results of the current approach. [12] GPDS-100 nref=5 (GF) 12.02 #nref=5 [19] #nref=13 (only G) 4.21 V. CONCLUSIONS [20] for nref=12 (GF) 6.2 Proposed 5.53 In this work a handwritten model based on the powerset [12] # ref = {10G, 15F} 8.26 #nref=12 of an ordered event topology with respect to inclusion is [13] #refn=12 (GF) 13.76 [24] #nref=12 (GF) 15.11 considered as a tool for offline signature verification. A [25] # nref=12 (only G) 15.4 number of verification experiments based on an SVM classifier have been carried out in two signature databases REFERENCES namely the GPDS and a proprietary one. Primary verification [1] R. Plamondon and S. N. Srihari, "On-line and off-line handwriting results indicate that the proposed feature extraction method recognition: A comprehensive survey," IEEE Transactions on Pattern has an appealing aspect; As a comment on the efficiency of Analysis and Machine Intelligence, vol. 22, pp. 63-84, 2000. the method one can state that in the case of the Corpus 1 a [2] F. Leclerc and R. Plamondon, "Automatic Signature verification: the substantial improvement is observed while in the case of state of the art-1989-1993", International Journal of Pattern Corpus 2 the results are comparable with those of the Recognition and Artificial Intelligence, vol. 8, pp. 643-660, 1994. [3] D. Impedovo, and G. Pirlo, "Automatic signature verification: The [23] Hazewinkel, M.: Encyclopedia of Mathematics, Springer, 2001. state of the art, "IEEE Transactions on Systems Man and [24] V. Nguyen, Y. Kawazoe, T. Wakabayashi, U. Pal, and M. Cybernetics" vol. 38, pp. 609-635, 2008. Blumenstein, "Performance Analysis of the Gradient Feature and the [4] L. Batista, D. Rivard, R. Sabourin, E. Granger, and P. Maupin, "State Modified Direction Feature for Off-line Signature Verification", in of the art in off-line signature verification". In Verma, B., Proc. 2010 Int Conf on Frontiers in Handwriting Recognition, pp. Blumenstein, M. (eds.) Pattern Recognition Technologies and 303-307, 2010. Applications: Recent Advances, pp. 39–62, 2008. [25] M. B. Yilmaz, B. Yanikoglu, C. Tirkaz, and A. Kholmatov, "Offline [5] M. C. Fairhurst, "Signature verification revisited: promoting practical signature verification using classifier combination of HOG and LBP exploitation of biometric technology", Electron. Commun. Eng. J., features", in Proc. Int Joint Conf on Biometrics, pp. 1-7, 2011. vol. 9, pp. 273–280, 1997. [6] R. C. Gonzalez and R. E. Woods, "Digital Image processing", Addison Wesley, Reading, 1992. [7] S. Theodoridis and K. Koutroumbas, "Pattern Recognition", Academic Press, 2009. [8] R. O. Duda and P. E. Hart, Pattern classification. New York: John Wiley and Sons, 2001. [9] D. Bertolini, L. S. Oliveira, E. Justino, and R. Sabourin, "Reducing forgeries in writer-independent off-line signature verification through ensemble of classifiers". Pattern Recognition, vol. 43, pp. 387–396, 2010. [10] D. Rivard, E. Granger and R. Sabourin, "Multi feature extraction and selection in writer independent off-line signature verification", International Journal on Document Analysis and Recognition, vol. 16, pp. 83-103, 2013. [11] V. K. Madasu, and B. Lovell. "An Automatic Off-line Signature Verification and Forgery Detection System", in Verma, B., Blumenstein, M. (eds.) Pattern Recognition Technologies and Applications: Recent Advances, pp. 63–89, 2008. [12] J. F. Vargas, M. A. Ferrer, C. M. Travieso and J. B. Alonso, "Off-line signature verification based on grey level information using texture features", Pattern Recognition, vol. 44, pp. 375-385, 2011. [13] R. Kumar, J. D. Sharma, and B. Chanda, "Writer independent off-line signature verification using surroundedness feature", Pattern Recognition Letters, vol. 33, pp. 301-308, 2012. [14] D. Impedovo, G. Pirlo, L. Sarcinella, E. Stasolla, and C. A. Trullo, "Analysis of Stability in Static Signatures using Cosine Similarity", in: Proc of International Conference on Frontiers in Handwriting Recognition, pp. 231-235, 2012. [15] B. H. Shekar, and R. K. Bharathi, "LOG-Grid based off-line signature verification", in Fourth International Conference on signal and image processing, 2012. S. Mohan, S., Kumar, S.S. (eds), LNEE 222, pp. 321-330, 2013. [16] J. P. Swanepoel, and J. Coester. "Off-line signature verification using flexible grid features and classifiers fusion", in International Conference on Frontiers in Handwriting Recognition, pp. 297-302. , 2012. [17] M. K. Kalera, S. Shrihari and A. Xu, "Offine line signature verification using distance statistics", International Journal of Pattern Recognition and Artificial Intelligence, vol. 18, pp. 1339-1360, 2005. [18] A. Gilperez, F. Alonso-Fernandez, S. Pecharroman, J. Fierrez- Aguilar, and J. Ortega-Garcia, "Off-line signature verification using contour features", in International Conference on Frontiers in Handwriting Recognition ICFHR 2008. [19] M. Parodi, J. C. Gomez, and A. Belaid, "A circular grid-based rotation invariant feature extraction approach for off-line signature verification", in 11th International Conference on Document Analysis and Recognition, pp. 1289-1293. 2011. [20] K. Tselios, E. N. Zois, E. Siores, A. Nassiopoulos, and G. Economou, "Grid-based feature distributions for off-line signature verification". IET Biometrics, vol. 1, pp. 72-81, 2012. [21] T. M. Cover, and A. Y. Thomas, "Elements of information theory", 2nd ed. John Wiley and Sons (2006). [22] P. R. Halmos, "Naive set theory". The University Series in Undergraduate Mathematics. van Nostrand Company, Princeton, 1960.