SYSTEM AND METHOD FACILITATING DOCUMENT IMAGE COMPRESSION UTILIZING A MASK

• US 20060274381A1
• Filed: 08/16/2006
• Published: 12/07/2006
• Est. Priority Date: 04/25/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Simard, Patrice Y., Renshaw, Erin L., Rinker, James Russell
• Granted Patent: US 7,764,834 B2
• Time in Patent Office: Days
• US Class Current: 358/426.60
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/162 Quantising the image signal

Abstract

A system and method facilitating document image compression utilizing a mask separating a foreground of a document image from a background is provided. The invention includes a pixel energy analyzer adapted to partition regions into a foreground and background. The invention further provides for a merge region component adapted to attempt to merge regions if the merged region would not exceed a threshold energy. Merged regions are partitioned into a new foreground and new background. Thereafter, a mask storage component stores the partitioning information in a binary mask.

Claims

1. A segmented layered image system, comprising:

a pixel energy component adapted to calculate pixel energy for a region of a document image, the pixel energy component further adapted to calculate a partition of the region based at least in part upon minimization of pixel energy of at least one of a foreground and a background;

a region merge component that merges pairs of regions of the document image based, at least in part, upon minimization of pixel energy; and

,

a mask storage component adapted to store information associated with the partition in a mask.

2. The segmented layered image system of claim 1, the pixel energy component calculating energy variances utilizing the equations:

$v_F=\underset{x\in <br><br>F}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\left(f<br><br>\left(x\right)-{\mathrm{\mu <br><br>}}_F\right)}^2$ $v_B=\underset{x\in <br><br>B}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\left(f<br><br>\left(x\right)-{\mathrm{\mu <br><br>}}_B\right)}^2$

where F is the foreground,

B is the background, f(x) is the value of the pixel,

${\mathrm{\mu <br><br>}}_F=\frac{1}{N_F}<br><br>\underset{x\in <br><br>F}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>f<br><br>\left(x\right)$

is the mean pixel value of the foreground,

${\mathrm{\mu <br><br>}}_B=\frac{1}{N_B}<br><br>\underset{x\in <br><br>B}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>f<br><br>\left(x\right)$

is the mean pixel value of the background,

N_F is the number of pixels in the foreground, and,

N_B is the number of pixels in the background

for calculation of pixel energy variances of the region.

3. The segmented layered image system of claim 1, the pixel energy component calculating energy utilizing the equations:

$v_F=\underset{x,y\in <br><br>F}{\sum <br><br>}<br><br>{\left(f<br><br>\left(x,y\right)+A_F<br><br>x+B_F<br><br>y+C_F\right)}^2$ $v_B=\underset{x,y\in <br><br>B}{\sum <br><br>}<br><br>{\left(f<br><br>\left(x,y\right)+A_B<br><br>x+B_B<br><br>y+C_B\right)}^2$

where F is the foreground,

B is the background, f(x, y) is the value of the pixel at location x, y,

A_F, B_F, C_F are chosen to minimize the energy of the foreground v_F,

A_B, B_B, C_B are chosen to minimize the energy of the background v_B,

for calculation of pixel energy of the region.

4. The segmented layered image system of claim 1, the region merge component attempting to merge regions until merge results in a threshold energy level being exceeded.

5. The segmented layered image system of claim 1, the region merge component evaluating a restricted subset of combinations of foregrounds and backgrounds of the two regions, based on an approximation f over the given regions, and selecting the combination with a least cumulative energy.

6. The segmented layered image system of claim 1, the document image comprising at least one of a YUV, RGB and binary representation of a document.

7. The segmented layered image system of claim 1, the mask being a binary representation of information associated with the partition of the foreground and the background.

8. The segmented layered image system of claim 1, the pixel energy component calculating pixel energy variances for a region utilizing at least in part a K-means clustering algorithm, where K=2.

9. The segmented layered image system of claim 1, the pixel energy component calculating energy variances utilizing the equations:

$v_F=\underset{x\in <br><br>F}{\sum <br><br>}<br><br>{\left(f<br><br>\left(x\right)-{\mathrm{\mu <br><br>}}_F\right)}^2$ $v_B=\underset{x\in <br><br>B}{\sum <br><br>}<br><br>{\left(f<br><br>\left(x\right)-{\mathrm{\mu <br><br>}}_B\right)}^2$

where F is the foreground,

B is the background, f(x) is the value of the pixel,

${\mathrm{\mu <br><br>}}_F=\frac{1}{N_F}<br><br>\underset{x\in <br><br>F}{\sum <br><br>}<br><br>f<br><br>\left(x\right)$

is the mean pixel value of the foreground,

${\mathrm{\mu <br><br>}}_B=\frac{1}{N_B}<br><br>\underset{x\in <br><br>B}{\sum <br><br>}<br><br>f<br><br>\left(x\right)$

is the mean pixel value of the background,

N_F is the number of pixels in the foreground, and,

N_B is the number of pixels in the background

for calculation of pixel energy variances of the region.

10. The segmented layered image system of claim 1, the pixel energy component at least temporarily storing at least some of the information associated with calculating pixel energy.

11. The segmented layered image system of claim 1, the pixel energy component calculating pixel energy for the region based at least in part upon a polynomial regression of the region.

12. The segmented layered image system of claim 1, partitioning of the region being based at least in part upon an average of pixel values of the merged region.

13. The mask separator component of claim 12, a pixel value greater than the average being assigned to the foreground.

14. The mask separator component of claim 12, a pixel value greater than the average being assigned to the background.

15. A method for generating a mask partitioning a document image into a background and a foreground, comprising:

calculating pixel energy for a region;

partitioning the region based at least in part upon the calculated pixel energy of at least one of a foreground and a background of the region;

merging adjacent pairs of regions if a threshold energy associated with a new foreground and background would not be exceeded in the merged region;

partitioning the merged region into the new foreground and the new background; and

,

storing the partitioning information in a mask.

16. The method of claim 15, calculating pixel energy for a region further comprising:

calculating a sum of pixel values for a foreground;

calculating a sum of pixel values for a background; and

,

calculating a sum of squares distances for substantially all of the pixels in the region.

17. The method of claim 15, partitioning the region further comprising minimizing pixel energy of at least one of a foreground and a background.

18. The method of claim 15, partitioning the merged region further comprising the following acts:

calculating an average pixel value of the foreground of the merged region;

calculating an average pixel value of the background of the merged region;

assigning pixels to one of the foreground and the background if the difference between the average pixel value of the foreground and the average pixel value of the background is greater than a third threshold.

19. The method of claim 15, partitioning the region further comprising the following acts:

calculating an energy for the region; and

,

assigning pixels of the region to one of the foreground and the background if the energy is less than a second threshold energy.

20. A mask separation component, comprising:

means for calculating pixel energy for a region of a representation of a document image;

means for calculating a partition of the region based at least in part upon minimization of energy of at least one of two planes;

means for merging pairs of regions of the representation of the document image based at least in part upon a determination of whether the regions to be merged would exceed a threshold energy;

means for partitioning pixels of regions into a foreground and a background based at least in part upon minimization of energy of pixels comprising at least one of the foreground and the background; and

,

means for storing information associated with the partition in a mask.