Signature based Document Image Retrieval Using Multi-level DWT Features

Published Online August 2017 in MECS

Signature is a unique entity and forms an important method for indexing of large documents stored in the database. Signature extraction from the document image and retrieving documents using the signature as a query is challenging task in the field of document image analysis and processing. Retrieval of documents using the signature as query finds its application in government organizations, banking sector, insurance companies, digital libraries etc.

The general method for signature based document image retrieval includes feature extraction from documents using various methods, matching the features of known signatures with extracted features using distance metrics or classifiers and finally ranking of the documents based on results of feature matching. This paper proposes a method for automatic signature extraction from scanned documents and retrieval of these documents using multi-level DWT features. It also compares the results of retrieval using single-level DWT and multi-level DWT features with different distance metrics such as Euclidean, Canberra, City-block, Chebychev, Cosine, Hamming and Jaccard.

The main contribution of this paper includes proposing a method for signature extraction from document image, signature based document image retrieval using multilevel DWT features and comparison of the results using various distance metrics. The rest of the paper is organized as follows. Section 2 provides related work carried out in the domain, proposed methodology in section 3, Results and discussion in section 4 and section 5 concludes the paper.

• II.    Related Work

Lot of work has been carried out in document image analysis and processing. In this section, we briefly discuss state of art related to signature segmentation from document image and signature based document image retrieval.

Djeziri et al. [1] introduced the filiformity as a criterion for detecting curvature characteristics of handwritten signatures. Filiformity is defined for two topological measures and it differentiates the contour lines of the signatures from the handwritten lines which are being isolated. A method for extracting signature from bank cheques and other documents by estimating approximate area using sliding window technique is proposed by Madasu et al.[2]. They computed density and entropy of each window for signature detection and applied fuzzy based theory to verification of signatures.

Chalache et al. [3] proposed signature based decomposition and retrieval of document images on Arabic/Persian documents employing geometric properties of connected components. Automatic links between signature feature vector and documents were used for retrieval process. The retrieval performance was measured by average normalized retrieval rate.

Document image retrieval using signature as the query was proposed by Srihari et al. [4]. They used a technique for noise and printed text removal from signature images which were previously extracted from business documents. Then normalized correlation similarity measure using global shape-based binary feature vectors was employed for signature matching. Zhu et al. [5] proposed a method for signature extraction using multiscale saliency feature in their work. They defined a saliency function which increases with the curve length and decreases with the curvature when totally squared. The method is robust against any changes in shape-based object detection problems and is applicable to different languages.

Signature based document retrieval using different shape representation like salient contour, computed by detection and segmentation of the skeleton that is extracted directly from labeled signature region of the database is presented in [6]. Thinning algorithm used in this method shows sensitivity to structural variations due to noise and neighboring stroke salient contours gave a globally consistent representation of structurally important shape feature. Srinivasan et al. [7] used conditional random fields (CRF) for signature based retrieval of scanned documents. They used CRF for extracting a signature from complex document and indexing is done by using a model based on CRF.

Mandal et al. [8] proposed a 3 stage work to extract signatures from document images. An algorithm to locate the signature word-level feature extraction, separation of signature strokes that overlap with the printed text and conditional random field minimization energy concept with skeleton analysis to classify real signature strokes. Rotated complex wavelet filters and dual-tree complex wavelet transform together are used for feature extraction in the work proposed by Shirdhonkar and Kokare [9]. Further to improve retrieval performance they employed query point movement.

Roy et al. [10] proposed signature based document retrieval from documents with a cluttered background. They characterized signature object by spatial features computed from recognition result of background blobs. A codebook of the background blobs is employed for indexing and Generalized Hough Transform (GHT) is used to detect the query signature. Mandal et al. [11] introduced a method for signature detection from scanned documents using two-stage approach. In the first stage, signature blocks are segmented from the document using word-wise component extraction and classification. Gradient-based features are extracted from each component at the word level to perform the classification task. In the 2nd stage, SIFT (Scale-Invariant Feature Transform) descriptors and Spatial Pyramid Matching (SPM)-based approaches are used for signature recognition. Support Vector Machines (SVMs) are employed as the classifier for both levels.

Cuceloglu and Ogul [14] proposed a method for detecting signature from scanned documents. Two-phase connected component labeling approach is used for segmentation and they evaluated the method using combined effects of several feature representation schemes with Support Vector Machine (SVM) classifier. Combined signature matching algorithm with the prefiltering method is used to minimize the search space by Schulz and Sablatnig [15]. Shape context distance is used for pre-filtering and a Thin-Plate Spline (TPS)

