Method, system, program, and data structure for generating raster objects

• US 6,850,338 B1
• Filed: 05/12/2000
• Issued: 02/01/2005
• Est. Priority Date: 05/12/2000
• Status: Expired due to Term

• Current Assignee: Ricoh Company Limited
• Original Assignee: International Business Machines Corporation
• Inventors: Kush, Christopher Starbuck, Varga, John Thomas, Aschenbrenner, Jean Margaret
• Primary Examiner(s): Poon, King Y.
• Application Number:
  US09/569,777
• Time in Patent Office: 1,726 Days
• Field of Search: 358 11- 19, 358 111- 118, 358/2.1, 358/2.99, 358/3.21, 358/3.24, 358/501, 358/515, 382173-180, 345418-428, 715/530, 715/531, 712/28
• US Class Current: 358/1.15
• CPC Class Codes: G06K 15/02 using printers
• CPC Class Codes: G06K 15/1855 Combining raster data and graphic primitives
• CPC Class Codes: H04N 1/3871 the composed originals being of different kinds, e.g. low- and high-resolution originals

Abstract

Disclosed is a method, system, program, and data structure for generating raster objects. A plurality of input contone and line work objects are received containing contone or line work data for at least one pixel on a sheet. For each input contone object, at least one output contone object is generated including color data for each pixel in the input contone object. For each input line work object, at least one output line work object is generated including color data for each pixel in the input print data object. Control data is generated for each pixel indicating whether to select data from the output line work object or output contone object for the pixel, wherein the control data is used by logic to select color data from the output line work object or output contone object for pixel data to send to an output device to render the pixel data.

Claims

1. A method for generating raster objects, comprising:

receiving a plurality of input contone and line work objects containing contone or line work data for at least one pixel on a sheet;

generating for each input contone object at least one output contone object including color data for each pixel in the input contone object;

generating for each input line work object at least one output line work object including color data for each pixel in the input line work object; and

generating control data for each pixel, wherein the control data is encoded to indicate one of a selection of pixel data from the output line work object, a selection of pixel data from a highest priority output contone object, and a selection of transparency and wherein the control data is used by logic to select color data from the output line work object or output contone object for pixel data to send to an output device to render the pixel data.

2. The method of claim 1, further comprising generating for each input contone and line work objects one output contone and line work object for each color component of the color data, wherein the logic is implemented in hardware, wherein a first number of the generated at least one output line work object does not exceed a first predetermined number of line work objects per scan line capable of being processed by the logic, and wherein a second number of the generated at least one output contone object does not exceed a second predetermined number of contone objects per scan line capable of being processed by the logic.

3. The method of claim 1, further comprising:

generating from each input line work object one intermediary line work object including color data for each pixel in the input line work object, wherein the output line work object is generated from one intermediary line work object;

generating from each input contone object one intermediary contone object including color data for each pixel in the input contone object, wherein the output contone object is generated from one intermediary contone object;

determining whether there are more than a maximum number of intermediary line work objects that intersect one scan line; and

merging multiple intermediary line work objects into one merged output line work object if there are more than the maximum number of intermediary line work objects intersecting the scan line, wherein one output line work object is generated for the merged intermediary line work object such that the generated output line work objects that intersect a scan line are less than the maximum number.

4. The method of claim 3, wherein merging the intermediary line work objects comprises:

determining regions comprising one or more scan lines intersected by a set of one or more intermediary line work objects, wherein there is a separate region for each set of scan lines intersected by a unique set of intermediary line work objects; and

determining for each region the set of intermediary line work objects that intersect the region, wherein the output line work objects are generated for each region and one merged output line work objects is generated for each region that has more than the maximum number of intermediary line work objects that intersect the region.

5. The method of claim 3, wherein each intermediary line work object has an associated priority value, wherein color data of one intermediary line work object is to be displayed over color data from intermediary line work objects having a lower associated priority, further comprising:

selecting at least two intermediary line work objects to merge into one merged output line work object for the region, wherein there is no intermediary line work object having a priority between the priorities associated with the selected line work object.

6. The method of claim 1, wherein generating each output line work object comprises performing:

associating a priority value with each intermediary line work and contone object has an associated priority value;

defining at least one set of one or more input line work objects that provide pixel data for a same set of one or more scan lines;

selecting, for each defined set of line work objects, a highest priority input line work object in one set of input line work objects; and

