方塊編碼算法之改進

2009-06-05 03:59:50王曉明

新媒體研究 2009年9期

[摘要]利用傳統方塊編碼算法編碼壓縮灰度圖像，算法簡單、失真率不大，卻因為其方法比較固定而導致了其壓縮比較小，伸縮度往往不大，在一些情況下不適合被利用來壓縮圖像。為了改變傳統方塊編碼算法編碼壓縮灰度圖像壓縮比之不足，對傳統方塊編碼算法作出改進以提高壓縮比。實驗證明在對一般圖像進行方塊編碼的時候，改進以后所獲得的算法有效。

[關鍵詞]方塊編碼編碼像素圖像方塊

中圖分類號：TP3文獻標識碼：A文章編號：1671－7597（2009）0510034－02

一、引言

方塊編碼算法是一種傳統的編碼壓縮算法，它簡單、有效，失真率較小，其基本思想是將圖像分成n×n的子塊（通常是4×4的子塊），并為每個子塊設計兩個電平量化器，量化門限和兩個重建電平隨子塊局部統計特征而變化，量化后用一個n×n位的映像矩陣表示，這n×n位代表了有關各個像素的重建電平和確定兩個重建電平的附加信息（分辨力分量）。譯碼時在各個像素點的映像位置選擇一個合適的重建電平完成譯碼。

傳統方塊編碼算法利用分辨力分量和兩個重建電平來進行編碼壓縮，當子塊的大小和原圖像大小確定以后，壓縮比就已經確定了，由于傳統方塊編碼算法兩個重建電平的編碼沒有充分考慮到相鄰子塊之間的關系和視覺冗余，因此其所需的編碼就較多，方塊編碼所實現的壓縮比也因此受到了限制，往往不大。

二、改進的方塊編碼算法

（一）傳統方塊編碼算法的改進思路

使用傳統方塊編碼算法編碼時所選的方塊區域的大小固定，利用固定的位數來記錄重建電平和分辨力分量，絲毫沒有考慮到相鄰方塊區域的聯系，絲毫沒有考慮到灰度值相差不多而且分布極其不均勻的現象，一切都導致了傳統方塊編碼算法所實現的壓縮比小而且固定，雖然我們不容易找到更好的記錄方式來記錄分辨力分量從而增大壓縮比，但是如果能夠充分考慮到相鄰方塊的相關性利用可變位數的方式記錄重建電平使記錄時使用的代碼更少則必然可以提高壓縮比。同時通過對經過傳統方塊編碼算法編碼壓縮后的數據進行分析和研究，我們可以發現即使經過傳統方塊編碼算法編碼壓縮以后圖像數據依然存在一定程度的像素間冗余和心理視覺冗余，那么我們完全可以利用灰度值序列編碼壓縮灰度值信息，也可以使用相鄰方塊重建電平替代相應子塊重建電平的方式來編碼灰度值從而減少編碼時所需要的數據量，只要失真率不大不至于影響視覺感受即可。

我們按照圖1所示設A、B、C、D、E、F、G、H、I為一副圖像中將要進行方塊編碼的相鄰區域局部各子塊，因為方塊編碼算法的子塊往往不大（一般情況下小于4×4），其各子塊之間的重建電平往往存在一定的相關性。則在很多情況下我們可以利用A、B、D三個子塊的重建電平來推測E子塊的重建電平，可以用A、B、D三個子塊的重建電平來替代E子塊的重建電平，同理其余子塊的重建電平也可以用其周圍的三個相鄰子塊的重建電平來替代。鑒于每個子塊的編碼要記錄兩個重建電平而且圖像本身也有自身的規律，相應子塊的重建電平可能與周圍三個相鄰子塊的六個重建電平（每個子塊都有兩個重建電平）中的一個重建電平相關，也可能與這六個重建電平都不相關，另外對應子塊的兩個重建電平都要與周圍三個子塊的六個重建電平依次對比，并且按照灰度值高和灰度值低的順序依次對子塊的重建電平進行編碼。考慮到在圖像中普遍存在的像素間冗余和心理視覺冗余以及方塊編碼的特點，可以在編碼端與解碼端事前規定好一組灰度值序列，當編碼端遇到重建電平的灰度值的時候如果不能利用相鄰子塊的重建電平替代則可以利用灰度序列中的值替代，解碼時再在解碼端解碼灰度值即可。

使用灰度值序列編碼灰度值的算法可以按照如下的思路進行：

假設通過圖像獲得的灰度值序列為COlOR,COLOR為一個256位的二進制數序列，每一位對應一個灰度值，例如第一位對應的灰度值為0，如果圖像中存在灰度值為0的像素，則第一位編碼為1否則編碼為0；第二位對應的灰度值為1，如果存在灰度值為1的像素則該位編碼為1否則為0，……以此類推。編碼的時候不按照實際的灰度值進行編碼而是按照灰度值在圖像中存在像素的灰度值的位置進行編碼，例如假設COLOR=000001111100000111110 0000111110000011111000001111100000111110000011111000001111100000111110000011111 000001111100000111110000011111000001111100000111110000011111000001111 10000011111000001111100000111110000011111000001111100000111110000011 1110000011111111111，灰度值為6則首先找到代表灰度值為6的數據位上的“1”是灰度值序列COLOR中的第幾個“1”，因為是第2個“1”，所以該灰度值按照2進行編碼。同理假設解碼端獲得的對應于灰度值的數據是6，則需要按照灰度值序列COLOR查找第6個“1”在灰度值序列COLOR中的相應位置，因為第6個“1”在第16個位置上，因此其實際灰度值是15。

