Intelligent scaling of images stored in low-cost image buffers

• US 5,953,464 A
• Filed: 09/23/1997
• Issued: 09/14/1999
• 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): Boudreau, Leo H
• Assistant Examiner(s): MEHTA, BHAVESH M
• Application Number:
  US08/935,727
• Time in Patent Office: 721 Days
• Field of Search: 382/166, 382/233, 382/243, 382/242, 382/262, 382/264, 382/299-301, 382/268, 382/266, 382/267, 382/239, 382/164, 382/305, 358/525, 358/528, 358/451, 358/428, 395/115-117
• US Class Current: 382/299
• 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 for decoding and scaling an image, the method comprising the steps of:

providing at least one first pixel block representation representing a first pixel area in the image that has been encoded by a first encoding method;

providing at least one second pixel block representation representing a second pixel area in the image that has been encoded by a second encoding method, the first pixel area being exclusive of the second pixel area, the first encoding method being different from the second encoding method, all of the at least one first and second pixel blocks being at a reduced resolution;

decoding the at least one first pixel block representation using a first decoding method corresponding to the first encoding method;

decoding the at least one second pixel block representation using a second decoding method corresponding to the second encoding method;

scaling the decoded at least one first pixel block to full resolution using a scaling method corresponding to the first encoding method; and

scaling the decoded at least one second pixel block to full resolution using a scaling method corresponding to the second encoding method.

2. A method according to claim 1, wherein the pixel block size is 8 by 8 pixels.

3. A method according to claim 1, further comprising the step of filtering said full resolution first pixel block values wherein the filtering method corresponds to the first encoding method.

4. A method according to claim 3, wherein said filtering step comprises the step of calculating the full resolution first pixel block values as a weighted sum of neighboring reduced-resolution pixel block values.

5. A method according to claim 1, wherein said first pixel block contains three independent colors that always occur in the same order in each row, wherein said scaling step comprises the steps of generating bitmaps for at least two of the three independent colors and scaling said bit maps.

6. A method according to claim 1, wherein said first pixel block contains three independent colors that always occur in the same order in each row, said at least one pixel block representation comprising an entry for each row describing an assignment of colors for that row, wherein said scaling step comprises the steps of generating bitmaps for at least two of the three independent colors and scaling said bitmaps.

7. A method according to claim 1, wherein said first pixel block contains three independent colors that always occur in the same order in each column, said at least one first pixel block representation comprising an entry for each column describing an assignment of colors for that column, wherein said scaling step comprises the steps of generating bitmaps for at least two of the three independent colors and scaling said bitmaps.

8. A method according to claim 1, wherein said first pixel block contains an edge between two independent colors, said at least one first pixel block representation comprising entries for each row describing subpixel placement of the edge for that row of the first pixel block, wherein said scaling step comprises the step of using edge placement values to determine which full resolution pixel contains the edge for each of the reduced resolution rows.

9. A method according to claim 1, wherein said first pixel block contains an edge between two independent colors, said scaling step comprising the step of using edge placement values to determine which full resolution pixel contains the edge for each reduced resolution rows.

10. A method according to claim 1, wherein said first pixel block contains an edge between two independent colors, said at least one of the first pixel block representation comprising entries for each reduced resolution row describing subpixel placement of the edge for that row of the first pixel block, wherein said scaling step comprises the step of interpolating edge positions to obtain edge positions for interleaved full-resolution rows.

11. A method according to claim 1, wherein said first pixel block contains an edge between two independent colors, said scaling step comprising the step of interpolating edge positions to obtain edge positions for interleaved full resolution rows.

12. A method according to claim 1, wherein said first pixel block contains an edge between two independent colors, said at least one of first pixel block representation comprising entries for each column describing subpixel placement of the edge for that column of the first pixel block, wherein said scaling step comprises the step of using edge placement values to determine which full resolution pixel contains the edge for each of the reduced resolution columns.

13. A method according to claim 1, wherein said first pixel block contains an edge between two independent colors, said scaling step comprising the step of using edge placement values to determine which full resolution pixel contains the edge for each reduced resolution column.

14. A method according to claim 1, wherein said first pixel block contains an edge between two independent colors, said at least one first pixel block representation comprising entries for each column describing subpixel placement of the edge for that column of the first pixel block, wherein said scaling step comprises the step of interpolating edge positions to obtain edge positions for interleaved full-resolution columns.

15. A method according to claim 1, wherein said first pixel block contains an edge between two independent colors, said scaling step comprising the step of interpolating edge positions to obtain edge positions for interleaved full resolution columns.

16. A method according to claim 1, wherein said first encoding method comprises the steps of storing at least one color value and further comprising the step of scaling the first pixel block representation wherein the scaling step includes linearly interpolating between said at least one color and other colors of neighboring blocks of pixels.

17. A method according to claim 16, wherein the pixel block size is 8 by 8 pixels.

18. A method according to claim 16, further comprising the step of generating a bitmap for each of said at least one color, wherein said bitmap is used in the selection of pixels in the linear interpolating step.

19. A method according to claim 18, further comprising the steps of determining a color value of said one color and said other colors, and placing said revised color at each location indicated by said bitmaps in accordance with said determining step.

