| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
A Transform for Multiscale Image Segmentation by Integrated Edge and Region Detection
December 1996 (vol. 18 no. 12)
pp. 1211-1235
Abstract—This paper describes a new transform to extract image regions at all geometric and photometric scales. It is argued that linear approaches such as convolution and matching have the fundamental shortcoming that they require a priori models of region shape. The proposed transform avoids this limitation by letting the structure emerge, bottom-up, from interactions among pixels, in analogy with statistical mechanics and particle physics. The transform involves global computations on pairs of pixels followed by vector integration of the results, rather than scalar and local linear processing. An attraction force field is computed over the image in which pixels belonging to the same region are mutually attracted and the region is characterized by a convergent flow. It is shown that the transform possesses properties that allow multiscale segmentation, or extraction of original, unblurred structure at all different geometric and photometric scales present in the image. This is in contrast with much of the previous work wherein multiscale structure is viewed as the smoothed structure in a multiscale decimation of image signal. Scale is an integral parameter of the force computation, and the number and values of scale parameters associated with the image can be estimated automatically. Regions are detected at all, a priori unknown, scales resulting in automatic construction of a segmentation tree, in which each pixel is annotated with descriptions of all the regions it belongs to. Although some of the analytical properties of the transform are presented for piecewise constant images, it is shown that the results hold for more general images, e.g., those containing noise and shading. Thus the proposed method is intended as a solution to the problem of multiscale, integrated edge and region detection, or low-level image segmentation. Experimental results with synthetic and real images are given to demonstrate the properties and segmentation performance of the transform.
[1] 1211 N. Ahuja, "A Transform for Detection of Multiscale Image Structure," Proc. Computer Vision and Pattern Recognition, pp. 780-781,New York, 1993.[2] N. Ahuja and J.-H. Chuang, “Shape Representation Using a Generalized Potential Field Model,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 19, no. 2, pp. 169-176, Feb. 1997.[3] N. Ahuja, "A Transform for Multiscale Image Segmentation," Beckman Institute Technical Note, no. 96-01, July 1995.[4] V. Berzins, "Accuracy of Laplacian Edge Detectors," Computer Vision, Graphics, and Image Processing, vol. 27, pp. 195-210, 1984.[5] T. Binford, "Inferring Surfaces from Images," Artificial Intelligence, vol. 17, pp. 205-244, Aug. 1981.[6] H. Blum, "A Transformation for Extracting New Descriptors of Shape," Models for the Perception of Speech and Visual Form, edited by W. Dunn. Cambridge, Mass.: MIT Press, pp. 362-380, 1967.[7] R. Boomgaard and A. Smeulders, "Towards a Morphological Scale-Space Theory," Shape in Picture: Mathematical Descriptions of Shape in Grey-Level Images.New York: Springer-Verlag, pp. 631-640, 1992.[8] J. Canny, “A Computational Approach to Edge Detection,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 8, no. 6, pp. 679-698, June 1986.[9] I.J. Clark, "Authenticating Edges Produced by Zero-Crossing Algorithms," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 11, no. 1, pp. 43-57, Jan. 1989.[10] L.S. Davis, "A Survey of Edge Detection Techniques," Computer Graphics and Image Processing, pp. 248-270, 1975.[11] S. Geman and D. Geman, "Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 6, no. 11, pp. 721-741, 1984.[12] R.M. Haralick, "Digital Step Edges from Zerocrossings of Second Directional Derivative," IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 58-68, 1984.[13] R.M. Haralick and L. Shapiro, "A Survey of Image Segmentation Techniques," Computer Vision, Graphics and Image Processing, vol. 29, pp. 100-132, 1985.[14] S.L. Horowitz and T. Pavlidis, "Picture Segmentation by a Directed Split and Merge Procedure," Proc. Second Int'l Joint Conf. Pattern Recognition, pp. 424-433, 1974.[15] A.K. Jain and R.C. Dubes, Algorithms for Clustering Data. Englewood Cliffs, N.J.: Prentice Hall, 1988.[16] J. Koënderink, Solid Shape. Cambridge, Mass.: MIT Press, 1991.[17] T. Lindeberg, Scale-Space Theory in Computer Vision. Kluwer Academic, 1994.[18] T. Lindeberg and J.O. Eklundh, “Scale Space Primal Sketch Construction and Experiments,” Image Vision Computing, vol. 10, pp. 3-18, 1992.[19] Y. Lu and R.C. Jain, "Behavior of Edges in Scale Space," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 11, pp. 337-356, Apr. 1989.[20] J. Malik and P. Perona, "Edge Detection by Diffusion," technical report, Univ. of California, Berkeley, 1986.[21] D. Marr and E. Hildreth, "A Theory of Edge Detection," Royal Society of London, vol. B-207, pp. 187-217, 1980.[22] F. Meyer and S. Beucher, "Morphological Segmentation," Vis. Comm. Image Representation, vol. 1, no. 1, pp. 21-46, 1990.[23] A. Montanvert, P. Meer, and A. Rosenfeld, Hierarchical Image Analysis Using Irregular Tesselations IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 13, no. 4, pp. 307-316, Apr. 1991.[24] B.S. Morse, S.M. Pizer, and A. Liu, "Multiscale Medial Analysis of Medical Images," Proc. 14th Int'l Conf. Information Processing in Medical Imaging, edited by H. Barrett and A. Gmitro. New York: Springer-Verlag, 1993.[25] D. Mumford and J. Shah, "Boundary Detection by Minimizing Functionals, i." IEEE Conf. Computer Vision and Pattern Recognition, pp. 22-26, 1985.[26] V.S. Nalwa and T.O. Binford, “On Detecting Edges,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 8, no. 6, pp. 699-714, 1986.[27] V.S. Nalwa, "Experiments with a Spatiotemporal Correlator," IEEE Conf. Computer Vision and Pattern Recognition, pp. 712-716, 1992.[28] P. Perona and J. Malik, "Detecting and Localizing Edges Composed of Steps, Peaks and Roofs," Proc. Third Int'l Conf. Computer Vision,Osaka, Japan, pp. 52-57, 1990.[29] J. Ponce and M. Brady, "Toward a Surface Primal Sketch, Technical Report MIT-AI-TR-824, Massachusetts Institute of Tech nology, 1985.[30] A. Rosenfeld and A.C. Kak,Digital Picture Processing. Academic Press, 2nd ed., 1982[31] A. Rosenfeld and M. Thurston, "Edge and Curve Detection for Visual Scene Analysis," IEEE Transactions on Computers, pp. 562-569, 1971.[32] R. Whitaker and S. Pizer, "Geometry-Based Image Segmentation Using Anisotropic Diffusion," Shape in Picture: Mathematical Descriptions of Shape in Grey-Level Images.New York: Springer-Verlag, pp. 641-650, 1992.[33] A. Witkin, "Scale Space Filtering," Int'l Joint Conf. Artificial Intelligence, 1983.[34] A. Yuille and T. Poggio, "Scaling Theorems for Zero Crossings," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 8, pp. 15-26, Jan. 1986.[35] M. Brady and H. Asada, "Smoothed Local Symmetries and Their Implementation," Int'l J. Robotics Research, vol. 3, no. 3, pp. 36-61, 1984.[36] S.P. Singh, "Transfer of Learning by Composing Solutions of Elemental Sequential Tasks," Machine Learning, vol. 8, pp. 323-339, 1992.
Index Terms:
Image segmentation, representation, scale-space, edge detection, region detection, perceptual structure, pyramids, medial axis, nonlinear image analysis, texture.
Citation:
Narendra Ahuja, "A Transform for Multiscale Image Segmentation by Integrated Edge and Region Detection," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 18, no. 12, pp. 1211-1235, Dec. 1996, doi:10.1109/34.546258
