US5157765A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for pipelined parallel rasterization
Assignee: International Business Machines Corp
•
Filing: 1992-01-03
•
Granted: 1992-10-20
•
Expires: 2012-01-03
Abstract
Abstract A rasterizer 10 for converting a datastream 12 which describes a page to be printed into a rasterized pagemap bitstream 13 to be sent to a printer. The rasterization is done in four stages using parallel processors in all stages except the first, and pipelining the processors between all of the stages. In the first stage 11, a scan processor 14 identifies and stores state-independent blocks 14 in the datastream. In the second stage 17, parallel block processors 22 convert the scanned blocks into stored intermediate-form data objects 20 and request preparation of often-used resources such as characters. In the third stage 23, the objects are sorted and stored by geographical region of the pagemap by parallel sort processors 24. In the fourth stage 31, the sorted objects are rasterized into pelmaps and placed in the pagemap by parallel bin processors 30. All four stages are pipelined. End-of-block markers are used in the third and fourth stages to maintain correct ordering of the objects within the final pagemap. The rasterizer uses general purpose microprocessors for all stages.
Inventors
- 👤 Yitzhak Birk
- 👤 James M. McCrossin
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 12:08
CPC Classifications
G; G09; G09G; G09G5/00; G09G5/36; G09G5/39; G09G5/393; G06; G06K; G06K15/00; G06K15/02; G06K15/18; G06K15/1848; G06K15/1856; G06K15/1857; G06K2215/00; G06K2215/0002; G06K2215/0005; G06K2215/0014; G06K2215/0062; G06K2215/0065
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
123 words
A method for rasterizing a datastream of sequential commands specifying at least one output image, comprising the computer-implemented steps of: (a) identifying at least two state-independent blocks of said commands within the datastream, the sequence of received commands in said datastream indicative of image portions that overlap other image portions; (b) converting the commands in said blocks, in parallel, into intermediate-form data and maintaining a sequence record of said intermediate-form data; and (c) converting into rasterized pelmaps representing at least part of the image, the intermediate-form data for at least two non-overlapping geographical regions of the image in parallel, and for each region, in the same sequence as said sequential commands were received which gave rise to said intermediate-form data for said region.
Claim 2
Independent Claim
123 words
A method for rasterizing a datastream of sequential commands specifying at least one output image, comprising the computer-implemented steps of: (a) identifying at least two state-independent blocks of said commands within the datastream, the sequence of received commands in said datastream indicative of image portions that overlap other image portions; (b) converting the commands in said blocks, in parallel, into intermediate-form data and maintaining a sequence record of said intermediate-form data; and (c) converting into rasterized pelmaps representing at least part of the image, the intermediate-form data for at least two non-overlapping geographical regions of the image in parallel, and for each region, in the same sequence as said sequential commands were received which gave rise to said intermediate-form data for said region.
Claim 3
Dependent Claim
14 words
A method according to claim 1, wherein step (b) is pipelined with step (a).
Claim 4
Dependent Claim
14 words
A method according to claim 1, wherein step (c) is pipelined with step (b).
Claim 5
Dependent Claim
41 words
A method according to claim 1, further comprising, after step b, the step of: b(1) sorting, in parallel, the intermediate-form data by geographical region of the image in which said intermediate-form data belongs before converting the intermediate-form data into rasterized pelmaps.
Claim 6
Dependent Claim
21 words
A method according to claim 1, further comprising the step of (d) assembling the pelmaps into a representation of the image.
Claim 7
Dependent Claim
28 words
A method according to claim 5, wherein the datastream comprises commands in a printer page definition language (PDL); and further comprising the step of (e) printing the image.
Claim 8
Dependent Claim
20 words
A method according to claim 1, wherein steps b, b1, c are performed, in parallel, by programmed general purpose microprocessors.
Claim 9
Dependent Claim
20 words
A method according to claim 7, wherein the microprocessors are programmed to perform more than one of the steps (a)-(c).
Claim 10
Dependent Claim
39 words
A method according to claim 1, further including, after step b, the steps of: b1 determining if any intermediate-form data is to be multiply used; and b2 reusing said intermediate-form data in converting the stored intermediate-form data into pelmaps.
Claim 11
Dependent Claim
34 words
A method according to claim 9, further including the step of preparing reusable intermediate-form data in parallel for at least two items of the selected block but only converting said reusable intermediate-form data once.
Claim 12
Dependent Claim
24 words
A method according to claim 10, wherein the reusable intermediate-form data is prepared in parallel with the conversion of the blocks into intermediate-form data.
Claim 13
Dependent Claim
22 words
A method according to claim 10, wherein the reusable intermediate-form data is prepared in parallel with the sorting of the intermediate-form data.
Claim 14
Independent Claim
114 words
A system for rasterizing a datastream of sequential commands specifying at least one output image, comprising: means for identifying at least two state-independent blocks of said commands within the datastream, the sequence of received commands in said datastream indicative of image portions that overlap other image portions; parallel processing means for converting the commands in said blocks into intermediate-form object data and maintaining a sequence record of said intermediate-form object data; and parallel-processing means for converting the intermediate-form object data into rasterized pelmaps of at least two non-overlapping geographic regions of the image and, for each region, in the same sequence as said sequential commands were received which gave rise to said intermediate-form data.
Claim 15
Independent Claim
114 words
A system for rasterizing a datastream of sequential commands specifying at least one output image, comprising: means for identifying at least two state-independent blocks of said commands within the datastream, the sequence of received commands in said datastream indicative of image portions that overlap other image portions; parallel processing means for converting the commands in said blocks into intermediate-form object data and maintaining a sequence record of said intermediate-form object data; and parallel-processing means for converting the intermediate-form object data into rasterized pelmaps of at least two non-overlapping geographic regions of the image and, for each region, in the same sequence as said sequential commands were received which gave rise to said intermediate-form data.
Claim 16
Dependent Claim
20 words
A system according to claim 13, wherein the means for converting blocks is pipelined with the means for identifying blocks.
Claim 17
Dependent Claim
22 words
A system according to claim 13, wherein the means for converting intermediate-form object data is pipelined with the means for converting blocks.
Claim 18
Dependent Claim
33 words
A system according to claim 13, further including parallel-processing means for sorting, in parallel, the intermediate-form object data into the geographical regions of the pagemap in which said intermediate form object data belong.
Claim 19
Dependent Claim
35 words
A system according to claim 16, wherein the means for sorting is pipelined with the means for converting blocks; and wherein the means for converting intermediate-form object data is pipelined with the means for sorting.
Claim 20
Dependent Claim
25 words
A system according to claim 16, wherein the parallel processing means for sorting comprises at least two general purpose microprocessors programmed to operate in parallel.
Claim 21
Dependent Claim
17 words
A system according to claim 13, further including means for printing the image based on the pagemap.
Claim 22
Dependent Claim
10 words
A system according to claim 19, further including a printer.
Claim 23
Dependent Claim
30 words
A system according to claim 13, wherein the parallel processing means for converting the commands in said blocks comprises at least two general purpose microprocessors programmed to operate in parallel.
Claim 24
Dependent Claim
26 words
A system according to claim 13, wherein the means for converting intermediate-form object data comprises at least two general purpose microprocessors programmed to operate in parallel.
Claim 25
Dependent Claim
33 words
A system according to claim 13, further including means for converting multiply used intermediate-form object data only once and for reusing said intermediate-form object data in converting the intermediate-form data into rasterized pelmaps.
Claim 26
Dependent Claim
34 words
A system according to claim 23, further including means for preparing reusable intermediate-form data in parallel for at least two items of the selected block but converting said reusable intermediate-form object data only once.
Claim 27
Dependent Claim
26 words
A system according to claim 23, further including means for preparing the reusable intermediate-form data in parallel with the means for converting blocks into intermediate-form data.
Claim 28
Dependent Claim
25 words
A system according to claim 23, further including means for preparing the reusable intermediate-form data in parallel with the means for sorting the intermediate-form data.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-10-20 | 1996-04-20 | 1996-10-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-10-20 | 2000-04-20 | 2000-10-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-10-20 | 2004-04-20 | 2004-10-20 | $7700.00 | Window Closed / Lapsed |