EE368B - Image and Video Compression

Suggested Topics for Image Coding

1. Influence of scan order on efficiency of predictive coding

   Predictive image coding requires the ordering of the pixels prior to encoding. Only previously encoded and transmitted pixels can be used for predicting the current one. Investigate the influence of difference orderings on the efficiency of a predictive coder for still images. Your orderings might include

   • line by line scan
   • multiple passes through the image with increasing sampling density (resolution pyramid)
   • space filling Peano curves (Hilbert scans)
   This might be a nice project for an individual student or a two-student team.

2. Energy compaction by orthonormal transforms

   Implement the orthonormal transforms that were mentioned in class (DCT, DFT, Slant, Walsh-Hadamard, Haar) and experimentally compare their energy compaction for a block size of 8x8. Compare this energy compaction to the energy compaction achieved by the Karhunen-Loeve transform.

3. Influence of DCT blocksize on coding efficiency

   Investigate the influence of the block size of a discrete cosine transform on the coding gain associated with the transform. Develop a theoretical model that explains the results you measured.

4. Lapped orthogonal transform

   Implement a still coder utilizing the Lapped Orthogonal Transform (LOT, H. Malvar, D. Staelin), and compare its performance to a DCT coder.

5. Sub-band pyramid encoder

   Implement a critically sampled sub-band pyramid coder for still images. Design and implement scalar quantizers followed by variable length coding. Compare the rate-distortion performance of the coder for

   • memoryless encoding of the sub-band coefficients
   • run-length encoding of zeros in the sub-bands
   • Shapiro's zero-tree encoding
   This is a bigger project, you can't do it alone.

6. Critically sampled vs. over-complete pyramids

   Implement a critically sampled sub-band pyramid coder for still images and an over-complete pyramid coder. Optimize scalar quantizers (or maybe vector quantizers) for each scheme, as well as entropy codes and bit allocation. Measure rate distortion performance for each scheme and compare their efficiency and computational requirements. This is a bigger project, you can't do it alone.

7. Pyramid coder with nonlinear prediction

   Simulate the classical Burt/Adelson pyramid coder and improve upon its compression performance by optimizing the filter kernels. Further optimize its performance by using nonlinear prediction from one resolution level to the next.

8. Block truncation coding

   Implement block truncation coding, as first introduced by E. Delp and later improved by others, and compare its rate distortion performance and its computational requirements with a mean-gain-shape vector quantizer using the same block size.

9. Stereo image compression

   Design an algorithm for jointly encoding stereo images of a scene and compare its rate distortion performance to independent encoding of the two views. We got two stereo sequences in the ISE lab directory /usr/local/class/ee392c/seqs/mpeg4: tunnel_l and tunnel_r as well as fun_fa_l and fun_fa_r

10. Perceptual Distortion Metrics for JPEG Images

    Implement a perceptual model for assessing image quality and compare its performance with MSE on still images compressed with JPEG. For a survey of perceptual distortion metrics, see A. Ahumada, Jr., "Computational Image Quality Metrics: A Review", Society for Information Display International Symposium, Digest of Technical Papers, 24, 305-308 (1993).

11. Classified Compression

    Improved compression can often be obtained by using different codes locally in an image to code distinct types, such as background (uniform or textured), text, graphics, etc. Explore what has been done and consider a variation or two. What shapes of segmented regions are allowed has a strong impact on complexity. An example for classified compression applied to medical images can be found in Perlmutter, K.O. et al. "Wavelet/TSVQ image coding with segmentation", Conference Record of The Twenty-Ninth Asilomar Conference on Signals, Systems and Computers (1996) p. 494-8 vol.1.

Suggested Topics for Motion Coding

1. Motion-compensated interpolation

   Design and implement a motion-compensated algorithm to interpolate additional frames that are temporally between two successive frames of a motion video sequence.

2. Search strategies for block matching

   Compare the prediction error variance achieved by motion-compensated prediction using block matching with different search strategies. Include

   • full-search
   • 2D coarse-to-fine search
   • conjugate direction search
   in your experiments. Also, compare the computation required for each method. Carry out the experiments for integer-pel, half-pel, and quarter-pel accuracy of motion compensation using bilinear interpolation for sub-pel positions. This is a bigger project, you can't do it alone.

3. Rate-constrained change detection

   For conditional replenishment video coding algorithms, typically a change detection mask is transmitted as side information in addition to the signal within the changed areas. The change detector should therefore achieve the best performance without exceeding a certain bit-rate available for encoding the change detection mask. Implement an efficient compression scheme to transmit the change detection mask and, based on this compression scheme, develop an algorithm for rate constrained change detection. Shape coding schemes as proposed for the MPEG-4 standard might be good candidates for encoding the change detector mask. This is a bigger project, you can't do it alone.

4. Rate-constrained motion estimation

   For motion-compensated video coding algorithms, typically the displacement vector field is transmitted in addition to the motion-compensated prediction error residual. Hence, the motion-compensated predictor has to achieve the best performance without exceeding a certain bit-rate available for the displacement vector field. Design an efficient compression scheme to transmit the displacement vector field and, based on this compression scheme, develop an algorithm for rate constrained motion estimation. Use a Lagrangian formulation J = D + lambda*R to replace the constrained optimization problem by an unconstrained problem. This is a bigger project, you can't do it alone.

5. Variable Shape and Size Motion Compensation

   To improve the rate-distortion efficiency of motion compensation segments of variable shape and size are being exploited, expressed in extensive studies in quad-tree and region-based coding. Implement motion estimation and compensation using segments of variable sizes and shapes. The sizes should be 16x16 (max) down to 8x8 (min). The shapes may be quadratic or rectangular blocks, triangles, or other kinds of space filling shapes. Evaluate prediction performance. This is a bigger project, you can't do it alone.

6. Multihypothesis disparity estimation for light field compression

   A light field is an array of images taken from a static 3-D scene. The images are taken from different angles such that a disparity is prevalent in neighboring images. Use multihypothesis disparity compensation to predict a light field image from neighboring images. Investigate averaging of disparity compensated images when the disparities are estimated independently and jointly. Examine the average prediction quality vs. the average bit-rate spent to predict a light field image for the investigated approaches.