Thresholding technique for graphics images using histogram analysis

• US 4,656,665 A
• Filed: 01/15/1985
• Issued: 04/07/1987
• Est. Priority Date: 01/15/1985
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Pennebaker, William B.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Couso, Jose L.
• Application Number:
  US06/692,008
• Time in Patent Office: 812 Days
• Field of Search: 382/18, 382/51, 358/282, 358/280, 358/80, 358/163
• 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: G06V 10/28 Quantising the image, e.g. histogram thresholding for discrimination between background and foreground patterns
• CPC Class Codes: H04N 1/4074 using histograms

Abstract

A system is described for thresholding graphics images to reduce the information content for transmission and reproduction and which uses a particular image data thresholding technique that may be used to obtain display images with a number of intensity levels. Firstly, an histogram of the image to be encoded is generated and analyzed to determine essential parameters. In particular, the background color of the image is determined by summing the histogram elements to find the median of the distribution, that is, the point at which the half sum of total pixels is reached. The extrema of the histogram are calculated and the skew is determined from the position of the median with respect thereto. If the difference between the median and the black extreme is less than half the difference between the median and the white extreme then the background of the image is deemed to be black, otherwise, the image will be defined as having a white background. After the background color is determined, the width of the background region, that is, the difference between the median and the foreground color extreme, is used to define the edge between the background and foreground regions, which edge occurs at one-half the background width from the median in the direction of the background color extreme. A sequence of threshold levels may then be determined using this edge as a base, by setting them at points disposed at fractionally different distances between the edge and the background color extreme.

Claims

1. A method for thresholding image data comprising the steps of:

generating a histogram of an image said histogram including histogram elements representative of a count of pixel elements of said image at predetermined intensities;

computing a median of distribution of the image by summing the histogram elements until a half sum of a total of all pixels is reached;

computing extremes of said distribution;

determining the skew of said distribution from the relative position of said median with respect to said extremes to determine the color of the image background;

determining a width of distribution of image background and defining an edge between background and foreground regions of the image by determining a point located between the median and the background extreme to be at a distance equal to half the distance between the median and the foreground color extreme, the edge point being used as a base for calculating a sequence of threshold levels; and

determining said sequence of threshold levels in a foreground region of said histogram by establishing a plurality of points differentially spaced along the distance between said edge point and said foreground color extreme.

2. Method as in claim 1 wherein the step of computing the extremes of said distribution is carried out by summing the histogram elements from each end of said distribution until a small but significant number is found and then scanning back toward the respective end until respective zero elements are found in the histogram.

3. Method as in claim 1 wherein said plurality of points are spaced 1/8, 1/4, and 1/2 of said distance.

4. Method as in claim 1 wherein said plurality of points are spaced 3/16, 3/8, and 3/4 of said distance.

5. Method as in claim 1 wherein the step of determining the skew of said distribution comprises measuring the lengths of the respective distances between said median and said extremes and then determining whether the length of one distance is less than one half the length of the other distance.

6. Apparatus for thresholding image data comprising:

means for generating a histogram of an image said histogram including histogram elements representative of a count of pixel elements of said image having predetermined intensities;

means for computing a median of distribution of the image by summing the histogram elements until the half sum of a total of all pixels is reached;

means for computing extremes of said distribution;

means for determining the skew of said distribution from the relative position of said median with respect to said extremes to determine an color of the image background;

means for defining the edge between background and foreground regions of the image by determining a point located between the median and the background color extreme a distance equal to half the distance between the median and the foreground color extreme, the edge point being used as a base for calculating a sequence of threshold levels; and

means for determining said sequence of threshold levels in a foreground region of said histogram by establishing a plurality of points differentially spaced along the distance between said edge point and said background color extreme.

7. Apparatus as in claim 6 wherein said means for computing the extremes of said distribution comprises means for summing the histogram elements from each end of said distribution until a small but significant number is found and then scanning back toward the respective end until respective zero elements are found in the histogram.

8. Apparatus as in claim 6 wherein said plurality of points are spaced 1/8, 1/4, and 1/2 of said distance.

9. Apparatus as in claim 6 wherein said plurality of points are spaced 3/16, 3/8, and 3/4 of said distance.

10. Apparatus as in claim 6 wherein said means for determining the skew of said distribution comprises means for measuring the lengths of the respective distances between said median and said extremes and means for determining whether the length of one distance is less than one half the length of the other distance.