generating, for each defined set of line work objects, color data for each pixel in the output line work object from non-transparent color data supplied for the pixel from the selected input line work object and setting the control data for the pixel to use the color data in the output line work object if there is no input contone object including non-transparent color data for the pixel having higher priority than the selected input line work object.

7. The method of claim 6, further comprising setting the control data for the pixel in the output line work object for the selected input line work object to use non-transparent color data in the output contone object for the pixel if the input contone object providing the non-transparent color data has a higher priority than the selected input line work object.

8. The method of claim 6, further comprising setting the control data for the pixel in the output line work object to transparent if the input line work object for the output line work object has transparent color data for the pixel and there is no input contone object with a higher priority than the selected input line work object providing non-transparent color data for the pixel, wherein a control data setting of transparent indicates that a next lower priority output line work object is considered to determine the color data for the pixel or that no color data is provided for the pixel.

9. The method of claim 1, further comprising generating a header object for each output line work object and output contone object including information identifying a location of the corresponding output line work or contone object in memory.

10. The method of claim 9, further comprising generating a linked list of pointers to the header objects corresponding to output line work and contone objects, wherein the list of pointers is ordered based on a priority associated with the input line work and contone objects used to generate the output line work and contone objects.

11. The method of claim 2, wherein the selection of transparency indicates that a pixel corresponding to a first output line work object is transparent and that a second output line work object should be used by the logic, wherein the first output line work object has a higher priority than the second output line work object.

12. The method of claim 11, wherein the control data is encoded in at least two bits, and wherein the second output line work object is a next lower priority output line work object to the first output line work object.

13. A system for generating raster objects, comprising:

means for receiving a plurality of input contone and line work objects containing contone or line work data for at least one pixel on a sheet;

means for generating for each input contone object at least one output contone object including color data for each pixel in the input contone object;

means for generating for each input line work object at least one output line work object including color data for each pixel in the input line work object; and

means for generating control data for each pixel, wherein the control data is encoded to indicate one of a selection of pixel data from the output line work object, a selection of pixel data from a highest priority output contone object and a selection of transparency, and wherein the control data is used by logic to select color data from the output line work object or output contone object for pixel data to send to an output device to render the pixel data.

14. The system of claim 13, further comprising means for generating for each input contone and line work objects one output contone and line work object for each color component of the color data, wherein the logic is implemented in hardware, wherein a first number of the generated at least one output line work object does not exceed a first predetermined number of line work objects per scan line capable of being processed by the logic, and wherein a second number of the generated at least one output contone object does not exceed a second predetermined number of contone objects per scan line capable of being processed by the logic.

15. The system of claim 13, further comprising:

means for generating from each input line work object one intermediary line work object including color data for each pixel in the input line work object, wherein the output line work object is generated from one intermediary line work object;

means for generating from each input contone object one intermediary contone object including color data for each pixel in the input contone object, wherein the output contone object is generated from one intermediary contone object;

means for determining whether there are more than a maximum number of intermediary line work objects that intersect one scan line; and

means for merging multiple intermediary line work objects into one merged output line work object if there are more than the maximum number of intermediary line work objects intersecting the scan line, wherein one output line work object is generated for the merged intermediary line work object such that the generated output line work objects that intersect a scan line are less than the maximum number.

16. The system of claim 15, wherein the means for merging the intermediary line work objects further comprises:

means for determining regions comprising one or more scan lines intersected by a set of one or more intermediary line work objects, wherein there is a separate region for each set of scan lines intersected by a unique set of intermediary line work objects; and

means for determining for each region the set of intermediary line work objects that intersect the region, wherein the output line work objects are generated for each region and one merged output line work objects is generated for each region that has more than the maximum number of intermediary line work objects that intersect the region.

17. The system of claim 15, wherein each intermediary line work object has an associated priority value, wherein color data of one intermediary line work object is to be displayed over color data from intermediary line work objects having a lower associated priority, further comprising:

means for selecting at least two intermediary line work objects to merge into one merged output line work object for the region, wherein there is no intermediary line work object having a priority between the priorities associated with the selected line work object.

18. The system of claim 13, wherein the means for generating each output line work object further comprises:

means for associating a priority value with each intermediary line work and contone object has an associated priority value;

means for defining at least one set of one or more input line work objects that provide pixel data for a same set of one or more scan lines;

means for selecting, for each defined set of line work objects, a highest priority input line work object in one set of input line work objects; and

means for generating, for each defined set of line work objects, color data for each pixel in the output line work object from non-transparent color data supplied for the pixel from the selected input line work object and setting the control data for the pixel to use the color data in the output line work object if there is no input contone object including non-transparent color data for the pixel having higher priority than the selected input line work object.

