Page background estimation using color, texture and edge features

• US 20060115153A1
• Filed: 11/30/2004
• Published: 06/01/2006
• Est. Priority Date: 11/30/2004
• Status: Active Grant

• Current Assignee: Seiko Epson Corporation (Seiko Group)
• Original Assignee: Seiko Epson Corporation (Seiko Group)
• Inventors: Bhattacharjya, Anoop K.
• Granted Patent: US 7,428,331 B2
• Time in Patent Office: Days
• US Class Current: 382/173
• CPC Class Codes: G06V 2201/01 Solutions for problems related to non-uniform document background
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/162 Quantising the image signal
• CPC Class Codes: G06V 30/413 Classification of content, e.g. text, photographs or tables

Abstract

An algorithm for estimating which pixels belong to the background of a scanned page. The algorithm is particularly designed to handle situations in which the page background varies in color/intensity, as is case when bleed-through artifacts from the reverse side of the page appear in the background. In determining background regions, including properly classifying bleed-through artifacts regions as such, the algorithm uses multiple local and global criteria for making the determination. In addition to being able to find large connected pieces of background, the algorithm is also able to find isolated islands of background by analyzing transition characteristics of neighboring regions. Regions are identified on the basis of similar local features and also by the nature of transitions between foreground regions that do not directly share a boundary. An adaptive white-point adjustment technique based on identified background regions improves the perceived quality of the printed output.

Claims

1. A method for estimating the background portion of a document, comprising the steps of:

obtaining a digital representation of the document, the digital representation comprising a two-dimensional array of elements, the color of each of which is specified by a combination of color component values;

delineating clusters of pixels in a multimodal space of selected image features;

assigning an initial label to each pixel to identify the closest feature mode in the multimodal feature space, the initial labels defining an initial label set;

grouping like-labeled pixels into respective regions based on adjacency and distance in feature space;

organizing the regions in a selected format representing region adjacency and spatial location; and

refining the organization of the regions in the selected format to obtain a reduced set of labels.

2. A method as recited in claim 1, wherein the delineating step is performed by applying a recursive mean-shift algorithm to the representation.

3. A method as recited in claim 1, wherein the selected format is a nodal graph in which each node represents a unique image label and an edge exists between two nodes if the corresponding labels are adjacent in the labeled representation.

4. A method as recited in claim 3, wherein the refining step comprises processing the nodal graph to merge adjacent nodes if the associated feature modes lie within corresponding thresholds.

5. A method as recited in claim 3, wherein the refining step comprises processing the nodal graph to determine transition regions in the representation.

6. A method as recited in claim 5, wherein the processing of the nodal graph to determine transition regions comprises examining paths of a specified length starting from nodes that connect to only one other node to construct a set of region-transition rules.

7. A method as recited in claim 1, further comprising the step of performing adaptive white-point adjustment.

8. A method as recited in claim 7, wherein the performing step comprises:

mapping each label in the initial label set to one of the labels in the reduced set of labels;

projecting the feature modes corresponding to each of the labels in the initial label set that map to a background label in a pixel location subspace to identify a set of pixel locations in the digital representation with associated colors corresponding to the feature modes;

using the associated colors as local estimates of white points for the document; and

propagating the local estimates to all locations in the document by interpolation.

9. An apparatus for estimating the background portion of a document, comprising one or more components or modules configured to:

obtain a digital representation of the document, the digital representation comprising a two-dimensional array of elements, the color of each of which is specified by a combination of color component values;

delineate clusters of pixels in a multimodal space of selected image features;

assign an initial label to each pixel to identify the closest feature mode in the multimodal feature space, the initial labels defining an initial label set;

group like-labeled pixels into respective regions based on adjacency and distance in feature space;

organize the regions in a selected format representing region adjacency and spatial location; and

refine the organization of the regions in the selected format to obtain a reduced set of labels.

10. An apparatus as recited in claim 9, wherein the one or more components or modules are configured to apply a recursive mean-shift algorithm to the representation in the delineate operation.

11. An apparatus as recited in claim 9, wherein the selected format is a nodal graph in which each node represents a unique image label and an edge exists between two nodes if the corresponding labels are adjacent in the labeled representation.

12. An apparatus as recited in claim 11, wherein the one or more components or modules are configured to process the nodal graph to merge adjacent nodes if the associated feature modes lie within corresponding thresholds in the refine operation.

13. An apparatus as recited in claim 11, wherein the one or more components or modules are configured to process the nodal graph to determine transition regions in the representation in the refine operation.

14. An apparatus as recited in claim 13, wherein the one or more components or modules are configured to examine paths of a specified length starting from nodes that connect to only one other node to construct a set of region-transition rules in the nodal graph process operation.

15. An apparatus as recited in claim 9, wherein the one or more components or modules are further configured to perform adaptive white-point adjustment.

16. A device-readable medium carrying a program of instructions for directing a machine to perform a method of estimating the background portion of a document, the program of instructions comprising:

instructions for obtaining a digital representation of the document, the digital representation comprising a two-dimensional array of elements, the color of each of which is specified by a combination of color component values;

instructions for delineating clusters of pixels in a multimodal space of selected image features;

instructions for assigning an initial label to each pixel to identify the closest feature mode in the multimodal feature space, the initial labels defining an initial label set;

instructions for grouping like-labeled pixels into respective regions based on adjacency and distance in feature space;

instructions for organizing the regions in a selected format representing region adjacency and spatial location; and

instructions for refining the organization of the regions in the selected format to obtain a reduced set of labels.

17. A device-readable medium as recited in claim 16, wherein the delineating instructions include instructions for applying a recursive mean-shift algorithm to the representation.

18. A device-readable medium as recited in claim 16, wherein the selected format is a nodal graph in which each node represents a unique image label and an edge exists between two nodes if the corresponding labels are adjacent in the labeled representation.

19. A device-readable medium as recited in claim 18, wherein the refining instructions includes instructions for processing the nodal graph to merge adjacent nodes if the associated feature modes lie within corresponding thresholds.

20. A device-readable medium as recited in claim 18, wherein the refining instructions include instructions for processing the nodal graph to determine transition regions in the representation.

21. A device-readable medium as recited in claim 20, wherein the instructions for processing of the nodal graph to determine transition regions includes instructions for examining paths of a specified length starting from nodes that connect to only one other node to construct a set of region-transition rules.

22. A device-readable medium as recited in claim 16, further comprising instructions for performing adaptive white-point adjustment.

23. A device-readable medium as recited in claim 22, wherein the performing instructions comprises:

instructions for mapping each label in the initial label set to one of the labels in the reduced set of labels;

instructions for projecting the feature modes corresponding to each of the labels in the initial label set that map to a background label in a pixel location subspace to identify a set of pixel locations in the digital representation with associated colors corresponding to the feature modes;

instructions for using the associated colors as local estimates of white points for the document; and

instructions for propagating the local estimates to all locations in the document by interpolation.