Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
2002-09-05
2004-11-09
Mehta, Bhavesh M. (Department: 2625)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C382S173000, C382S284000, C345S619000, C345S629000
Reexamination Certificate
active
06816619
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the creation of computer-generated images both in the form of still pictures and video imagery, and, in particular, relates to efficient process, apparatus, and system for creating an image made up by compositing multiple components.
BACKGROUND
Computer generated images are typically made up of many differing components or graphical elements which are rendered and composited together to create a final image. In recent times, an “opacity channel” (also known as a “matte”, an “alpha channel”, or simply “opacity”) has been commonly used. The opacity channel contains information regarding the transparent nature of each element. The opacity channel is stored alongside each instance of a colour, so that, for example, a pixel-based image with opacity stores an opacity value as part of the representation of each pixel. An element without explicit opacity channel information is typically understood to be fully opaque within some defined bounds of the element, and assumed to be completely transparent outside those bounds.
An expression tree offers a systematic means for representating an image in terms of its constituent elements and which facilitates later rendering. Expression trees typically comprise a plurality of nodes including leaf nodes, unary nodes and binary nodes. Nodes of higher degree, or of alternative definition may also be used. A leaf node, being the outer most node of an expression tree, has no descendent nodes and represents a primitive constituent of an image. Unary nodes represent an operation which modifies the pixel data coming out of the part of the tree below the unary operator. Unary nodes include such operations as colour conversions, convolutions (blurring etc) and operations such as red-eye removal. A binary node typically branches to left and right subtrees, wherein each subtree is itself an expression tree comprising at least one leaf node. Binary nodes represent an operation which combines the pixel data of its two children to form a single result. For example, a binary node may be one of the standard “compositing operators” such as OVER, IN, OUT, ATOP and alpha-XOR, examples of which and other are seen in FIG.
20
.
Several of the above types of nodes may be combined to form a compositing tree. An example of this is shown in FIG.
1
. The result of the left-hand side of the compositing tree may be interpreted as a colour converted image being clipped to spline boundaries. This construct is composited with a second image.
Although the non-transparent area of a graphical element may of itself be of a certain size, it need not be entirely visible in a final image, or only a portion of the element may have an effect on the final image. For example, assume an image of a certain size is to be displayed on a display. If the image is positioned so that only the top left corner of the image is displayed by the display device, the remainder of the image is not displayed. The final image as displayed on the display device thus comprises the visible portion of the image, and the invisible portion in such a case need not be rendered.
Another way in which only a portion of an element may have an effect is when the portion is obscured by another element. For example, a final image to be displayed (or rendered) may comprise one or more opaque graphical elements, some of which obscure other graphical elements. Hence, the obscured elements have no effect on the final image.
A conventional compositing model considers each node to be conceptually infinite in extent. Therefore, to construct the final image, a conventional system would apply a compositing equation at every pixel of the output image. Interactive frame rates of the order greater than 15 frames per second can be achieved by relatively brute-force approaches in most current systems, because the actual pixel operations are quite simple and can be highly optimised. This highly optimised code is fast enough to produce acceptable frame rates without requiring complex code. However, this is certainly not true in a compositing environment.
The per-pixel cost of compositing is quite high. This is because typically an image is rendered in 24-bit colour in addition to an 8-bit alpha channel, thus giving 32 bits per pixel. Each compositing operator has to deal with each of the four channels. Therefore, the approach of completely generating every pixel of every required frame when needed is inefficient, because the per-pixel cost is too high.
Problems arise with prior art methods when rendering graphical objects which include transparent and partially-transparent areas. Further, such methods typically do not handle the full range of compositing operators.
SUMMARY OF THE INVENTION
It is an object of the present invention to substantially overcome, or ameliorate, one or more of the deficiencies of the above mentioned methods by the provision of a method for creating an image made up by compositing multiple components.
According to one aspect of the present invention there is provided a method of creating an image, said image being formed by rendering at least a plurality of graphical objects to be composited according to a compositing expression, each said object having a predetermined outline, said method comprising the steps of:
dividing a space in which said outlines are defined into a plurality of mutually exclusive regions wherein each of said regions is defined by a region outline substantially following at least one of said predetermined outlines or parts thereof;
examining each said region to determine those said objects which contribute to said region;
modifying said compositing expression on the basis of the contribution of each of said objects within said region to form an optimized compositing expression for each said region; and
compositing said image using each of said optimized compositing expressions.
According to another aspect of the present invention there is provided a method of creating an image, said image being formed by rendering at least a plurality of graphical objects to be composited according to a compositing expression, each said object having a predetermined outline, said method comprising the steps of:
dividing a space in which said outlines are defined into a plurality of mutually exclusive regions;
examining each said region to determine those said objects which contribute to said region;
modifying said compositing expression on the basis of the contribution of each of said objects within said region; and
compositing said image using said modified compositing expression.
According to still another aspect of the present invention there is provided a method of creating an image, said image comprising a plurality of graphical objects to be composited according to a compositing expression, said method comprising the steps of:
dividing a space in which said graphical objects are defined into a plurality of regions;
examining each said region to determine those said objects which contribute to said region;
modifying said compositing expression on the basis of said examination; and
compositing said image using said modified compositing expression.
According to still another aspect of the present invention there is provided an apparatus for creating an image, said image being formed by rendering at least a plurality of graphical objects to be composited according to a compositing expression, each said object having a predetermined outline, said apparatus comprising:
dividing means for dividing a space in which said outlines are defined into a plurality of mutually exclusive regions wherein each of said regions is defined by a region outline substantially following at least one of said predetermined outlines or parts thereof;
examining means for examining each said region to determine those said objects which contribute to said region;
modifying means for modifying said compositing expression on the basis of the contribution of each of said objects within said region to form an optimized compositing expression for each said region; and
compositi
Long Timothy Merrick
Tlaskal Martin Paul
Canon Kabushiki Kaisha
Fitzpatrick ,Cella, Harper & Scinto
Mehta Bhavesh M.
Patel Kanji
LandOfFree
Optimising image compositing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimising image compositing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimising image compositing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3346200