On the Detection of Dominant Points on Digital Curves
August 1989 (vol. 11 no. 8)
pp. 859-872
DOI Bookmark:
http://doi.ieeecomputersociety.org/10.1109/34.31447
A parallel algorithm is presented for detecting dominant points on a digital closed curve. The procedure requires no input parameter and remains reliable even when features of multiple sizes are present on the digital curve. The procedure first determines the region of support for each point based on its local properties, then computes measures of relative significance (e.g. curvature) of each point, and finally detects dominant points by a process of nonmaximum suppression. This procedure leads to the observation that the performance of dominant points detection depends not only on the accuracy of the measure of significance, but also on the precise determination of the region of support. This solves the fundamental problem of scale factor selection encountered in various dominant point detection algorithms. The inherent nature of scale-space filtering in the procedure is addressed, and the performance of the procedure is compared to those of several other dominant point detection algorithms, using a number of examples. [1] F. Attneave, "Some informational aspects of visual perception,"Psychol. Rev., vol. 61, no. 3, pp. 183-193, 1954.[2] A. Rosenfeld and E. Johnston, "Angle detection on digital curves,"IEEE Trans. Comput., vol. C-22, pp. 875-878, Sept. 1973.[3] A. Rosenfeld and J. S. Weszka, "An improved method of angle detection on digital curves,"IEEE Trans. Comput., vol. C-24, pp. 940- 941, Sept. 1975.[4] H. Freeman and L. S. Davis, "A corner-finding algorithm for chaincoded curves,"IEEE Trans. Comput., vol. C-26, pp. 297-303, Mar. 1977.[5] P. V. Sankar and C. V. Sharma, "A parallel procedure for the detection of dominant points on a digital curve,"Comput. Graphics Image Processing, vol. 7, pp. 403-412, 1978.[6] I. M. Anderson and J. C. Bezdek, "Curvature and tangential deflection of discrete arcs: A theory based on the commutator of scatter matrix pairs and its application to vertex detection in planar shape data,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-6, pp. 27-40, Jan. 1984.[7] R. L. T. Cederberg, "An iterative algorithm for angle detection on digital curves," inProc. 4th Int. Joint Conf. Pattern Recognition, Kyoto, Japan, Nov. 7-10, 1978, pp. 576-578.[8] B. Kruse and C. V. K. Rao, "A matched filtering technique for corner detection," inProc. 4th Int. Joint Conf. Pattern Recognition, Kyoto, Japan, Nov. 7-10, 1978, pp. 642-644.[9] T. Pavlidis, "Algorithms for shape analysis and waveforms,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-2, pp. 301-312, July 1980.[10] J.G. Dunham, "Optimum uniform piecewise linear approximation of planar curves,"IEEE Trans., vol. PAMI-8, no. 1, pp. 66-75, Jan. 1986.[11] L.-D. Wu, "A piecewise linear approximation based on a statistical model,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-6, pp. 41-45, Jan. 1984.[12] K. Wall and P. Danielsson, "A Fast Sequential Method for Polygonal Approximation of Digitized Curves,"Computer Vision, Graphics, and Image Processing, Vol. 28, No. 2, Nov. 1984, pp. 220-227.[13] J. C. Bezdek and I. M. Anderson, "An application of thec-varieties clustering algorithms to polygonal curve fitting,"IEEE Trans. Syst., Man, Cybern., vol. SMC-15, pp. 637-641, Sept. 1985.[14] H. Imai and M. Iri, "Computational-geometric methods for polygonal approximations of a curve,"Comput. Vision, Graphics, Image Processing, vol. 36, no. 1, pp. 31-34, Oct. 1986.[15] T. Pavlidis,Structural Pattern Recognition. New York: Springer-Verlag, 1977.[16] A. P. Witkin, "Scale-space filtering," inProc. 8th Int. Joint Conf. Artificial Intell., Kalsruhe, West Germany, 1983, pp. 1019-1021.[17] L. S. Davis, "Understanding shape: Angles and sides,"IEEE Trans. Comput., vol. C-26, pp. 236-242, Mar. 1977.[18] A. Rosenfeld and M. Thurston, "Edge and curve detection for digital scene analysis,"IEEE Trans. Comput., vol. C-20, pp. 562-569, May 1971.[19] A. Rosenfeld, M. Thurston, and Y. H. Lee, "Edge and curve detection: Further experiments,"IEEE Trans. Comput., vol. C-21, pp. 677-715, July 1972.[20] L. S. Davis and A. Rosenfeld, "Detection of step edges in noisy one-dimensional data,"IEEE Trans. Comput., vol. C-24, pp. 1006-1010, Oct. 1975.[21] J. A. Saghri and H. Freeman, "Analysis of the precision of generalized chain codes for the representation of planar curves,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-3, pp. 533-539, Sept. 1981.[22] J. R. Bennett and J. S. MacDonald, "On the measurement of curvature in a quantized environment,"IEEE Trans. Comput., vol. C-24, pp. 803-820, Aug. 1975.[23] M. J. Eccles, P. C. McQueens, and D. Rosen, "Analysis of the digitized boundaries of planar objects,"Pattern Recognition, vol. 9, pp. 31-41, 1977.[24] F. C. A. Groan and P. W. Verbeek, "Freeman-code probabilities of object boundary quantized contours,"Comput. Vision, Graphics, Image Processing, vol. 7, pp. 391-402, 1978.[25] B. Rosenberg, "The analysis of convex blobs,"Comput. Graphics Image Processing, vol. 1, pp. 183-192, 1972.[26] D. Langridge, "On the computation of shape," inFrontiers of Pattern Recognition, S. Watanabe, Ed. New York: Academic, 1972, pp. 347-365.[27] A. Rosenfeld and A. Kak,Digital Picture Processing, New York: Academic, 1976.
Index Terms:
dominant point detection; computerised picture processing; computerised pattern recognition; digital curves; parallel algorithm; scale factor selection; scale-space filtering; computerised pattern recognition; computerised picture processing; filtering and prediction theory; parallel algorithms
Citation:
C.H. Teh, R.T. Chin, "On the Detection of Dominant Points on Digital Curves," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 11, no. 8, pp. 859-872, Aug. 1989, doi:10.1109/34.31447
Usage of this product signifies your acceptance of the
Terms of Use.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb