Document segmentation system

• US 5,956,468 A
• Filed: 01/10/1997
• Issued: 09/21/1999
• Est. Priority Date: 07/12/1996
• Status: Expired due to Term

• Current Assignee: Seiko Epson Corporation (Seiko Group)
• Original Assignee: Seiko Epson Corporation (Seiko Group)
• Inventors: Ancin, Hakan
• Primary Examiner(s): ROGERS, SCOTT A
• Application Number:
  US08/782,144
• Time in Patent Office: 984 Days
• Field of Search: 382/176, 382/173, 382/180, 382/164, 382/165, 358/462, 358/467, 395/109
• US Class Current: 358/1.9
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/162 Quantising the image signal
• CPC Class Codes: H04N 1/40062 Discrimination between different image types, e.g. two-tone, continuous tone
• CPC Class Codes: H04N 1/52 Circuits or arrangements for halftone screening

Abstract

A method and apparatus for segmenting a document which has both text and image regions. The method and apparatus implement a technique in which large text pixels and image pixels are identified in a document having a relatively low resolution. The method and apparatus then detect dark text pixels on a light background region of a document and assign segmentation labels to each pixel. The pixel labels are post-processed using a plurality of syntactic rules to correct mislabeling of pixels. This process does not change the visual perception of the image regions in the document. Pixels identified as being in the background region of the document are assigned a white label and pixels identified as being in the text region are assigned a black label. The resulting processed document contains sharp black text and white background, resulting in improved perceptual quality and efficient ink utilization during a printing process.

Claims

1. A method of processing a mixed document defining a plurality of pixels, the method comprising the steps of:

(a) detecting a first set of the pixels corresponding to image pixels;

(b) detecting a second set of the pixels corresponding to large text pixels;

(c) computing, in a first color space, a first value corresponding to a white point of a media on which the document is printed;

(d) computing, in the first color space, a second value corresponding to a black point of the media;

(e) generating, via the first value, a table of values that are compensated for the white point of the media;

(f) labeling, via the table of values, each of the pixels in the document with one of;

(1) a color label;

(2) a black label; and

(3) a white label; and

(g) applying a plurality of syntactic rules to pixel sequences having predetermined labels and predetermined lengths.

2. The method of claim 1 wherein prior to step (a), the method further comprises the step of generating a low resolution mixed document.

3. The method of claim 2 wherein the step of generating a low resolution document further comprises the steps of:

scanning an original document a first time to provide a first document having a first resolution; and

scanning the original document a second time to provide a second document having a second different resolution wherein the first resolution is lower than the second resolution.

4. The method of claim 2 wherein the step of generating a low resolution document further comprises the steps of:

scanning the document with a scanner to provide a high resolution document having a first resolution; and

subsampling the first scanned document to provide a low resolution document having a second resolution wherein the second resolution is less than the first resolution.

5. The method of claim 2 further comprising the steps of:

labeling image pixels in the low resolution document; and

labeling large text pixels in the low resolution document.

6. The method of claim 5 further comprising the steps of:

partitioning, via the image pixel labels and the large text pixel labels, the image region of the mixed document into at least one foreground region and at least one background region; and

identifying first portions of at least one foreground region which corresponds to a text region and second portions of at least one foreground region which corresponds to an image region.

7. The method of claim 6 wherein the step of partitioning the document includes the steps of bi-level thresholding the pixels in the low resolution document.

8. The method of claim 7 wherein the step of identifying first portions of at least one foreground region which corresponds to a text region and second portions of at least one the foreground region which corresponds to an image region includes the steps of:

computing connected components in the foreground region; and

computing bounded boxes of the connected components in the foreground region.

9. The method of claim 8 further comprising the steps:

computing the size of at least one of the connected components in each of the at least one foreground regions;

computing bounding box dimensions of at least one of the connected components in each of the at least one foreground regions; and

labeling pixels within a connected component as large text pixels in response to the component size of the connected component having a value within a first predetermined range of values and the bounding box dimensions of the connected component having a value within a second predetermined range of values.

10. The method of claim 7 further comprising the steps of:

mapping a first pixel group having a first label in the mixed document to a first pixel having the first label in the low resolution document;

defining a pixel window in the low resolution document, wherein the pixel window surrounds the first pixel in the low resolution document;

in response to a pixel having a second different label existing in the pixel window surrounding the first pixel in the low resolution document, then performing the step of;

changing the label of the first pixel in the low resolution document from the first label to the second label.

11. The method of claim 10 wherein the first label corresponds to a black label and the second label corresponds to a color label.

12. The method of claim 2 wherein the pixel sequences correspond to a column of the mixed document and the low resolution document is centered within the pixel window.

13. The method of claim 1 wherein the pixel sequences correspond to rows of the mixed document.

14. The method of claim 1 wherein:

the first color space is an RGB color space;

the white point corresponds to an RGB triplet in the RGB color space;

the black point corresponds to an RGB triplet in the RGB color space; and

the media is a sheet of paper.

15. The method of claim 1 further comprising a method for post processing color run lengths in the mixed document, the mixed document being a mixed color document and having a plurality of pixel sequences, each of the pixel sequences having a plurality of pixels, the post processing method comprising the steps of:

(h) selecting a sequence of pixels;

(i) computing a run length value of the selected pixel sequence;

(j) comparing the run length value of the selected pixel sequence to a threshold run length value;

(k) in response to the run length value of the selected pixel sequence being less than the threshold run length value performing the steps of;

(1) applying a plurality of syntactic rules to the selected pixel sequence;

(2) changing a label of a pixel in the selected pixel sequence in response to at least one of the syntactic rules;

(l) repeating steps (i)-(k) in response to at least one pixel label changing.

16. The method of claim 15 wherein the post processing method further comprising the steps of:

in response to no pixel label changing, repeating steps (h)-(l) for a next one of the plurality of pixel sequences.

17. The method of claim 1 further comprising a method for processing a plurality of pixel sequences in the mixed document, each of the pixel sequences having a label, the pixel sequences processing method comprising the steps of:

(m) selecting a pixel sequence from the plurality of pixel sequences;

(n) computing a run length value of the selected pixel sequence;

(o) comparing the run length value of the selected pixel sequence to a threshold run length value;

(p) in response to the run length value of the selected pixel sequence being less than the threshold run length value, performing the steps of;

(1) applying a syntactic rule to the selected pixel sequence to eliminate a group of color pixels existing at a tip of a text character in the mixed document;

(q) repeating steps (m)-(p) for each of the plurality of pixel sequences in the mixed document;

(r) determining if a white run in one of the plurality of pixel sequences is in an image region of the mixed document;

(s) changing the white run to a color run in response to the white run being in an image region of the mixed document;

(t) determining if a black run in the one of the plurality of pixel sequences is in an image region of the mixed document; and

(u) changing the black run to a color run in response to the black run being in an image region of the mixed document.

18. The method of claim 17 wherein the step of determining if a white run is in an image region comprises the steps of:

determining the length of color runs neighboring the white run;

comparing the length of color runs neighboring the white run to a predetermined threshold value;

in response to the length of the color runs neighboring the white run being greater than the predetermined threshold value, changing the labels of each of the pixels in the white run from a white label to a color label; and

for each of the pixels in the selected white run, checking a value corresponding to a luminance pixel value.

19. The method of claim 17 wherein the one of the plurality of the pixel sequences corresponds to one of a vertical pixel sequence and a horizontal pixel sequence.

20. The method of claim 17 wherein steps (t) and (u) comprise the steps of:

determining the length of color runs neighboring the black run;

comparing the length of color runs neighboring the black run to a predetermined threshold value; and

in response to the length of the color runs neighboring the black run being greater than the predetermined threshold value, changing the labels of each of the pixels in the black run from a black label to a color label.

21. The method of claim 17 wherein steps (t) and (u) comprise the steps of:

determining if the any of the two immediate neighbors to the left and to the right of the black run are white; and

in response to none of the two immediate neighbors to the left and to the right of the black run being white, changing the labels of the pixels in the black run from black to color.

22. The method of claim 17 further comprising the steps of repeating steps (r)-(u) for each of the plurality of pixel sequences in the mixed document.

23. The method of claim 1 further comprising a method for processing mixed document, the mixed document being a mixed color document and having a plurality of pixels, the mixed color document processing method comprising the steps of:

identifying large text regions of the mixed color document;

identifying image regions of the mixed color document;

labeling pixels in the large text region of the mixed color document with a first one of the labels;

labeling pixels in the image region of the mixed color document with the first one of the labels;

labeling each of remaining plurality of pixels in the mixed color document with a second or third one of the labels;

selecting a sequence of pixels in the document; and

applying a first one of the plurality of syntactic rules to predetermined ones of pixels having a first predetermined label in the selected pixel sequence.

24. The method of claim 23 further comprising the step of applying a second one of the plurality of syntactic rules to predetermined ones of pixels having a second predetermined label in the selected pixel sequence.

25. The method of claim 24 further comprising the step of applying a third one of the plurality of syntactic rules to predetermined ones of pixels having a third predetermined label in the selected pixel sequence.

26. The method of claim 24 wherein:

the first label is the color label;

the second label is the white label; and

