Patent US5724494A successfully refreshed from Google Patents.
US5724494A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Optimization method for the efficient production of images
Assignee: Canon Inc
•
Filing: 1995-07-21
•
Granted: 1998-03-03
•
Expires: 2015-07-21
Abstract
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.
Inventors
- 👤 George Politis
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 13:47
CPC Classifications
G; G06; G06T; G06T11/00; G06T11/60
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
111 words
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.
Claim 2
Independent Claim
111 words
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.
Claim 3
Dependent Claim
79 words
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.
Claim 4
Dependent Claim
42 words
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.
Claim 5
Dependent Claim
26 words
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.
Claim 6
Dependent Claim
28 words
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.
Claim 7
Dependent Claim
28 words
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.
Claim 8
Dependent Claim
28 words
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.
Claim 9
Dependent Claim
43 words
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.
Claim 10
Dependent Claim
28 words
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.
Claim 11
Dependent Claim
28 words
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.
Claim 12
Dependent Claim
34 words
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.
Claim 13
Dependent Claim
35 words
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".
Claim 14
Dependent Claim
106 words
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.
Claim 15
Dependent Claim
106 words
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.
Claim 16
Dependent Claim
78 words
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.
Claim 17
Dependent Claim
41 words
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.
Claim 18
Dependent Claim
25 words
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.
Claim 19
Dependent Claim
40 words
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.
Claim 20
Dependent Claim
27 words
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.
Claim 21
Dependent Claim
31 words
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.
Claim 22
Dependent Claim
34 words
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".
Claim 23
Dependent Claim
113 words
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.
Claim 24
Dependent Claim
113 words
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.
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) | 2001-03-02 | 2001-09-01 | 2002-03-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-03-02 | 2005-09-01 | 2006-03-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-03-02 | 2009-09-01 | 2010-03-03 | $7700.00 | Window Closed / Lapsed |