transformation for matching of signatures. Nurdiyanto and Hermanto [16] presented neural network-based signature recognition technique. They used Shannon entropy for feature extraction and Probabilistic Neural Network for recognition of signature in their work.

Seyyid Ahmed Medjahed [17] presented a comparative study of feature extraction methods used for classification of images in various applications. Belhallouche and Kpalma [18] proposed shape adaptive DWT for region based retrieval. The advantage of this method is a number of coefficients after transformation will be same as that of a number of pixels in the region.

• III.    Proposed Methodology

In the proposed method we implement signature based document image retrieval using two-stage approaches, that include (i) Signature extraction from query document image and (ii) Retrieval of documents based on the signature. These two stages are briefly discussed in the following section.

• A.    Signature Extraction from Document Image

The Algorithm 1 shows the process used for signature detection and extraction from document image in our method. Steps used in the algorithm are briefly discussed in the following sections.

Algorithm 1: To detect and extract signature from document image.

• 1.    Begin

• 2.    Input : Query document, Output : Extracted signature

• 3.    Read document image containing signature as query.

• 4.    Preprocess the query document.

• 5.    Find connected components and perform area based thresholding to get possible signature candidates.

• 6.    Apply multi-level  DWT to all  possible

• 7.    Find the distance between FSPC[1:N] and FSSS i [1:N] using Canberra distance and store in CanDist[i]. Where FSSS i [1:N] will contain feature set of sample signatures.

• 8.    Detected signature candidate = candidate with lowest(CanDist).

• 9.    Extract the detected signature candidate.

• 10.    End

signature candidates and obtain feature set FSPC[1:N]. Where FSPC represents an array containing feature set of possible candidates.

• •    Preprocessing: The given query document is read and converted to binary image consisting of intensity values 0s and 1s. This step employs noise removal techniques for enhancement of the document image given as a query. Generally scanned documents suffer from horizontal and vertical lines (black strips)

at their edge portions. These horizontal and vertical black strips are removed by replacing continuous black pixels oriented either vertically or horizontally with white pixels. This pre-processing step also helps in removing the lines that overlap the signature in most of the documents. Then a median filter of size 3×3 is applied to remove impulse noise from the document images.

• •    Finding possible signature candidates: The length of the signature component in the document image will be larger compared to the length of the other components of the document image. We used this idea initially to identify a set of possible signature candidates in our proposed method. Hence after removing the noise from document image we find connected components in the document image and perform area based thresholding, which results in a pool of possible signature candidates.

• •    Feature extraction: We used multi-level DWT for obtaining features from possible signature candidates. Multilevel decomposition provides multi-resolution analysis of the image with increased number of features. Multi-level DWT is obtained by applying DWT repeatedly on approximate coefficients at each level. Since the size of the signature area will be small, here we have decomposed the signature candidates up to the second level. A two-level DWT will have the form as shown in Fig. 1. CA1, CH1, CD1, CV1 are coefficient matrices obtained at single-level and    CA2, CH2, CD2, CV2 are

coefficient matrices obtained at second-level decomposition.

SDcHrjMb^i^CH^j) - ^ CRi )² (4)

Echi, SD CH1 and H_CR1 in equations (3) and (4) represent energy, standard deviation and mean of horizontal coefficient matrix CH1.

Ecdi = ^Zr=iZ7=i|CD1(i,j)|

SDcdi = ^^=iL?=i(CD1(m)-^cdi)2(6)

E_cd1, SD_cd1 and H_CDi in equations (5) and (6) represent energy, standard deviation and mean of diagonal coefficient matrix CD1.

Ecvi = M^Z?=iZ7=i|CV1(iJ)l

SDcvi = ^3UZ?=i(CV1(ij) — ^cvi)2(8)

Ecvi, SD CV1 and ^_CVi in equations (7) and (8) represent energy, standard deviation and mean of vertical coefficient matrix CD1.

Similarly, we also compute E CA2 , E CH2 , E CD2 , E CV2 , SD CA2 , SD CH2 , SD CD2 and SD CV2 for DWT coefficients obtained at second level decomposition. FV1 in equation (9) represent feature vector generated from single level DWT and FV2 in (10) represent second level DWT features.

Fig.1. Two level DWT on Signature Component

FV1 = {ECA1, ECH1, ECD1, ECV1, SDCA1, SDCH1, SDCD1, SDCV1}

FV2 = {ECA2, ECH2, ECD2, ECV2, SDCA2, SDCH2, SDCD2 and SDCV2}

Finally, the feature vector FV is then constructed using all the 16 computed values obtained from FV 1 and FV 2 as shown by equation (11)

FV = {FV 1 } U {FV 2 }            (11)

