一種基于自適應(yīng)分塊八叉樹顏色量化的圖像壓縮技術(shù)*

吳振華,沈虎峻,2,公佐權(quán),馮平,龔?fù)G,3,鄧明森

(1.貴州財經(jīng)大學(xué)信息學(xué)院，貴州 貴陽 550025; 2.貴州師范學(xué)院貴州省納米材料模擬與計算重點實驗室，貴州 貴陽 550018; 3.中國科學(xué)院計算研究所計算機體系結(jié)構(gòu)國家重點實驗室，北京 100180)

1 引言

隨著信息時代逐漸演變?yōu)閿?shù)字時代，基于計算機的多媒體技術(shù)的發(fā)展引起了許多研究者的極大關(guān)注。數(shù)字圖像信息作為最重要的信息之一，在我們的日常生活中越來越廣泛和頻繁地被使用。因為高分辨率的圖像需要占用大量的存儲空間，因此改進圖像數(shù)據(jù)的壓縮技術(shù)對于多媒體行業(yè)來說變得非常迫切和必要[1 - 3]。

眾所周知，圖像中的任何顏色都可以通過幾種特定的原色組合生成，例如紅色、綠色和藍色(RGB)。對于常見的圖像，每個顏色分量由0～255的數(shù)字表示，對應(yīng)于1個字節(jié)。因此，RGB圖像的文件大小(分辨率為M×N)至少為M×N×3個字節(jié)，而帶Alpha通道的RGB(ARGB)圖像文件大小至少為M×N×4個字節(jié)。圖像壓縮技術(shù)的關(guān)鍵問題是，如何在保證圖像質(zhì)量的前提下有效地壓縮圖像數(shù)據(jù)，以及如何在顏色損失最低的前提下有效地恢復(fù)原始圖像。

在圖像壓縮技術(shù)中，由于顏色量化CQ(Color Quantization)技術(shù)可以很容易地實現(xiàn)圖像壓縮，有效地減少圖像存儲空間，已經(jīng)被廣泛使用。為了重建具有最小色彩損失的壓縮圖像并減少人眼可以檢測到的視覺差異，人們已經(jīng)提出了各種基于CQ的算法。這些算法包括神經(jīng)網(wǎng)絡(luò)[4]、中值切割算法[5,6]、RWM切割算法[7]、k-均值算法[8 - 12]、中位分割算法[13]、模糊C均值算法[14 - 16]、基于DWT的聚類算法[17]等。然而，由于色彩空間的選擇、圖像內(nèi)容的差異等方面的影響，目前還沒有一種萬能的方法適應(yīng)所有的顏色量化，都或多或少地存在一些缺陷。八叉樹顏色量化OCQ(Octree Color Quantization)算法最初由Gervautz等人[18]提出。與其他CQ算法相比，該算法量化后的圖像效果層次豐富，并且時間和空間上的消耗很低。此外，OCQ算法使用了調(diào)色板技術(shù)，可以在常數(shù)時間內(nèi)通過調(diào)色板直接訪問每個像素數(shù)據(jù)，而這種特征是其他圖像壓縮算法如離散余弦變換(典型代表是JPEG文件[19])、小波變換(典型代表是JPEG2000文件[20])、字典壓縮(典型代表是PNG文件使用的LZ77[21]派生算法壓縮)等所不具備的，因為這些算法需要經(jīng)過復(fù)雜的解碼恢復(fù)所有原始數(shù)據(jù)后，才能隨機訪問任意像素。因此，OCQ使用的調(diào)色板技術(shù)可以在圖像壓縮狀態(tài)下隨機訪問圖像中的數(shù)據(jù)，該特性能讓應(yīng)用程序在有限的內(nèi)存資源下容納更多的壓縮圖像數(shù)據(jù)，也保證應(yīng)用程序能高效率地對壓縮圖像數(shù)據(jù)做隨機訪問。實際上，有很多的場合需要這種特性，譬如繪制帶有大量圖片的Web頁面、畫面豐富絢麗的電腦游戲軟件等等。然而，由于傳統(tǒng)OCQ算法的限制，處理后的圖像細節(jié)已經(jīng)不能滿足多媒體行業(yè)日益增長的需求。

