Ngưỡng và phân đoạn

Thresholding and Segmentation,By James Matthews

This article looks at segmentation, thresholding images and lastly how to automatically select a threshold value for a greyscale image. This article assumes you have read theIntroduction to Image Processing article and are acquainted with colour depth and histograms.

Thresholding essentially involves turning a colour or greyscale image into a 1-bit binary image. This is done by allocating every pixel in the image either black or white, depending on their value. The pivotal value that is used to decide whether any given pixel is to be black or white is the threshold.

Figure 1: An image of a £2 coin and the same image thresholded.

So, why do this? The principle reason is to segment the image. As the name implies, segmentation tries to split a given image up into segments. Thresholding is the simplest form of segmentation. Another picture probably demonstrates this idea the best.

Figure 2: Example segmentation.

The left image is an RGB image of a Shakespeare extract, each pixel containing 24-bits of colour information. The right image shows the same text after it has been thresholded. Each pixel now contains only 1-bit of information.

Often, we want to threshold images to gain a better understanding of the shape or objects within a scene. Many machine vision techniques require a binary image as input. For example, a Hough transform (a method of finding parametrically defined shapes) requires a binary image of the edges within an image. Below we have an input image, the result of a Sobel edge detector, which is then thresholded. This is fed into the Hough Transform which detects all the strong lines within the image:

Figure 3: Hough Transforms using segmented image.

Now we must look at how to ascertain a useful thresholding point.

Automatically Picking a Threshold

Obviously, one method of doing this is to always threshold the image at 128, the midpoint in the histogram. This is not an intelligent approach though, since it doesn't account for the frequencies within the image. Below is another picture of a B-2, this time demonstrating that despite there being a strong constrast between the foreground and background, picking 128 as the threshold point yields very poor results:

Figure 4: Threshold set at 128.

Instead, an iterative approach can be used. The algorithms is as follows:

1. Pick an initial threshold value, t (say 128).
2. Calculate the mean values in the histogram below (m₁) and above (m₂) the threshold t.
3. Calculate new threshold. t_new = (m₁ + m₂) / 2.
4. If the threshold has stabilized (t = t_new), this is your threshold level. Otherwise, t become t_new and reiterate from step 2.

This algorithm can be succinctly implemented using the Generation5 JDK with the following Java function:

protected int getThresholdPoint(Histogram histogram) {
    int threshold = 0;   // the current threshold
    int tnew = 128;      // the new threshold
    long cumtotal = 0;   // the current cumulative total
    double m1, m2;       // the two means
        
    do {
        threshold = tnew;
        m1 = m2 = 0.0;
        for (int i=0; i            m1 += (histogram.getFrequency(i) * i);
            
        m1 /= histogram.getCumulativeFrequency(threshold-1);
            
        for (int i=threshold; i<256 br="" i="" style="font-size: 1px; height: 1px;">            m2 += (histogram.getFrequency(i) * i);
          
        m2 /= histogram.getCumulativeFrequency(255);
            
        tnew = (int)((m1 + m2) / 2.0);
    } while (tnew != threshold);
        
    return tnew;
}

When run on our B-2 image, it settles at 74 as the optimum threshold. This produces the following image:

Figure 5: Properly thresholded at 74.

There is much more to segmentation and thresholding than the introductory material presented here. Firstly, thresholding is not limited to a singular point, two-point thresholding that specifies lower and upper boundaries is also commonly used. Another method commonly used isadaptive thresholding which uses more localized information for the thresholding criteria.

References

Efford, Nick. Digital Image Processing: A Practical Introduction Using Java. Addison-Wesley. Essex: 2000.