Digital image processing method employing histogram peak detection

• US 4,731,863 A
• Filed: 04/07/1986
• Issued: 03/15/1988
• Est. Priority Date: 04/07/1986
• Status: Expired due to Term

• Current Assignee: Eastman Kodak Company
• Original Assignee: Eastman Kodak Company
• Inventors: Sezan, Muhammed I., Schaetzing, Ralph
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): NOT, DEFINED
• Application Number:
  US06/848,509
• Time in Patent Office: 708 Days
• Field of Search: 382/51, 358/282, 358/284, 364/414, 307/351, 328/150, 328/115
• US Class Current: 382/172
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/136 involving thresholding
• CPC Class Codes: H04N 5/32 Transforming X-rays cameras or camera modules for generating image signals from X-rays H04N23/30; circuitry of SSIS for transforming X-rays into image signals H04N25/30

Abstract

In many digital image processing methods, it is desirable to selectively apply digital image processing to identifiable structures in the image. For this purpose it is known to select gray level thresholds between structures based upon the location of corresponding peaks in the gray level histogram of the digital image. However, it is a problem to automatically detect the locations of peaks in the histogram and to select the gray level thresholds. The present invention provides a method for automatically detecting the peaks and selecting gray level thresholds for segmenting a digital image into distinguishable structures including the steps of detecting peaks in a gray level histogram of the digital image by applying smoothing and differencing operators to the gray level histogram to generate a peak detection function wherein positive to negative zero crossings of the peak detection function represent the start of a peak, and maxima following such a zero crossing represents the end of a peak.

Claims

1. In a method of processing a digital image by computer, including the steps of forming a gray-level histogram of the digital image, forming a peak detection function from the gray-level histogram, employing the peak detection function to detect peaks in the histogram, and employing the location of detected peaks to process the image, the improvement wherein said step of forming a peak detection function comprises the steps of:

a. forming a cumulative distribution function from said gray-level histogram;

b. smoothing said cumulative distribution function with a sliding window average of size w to produce a smoothed cumulative distribution function; and

c. subtracting said smoothed cumulative distribution function from said cumulative distribution function to produce said peak detection function; and

wherein said step of employing the peak detection function to locate peaks in the histogram includes the steps of;

a. identifying positive to negative zero crossings of the peak detection function as the start of a detected histogram peak, and

b. identifying a maximum following such a positive to negative zero crossing as the end of a detected histogram peak.

3. The digital image processing method claimed in claims 1 or 2, further including the steps of:

a. employing a relatively wide window size w to form a first peak detection function;

b. employing a relatively narrow window size w to form a second peak detection function; and

c. forming a set of detected peaks located from said first and second peak detection functions based upon the percentage of overlap between the peaks located by said first and second peak detection functions.

4. The digital image processing method claimed in claim 3, wherein said step of forming a set of detected peaks further includes basing said selection on the number of peaks detected by said second peak detection function that overlap with peaks detected by said first peak detection function.

5. The digital image processing method claimed in claim 1 or 2, wherein said digital image processing is of the type including the step of determining gray-level thresholds for segmenting the digital image into distinguishable structures, the gray-level thresholds being located between detected peaks in the histogram, and wherein said step of employing the peak detection function to detect peaks further includes the step of:

classifying peaks into clusters of peaks based upon the gray-level separation between the end of a detected peak, and the start of the next detected peak.

6. The digital image processing method claimed in claim 5, wherein the step of determining the gray-level thresholds is employed to determine the gray-level threshold between lung and mediastinum in a digital chest radiograph, further comprising the steps of:

a. if the peaks are classified into two clusters, setting the gray-level threshold at a convex combination of the gray-level at which the first cluster ends and the gray-level at which the second cluster starts;

b. if the peaks are classified into more than 2 clusters, determine the two adjacent clusters having the largest gray-level separation and set the gray-level threshold at a convex combination of the gray-level at which the first cluster ends and the gray-level at which the second cluster starts;

c. if there is only one peak, and if at least P_t percent of the total number of gray-levels are confined between the largest gray-level (n_max) and the gray-level at which the peak ends, setting the threshold to the gray-level at which the peak ends;

if the P_T percent criterion does not hold, then repeat the peak detection and classification steps with a smaller averaging window size w and repeat step (a) et seq. if at the end of a given number of repetitions there is still one peak detected and the percent criterion does not hold, then the histogram is essentially unimodal and a threshold does not exist; and

d. if the peaks are classified into only one cluster, and if at least P_T percent of the total number of gray-levels are confined between the largest gray-level (n_max) and the gray-level at which the cluster ends, setting the threshold to the gray-level at which the cluster ends, if the P_T percent criterion does not hold, then repeat the peak detection and classification steps with a larger averaging window size w and repeat step (a) et seq. if at the end of a given number of repetitions the peaks are classified into only one cluster and the P_T percent criterion does not hold, then treat the peaks as clusters and use step (b) for decision.

2. In a method of processing a digital image by computer, including the steps of forming a gray-level histogram of the digital image, forming a peak detection function from the gray-level histogram, employing the peak detection function to detect peaks in the histogram, and employing the location of detected peaks to process the image, the improvement wherein said step of forming a peak detection function comprises the step of:

convolving the histogram with a function q_w (n) of the form;

space="preserve" listing-type="equation">q.sub.w (n)=d(n)*s.sub.w (n)

where ##EQU5## where w is an adjustable parameter representing the size of an averaging window, and wherein said step of employing the peak detection function to loacate peaks in the histogram includes the steps of;

a. identifying positive to negative zero crossings of the peak detection function is the start of a detected histogram peak, and

b. identifying a maximum following such a positive to negative zero crossing as the end of a detected histogram peak.