Optimization method for the efficient production of images

• US 5,724,494 A
• Filed: 07/21/1995
• Issued: 03/03/1998
• Est. Priority Date: 07/25/1994
• Status: Expired due to Term

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Information Systems Research Australia Pty Limited (Canon Inc.), Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Politis, George
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US08/505,752
• Time in Patent Office: 956 Days
• Field of Search: 395/134, 395/140, 395/141, 345/118, 345/119
• US Class Current: 345/592
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text

Abstract

A system, method and language for compositing or creating images in which the images typically comprise a plurality of graphical elements each including color and opacity information. The system utilizes operators having the graphical elements as operands in which the operators combine the operands according to a function defined by the operators, the colour information, and the opacity information, to produce new graphical elements. The system includes interpreting the language by parsing and executing a sequence of statements and forming an expression tree the nodes of which comprise the graphical elements. Instructions are then derived from the tree. Bounding box methods are used for locating active areas of graphical elements from the nodes. Manipulation of the expression tree is used to reduce the expected execution time of the compositing commands.

Claims

1. A method of producing an image formed from a series of statements and multiple graphical elements, the method being performed by a computer and comprising the steps of:

determining an expression tree comprising a plurality of nodes from the series of statements and the graphical elements for the construction of the image by parsing and executing the series of statements one or more of which include operations which are used to create the expression tree, and

for each node in the tree, constructing a bounding box about locations at which graphical elements of the node and corresponding descendant nodes of the expression tree are active in the production of the image.

2. A method as claimed in claim 1 wherein said construction of said bounding boxes includes constructing a bounding box around leaf nodes of said expression tree and constructing a bounding box of each internal node of said expression tree from the child nodes of said internal node, the size of the bounding box of said internal node being dependant on an operator stored with said internal node and the bounding box of said child nodes of said internal node.

3. A method as claimed in claim 2, wherein said construction of said bounding boxes further comprises intersecting the bounding box of at least one node with the bounding boxes of at least one of the descendants of said at least one node.

4. A method as claimed in claim 3, wherein said intersecting comprises intersecting the bounding box of said at least one node with substantially all its descendants.

5. A method as claimed in claim 4 wherein substantially only that portion of each graphical element which appears in the final image is utilized in producing the image.

6. A method as claimed in claim 3 wherein substantially only that portion of each graphical element which appears in the final image is utilized in producing the image.

7. A method as claimed in claim 2 wherein substantially only that portion of each graphical element which appears in the final image is utilized in producing the image.

8. A method as claimed in claim 1 further comprising the step of, for each node, constructing a second bounding box from the intersection of said bounding box with substantially all of the said bounding boxes of the ancestor nodes of a current node.

9. A method as claimed in claim 8 wherein substantially only that portion of each graphical element which appears in the final image is utilized in producing the image.

10. A method as claimed in claim 1 wherein substantially only that portion of each graphical element which appears in the final image is utilised in producing the image.

11. A method as claimed in claim 1, wherein the construction of one said bounding box at one said node is derived from a union of bounding boxes of descendent nodes to said one node.

12. A method as claimed in claim 11, wherein the union is obtained from at least one operator selected from the group consisting of "over", "rover", "xor", "plusW", "plusC", "in", "rin", "out", "ratop", "rout" and "atop".

13. Apparatus for producing an image formed from a series of statements and multiple graphical elements, the apparatus comprising:

means for determining an expression tree comprising a plurality of nodes from the series of statements and the graphical elements for the construction of the image by parsing and the executing the series of statements one or more of which include operations which are used to create said expression tree, and

means for constructing, for each node in said tree, a bounding box about locations at which graphical elements of the node and corresponding descendant nodes of the expression tree are active in the production of the image.

14. Apparatus as claimed in claim 13, wherein the construction of said bounding boxes includes constructing a bounding box around leaf nodes of said expression tree and constructing a bounding box of each internal node of said expression tree from the child nodes of said internal node, the size of the bounding box of said internal node being dependent on an operator stored with said internal node and the bounding box of said child nodes of said internal node.

15. Apparatus as claimed in claim 14, wherein the construction of said bounding boxes further comprises intersecting the bounding box of at least one node with the bounding boxes of at least one of the descendants of said at least one node.

16. Apparatus as claimed in claim 15, wherein said intersecting comprises intersecting the bounding box of said at least one node with substantially all its descendants.

17. Apparatus as claimed in claim 13, further comprising means for constructing, for each node, a second bounding box from the intersection of said bounding box with substantially all of the bounding boxes of the ancestor nodes of a current node.

18. Apparatus as claimed in claim 13, wherein substantially only that portion of each graphical element which appears in the final image is utilized in producing the image.

19. Apparatus as claimed in claim 13, wherein said means for construction comprises, at one said node, means for forming a union of bounding boxes of descendent nodes to said one node.

20. Apparatus as claimed in claim 19, wherein said union is obtained from at least one operator selected from the group consisting of "over", "rover", "xor", "plusW", "plusC", "in", "rin", "out", "ratop", "rout" and "atop".

21. A recording medium having recorded thereon a computer implementable method for producing an image formed from a series of statements and multiple graphical elements, the method comprising the steps of:

determining an expression tree comprising a plurality of nodes from the series of statements and the graphical elements for the construction of the image by parsing and executing the series of statements one or more of which include operations which are used to create the expression tree; and

for each node in the tree, constructing a bounding box about locations at which graphical elements of the node and corresponding descendant nodes of the expression tree are active in the production of the image.