next up previous
Next: vii Compression Examples Up: vi OptimizationBasis Search Previous: vi OptimizationBasis Search

vi-A Cost Functions

In order to produce the basis with the lowest total coding cost, the cost function should indicate the cost of coding each node. One restriction is that the cost function is additive. Coifman and Meyer [CW92] suggested the entropy measure as an appropriate cost function. Ramchandran and Vetterli [RV93] suggested that a rate-distortion additive cost function is more suited to the compression problem. This two-sided measure better matches the goal of finding the optimal rate-distortion point for compression. We assign rate-distortion costs to each node in the graph by quantizing the data using the set of quantizers. This produces a set of rate-distortion points for each node. The procedure for pruning the graph involves both identification of the optimal rate-distortion points and the pruning decisions, and is illustrated in Figure 13. For a detailed description of the algorithm, refer to [RV93]. A brief description follows: the algorithm sweeps through a series of rate-distortion operating points tex2html_wrap_inline1245 , and the least cost quantizer for each node is selected as the one that minimizes tex2html_wrap_inline1247 , see Figure 13(b). Next the least cost embedded graph is found by pruning, and the total rate is compared to the budget, see Figure 13(a). If the total rate exceeds the budget, tex2html_wrap_inline1245 is adjusted and the procedure is repeated.



John R. Smith
[email protected]
http://www.ctr.columbia.edu/~jrsmith
March 6, 1996