Segmented layered image system Number:7,120,297 from the United States Patent and Trademark Office (PTO) owispatent 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.<H Segmented, layered, Segmented, layer, 7120297.html, Patent, pto, 7120297

Title: Segmented layered image system

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.

Patent Number: 7,120,297 Issued on 10/10/2006 to Simard, et al.

Inventors: Simard; Patrice Y. (Bellevue, WA), Renshaw; Erin L. (Kirkland, WA), Rinker; James Russell (Kirkland, WA), Malvar; Henrique S. (Sammamish, WA)
Assignee: Microsoft Corporation (Redmond, WA)

Appl. No.: 10/180,169

Filed: June 26, 2002

Current U.S. Class: 382/166 ; 358/426.01; 382/232; 382/243

Current International Class: G06K 9/00 (20060101); G06K 9/36 (20060101)

Field of Search: 382/162,166,232,243 358/426.01-426.16

References Cited [Referenced By]

U.S. Patent Documents


3606546	September 1971	Dudley et al.
3719922	March 1973	Lopes, Jr. et al.
3882454	May 1975	Marie et al.
4606069	August 1986	Johnson et al.
4747156	May 1988	Wahl
4754492	June 1988	Malvar
4922545	May 1990	Endoh et al.
4924494	May 1990	Shung
5077807	December 1991	Bokser
5129014	July 1992	Bloomberg
5304991	April 1994	Motegi
5402146	March 1995	Rodriguez et al.
5434953	July 1995	Bloomberg
5454047	September 1995	Chang et al.
5572565	November 1996	Abdel-Mottaleb
5572604	November 1996	Simard
5610996	March 1997	Eller
5737455	April 1998	Harrington et al.
5754183	May 1998	Berend et al.
5778092	July 1998	MacLeod et al.
5790696	August 1998	Takahashi
5805727	September 1998	Nakano
5805739	September 1998	Malvar et al.
5828771	October 1998	Bloomberg
5910805	June 1999	Hickey et al.
5914748	June 1999	Parulski et al.
5915044	June 1999	Gardos et al.
5917951	June 1999	Thompson et al.
5917964	June 1999	Normile
5923380	July 1999	Yang et al.
5930377	July 1999	Powell et al.
5960111	September 1999	Chen et al.
5960119	September 1999	Echigo et al.
5991515	November 1999	Fall et al.
6000124	December 1999	Saito et al.
6029126	February 2000	Malvar
6058362	May 2000	Malvar
6064762	May 2000	Haenel
6069636	May 2000	Sayuda et al.
6072496	June 2000	Guenter et al.
6073153	June 2000	Malvar
6094506	July 2000	Hullender
6100825	August 2000	Sedluk et al.
6108446	August 2000	Hoshen
6115689	September 2000	Malvar
6118890	September 2000	Senior
6137908	October 2000	Rhee
6144767	November 2000	Bottou et al.
6151424	November 2000	Hsu
6154762	November 2000	Malvar
6182034	January 2001	Malvar
6192360	February 2001	Dumais et al.
6233364	May 2001	Krainiouk et al.
6240380	May 2001	Malvar
6253165	June 2001	Malvar
6256608	July 2001	Malvar
6272253	August 2001	Bannon et al.
6285801	September 2001	Mancuso et al.
6309424	October 2001	Fallon
6310972	October 2001	Li et al.
6321243	November 2001	Ballard
6324560	November 2001	Malvar
6326977	December 2001	Westerman
6334001	December 2001	de Queiroz et al.
6345119	February 2002	Hotta et al.
6564263	May 2003	Bergman et al.
6633670	October 2003	Matthews
6731800	May 2004	Barthel et al.
6738079	May 2004	Kellerman et al.
6819796	November 2004	Hong et al.
6826727	November 2004	Mohr et al.
6901153	May 2005	Leone
6907141	June 2005	Okamoto
6977664	December 2005	Jinzenji et al.
2001/0004618	June 2001	Hur
2002/0064313	May 2002	Cheng
2003/0123729	July 2003	Mukherjee et al.
2003/0229856	December 2003	Lynn et al.

Foreign Patent Documents


