Method and apparatus for separating foreground from background in images containing text

US 5,889,885 A
Filed: 04/24/1997
Issued: 03/30/1999
Est. Priority Date: 01/31/1995
Status: Expired due to Term

First Claim

Patent Images

1. A method of comparing two binary images corresponding to different thresholdings of a gray-scale image, each of said binary images having a first one of two values for portions of said binary image and a second one of two values for the remainder of said binary image, comprising, prior to applying a character recognition process to said images, the steps of:

locating connected components in each of said binary images;

determining a piece size of each of said connected components, said piece size having a value corresponding to the number of pixels in each of said connected components;

determining piece size distributions for said binary images, each piece size distribution having the number of connected components by size for connected components of each said binary image having said first one of two values; and

comparing said piece size distributions by;

constructing a multi-bin histogram of each of said piece size distributions with a first bin corresponding to small piece sizes in said binary images and with a second bin corresponding to big piece sizes in said binary images;

computing a first quotient by dividing the value of said first bin of said histogram for a first of said two binary images by the value of said first bin of said histogram for a second of said two binary images; and

computing a second quotient by dividing the value of said second bin of said histogram for a first of said two binary images by the value of said second bin of said histogram for a second of said two binary images; and

selecting said first binary image if said first quotient is less than said second quotient multiplied by a quality value.

View all claims

0 Assignments

Timeline View

Assignment View

0 Petitions

Accused Products

Abstract

A method and apparatus for thresholding gray-scale images containing text as foreground and dirt, colors, noise and the like as background. The method is adaptive in nature and can successfully separate a wide variety of text fonts and sizes, whether printed, typewritten, or handwritten, from the image background. The method uses multiple sets of thresholding process parameters in a contrast-based histogram evaluation to produce multiple candidate thresholded binary images. The method automatically selects the highest quality binary image, that is, the binary image that best represents text in the foreground, from among the multiple candidate binary images. The apparatus for implementing the method is a pipeline processor for highest speed.

92 Citations

View as Search Results

19 Claims

1. A method of comparing two binary images corresponding to different thresholdings of a gray-scale image, each of said binary images having a first one of two values for portions of said binary image and a second one of two values for the remainder of said binary image, comprising, prior to applying a character recognition process to said images, the steps of:
- locating connected components in each of said binary images;
  
  determining a piece size of each of said connected components, said piece size having a value corresponding to the number of pixels in each of said connected components;
  
  determining piece size distributions for said binary images, each piece size distribution having the number of connected components by size for connected components of each said binary image having said first one of two values; and
  
  comparing said piece size distributions by;
  
  constructing a multi-bin histogram of each of said piece size distributions with a first bin corresponding to small piece sizes in said binary images and with a second bin corresponding to big piece sizes in said binary images;
  
  computing a first quotient by dividing the value of said first bin of said histogram for a first of said two binary images by the value of said first bin of said histogram for a second of said two binary images; and
  
  computing a second quotient by dividing the value of said second bin of said histogram for a first of said two binary images by the value of said second bin of said histogram for a second of said two binary images; and
  
  selecting said first binary image if said first quotient is less than said second quotient multiplied by a quality value.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
