Improving Image Segmentation Through Evaluation Function Analysis

EPA Grant Number: U915196
Title: Improving Image Segmentation Through Evaluation Function Analysis
Investigators: Langford, Bill
Institution: Oregon State University
EPA Project Officer: Packard, Benjamin H
Project Period: January 1, 1997 through January 1, 2000
Project Amount: $102,000
RFA: STAR Graduate Fellowships (1997) RFA Text |  Recipients Lists
Research Category: Academic Fellowships , Engineering and Environmental Chemistry , Fellowship - Computer Science and Engineering


The goal of this research project is to improve optimization algorithms used in segmenting environmental images by analyzing and steering the evaluation functions that guide the optimization. Segmentation is the process of defining boundaries around homogeneous segments of an image as opposed to the classification of the contents of those segments (e.g., according to land cover type).


Many algorithms have been proposed for segmentation images, but none have shown widespread applicability. One method that often gives visually pleasing results is morphological reconstruction. This algorithm takes a segmentation that has too many small regions, and it uses a heuristic evaluation function to combine ones with low local contrast. This contrast measure is computed as a function of the minimum edge height values of regions and their boundaries. Thresholding the contrast measure at different levels produces segmentations at various scales of detail. Although these segmentations are usually intuitively sensible, they often do not match the details of a segmentation given by an ecologist when they are defining polygons related to variables such as habitat type, regardless of what parameters are used in the segmentation algorithm. In our research, we have statistically analyzed the reasons for this failure. We also have also developed a proof showing that an entire class of deterministic merging algorithms such as this one have a restricted hypothesis space that is only capable of representing n out of 2^n possible segmentations for any given image (where n is the number of inter-region boundaries). This shows that in general, tuning these algorithms is uselesscannot do any good because they can only express a tiny fraction of the possible segmentations of any image.

Because morphological reconstruction can be viewed as a "greedy" optimizer, it is essentially the combination of a particular evaluation function with a particular strategy for generating the next guessestimate, and we can substitute other mechanisms for either or both elements of this combination. To remedy the shortcomings of reconstruction, we design various replacements for the evaluation function based on the use of more robust statistics than local minima and on identifying local approximations to external evaluation criteria that are adapted to each problem. Finally, we make use of stochastic optimizers to enable us to search a larger hypothesis space. The resulting algorithms are applied to images from several domains, where the desired segmentation is known.

Supplemental Keywords:

fellowship, image segmentation, evaluation function analysis, optimization algorithms, environmental images, segmentation, segmentation images., RFA, Scientific Discipline, Ecosystem Protection/Environmental Exposure & Risk, Mathematics, computing technology, environmental images, morphological reconstruction, optimization algorithms, segmentation, computer science, information technology, optimization modeling, evaluation functional analysis

Progress and Final Reports:

  • 1997
  • 1998
  • Final