International Journal of Scientific & Engineering Research, Volume 4, Issue 11, November-2013 1327

ISSN 2229-5518

Cycle Detection in Signature Images

* Zulfiqar A. Khan, Asstt. Prof., Sir Syed University of Engineering and Technology, zulfi6000@yahoo.com

AbstractCycle/loop detection is a well known problem in graph theory. Surveyed literature shows that this problem has been studied in diverse domains like operating systems, circuit analysis, network analysis, curriculum adjustment and automata theory. Efforts have also been made to study it in the context of handwriting and digital signature recognition. However no attempt has been made to completely illustrate the cycle detection process

in signature images/alphabetic characters despite the fact that cyclic structures form an inherent part of many characters and human signatures. This paper shows techniques for finding out cycles/loops in signature images by analyzing their neighboring pixels & then applying the Depth First Search algorithm and a variant of it. Results of the technique are promising.

Index Terms—Cylce Detection, Depth First Search Algorithm, Image Processing, Signature images.

I. INTRODUCTION
Cycle detection is one of the most exciting problems which has confronted the computer scientists and engineers in diverse domains like Operating Systems [5], curriculum adjustment [11], automata theory [3], and network analysis [14]. In
recognition, shape oriented techniques involving cyclic structures can play an important role. Two techniques possible: one in which the size and orientation is irrelevant and only cyclic structures along with other geometrical features like

* Computer Engineering Department, zulfi6000@yahoo.

crossovers, junction points, lines and line endings etc, are used for signature identification as indicated by Ke Han and I.K. Sethi in [4]. The other technique is to account for the orientation factor also if required as in [16]. However both these researches and other techniques [7, 9, 10] used for signature recognition using shape oriented geometric/texture features have not elaborated the detailed steps of discovering cycles/loops in signature images, thus not fulfilling the demands of novice entrants to understand this basic and fundamental technique of pattern recognition in the context of handwritten text and signatures. This work can provide a healthy exercise for learning the nuts and bolts of detecting this geometric feature. The other aspect of this research is to highlight the use of Depth First Search (DFS) algorithms in document analysis and OCR applications which again rarely appears in text books and research papers. Previous research shows its application in human biology [1], handwriting recognition [8, 13], and image segmentation for face recognition [15].
The novelty of this research is that it shows the
entire process of detecting cyclic structures within the signature images. Different cyclic structures are identified in this context and DFS algorithm is used for their detection. A variant of DFS algorithm is also proposed to handle the problem case. Detailed description of both the techniques is provided here.
The text in this paper first gives an overview of cycles. This is followed by the application of DFS algorithm on signature images. In the same context, the concept of neighbor-pixel-repeated-node (NPRN) is presented. Later on, step-wise cycle detection is performed on a sample signature. Finally the results and the conclusion section are provided.
II. LOOP/CYCLE DEFINITION
Before discussing the details of what is a cycle

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 11, November-2013 1328

ISSN 2229-5518

and what are its possible types, various features of characters and signatures like crossovers, junctions, line endings are collectively referred to as ‘node’ in this research. A loop/cycle can then be defined as a continuous series of pixels starting from a single node and ending at the same node. Cycles/loops can be classified into three major categories based on their geometric features, a) Single node loops Fig.[2.1a], b) Double node loops Fig.[2.1b], c) Multiple node loops Fig. [2.1c].


Fig. [2.1a] Fig. [2.1b] Fig. [2.1c]

Single node cycle Double node cycle Multiple node cycle

The interesting characteristic of cyclic structures is that they can also be used for identifying
handwriting. As discussed earlier, loops may contain one or more than one nodes. Multiple loops between the same nodes can also exist. These can be used in the context of loops having weights representing various inherent attributes such as
adjacent nodes. This paper tries to detect all the three types of cycles. For the single node loops, the idea of neighboring pixel repeated nodes (NPRN) is used while for multiple nodes DFS algorithm is employed. A detailed description of both the techniques has been described here.
III. APPLICATION OF DFS ON SIGNATURE IMAGES
In a depth first search of graph, we start at a node v and mark it as having been visited. The exploration of a node v is suspended as soon as a new node is reached. At this time the exploration of the new node u begins. When this new node is explored we continue to explore v. The search terminates when all reached nodes have been fully explored. A depth first search of a graph of Fig.[3.1a] starting at node 1 using the adjacency lists given in Fig.[3.1b], results in the cycle of nodes 2,4,3 as given in Fig.[3.1c].