因此，本文提出了一種自適應(yīng)分塊八叉樹顏色量化AB-OCQ(Adaptive Block Octree Color Quantization)算法來提高圖像質(zhì)量。其中，自適應(yīng)分塊量化用于提高圖像的局部細節(jié)質(zhì)量，在保留OCQ優(yōu)勢的前提下，有效地解決了OCQ算法所面臨的問題。

2 AB-OCQ算法介紹

傳統(tǒng)的OCQ算法僅支持RGB 3個顏色通道，由于每個顏色通道的每1位有0或1 2種狀態(tài)，因此傳統(tǒng)的OCQ算法需要23=8個分支來存儲每個節(jié)點上的顏色狀態(tài)。為了支持帶Alpha通道圖像的顏色量化，我們把八叉樹擴展為24=16分支樹，如圖1所示。

Figure 1 Tree representation for sixteen branches employed by AB-OCQ algorithm圖1 AB-OCQ算法使用的16分支樹表示

例如，對于半透明橙色，其ARGB值的分量分別用128,255,168,76表示，二進制表示分別為10000000,1111111,10101000,01001100。根據(jù)每個顏色位從高到低的優(yōu)先級劃分，第1層子節(jié)點的位值為14(二進制值為1110)，接下來的子節(jié)點的位值分別為5(0101)，6(0110)，4(0100)，7 (0111)，5(0101)，4(0100)和4(0100)。通過插入圖像中所有的顏色值，形成1個稱為顏色樹的結(jié)構(gòu)。在該顏色樹中(如圖2所示)，最高層(Level 1)具有最高優(yōu)先級，而最低層(Level 8)具有最低優(yōu)先級。

Figure 2 Process of prioritizing hierarchies in translucent orange圖2 半透明橙色按優(yōu)先級劃分層次結(jié)構(gòu)的過程

Figure 4 Process of inserting node in AB-OCQ algorithm圖4 AB-OCQ算法插入節(jié)點的過程

從圖1和圖2中可以看出，這個結(jié)構(gòu)下最大顏色數(shù)量是168，是1個巨大的數(shù)字。為了充分壓縮存儲空間，需要合并和裁剪顏色樹上那些不重要的顏色。如果最終留下的顏色數(shù)量不超過256，我們就可以使用1個字節(jié)來表示在這個顏色樹上每個原始ARGB顏色的位置，從而可以顯著減少存儲空間占用。對每個節(jié)點，我們定義它的結(jié)構(gòu)如圖3所示。

Figure 3 Node structure in the color tree圖3 顏色樹的節(jié)點結(jié)構(gòu)

初始化節(jié)點時，節(jié)點結(jié)構(gòu)中的每個分量都被賦值為0。顏色插入過程按照以下步驟進行(參見圖4)：

(1)從Root層開始，當前處理的節(jié)點指針指向Root。

(2)按照顏色的bit位從高到低的優(yōu)先級進行如下循環(huán)處理。

①根據(jù)ARGB的bit值生成索引值。

②判斷索引位置的childNode是否為空。如果為空，則在此位置創(chuàng)建新的子節(jié)點，并記錄當前層次。如果處理到最低位，則將該節(jié)點標記為葉節(jié)點，并將其添加到葉節(jié)點列表中。

③將顏色的A,R,G,B值添加到該子節(jié)點的A,R,G,B值，然后將訪問次數(shù)加1。

④如果該子節(jié)點是葉節(jié)點則跳出循環(huán)，否則，將當前處理的指針指向該子節(jié)點。

通過上述過程不斷插入顏色數(shù)據(jù)，就可以構(gòu)造出1棵顏色樹：這棵樹上的每個父節(jié)點都有其所有子節(jié)點的統(tǒng)計信息。根據(jù)這個特征，當顏色樹中的葉節(jié)點數(shù)超過256時，進行如下的合并處理(參見圖5)：

(1)從葉節(jié)點鏈表中，找到最低層和最低訪問次數(shù)的葉節(jié)點，它是當前最不重要的，應(yīng)該首先被合并。

(2)合并該葉節(jié)點到父節(jié)點下，并將父節(jié)點標記為新的葉節(jié)點，添加到葉節(jié)點列表中。

