1 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 18, NO. 12, DECEMBEFI 1996 1211. A Transform for Multiscale Image Segmentation by integrated Edge and Region detection Narendra Ahuja, Fellow, / E Computer Society 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.
2 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 kansform 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.)
3 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, , those containing noise and shading. Thus the proposed method is intended as a solution to the problem of Multiscale , integraled 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 . Index Terms-Image segmentation, representation, scale-space, edge detection , region detection , perceptual structure, pyramids, medial axis, nonlinear image analysis, texture. +. 1 INTRODUCTION. HIS paper is concerned with the problem of low level T image segmentation, or partitioning of an image into regions , that represent low level image structure.
4 A region If the amount of acceptable variability and the contrast value of the regions are reduced, the frames of the eye- glasses and the ear emerge as new, smaller regions . If the is characterized as possessing a certain degree of interior homogeneity and sensitivity to contrast are increased fur- homogeneity and a contrast with the surround which is ther, nose and lips sepairate as regions from the rest of the large compared to the interior variation. This is a satisfac- face. Thus, a decrease in the acceptable contrast leads to tory characterization from both perceptual and quantitative increased, hierarchical decomposition, which culminates in viewpoints. Homogeneity and contrast may be defined constant-value regions at the bottom of the hierarchy. In differently: A region may be uniform, in which case its another window in the same image, , the upper window contrast with the surround must be large; alternatively, a shown in Fig.
5 Loa, the depth of the hierarchy and the region region may be shaded, in which case the local contrast homogeneity, contrast, :shape and size parameters associ- across a boundary point must be large compared to the ated with the different levels are unrelated to the corre- interior variation on each side. The sizes, shapes, types of sponding values in the lower window. Thus, in the tree homogeneity, and contrast values of regions in an image representing the entire image, features such as depth and are a priori unknown. To illustrate, consider the image branching factor are unrelated across subtrees, each solely shown in Fig. loa, which shows people at a 3D movie. determined by the image and therefore a priori unknown. Within the lower of the two windows shown, the lenses The homogeneity and contrast parameters associated with and the rest of the head form two regions having homoge- different image regions will be said to form the set of pho- neous intensities and large contrasts with their surrounds.
6 Tometric scales present in the image, while the region shapes and sizes will be said to define the geometric scales present. The author is with Beckmun Institute, Coordinated Science Laboratoy, and Department of Electrical and Computer Engineering, University of Illinois Finding a solution of the low level segmentation prob- at Urbana-Champaign, Urbana, IL 61801. lem poses two main challenges. First, a valid image region E-mail: must be detected regardlless of its shape, size, type of ho- Manuscript received July 12,1994; revised June 10,1996. Recommended for accep- mogeneity, and contrast. Second, all geometric and pho- tance by A. lain. tometric scales at which regions happen to occur across an For information on obtaining reprints of this article, please send e-mail to: reference IEEECS Log Number P96083, image must be identified.
7 If these two problems are solved, 00 01996 IEEE. 0162-8828/96505. 1212 IEEE TRANSACTIONS ON PA-ERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 18, NO. 12, DECEMBER 1996. the result will be a segmentation tree representing the mul- collecting globally distributed evidence for image structure tiscale, low level, image structure. To obtain such a tree for and making it available locally, , at the locations of re- an arbitrary gray-scale image is the objective of image seg- gion edges and medial axes (The medial axis of a region is mentation pursued in this paper. defined as the locus of points inside the region which are Limited work has been done to meet both of the above equidistant from two or more points on the region bound- challenges. Much of the previous work on Multiscale analysis ary , 1161.)
8 The regions are encoded in the force field via is concerned with a scale-space decomposition of the image distinct signatures amenable to robust, local identification. signal, determined by a single scale parameter. The decom- In this sense, the Transform performs Gestalt analysis. position amounts to a blurring of the image to different de- This paper introduces the Transform and shows how it grees. The image structure is present across this scale-space can be used for segmentation (the basic idea of the trans- continuum, and methods for extracting image regions of dif- form can be found in ill). It does not present specific seg- ferent sizes and contrasts from this continuum are not avail- mentation algorithms. The segmentation is intended to rep- able. Further, even if they were extracted, the regions in the resent low-level image structure at all scales, thus with ap- different decompositions would be correspondingly de- plicability to textured as well as smooth images.
9 To analyze formed. Automatic estimation of scale parameters is typically and illustrate the basic properties of the Transform , we not addressed. Even at a given scale, robust detection of a model regions , whenever necessary, as possessing uniform region continues to be an area of active investigation, mainly gray levels and step edges . However, the Transform prop- through the work on edge detection . Region detection such erties and segmentation results are shown to apply to im- that the detected boundaries are closed and coincident with ages containing general types of regions as discussed the true region boundaries regardless of region parameters is above, , having shading and noise. Section 2 discusses not a solved problem. Most methods are linear and often use some basic desired characteristics of segmentation and how restrictive region models, , allowed geometric and pho- they motivate the proposed approach.
10 Section 3 describes tometric complexity of edges . Although these models sim- the Transform , describes some of its properties of interest, plify processing, they cause fundamental limitations in the and shows how these properties facilitate Multiscale seg- detection accuracy and sensitivity achieved which is partly mentation. Section 4 analyzes the segmentation perform- why the problem of region and edge detection continues to ance of the Transform , and Section 5 describes some ex- evade a satisfactory solution. periments conducted to demonstrate this performance. A central theme of this paper is to meet both of the Section 6 presents concluding remarks. aforementioned challenges, namely, accurate detection of regions without using rigid, geometric, and photometric models and automatic estimation of all scales associated 2 BACKGROUND.