National Aeronautics and Space Administration

Logical Predicate Image Segmentation is defined as the partitioning of an image, X, into R disjointed subsets X1, X2, X3, ..., XR or regions for which the following four conditions are true:

1. Every image pixel must be in a region.
2. Each region, Xi, must be connected.
3. Every pixel in each region must satisfy a mathematical criterion, P(Xi), called a Logical Predicate
4. In the final segmentation result, merging of any spatially adjacent regions would violate the third condition.

An example of a simple Logical Predicate for a single band image is for the absolute difference between a pixel value and a particular constant value be less than a certain constant threshold value.

This definition of Logical Predicate Image Segmentation does not uniquely specify an algorithm for producing the segmentation. Approaches based on region growing are usually employed. In a simple such region growing approach, the image is repeatedly scanned (e.g. left to right, top to bottom) until no further region merges can occur. In the first scan, each pixel is placed in a nearby region from the previous scan line or column if condition #3 is satisfied. If no such region exists, it forms a new one-pixel region. In subsequent scans, spatially adjacent regions are merged if they violate condtion #4. The process terminates when no merges occur in a complete scan. Utilizing this implementation, if there are more than one neighboring region by which a pixel would satisfy condition #3, or if there are more than one neighboring region with which a region would violate condition #4, the best merge is chosen (if more than one region is a best merge, the region with the lowest region label is arbitrarily chonsen).

(a)

(b)

(c)

Fig. 1. (a) The "3D NASA Logo" image used an image segmentation test image. This image is 200 x 200 pixels with a 3-element vector at each pixel representing the red, green, and blue spectral values. (b) Region mean image for the 313 region segmentation result produced by using region growing with logical predicate segmentation with threshold, T, equal to 42.0. The global dissimilarity value from the logical predicate segmentation is 10.0878. (c) Boundary map for (b).

There are two significant problems with Logical Predicate image segmentation: (1) The segmentation results are often poor, with region boundaries inappropriately following along to image scan lines, and (2) the computational efficiency is very poor, since each region pixel needs to be considered in each region merge decision.