The quadtree data structure is commonly used in image coding to decompose an image into separate spatial regions to adaptively identify the type of quantizer used in various regions of an image. The authors describe the theory needed to construct quadtree data structures that optimally allocate rate, given a set of quantizers. A Lagrange multiplier method finds these optimal rate allocations with no monotonicity restrictions. They use the theory to derive a new quadtree construction method that uses a stepwise search to find the overall optimal quadtree structure. The search can be driven with either actual measured quantizer performance or ensemble average predicted performance. They apply this theory to the design of a motion compensated interframe video coding system using a quadtree with vector quantization.

Discusses the design of a CMOS integrated circuit for real time vector quantization (VQ) of images at MPEG rates. It has been designed as a slave processor which can implement binary, non-binary, and pruned tree search VQ algorithms. Inputs include the image source vectors, the VQ codevectors and external control signals that direct the search. The chip outputs the index of the codevector that best approximates the input in a mean square error sense. The layout has been generated using a 1.2 mu CMOS library and measures 5.76*6.6 mm/sup 2/. Critical path simulation with SPICE indicates a maximum clock rate of 40 MHz.>

An architecture for implementing pruned tree search vector quantization (VQ) which has a performance close to the optimal rate distortion bound is presented. A layout design is also presented to verify the feasibility of such an implementation. The chip has been designed as a slave processor which can implement binary, non-binary and pruned tree search VQ algorithms which allow near optimal performance in a mean square error sense while still permitting real time VQ codevectors and external control signals that direct the search. The chip outputs the index of the codevector that best approximates the input in a mean square error sense. The input source and codevectors have a wordlength of 8 bits each. An internal wordlength of 24 bits allows a maximum of 256 pixels per vector. The layout has been generated using a 1.2- mu library and is 5.76 mm*6.6 mm. Critical path simulation with SPICE indicates a maximum clock rate of 40 MHz.>

A new algorithm is proposed for the generation of rate-distortion optimized tree-structures used in source coding. The algorithm solves a more general problem than that assumed for a previous method by P.A. Chou et al. (1989). It arises when the tree structure is to be optimized with a multi-way decision made at each leaf node. The simplifying assumption that the three structure performance functions are monotone with respect to the level of nodes in the tree is also removed. Two applications of the more general problem in image/video compression are quadtree coding with vector quantization and variable block-size motion compensation. This new method is not a pruning algorithm, as the optimal trees may not be nested. The new algorithm finds the global optimal tree structure and node decisions in the unconstrained rate allocation sense.>

The design of an encoder for pruned tree-search vector quantization (VQ) is discussed. This allows near-optimal performance in a mean square error sense while keeping the hardware complexity low. The encoder is partitioned into a slave processor chip that computes the distance and performs minimizations and an off-chip controller that directs the search. Pointer addressing is exploited in the codebook memory to keep the controller hardware simple. Inputs to the slave processor include the source vectors, the code vectors; and external control signals. The slave processor outputs the index of the code vector that best approximates the input in a mean square error sense. The layout for the slave processor has been generated using a 1.2- mu m CMOS library and measures 5.76*6.6 mm/sup 2/. Critical path simulation with SPICE indicates a throughput of 89 million multiply-accumulates per second. This implies that real-time processing at MPEG rates can be achieved if the number of levels (N7) and the number of children at any node (M) obey the constraint M*N>

A pruning algorithm of P.A. Chou et al. (1989) for designing optimal tree structures identifies only those codebooks which lie on the convex hull of the original codebook's operational distortion rate function. The authors introduce a modified version of the original algorithm, which identifies a large number of codebooks having minimum average distortion, under the constraint that, in each step, only modes having no descendents are removed from the tree. All codebooks generated by the original algorithm are also generated by this algorithm. The new algorithm generates a much larger number of codebooks in the middle- and low-rate regions. The additional codebooks permit operation near the codebook's operational distortion rate function without time sharing by choosing from the increased number of available bit rates. Despite the statistical mismatch which occurs when coding data outside the training sequence, these pruned codebooks retain their performance advantage over full search vector quantizers (VQs) for a large range of rates.

The generalized BFOS (G-BFOS), a sequential pruning algorithm for designing optimal tree structures, was presented by Chou, Lookabaugh, and Gray (see IEEE Trans. Inf. Theory, vol.35, no.2, p.299, 1989), and it was applied to tree-structured vector quantizers (TSVQ). G-BFOS yields VQ codebooks that often outperform conventional generalized Lloyd full search codebooks having the same rate and block size. The authors have developed a modified version of G-BFOS, called the recursive optimal pruning algorithm (ROPA), which recursively searches for the nodes to be pruned next. The sequence of these pruned codebooks includes the original optimal G-BFOS codebooks and many additional ones. The optimality of these codebooks is described, and simulations evaluate their performance.>