For each coefficient obtained after second level DWT, we compute energy and standard deviation as follows and construct a feature vector.

Ecai= ^Z ?=i Z 7=i |CA1(i,j)|         (1)

SDcai = j M^N ZM =₁ (CA1(i,j)-^ cAi )²    (2)

E_ca1, SD CA1 and H_CAi equations (1) and (2) represent energy, standard deviation and mean of approximate coefficient matrix CA1.

Echi = M^N Z ?=i Z 7=i |CH1(i,j)|

• •    Signature detection and extraction: To detect a signature candidate from a pool of possible signature candidates we compare features of each possible signature candidate with features of sample signatures. For each author, we have used 3 sample signatures and their features are stored in the repository. To compare similarity a Canberra distance is found between features of possible signature candidates and sample signatures using (12).

|FSPCj-FSSSj|

^CanDist(j) = Z _i=i |FspC_i|₊|Fsss_i|  forJ=l,², ..,N ⁽¹²⁾

Where CanDist[1:N] is an array that holds Canberra distance between each possible signature candidate and sample signatures collected from authors. FSPC i and

FSSS i used in equation (12) represent feature vector of possible signature candidate and feature vector of sample signatures collected from authors. The algorithm finally decides that a candidate with the lowest distance is signature component of the document image and this particular connected component is stored in a twodimensional array as an extracted signature.

• B.    Signature based Document Image Retrieval

• 2.    Input :   Extracted signature from query

• 3.    Store multi-level DWT features of extracted signature in FES[1:N] and Let FSD i [1:N] holds features of signatures corresponding to the documents stored in the database.

• 4.    Find the similarity distance between FES[1:N] and FSD i [1:N] using different distance metrics such as Euclidean, Canberra, City-block, Chebychev, Cosine, Hamming and Jaccard.

• 5.    Sort the values of similarity distance values stored in SimDist[1:N] and display top N documents that corresponds to top N distance values.

• 6.    End

Steps used for the process of document retrieval using a document containing signature as a query are shown in Algorithm 2. In the following section, we briefly discuss these steps.

Algorithm 2: Signature based document retrieval1.    Begin

document. Output : Retrieved documents.

SimDist[i]=Distance between FES[1:N] and FSD i [1:N]

• •    Matching features of query signature:  To

implement signature based document retrieval, we first extracted the signature from all the documents using signature extraction algorithm and store the features corresponding to these signatures in an array FSD i [1:N] for i=1,2, … M . Where M is a number of documents in the database and N is a number of features stored for each document.

Let FES[1:N] is a multi-level DWT feature vector of extracted signature from the document image. To find a match between the query signature and signatures of documents stored in the database similarity distance is computed using different distance metrics and are stored in SimDist[1:M]. We used 7 distance metrics such as Euclidean, Canberra, City-block, Chebychev, Cosine, Hamming and Jaccard for similarity matching, to decide the appropriate distance metric for the proposed method. The different distance metrics used for retrieval of documents with their corresponding equations are listed in Table 1. In all the equations provided in table 1, X and Y represent the feature vectors of size N and D is the distance value that indicates measure of similarity between query document and database documents.

Table 1. Different distance metrics

Sl. No	Distance metrics	Equation for computing distance (D)
1	Canberra	Y ри —Yi| A |Xi| + |ri| i=1
2	Euclidean	V2 ?=i (^ — Yi) 2
3	Cityblock	2 ?=i |Xi —Yi)|
4	Chebychev	Max № —Yi|}
5	Cosine	^     ^xi.Yi Y^Xi2 Yi2
6	Hamming	5 "=1 |Xi — Yi| , The distance is 1 if Xi * Yi and 0 if Xi = Yi
7	Jaccard	|X nY| |XUY|

• •    Ranking and retrieval of documents: As we discussed in section 3.2.1, similarity distance between query signature and signatures of all the documents from the database are made available in SimDist[1:M]. Lowest distance indicates the highest similarity and vice versa, therefore we sort the array SimDist[1:N] in ascending order and the corresponding document files in the database such that first document will have a closest match with the query. These sorted document images are displayed for the users as a set of retrieved documents.

• IV. Experimental Results

The proposed method is tested for a total of 180 scanned documents signed by 18 different persons. The content of the document images includes a variety of mixed text of English with different fonts and sizes, company logo, signatures, etc. Fig. 2 shows some of the sample documents used for testing with signature extracted using algorithm 1. In the sample results, we can observe that documents have tables, graphics and text with different font and size.

Fig.2. Three sample documents with extracted signatures

