Graph theory based segmentation of traced boundary into open and closed sub-sections

Many shape descriptors based on the boundary have been developed for feature extraction and pattern matching/recognition of objects. This paper presents a novel algorithm to segment a traced boundary in open and closed sub-sections. The obtained sub-sections can be utilized for generating more features while being one of the features. A traced boundary has been considered as an undirected graph with pixels representing the vertices. It is proved that “For a boundary traced using 8-connectivity maximum degree of a vertex cannot exceed four”. This aspect and the instances of degree and number of occurrences are used to categorize all the vertices in eight exhaustive types. Six of these are identified as critical vertices. The segmentation is done based on the principle that in an Eulerian circuit, each edge is traversed only once. Further segregation in open and closed sub-graphs is done by choosing critical vertices at a minimum directed distance. The testing of the algorithm has been done on artificially generated images and from different databases of hand written text. The performance analysis shows that the execution time is a linear function of the number of occurrences of each type of the vertices. The performance analysis is further supported using multiple regression.

► A novel algorithm to segment traced boundary in open and closed sub-sections.
► The segmentation is done based on the principle of an Eulerian circuit.
► The obtained sub-sections can be utilized for pattern matching applications.
► To support the algorithm the paper provides necessary mathematical proof.
► Algorithm analysis supported by multiple regression, shows linear execution time.