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

Claim 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.

Claim 2

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.

Claim 13

A method of thresholding a gray-scale image, comprising the steps of 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 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.

Claim 14

A method of thresholding a gray-scale image, comprising the steps of 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 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.

Claim 17

An apparatus for thresholding a gray-scale image, comprising means 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 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.

Claim 18

An apparatus for thresholding a gray-scale image, comprising means 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 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.

Claim 21

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.

Claim 22

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.