Segmented layered image system

• US 20030202697A1
• Filed: 06/26/2002
• Published: 10/30/2003
• Est. Priority Date: 04/25/2002
• Status: Active Grant

• 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
• Granted Patent: US 7,120,297 B2
• Time in Patent Office: Days
• US Class Current: 382/195
• 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 part upon minimization of pixel energy; 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, further 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 segmenter into a foreground bitstream; and

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

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;

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.

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

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

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

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

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

22. A photocopier employing the system of claim 15.

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

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

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

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

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

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

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

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

31. A document encoding system comprising:

a colorspace converter that converts a 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 segmenter that segments the converted 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.

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

33. The system of claim 31, the first colorspace being RGB and the second colorspace being YCoCg.

34. 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; and

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

35. The system of claim 34, 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.

36. The system of claim 34, the document image being identical to an original document image.

37. The system of claim 34, the document image being substantially similar to an original document image.

38. The system of claim 37, 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.

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

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

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

42. The system of claim 39, 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.

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

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

45. The system of claim 44, 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.

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

47. The system of claim 45, 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 that combines the mask bitstream, the foreground bitstream and the background bitstream into a combined bitstream.

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

49. The system of claim 48, 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.

50. 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; and

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

51. The method of claim 50, 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.

52. The method of claim 50, 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.

53. The method of claim 50, further comprising filling don'"'"'t care regions of the foreground image and the background image with don'"'"'t care pixels.

54. The method of claim 50, further comprising identifying layout information from the mask.

55. The method of claim 50, further comprising removing noise from the mask.

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

57. 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; and

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

58. The method of claim 57, further comprising providing display properties;

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

60. The method of claim 57, the display properties being dynamically determined.

61. The method of claim 57, the display properties being predetermined.

62. The method of claim 57, further comprising modifiying the foreground image, the background image and the mask according to the display properties.

63. The method of claim 57, further comprising converting a colorspace of the reconstructed document image.

64. A data packet adapted to be transmitted between two or more computer processes, the data packet comprising:

information associated with a mask, a background image and a foreground image, the background image and the foreground image forming a reconstructed document image according to the mask.

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

a colorspace converter component that 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.

66. The computer readable medium of claim 65, 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.

67. The computer readable medium of claim 66, 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.

68. 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;

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.