在具體操作上，按照灰度值序列編碼灰度值的編碼算法可以按照如下方法進行操作：

1．首先獲得灰度值序列；

2．根據灰度值找到灰度值在灰度值序列中的實際存在像素的相對位置；

3．按照灰度值在灰度值序列中的實際存在像素的相對位置編碼灰度值。

在具體操作上，按照灰度值序列編碼灰度值的解碼算法可以按照如下方法進行操作：

1．首先獲得灰度值序列；

2．按照灰度值在灰度值序列中的實際存在像素的相對位置找到相應的灰度值位置；

3．按照絕對的灰度值位置-1解碼灰度值。

按照圖像獲得灰度值序列的方法要求在編碼端與解碼端之間有一個長達256位的編碼頭來表達圖像中存在的灰度值。而使用相鄰區域方塊重建電平替代相應方塊重建電平的方法編碼重建電平以后再用灰度值序列替代的方法來記錄灰度值所獲得的壓縮比往往不會大幅度提高卻會提高解碼算法的復雜度，因此利用灰度值序列編碼灰度值的算法只是在一些特定情況下使用，本文主要探討使用相鄰方塊重建電平替代的方式，灰度值序列編碼只是作為補充和輔助。

因為改進的方塊編碼算法只是對記錄方法進行了改進，同時即使應該記錄的灰度值有了改變也是在灰度值相差不大的前提下進行的，其失真率實際上不大，也不至于影響視覺效果，所以傳統方塊編碼算法原有的優點得以保留，同時由于減少了重建電平平均占有的位數則必然可以提高壓縮比。

（二）改進的方塊編碼算法算法描述

改進的方塊編碼算法可以描述如下：

SC={Ci|i=0~n}

Ci=(Pi,Li)

Pi=(Ai,Bi,Ci,Di)

其中SC為某個數據流的所有編碼集合，Ci為第i個編碼，對應于圖像中第i個子塊的編碼數據。Pi為表示第i個子塊重建電平的數據，位寬根據實際的需要而定。Ai為表示圖像中第i個子塊的重建電平中灰度值較高的重建電平與第i個子塊周圍的三個子塊的重建電平的替代關系，Bi為表示第i個子塊的重建電平中灰度值較低的重建電平與第i個子塊周圍的三個子塊的重建電平的替代關系，Ci為當第i個子塊的重建電平中灰度值較高的重建電平不能從周圍子塊的重建電平推測時記錄的灰度值較高的重建電平數據，Di為當第i個子塊的重建電平中灰度值較低的重建電平不能從周圍子塊的重建電平推測時記錄的灰度值較低的重建電平數據。每個Pi都有一個Ai 和一個Bi與之對應，當第i個子塊的重建電平中灰度值較高的重建電平可以從周圍子塊的重建電平推測時沒有Ci，當第i個子塊的重建電平中灰度值較低的重建電平可以從周圍子塊的重建電平推測時沒有Di。Li為表示第i個子塊分辨力分量的數據，位寬固定。

在不考慮灰度級深度壓縮和灰度值序列編碼灰度值的編碼過程中，記錄改進方塊編碼算法的重建電平的數據量由表示替代的信息總量和不能替代時所需要記錄的重建電平的數據總量決定，記錄傳統方塊編碼算法重建電平的數據量由實際記錄重建電平的數據量決定，則設L改進為改進的方塊編碼算法記錄重建電平所需要的總數據量，L傳統為傳統的方塊編碼算法記錄重建電平所需要的總數據量，A改進和B改進為表示子塊重建電平與周圍子塊重建電平關系的總數據量，C改進和D改進為表示無法通過相鄰子塊重建電平推測子塊重建電平時所需要記錄的數據量，C傳統和D傳統為傳統方塊編碼算法記錄重建電平的總數據量，則

L改進=A改進+B改進+C改進+D改進

L傳統=C傳統+D傳統

鑒于方塊編碼算法記錄分辨力分量的數據量是固定的，通過L改進和L傳統的對比可以知道A改進+B改進>C傳統+D傳統-C改進-D改進時改進方塊編碼算法必然憂于傳統方塊編碼算法。

（三）改進的方塊編碼算法的編碼過程

對圖像利用改進的方塊編碼算法進行編碼與利用傳統方塊編碼算法編碼圖像非常類似，區別主要是在重建電平的編碼上，改進的方塊編碼可以事前約定采用的灰度值，需要參考各相鄰子塊的重建電平編碼重建電平。設有將要進行改進的方塊編碼算法編碼的二進制流SC，SC={Bi|i=0～n},SC為圖像中各個像素點的數據集合，Bi對應于單個像素點的灰度值，SR={Wi,Ci,Di| i=0～n }/{Wi,Ci,Di,Ei| i=0～n },SR為一個子塊進行改進的方塊編碼算法編碼后獲得的對應于單個子塊的編碼集合，Wi為對應子塊的分辨力分量的數據，Ci為對應子塊重建電平中灰度值高的重建電平與相鄰子塊重建電平的對比結果編碼，Di為對應子塊重建電平中灰度值低的重建電平與相鄰子塊重建電平的對比結果編碼，Ei為對比不符時所需要記錄的重建電平的編碼，一個對應子塊只對應SR中的一個元素。

改進的方塊編碼算法的編碼過程如下：

1．按照傳統方塊編碼算法的方式獲得子塊的兩個重建電平和分辨力分量；

2．將非邊緣子塊的兩個重建電平與其各緊鄰子塊的兩個重建電平進行比較，并按照表1相鄰方塊區域重建電平關系表所表示的各種情況得出Ci、Di（以圖1中的E塊為例，具體請參考圖1）；