Fast piecewise linear approximation of rate-distortion functions for MPEG video
Chun H. Choi, Oscar C. L. Au · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1997
Rate distortion based bit allocation algorithms were previously proposed to yield minimum distortion for a given bit rate in the framework of MPEG. However, they are impractical due to the huge computation required to generate the rate-distortion curve for each image block. In this paper, we propose a fast piecewise linear approximation of the rate distortion function that makes rate-distortion based bit allocation close to practical. By using the proposed fast recursive algorithm to compute selected points on the rate-distortion function and then apply linear interpolation, we show that the computation can be reduced by a factor of approximately 17. Simulation is performed in which rate distortion based bit allocation using bisection approach is applied to an MPEG-1 coder. A significant gain of 1.15dB in PSNR is found to be possible. But the proposed fast algorithm can only achieve a PSNR gain of 0.64dB suggesting that further work is needed.