Describing the shape of an object is a well-studied, yet ever-engrossing problem, because an appropriate description can improve the efficiency of a shape matching algorithm, thereby enriching subsequent applications. The authors propose a novel boundary-based shape description using the Farey sequence to capture an object shape represented as a sequence of discrete straight line segments. The straight edges are extracted directly from a gray-scale image without resorting to any edge map detection, and without using any thinning procedure. Then we merge the straight pieces, which are almost collinear but usually small in length, by employing the novel idea of an Augmented Farey Table (AFT). An AFT is a preprocessed data structure that provides us the Farey indices based on which the amount of linearity of three consecutive vertices of a polygon in the digital plane, is decided. Using the final straight pieces after AFT-based merging, the authors build a shape description using the Farey indices of the merged/larger pieces. In particular, the method would be computationally attractive for polygonal approximation and shape description of a large database of gray-scale images. Experimental results demonstrate its usefulness, efficiency, and elegance.
TopIntroduction
Shape is an attributive embodiment of human perception. Various shape description and matching techniques, therefore, are found to play important roles in the automated machine recognition of digital objects and patterns. Understanding the shape of a graphic object as a polygon described as a numeric sequence — of its vertex coordinates or some other attributes — can be of great interest, as a numeric representation can be analyzed easily and efficiently by an algorithm working on the integer input. Description of the shape of an object in a digital image can be also given as a sequence of internal angles of the underlying polygon, and the resultant representation of the object leads towards compactness and reduced memory requirement. Further, it also becomes almost invariant to rotation and also to isotropic scaling. However, the internal angle at a vertex of the polygon being a real value lying in the open interval (0, 2π), floating-point computations and allied procedural complexities do play significant roles in determining the runtime of an algorithm that deals with shapes. This paper shows how a Farey sequence can be used to represent the edge slopes, and the vertex angles thereof, to describe a polygon for its readiness to subsequent applications.
Once we get a proper descriptor of digital images, we can apply some shape matching algorithm for shape-based retrieval. There are a number of methods that build classifiers without finding correspondences. These approaches have been used for handwritten digit recognition (LeCun, Bottou, Bengio, & Haffner, 1998), face recognition (Moghaddam, Jebara, & Pentland, 2000), hand recognition (Shamaie, Hai, & Sutherland, 2011), etc. Methods are also there to perform recognition based on shape information. For example, silhouettes have been described using Fourier descriptors in Zahn and Roskies (1972). Skeleton extraction and feature descriptions based on medial-axis transform are discussed in Sharvit, Chan, Tek, and Kimia (1998). Other approaches that treat the shape as a set of points, extracted using an edge detector, are available in Borgefors (1988), Gavrila and Philomin (1999), and Huttenlocher, Lilien, and Olson (1999).
Polygonal approximation/polygonization itself is also used as intermediate steps in various applications such as volume rendering and multi resolution modeling (De-Haemer, Jr. & Zyda, 1991; Shirley & Tuchman, 1990), image and video retrieval (Mokhtarian & Mohanna, 2002), shape coding (O’Connell, 1997), etc. There exists a rich literature of different techniques for polygonal (or poly-chain) approximation of a digital curve (Bhowmick & Bhattacharya, 2007; Chen & Chung, 2001; Climer & Bhatia, 2003; Dunham, 1986; Imai & Iri, 1986; Perez & Vidal, 1994; Rosin, 1997; Teh & Chin, 1989; Wall & Danielsson, 1984; Yin, 2003, 2004). However, none of these algorithms can be used for approximating a gray-level curve or an object in a gray-scale image. Hence, for polygonal approximation of (objects in) a gray-scale image, at first the edge map needs to be extracted, and then the edge map has to be thinned for obtaining strictly one-pixel-thick curves. We can use edge detection operators (e.g., Prewitt operator, Sobel operator, etc.) or an well-known edge extraction algorithm, e.g., Canny’s edge detection algorithm (Canny, 1986), to get the edge map first. Thus, with the existing practice, polygonal approximation of a gray-scale image is realizable only after the extraction of the thinned edges of objects present in the image. And then only we can apply one of the above-mentioned algorithms on the thinned edge/curve to get polygonal (or poly-chain) approximation of the objects. The entire procedure is, therefore, not only susceptible to pitfalls of the adopted edge extraction algorithm and subsequent thinning, but also affected by inter-stage dependence and high runtime.