Expression tree optimization for processing obscured graphical objects

Abstract

The present invention relates to a method, apparatus and system for optimizing an expression tree (101,902,1102) for compositing an image. Such an expression tree (101,902, 1102) can comprise at least two nodes. Each node is either a graphical element (102,104) or image compositing operator ((103,104) and has a region of the image represented by the node (102,103,104). In the method, for at least one node in the tree, several steps are carried out. The region represented by the node (103,104) is compared to a region representation data structure, which is preferably a quadtree representation, corresponding to one or more regions represented by at least one other node. A determination is then made if the region represented by the node (102,103,104) is totally or partially obscured by the one or more regions. If the region represented by the node is at least partially or totally obscured, the expression tree (101,902,1102) is modified. Modifying the expression tree (101,902,1102) involves applying a clipping operator (58,59) to the node if the region represented by the node is partially obscured. If the node is totally obscured, either removing the node if the node is a graphical element (102, 104) or applying a predetermined set of node replacement rules in accordance with the image compositing operator if the node (103) is a image compositing operator.

1. A method of optimising an expression tree, said expression tree for compositing an image and comprising at least three nodes, each said node of said tree being at least either a graphical element or a graphical operator, the method comprising, for at least one node in said tree, the steps of:
 comparing a first region of said node to a second region derived from at least one other node anywhere in said expression tree; 
 determining if said first region is totally or partially obscured by said second region; and 
 modifying the expression tree if said first region is at least partially or totally obscured by said second region, to form an optimised expression tree in which an optimised part of said expression tree substantially represents unobscured portions of said first region, 
 wherein said steps are performed by means of a programmed computer. 
 
     
     
       2. The method as recited in  claim 1 , wherein the step of modifying the expression tree includes applying a clipping operator to said node in the event said first region is partially obscured. 
     
     
       3. The method as recited in  claim 1 , wherein the step of modifying the expression tree when said node is totally obscured further includes the steps of:
 removing the node; and 
 if the node has a parent node which has a graphical operator, selecting a node replacement rule from a predetermined set of node replacement rules in accordance with said graphical operator and applying said rule. 
 
     
     
       4. The method as recited in  claim 3 , wherein said predetermined set of node replacement rules comprises at least one step selected from the group consisting of:
 if the parent node is an “over” graphical operator and the current node is at a left branch of the parent node, replacing the parent node with a right subtree of the parent node; 
 if the parent node is an “over” graphic graphical operator and the current node is at a right branch of the parent node, replacing the parent node with a left subtree of the parent node; 
 if the parent node is an “in” graphical operator, removing the parent node and any subtrees branching off the parent node; 
 if the parent node is a “ratop” graphical operator and the current node is at a left branch of the parent node, removing the parent node and any subtrees branching off the parent node; 
 if the parent node is a “ratop” graphical operator and the current node is at a right branch of the parent node, replacing the parent node with a left subtree of the parent node; 
 if the parent node is an “out” graphical operator and the current node is at a left branch of the parent node, removing the parent node and any subtrees branching off the parent node; 
 if the parent node is an “out” graphical operator and the current node is at a right branch of the parent node, replacing the parent node with a left subtree of the parent node; 
 if the parent node is a “plusC” graphical operator and the current node is at a left branch of the parent node, replacing the parent node with a right subtree of the parent node; 
 if the parent node is a “plusC” graphical operator and the current node is at a right branch of the parent node, replacing the parent node with a left subtree of the parent node; 
 if the parent node is a “plusW” or an “Xor” graphical operator and the current node is at a left branch of the parent node, replacing the parent node with a right subtree of the parent node; and 
 if the parent node is an “plusW” or an “Xor” graphical operator and the current node is at a right branch of the parent node, replacing the parent node with a left subtree of the parent node. 
 
     
     
       5. The method as recited in any one of  claims 1  to  4 , wherein the graphical operators are image compositing operators. 
     
     
       6. The method as recited in  claim 1 , wherein said second region is represented by a region representation in the form of a hierarchical data structure. 
     
     
       7. The method as recited in  claim 6 , wherein the hierarchical data structure is a quadtree representation. 
     
     
       8. A method of optimising an expression tree for compositing an image, said expression tree comprising a plurality of nodes, each said node being at least either a graphical element or a graphical operator, said method comprising the steps of:
 traversing the expression tree node by node; and  
 determining at a current node if a first region of the image represented at said current node is obscured by a second region derived from at least one other node anywhere in said expression tree, and modifying said expression tree in the event that said first region of said current node is partially or totally obscured by said second region, to form an optimised expression tree in which an optimised part of said expression tree substantially represents unobscured portions of said first region,  
 wherein said steps are performed by means of a programmed computer. 
 
     
     
       9. The method as recited in claim ti, wherein said modityinig modifying includes removing said current rode or replacing said current node with another node of the expression tree. 
     
     
       10. The method as recited in claim  7  8, wherein said modifying further includes clipping, or marking for clipping at a later time, said first region represented by said current node. 
     
     
       11. A method of optimising an expression tree for compositing an image, said expression tree comprising a plurality of nodes, each said node comprising:
 at least either a graphical element or a graphical operator and having a region of the image represented by said node, said method comprising the steps of:
 traversing the expression tree node by node and at each current node comprising a graphical operator applying the sub-steps of: 
 (i) receiving a first region representation from a parent node; 
 (ii) passing to a first operand of said graphical operator a modified first region representation in accordance with a first predetermined modification rule for said operator; 
 (iii) returning to the graphical operator a second region representation of regions obscured by a sub-tree associated with the first operand; 
 (iv) passing to a second operand of said graphical operator a modified second region representation in accordance with a second predetermined modification rule for said operator; 
 (v) returning to the graphical operator a third region representation of regions obscured by a sub-tree associated with the second operand; and 
 (vi) determining, in accordance will a set rule for said graphical operator, a final region representation to be returned to the parent node to form an optimised expression tree in which said final region representation substantially represents an unobscured portion of the first region represented at the parent node a region within which said current node is capable of obscuring other nodes in said expression tree, 
 
 wherein said steps are performed by means of a programmed computer. 
 
     
     
       12. The method as recited in  claim 11 , wherein said set rule is selected from the group consisting of:
 (a) where the graphic operator is an “over” or a “plusC” operator, the final region representation to be returned to the parent node is determined from a union of the second region representation and the third region representation; 
 (b) where the graphic operator is an “in” operator, the final region representation to be returned to the parent node is determined from an intersection of the second region representation and the third region representation; 
 (c) where the graphic operator is a “ratop” operator, the final region representation to be returned to the parent node is the second region representation; 
 (d) where the graphic operator is an “out” operator, the final region representation to be returned to the parent node is determined from a difference of the second region representation and a region representation comprising at least a region represented by a bounding box of a node at a right subtree of the current node; and 
 (e) where the graphic operator is an “Xor” or a “plusW” operator the final region representation to be returned to the parent node is determined from a union of the second region representation less a region representation comprising at least a region represented by a bounding box of a node at a right subtree of the current node and the third region representation less a region representation containing a bounding box of a node at a right subtree of the current node. 
 
     
     
       13. The method as recited in  claim 11 , wherein the first predetermined modification rule comprises:
 passing substantially the first region representation as the modified first region representation in the event that the graphical operator is an “over”, “in”, “ratop”, “plusC”, “plusW”, “Xor”, or “out” (visit left operand first)” or alike operators operator; and 
 if the graphical operator is an “out (visit right operand first)” operation, passing as the modified first region representation a union of the first region representation with the second region representation. 
 
     
     
       14. The method as recited in  claim 11 , wherein the second predetermined modification rule comprises:
 passing substantially the first region representation as the modified second region representation in the event that the graphical operator is an “in”, “ratop”, “out”, “plusC”, “plusW”, or “Xor” or alike operators operator; and 
 in the event that the graphical operator is an “over” operator passing as the modified second region representation union of the first region representation with the second region representation. 
 
     
     
       15. The method as recited in any one of  claims 11  to  14 , wherein the image representation is not created at a node, or returned to a parent node of said node, unless said image representation is subsequently utilised. 
     
     
       16. The method as recited in  claim 15 , wherein the image representation is not created at a node or returned to the parent node if the node is selected from a group consisting of:
 a right operand of an “over” operator and the “over” operator node does not need to return an image representation to its parent node; 
 a left operand of an “in”, “plusC”, “plusW” or “Xor” operator and said operator node does not need to return an image representation to its parent node; 
 a right operand of an “in”, “plusC”, “plusW” or “Xor” operator and said operator node does not need to return an image representation to its parent node; 
 a left operand of an “out” or “ratop” operator and said operator node does not need to return an image representation to its parent node; 
 a right operand of a “ratop” operator; 
 a root of the expression tree; 
 an operand of an image warp, affine transformation or convolution operator; and  
 an operand of a colour transformation that does not preserve opaqueness or if said transformation node does not need to return an image representation to its parent node. 
 
     
     
       17. An apparatus for optimising an expression tree, said expression tree for compositing an image and comprising at least three nodes, each said node of said tree being at least either a graphical element or a graphical operator, the apparatus comprising:
 means for, comparing a first region of said node to a second region derived from at least one other node anywhere in said expression tree; 
 means for determining if said first region is totally or partially obscured by said second region; and 
 means for modifying the expression tree in the event that said first region is at least partially or totally obscured by said second region, to form an optimized expression tree in which an optimized part of said expression tree substantially represents unobscured portions of said first region. 
 
     
     
       18. The apparatus as recited in  claim 17 , wherein the modifying means includes means for applying a clipping operator to said node in the event said first region is partially obscured. 
     
     
       19. The apparatus as recited in  claim 17 , wherein the modifying means comprises:
 means for removing the node; and 
 means for selecting a node replacement rule from a predetermined set of node replacement rules in accordance with said graphical operator and applying said rule if the node has a parent node which has a graphical operator and the node is totally obscured. 
 
     
     
       20. The apparatus as recited in  claim 19 , wherein said predetermined set of node replacement rules comprises at least one step selected from the group consisting of:
 if the parent node is an “over” graphical operator and the current node is at a left branch of the parent node, replacing the parent node with a right subtree of the parent node; 
 if the parent node is an “over” graphic graphical operator and the current node is at a right branch of the parent node, replacing the parent node with a left subtree of the parent node; 
 if the parent node is an “in” graphical operator, removing the parent node and any subtrees branching off the parent node; 
 if the parent node is a “ratop” graphical operator and the current node is at a left branch of the parent node, removing the parent node and any subtrees branching off the parent node; 
 if the parent node is a “ratop” graphical operator and the current node is at a right branch of the parent node, replacing the parent node with a left subtree of the parent node; 
 if the parent node is an “out” graphical operator and the current node is at a left branch of the parent node, removing the parent node and any subtrees branching off the parent node; 
 if the parent node is an “out” graphical operator and the current node is at a right branch of the parent node, replacing the parent node with a left subtree of the parent node; 
 if the parent node is a “plusC” graphical operator and the current node is at a left branch of the parent node, replacing the parent node with a right subtree of the parent node; 
 if the parent node is a “plusC” graphical operator and the current node is at a right branch of the parent node, replacing the parent node with a left subtree of the parent node; 
 if the parent node is a “plusW” or an “Xor” graphical operator and the current node is at a left branch of the parent node, replacing the parent node with a right subtree of the parent node; and 
 if the parent node is a “plusW” or an “Xor” graphical operator and the current node is at a right branch of the parent node, replacing the parent node with a left subtree of the parent node. 
 
     
     
       21. The apparatus as recited in any one of  claims 17  to  20 , wherein the graphical operators are image compositing operators. 
     
     
       22. The apparatus as recited in  claim 17 , wherein said second region is represented by a region representation in the form of a hierarchical to data structure. 
     
     
       23. The apparatus as recited in  claim 22 , wherein the hierarchical data structure is a quadtree representation. 
     
     
       24. An apparatus for optimizing an expression tree for compositing an image, said expression tree comprising a plurality of nodes, each said node being at least either a graphical element or a graphical operator, said apparatus comprising:
 means for traversing the expression tree node by node; 
 means for determining at a current node if a first region of the image represented at said current node is obscured by a second region derived from at least one other node anywhere in said expression tree; and 
 means for modifying said expression tree in the event that said first region of said current node is partially or totally obscured by said second region to form an optimized expression tree in which an optimized part of said expression tree substantially represents unobsured unobscured portions of said first region. 
 
     
     
       25. The apparatus as recited in  claim 24 , wherein said modifying means includes means for removing said current node or replacing said current node with another node of the expression tree. 
     
     
       26. The apparatus as recited in  claim 24 , wherein said modifying means further includes means for clipping, or marking for clipping at a later time, the region represented by said current node. 
     
     
       27. An apparatus for optimizing an expression tree for compositing an image, said expression tree comprising a plurality of nodes, each said node comprising at least either a graphical element or a graphical operator and having a region of the image represented by said node, said apparatus comprising:
 means for traversing the expression tree node by node, said traversing means for each current node comprising a graphical operator, further comprising: 
 means for receiving a first region representation from a parent node; 
 means for passing to a first operand of said graphical operator a modified first region representation in accordance with a first predetermined modification rule for said operator; 
 means for returning to the graphical operator a second region representation of regions obscured by a sub-tree associated with the first operand; 
 means for passing to a second operand of said graphical operator a modified second region representation in accordance with a second predetermined modification rule for said operator; 
 means for returning to the graphical operator a third region representation of regions obscured by a sub-tree associated with the second operand; and 
 means for determining, in accordance with a set rule for said graphical operator, a final region representation to be returned to the parent to form an optimized expression tree in which said final region representation substantially represents an unobscured portion of said first region represented at the parent node a region within which said current node is capable of obscuring other nodes in said expression tree. 
 
     
     
       28. The apparatus as recited in  claim 27 , wherein said set rule is selected from the group consisting of:
 (a) where the graphic operator is an “over” or a “plusC” operator, the final region representation to be returned to the parent node is determined from a union of the second region representation and the third region representation; 
 (b) where the graphic operator is an “in” operator, the final region representation to be returned to the parent node is determined from an intersection of the second region representation and the third region representation; 
 (c) where the graphic operator is an a “ratop” operator, the final region representation to be returned to the parent node is the second region representation; 
 (d) where the graphic operator is an “out” operator, the final region representation to be returned to the parent node is determined from a difference of the second region representation and a region representation comprising at least a region represented by a bounding box of a node at a right subtree of the current node; and 
 (e) where the graphic operator is an “Xor” or a “plusW” operator the final region representation to be returned to the parent node is determined from a union of the second region representation less a region representation comprising at least a region represented by a bounding box of a node at a right subtree of the current node and the third region representation less a region representation containing a bounding box of a node at a right subtree of the current node. 
 
     
     
       29. The apparatus as recited in  claim 27 , wherein the first predetermined modification rule comprises:
 passing substantially the first region representation as the modified first region representation in the event that the graphical operator is an “over”, “in”, “ratop”, “plusC”, “plusW”, “Xor”, or “out” (visit left operand first)” or alike operators operator; and 
 if the graphical operator is an “out (visit right operand first)” operation, passing as the modified first region representation a union of the first region representation with the second region representation. 
 
     
     
       30. The apparatus as recited in  claim 27 , wherein the second predetermined modification rule comprises:
 passing substantially the first region representation as the modified second region representation in the event that the graphical operator is an “in”, “ratop”, “out”, “plusC”, “plusW”, or “Xor” or alike operators operator; and 
 in the event that the graphical operator is an “over” operator, passing as the modified second region representation a union of the first region representation with the second region representation. 
 
     
     
       31. The apparatus as recited in any one of  claims 27  to  30 , wherein the image representation is not created at a node, or returned to a parent node of said node, unless said image representation is subsequently utilised. 
     
     
       32. The apparatus as recited in  claim 31 , wherein the image representation is not created at a node or returned to the parent node if the node is selected from a group consisting of:
 a right operand of an “over” operator and the “over” operator node does not need to return an image representation to its parent node; 
 a left operand of an “in”, “plusC”, “plusW” or “Xor” operator and said operator node does nor need to return an image representation to its parent node; 
 a right operand of an “in”, “plusC”, “plusW” or “Xor” operator and said operator node docs not need to return an image representation to its parent node; 
 a left operand of an “out” or “ratop” operator and said operator node does not need to return an image representation to its parent node; 
 a right operand of a “ratop” operator; 
 a root of the expression tree; 
 an operand of an image warp, affine transformation or convolution operator; and  
 an operand of a colour transformation that does not preserve opaqueness or if said transformation node does not need to return an imap representation to its parent node.