- - 2. The method of claim 1, wherein the step of determining piece size distributions for said binary images comprises the steps of:
    - converting the portions of each of said binary images having said first one of two values into a run-length-encoded (RLE) image; and
      
      determining the piece size distribution of connected components of each of said RLE images using piece extraction.
  - 3. The method of claim 1, wherein the step of comparing said piece size distributions comprises the steps of:
    - constructing a multi-bin histogram of each of said piece size distributions; and
      
      comparing the values in selected bins of said multi-bin histograms.
  - 4. The method of claim 3, wherein the step of comparing the values in selected bins of said multi-bin histograms comprises the step of:
    - comparing the ratio of values in a first bin of each of said multi-bin histograms with the ratio of values in a second bin of each of said multi-bin histograms; and
      
      further comprising the step of;
      
      selecting one of said two binary images based on the comparison in the previous step.
  - 5. The method of claim 1, wherein the step of comparing said piece size distributions comprises the steps ofconstructing a multi-bin histogram of each of said piece size distributions;
    - andproviding the values from selected bins of each of said multi-bin histograms as inputs to a previously-trained neural network; and
      
      further comprising the step of;
      
      selecting one of said two binary images based upon the value of the output of said previously-trained neural network.
  - 6. The method of claim 3, wherein said histograms are multi-bin histograms with a first bin corresponding to small connected components in said binary images and with a second bin corresponding to big connected components in said binary images and said step of comparing the values in selected bins of said multi-bin histograms comprises the steps of:
    - computing a first quotient by dividing the value of said first bin of said histogram for a first of said two binary images by the value of said first bin of said histogram for a second of said two binary images;
      
      computing a second quotient by dividing the value of said second bin of said histogram for a first of said two binary images by the value of said second bin of said histogram for a second of said two binary images; and
      
      further comprising the step of;
      
      selecting said first binary image if said first quotient is less than said second quotient multiplied by a quality value.
  - 7. The method of claim 6, wherein said quality value is a preselected constant.
  - 8. The method of claim 6, wherein said quality value is computed from a predetermined formula employing preselected constants and said value of said second bin of said histogram for said first of two binary images.
  - 9. The method of claim 6, wherein said quality value is computed from a predetermined formula employing preselected constants and said value of said second bin of said histogram for said second of two binary images.
  - 10. The method of claim 6, wherein said first bin of said multi-bin histogram contains the count of connected components of said binary images having from 0 to approximately 10 pixels.
  - 11. The method of claim 6, wherein said second bin of said multi-bin histogram contains the count of connected components of said binary images having more than approximately 100 pixels.

12. A method of thresholding a gray-scale image, comprising the steps ofconstructing a contrast image corresponding to said gray-scale image, wherein each pixel of said contrast image has a value LC_ij given by the formula

space="preserve" listing-type="equation">LC.sub.ij =C (1-(MIN.sub.ij +p)/(MAX.sub.ij +p)),
where (i,j) is the position of said pixel in said contrast image, C is a preselected maximum contrast value, p is a preselected positive value small in comparison to C, MIN_ij is the minimum gray-scale value of all pixels in a rectangular window centered on the corresponding position in said gray-scale image, and MAX_ij is the maximum gray-scale value of all pixels in said rectangular window;

selecting a predetermined number of sets of thresholding parameters, said thresholding parameters being a peak-floor-level value, a nominal-peak-width value, a minimum-contrast value, a nominal-text-peak-width value, a minimum-contrast-scale value, and a nominal-contrast-excess value;

for each set of thresholding parameters, obtaining a candidate binary image by constructing a contrast histogram of said contrast image over all possible contrast values in said contrast image;

finding all peaks in said contrast histogram greater than said preselected peak-floor-level value and separated from any higher peak by said preselected nominal-peak-width value;

selecting from among said found peaks a minimum-text peak by locating a peak occurring at the lowest contrast value which is greater than said preselected minimum-contrast value;

obtaining a minimum-allowable-contrast value by subtracting said preselected nominal-text-peak-width value from the contrast value of said minimum-text peak;

assigning the pixel at the (i,j) position of said gray scale image to a background class of said candidate binary image if LC_ij is less than said minimum-allowable-contrast value;

computing, if said pixel of said gray scale image is not already assigned to said background class, the difference between MAX_ij and MIN_ij and assigning said pixel to said background class if said max-to-min difference is less than said preselected minimum-contrast-scale value;

computing, if said pixel of said gray scale image is not already assigned to said background class, the difference between MAX_ij and the gray-scale value of said pixel and assigning said pixel to said background class if said max-to-pixel-value difference is less than said preselected nominal-contrast-excess value; and

assigning, if said pixel of said gray scale image is not already assigned to said background class, said pixel to a foreground class;

selecting a first one of said candidate binary images;

converting the portions of said first-selected candidate binary image having a first one of two values into a first run-length-encoded (RLE) image;

prior to applying a character recognition process to said first RLE image, locating connected components in said first RLE image and determining a piece size of each of said connected components, said piece size having a value corresponding to the number of pixels in each of said connected components;

determining a first piece size distribution of connected components of said first RLE image;

constructing a first multi-bin histogram of said first piece size distribution;

selecting a second one of said candidate binary images from among said candidate binary images not previously selected;

converting the portions of said second-selected candidate binary image having a first one of two values into a second RLE image;

prior to applying a character recognition process to said second RLE image, locating connected components in said second RLE image and determining a piece size of each of said connected components, said piece size having a value corresponding to the number of pixels in each of said connected components;

determining a second piece size distribution of connected components of said second RLE image;

constructing a second multi-bin histogram of said second piece size distribution;

