A central problem, called segmentation, is to distinguish objects from background [10]. For intensity images (ie, those represented by point-wise intensity levels) four popular approaches are: threshold techniques, edge-based methods, region-based techniques, and connectivity-preserving relaxation methods.
Threshold techniques, which make decisions based on local pixel information, are effective when the intensity levels of the objects fall squarely outside the range of levels in the background. Because spatial information is ignored, however, blurred region boundaries can create havoc.
Edge-based methods center around contour detection: their weakness in connecting together broken contour lines make them, too, prone to failure in the presence of blurring.
A region-based method usually proceeds as follows: the image is partitioned into connected regions by grouping neighboring pixels of similar intensity levels. Adjacent regions are then merged under some criterion involving perhaps homogeneity or sharpness of region boundaries. Overstringent criteria create fragmentation; lenient ones overlook blurred boundaries and overmerge. Hybrid techniques using a mix of the methods above are also popular.
A connectivity-preserving relaxation-based segmentation method, usually referred to as the active contour model, was proposed recently. The main idea is to start with some initial boundary shape represented in the form of spline curves, and iteratively modify it by applying various shrink/expansion operations according to some energy function. Although the energy-minimizing model is not new, coupling it with the maintenance of an ``elastic'' contour model gives it an interesting new twist. As usual with such methods, getting trapped into a local minimum is a risk against which one must guard; this is no easy task.
In contrast to the heuristic nature of these approaches, computational geometry suggests a more algorithmic tack. One would first formalize a mathematical criterion for the ``goodness'' of a given segmentation. This would allow us to formulate the segmentation problem as an optimization problem under certain geometric constraints.
The objective function that one would seek to optimize is the
interclass variance that is used in discriminant analysis.
Experimentation seems to suggest that this approach might be
very promising.
Formally, the criterion is
described as follows. Imagine that an image is to be partitioned
into two connected sets and
. The average intensity levels
of the sets are denoted by
and
, respectively.
Then, the objective is to minimize the potential function
Computational geometry provides several tools (for instance, hand probing, Monge matrix searching) that lead to efficient solutions for optimal segmentation, as long as one is only interested in separation of an object defined by monotone chains. Without such assumptions the problem is NP-hard, and efficient heuristics remain to be found.
Discriminant analysis has also been applied
successfully to the problem of
transforming an intensity image into a binary black&white picture.
This line of research relates directly to what has
long been an active line of research in
computational geometry, point clustering:
Partition a set of points in
into
clusters so that some inter-cluster criterion is minimized.