Segmented layered image system

• US 7,120,297 B2
• Filed: 06/26/2002
• Issued: 10/10/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: Malvar, Henrique S., Simard, Patrice Y., Renshaw, Erin L., Rinker, James Russell
• Primary Examiner(s): Wu, Jingge
• Assistant Examiner(s): CARTER, AARON W
• Application Number:
  US10/180,169
• Publication Number:
  US 20030202697A1
• Time in Patent Office: 1,567 Days
• Field of Search: 382/162, 382/166, 382/232, 382/243, 35842601-42616
• US Class Current: 382/166
• CPC Class Codes: G06V 30/413 Classification of content, e.g. text, photographs or tables
• CPC Class Codes: H04N 1/403 Discrimination between the two tones in the picture signal of a two-tone original

Abstract

Systems and methods for encoding and decoding document images are disclosed. Document images are segmented into multiple layers according to a mask. The multiple layers are non-binary. The respective layers can then be processed and compressed separately in order to achieve better compression of the document image overall. A mask is generated from a document image. The mask is generated so as to reduce an estimate of compression for the combined size of the mask and multiple layers of the document image. The mask is then employed to segment the document image into the multiple layers. The mask determines or allocates pixels of the document image into respective layers. The mask and the multiple layers are processed and encoded separately so as to improve compression of the document image overall and to improve the speed of so doing. The multiple layers are non-binary images and can, for example, comprise a foreground image and a background image.

Claims

1. A document encoding system comprising:

a mask separator that receives a document image and generates a mask from the document image, the mask being generated at least in part via merging regions by pairs of the document image based at least in pan upon minimization of pixel energy, the mask generated so as to reduce an estimated compression of a foreground image and a background image, the estimated compression comprising an energy variance computation; and

an image segmenter that segments the document image into a plurality of layers according to the mask, the plurality of layers represented in non-binary format.

2. The document encoding system of claim 1, the plurality of layers comprising a first image layer and a second image layer and the mask represented in binary format.

3. The document encoding system of claim 2, the first image layer being a foreground image and the second image layer being a background image.

4. The document encoding system of claim 3, ftrther comprising a mask encoder to encode the mask into a mask bitstream.

5. The document encoding system of claim 4, the mask encoder utilizing a fax based compression scheme.

6. The document encoding system of claim 4, the mask encoder utilizing a bi-level compression scheme.

7. The document encoding system of claim 4, further comprising:

a foreground encoder that encodes the foreground image from the image segmcnter into a foreground bitstream; and

a background encoder that encodes the background image from the image segmenter into a background bitstrearn.

8. The document encoding system of claim 7, the foreground encoder and the background encoder utilizing a progressive wavelet transform compression scheme.

9. The document encoding system of claim 7, the foreground encoder and the background encoder utilizing a progressive transform compression scheme.

10. The document encoding system of claim 7, the foreground encoder and the background encoder utilizing a masked wavelet compression scheme.

11. The document encoding system of claim 7, further comprising a combiner component to combine the mask bitstream, the foreground bitstream and the background bitstream into a combined bitstream.

12. A document encoding system comprising:

a mask separator that receives a document image and generates a mask from the document image, the mask generated so as to reduce an estimated compression of a foreground image and a background images, the estimated compression comprising an energy variance computation;

a retouch component that identifies spurious boundaries and/or extends the foreground and/or background image by way of the mask; and

an image segmenter that segments the document image into a plurality of layers according to the mask, the plurality of layers represented in non-binary format.

13. The document encoding system of claim 12, the retouch component being operative to generate a foreground mask and a background mask based on the identified spurious boundaries and the image segmenter utilizing the foreground mask to obtain a foreground image and the background mask to obtain a background image.

14. The document encoding system of claim 12, further comprising:

a mask encoder to encode the mask into a mask bitstream;

a foreground encoder that encodes the foreground image from the image segmenter into a foreground bitstream; and

a background encoder that encodes the background image from the image segmenter into a background bitstream.

15. A document encoding system comprising:

a mask separator that receives a document image and generates a mask from the document image, the mask represented in binary format and generated at least in part via merging regions by pairs of the document image based at least in part upon minimization of pixel energy; and