Figure 5 Process of merging node in AB-OCQ algorithm圖5 AB-OCQ算法合并節(jié)點的過程

按照上面插入和合并的過程處理完所有顏色數(shù)據(jù)之后，即得到1棵顏色樹。樹中的每個葉節(jié)點都包含重要的顏色信息。把這些葉節(jié)點的顏色數(shù)據(jù)提取出來，得到1個顏色集合(稱為調(diào)色板)，可用于映射原始的顏色數(shù)據(jù)。

傳統(tǒng)的OCQ由于僅僅使用了1個至多256種顏色的全局調(diào)色板，在處理色彩豐富的圖像時不可避免地會導(dǎo)致顏色失真，如圖6所示。

Figure 6 Details of the image are seriously distorted in the traditional octree color quantization algorithm圖6 傳統(tǒng)八叉樹顏色量化算法造成圖像細節(jié)部分失真

因此，改進的OCQ算法(即自適應(yīng)分塊OCQ或AB-OCQ)的基本思想是對圖像中那些細節(jié)豐富的部分執(zhí)行分塊的OCQ處理。首先，使用1個大小為16×16的滑動窗口來分析圖像中的透明區(qū)域和單一顏色區(qū)域，這些透明區(qū)域和單一顏色區(qū)域是可以用更簡單的方式表達的。如果圖像中沒有這些區(qū)域，則將整個圖像視為1個子區(qū)域。然后，對子區(qū)域(或分塊)執(zhí)行OCQ處理，計算子區(qū)域內(nèi)得到的調(diào)色板顏色數(shù)量和原始圖像的顏色數(shù)量，把這2個數(shù)量的比率記為α：如果α=1，則表示這個子區(qū)域內(nèi)沒有任何顏色被合并，此時通過OCQ算法處理這個區(qū)域，不會造成顏色數(shù)據(jù)損失；如果α接近0，則表示這個子區(qū)域中的大多數(shù)顏色都會被合并，如果用OCQ處理將會產(chǎn)生嚴重的失真。因此，在AB-OCQ算法中設(shè)置了1個閾值。計算過程中，如果計算出來的α值小于該閾值，則需要繼續(xù)把這個子區(qū)域劃分為更小的子區(qū)域，重復(fù)執(zhí)行AB-OCQ過程。特別地，如果把這個閾值設(shè)置為1，則表示不允許合并任何顏色，處理完整個圖像后將獲得1個完全無損圖像。如果此閾值設(shè)置為0，則表示每個子區(qū)域的處理過程都退化為傳統(tǒng)的OCQ算法。

圖7顯示了AB-OCQ算法的過程。

AB-OCQ中定義了4種類型的子區(qū)域。

(1)完全透明的塊(不占用任何空間);

(2)相同的顏色塊(只需要1個像素空間);

(3)普通顏色塊(包含1個局部調(diào)色板數(shù)據(jù)和顏色索引數(shù)據(jù));

(4)子區(qū)域塊(包含這4種類型的子區(qū)域)。

OCQ使用的調(diào)色板技術(shù)具有直接隨機訪問每個像素的顏色數(shù)據(jù)的特性，圖像通過AB-OCQ算法處理后，可獲得各種子區(qū)域的數(shù)據(jù)塊，圖像中的每個像素都有相應(yīng)的數(shù)據(jù)塊映射，因此不難看出AB-OCQ依然保留了這一特性，使圖像中的像素數(shù)據(jù)在保持壓縮狀態(tài)下依然能夠高效率地被隨機訪問。

Figure 7 Process of AB-OCQ algorithm圖7 AB-OCQ算法的處理過程

3 AB-OCQ 算法的實驗與討論

為了驗證AB-OCQ算法的性能，我們在量化大小、壓縮比和圖像質(zhì)量方面對AB-OCQ和OCQ算法進行了比較；同時，對AB-OCQ算法處理后的圖像與JPEG、PNG等典型的主流圖像格式在文件大小、壓縮比和圖像質(zhì)量等方面進行了比較。

本文用峰值信噪比PSNR評估圖像質(zhì)量：

(1)

其中，MAX代表圖像顏色的最大值，對于常用的每個顏色分量使用8位表示時，該值為255，MSE為式(2)定義的均方誤差：