20. The method of claim 1, wherein the first pixel block representation includes an identifier of the first encoding method and wherein the second pixel block representation includes an identifier of the second encoding method.

34. An apparatus according to claim 20, wherein said first pixel block contains an edge between two independent colors, said at least one first pixel block representation comprising entries for each column describing subpixel placement of the edge for that column of the first pixel block, wherein said scaler comprises a processor for using edge placement values to determine which full resolution pixel contains the edge for each reduced resolution column.

21. An apparatus for decoding and scaling an image, the apparatus comprising:

a decoder that decodes at least one first pixel block representation using a first decoding method and at least one second pixel block representation using a second decoding method, the at least one first pixel block representation representing a first pixel area in the image and being encoded by a first encoding method, the first decoding method corresponding to the first encoding method and the at least one second pixel block representation representing a second pixel area in the image and being encoded by a second encoding method, the second decoding method corresponding to the second encoding method, the first pixel area being exclusive of the second pixel area and the first encoding method being different from the second encoding method, all of the first and second pixel block representations being at a resolution reduced from the full resolution; and

a scaler that scales the decoded at least one first pixel block to full resolution using a scaling method corresponding to the first encoding method and the decoded at least one second pixel block to full resolution using a scaling method corresponding to the second encoding method.

22. An apparatus of claim 21, wherein the pixel block size is 8 by 8 pixels.

23. An apparatus according to claim 21, further comprising a filter for filtering said full-resolution first pixel block values in accordance with the first encoding method.

24. An apparatus according to claim 23, wherein said filter is a low-pass filter.

25. An apparatus according to claim 23, wherein said filter is an edge-preserving filter.

26. An apparatus according to claim 23, wherein said filter comprises a processor for calculating the full resolution first pixel block values as a weighted sum of neighboring reduced resolution pixel block values.

27. An apparatus according to claim 21, wherein said scaler comprises a processor for recognizing corner patterns and smoothing said corner patterns at full resolution.

28. An apparatus according to claim 21, wherein said first pixel block contains three independent colors that always occur in the same order in each row, said at least one first pixel representation comprising an entry for each row describing an assignment of colors for that row, wherein said scaler comprises a processor for generating bitmaps for at least two of the three independent colors and for scaling said bitmaps.

29. An apparatus according to claim 21, wherein said first pixel block contains three independent colors that always occur in the same order in each column, said at least one first pixel block representation comprising an entry for each column describing an assignment of colors for that column, wherein said scaler comprises a processor for generating bitmaps for at least two of the three independent colors and for scaling said bitmaps.

30. An apparatus according to claim 21, wherein said first pixel block contains an edge between two independent colors, said at least one first pixel block representation comprising entries for each row describing subpixel placement of the edge for that row of the first pixel block, wherein said scaler comprises a processor for using edge placement values to determine which full resolution pixel contains the edge for each of the reduced resolution rows.

31. An apparatus according to claim 21, wherein said first pixel block contains an edge between two independent colors, said scaler comprising a processor for using edge placement values to determine which full resolution pixel contains the edge for each reduced resolution row.

32. An apparatus according to claim 21, wherein said first pixel block contains an edge between two independent colors, said at least one first pixel block representation comprising entries for each row describing subpixel placement of the edge for that row of the first pixel block, wherein said scaler comprises a processor for interpolating edge positions to obtain edge positions for interleaved full-resolution rows.

33. An apparatus according to claim 21, wherein said first pixel block contains an edge between two independent colors, said scaler comprising a processor for interpolating edge positions to obtain edge positions for interleaved full resolution rows.

35. An apparatus according to claim 21, wherein said first pixel block contains an edge between two independent colors, said scaler comprising a processor for using edge placement values to determine which full resolution pixel contains the edge for each reduced resolution column.

36. An apparatus according to claim 21, wherein said first pixel block contains an edge between two independent colors, said at least one first pixel block representation comprising entries for each column describing subpixel placement of the edge for that column of the first pixel block, wherein said scaler comprises a processor for interpolating edge positions to obtain edge positions for interleaved full-resolution columns.

37. An apparatus according to claim 21, wherein said first pixel block contains an edge between two independent colors, said scaler comprising a processor for interpolating edge positions to obtain edge positions for interleaved full resolution columns.

38. An apparatus according to claim 21, comprising an encoder for encoding image regions of varying color including a storage device for storing at least one color value and wherein the scaler also scales the first pixel block representation and linearly interpolates between said at least one color and other colors of neighboring blocks of pixels.

39. An apparatus according to claim 38, wherein the pixel block size is 8 by 8 pixels.

40. An apparatus according to claim 38, further comprising a bitmap generator for generating a bitmap for each of said at least one color, wherein said bitmap is used in the selection of pixels by the scaler when linearly interpolating.

41. An apparatus according to claim 40, wherein the processor also determines a color value of said one color and said other colors, and places said revised color at each location indicated by said bitmaps.

42. The apparatus of claim 21, wherein the first pixel block representation includes an identifier of the first encoding method and wherein the second pixel block representation includes an identifier of the second encoding method.