Region Segmentation of Images by Expansion and Contraction of Edge Points
Proceedings of the Sixth International Joint Conference on Artificial Intelligence. .
© 1979 International Joint Conferences on Artificial Intelligence
Abstract
A new method for segmenting images using edge points to separate regions of smoothly varying intensity is discussed, Region segmentation using edge points has not been very successful in the past because small gaps would allow merging of dissimilar regions. The present method uses an expansion-contraction technique in which the edge regions are expanded to close gaps and then contracted after the separate uniform regions have been identified. In order to perserve small uniform regions, the process is performed iteratively with increasing expansions, but no expansion for edge regions that already separate different regions. The final result is a set of uniform intensity regions (usually less than 100) and a set of edge boundary regions. The program has successfully segmented scenes with industrial parts, landscapes, and IC chips.
- McKee, J. w., and Aggarwal, J. K., "Finding the Edges of the Surfaces of Three-Dimensional Curved Objects by Computer." Pattern Recognition. 7:1 (1975) 25-52.
- Perkins, W, A., "A Model-Based Vision System for Industrial Parts." IEEE Trans. Comput., C-27:2 (1978) 126=143.
- Brice, c. R., and Fennema, C. L., "Scene Analysis Using Regions." Artif. Intell. 1:3 (1970) 205-226.
- Yakamovsky, Y,, and Feldman, J, A., "A Semantics-Based Decision Theory Region Analyzer." in Proc. IJCAI-73. Stanford, Stanford, Calif., 1973, pp. 58Q-588,
- Oblander, R. B., "Analysis of Natural Scenes." PhD thesis, Carnegie-Mellon University, Pittsburgh, Pennsylvania, April, 1975.
- Rosenfeld, A., Park, c. M,, and Strong, J, P,, "Noise Cleaning in Digital Pictures." EASCON '69 Record, (1969) 264- 273.
- Baird, M, L., "Image Segmentation Technique for Locating Automotive Parts on Belt Conveyors." in Proc. IJCAI-77. IJCAI
- Jacobus, c., and Chien, R, T., "Variable Neighborhood Computations In Scene Analysis." University of Illinois CSL Report T-60 (1978).
- Duda, R. 0,, and Hart, P. E., Pattern Classification and Scene Analysis. Wiley and Sons (1973) pp. 271-272.
- Eberlein, R. B., "An Iterative Gradient Edge Detection Algorithm." Computer Graphics and Image Processing, 5: (1976) 245-253.
- Perkins, W, A., "Area Segmentation of Images Using Edge Points." IEEE Trans. Pattern Analysis and-;&Chine Intelligence. To be published,
- Kelly, M, D., "Visual Identification of People by Computer." PhD thesis, Stanford Artif. Intell. Project Memo AIM-130, Stanford University, 1970, PP• 54-55.
- Milgram, D. L., "Region Extraction Using Convergent Evidence." University of Maryland Report TR-674, June, 1978.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1. INTRODUCTION
It is generally agreed that it is necessary to organize the image data as the first step in image understanding. In organizing the image data two courses of action are generally employed: (1) Locating discontinuities in intensity (edge points) and connecting them [1,2], and (2) Trying to find regions of fairly uniform intensity by growing regions [3,4] or thresholding at a calculated level [5].
The goal of the latter approach is to segment the picture into a set of uniform intensity regions to increase the degree of organization. The early methods involved merging regions sharing the weakest boundary in an iterative process [3,4] until the weakest boundary was stronger than some threshold. To continue merging regions in complex pictures, it was necessary to use semantic information [4], limiting the general usefulness of the method. A thresholding technique developed by Oblander (5] was found to be very effective on complex
color pictures.
Because of the shortcomings of the region growing method (without semantic information) and failure of the simple histogram thresholding approach to work on monochromatic pictures in general, ~e developed an entirely different method. It uses an expansion contraction technique in which edge regions are expanded to close gaps and then contracted after the separate regions have been labeled. Expansion-contraction techniques have been very useful for the analysis of binary pictures [6], but their us.e on edge data has been limited [7,8].
2. SEGMENTATION METIIOD
In transforming the gray-level picture into regions of uniform intensity, processes 2.12.8 are performed serially with processes 2.32.7 performed in three cycles of 0, 1, and 2 pixel expansion. The segmentation techniques will be illustrated using Fig. la. The resolution is 240 by 256 with 32 gray levels, and its intensity histogram is shown in Fig. lb. Note that this picture is not thresholdable by Oblander's criteria (5] of
ratio of peak maximum to peak minimum ~ 2.
2.1 Edge-Finding
Figure lc was obtained by applying the Sobel edge operator [9] at every pixel of the gray level picture (Fig. la).
2.2 Thinning
Eberlein's relaxation algorithm [10] was used to thin the edges. A threshold was calculated from the curvature of the thinned edge distribution [11]. Figure ld shows the results of thinning and thresholding the edge picture.
2,3 Expanding Edge Points
Expansion of edge points is necessary to fill small gaps in the edge boundaries. The present method involves no expansion of pixels which touch two different regions [11]. The expansion was done in three stages: (1) no expansion (see Fig. ld), (2) expansion of edge pixels to fill a 3 by 3 pixel square (see Fig. 2a), and (3) expansion of edge pixels to fill a 5 by 5 square (see Fig. 2b).

