US5583953A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Intelligent doubling for low-cost image buffers
Assignee: Xerox Corp
•
Filing: 1993-06-30
•
Granted: 1996-12-10
•
Expires: 2013-06-30
Abstract
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.
Inventors
- 👤 Steven J. Harrington
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 14:34
CPC Classifications
G; G06; G06T; G06T3/00; G06T3/40; G06T3/403; G06T9/00; G06T9/005
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
125 words
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.
Claim 2
Independent Claim
125 words
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.
Claim 3
Dependent Claim
31 words
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.
Claim 4
Dependent Claim
75 words
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.
Claim 5
Dependent Claim
31 words
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.
Claim 6
Dependent Claim
84 words
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.
Claim 7
Dependent Claim
31 words
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.
Claim 8
Independent Claim
134 words
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.
Claim 9
Independent Claim
134 words
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.
Claim 10
Dependent Claim
30 words
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.
Claim 11
Dependent Claim
74 words
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.
Claim 12
Dependent Claim
30 words
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.
Claim 13
Dependent Claim
83 words
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.
Claim 14
Dependent Claim
30 words
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.
Claim 15
Independent Claim
225 words
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.
Claim 16
Independent Claim
225 words
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.
Claim 17
Dependent Claim
44 words
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.
Claim 18
Independent Claim
228 words
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.
Claim 19
Independent Claim
228 words
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.
Claim 20
Dependent Claim
47 words
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.
Claim 21
Independent Claim
216 words
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.
Claim 22
Independent Claim
216 words
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.
Claim 23
Dependent Claim
32 words
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.
Claim 24
Dependent Claim
23 words
A method according to claim 18, wherein said determining step further comprises the step of providing a tag and a color table index.
Claim 25
Dependent Claim
47 words
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.
Claim 26
Dependent Claim
23 words
A method according to claim 20, wherein said determining step further comprises the step of providing a tag and a color table index.
Claim 27
Dependent Claim
75 words
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.
Claim 28
Dependent Claim
53 words
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.
Claim 29
Independent Claim
225 words
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.
Claim 30
Independent Claim
225 words
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.
Claim 31
Dependent Claim
31 words
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.
Claim 32
Dependent Claim
22 words
An apparatus according to claim 25, wherein said determining means further comprises means for providing a tag and a color table index.
Claim 33
Dependent Claim
54 words
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.
Claim 34
Dependent Claim
22 words
An apparatus according to claim 27, wherein said determining means further comprises means for providing a tag and a color table index.
Claim 35
Dependent Claim
77 words
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.
Claim 36
Dependent Claim
52 words
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.
References Cited (Backward Citations)
US4183013A
Cited
US4547812A
Cited
US4454593A
Cited
US4620288A
Cited
US4959868A
Cited
US5001576A
Cited
US4986526A
Cited
US5048112A
Cited
US5204665A
Cited
US5347368A
Cited
US5265176A
Cited
US5335295A
Cited
US5293430A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-12-10 | 2000-06-10 | 2000-12-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-12-10 | 2004-06-10 | 2004-12-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-12-10 | 2008-06-10 | 2008-12-10 | $7700.00 | Window Closed / Lapsed |