Intelligent doubling for low-cost image buffers

• US 5,583,953 A
• Filed: 06/30/1993
• Issued: 12/10/1996
• Est. Priority Date: 06/30/1993
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Harrington, Steven J.
• Primary Examiner(s): Mancuso, Joseph
• Assistant Examiner(s): Prikockis, Larry J.
• Application Number:
  US08/083,581
• Time in Patent Office: 1,259 Days
• Field of Search: 382/9, 382/56, 382/47, 382/21, 382/22, 382/176, 382/239, 382/299, 382/300, 382/203, 395/139, 395/102, 395/116, 358/467, 358/462, 358/451
• US Class Current: 382/239
• CPC Class Codes: G06T 3/403 Edge-driven scaling; Edge-based scaling
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding

Abstract

A method and apparatus for achieving an ultra-small or compressed image buffer images at half the resolution and then scales by two to achieve the device resolution. Acceptable quality can be maintained by identifying edge and interior portions of the page image and using this information to scale intelligently. A split-level frame buffer provides this identification of the image components. Further, an extension of block-truncation coding can be used with the split-level frame buffer to provide up to a 16 to 1 compression for an overall compression of up to 64 to 1. Actual techniques to scale these encodings are described along with new encodings for graphics and text designed this high compression of the image.

Claims

1. A method of encoding a graphic image at full resolution for storing in a reduced image buffer for subsequent decoding and printing by a marking device, the method comprising the steps of:

segmenting said graphic image into blocks;

distinguishing smooth areas of the image from edges of the image;

determining a construction of the edges in a block of the image blocks, said determining step comprising describing an edge for the block by storing positions at which the edge enters and exits the block;

assigning reference points around the entire perimeter of the block relative to a given point; and

storing the construction, encoded as the entry and exit points of the edge measured in terms of said reference points in the reduced image buffer.

2. A method according to claim 1, wherein said determining step further comprises the step of providing a tag and a color table index to a table of at least color pairs.

3. A method according to claim 1, wherein said determining step comprises the step of describing first and second edges for the block by storing positions at which the first edge enters and exits the block measured as a first distance in terms of said reference points and an offset amount from the entry position of the first edge to the entry position of the second edge measured as a second distance around the block perimeter.

4. A method according to claim 3, wherein said determining step further comprises the step of providing a tag and a color table index to a table of at least color pairs.

5. A method according to claim 1, wherein said determining step comprises the step of defining a right angle corner of the image by storing an entry position of the right angle corner measured as a first distance in terms of said reference points on one side of said block and storing an exit position measured as a second distance in terms of said reference points so that the exit position of the right angle corner is on the same side as the entry position.

6. A method according to claim 5, wherein said defining step further comprises the step of describing first and second edges for the corner by also storing a parallel edge offset value.

7. An apparatus for encoding a graphic image at full resolution for storing in a reduced image buffer for subsequent decoding and printing by a marking device, the apparatus comprising:

means for segmenting said graphic image into blocks;

means for distinguishing smooth areas of the image from edges of the image;

means for determining a construction of the edges in a block of the image blocks, said determining means comprising means for describing an edge for the block by storing positions at which the edge enters and exits the block;

means for assigning reference points around the entire perimeter of the block relative to a given point; and

means for storing the construction, encoded as the entry and exit points of the edge measured in terms of said reference points, in the reduced image buffer.

8. An apparatus according to claim 7, wherein said determining means further comprises means for providing a tag and a color table index to a table of at least color pairs.

9. An apparatus according to claim 7, wherein said determining means comprises means for describing first and second edges for the block by storing positions at which the first edge enters and exits the block measured as a first distance in terms of said reference points, and an offset amount from the entry position of the first edge to the entry position of the second edge measured as a second distance around the block perimeter.

10. An apparatus according to claim 9, wherein said determining means further comprises means for providing a tag and a color table index to a table of at least color pairs.

11. An apparatus according to claim 7, wherein said determining means comprises means for defining a right angle corner of the image by storing an entry position of the right angle corner measured as a first distance in terms of said reference points on one side of said block and storing an exit position measured as a second distance in terms of said reference points so that the exit position of the right angle corner is on the same side as the entry position.

12. An apparatus according to claim 11, wherein said defining means further comprises means for describing first and second edges for the corner by also storing a parallel edge offset values.

13. A method of encoding and decoding a continuous tone image having a plurality of image region types, in a reduced image buffer with a uniform a block structure for printing by a marking device, wherein the image region types comprise pictorial and nonpictorial image region types and the nonpictorial image region types comprise at least one of text region types and graphic and line region types, the method comprising the steps of:

identifying edge regions and non-edge regions of said continuous tone image;

distinguishing between pictorial region types and non-pictorial region types;

encoding said continuous tone image according to said identifying step, by using different encoding methods for said edge regions, and said non-edge regions;

encoding pictorial region types at half a required resolution for the marking device;

storing said encoded continuous tone image in said reduced image buffer;

decoding said stored encoded continuous tone image in accordance with said identifying step that identifies edge regions; and

doubling said pictorial region types, wherein said pictorial region types are decoded and doubled by the steps of,

distinguishing smooth areas of the pictorial region types from edges of the pictorial region types;

resolution doubling said smooth areas by a first resolution doubling technique; and

resolution doubling said edges by a second resolution doubling technique, said second resolution doubling technique being different from said first resolution doubling technique.

