Segmentation by "Painting"

Mark A. Ruzon

Segmentation has always been the goal of early vision. If we could divide an image into regions with a reliable assurance that each region represents part of an object in the world (although the question "What constitutes a part?" is sticky enough for humans, let alone computers), then we might have a reasonable chance to analyze the parts independently, recognize them, and combine them to form the context of an image.

Unfortunately, edges, even if properly detected, do not necessarily form closed curves that partition an image. Some edges may contain gaps due to occlusions or unusual amounts of noise, while other edges may be isolated, not connecting to other edges. Furthermore, many operators (including both Canny's and the compass operator) exhibit a "rounding off" of corners. If one were to merely follow an edge, then we would actually miss the corner entirely, because the response at the corner is never as strong as the response a few pixels inside it. If we want to connect edges and corners, a new approach must be found.

The "painting" concept can be summarized as follows: if an operator detects an edge (or a corner) at a point, then the hypothesized edge (or corner) should be "painted" onto the image by labeling pixels that lie on that edge (or corner). The result will itself be a region; the boundary between two different parts of an image will be many pixels wide (unless the edge is perfectly straight). We can then remove small image regions and boundary regions that do not affect the topology of the segmentation to get an answer.

Below is the result of this process applied to a natural landscape using the output of a compass operator at a radius of 8 pixels and a strength threshold of 0.7:

No hysteresis thresholding has been done; only one threshold has been applied. Nevertheless, the painting algorithm creates a moderately good segmentation on a difficult image.

The critical question, though, concerns the nature of a boundary as it has been described here. Why is a boundary a region, and not a curve? Though it is true that the boundary between two regions in the world is a curve, that curve will almost never be represented precisely in an image. Lenses are imperfect, so that even if two objects are in focus, there will always be some blur. For objects not in focus, the effect is worse. Furthermore, if parts of an object are unresolvable by the camera because of distance (think of the leaves of a tree), it will be impossible to draw a single curve that separates the two regions. A boundary region may be the best we can hope for.