a foreground background segmenter that segments the document image into a foreground image and a background image according to the mask, the foreground image and the background image represented in a non-binary format, the mask generated so as to reduce an estimated compression of the foreground image and the background image, the estimated compression comprising an energy variance computation.

16. The system of claim 15, the mask generated to reduce a combined size of the mask, the foreground image and the background image.

17. The system of claim 15, the foreground image comprising a plurality of colors and the background image comprising a plurality of colors.

18. The system of claim 15, the document image comprising textual information.

19. The system of claim 15, the document image comprising a single page.

20. The system of claim 15, the document image comprising handwriting.

21. A photocopier employing the system of claim 15.

22. A document scanner employing the system of claim 15.

23. An optical character recognition system employing the system of claim 15.

24. A personal digital assistant employing the system of claim 15.

25. A fax machine employing the system of claim 15.

26. A digital camera employing the system of claim 15.

27. A digital video camera employing the system of claim 15.

28. A segmented layered image system employing the system of claim 15.

29. A video game employing the system of claim 15.

30. A document encoding system comprising:

a colorspace converter that converts a document image having a first colorspace to a converted document image having a second colorspace;

a mask separator that generate a mask from the converted document image, the mask represented in binary format and being generated at least in part via merging regions by pairs of the document image based at least in part upon minimization of pixel energy; and

a foreground background segnienter that segments the convened document image into a foreground image and a background image according to the mask, the foreground image and the background image represented in a non-binary format, the mask generated so as to reduce an estimated compression of the foreground image and the background image, the estimated compression comprising an energy variance computation.

31. The system of claim 30, the first colorspace being RGB and the second colorspace being YUV.

32. The system of claim 30, the first colorspace being RGB and the second colorspace being YCoCg.

33. A document decoding system comprising:

a separator component that separates a bitstream into a foreground bitstream, a background bitstream and a mask bitstream;

a foreground decoder that decodes the foreground bitstream into a foreground image;

a background decoder that decodes the background bitstream into a background image;

a mask decoder that decodes the mask bitstream into a mask, the mask generated so as to reduce an estimated compression of the foreground image and the background image, the estimated compression comprising an energy variance computation; and

a combiner component that generates a document image as a combination of the foreground image and the background image according to the mask.

34. The system of claim 33, the document image having a pluarlity of pixels, each of the plurality of pixels obtained from one of the group comprising the foreground image and the background image.

35. The system of claim 33, the document image being identical to an original document image.

36. The system of claim 33, the document image being substantially similar to an original document image.

37. The system of claim 36, further comprising a segmented layer document encoding system to generate the mask, the foreground image and the background image, to encode the mask into the mask bitstream, to encode the foreground image into the foreground bitstream, to encode the background image into the background image and to combine the mask bitstream, the foreground bitstream and the background bitstream into the bitstream.

38. A document system comprising:

a colorspace converter that converts a colorspace of a document image;

a mask separator that receives the document image from the colorspace converter and generates a mask for the document image at least in part via merging regions by pairs of the document image based at least in part upon minimization of pixel energy;

a mask processor component that receives the mask from the mask separator and to process the mask; and

a segmenter that segments the document image into a foreground image and a background image according to the mask, the mask generated so as to reduce an estimated compression of the foreground image and the background image, the estimated compression comprising an energy variance computation.

39. The system of claim 38, the mask processor component comprising a dither detection component to identify and remove dithering from the mask.

40. The system of claim 38, the mask processor component further comprising a noise removal component to identify and remove noise from the mask.

41. The system of claim 38, further comprising a clustering component that receives the mask from the mask processor component and determines connected components in the mask and groups similar connected components together as clusters utilizing at least one screening property.

42. The system of claim 41, further comprising a layout component that receives the mask from the clustering component and identifies layout information from the mask.

43. The system of claim 42, further comprising a mask encoder that receives the mask from the layout component and encodes the mask into a mask bitstream.

44. The system of daixn 43, the segmenter comprising a retouch component that analyzes the mask and the document image for spurious boundaries and extends a foreground mask and a background mask by a number of pixels across the spurious boundaries, the foreground mask and the background mask based on the mask, the foreground mask utilized by the segmenter to obtain the foreground image and the background mask utilized by the segmenter to obtain the background image.

45. The system of claim 44, further comprising a color connected component that identifies color connected components in the foreground image and the background image.