(2)

其中,I(i,j)表示像素點(i,j)處理后的數(shù)據(jù)，K(i,j)表示像素點(i,j)的原始數(shù)據(jù)，M和N表示圖像的寬和高，根據(jù)方程式中的定義，圖像質(zhì)量的改善需要增加PSNR值。

壓縮比Rc定義為未壓縮圖像數(shù)據(jù)大小Sunc和壓縮圖像數(shù)據(jù)大小Sc之間的比率：

(3)

3.1 不同算法處理不帶Alpha通道的圖像比較

圖8和表1顯示了在處理不帶Alpha通道的無損圖像(大小為1960×1960)時，OCQ和AB-OCQ算法之間的比較(圖8a)。當采用傳統(tǒng)的OCQ算法處理該圖像時，能看到圖像上的臉部明顯出現(xiàn)了嚴重的失真(如圖8b所示)。圖8c是無損圖像到JPEG圖像高質(zhì)量的轉(zhuǎn)換，轉(zhuǎn)換后的JPEG圖像PSNR值是40 dB。從表1可以看出，與傳統(tǒng)的OCQ算法相比，AB-OCQ算法在圖像質(zhì)量方面得到了顯著改善，并且改善的程度取決于閾值的設(shè)定。我們發(fā)現(xiàn)當閾值設(shè)置為0.05時，采用AB-OCQ算法可以在圖像質(zhì)量和圖像量化尺寸之間實現(xiàn)最佳平衡。比如，與OCQ算法相比，AB-OCQ算法將圖像量化大小僅僅增加了1.05倍，但將圖像質(zhì)量提高了1.25倍。令人興奮的是，當閾值設(shè)置為0.05時，AB-OCQ算法的圖像質(zhì)量(40 dB)已經(jīng)與JPEG圖像的質(zhì)量相當了。

Figure 8 Comparison of RGB images processed by different algorithms圖8 不同算法處理后的RGB圖像比較

為了進一步評估AB-OCQ的性能，從各種互聯(lián)網(wǎng)站點隨機選擇了1 000幅不帶Alpha通道的圖像,然后分別用OCQ和AB-OCQ算法來處理。表2顯示了OCQ和不同閾值的AB-OCQ算法獲得的結(jié)果之間的比較。類似地，當閾值設(shè)置為0.03時，采用AB-OCQ算法可以在圖像質(zhì)量和圖像量化尺寸之間實現(xiàn)最佳平衡。比如，與OCQ算法相比，AB-OCQ算法將平均量化大小增加了1.07倍，但圖像質(zhì)量提高了1.15倍。

Table 1 Comparison between OCQ and AB-OCQ algorithms with different thresholds on a RAW image from quantization size,compression ratio, and image quality表1 在量化大小、壓縮比和圖像質(zhì)量方面，用OCQ和不同閾值的AB-OCQ算法處理無損圖像的比較

3.2 不同算法處理帶Alpha通道的半透明圖像比較

帶Alpha通道的半透明圖像通常用于Web頁面和電腦游戲的圖像合成等。為了說明AB-OCQ算法在處理帶Alpha通道的半透明圖像的性能，從互聯(lián)網(wǎng)上隨機選擇了1幅半透明的PNG圖像(大小為1698×1131)。圖9和表3顯示了OCQ和AB-OCQ算法性能之間的比較。圖9a是1幅無損的PNG圖像，圖9b是圖9a的局部放大。由于AB-OCQ算法不需要大量空間來存儲同色或透明子區(qū)域，因此AB-OCQ算法在處理這類圖像時的表現(xiàn)優(yōu)于OCQ。比如，當閾值設(shè)置為0.3或更低時，AB-OCQ算法顯著提高了圖像質(zhì)量和壓縮比，如圖9c、圖9d和表3所示。

Table 2 Comparison between OCQ and AB-OCQ algorithms with different thresholds on 1 000 images without Alpha channel表2 OCQ和不同閾值的AB-OCQ算法處理1 000幅不帶Alpha通道圖像的比較

Figure 9 Comparison of ARGB images processed by different algorithms圖9 不同算法處理后的ARGB圖像比較

