System and method facilitating document image compression utilizing a mask

• US 7,110,596 B2
• Filed: 06/26/2002
• Issued: 09/19/2006
• Est. Priority Date: 04/25/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Simard, Patrice Y., Renshaw, Erin L., Rinker, James Russell
• Primary Examiner(s): Wu, Jingge
• Assistant Examiner(s): CARTER, AARON W
• Application Number:
  US10/180,771
• Publication Number:
  US 20030202699A1
• Time in Patent Office: 1,546 Days
• Field of Search: 382/162, 382/166, 382232-253, 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. 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, the region merge component evaluating combinations of foregrounds and backgrounds of the two regions, and selecting the combination with a least cumulative 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:

$\begin{array}{c}{v}_F=\underset{x<br><br><br><br>\mathrm{\epsilon <br><br>}<br><br><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<br><br><br><br>\mathrm{\epsilon <br><br>}<br><br><br><br>B}{\sum <br><br>}<br><br>{\left(f<br><br>\left(x\right)-{\mathrm{\mu <br><br>}}_B\right)}^2\end{array}$

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<br><br><br><br>\mathrm{\epsilon <br><br>}<br><br><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<br><br><br><br>\mathrm{\epsilon <br><br>}<br><br><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.

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

$\begin{array}{c}{v}_F=\underset{x,y<br><br><br><br>\mathrm{\epsilon <br><br>}<br><br><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<br><br><br><br>\mathrm{\epsilon <br><br>}<br><br><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\end{array}$

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 ν

_F,

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

_B, for calculation of pixel energy of the region.

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

5. A photocopier employing the segmented layered image system of claim 1.

6. A document scanner employing the segmented layered image system of claim 1.

7. An optical character recognition system employing the segmented layered image system of claim 1.

8. A personal digital assistant employing the segmented layered image system of claim 1.

9. A fax machine employing the segmented layered image system of claim 1.

10. A digital camera employing the segmented layered image system of claim 1.

11. A digital video camera employing the segmented layered image system of claim 1.

12. A video game system employing the segmented layered image system of claim 1.

13. A method for generating a mask employed in a segmented layered image system, comprising:

calculating pixel energy for a region based at least in part upon a polynomial regression of the 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 based upon minimization of energy of at least one of the foreground and the background; and

,

storing the partitioning information in a mask.

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

15. A mask separator component comprising:

a pixel energy component adapted to calculate pixel energy for a region of a document image, the pixel energy component calculating pixel energy variances for a region utilizing at least in part a K-means clustering algorithm, where K=2, 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 merge region component adapted to merge pairs of regions of the document image based at least in part upon a determination of whether the merged region would exceed a first threshold energy, the merge component further adapted to partition the merged region into a new foreground and a new background; and

,

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

16. The mask separator component of claim 15, the document image comprising at least one of a YUV, RGB and binary representation of a document.

17. The mask separator component of claim 15, the mask being a binary representation of information associated with the partition of the foreground and the background.

18. The mask separator component of claim 15, the pixel energy component calculating energy variances utilizing the equations:

$\begin{array}{c}{v}_F=\underset{x<br><br><br><br>\mathrm{\epsilon <br><br>}<br><br><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<br><br><br><br>\mathrm{\epsilon <br><br>}<br><br><br><br>B}{\sum <br><br>}<br><br>{\left(f<br><br>\left(x\right)-{\mathrm{\mu <br><br>}}_B\right)}^2\end{array}$

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<br><br><br><br>\mathrm{\epsilon <br><br>}<br><br><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<br><br><br><br>\mathrm{\epsilon <br><br>}<br><br><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.

19. The mask separator component of claim 15, the pixel energy component at least temporarily storing at least some of the information associated with calculating pixel energy.

20. The mask separator component of claim 15, the pixel energy component calculating pixel energy for the region based at least in part upon a polynomial regression of the region.

21. The mask separator component of claim 15, partitioning of the region merge component being based at least in part upon an average of pixel values of the merged region.

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

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

24. The mask separator component of claim 15, the document image being a YUV representation and the pixel energy component utilizing at least the Y component in calculating pixel energy.

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

calculating pixel energy for a region based at least in part upon a polynomial regression of the 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.

26. The method of claim 25, 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.

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

28. The method of claim 25, partitioning the merged region further comprising calculating an average of pixel values of the merged region.

29. The method of claim 25, 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.

30. The method of claim 25, 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.

31. A document image compression system, comprising:

a document transformation component adapted to receive a document image and output a transformed representation of the document image; and

,

a mask separator component comprising a pixel energy component adapted to determine pixel energy for a region of the transformed representation, the pixel energy component calculating pixel energy for the region based at least in part upon a polynomial regression of the region, the pixel energy component further adapted to determine a partition of the region based at least in part upon minimization of energy of at least one of a foreground and a background, the mask separator component further comprising a merge region component adapted to merge pairs of regions, if a first threshold energy has not been exceeded, the merge region component further adapted to partition pixels of merged regions into a new foreground and a new background based at least in part upon minimization of energy of pixels comprising the new foreground and the new background, the mask separator component further comprising a mask storage component adapted to store partition information in a mask.

32. The document image compression system of claim 31, further comprising a foreground/background segmenter component adapted to separate the transformed representation into a foreground image and a background image based at least in part upon information stored in the mask.

33. The document image compression system of claim 31 further comprising at least one of a foreground encoder, a background encoder and a mask encoder.

34. The document image compression system of claim 31, the document transformation component adapted to receive an RGB document image and output a YUV representation of the RGB document image.

35. A computer readable medium having computer usable components for a mask separation component, comprising:

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

a merge region component adapted to merge 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, the merge component further adapted to partition the merged region into a foreground and a background based at least in part upon minimization of energy of pixels of at least one of the foreground and the background; and

,

a mask storage component adapted to store information associated with partitioning of the foreground and the background in a mask.

36. A mask separation component, comprising:

means for calculating pixel energy for a region of a representation of a document image, the pixel energy for a region being based at least in pan upon a polynomial regression of the region;

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.