picking one of said first-selected candidate binary image and second-selected candidate binary image based on an evaluation of said first and second multi-bin histograms; and

repeating the previous step, with said picked candidate binary image replacing said first-selected candidate binary image, until all said candidate binary images have been selected.
View Dependent Claims (13, 14)

13. The method of claim 12, wherein the step of picking one of said first-selected candidate binary image and second-selected candidate binary image based on an evaluation of said first and second multi-bin histograms comprises the steps ofcomparing the ratio of the value in a first bin of said first multi-bin histogram to the value in a first bin of said second multi-bin histogram with the ratio of the value in a second bin of said first multi-bin histogram to the value in a second bin of said second multi-bin histogram;
andpicking one of said first-selected candidate binary image and second-selected candidate binary image based on the comparison of said ratios.

14. The method of claim 13, wherein the step of picking one of said first-selected candidate binary image and second-selected candidate binary image based on an evaluation of said first and second multi-bin histograms comprises the steps ofproviding the values from selected bins of each of said multi-bin histograms as inputs to a previously-trained neural network;
andpicking one of said first-selected candidate binary image and second-selected candidate binary image based upon the value of the output of said previously-trained neural network.

15. An apparatus for thresholding a gray-scale image, comprisingmeans for constructing a contrast image corresponding to said gray-scale image, wherein each pixel of said contrast image has a value LC_ij given by the formula

space="preserve" listing-type="equation">LC.sub.ij =C (1-(MIN.sub.ij +p)/(MAX.sub.ij +p)),
where (i,j) is the position of said pixel in said contrast image, C is a preselected maximum contrast value, p is a preselected positive value small in comparison to C, MIN_ij is the minimum gray-scale value of all pixels in a rectangular window centered on the corresponding position in said gray-scale image, and MAX_ij is the maximum gray-scale value of all pixels in said rectangular window;

means for selecting a predetermined number of sets of thresholding parameters, said thresholding parameters being a peak-floor-level value, a nominal-peak-width value, a minimum-contrast value, a nominal-text-peak-width value, a minimum-contrast-scale value, and a nominal-contrast-excess value;

means for obtaining, for each set of thresholding parameters, a candidate binary image by constructing a contrast histogram of said contrast image over all possible contrast values in said contrast image;

finding all peaks in said contrast histogram greater than said preselected peak-floor-level value and separated from any higher peak by said preselected nominal-peak-width value;

selecting from among said found peaks a minimum-text peak by locating a peak occurring at the lowest contrast value which is greater than said preselected minimum-contrast value;

obtaining a minimum-allowable-contrast value by subtracting said preselected nominal-text-peak-width value from the contrast value of said minimum-text peak;

assigning the pixel at the (i,j) position of said gray scale image to a background class of said candidate binary image if LC_ij is less than said minimum-allowable-contrast value;

computing, if said pixel of said gray scale image is not already assigned to said background class, the difference between MAX_ij and MIN_ij and assigning said pixel to said background class if said max-to-min difference is less than said preselected minimum-contrast-scale value;

computing, if said pixel of said gray scale image is not already assigned to said background class, the difference between MAX_ij and the gray-scale value of said pixel and assigning said pixel to said background class if said max-to-pixel-value difference is less than said preselected nominal-contrast-excess value; and

assigning, if said pixel of said gray scale image is not already assigned to said background class, said pixel to a foreground class;

means for selecting a first one of said candidate binary images;

converting the portions of said first-selected candidate binary image having a first one of two values into a first run-length-encoded (RLE) image;

means operative prior to applying a character recognition process to said-first RLE image, for locating connected components in said first RLE image and determining a piece size of each of said connected components, said piece size having a value corresponding to the number of pixels in each of said connected components;

determining a first piece size distribution of components of said first RLE image; and

constructing a first multi-bin histogram of said first piece size distribution;

means for selecting a second one of said candidate binary images from among said candidate binary images not previously selected;

converting the portions of said second-selected candidate binary image having a first one of two values into a second RLE image;

means operative prior to applying a character recognition process to said second RLE image, for locating connected components in said second RLE image and determining a piece size of each of said connected components, said piece size having a value corresponding to the number of pixels in each of said connected components;

determining a second piece size distribution of connected components of said second RLE image; and

constructing a second multi-bin histogram of said second piece size distribution;

means for picking one of said first-selected candidate binary image and second-selected candidate binary image based on an evaluation of said first and second multi-bin histograms; and