19. The system of claim 18, further comprising means for setting the control data for the pixel in the output line work object for the selected input line work object to use non-transparent color data in the output contone object for the pixel if the input contone object providing the non-transparent color data has a higher priority than the selected input line work object.

20. The system of claim 18, further comprising means for setting the control data for the pixel in the output line work object to transparent if the input line work object for the output line work object has transparent color data for the pixel and there is no input contone object with a higher priority than the selected input line work object providing non-transparent color data for the pixel, wherein a control data setting of transparent indicates that a next lower priority output line work object is considered to determine the color data for the pixel or that no color data is provided for the pixel.

21. The system of claim 13, further comprising means for generating a header object for each output line work object and output contone object including information identifying a location of the corresponding output line work or contone object in memory.

22. The system of claim 21, further comprising means for generating a linked list of pointers to the header objects corresponding to output line work and contone objects, wherein the list of pointers is ordered based on a priority associated with the input line work and contone objects used to generate the output line work and contone objects.

23. The system of claim 14, wherein the selection of transparency indicates that a pixel corresponding to a first output line work object is transparent and that a second output line work object should be used by the logic, wherein the first output line work object has a higher priority than the second output line work object.

24. The system of claim 23, wherein the control data is encoded in at least two bits, and wherein the second output line work object is a next lower priority output line work object to the first output line work object.

25. An information bearing medium for generating raster objects, wherein the information bearing medium includes code capable of causing a processor to perform:

receiving a plurality of input contone and line work objects containing contone or line work data for at least one pixel on a sheet;

generating for each input contone object at least one output contone object including color data for each pixel in the input contone object;

generating for each input line work object at least one output line work object including color data for each pixel in the input line work object; and

generating control data for each pixel, wherein the control data is encoded to indicate one of a selection of pixel data from the output line work object, a selection of pixel data from a highest priority output contone object, and a selection of transparency, and wherein the control data is used by logic to select color data from the output line work object or output contone object for pixel data to send to an output device to render the pixel data.

26. The information bearing medium of claim 25, wherein the code is further capable of causing the processor to perform generating for each input contone and line work objects one output contone and line work object for each color component of the color data, wherein the logic is implemented in hardware, wherein a first number of the generated at least one output line work object does not exceed a first predetermined number of line work objects per scan line capable of being processed by the logic, and wherein a second number of the generated at least one output contone object does not exceed a second predetermined number of contone objects per scan line capable of being processed by the logic.

27. The information bearing medium of claim 25, wherein the code is further capable of causing the processor to perform

generating from each input line work object one intermediary line work object including color data for each pixel in the input line work object, wherein the output line work object is generated from one intermediary line work object;

generating from each input contone object one intermediary contone object including color data for each pixel in the input contone object, wherein the output contone object is generated from one intermediary contone object;

determining whether there are more than a maximum number of intermediary line work objects that intersect one scan line; and

merging multiple intermediary line work objects into one merged output line work object if there are more than the maximum number of intermediary line work objects intersecting the scan line, wherein one output line work object is generated for the merged intermediary line work object such that the generated output line work objects that intersect a scan line are less than the maximum number.

28. The information bearing medium of claim 25, wherein merging the intermediary line work objects comprises:

determining regions comprising one or more scan lines intersected by a set of one or more intermediary line work objects, wherein there is a separate region for each set of scan lines intersected by a unique set of intermediary line work objects; and

determining for each region the set of intermediary line work objects that intersect the region, wherein the output line work objects are generated for each region and one merged output line work objects is generated for each region that has more than the maximum number of intermediary line work objects that intersect the region.

29. The information bearing medium of claim 27, wherein each intermediary line work object has an associated priority value, wherein color data of one intermediary line work object is to be displayed over color data from intermediary line work objects having a lower associated priority, wherein the code is further capable of causing the processor to perform:

selecting at least two intermediary line work objects to merge into one merged output line work object for the region, wherein there is no intermediary line work object having a priority between the priorities associated with the selected line work object.

30. The information bearing medium of claim 25, wherein the code for generating each output line work object is further capable of causing the processor to perform:

associating a priority value with each intermediary line work and contone object has an associated priority value;

defining at least one set of one or more input line work objects that provide pixel data for a same set of one or more scan lines;

selecting, for each defined set of line work objects, a highest priority input line work object in one set of input line work objects; and

generating, for each defined set of line work objects, color data for each pixel in the output line work object from non-transparent color data supplied for the pixel from the selected input line work object and setting the control data for the pixel to use the color data in the output line work object if there is no input contone object including non-transparent color data for the pixel having higher priority than the selected input line work object.

31. The information bearing medium of claim 30, wherein the code is further capable of causing the processor to perform setting the control data for the pixel in the output line work object for the selected input line work object to use non-transparent color data in the output contone object for the pixel if the input contone object providing the non-transparent color data has a higher priority than the selected input line work object.

32. The information bearing medium of claim 30, wherein the code is further capable of causing the processor to perform setting the control data for the pixel in the output line work object to transparent if the input line work object for the output line work object has transparent color data for the pixel and there is no input contone object with a higher priority than the selected input line work object providing non-transparent color data for the pixel, wherein a control data setting of transparent indicates that a next lower priority output line work object is considered to determine the color data for the pixel or that no color data is provided for the pixel.

33. The information bearing medium of claim 25, wherein the code is further capable of causing the processor to perform generating a header object for each output line work object and output contone object including information identifying a location of the corresponding output line work or contone object in memory.

34. The information bearing medium of claim 25, wherein the code is further capable of causing the processor to perform generating a linked list of pointers to the header objects corresponding to output line work and contone objects, wherein the list of pointers is ordered based on a priority associated with the input line work and contone objects used to generate the output line work and contone objects.

35. The information bearing medium of claim 26, wherein the selection of transparency indicates that a pixel corresponding to a first output line work object is transparent and that a second output line work object should be used by the logic, wherein the first output line work object has a higher priority than the second output line work object.

36. The information bearing medium of claim 35, wherein the control data is encoded in at least two bits, and wherein the second output line work object is a next lower priority output line work object to the first output line work object.

37. A computer readable medium containing raster object data structures comprising:

at least one output line work object including line work color data for each pixel for which color data is provided in at least one input line work object, wherein one output line work object is generated for each input line work object; and

at least one output contone object including contone color data for each pixel for which color data is provided in at least one input contone object, wherein one output line work object is generated for each input contone object; and

control data for each pixel indicating whether to select data from the output line work object or output contone object for the pixel, wherein the control data is encoded to indicate one of a selection of pixel data from the output line work object, a selection of pixel data from a highest priority output contone object, and a selection of transparency, and wherein the control data is used by logic to select color data from the output line work object or output contone object for pixel data to send to an output device to render the pixel data.

38. The computer readable medium of claim 37, wherein there is one output contone and line work object generated for each input contone and line work object, respectively, for each color component of the color data, wherein the logic is implemented in hardware, and wherein a first number of the generated at least one output line work object does not exceed a first predetermined number of line work objects per scan line capable of being processed by the logic, and wherein a second number of the generated at least one output contone object does not exceed a second predetermined number of contone objects per scan line capable of being processed by the logic.

39. The computer readable medium of claim 37, further comprising:

at least one intermediary line work object including color data for each pixel in the input line work object, wherein one intermediary line work object is generated for each input line work object, wherein the output line work object is generated from one intermediary line work object;

at least one intermediary contone object including color data for each pixel in the input contone object and generated for each input contone object, wherein the output contone object is generated from one intermediary contone object;

a merged output line work object formed by merging multiple intermediary line work objects if there are more than the maximum number of intermediary line work objects intersecting the scan line, wherein one output line work object is generated for the merged intermediary line work object such that the generated output line work objects that intersect a scan line are less than the maximum number.

40. The computer readable medium of claim 39, wherein each intermediary line work object has an associated priority value, wherein color data of one intermediary line work object is to be displayed over color data from intermediary line work objects having a lower associated priority, wherein there is no intermediary line work object having a priority between the priorities associated with the selected line work object.

41. The computer readable medium of claim 37, further comprising a header object for each output line work object and output contone object including information identifying a location of the corresponding output line work or contone object in memory.

42. The computer readable medium of claim 41, further comprising a linked list of pointers to the header objects corresponding to output line work and contone objects, wherein the list of pointers is ordered based on a priority associated with the input line work and contone objects used to generate the output line work and contone objects.

43. The computer readable medium of claim 38, wherein the selection of transparency indicates that a pixel corresponding to a first output line work object is transparent and that a second output line work object should be used by the logic, wherein the first output line work object has a higher priority than the second output line work object.

44. The computer readable medium of claim 43, wherein the control data is encoded in at least two bits, and wherein the second output line work object is a next lower priority output line work object to the first output line work object.