A discrete geometry approach for dominant point detection☆,☆☆
Introduction
The work on the detection of dominant points started from the research of Attneave [6] who proposed that the local maximum curvature points on a curve have a rich information content and are sufficient to characterize this curve. A method for detection of dominant points can lead to a good representation of a planar shape at different resolutions. In addition, a representation of a planar shape based on dominant points has some advantages. Firstly, it enables a high data reduction. Secondly, this representation concentrates on principal features of the shape, so it is efficient for shape matching, feature extraction or decomposition of the curve into meaningful parts. Therefore, these points have a critical role in curve approximation, shape matching and image matching [7]. They also lead to some applications in other domains of machine vision such as vector data compression [8]. Starting from Attneave's work, there are many existing methods for dominant points detection. Concerning this problem, several problems in this topic have been identified: evaluation, number of parameters, selection of starting point, multi-scale, working with noisy curves, … .
In general, we can classify these methods into two groups. The first one contains direct methods that determine dominant points such as high curvature value points by using curvature-based significant measures [9], or using alternative significant measures such as k-cosine [10], region of support (ROS) [11]. Rosenfeld and Johnston [10] used cosine of the angle between the arcs of length k on each side of a point (termed k-cosine) as curvature-based significant measure. Teh and Chin [11] proposed a non-parametric method for detecting dominant points. They used ROS as significant measure that is determined at each point pi thanks to its local properties (chord pi−kpi+k and perpendicular distance from pi to this chord). The dominant points are finally detected by a non-maximum suppression process. They also concluded in this work that the performance of a dominant point detection algorithm depends not only on the accuracy of significant measure, but also on the precise determination of ROS. Marji and Siy [12] determined ROS by using integral square error. They selected end points of support arm as dominant points upon the frequency of their selection. Other algorithms exploit the rule, iteration on neighboring pixels. Sarkar [13] proposed a simple non-parametric method for detecting dominant points from a chained-code boundary. This algorithm examines the differential chain-code of the boundary points sequentially and confirms the significant points based on pure chain code manipulation. Cronin [14] assigned a special code to each boundary point based on the Freeman chain code [15] applied for its two immediate neighbors. The initial dominant points are the set of points with non-zero differential chain code. An elimination process is followed where the boundary is searched exhaustively for predefined sequences to eliminate them from initial dominant set.
The indirect methods are often based on polygonal approximation of the curve, the dominant points are deduced after doing this step. In these methods, the dominant points are detected as the vertex of approximated polygons. In addition, we can divide polygonal approximation methods into three principal approaches: sequential approach, split and merge approach, heuristic search one. For sequential approach, Ray and Ray [16] determined the longest possible line segments with minimum error. Kolesnikov [17] proposed a sub-optimal algorithm for polygon approximation of closed curves based on the corresponding optimal dynamic programming algorithm for open curves. Aoyama [18] used a linear scan to evaluate error conditions, if the conditions are not satisfied, a new segment search is started. The problem of this method is that sometimes the nodes do not correspond to the corners because a new vector is defined only when the conditions are violated. For split-and-merge methods [19], [20], lines are fitted to an initial segmentation of the boundary and then the least square error is computed. These methods then iteratively split a line if the error is too large and merge two points if the error is too small. Heuristic approach is used to reduce the complexity of an optimal algorithm for approximating polygon. Genetic algorithm [21], tabu search [22], ant colony search [23], fuzzy reasoning [24] are some popular techniques in this approach. Among three approaches, the sequential approach is simple and fast, but the quality of its result depends on the starting point. Recently, Masood [25] has proposed an efficient method that does not belong to any of the above groups. It is based on break point extraction. A break point is a point of which the chain code is different from that of the previous point. Break points are taken as initial set of dominant points. Each break point DPj is labeled by corresponding AVE (Associated Value Error) that is maximum perpendicular distance of all points between DPj−1 and DPj+1 from the straight line DPj−1 DPj+1. An iterative process is applied to remove the break point which has the smallest AVE until the error approximation passes a threshold. This idea is similar to Latecki's approach [26].
Many methods for dominant point detection and polygonal approximation have been proposed. So, an evaluation measure for comparing these existing methods is also a critical request. Sarkar [13] proposed a trade off between the approximating error and the profit of high data reduction that are obtained by the method. The term compression rate (CR) is used for determining the capacity of data reduction. So, he introduced the term figure of merit (FOM) which is a division between CR and ISE (integral square error) as an evaluation criterion for comparing dominant point detectors. Rosin [27] investigated evaluation measures which can be used to compare polygonal approximations with different number of line segments. The assessment is splitted into two components: fidelity and efficiency. The first component measures how well the method fits the curve relative to the optimal polygon concerning approximation error with the same number of line segments. The second one measures how compact the method represents the curve relative to the optimal polygon with the same error. A combined measure (Merit) is defined as the product of both components.
In this paper, we present a new and fast sequential method issued from theoretical results of discrete geometry, it only requires one parameter. It relies on the geometrical structure of the studied curve obtained by considering the decomposition of the curve into maximal blurred segments for a given width [2]. Thanks to this decomposition, a scan process for determining common zones of maximal blurred segments that contain dominant point candidates can be done efficiently. For each common zone, the corresponding dominant point is detected as its central point. Thanks to the advantage of blurred segment notion, our method can work naturally in different scales. In addition, it works naturally with possibly noisy or disconnected curves. These are good properties for shape matching of planar curves based on dominant points.
The rest of the paper is presented as follows. In Section 2, we recall theoretical results of discrete geometry used in this paper to analyze a curve. Section 3 describes our method for dominant point detection with a fixed parameter. Section 4 introduces several experimental results and conclusions.
Section snippets
Discrete line and blurred segment
We recall below several notions concerning discrete lines [28], blurred segments [4], and maximal blurred segments [2] which are used in the next section of this paper. Definition 1 A discrete line , with a main vector (b, a), a lower bound , and an arithmetic thickness (with a, b, and being integer such that the great common division of them is 1, gcd(a, b)=1) is the set of integer points (x, y) verifying . Such a line is denoted by .
For a simplified writing, Debled
Dominant point detection
Dominant point or corner point is a popular notion in pattern recognition, especially in shape representation. The most critical role of dominant points is that they are partitioning points for the decomposition of a curve into meaningful parts. This is one important step in shape analysis. Many methods have been proposed with several definitions for dominant point detection. We recall here the definition of Attneave in the first work [6] about dominant points. Definition 6 A dominant point (corner point)
Experimentation and comparison with other methods
We present in Fig. 8 our obtained results on three well-known curves: chromosome, leaf, semicircle. Fig. 9 shows some experimentation of the proposed method on simple shapes in comparison with Marji's method. Fig. 10, Fig. 11, Fig. 12, Fig. 13 show the comparison with the results obtained by other methods on 3 well-known curves: chromosome, leaf and semicircle.
We have compared our method with others (see Table 3) on some criteria: number of dominant points (nDP), compression ratio (CR), ISE
Application to vectorization
We apply the proposed method for an application of vectorization. Fig. 19 shows a small dataset of four different images whose edge images are given in Fig. 20 by using Canny filter. Each edge image is considered as a set of contour curves. The proposed method is applied on these contour curves to obtain the corresponding image of vectorization.
Fig. 21 and Table 2 presents the obtained results by the proposed method on these edge images. The experimentations are undertaken on a configuration
Conclusion
Detection of dominant points on the curves is a traditional topic in shape representation. It implies applications in image analysis, vectorization and shape matching. In this paper, we have presented a new method for dominant point detection based on the point of view of the discrete geometry. This method utilizes the recent results in this domain to work naturally with noisy curves. The result of this method has been compared with many other methods. It shows its ability to produce high
Acknowledgments
We would like to thank anonymous reviewers for their valuable comments to improve this work.
Thanh Phuong Nguyen received his B.S. in Computer Science from the Ha Noi University of Technology, Vietnam, in 2003 and received his M.Sc. in Computer Science from the French Institute of Computer Science, Vietnam, in 2005. He is now a Ph.D. student in Computer Science at the LORIA, Nancy, under the direction of Isabelle Debled-Rennesson, and a Graduate Assistant at Henri Poincaré Université in Nancy. His research interests include shape representation, discrete geometry, geometric feature
References (42)
- et al.
Optimal blurred segments decomposition of noisy shapes in linear time
Comput. Graph.
(2006) - et al.
A new algorithm for dominant points detection and polygonization of digital curves
Pattern Recognition
(2003) A simple algorithm for detection of significant vertices for polygonal approximation of chain-coded curves
Pattern Recognition Lett.
(1993)A boundary concavity code to support dominant point detection
Pattern Recognition Lett.
(1999)- et al.
Polygonal approximation of closed discrete curves
Pattern Recognition
(2007) - et al.
A piecewise linear approximation method preserving visual feature points of original figures
CVGIP: Graph. Models Image Process.
(1991) - et al.
Polygonal approximation using genetic algorithms
Pattern Recognition
(1999) - et al.
Optimal polygonal approximation of digital planar curves using meta heuristics
Pattern Recognition
(2001) Ant colony search algorithms for optimal polygonal approximation of plane curves
Pattern Recognition
(2003)Dominant point detection by reverse polygonization of digital curves
Image Vision Comput.
(2008)
Maintenance of configurations in the plane
J. Comput. Syst. Sci.
Polygonal representation of digital planar curves through dominant point detection—a nonparametric algorithm
Pattern Recognition
Non-parametric dominant point detection
Pattern Recognition
Finding contour-based abstractions of planar patterns
Pattern Recognition
Wavelet-based corner detection technique using optimal scale
Pattern Recognition Lett.
An adaptive method for detecting dominant points
Pattern Recognition
An algorithm for polygonal approximation of digitized curves
Pattern Recognition Lett.
Detection of significant points and polygonal approximation of digitized curves
Pattern Recognition Lett.
Fast and robust dominant point detection on digital curves
Curvature estimation in noisy curves
Optimal time computation of the tangent of a discrete curve: application to the curvature
Cited by (0)
Thanh Phuong Nguyen received his B.S. in Computer Science from the Ha Noi University of Technology, Vietnam, in 2003 and received his M.Sc. in Computer Science from the French Institute of Computer Science, Vietnam, in 2005. He is now a Ph.D. student in Computer Science at the LORIA, Nancy, under the direction of Isabelle Debled-Rennesson, and a Graduate Assistant at Henri Poincaré Université in Nancy. His research interests include shape representation, discrete geometry, geometric feature estimators and image analysis.
Isabelle Debled-Rennesson graduated in Mathematics and Computer Science. She recieved her PhD degree in Computer Science from Louis Pasteur University, Strasbourg, France in 1995. She is Associate Professor at Henri Poincaré University, in Nancy, France. She is the head of the ADAGIo team of the LORIA Laboratory. Her research interests include digital geometry, image and shape analysis, and discrete modeling.
- ☆
This work is supported by the ANR in the framework of the GEODIB Project, BLAN06-2 134999.