the third label is the black label.

27. The method of claim 26 wherein:

the first plurality of syntactic rules correspond to rules for validating pixels having the color label; and

the first predetermined label corresponds to the color label.

28. The method of claim 27 wherein:

the second plurality of syntactic rules correspond to rules for validating pixels having the white label; and

the second predetermined label corresponds to the white label.

29. The method of claim 28 wherein:

the third plurality of syntactic rules correspond to rules for validating pixels having the black label; and

the third predetermined label corresponds to the black label.

30. An apparatus for segmenting a document comprising:

a large text region identifier to identify large text regions of the document;

an image region identifier to identify image regions of the document;

a document segmentor to label pixels in the large text region and the image region of the document with a first label and to label each of remaining plurality of pixels in the document with a first one of a second label and a third label;

a pixel sequence selector to select a sequence of pixels in the document; and

a pixel label validator to apply predetermined ones of a first plurality of syntactic rules to predetermined ones of pixels having a first predetermined label in a pixel sequence selected by said pixel sequence selector, to validate pixel labels of pixels which satisfy the predetermined ones of the first plurality of syntactic rules and to change pixel labels of pixels which do not satisfy the predetermined ones of the first plurality of syntactic rules.

31. The apparatus of claim 30 further comprising a preview document generator having an input port and an output port, said preview document generator coupled to said large text region identifier and to said image region identifier, said preview document generator to receive at the input port thereof a document having a first resolution and to provide at the output port thereof a document having a second resolution wherein the second resolution is lower than the first resolution. coupled to said document segmentor wherein said document segmentor provides a segmented document to said halftone printing system.

32. The apparatus of claim 31 further comprising a halftone printing system coupled to said document segmentor wherein said document segmentor provides a segmented document to said halftone printing system.

33. A color printing system comprising:

a scanner having a scanner color space, said scanner having an input port to receive a mixed color document to be scanned and an output port to provide a stream of bits representing the mixed color document;

a document segmentation system having an input port and an output port, said document segmentor for receiving on the input port thereof the stream of digital bits from the output port of said scanner and to provide at the output port thereof a segmented document bit stream, said document segmentation comprising;

a large text region identifier to identify large text regions of the mixed color document;

an image region identifier to identify image regions of the mixed color document;

a document segmentor to label pixels in the large text region and the image region of the document with a first label and to label each of the remaining plurality of pixels in the document with a one of a second label and a third label;

a pixel sequence selector to select a sequence of pixels in the document; and

a pixel label validator to apply predetermined ones of a first plurality of syntactic rules to predetermined ones of pixels having a first predetermined label in a pixel sequence selected by said pixel sequence selector, to validate pixel labels of pixels which satisfy the predetermined ones of the first plurality of syntactic rules and to change pixel labels of pixels which do not satisfy the predetermined ones of the first plurality of syntactic rules; and

a printing system, having an input port coupled to the output port of said segmentation processor, said printing system to receive at the input port thereof a stream of bits which represent a segmented mixed color document and to print a mixed color document in response to a segmented document bit stream fed thereto from said segmentation system.

34. The color printing system of claim 33 wherein said document segmentation system further comprises:

a preview document generator having an input port coupled to the output port of said scanner and having an output port coupled to said large text region identifier and to said image region identifier, said preview document generator to receive at the input port thereof a document having a first resolution and to provide at the output port thereof a document having a second resolution wherein the second resolution is lower than the first resolution.

35. A computer program product for use with a color reproduction system including a scanner, a processor and a printer, the computer program product comprising:

a computer useable medium having computer readable program code to identify large text regions and image regions of a mixed color document;

a computer useable medium having computer readable program code to label pixels in the large text region and the image region of the mixed color document with a first label;

a computer useable medium having computer readable program code to label each of remaining plurality of pixels in the mixed color document with a first one of a second label and a third label;

a computer useable medium having computer readable program code to select a sequence of pixels in the mixed color document; and

a computer useable medium having computer readable program code to apply a first plurality of syntactic rules to predetermined ones of pixels having a first predetermined label in the selected pixel sequence.

36. The computer program product of claim 35 further comprising:

a computer useable medium having computer readable program code to apply a second plurality of syntactic rules to predetermined ones of pixels having a second predetermined label in the selected pixel row.

37. The computer program product of claim 35 further comprising:

a computer useable medium having computer readable program code to apply a third plurality of syntactic rules to predetermined ones of pixels having a third predetermined label in the selected pixel sequence.

38. The computer program product of claim 36 further comprising:

a computer useable medium having computer readable program code to receive a document having a first resolution and to generate a document having a second resolution wherein the second resolution is lower than the first resolution.