14. A method according to claim 13, wherein said text regions are further encoded by the steps of determining whether the characters or a background are colored, and providing color indices indicating the color of the characters or background in accordance with the determining step.

15. An apparatus for encoding and decoding a continuous tone image having a plurality of image region types, in a reduced image buffer with a uniform block structure for printing by marking a device, wherein the image region types comprise pictorial and nonpictorial image region types and the nonpictorial image region types comprise at least one of text region types and graphic and line region types, the apparatus comprising:

means for identifying edge regions and non-edge regions of said continuous tone image;

means for distinguishing between pictorial region types and non-pictorial region types;

means for encoding said continuous tone image according to identification of said edge regions and said non-edge regions;

means for encoding pictorial region types at half a required resolution for the marking device;

means for storing said encoded continuous tone image in said reduced image buffer;

means for decoding said stored encoded continuous tone image in accordance with said identifying means that identifies edge regions; and

means for doubling said pictorial region types, wherein said means for decoding and doubling pictorial region types comprises,

means for distinguishing smooth areas of the image from edges of the image;

means for resolution doubling said smooth areas by a first resolution doubling technique; and

means for resolution doubling said edges by a second resolution doubling technique, said second resolution doubling technique being different from said first resolution doubling technique.

16. An apparatus according to claim 15, wherein said means for encoding said text regions further comprises means for determining whether the characters or a background are colored, and means for providing color indices indicating the color of the characters or background in accordance with the determining means.

17. A method of encoding and decoding a continuous tone image, having a plurality of image region types, in a a reduced image buffer with a uniform a block structure for printing by a marking device, wherein the image region types comprise pictorial and nonpictorial image region types and the nonpictorial image region types comprise at least one of text region types and graphic and line region types, the method comprising the steps of:

identifying edge regions and non-edge regions of said continuous tone image;

distinguishing between pictorial region types and non-pictorial region types;

encoding said continuous tone image according to said identifying step, by using different encoding methods for said edge regions, and said non-edge regions;

encoding pictorial region types at half a required resolution for the marking device;

storing said encoded continuous tone image in said reduced image buffer;

decoding said stored encoded continuous tone image in accordance with said identifying step that identifies edge regions; and

doubling said pictorial region types, wherein said graphic and line region types are encoded by the steps of,

segmenting said image into blocks;

distinguishing edge regions and non-edge regions of said graphic and line region types;

determining a construction of the edges in a block of the image blocks; and

storing the construction in the reduced image buffer.

18. A method according to claim 17, wherein said determining step comprises the step of describing an edge for the block by storing positions at which the edge enters and exits the block.

19. A method according to claim 18, wherein said determining step further comprises the step of providing a tag and a color table index.

20. A method according to claim 17, wherein said determining step comprises the step of describing first and second edges for the block by storing positions at which the first edge enters and exits the block and an offset amount to the entry position of the second edge.

21. A method according to claim 20, wherein said determining step further comprises the step of providing a tag and a color table index.

22. A method according to claim 17, wherein said determining step comprises the step of defining a right angle corner of the image by storing an entry position of the right angle corner measured as a first distance around the block perimeter on one side of said block and storing an exit position measured as a second distance around the block perimeter so that the exit position lies on the same side as the entry position.

23. A method according to claim 22, wherein said defining step further comprises the step of describing first and second edges for the corner by also storing an offset amount of said entry position of said second edge from said entry position of said first edge measured as a distance around the block perimeter.

24. An apparatus for encoding and decoding a continuous tone image having a plurality of image region types, in a reduced image buffer with a uniform block structure for printing by marking a device, wherein the image region types comprise pictorial and nonpictorial image region types and the nonpictorial image region types comprise at least one of text region types and graphic and line region types, the apparatus comprising:

means for identifying edge regions and non-edge regions of said continuous tone image;

means for distinguishing between pictorial region types and non-pictorial region types;

means for encoding said continuous tone image according to identification of said edge regions and said non-edge regions;

means for encoding pictorial region types at half a required resolution for the marking device;

means for storing said encoded continuous tone image in said reduced image buffer;

means for decoding said stored encoded continuous tone image in accordance with said identifying means that identifies edge regions; and

means for doubling said pictorial region types, wherein said means for encoding said graphic and line region types comprises,

means for segmenting said image into blocks;

means for distinguishing edge regions and non-edge regions of said graphic and line region types;

means for determining a construction of the edges in a block of the image blocks; and

means for storing the construction in the reduced image buffer.

25. An apparatus according to claim 24, wherein said determining means comprises means for describing an edge for the block by storing positions at which the edge enters and exits the block.

26. An apparatus according to claim 25, wherein said determining means further comprises means for providing a tag and a color table index.

27. An apparatus according to claim 24, wherein said determining means comprises means for describing first and second edges for the block by storing positions at which the first edge enters and exits the block and an offset amount from the entry position of the first edge to the entry position of the second edge.

28. An apparatus according to claim 27, wherein said determining means further comprises means for providing a tag and a color table index.

29. An apparatus according to claim 24, wherein said determining means comprises means for defining a right angle corner of the image by storing an entry position of the right angle corner measured as a first distance around the block perimeter on one side of said block and storing an exit position of the corner measured as a second distance around the block perimeter so that the exit position lies on the same side as the entry position.

30. An apparatus according to claim 29, wherein said defining means further comprises means for describing first and second edges for the corner by also storing an offset amount from the entry position of the first edge to the entry position of the second edge measured as a distance around the block perimeter.