Linear-time algorithms for region growing with applications to image and curve segmentation
Peter Veelaert · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1997
The goal of segmentation is to partition a digital image or curve into segments such that the points in each segment share a common property. For example, we can partition a curve into connected subsets such that the points of each subset lie on a common straight line, or we can partition an image such that intensity function is linearly varying when restricted to ne part. A region growing algorithm starts from a small seed segment, and then repeatedly tries to add new points to this segment. Each time a point is added seed segment, whether the segmentation criterion is still satisfied for the enlarge segment, otherwise a new segment is started. In general, the verification of the segmentation criterion becomes increasingly more difficult when the segment gets larger. We propose new linear-time algorithms for region growing. These algorithms are related to the economical design of mechanical frameworks, where the goal is to make a rigid construction with as few bars as possible. According to this analogy, the region growing algorithm tries to attach each new point as firmly as possible to the existing region with a minimal amount of computation. We illustrate this technique for the segmentation of digital curves into straight or parabolic line segments, and for image segmentation with segments of linearly varying intensity.