AdjL[1] = 3

1 AdjL[2] = 4,6,3

AdjL[3] = 1,2,4

AdjL[4] = 5,2,3

3 AdjL[5] = 4

3 AdjL[6] = 2

Fig.[3.1b], Adjacent nodes for Fig.[3.1a].

[2.2a] and Fig. [2.2b] show improvised pictures of character ‘O’ and character ‘8’ respectively to highlight the possible nodes and cycles. In Fig. [2.2a] there are three, two node loops but after weights (distances) are assigned, the outer loop may

4

6 5

Fig. [3.1a], Graph showing nodes
be selected since it closely matches the character
pattern (“O”). But in Fig.[2.2b], the assigned

Last

Path

Node

Visited

Adjacent

Nodes


weights can help us to declare the character as “8”.

Fig.[2.2a], Character ‘O’ Fig. [2.2b], Character ‘8’

Although cycles having two or more than two nodes can be successfully detected using the Depth First Search algorithm (DFS) (1990a), however when it is applied to single node cycles, it is unable to detect them. This is because it uses the concept of
1 3
1 3 2,4
1,3 2 4,6
1,3,2 4 5,3
1,3,2,4 5 No
1,3,2,4,5 No
1,3,2,4 3 1,2
1,3,2,4,3 Cycle found
1,3,2,4 6 No
…… …….. ……
Fig. [3.1c], DFS traversal for Fig. [3.1a].

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 11, November-2013 1329

ISSN 2229-5518

Below Fig. [3.2a] illustrates the application of DFS
algorithm on signature image shown in Fig. [3.2b].

Cycles obtained for Fig.[3.2b] along withAdjacency Lists

AdjL [0] [0] = 42 1
AdjL [1] [0] = 37 1 37
AdjL [2] [0] = 10 1 37 43
AdjL [3] [0] = 16 1 37 43 42
AdjL [4] [0] = 32 1 37 43 42 0
AdjL [5] [0] = 42 1 37 43 42
AdjL [6] [0] = 10 1 37 43 42 5
AdjL [7] [0] = 43 AdjL [7] [1]=39 AdjL[7][2]=36
1 37 43 42
AdjL [8] [0] = 10 1 37 43 7
AdjL [9] [0] = 44 1 37 43 7 39
AdjL [10] [0] = 8 AdjL [10] [1]=6 AdjL[10][2]=2
1 37 43 7 39 44
AdjL [11] [0] = 45 1 37 43 7 39 44 9
AdjL [12] [0] = 38 1 37 43 7 39 44
AdjL [13] [0] = 25 1 37 43 7 39 44 37

(cycle found)

AdjL [14] [0] = 36 1 37 43 7 39 44
AdjL [15] [0] = 45 1 37 43 7 39
AdjL [16] [0] = 3 1 37 43 7 39 27
AdjL [17] [0] = 23
………………………………………….
AdjL [18] [0] = 47 1 37 43 7 36 41 47 40
AdjL [19] [0] = 20 1 37 43 7 36 41 47 40
41 (cycle found)
AdjL [20] [0] = 19 AdjL[2 0][1]=27 AdjL[2
0][2]=33
…………………………………………. AdjL [21] [0] = 27 1 37 44 39

AdjL [22] [0] = 24 1 37 44

AdjL [23] [0] = 17 AdjL[23][1]=51 AdjL[23][2]=25 1 37

AdjL [24] [0] = 22 1(Finish)

AdjL [25] [0] = 13 AdjL[25][1]=23 AdjL [25][2]=26

AdjL [26] [0] = 25

AdjL [27] [0] = 20 AdjL[27][1]=21 AdjL [27][2]=39

AdjL [28] [0] = 36

AdjL [29] [0] = 39

AdjL [30] [0] = 49

AdjL [31] [0] = 48

AdjL [32] [0] = 4 AdjL[32][1]= 48 AdjL[32][2]=35

AdjL [33] [0] = 20

AdjL [34] [0] = 46

AdjL [35] [0] = 32

AdjL [36] [0] = 7 AdjL[36][1]=28 AdjL[36][2]=7 AdjL [36] [3]=41

AdjL [37] [0] = 1 AdjL[37][1]=43 AdjL[37][2]=44

AdjL [38] [0] = 46 AdjL [38] [1] = 12

AdjL [39] [0] = 44 AdjL [39] [1]=7 AdjL[39][2]=27 AdjL[39][3]=29

AdjL [40] [0] = 47 AdjL [40] [1] = 48 AdjL [40] [2] = 41

AdjL [41] [0] = 36 AdjL [41] [1] = 47 AdjL [41] [2] = 40

AdjL [42] [0] = 0 AdjL [42] [1] = 43 AdjL [42] [2] = 5

AdjL [43] [0] = 42 AdjL [43] [1] = 37 AdjL [43] [2] = 7

AdjL [44] [0] = 9 AdjL [44] [1] = 37 AdjL [44] [2] = 39

AdjL [45] [0] = 11 AdjL [45] [1] = 16 AdjL [45] [2] = 15

AdjL [46] [0] = 16 AdjL [46] [1] = 38 AdjL [46] [2] = 34

AdjL [47] [0] = 16 AdjL [47] [1] = 40 AdjL [47] [2] = 41

AdjL [48] [0] = 40 AdjL [48] [0] = 40 AdjL [48] [0] = 40

AdjL [49] [0] = 51 AdjL [49] [1] = 51

AdjL [51] [0] = 38 AdjL [51] [1] = 38 AdjL [51] [2] = 38

Fig. [3.2a], Cycles and Adjacency list for Fig. [3.2b]

Fig. [3.2b], A signature image with numbered nodes

IV. APPLICATION OF NEIGHBORING-PIXEL- REPEATED-NODE (NPRN)

Neighbor-pixel-repeated-nodes (NPRN) are found in the same way as adjacent nodes. A NPRN is an adjacent node of itself. First of all, the nodes in the signature image are identified as in Fig. [4.1a]. Then for identification purpose, the nodes are subjected to numbering as in Fig. [4.1b]. After the numbering process completes, for a node N all its adjacent nodes are found but now the node N can be the adjacent of itself. Once the adjacent nodes are found for each node, a check is made to see if the node and its adjacent node are same. If this is true, then that node is termed as NPRN and the cycle so obtained is a one node cycle, starting from NPRN node and back to itself. Node 5 is an NRPN as shown in Fig. [4.1b].

Fig. [4.1a], Nodes obtained for the signature

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 11, November-2013 1330

ISSN 2229-5518

Fig. [4.1b], Numbering of nodes

After the adjacent nodes are determined, it is found that node 5 is an NPRN node as shown in Fig. [4.1d]. The obtained cycles are shown in Fig. [4.1c].

Fig. [4.1c], Loops obtained using NPRN technique

The List of Neighbor-Pixel-Repeated-Nodes (NPRN) and Adjacent nodes (AdjL) for Fig. [4.1c] is given below:

AdjL[0][0]=6

AdjL[1][0]=4

AdjL[2][0]=7 AdjL[2][1]=3 AdjL[2][2]=7

AdjL[3][0]=2

AdjL[4][0]=5 AdjL[4][1]=1 AdjL[4][0]=6

NPRN[5][0]=4 NPRN[5][1]=5 NPRN[5][2]=5

Fig. [4.1d], Application of NPRN on Fig. [4.1c].

It is interesting to understand the difference between the AdjL and the NPRN nodes. An NPRN differs from the adjacent nodes by the fact that a node cannot be the adjacent node of itself. However a node can be an NPRN of itself. This is illustrated in Fig. [4.1e].

AdjL[A] = B,C NPRN[A] = A,A,B,C

A
B C

Fig. [4.1e], Difference between Neighbor Pixel Repeated

Nodes (NPRN) and Adjacent nodes (AdjL).

V. STEPWISE CYCLE DETECTION IN SIGNATURE IMAGES
The preprocessing steps prepare the image for feature extraction. The test image is first localized as in Fig. [5.1a]. This process captures the image in a rectangular window according to its size. Next step is to threshold the gray scale image to convert it into a binary image shown in Fig. [5.1b]. Threshold value is determined using the technique mentioned in (1995b). This algorithm can be applied in an iterative fashion also and the threshold value so evaluated can be used to obtain the desired image. Once the thresholding is done, then skeletonization (thinning) using the approach mentioned in (1994) is performed in order to reduce the image to a width of one pixel as in Fig. [5.1c]. After the process of skeletonization finishes, the image is scanned from left to right and all the nodes of each connected component are determined as in Fig. [5.1d]. This is accompanied by node numbering process which is carried out for identification of nodes and has already been shown in Fig. [3.2b] and Fig. [4.1b]. Then the Adj and NPRN nodes of each node are determined. This has been shown in the previous sections. Once the Adj and NPRN nodes are determined, the image is ready for specifying the loops. as shown in Fig. [5.1e].

