HEURISTIC TECHNIQUES FOR HANDWRITTEN SIGNATURE CLASSIFICATION

New theoretical and experimental techniques for offline classification of handwritten signatures are introduced in this paper. The proposed algorithms are mainly based on boundary tracing technique for extracting characteristic features. Outer and inner boundaries of the signature image are treated separately. The upper and lower parts of the boundaries are extracted to form two sequences of points. Three algorithms for calculating feature vectors are applied based on y coordinate, distances between consecutive points and from polar coordinates system. Experiments on classification of the resulted vectors were carried out by means of Dynamic Time Warping algorithm using window and slope constraints. A brief comparison between the authors' work and other known signature techniques is also discussed in the paper.


INTRODUCTION
The handwritten signature is still very common way for authorizing various kinds of documents. From legal contracts to payment bills they play an important role and are used on everyday basis. Signatures are usually written on regular paper without any specialized equipment. Therefore, the only information available, which future verification may be based on, is the static image of the signature. This kind of authorization is obviously far from being perfect. It is not difficult for a skilled person to forge someone's signature. The shape of the signature can be duplicated when one has access to the original signatures and enough time to train signing.

INPUT DATA AND PREPROCESSING
In order to prepare data for classification algorithm, the images of signatures are first stored as Portable Network Graphics files (Fig 1). This particular format for graphical files provides lossless compression that retains all important features without introducing distortions, and results in relatively small footprint. Images can be obtained by means of scanning devices from original documents. The segmentation of signatures from acquired scans is not considered in this work, but can be easily implemented by applying certain constraints on the position of the signature inside the analyzed document. Another problem is noise and defects caused by poor quality of documents and the scanning process. In our experiments we used threshold technique to eliminate minor distortions and convert images from grayscale into black-andwhite binary map.

DATA REDUCTION
The line of a signature in an image may consist of a large amount of pixels. Depending on the resolution and thickness of ink trace it can even reach a few dozen thousands of points. Classification of such a complex object may pose a very difficult task. In fact, most of the points don't give additional information and can be safely ignored. There are many techniques for reducing their number whilst preserving the most important  [2], view-based approach [3], and contour based techniques [4,5].
During thinning process most of the points comprising a particular object are removed to achieve one-pixel-width skeleton (Fig 2). This approach has many applications and has been widely used in cursive script recognition systems.

Fig. 2 -Signature (a) with its thinned version (b)
Projection based techniques capture the distribution of ink in an object by projecting its pixels onto different axes and summing their number or intensity values. The following figure (Fig. 3b) shows a projection of a signature image calculated by computing total number of pixels in every column of the picture.

Fig. 4 -Signature (a) with its upper (b) and down (c) views
Contour tracing algorithm follows the boundaries comprising object image and collects coordinates of their consecutive points (Fig 5a). By boundary we mean the group of the object's pixels that share at least one edge with the background of the image. In many cases a signature is made of several disconnected segments like letters, dashes, points, etc. Those different parts can be treated separately or can be concatenated to form one continuous object.
Sometimes it is also useful to separate outer boundaries from internal and consider upper and down parts of the boundaries separately (Fig 5b, 5c, 5d).

Fig. 5 -Examples of full contour (a), internal contour (b), upper concatenated contour (c), down concatenated contour (d)
Those transformations may reduce complexity of classification task by considering different components individually. In order to further reduce the number of points a simple sampling may be used by selecting every M-th value from the acquired sequences to form feature vectors (value of M denotes a step in the sampling process). In this work we focused on boundary tracing for reduction of data. Experiments with other techniques were carried out and presented in [4,6].

FEATURE VECTOR COMPUTATION
For the classification process each of the signatures is represented by one or more vectors. There are various methods for constructing such vectors. These methods should preserve all the features necessary for distinguishing between different classes of signatures. The other goal is to improve the separation of the classes by ignoring disturbances created by roughness of the ink trace and minor artifacts, which mostly are conducive to inaccuracy of the signing individual. By the class of a signature we mean the group of signatures signed by a particular person.

