Shape Representation by Multiscale Contour Approximation
|
An approach is presented for deriving qualitative descriptions of contours containing structures at different (unknown) scales. The descriptions are in terms of straight arcs, curved arcs with sign of curvature, corners, and points delimiting the arcs: inflexion points and transitions from straight to curved. Furthermore, the tangents at these points are derived. The approach is based on the construction of a hierarchic family of polygons, having the scale-space property of causality; structure can only disappear as scale goes from fine to coarse. Using the principle that structures that are stable over scale represent significant properties, the features of the descriptive representations are then derived.
[1] 85H. G. Barrow and J. M. Tenenbaum, "Interpreting line drawings as three-dimensional surfaces,"Artificial Intell., vol. 17, pp. 75-116, 1981.
[2] T. Kanade, "Geometrical aspects of interpreting images as a three-dimensional scene,"Proc. IEEE, vol. 71, pp. 789-802, 1983.
[3] D.G. Lowe and T.O. Binford, "The recovery of three-dimensional structure from image curves,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-7, pp. 320-326, 1985.
[4] H. H. Baker and T. O. Binford, "Depth from edge and intensity based stereo," inProc. 7th IJCAI, Vancouver, B.C., Canada, 1981, pp. 631-636.
[5] J. K. Aggarwal and A. Mitiche, "Structure and motion from images," inProc. Darpa Image Understanding Workshop, 1985, pp. 89-98.
[6] H. H. Bülthoff and H. A. Mallot, "Interaction of different modules in depth perception, "inProc. 1st ICCV, London, 1987, pp. 295-305.
[7] S.W. Zucker, C. David, L. Dobbins, and L. Iverson, "The organization of curve detection: Coarse tanget fields and fine spline coverings," inProc. 2nd ICCV, Tarpon Springs, FL, 1988, pp. 568-577.
[8] D. Lowe, Perceptual Organization And Visual Recognition. Boston: Kluwer, 1985.
[9] N. Ayache and O.D. Faugeras, "Maintaining representations of the environment of a mobile robot," inProc. Int. Symp. Robotics Research, Santa Cruz, CA, 1987.
[10] A. Rosenfeld and M. Thurston, "Edge and curve detection for visual scene analysis,"IEEE Trans. Comput., vol. C-20, pp. 562-569, 1971.
[11] A.P. Witkin, "Scale-space filtering," inProc. IJCAI-83, Karlsruhe, West Germany, 1983, pp. 1019-1022.
[12] J. Koenderink, "The structure of images,"Biol. Cybern., vol. 50, pp. 363-370, 1984.
[13] A. Yuille and T. Poggio, "Scaling theorems for zero crossings,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-8, no. 1, pp. 15-25, 1986.
[14] F. Moktarian and A. Mackworth, "Scale-based description and recognition of planar curves and two-dimensional shapes,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-8, no. 1, pp. 34-43, Jan. 1986.
[15] A. K. Mackworth and F. Mokhtarian, "The renormalized curvature scale-space and the evolution properties of planar curves," inProc. CVPR, Ann Arbor, MI, 1988, pp. 298-303.
[16] D. G. Lowe, "Organization of smooth image curves at multiple scales," inProc. 2nd Int. Conf. Computer Vision, 1988, pp. 558-567, 1988.
[17] B. B. Kimia, "Conservation laws and a theory of shape," Ph.D. dissertation, McGill Univ., Montreal, P.Q., Canada, 1989.
[18] B. B. Kilmia, A. Tannenbaum, and S.W. Zucker, "Towards a computational theory of shape," inProc. 1st ECCV, Antibes, 1990, pp. 402-407.
[19] M. A. Fischler and R. C. Bolles, "Perceptual organization and the curve partitioning problem," inProc. IJCAI-83, Karlsruhe, West Germany, 1983, pp. 1014-1018.
[20] T. Lindeberg and R. Weiss, "Some thoughts about curves, surfaces, and singularity theory," CVAP, Royal Inst. Technol., Stockholm, Sweden, Rep. TN-04, 1990.
[21] A. Bengtsson, J. O. Eklundh, and J. Howako, "Shape representation by multiscale contour approximation," Royal Inst. Technol., Stockholm, Sweden, Rep. TRITA-NA-8607, 1986.
[22] J. O. Eklundh and J. Howako, "Robust shape description based on curve fitting," inProc. 7th ICPR, Montreal, P.Q., Canada, 1984, pp. 109-112.
[23] A. Bengtsson, "An algorithm for estimation of shape properties at multiple scales," Royal Inst. Technol., Stockholm, Sweden, in preparation, 1989.
[24] C. de Boor,A Practical Guide to Splines. New York: Springer-Verlag, 1978.
[25] T. Pavlidis, "Curve fitting with conic splines,"ACM Trans. Graphics, vol. TOGS-1, pp. 1-31, 1983.
[26] T. Lindeberg and J. O. Eklundh, "On the computation of a scale-space primal sketch," submitted for publication.
[27] F. Ulupinar and R. Nevatia, "Using symmetries for analysis of shape from contour," inProc. 2nd ICCV, Tarpon Springs, FL, 1988, pp. 414-426.
Index Terms:
shape representation; scale stability; multiscale contour approximation; qualitative descriptions; straight arcs; curved arcs; corners; points delimiting the arcs; inflexion points; polygons; scale-space property of causality; computer vision; computerised pattern recognition; computerised picture processing
Citation:
A. Bengtsson, J.O. Eklundh, "Shape Representation by Multiscale Contour Approximation," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 13, no. 1, pp. 85-93, Jan. 1991, doi:10.1109/34.67634
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb