Thresholding of gray level images using fractal dimensions

• US 5,054,101 A
• Filed: 02/28/1989
• Issued: 10/01/1991
• Est. Priority Date: 02/28/1989
• Status: Expired due to Term

• Current Assignee: E. I. du Pont de Nemours and Company (Corteva, Inc.)
• Original Assignee: E. I. du Pont de Nemours and Company (Corteva, Inc.)
• Inventors: Prakash, Arun
• Primary Examiner(s): Moore, David K.
• Assistant Examiner(s): Couso, Jose L.
• Application Number:
  US07/316,716
• Time in Patent Office: 945 Days
• Field of Search: 382/41, 382/47, 382/49, 382/50, 382/56, 364/518, 364/521, 364/522, 340/729
• US Class Current: 382/270
• CPC Class Codes: G06V 10/28 Quantising the image, e.g. histogram thresholding for discrimination between background and foreground patterns

Abstract

The locality of a two dimensional gray level image from which is generated a reference threshold value for converting the image to its corresponding binary image is determined by finding the fractal dimension of a hypothetical three dimensional surface overlying the two dimensional image.

Claims

1. A method of converting a two dimensional gray level image to a corresponding binary image comprising the steps of:

subdividing the two dimensional image into a predetermined number of picture elements each of which has a gray level associated therewith;

computing, from the two dimensional image, the surface area A(r) of a corresponding hypothetical three dimensional surface overlying the plane of the two dimensional image, the height that a portion of the hypothetical surface lies above a given pixel in the two dimensional image being functionally related to the gray level of the pixel;

determining the fractal dimension of the hypothetical surface by computing the change in the logarithm of the area A(r) with respect to the change in the logarithm of the scale of resolution r in accordance with the relationship

space="preserve" listing-type="equation">D=2-d[log A(r)]/d[log (r)]

determining the scale of resolution r_max at which the fractal dimension is a maximum;

determining a reference threshold gray level for each pixel in the two dimensional image, each reference threshold gray level being functionally related to the gray levels of each pixel lying within a predetermined locality about a given pixel, the dimensions of the predetermined locality being functionally related to the value r_max ; and

converting the gray level of each pixel in the two dimensional image into a corresponding binary representation thereof by comparing the gray level of each pixel with the reference threshold gray level for the locality surrounding that pixel and assigning a binary value to the pixel in accordance with the results of the comparison.

2. The method of claim 1 wherein the predetermined locality has a square shape and wherein the dimension of the locality exceeds the value r_max by a predetermined amount.

3. The method of claim 2 wherein the predetermined distance dimension of the locality exceeds the value r_max by less than twenty percent (20%).

4. The method of claim 1 wherein the computation of the surface areas A(r) is performed in the Fourier domain.

5. The method of claim 2 wherein the computation of the surface areas A(r) is performed in the Fourier domain.

6. The method of claim 3 wherein the computation of the surface areas A(r) is performed in the Fourier domain.

7. Apparatus for converting a two dimensional gray level image to a corresponding binary image comprising:

means for subdividing the two dimensional image into a predetermined number of picture elements each of which has a gray level associated therewith;

means for computing, from the two dimensional image, the surface area A(r) of a corresponding hypothetical three dimensional surface overlying the plane of the two dimensional image, the height that a portion of the surface lies above a given pixel in the two dimensional image being functionally related to the gray level of the pixel;

means for determining the fractal dimension of the hypothetical surface by computing the change in the logarithm of the area A(r) with respect to the change in the logarithm of the scale of resolution r in accordance with the relationship

space="preserve" listing-type="equation">D=2-d[log A(r)]/d[log (r)],

means for determining the scale of resolution r_max at which the fractal dimension is a maximum;

means for generating a reference threshold gray level for each pixel in the two dimensional image, each reference threshold gray level being functionally related to the gray level in each pixel lying within a predetermined locality about a given pixel, the dimensions of the predetermined locality being functionally related to the value r_max ; and

means for converting the gray level of each pixel in the two dimensional image into a corresponding binary representation thereof by comparing the gray level of each pixel with the reference threshold gray level for the locality surrounding that pixel and assigning a binary value to the pixel in accordance with the results of the comparison.

8. The apparatus of claim 7 wherein the computation of the surface areas A(r) is performed in the Fourier domain.