0 567 344	Oct., 1993	EP
0 621 554	Oct., 1994	EP
0802680	Oct., 1997	EP
0853421	Jul., 1998	EP
1006714	Jun., 2000	EP
1104916	Jun., 2001	EP
1006714	Sep., 2001	EP
1146478	Oct., 2001	EP
2181875	Apr., 1987	GB
2 230 633	Oct., 1990	GB

Other References

Debargha Mukherjee, et al.; "JPEG2000-Matched MRC Compression of Compound Documents"; Jun. 6, 2002. cited by other .
Rangachar Kasturi, et al.; "Document Image Analysis: A Primer"; Sadhana vol. 27, Part 1, Feb. 2002, pp. 3-22. cited by other .
Qian Huang et al.; "Foreground/Background Segmentation of Color Images by Integration of Multiple Cues"; Proceedings of '95 Int'l. Conf. on Image Processing (ICIP. cited by other .
Guotong Feng, et al.; "High Quality MRC Document Coding"; School of Electrical and Computer Engineering; Purdue University; Sarnoff Corporation. cited by other .
Ping Wah Wong; Halftoning by Multiscale Dot Distribution; Proceedings of the '95 Int'l. Conf. on Image Processing (ICIP '95); pp. 117-120. cited by other .
Yann LeCun, et al.; "Learning Algorithms for Classification: A Comparison on Handwritten Digit Recognition"; AT&T Bell Laboratories. cited by other .
Patrice Y. Simard, et al.; "Boxlets: A Fast Convolution Algorithm for Signal Processing and Neural Networks"; AT&T Labs-Research. cited by othe- r .
Trevor Hastie, et al.; "Metrics and Models for Handwritten Character Recognition"; Dec. 8, 1997; pp. 1-18. cited by other .
Leon Bottou, et al.; "High Quality Document Image Compression with DjVu"; Jul. 13, 1998; AT&T Labs. cited by other .
Patrick Haffner, et al.; "Color Documents on the Web with DjVu"; AT&T Labs--Research. cited by other .
Yiu-fai Wong, et al.; Preprocessing of Video Signals for MPEG Coding by Clustering Filter; Proceedings of the '95 Int'l. Conf. on Image Processing (ICIP: '95); pp. 129-132. cited by other .
Patrick Haffner, et al.; "DjVu: Analyzing and Compressing Scanned Documents for Internet Distribution"; AT&T Labs-Research; pp. 1-4. cited by other .
Felix Balado Pumarino, et al.; "A Two-Stage Codebook Building Method Using Fast WAN"; University of Vigo, Communications Technology Department. cite- d by other .
Henrique S. Malvar; "Fast Progressive Wavelet coding"; Microsoft Research. cited by other .
Patrice Y. Simard, et al.; "A Wavelet Coder for Masked Images"; Proceedings of the Data Compression Conference (DCC'01); Microsoft Research. cited by other .
U.S. Appl. No. 10/180,800, filed Jun. 26, 2002, Malvar et al. cited by oth- er .
U.S. Appl. No. 10/180/649, filed Jun. 26, 2002, Simard et al. cited by oth- er .
U.S. Appl. No. 10/133,939, filed Apr. 25, 2002, Simard et al. cited by oth- er .
U.S. Appl. No. 10/133,558, filed Apr. 25, 2002, Simard et al. cited by oth- er .
U.S. Appl. No. 10/180,771, filed Jun. 26, 2992, Simard et al. cited by oth- er .
Queiroz, et al. "Optimizing Block-Threseholding Segmentation for Multilayer Compression of Compound Images" (Sep. 9, 2000) IEEE Transactions on Image Processing, IEEE Inc. New York, pp. 1461-1471. cite- d by other .
Salembier, et al. "Region-Based Representations of Image and Video: Segmentation Tools for Multimedia Services" (Dec. 8, 1999) IEEE Transactions on Circuits and Systems for Video Technology, IEEE Inc. New York, pp. 1147-1169. cited by other .
Haffner, et al. "Browsing through high quality document images with DjVu" Research and Technology Advances in Digital Libraries. ADL 1998 Proceedings (Apr. 22, 1998) IEEE International Forum in Santa Barabra, California, pp. 309-318. cited by other .
Simard, et al. "A Wavelet coder for Masked Images" Proceedings IEE Data Compression Conference (Mar. 27, 2001) Snowbird, Utah, pp. 93-102. cited by other .
Simard, et al. "A Forefround/Background Separation Algorith for Image Compression" (Mar. 23, 2004) Data Compression Conference, Snowbird, Utah, pp. 498-507. cited by other .
European Search Report dated Oct. 4, 2005 mailed Oct. 13, 2005 for EP Application Serial No. 03005430, 5 pages. cited by other .
Mukherjee, et al. "LPEG-Matched MRC Compression of Compound Documents" Proceedings 2001 International Conference of Image Processing (Oct. 7-10, 2001) Thessalonki, Greece, pp. 434-437. cited by other .
Cosman, et al. "Memory Efficient Quadtree Wavelet Coding for Compound Images" Conference Record of the Thirty-Third Asilomar Conference (Oct. 24-27, 1999) Piscataway, New Jersey, pp. 1173-1177. cited by other .
European Search Report dated Oct. 4, 2005 mailed Oct. 13, 2005 for EP Application Serial No. 03/005,431, 5 pages. cited by other .
European Search Report dated Oct. 4, 2005 mailed Oct. 13, 2005 for PCT Application Serial No. 10/180,169, 5 pages. cited by other .
U.S. Appl. No. 10/133,842, filed Apr. 25, 2002, Simard et al. cited by oth- er .
U.S. Appl. No. 11/198,562, filed Aug. 5, 2005, Simard et al. cited by othe- r .
U.s. Appl. No. 11/286,622, filed Nov. 23, 2005, Malvar et al. cited by oth- er .
European Search Report dated Sep. 15, 2005, mailed Sep. 30, 2005, for European Patent Application Serial No. EP 03 00 5429, 4 Pages. cited by other .
Witten, Ian H., et al; "Textual Image Compression", Data Compression Conference, IEEE, 10 pages, Mar. 24, 1992. cited by other .
European Search Report dated Nov. 21, 2005, mailed Nov. 30, 2005, for European Patent Application Serial No. EP 03 00 6769, 3 Pages. cited by other.

Primary Examiner: Wu; Jingge
Assistant Examiner: Carter; Aaron
Attorney, Agent or Firm: Amin & Turocy, LLP

Parent Case Text

This application is a continuation-in-part of U.S. Utility Application Ser. No. 10/133,842 which was filed Apr. 25, 2002, entitled ACTIVITY DETECTOR, U.S. Utility Application Ser. No. 10/133,558 which was filed Apr. 25, 2002, entitled CLUSTERING, and of U.S. Utility Application Ser. No. 10/133,939 which was filed Apr. 25, 2002, entitled LAYOUT ANALYSTS. This application is also related to co-pending U.S. application Ser. No. 10/180,771 entitled SYSTEM AND METHOD FACILITATING DOCUMENT IMAGE COMPRESSION UTILIZING A MASK, the entirety of which is incorporated herein by reference. This application is also related to co-pending U.S. application Ser. No. 10/180,649 entitled BLOCK RETOUCHING, the entirety of which is incorporated herein by reference.

Claims

What is claimed is:

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.

Description

TECHNICAL FIELD

The present invention relates generally to document image processing, and more particularly to systems and methods for identifying and compressing document images.

BACKGROUND OF THE INVENTION

The amount of information available via computers has dramatically increased with the wide spread proliferation of computer networks, the Internet and digital storage means. With such an increased amount of information has come the need to transmit information quickly and to store the information efficiently. Data compression is a technology that facilitates effectively transmitting and storing of information

Data compression reduces an amount of space necessary to represent information, and can be used for many information types. The demand for compression of digital information, including images, text, audio and video has been ever increasing. Typically, data compression is used with standard computer systems; however, other technologies make use of data compression, such as but not limited to digital and satellite television as well as cellular/digital phones.

As the demand for handling, transmitting and processing large amounts of information increases, the demand for compression of such data increases as well. Although storage device capacity has increased significantly, the demand for information has outpaced capacity advancements. For example, an uncompressed image can require 5 megabytes of space whereas the same image can be compressed and require, for example, only 2.5 megabytes of space for lossless compression or 500 kilobytes of space for lossy compression. Thus, data compression facilitates transferring larger amounts of information. Even with the increase of transmission rates, such as broadband, DSL, cable modem Internet and the like, transmission limits are easily reached with uncompressed information. For example, transmission of an uncompressed image over a DSL line can take ten minutes. However, the same image can be transmitted in about one minute when compressed thus providing a ten-fold gain in data throughput.

In general, there are two types of compression, lossless and lossy. Lossless compression allows exact original data to be recovered after compression, while lossy compression allows for data recovered after compression to differ from the original data. A tradeoff exists between the two compression modes in that lossy compression provides for a better compression ratio than lossless compression because some degree of data integrity compromise is tolerated. Lossless compression may be used, for example, when compressing critical text, because failure to reconstruct exactly the data can dramatically affect quality and readability of the text. Lossy compression can be used with images or non-critical text where a certain amount of distortion or noise is either acceptable or imperceptible to human senses. Data compression is especially applicable to digital representations of documents (digital documents). Typically, digital documents include text, images and/or text and images. In addition to using less storage space for current digital data, compact storage without significant degradation of quality would encourage digitization of current hardcopies of documents making paperless offices more feasible. Striving toward such paperless offices is a goal for many businesses because paperless offices provide benefits, such as allowing easy access to information, reducing environmental costs, reducing storage costs and the like. Furthermore, decreasing file sizes of digital documents through compression permits more efficient use of Internet bandwidth, thus allowing for faster transmission of more information and a reduction of network congestion. Reducing required storage for information, movement toward efficient paperless offices, and increasing Internet bandwidth efficiency are just some of many significant benefits associated with compression technology.

Compression of digital documents should satisfy certain goals in order to make use of digital documents more attractive. First, the compression should enable compressing and decompressing large amounts of information in a small amount of time. Secondly, the compression should provide for accurately reproducing the digital document. Additionally, data compression of digital documents should make use of an intended purpose or ultimate use of a document. Some digital documents are employed for filing or providing hard copies. Other documents may be revised and/or edited. Many conventional data compression methodologies fail to handle re-flowing of text and/or images when viewed, and fail to provide efficient and effective means to enable compression technology to recognized characters and re-flow them to word processors, personal digital assistants (PDAs), cellular phones, and the like. Therefore, if hard copy office documents are scanned into digital form, current compression technology can make it difficult if not impossible to update, amend, or in general change the digitized document.

Often, compression schemes are tailored to a particular type of document, such as binary, non-binary, textual or image, in order to increase compression. However, a compression scheme tailored for one type of document does not typically perform well for other types of documents. For example, a compression scheme tailored for textual based documents does not generally perform well with an image document. One solution to this problem is to select a compression scheme tailored to the type of document or image to be encoded. However, this solution can fail for digital documents which have more than one type of information in a single document. For example, a digital document can have a hi-color image along with textual information, such as is commonly seen in magazine articles. One approach to overcome this failing is to analyze a document and divide it into various regions. The various regions can be analyzed to determine the type of information contained within the reasons. A compression scheme can be selected for each region based on the type of information. However, this approach can be quite difficult to implement and requires regions of a variety of sizes and shapes which cause difficulties for compression. Another approach is to separate a document into a background and a constant color image. This can be helpful because a different compression scheme can be used for the background and the constant color image. However, the constant color image can cause information to be lost by forcing pixel values to be a constant color.

Additionally, data compression of digital documents should make use of the purpose of a document. Some digital documents are used for filing or providing hard copies. Other documents may be revised and/or edited. Current data compression fails to handle re-flowing of text and/or images when viewed, and fails to provide efficient and effective means to enable compression technology to recognized characters and re-flow them to word processors, personal digital assistants (PDAs), cellular phones, and the like. Therefore, if hard copy office documents are scanned into digital form, current compression technology can make it difficult if not impossible to update, amend, or in general change the digitized document.

SUMMARY OF THE INVENTION

The following is a summary of the invention in order to provide a basic understanding of some aspects of the invention. This summary is not intended to identify key/critical elements of the invention or to delineate the scope of the invention. Its sole purpose is to present some concepts of the invention in a simplified form as a prelude to the more detailed description that is presented later.

The present invention relates generally to systems and methods for encoding and decoding document images. Document images are segmented into multiple layers according to a mask, where the multiple layers are represented as non-binary. The respective layers can then be processed and compressed separately in order to facilitate better compression of the document image overall.

According to one aspect of the invention, 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.

According to another aspect of the invention, a document image is segmented into multiple layers, the multiple layers comprising a foreground image, a background image and a mask. The mask is a binary image and used to segment the document image into the foreground image and the background image. Generally, the mask is generated so as to reduce an estimate of a combined size of the mask, the foreground image and the background image. Unlike some conventional systems that limit a layer to a single color, both the foreground image and the background image can use any suitable range of colors and are not limited to a single or constant color. Additional processing of the mask, the foreground image and the background image can be performed. The mask, the foreground image and the background image are encoded and combined into a single bitstream. Any number of suitable compression schemes can be used for encoding purposes. For decoding, a compressed bitstream is separated into a mask bitstream, a foreground bitstream and a background bitstream. The mask bitstream, the foreground bitstream and the background bitstream are decoded into a mask, a foreground image and a background image. Additional processing of the mask, the foreground image and the background image can be performed. The foreground image and the background image are combined into a recombined document image according to the mask.

According to yet another aspect of the invention, a mask separator receives a document image and generates a mask from the document image. The mask is represented in binary format. A foreground background segmenter receives the mask and the document image and segments the document image into a foreground image and a background image. A mask encoder encodes the mask into a mask bitstream. A foreground encoder encodes the foreground image into a foreground bitstream. A background encoder encodes the background into a background bitstream. A combiner component combines the mask bitstream, the foreground bitstream and the background bitstream into a combined bitstream.

To the accomplishment of the foregoing and related ends, certain illustrative aspects of the invention are described herein in connection with the following description and the annexed drawings. These aspects are indicative of various ways in which the invention may be practiced, all of which are intended to be covered by the present invention. Other advantages and novel features of the invention may become apparent from the following detailed description of the invention when considered in conjunction with the drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram of a segmented layered image encoding system according to one aspect of the invention.

FIG. 2 is a diagram of one exemplary step of a wavelet computation.

FIG. 3 is a diagram illustrating an exemplary step of a wavelet computation where some pixels are missing.

FIG. 4 is a diagram illustrating an exemplary step of a masked wavelet computation.

FIG. 5 is a block diagram of a segmented layered image decoding system according to one aspect of the invention.

FIG. 6 illustrates a sample document image according to one aspect of the present invention.

FIG. 7 is a block diagram of a segmented layered image encoding system according to one aspect of the invention.

FIG. 8 is a block diagram of a segmented layered image decoding system according to one aspect of the invention.

FIG. 9 is a flow diagram of a method of encoding a document according to one aspect of the invention.

FIG. 10 is a flow diagram of a method of encoding a document according to one aspect of the invention.

FIG. 11 is a schematic block diagram of an exemplary operating environment for a system configured in accordance with the present invention.

FIG. 12 is a schematic block diagram of an exemplary communication environment in accordance with the present invention.

DETAILED DESCRIPTION OF THE INVENTION

The present invention is now described with reference to the drawings, wherein like reference numerals are used to refer to like elements throughout. In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It may be evident, however, that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to facilitate describing the present invention.

As used in this application, the term "component" is intended to refer to a computer-related entity, either hardware, a combination of hardware and software, software, or software in execution. For example, a component can be, but is not limited to being, a process running on a processor, a processor, an object, an executable, a thread of execution, a program, and a computer. By way of illustration, both an application running on a server and the server can be a component. One or more components can reside within a process and/or thread of execution and a component may be localized on one computer and/or distributed between two or more computers.

Further, "document image" is intended to refer to a digital representation of document(s) comprising one or more color(s) (e.g., binary (black/white), gray-scale and/or color document(s)). Additionally, a document image can have image(s), text and/or text with images, with potential superimposition of text and images. A document image can comprise binary, RGB, YUV and/or other representations of document(s). An RGB document image is represented r