The authors describe the theory needed to construct quadtree data structures which optimally allocate rate, given a set of quantizers. A Lagrange multiplier method finds these optimal rate allocations with no monotonicity restrictions. The theory is used to derive a new quadtree construction method which uses a stepwise search to find the overall optimal quadtree structure. The search can be driven with either actual measured quantizer performance or ensemble average predicted performance. This theory is then applied to the design of an interframe hybrid video coding system using a quadtree with vector quantization.>

A new class of motion compensation methods that are based on control grid interpolation (CGI) for use in video compression is described. The predominant motion compensation method, block matching, is shown to be a special case of CGI. A new CGI method is presented that produces a smooth motion vector field, preserving continuity and connectivity in the prediction image. When contrasted with block matching, the new algorithm eliminates blocking artifacts while using the same or less side information for approximately the same mean square error. Search algorithms and coding methods developed previously for block matching can be used with this new technique.>

An algorithm is presented for estimating and compensating camera zooms and pans. It models the global motion in each frame with just two parameters: a zoom factor and a two-dimensional pan vector both based on local displacement vectors found by conventional means (such as block matching). Since motion by objects in the scene obscures global motion, the algorithm can iterate to refine its estimate. Simulations suggest the algorithm is robust and accurate, and can significantly reduce both the energy of the motion compensated residual image as well as the zeroth-order entropy of the local displacement vector field.>

The authors develop the optimum bit allocations for fixed rate (minimum distortion) and fixed distortion (minimum rate) hierarchical Laplacian pyramid image coding structures, using scalar quantizers that have negative exponential quantizer functions. The optimum MSE (mean square error) bit allocation is shown to agree closely with P.J. Burt and E.H. Adelson's (IEEE Trans. Acoust., Speech and Signal Proc., vol. ASSP-34, p.1278-88, Oct. 1987) empirically derived and perceptually based allocation. The slope of the distortion-rate function is found to vary with the number of levels, N, in the pyramid, becoming worse as N increases. It is also shown that since the amount of compression is a function of the distribution of energies among the Laplacian images, performance is strongly affected by the quality of the filters. The analysis permits comparison with other important schemes, such as subband coding, from a distortion-rate perspective.>

A subband image codec is presented that approximately attains a user-prescribed fidelity by allowing the encoder's compression rate to vary. The fixed distortion subband coding (FDSBC) system is suitable for use with future of packet-switched networks. The codec's design is based on an algorithm that allocates distortion among the subbands to minimize channel entropy. By coupling this allocation procedure with judiciously selected subband quantizers, an elementary four-band codec was obtained. Additional four-band structures may be nested in a hierarchical configuration for improved performance. Each of the configurations tested attains mean square distortions within 2.0 dB of the user-specific value over a wide range of distortion for several standard test images. Rate versus mean-square distortion performance rivals that of fixed-rate systems having similar complexity. The encoder's output is formatted to take advantage of prioritized packet networks. Simulations show that FDSBC is robust with respect to packet loss and may be used effectively for progressive transmission applications.>

It is shown that motion compensated vector quantizer (MCVQ) performance can be improved by inserting spatial filters within the MCVQs prediction loop. The degree of improvement depends on the type of filter applied. Median filtering is poorly matched to the MCVQ noise process and does not work well. Gaussian filters do a much better job of cleaning foreground regions; peak SNR improves from 1 to 3 dB, with an average of about 1.5 dB. Edge rendition can be further improved by using an adaptive space-variant filter that smooths in a direction parallel to strong edges. The rate increases slightly to communicate edge orientations, but this information can be used to upgrade the VQ to a classified VQ structure.>

A finite-state vector quantizer (VQ) suitable for both intraframe and interframe coding is presented. Interblock and interframe memory is expressed through a state variable driven by an improved classifier which keys on the intensity gradients of a block's neighbours and its own interframe motion. A bilinear interpolator reduces the energy of foreground residuals encoded by the quantization, improving edge rendition and limiting blocking artifacts. Background blocks are vector predictive coded using simple frame differencing and codebooks built with a gradient design algorithm. The codec at 0.4 bit/pixel outperforms a similar but non-finite-state intraframe VQ at 1.0 bit/pixel by 4 dB.>

Vector quantization (VQ) is an effective spatial domain image coding technique at under 1.0 bits per pixel (bpp). Its performance can be improved by incorporating block-to-block memory. Finite State VQs (FSVQ) do this by using a state variable to express characteristics of neighboring blocks and identify which subset of a supercodebook the FSVQ encoder and decoder are to use for the current vector. This paper describes a new method for image sequence coding that uses an interframe FSVQ In the spatial domain. Block-to-block and frame-to-frame memory is expressed through a state which is a function of block motion and the intensity gradients of a block's neighbors. A scalar predictor adds additional interframe memory and reduces the energy of residuals encoded by the VQ, improving edge rendition and limiting blocking artifacts. The codec at 0.6 bpp outperforms a similar, non-finite state intraframe VQ at 1.0 bpp. No motion compensation or conditional replenishment is used.