means for repeating the previous function, with said picked candidate binary image replacing said first-selected candidate binary image, until all said candidate binary images have been selected.
View Dependent Claims (16, 17)

16. The apparatus of claim 15, wherein the means for picking one of said first-selected candidate binary image and second-selected candidate binary image based on an evaluation of said first and second multi-bin histograms comprises:
means for comparing the ratio of the value in a first bin of said first multi-bin histogram to the value in a first bin of said second multi-bin histogram with the ratio of the value in a second bin of said first multi-bin histogram to the value in a second bin of said second multi-bin histogram; and

means for picking one of said first-selected candidate binary image and second-selected candidate binary image based on the comparison of said ratios.

17. The apparatus of claim 15, wherein the means for picking one of said first-selected candidate binary image and second-selected candidate binary image based on an evaluation of said first and second multi-bin histograms comprises:
means for providing the values from selected bins of each of said multi-bin histograms as inputs to a previously-trained neural network; and

means for picking one of said first-selected candidate binary image and second-selected candidate binary image based upon the value of the output of said previously-trained neural network.

18. A method of comparing two binary images corresponding to different thresholdings of a gray-scale image, each of said binary images having a first one of two values for portions of said binary image and a second one of two values for the remainder of said binary image, comprising, prior to applying a character recognition process to said images, the steps of:
- locating connected components in each of said binary images;
  
  determining a piece size of each of said connected components, said piece size having a value corresponding to the number of pixels in each of said connected components;
  
  determining piece size distributions for said binary images, each piece size distribution having the number of connected components by size for connected components of each said binary image having said first one of two values; and
  
  comparing said piece size distributions by;
  
  constructing a multi-bin histogram of each of said piece size distributions, said histograms being multi-bin histograms with a first bin corresponding to small connected components in said binary images and with a second bin corresponding to big connected components in said binary images; and
  
  comparing the values in selected bins of said multi-bin histograms by;
  
  computing a first quotient by dividing the value of said first bin of said histogram for a first of said two binary images by the value of said first bin of said histogram for a second of said two binary images; and
  
  computing a second quotient by dividing the value of said second bin of said histogram for a first of said two binary images by the value of said second bin of said histogram for a second of said two binary images; and
  
  selecting said first binary image if said first quotient is less than said second quotient multiplied by a quality value.

19. A computing device having executable instructions for comparing two binary images corresponding to different thresholdings of a gray-scale image, each of said binary images having a first one of two values for portions of said binary image and a second one of two values for the remainder of said binary image, comprising, prior to applying a character recognition process to said images, according to the steps of:
- locating connected components in each of said binary images;
  
  determining a piece size of each of said connected components, said piece size having a value equal to the number of pixels in each of said connected components;
  
  determining piece size distributions for said binary images, each piece size distribution having the number of connected components by size for connected components of each said binary image having said first one of two values; and
  
  comparing said piece size distributions by;
  
  constructing a multi-bin histogram of each of said piece size distributions with a first bin corresponding to small piece sizes in said binary images and with a second bin corresponding to big piece sizes in said binary images;
  
  computing a first quotient by dividing the value of said first bin of said histogram for a first of said two binary images by the value of said first bin of said histogram for a second of said two binary images; and
  
  computing a second quotient by dividing the value of said second bin of said histogram for a first of said two binary images by the value of said second bin of said histogram for a second of said two binary images; and
  
  selecting said first binary image if said first quotient is less than said second quotient multiplied by a quality value.

Specification

Resources

Litigation Campaign Assessment

Current Assignee
United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
Original Assignee
United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
Inventors
Moed, Michael C., Gorian, Izrael S.
Primary Examiner(s)
COUSO, YON JUNG

Application Number

US08/847,303
Time in Patent Office

705 Days
Field of Search

382/171, 382/172, 382/205, 382/245, 382/270, 382/271, 382/176, 382/273, 358/466
US Class Current

382/172
CPC Class Codes

G06V 30/10 Character recognition

G06V 30/162 Quantising the image signal

Method and apparatus for separating foreground from background in images containing text

First Claim

0 Assignments

0 Petitions

Accused Products

Abstract

92 Citations

19 Claims

Specification

Solutions

Use Cases

Quick Links

Method and apparatus for separating foreground from background in images containing text

First Claim

0 Assignments

Subscription Required

Subscription Required

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

92 Citations

19 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links