Image analysis – Image compression or coding – Quantization
Reexamination Certificate
2002-08-15
2004-03-23
Couso, Yon J. (Department: 2625)
Image analysis
Image compression or coding
Quantization
C382S240000, C348S405100
Reexamination Certificate
active
06711300
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to compressing information stored in a scene graph used in a multi-media presentation.
2. Related Art
MPEG-4 (Moving Pictures Expert Group) is a digital bit stream format used to broadcast or multicast (“netcast”) multimedia presentations. Elements such as HTML objects, Flash animations, audio/visual streams, Java scripts and similar objects can be included in an MPEG-4 scene. The MPEG-4 scene is constructed as a direct acyclic graph of nodes (also referred to as a scene graph) arranged in a hierarchical tree. Grouping nodes are used to construct the scene structure. Children of grouping nodes are used to represent the various multimedia objects in the scene. These children may also have siblings that such that each sibling is associated with a multimedia object. Each node includes a list of fields that define the particular behavior of the node. Taken together, the nodes in a scene graph represent the layout, presentation, interactions and animation of a multimedia scene.
One problem associated with using scene graphs to store information is that a scene graph for a relatively complex scene is very large. A correspondingly large memory is required to store all the scene graphs in a given presentation. The available bandwidth may not be sufficiently large, thus necessitating uncomfortably long download times.
One approach to solving this problem involves inserting a quantization parameter node at the top of the scene graph (that is, in a position that is relatively proximate to the root node) or at one or more other locations in the graph. A quantization parameter node is a specialized node that shows how scene parameters (such as color, angle, scale, rotation and others) are used to specify an aspect of the scene graph or a portion of the scene graph are to be quantized. However, the degree of compression that results from this approach in not optimal because the locations where the quantization parameter nodes are placed are not responsive to the values being quantized. For example, in very small scenes, the cost (as measured by the number of bits) of specifying quantization parameter may exceed the number of bits saved in the scene by including the quantization parameter node. In very large scenes, the degree of compression may be less than optimal because an insufficient number of quantization parameter nodes have been inserted, such that the quantization parameters include a maximum and minimum quantization range for extremely disparate values. In short, the problem of determining an efficient placement of quantization nodes, particularly with respect to an acceptable error range, remains unsolved.
SUMMARY OF THE INVENTION
In a first aspect of the invention, the size of a scene graph and the corresponding amount of memory required to store the scene graph can be reduced by selective placement of quantization parameter nodes in a scene graph. Unlike the prior art of placing the quantization parameter node at the top of the scene graph or at the top of each subtree, a technique is presented for traversing a scene graph so as to determine the most efficient placement of quantization parameter nodes.
The scene graph is traversed depth first to establish an order and then traversed in reverse order. At each node, a calculation relating to (1) the relative cost of inserting a quantization parameter node, and (2) the relative savings that result from insertion of a quantization node is performed. Quantization parameter nodes are selectively placed in response to a result of these calculations. Locations in the scene graph where subtrees of the graph include clustered values (that is, values that fall within a particular range) are identified and quantization parameters that are responsive to these clustered values are inserted. This selective placement of quantization parameters reduces the size of a scene graph substantially. The scene and all of it's various audio-visual components can be transmitted and presented using less memory because a small range of values is used for each portion of the graph controlled by a particular quantization parameter node.
In a second aspect of the invention, the maximum degree of acceptable error value (designated herein as e
max
) is chosen for each quantization type. This error value limits the number of quantization parameter nodes that can be placed in a scene graph. While the insertion of quantization parameter nodes increases the error, this increase remains less than a preselected maximum acceptable value.
REFERENCES:
patent: 6023296 (2000-02-01), Lee et al.
patent: 6069977 (2000-05-01), Kim et al.
patent: 6084908 (2000-07-01), Chiang et al.
patent: 6351491 (2002-02-01), Lee et al.
patent: 6490627 (2002-12-01), Kalra et al.
Deniau Eric
Fisher Yuval
Signes Julien
Couso Yon J.
Envivio, Inc.
Swernofsky Law Group PC
LandOfFree
Quantization and compression of information in a direct... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Quantization and compression of information in a direct..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantization and compression of information in a direct... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3243841