Elsevier

Pattern Recognition

Volume 44, Issue 1, January 2011, Pages 32-44
Pattern Recognition

A discrete geometry approach for dominant point detection,☆☆

https://doi.org/10.1016/j.patcog.2010.06.022Get rights and content

Abstract

We propose two fast methods for dominant point detection and polygonal representation of noisy and possibly disconnected curves based on a study of the decomposition of the curve into the sequence of maximal blurred segments [2]. Starting from results of discrete geometry [3], [4], the notion of maximal blurred segment of width ν [2] has been proposed, well adapted to possibly noisy curves. The first method uses a fixed parameter that is the width of considered maximal blurred segments. The second method is deduced from the first one based on a multi-width approach to obtain a non-parametric method that uses no threshold for working with noisy curves. Comparisons with other methods in the literature prove the efficiency of our approach. Thanks to a recent result [5] concerning the construction of the sequence of maximal blurred segments, the complexity of the proposed methods is O(n log n). An application of vectorization is also given in this paper.

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 pikpi+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 D(a,b,μ,ω), 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 μaxby<μ+ω. Such a line is denoted by D(a,b,μ,ω).

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)

  • M. Overmars et al.

    Maintenance of configurations in the plane

    J. Comput. Syst. Sci.

    (1981)
  • M. Marji et al.

    Polygonal representation of digital planar curves through dominant point detection—a nonparametric algorithm

    Pattern Recognition

    (2004)
  • N. Ansari et al.

    Non-parametric dominant point detection

    Pattern Recognition

    (1991)
  • C. Arcelli et al.

    Finding contour-based abstractions of planar patterns

    Pattern Recognition

    (1993)
  • A. Quddus et al.

    Wavelet-based corner detection technique using optimal scale

    Pattern Recognition Lett.

    (2002)
  • W.-Y. Wu

    An adaptive method for detecting dominant points

    Pattern Recognition

    (2003)
  • B.K. Ray et al.

    An algorithm for polygonal approximation of digitized curves

    Pattern Recognition Lett.

    (1992)
  • B.K. Ray et al.

    Detection of significant points and polygonal approximation of digitized curves

    Pattern Recognition Lett.

    (1992)
  • T.P. Nguyen et al.

    Fast and robust dominant point detection on digital curves

  • T.P. Nguyen et al.

    Curvature estimation in noisy curves

  • F. Feschet et al.

    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.

    ☆☆

    Based on “Fast and robust dominant points detection on digital curves” by T.P. Nguyen and I. Debled-Rennesson in Proceedings of ICIP’09 [1].

    View full text