y-coordinates
The first approach presented in this work is collecting y coordinates of subsequent pixels that form the boundary of analyzed signatures (Fig 6).
As a result a vector V is obtained as a signature representation used for classification process (1): n n y y y y V , ,..., ,

Consecutive points
Another technique is to describe subsequent points as vectors. These vectors are computed as the difference between positions of each consecutive pair of points (2,3). This process is illustrated by Fig. 7. [ ]

Polar coordinates
The third alternative is the algorithm used in this work is the calculation of vectors describing points as vectors from the origin of the polar coordinate system (Fig 8).
In addition, two modifications were applied to reduce amount of unintuitive alignments called singularities [7]. The first used a window which constrained possible paths in the matrix of The second used a slope constraint allowing warping path to follow only particular directions. The applied slope constraint [7,8] can be expressed by the following equation (Eq. 6):

RESULTS
In order to evaluate effectiveness of presented methods several experiments were carried out. The database of signatures was created by 20 different people, with each signature repeated three times, giving a total of 60 signatures.
For each person, each two of the signature versions were used as reference patterns to classify the third one. Therefore 60 3 20 = × tests were conducted in each variant of the experiment. In all cases boundary tracing algorithm was applied to reduce dimensionality of data. During boundary tracing a sampling step of 10 was used to eliminate disturbances created by roughness of the ink trace and to further reduce amount of redundant information.
In the first three approaches only external boundaries were used. Upper parts of boundaries were concatenated and treated separately from bottom parts as described in section 3. The classification process was based on distance measure computed by means of Dynamic Time Warping algorithm. The distance of the reference vector from the one being classified was calculated according to Eq. 7: When comparing subsequent vectors representing points in method 2 and 3 a measure given by Eq. 8 was applied:  table 1 show the percentage of properly classified signatures using each of the methods described earlier. The best classification rate was achieved by using only y coordinates of selected boundary points.
In addition to tracing external boundaries, contours of internal elements like loops were also examined. During experiments it was discovered that most signatures used to construct database were written carelessly. Many of the signatures written by one person varied in number and shape of internal loops. However, some consistency in the numbers of loops in signatures was found. To include this information in a distance measure we added the following modification (9): The following table (Tab. 2) shows results for different value of k using the first approach for building feature vectors. As can be seen from Tab. 2, changing the value of the weighting factor k has noticeably changed the classification rate. It is 93% for . When individuals are required to write their signatures more carefully, the applied algorithms for comparing shapes and loop position definitely result in even better classification rates.

COMPARISON WITH PREVIOUS WORKS AND OTHER APPROACHES
In our previous works [11,12] we experimented with view-based approach and several other modifications of DTW algorithm. Table 3 presents the results achieved with different versions of DTW and various window sizes [7,8].
The column titles have the following meanings: 1. p -percentage of maximum window's size, 2. DTW -basic algorithm with window constraint, 3. DDTW -dynamic time warping with window constraint, 4. DTWS -basic algorithm with window and slope constraints. The results show that applying boundary tracing techniques to signature image gives better classification rate than view-based approach. The advantage of the view-based method is that it is computationally less expensive.

CONCLUSIONS
The methods presented in this paper are based on the techniques applied to cursive word recognition. The signature images are examined as whole words without segmentation into distinct letters or strokes. The aim of this experimental approach is to enable identification based on handwritten signature that would compare general appearance of the signatures. Most of the research in the area of automatic signature recognition is focused on verification and resistance to forgery. Those systems are based on features and techniques allowing for rejection of forged signatures. Combining comparison based on general appearance with more restrictive verification methods may result in more flexible systems capable of both identification and verification for different levels of requirements on exactness of signature repetitions.
The new experiments and comparison with our recent works and other approaches show that the results obtained in [13] using the described approach had really been promising as presented there. The classification rate is still higher than the previous work results as shown in Tables 2 and 3. The authors' current research is being focused on incorporating other classification methods like Neural Networks or Hidden Markov Models. Toeplitz matrix minimal eigenvalues are still under studying to consider their use in feature points extraction. In addition, it is planned to combine and fuse the offline information collected from the signature image with the online data and information obtained from a camera or tablet devices in a hybrid system. These approaches will definitely increase the recognition rate as they had already done with other applications [9,10].