lai

lei
N

iNTENSITY LEVEL
lbi

ldi
Fig, 1, (a) Digitized picture of some industrial parts. (b) Intensity histogram. (c) Edge magnitude. (d) Thresholded thinned edge array.
2.4 Labeling Uniform Intensity Regions with Connectivity AlJorithm
Using the expanded edge boundary between uniform intensity regions, pixels in each uniform intensity region are connected by giving each pixel the same label with a four connected algorithm [12]. Uniform intensity regions are taken to be four-connected and edge regions eight-connected [13].
2,5 Eliminating Small Uniform Intensity Regions
For simplicity, small uniform regions (less than 10 pixels) are eliminated by merging them into their surrounding edge region,
2,6 Shrinking Edge Regions
Edge regions are contracted by replacing "expansion" edge pixels with uniform intensity region numbers [11].
2.7 Placing Edge Boundaries Between Uniform Intensity Regions

lei ldi
Fig. 2. (a) Expansion of edges to fill 3 by 3 square. (b) Expansion of edges to fill 5 by 5 square. (c) Edge regions after final contraction and elimination of small regions. (d) Reconstructed gray-level picture with bright edge regions, Total CPU time · 31 sec. on IBM 370/3033.
After removing artificial edges (process 2.6). some region pixels are replaced by edge pixels to separate different regions,
2,8 Eliminating Small Edge Regions
For simplicity, small isolated edge regions are eliminated after the segmentation into uniform intensity regions is finished. Figure 2c shows the final edge regions after shrinking and eliminating small regions, The thick edge regions are indicative of textured areas [11],
The gray-level picture of Fig, 2d was generated using the average-intensity region data, Edge regions are shown at the maximum brightness. A comparison of Fig. 2d and Fig. la shows that the initial data has been greatly simplified by the organizational process with a slight loss in detail. The final result is 72 uniform intensity regions and 10 edge regions.
3. RESULTS
This segmentation technique was tested on many scenes. Figure 3a (206 by 255 with 8 bit resolution) shows a landscape scene that was analyzed previously by a region growing technique (see Fig. C of [4]). The final result (Fig. 3d) has 38 uniform intensity regions and 5 edge regions which embody more of the meaningful information than the results of the non-semantic region grower (Fig. C2 of [4)).
When does this segmentation method fail? It fails if the gaps between the edge points are so large that the expansion cannot close them as illustrated in Figs. 1 and 2 for the universal yoke in the lower right-hand corner. Some possible methods of eliminating this type of failure (such as using boundary coincidence of edge points and intensity threshold [14]) are discussed in [11].

(c)
Fig. 3. (a) Digitized picture of landscape scene. {b) Thresholded thinned edge array. {c) Final edge regions. (d) Reconstructed gray-level picture with bright edge regions. Total CPU time · 27 sec. on IBM 370/3033,
4. CONCLUSIONS
The area segmentation method described here has some advantages over the region-growing and histogra~thresholding techniques. Without semantic information, it can segment an image better than the region growing technique. For many scenes (particularly monochromatic images) the intensity histograms do not have clearly separated peaks (see for example Fig. lb) and often there .is no optimum threshold, although clear edge boundaries exist [14].
ACKNOWLEDGEMENTS
The author wishes to thank L. Rossol and G. G. Dodd for their interest and encouragement throughout this project.
@inproceedings{ijcai1979p154,
title = {Region Segmentation of Images by Expansion and Contraction of Edge Points},
author = {Perkins, W. A.},
booktitle = {Proceedings of the Sixth International Joint Conference on
Artificial Intelligence, {IJCAI-79}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Bruce G. Buchanan},
year = {1979},
month = {8},
url = {https://ijcai.org/proceedings/1979/154},
}
TY - CPAPER TI - Region Segmentation of Images by Expansion and Contraction of Edge Points AU - Perkins, W. A. T2 - Proceedings of the Sixth International Joint Conference on Artificial Intelligence, IJCAI-79 PB - International Joint Conferences on Artificial Intelligence PY - 1979 UR - https://ijcai.org/proceedings/1979/154 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: