64-Bit Computing & DSPs

Autonomous Threshold Detection

Broadly speaking, image segmentation is the task of isolating those parts of images that constitute objects or areas of interest and separating these objects or areas from the image. Once this separation has been achieved, various characteristics (center-of-mass or area, for instance) can be computed and used toward a particular application. One such means of accomplishing image segmentation is to threshold the image, whereby all pixels less than some threshold T are set to zero while the remaining pixels are left alone. There are different twists on this idea—for example, setting all pixels greater than T to 0 and the remaining pixels set to some other value V—but the basic concept is the same. A central problem facing this scheme is how to choose a suitable value for T. If the input image is guaranteed to be of high contrast, then simply selecting a brightness threshold somewhere within the middle of the dynamic range may be sufficient (128 for 8-bit images). Obviously, this is not always going to be the case and there are a variety of algorithms that attempt to derive a "good" threshold from the histogram of the image—where the goodness criterion is one where the number of falsely classified pixels is kept to a minimum. One such means is to use known properties of the image to select the threshold value. For example, in the case of optical character recognition (OCR) applications, it may be known that text covers 1/p of the total canvas area. Thus, it follows that the optimal algorithm for OCR is to select a threshold value such that 1/p of the image area has pixel intensities less than some threshold T (assuming the text is dark and the sheet is white), which is easily determined through inspection of the histogram. This method is known as "p-tile-thresholding."

Alternative techniques relying on the morphology of the histogram are used where such knowledge is not available. One such method is the iterative isodata clustering algorithm of Ridler and Calvard (see "Picture thresholding using an iterative selection method," IEEE Transactions on Systems, Man and Cybernetics, SMC-8:630-632, 1978). The image histogram is initially segmented into two sections starting with an initial threshold value T⁰ such as 2bpp-1, or half the dynamic range. The algorithm then proceeds as follows:

1. 1. Compute sample mean of the pixel intensities of the foreground mf.
2. 2. Compute sample mean of the pixel intensities of the background mb.
3. 3. Set Tⁱ⁺¹ = (m_f + m_b) / 2.
4. 4. Terminate iteration if Tⁱ⁺¹ = Tⁱ, else go to 1.

This method has been shown to work well under a variety of image contrast conditions.

—S.Q.