System and method facilitating document image compression utilizing a mask

• US 7,764,834 B2
• Filed: 08/16/2006
• Issued: 07/27/2010
• 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. III, Rinker, James Russell, Renshaw, Erin L.
• Primary Examiner(s): Carter; Aaron W
• Application Number:
  US11/465,083
• Publication Number:
  US 20060274381A1
• Time in Patent Office: 1,441 Days
• Field of Search: 382232-253, 382/162, 382/166, 35842601-42616
• US Class Current: 382/166
• 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. One or more computer storage media comprising computer executable instructions for 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. One or more computer storage media of claim 1, the pixel energy component calculating energy variances utilizing the equations:

$v_F=\underset{x\in <br><br>F}{\overset{}{\sum <br><br>}}<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><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{}{\sum <br><br>}}<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{}{\sum <br><br>}}<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. One or more computer storage media 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. One or more computer storage media of claim 1, the region merge component evaluating combinations of foregrounds and backgrounds of the two regions, and selecting the combination with a least cumulative energy.

5. One or more computer storage media of claim 1, the region merge component evaluating a 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. One or more computer storage media of claim 1, the document image comprising at least one of a YUV, RGB and binary representation of a document.

7. One or more computer storage media of claim 1, the mask being a binary representation of information associated with the partition of the foreground and the background.

8. One or more computer storage media 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. One or more computer storage media of claim 1, the pixel energy component at least temporarily storing at least some of the information associated with calculating pixel energy.

10. One or more computer storage media 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.

11. One or more computer storage media of claim 1, partitioning of the region being based at least in part upon an average of pixel values of the merged region.

12. One or more computer storage media of claim 11, a pixel value greater than the average being assigned to the foreground.

13. One or more computer storage media of claim 11, a pixel value greater than the average being assigned to the background.

14. 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 based; and

,

storing the partitioning information in a mask.

15. The method of claim 14, 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.

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

17. The method of claim 14, 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; and

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.

18. The method of claim 14, 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.

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