Sample result obtained for document image retrieval using algorithm 2 is shown in Fig. 3. It includes an image of query document along with top 4 documents retrieved. Recall (R) and Precision (P) are used for evaluating the performance of proposed signature-based document image retrieval method. The recall is computed as ratio of relevant documents retrieved to a total number of relevant documents available in the database, whereas precision is the ratio of number of relevant documents retrieved to total number of documents retrieved for a specific query.

Precision and recall values obtained for top 30 documents with single and multi-level DWT features using different distance metrics are shown in table 2 and 3 respectively.

Top 4 Retrieved Documents

Fig.3. Retrieved documents for a sample query

Precision and recall values obtained for top 30 documents with DWT and multi-level DWT using different distance metrics are shown in Table 2 and 3 respectively. Testing of the proposed method is carried out for all the distance metrics for same set of documents, to provide a comparison of results with various distance metrics.

Table 2. Precision and Recall values using single-level DWT features for top 30 documents

Query Document	Canberra		Euclidean		City Block		Chebychev		Cosine		Hamming		Jaccard
	%R	%P	%R	%P	%R	%P	%R	%P	%R	%P	%R	%P	%R	%P
1	13.33	40	16.66	50	13.33	40	13.33	40	3.33	10	33.33	100	33.33	100
2	13.33	40	16.66	50	13.33	40	16.66	50	00	00	33.33	100	33.33	100
3	26.66	80	30	90	26.66	80	30	90	30	90	00	00	00	00
4	33.33	100	33.33	100	33.33	100	33.33	100	33.33	100	00	00	00	00
5	26.66	80	26.66	80	26.66	80	30	90	30	90	26.66	80	26.66	80
6	33.33	100	33.33	100	33.33	100	33.33	100	33.33	100	00	00	00	00
7	23.33	70	16.66	50	23.33	70	20	60	13.33	40	33.33	100	33.33	100
8	20	60	20	60	20	60	20	60	00	00	00	00	00	00
9	26.66	80	26.66	80	26.66	80	26.66	80	33.33	100	00	00	00	00
10	20	60	20	60	20	60	20	60	00	00	00	00	00	00
Average	23.66	71	24	72	23.66	71	24.33	73	17.66	53	12.66	38	12.66	38

Table 3. Precision and Recall values using multi-level DWT features for top 30 documents

Query Document	Canberra		Euclidean		City Block		Chebychev		Cosine		Hamming		Jaccard
	%R	%P	%R	%P	%R	%P	%R	%P	%R	%P	%R	%P	%R	%P
1	23.33	70	16.66	50	20	60	13.33	40	20	60	33.33	100	33.33	100
2	23.33	70	20	60	23.33	70	10	30	6.66	20	33.33	100	33.33	100
3	30	90	16.66	50	30	90	20	60	20	60	00	00	00	00
4	26.66	80	30	90	26.66	80	26.66	80	23.33	70	00	00	00	00
5	30	90	30	90	30	90	13.33	40	10	30	26.66	80	26.66	80
6	26.66	80	16.66	50	26.66	80	10	30	26.66	80	00	00	00	00
7	23.33	70	20	60	20	60	16.66	50	23.33	70	33.33	100	33.33	100
8	26.66	80	23.33	70	26.66	80	23.66	70	13.33	40	00	00	00	00
9	20	60	33.33	100	33.33	100	33.33	100	23.66	70	00	00	00	00
10	30	90	30	90	30	90	23.33	70	20	60	00	00	00	00
Average	26	78	23.66	71	26.66	80	19	57	18.66	56	12.66	38	12.66	38

• ■    Single Level DWT Features

• ■    Multi-level DWT Features

Fig.4. Comparison of recall parameter for top 30 results

Fig. 4 shows the comparison of Precision parameter using single level and multi-level DWT features with different distance metrics in graphical form. The horizontal axis of the graph depicts different distance measures and vertical axis provides % Precision for both DWT and multi-level DWT features. This graphical comparison of the results reveals that,

• •    Multi-level DWT features with city block distance measure provide highest performance i.e. 80% Precision for top 30 results.

• •    However single-level DWT features combined with chebychev distance has provided highest performance i.e. 73% Precision for top 30 results. This variation in performance is due to fewer features and directional information available with single-level DWT.

• V. Conclusion

In this paper, we proposed a method for automatic signature extraction and retrieval of documents using signature as a query. DWT features extracted at singlelevel and multi-level are used for document image retrieval. We also compared the results obtained with proposed method using various distance metrics such as Euclidean, Canberra, City-block, Chebychev, Cosine, Hamming and Jaccard. From the experimental results, we conclude that multi-level DWT features with city block distance provide better performance.

Acknowledgement