同樣地，從各種互聯(lián)網(wǎng)站點隨機選擇了1 000幅帶Alpha通道的半透明PNG圖像并分別對這些圖像用OCQ和AB-OCQ算法進行處理，結(jié)果如表4所示。與OCQ算法相比，AB-OCQ算法顯著提高了圖像質(zhì)量。同時，當閾值小于0.3(表4中所示)時，AB-OCQ算法實現(xiàn)了更高的壓縮比，與表3中給出的結(jié)果一致。

Table 3 Comparison between OCQ and AB-OCQ algorithms with different thresholds on a half-transparent lossless PNG image from quantization size,compression ratio, and image quality表3 在量化大小、壓縮比和圖像質(zhì)量方面，用OCQ和不同閾值的AB-OCQ算法處理帶Alpha通道的半透明PNG圖像時的比較

Table 4 Comparison between OCQ and AB-OCQ with different thresholds on 1 000 PNG images with different sizes表4 OCQ和不同閾值的AB-OCQ處理1 000幅不同尺寸的帶Alpha通道的半透明PNG圖像的比較

3.3 AB-OCQ算法和主流圖片格式使用的壓縮算法的對比

為了和主流圖像格式使用的壓縮算法進行對比，隨機選擇了1 000幅原始圖像，其中有一半是帶有Alpha通道的半透明圖像。用Adobe Photoshop將這些圖像轉(zhuǎn)換為常見的JPEG和PNG格式，其中JPEG文件的核心算法使用的是離散余弦變換(DCT)，而PNG文件使用的主要是基于LZ77派生的字典壓縮算法；同時也用AB-OCQ算法對原始圖像進行處理。對于帶Alpha通道的半透明圖像，根據(jù)實驗取閾值為0.2，其他圖像根據(jù)實驗取閾值為0.05，并把AB-OCQ處理后的數(shù)據(jù)直接保存為文件，然后和原始的像素矩陣、JPEG、PNG文件做對比，得到的結(jié)果如表5所示。

Table 5 Comparison of AB-OCQ algorithm and the algorithm used by JPEG, PNG files表5 AB-OCQ算法和JPEG，PNG文件使用的算法比較

從表5可以看出，在壓縮比上，AB-OCQ算法和JPEG使用的DCT算法相比雖然不占優(yōu)勢，但好于PNG文件使用的LZ77派生算法；在圖像質(zhì)量上，AB-OCQ算法雖然比不上PNG文件使用的算法，但卻優(yōu)于JPEG文件使用的算法； AB-OCQ算法不僅能支持帶Alpha通道的圖像，更重要的，它還擁有著隨機訪問任意像素的特性，該特性是JPEG文件和PNG文件使用的壓縮算法所沒有的——DCT和LZ77派生算法都需要經(jīng)過解碼變成原始像素矩陣才能支持隨機訪問像素。因此，和JPEG、PNG文件所用的算法相比，AB-OCQ算法雖然不是在所有方面都是最優(yōu)的，但卻是綜合性能最平衡的1個算法。

4 結(jié)束語

本文提出了一種改進的OCQ算法，即AB-OCQ算法。用OCQ和AB-OCQ算法進行了比較：在處理不帶Alpha通道的圖像時，盡管通過AB-OCQ算法獲得的壓縮比與OCQ算法的壓縮比相當，但AB-OCQ算法圖像質(zhì)量比OCQ算法提高了很多;而在處理帶Alpha通道的圖像時，AB-OCQ算法不僅具有更好的圖像質(zhì)量，而且還具有更好的壓縮比；和常見的主流圖像格式所使用的壓縮算法比較，AB-OCQ算法雖然不是在各方面都最優(yōu)，但卻是綜合性能最平衡的1個算法。更為重要的是，通過AB-OCQ算法處理后的圖像數(shù)據(jù)可直接隨機訪問圖像上的像素，該特性是其他圖像壓縮算法如離散余弦變換、小波變換和字典壓縮等方法所不具備的。因此，從這個特性出發(fā)，如果應(yīng)用程序使用AB-OCQ算法對圖像進行存儲、繪制，就能在保證圖像質(zhì)量的前提下大大減少內(nèi)存消耗。未來，將繼續(xù)從這個特性出發(fā)做進一步研究。