Quantization and compression of information in a direct acyclic graph
View Patent ↗A technique wherein the number and position of a quantization parameter node is determined in response to the quantization parameters and a preselected error. The size of 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. The scene graph is traversed depth first to establish an order and then traversed in reverse. 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. The maximum degree of acceptable error value is chosen for each quantization type. This error value limits the number of quantization parameter nodes that can be placed in a scene graph.
1. A method for compressing a scene graph in a multimedia presentation, the method comprising:
ordering a plurality of graph nodes in the screen graph in a first direction;
traversing said ordered graph nodes in a second direction, the second direction being a reverse of said first direction, wherein the step of traversing comprises determining, for each traversed ordered graph node that has a successive sibling node lying in the second direction, whether to insert a quantization parameter node immediately following said each traversed ordered node, each quantization parameter node being capable of affecting compression of ordered nodes lying in the first direction from said each quantization parameter node; and
inserting the quantization node between said each traversed ordered graph node and the successive sibling node lying in the second direction in response to the step of determining.
2. The method of compressing according to claim 1 , wherein the step of determining comprises costs of inserting a single quantization parameter node controlling compression of the successive sibling node and of said each traversed ordered graph node to the cost of inserting separate quantization parameter nodes to control compression of the successive sibling node and of said each traversed ordered graph node.
3. The method of compressing according to claim 2 , wherein the step of comparing comprises:
calculating a first cost of inserting a first quantization parameter node between said each traversed ordered graph node and the successive sibling node lying in the second direction, the first quantization parameter node controlling compression of said each traversed ordered graph node;
calculating a second cost of inserting a second quantization parameter node lying immediately adjacent to the successive sibling node in the second direction, the second quantization parameter node controlling compression of the successive sibling node while the first quantization parameter node controls compression of said each traversed ordered graph node; and
calculating a third cost of inserting a third quantization parameter node lying immediately adjacent to the successive sibling node in the second direction, the third quantization parameter node controlling compression of the successive sibling node and of said each traversed ordered graph node.
4. The method of compressing according to claim 3 , wherein the step of comparing further comprises:
summing the first cost and the second cost to obtain a combined cost; and
deciding whether the third cost is greater than the combined cost.
5. A system for compressing a scene graph in a multi-media presentation, the system comprising a memory storing computer instructions and a processor coupled to the memory, the processor being capable of executing the instructions, wherein the instructions, when executed by the processor, cause the processor to perform the following steps:
ordering graph nodes of a plurality of nodes in the scene graph in a first direction to obtain ordered graph nodes;
selecting one or more ranges of quantization values for one or more quantization types of the ordered graph nodes;
traversing the ordered graph nodes in a second direction, the second direction being a reverse of the first direction, wherein the step of traversing comprises determining, for each traversed ordered graph node that has a successive sibling node lying in the second direction, whether to insert a quantization parameter node immediately following said each traversed ordered node, each quantization parameter node being capable of affecting compression of ordered nodes lying in the first direction from said each quantization parameter node; and
inserting the quantization node between said each traversed ordered graph node and the successive sibling node lying in the second direction in response to the step of determining.
6. The system according to claim 5 , wherein the instructions, when executed by the processor, cause the processor, in the course of performing the step of determining, to compare costs of inserting a single quantization parameter node controlling compression of the successive sibling node and of said each traversed ordered graph node to the cost of inserting separate quantization parameter nodes to control compression of the successive sibling node and of said each traversed ordered graph node.
7. The system according to claim 6 , wherein the instructions, when executed by the processor, cause the processor, in the course of performing the step of comparing, to:
calculate a first cost of inserting a first quantization parameter node between said each traversed ordered graph node and the successive sibling node lying in the second direction, the first quantization parameter node controlling compression of said each traversed ordered graph node;
calculate a second cost of inserting a second quantization parameter node lying immediately adjacent to the successive sibling node in the second direction, the second quantization parameter node controlling compression of the successive sibling node while the first quantization parameter node controls compression of said each traversed ordered graph node; and
calculate a third cost of inserting a third quantization node lying immediately adjacent to the successive sibling node in the second direction, the third quantization parameter node controlling compression of the successive sibling node and of each traversed ordered graph node.
8. The system according to claim 7 , wherein the instructions, when executed by the processor, cause the processor, in the course of performing the step of comparing, to:
sum the first and the second cost to obtain a combined cost; and
decide whether the third cost is greater than the combined cost.
9. The system according to claim 8 , wherein the instructions, when executed by the processor, cause the processor to insert the quantization node between said each traversed ordered graph node and the successive sibling node lying in the second direction when the third cost is greater than the combined cost.
10. The system according to claim 9 , wherein the instructions, when executed by the processor, cause the processor, in the course of performing the step of selecting, to select the one or more ranges of quantization values for a quantization type affecting object position.
11. The system according to claim 9 , wherein the instructions, when executed by the processor, cause the processor, in the course of performing the step of selecting, to select the one or more ranges of quantization values for a quantization type affecting object size.
12. The system of claim 9 , wherein the instructions, when executed by the processor, cause the processor, in the course of performing the step of selecting, to select the one or more ranges of quantization values for a quantization type affecting color and intensity.
13. The system according to claim 9 , wherein the instructions, when executed by the processor, cause the processor, in the course of performing the step of selecting, to select the one or more ranges of quantization values for a quantization type affecting scale in transformation.
14. The system according to claim 9 , wherein the instructions, when executed by the processor, cause the processor, in the course of performing the step of selecting, to select the one or more ranges of quantization values for a quantization type affecting angles.