46. The system of claim 44, further comprising a foreground encoder that receives the foreground image and encodes the foreground image into a foreground bitstream;

a background encoder that receives the background image and encodes the background image into a background bitstream; and

a combiner component tat combines the mask bitstream, the foreground bitstream and the background bitstream into a combined bitstream.

47. The system of claim 46, further comprising an optical character recognition component that receives the mask from the clustering component and identifies characters in the mask.

48. The system of claim 47, further comprising a foreground pixel filler and a background pixel filler, the foreground pixel filler fills don'"'"'t care regions of the foreground image with don'"'"'t care pixels and the background pixel filler fills don'"'"'t care regions of the background image with don'"'"'t care pixels.

49. A method of encoding a document comprising:

generating a mask for a document image at least in part via merging regions by pairs of the document image based at least in part upon minimization of pixel energy, the mask generated such that an energy variance of a foreground image, a background image and the mask is reduced, the energy variance being an estimate of compression; and

segmenting the document image into the foreground image and the background image, the foreground image and the background image being a non-binary format.

50. The method of claim 49, further comprising:

encoding the mask to generate a mask bitstream;

encoding the foreground image to generate a foreground bitstream;

encoding the background image to generate a background bitstream; and

combining the mask bitstream, the foreground bitstream and the background bitstream into a combined bitstream.

51. The method of claim 49, fbrther comprising filling don'"'"'t care regions of the foreground image and the background image with don'"'"'t care pixels.

52. The method of claim 49, further comprising identifying layout information from the mask.

53. The method of claim 49, further comprising removing noise from the mask.

54. The method of claim 49, segmenting the document image further comprising extending the foreground image and the background image a number of pixels.

55. A method of decoding a document comprising:

receiving a bitstream;

separating the bitstream into a mask bitstream, a foreground bitstream and a background bitstream;

decoding the foreground bitstream into a foreground image;

decoding the background bitstream into a background image;

decoding the mask bitstream into a mask, the mask generated such that an energy variance of the foreground image, the background image and the mask is reduced, the energy variance being an estimate of compression; and

combining the foreground image and the background image according to the mask into a reconstructed document image.

56. The method of claim 55, further comprising providing display properties.

57. The method of claim 56, the display properties being provided by a user.

58. The method of claim 56, the display properties being dynamically determined.

59. The method of claim 56, the display properties being predetermined.

60. The method of claim 56, further comprising modifying the foreground image, the background image and the mask according to the display properties.

61. The method of claim 55, further comprising converting a colorspace of the reconstructed document image.

62. A computer readable medium having computer usable components for a document encoding system, comprising:

a colorspace converter component tat converts a colorspace of a document image;

a mask separator component that receives the document image from the colorspace converter component and generates a mask for the document image at least in part via merging regions by pairs of the document image based at least in part upon minimization of pixel energy; and

a segmenter component that receives the document image from the colorspace converter and segments the document image into a foreground image and a background image according to the mask, the mask generated such that an energy variance of the foreground image, the background image and the mask is reduced, the energy variance being an estimate of compression.

63. The computer readable medium of claim 62, further comprising:

a mask processor component that receives the mask from the mask separator component and processes the mask;

a clustering component that receives the mask from the mask processor component and identifies clusters in the mask; and

a layout component that receives the mask from the clustering component and identifies layout information from the mask.

64. The computer readable medium of claim 63, further comprising:

a mask encoder component that receives the mask from the layout component and encodes the mask into a mask bitstream;

a foreground encoder component that encodes the foreground image into a foreground bitstream;

a background encoder component that receives the background image and encodes the background image into a background bitstream; and

a combiner component that combines the mask bitstream, the foreground bitstream and the background bitstream into a combined bitstream.

65. An encoding system comprising:

means for generating a mask for a document image at least in part via merging regions by pairs of the document image based at least in part upon minimization of pixel energy;

means for segmenting the document image into a foreground image and a background image;

means for encoding the mask into a mask bitstream, the mask generated such that an energy variance of the foreground image, the background image and the mask is reduced, the energy variance being an estimate of compression;

means for encoding the foreground image into a foreground bitstream;

means for encoding the background image into a background bitstream; and

means for combining the mask bitstream, the foreground bitstream and the background bitstream into a combined bitstream.