以基因演算法為基礎之適應性非失真影像預測編碼架構

近年來在非失真影像壓縮領域之預測編碼架構上已有許多有效率的演算法被提出；其中最小平方法（Least-Square）是一項被大家廣為應用的方法之ㄧ。整體來說，最小平方法在平緩區域上能有良好的預測能力，在邊界預測上又擁有邊界導向的特性（Edge-oriented characteristic），因此已有學者在EDP演算法中證明，以最小平方法修正預測器係數的方式往往能夠在自然影像上達到很好的壓縮率。但使用最小平方法需建立所謂的normal equations來求取系統的最小平方法解，而此一過程卻需要耗費相當大量的乘法與加法運算。為此，本論文乃嘗試提出一具有低運算複雜度且能維持一定壓縮效能之非失真影像編碼演算法。鑑於基因演算法能夠有系統地求解最佳化之問題，因此在本論文中，我們遂採用基因演算法來取代最小平方法並藉以計算出最佳預測器係數。實驗結果證明，所提出以基因演算法為基礎之適應性預測編碼架構雖然在壓縮率方面與最小平方法相比有些微地退化，但與最小平方法建構normal equations過程的高度複雜度相比較，所提出之基因演算法在求解最佳化係數過程中卻能夠大幅地降低運算複雜度，提高編碼效能。

關鍵字

非失真影像壓縮；預測編碼；基因演算法；最小平方法；邊界偵測

並列摘要

Recently, many predictive coding structures have been proposed for lossless compression of images. Among which, the Least-Square (LS) algorithm has been noted as an efficient approach for the adaptation of predictor coefficients. Due to the inherent edge-oriented characteristic, the LS-adapted predictor has been shown to perform very well not only in slowly-varying areas but also for pixels around boundaries. To find the LS-adapted predictor coefficients, we have to construct the so-called normal equations in a predefined causal area of the coding pixel and then find the LS solution of the equations. However, a large amount of computations is required for the construction of normal equations, and that’s why a pixel-by-pixel LS adaptation process is regarded as prohibitive. For this, we try to propose an efficient algorithm with much lower computational complexity than that of in the LS-adapted approach but still exhibit a very good compression performance. We propose the use of a genetic algorithm (GA) for the adaptation of predictor coefficients so that the computational burden can be alleviated. Experimental results show that the proposed approach can have a very good run time performance with only a minor degradation in prediction results when compared with that of a LS-adapted predictor.

並列關鍵字

Lossless image compression ； predictive coding ； genetic algorithm ； least-square ； edge detection

參考文獻

[5] Pramod Uttamrao Chavan, Pratibha Pramod Chavan, Dr. Yogesh Haribhau Dandawate , “Codebook Optimization in Vector Quantization using Genetic Algorithm,” in Proc. Second Int. conf. Computer and Electrical Engineering, Vol.1, pp. 280-283, Dec. 2009.

[21] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms 3rd ed., The MIT Press, Massachusetts Institute of Technology Cambridge, Massachusetts 02142. [Online] Available: http://mitpress.mit.edu.

[1] X. Wu and N. Memon, “Context-Based, Adaptive, Lossless Image Coding,” IEEE Transaction on Communication, Vol.45, No.4, pp. 437-444, April 1997.

[2] Marcelo J. Weinberger, Gadiel Seroussi, and Guillermo Sapiro, “The LOCO-I Lossless Image Compression Algorithm: Principle and Standardization into JPEG-LS,” IEEE Transaction on Image Processing, Vol.9, No.8, pp. 1309-1324, August 2000.

[3] Charilaos Christopoulos, Joel Askelof, Mathias Larrson, “Efficient Region of Interest Coding Techniques in The Upcoming JPEG2000 Still Image Coding Standard,” in Proc. IEEE Int. Conf. Image Proc. (ICIP 2000), Vol. II, pp. 41-44, Vancouver, Canada, Sep.10-13, 2000.

國際替代計量

以基因演算法為基礎之適應性非失真影像預測編碼架構

全文下載

主題瀏覽