Fig. [5.1a], Gray scale image.

Fig. [5.1b] , Image after thresholding

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 11, November-2013 1331

ISSN 2229-5518

Fig. [6.1b], Correct loops detected using iterative thresholding.

Fig. [5.1c] , Image after thinning

Fig. [6.1c], Correct loops detected using iterative thresholding.

Fig. [5.1d], Determination of nodes.

Fig. [5.1e], Determination of Loops/Cycles

VI. EXPERIMENTAL RESULTS

From Fig.[6.1a] it is clear that the above techniques can give erroneous results also if the thinning is not performed in a proper way. Nodes may come very close to each other resulting in an incorrect cycle detection. Thus these techniques are sensitive to noise and even a noise of one pixel may lead to the detection of non-existent loops.

Fig. [6.1a], Incorrect Loops detected.

Correct loops can then be obtained by repeated thresholding in an iterative fashion. Fig.[6.1b] and Fig. [6.1c] demonstrate this technique.
VII. CONCLUSION
Cycle/loop detection methods discussed in this paper can be used as a component in the broader signature recognition systems exploiting geometrical and texture oriented features. Once these features like loops, endpoint points, junctions, and crossovers are determined, a signature can be represented by a string e.g, LEEEJ meaning that a signature has one connected component consisting of one loop, three endpoints and one junction point. The above methods have been tested on a variety of signatures and the author found that the results were very encouraging (out of a set of 100 signatures 83 returned correct results). The ambiguity of the remaining is attributed to the deficiencies of thinning algorithm. No attempts were made to measure the performance in terms of time and space efficiency and the author sincerely hopes that the scope can be extended in future.
ACKNOWLEDGMENT
This research is part of the Master thesis completed by the author under the supervision of Dr. I.K. Sethi (Prof., Computer Science Department, Wayne State University; sethi@cs.wayne.edu). The author highly appreciates his masterly advices on this topic and his permission to use the signature data collected by the image processing and computer vision lab of the computer science department of Wayne State University.

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 11, November-2013 1332

ISSN 2229-5518

REFERENCES
1. Chen. B.Y. et al. Journal of Computational

Biology. 2007. 14. 791p.

2. Cormen T. et al. Introduction to Algorithms.
1994. 14. 477p.
3. S. Demri, and D. D’Souza. Information and

Computation. 2007. 205. 380p.

4. Han K. and Sethi. I. K. Pattern Recognition

Letters. 1995. 17. 83p.

5. Hayden M. and Tempero E. ACSC: Proceedings

of the thirtieth Australasian conference on

Computer science. 2007. 62. 87p.

6. Lee C. L. and Wang P. S. P. Proceedings of the

12th IAPR International Conference on Pattern

Recognition. 1994. 546p.

7. Lee S. and Pan J. C. IEEE Transactions on

Systems, Man and Cybernetics. 1992. 22(4). 755p.

8. Lenaghan A. PhD. Thesis. Kingston University.
2007.
9. Lorette G. and Plamondon R. Computer

processing of Handwritting, eds. 1990. 21p

10. Nanni L. and Lumini A. Pattern Recognition

Letters 2008. 29(5). 559p.

11. Pedroni M. et al. ACM SIGCSE Bulletin, 2007.
39(3). P?
12. Ramesh N. et al. IEEE proc. Vision, Image,

Signal Processing. 1995. 142(5).

13. Steinherz T. et al. IEEE Transactions on Pattern

Analysis and Machine Intelligemnce. 2009.

31(2). 193p.
14. Subramani. K. 2007. Journal of Discrete

Algorithms. 5(3). 408p.

15. Report-repository. 2005.
Available at:
http://www.cse.iitk.ac.in/report- repository/2005/Y0146.pdf
16. Kalenova. D. 2003.
Article available at:
http://www.it.lut.fi/kurssit/03-
04/010970000/seminars/Kalenova.pdf,

IJSER © 2013 http://www.ijser.org