方塊編碼算法之改進

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

[關(guān)鍵詞]方塊編碼 編碼 像素 圖像 方塊

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

一、引言

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

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

二、改進的方塊編碼算法

（一）傳統(tǒng)方塊編碼算法的改進思路

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

SC={Ci|i=0~n}

Ci=(Pi,Li)

Pi=(Ai,Bi,Ci,Di)

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

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

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

L傳統(tǒng)=C傳統(tǒng)+D傳統(tǒng)

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

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

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

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

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

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

3．如果對應(yīng)于Ci或Di的編碼為000即E子塊的重建電平與各子塊的重建電平均不相同則將需要編碼的重建電平灰度值編碼；

4．將Wi、Ci、Di（或者Wi、Ci、Di、Ei）進行編碼，當(dāng)需要對Ei進行編碼的時候需要按照特定的編碼方式編碼Ei；

5．重復(fù)1～4；

6．最后添加000作為碼流結(jié)束標(biāo)志；

7．對二進制位流按照8位寬度進行切割，形成編碼數(shù)據(jù)流。

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

對經(jīng)過改進的方塊編碼算法編碼壓縮以后的數(shù)據(jù)進行解碼，首先要解碼重建電平和分辨力分量，然后按照子塊對應(yīng)的位置來進行解碼，如果事前約定了灰度值序列還需要解碼成真正的灰度值。

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

1．首先進行碼流分解，獲得SR、Wi、Ci、Di（或者SR、Wi、Ci、Di、Ei）；

2．根據(jù)Ci、Di（或Ci、Di、Ei）的值和表1求對應(yīng)子塊的兩個重建電平，當(dāng)需要使用Ei的時候需；

要按照特定的解碼方法，結(jié)合Ci、Di的值和表1來獲取兩個重建電平；

3．按照對應(yīng)的兩個重建電平和Wi進行解碼，得到解壓圖像對應(yīng)子塊各個像素點的灰度值；

4．重復(fù)進行1～3直到數(shù)據(jù)流結(jié)束。

三、編碼試驗

為了檢驗改進的方塊編碼算法的效果，對國際標(biāo)準(zhǔn)圖LENA圖基于4×4子塊進行了試驗，其壓縮比為4.2（大于傳統(tǒng)方塊編碼算法的壓縮比4），其效果圖像對比如圖2改進的方塊編碼算法實驗圖所示：

四、結(jié)論

實驗證明改進的方塊編碼算法所獲得的壓縮比大于傳統(tǒng)方塊編碼算法所獲得的壓縮比，保留了傳統(tǒng)方塊編碼算法的優(yōu)點，算法簡單、有效，失真率較小。

參考文獻：

[1](美)Rafael C.Gonzalez和Richard E.Woods著，阮秋琦、阮宇智等譯，數(shù)字圖像處理（第二版）[M].北京:電子工業(yè)出版社，2002:15-18.

[2](美)David Salomon（編著），吳樂南等（譯），數(shù)據(jù)壓縮原理與應(yīng)用[M].北京:電子工業(yè)出版社，2003:15-18.

[3]劉國強、錢建生、曹國清編著，多媒體圖像技術(shù)及應(yīng)用[M].北京:人民郵電出版社，2000:15-18.

[4]霍宏濤，數(shù)字圖像處理[M].北京：北京理工大學(xué)出版社，2002:117.

作者簡介：

王曉明，男，遼寧省錦州市人，碩士研究生，研究方向為圖形圖像。