基于視覺閾值的分形圖像壓縮算法研究

郭慧 賀杰

［摘要］ 本文提出一種基于視覺閾值的四叉樹分割方案，應用于定義域塊和值域塊的劃分，并引入人類視覺系統理論，對傳統的定義域塊的搜索方法進行了改進，將其與基本的分形圖像壓縮算法通過實驗進行了比較。實驗結果表明，在保證重建圖像質量的前提下，當視覺閾值為30、60、90 時，該算法的編碼速度是基本算法的8~27倍，是一種有效的圖像壓縮方法。

［關鍵詞］ 視覺閾值； 分形； 圖像壓縮； 四叉樹； 人類視覺系統

doi : 10 . 3969 / j . issn . 1673 - 0194 . 2012 . 02. 031

［中圖分類號］TP391［文獻標識碼］A［文章編號］1673 - 0194（2012）02- 0055- 02

１引言

在信息技術領域，圖像壓縮已經成為一個十分重要的課題。目前出現的圖像壓縮技術已達到上百種，但是壓縮比和壓縮效果不佳，且編碼、解碼時間過長，遠不能滿足當前信息時代的需要。分形圖像編碼技術是一種思想新穎的圖像壓縮技術，具有壓縮比率高、解碼分辨率無關、解碼速度快等優點，受到了國際科學界的廣泛關注。但是，分形編碼技術具有不對稱性，雖然具有很高的壓縮比且能快速解碼，但是編碼時間非常長，使得該技術一直沒有得到廣泛應用。因此對如何加快分形編碼速度方面的研究將具有重要的理論意義和實際意義。

２分形圖像壓縮的基本原理

圖像數據的分形壓縮是利用圖像的自相似和自仿射性質，尋找生成該圖像的若干局部ＩＦＳ，將所得的局部ＩＦＳ參數保存起來，形成編碼文件（即壓縮后的圖像），這就是編碼過程。分形壓縮的理論基礎是迭代函數系統定理和拼貼定理。至于解碼過程，是從任意一個初始圖像出發，用編碼文件中的局部ＩＦＳ參數，經過若干次迭代生成不變集，所得到的就是與原圖像近似的一個圖像。

２．１經典的分形圖像壓縮算法

Ｊａｃｑｕｉｎ首次成功實現了分形圖像壓縮的全自動算法［１］，該算法成為分形圖像壓縮的一個新的里程碑，其編碼算法的主要步驟如下：

步驟１：對大小為Ｍ × Ｍ的原始圖像Ｇ進行正方形分割，得到互不重疊且大小相同的２ｋ × ２ｋ的圖像子塊，將其稱為值域塊，用Ｒ表示，以下相同。

步驟２： 對于每一個Ｒ塊，在原始圖像Ｇ中找出一個尺寸為２ｋ ＋ １ × ２ｋ ＋ １的子塊Ｄ（稱之為定義域塊，用Ｄ表示，以下相同），確保對Ｄ 進行灰度仿射變換及空間變換后，所得到的Ｄ′與Ｒ之間的平方誤差值最小。

步驟３：對于每一個值域塊Ｒ，記錄下面５個參數：

（１） 搜索到的最佳匹配子塊Ｄ的左上角坐標（ｄｘ，ｄｙ）。

（２） 使Ｒ與Ｄ成為最佳匹配的等距變換的序號ｎ（一共有８種等距變換）。

（３） 灰度對比度因子ｗ，灰度平移因子ｇ。

以上參數便為原始圖像的ＩＦＳ碼，解碼時可從任意一個初始圖像出發，利用這些ＩＦＳ碼，經過１０次迭代生成不變集，得到與原圖近似的重建圖像。

３基于視覺閾值分割的分形圖像編碼算法

Ｊａｃｑｕｉｎ的算法是將圖像分割成固定尺寸的方塊，但圖像的自相似性不一定會精確地落在給定尺寸的方塊內，因此影響了壓縮效果。于是學者們提出了更多的分割方法。由Ｆｉｓｈｅｒ等人提出的四叉樹分割法［２］最大特點在于可依據匹配誤差及壓縮比自適應地調整子塊和父塊的尺寸，盡可能合理地分割圖像。與Ｊａｃｑｕｉｎ的基本分形壓縮算法相比，雖然解碼圖像質量有一定下降，但具備靈活的分塊機制和較高的壓縮比，使其較為流行。ＨＶ分割法將原始圖像分割成一系列矩形子塊，對于搜索不到匹配父塊的子塊，水平或垂直地將其劃分為兩個矩形區域，在劃分時須使矩形子塊的邊與圖像中出現的水平邊、垂直邊位置對應，使得子塊與父塊的圖像內容具備自相似性，故能更好地進行匹配。

３．１ 基于視覺閾值分割的分形圖像編碼算法的提出

四叉樹分割法、ＨＶ分割法及其后續的一些改進方案，基本思路都是把圖像分割成矩形，但均未考慮到人類視覺系統（ＨＶＳ）的特性，故無法確保圖像子塊間的相似性一定能落在矩形塊內。由于人眼對灰度的分辨能力僅有幾十個數量級，故在一幅相鄰像素灰度值相近的的灰度圖像中，即便其包含的信息量較為豐富，人眼也難以精確地識別和提取。這說明了人類視覺系統的一個顯著特性就是非均勻、非線性的認知圖像，即人眼并不能完全感知到圖像中的任意細節和變化。因此，如能把壓縮過程中一些由數量化誤差引起的解碼圖像變化控制在人眼無法察覺的范圍內，就能夠在ＨＶＳ認可的相同圖像質量下獲得較高的壓縮比。

本文提出了一種基于視覺閾值分割的分形編碼方案，是在改進的四叉樹法的圖像塊分割過程中，引入了檢測像素灰度值一致性的步驟，即劃分過程中要確保同一塊內的各像素灰度值的取值范圍不超過給定的閾值Ｓ。Ｓ的取值一般為幾十個數量級，這是由人類視覺系統的特性決定的。

與Ｆｉｓｈｅｒ等人提出的四叉樹分割法相比，本文提出的算法主要改進的方面為：

（１） 對值域塊的分割方案。若值域塊內所有像素灰度值的兩個最值之差超過給定閾值，則把該值域塊分割成4個尺寸相同的子塊，直至小于給定閾值或達到預設的圖像分割尺度時，則分割過程停止，最后得到多種不同尺寸的Ｒ塊。本方案將ＨＶＳ的視覺閾值這一特性納入了考量，按照一致性準則，圖像塊的相似性必定落在矩形內。

（２） 對定義域塊的分割方案。首先將Ｍ × Ｍ的原始圖像Ｇ整體進行水平與垂直的１／２的子采樣，得到子采樣圖像Ｇ′，其尺寸為（Ｍ／２） × （Ｍ／２），該方法通過對圖像整體的一次子采樣即實現了對全部Ｄ塊的縮放，大大加快了編碼速度。隨后采用對值域塊的分割方案對采樣圖像Ｇ′進行定義域塊分割，最后得到多種不同尺寸的Ｄ塊。

（３） 對搜索Ｄ塊方案的改進。尋找與某一Ｒ塊形成最佳匹配的Ｄ塊，只需搜索Ｄ池的一個子集，該子集中所有Ｄ塊的尺寸均與該Ｒ塊相同，故避免了對Ｄ池進行全域搜索，有效地縮小了搜索范圍。因此，本文算法總的搜索空間僅僅為不同尺寸值域塊的總數和定義域塊的總數的乘積之和的８倍，之所以要乘以８是因為每個定義域塊還存在８種等距變換。

顯然，這種基于視覺閾值的分割方案能極大地縮小搜索空間，從而也能顯著地降低編碼時間，并且由于引入ＨＶＳ的視覺閾值分割方案，也保證了重建圖像的質量。設原始圖像Ｇ的尺寸為Ｍ × Ｍ，以下是編碼算法的詳細步驟：

步驟１：給定視覺閾值Ｑ，將Ｇ分割為４個尺寸相同的正方形子塊，對每個子塊進行一致性標準檢測，即檢測子塊內像素灰度值的取值范圍不超過閾值Ｑ。

步驟２：設置分割Ｒ塊時的深度范圍，即Ｒ塊尺寸的最大值、最小值。

步驟３：若子塊尺寸分割已達最小深度范圍，即便其各像素灰度值的范圍大于Ｑ，仍停止分割；否則若塊內像素灰度值范圍大于Ｑ，則將其分割為４個更小的正方形子塊，并對這些子塊進行深度范圍檢測和像素灰度值范圍檢測。

步驟４：循環執行步驟３，當全部方塊的像素灰度值范圍均不超過Ｑ時（即滿足一致性標準），退出循環，得到所有Ｒ塊。

步驟５：對Ｇ進行水平與垂直的１／２的子采樣，得到次采樣圖像Ｇ′，其尺寸為（Ｍ／２） × （Ｍ／２），將Ｇ′分成4個大小相同的方塊，判斷每個方塊是否滿足一致性標準。

步驟６：重復步驟３，直到所有的方塊都滿足一致性標準才結束。得到多種尺寸的Ｄ塊，形成Ｄ塊池。

步驟７：對任意Ｒ塊，在Ｄ塊池中搜索一個尺寸相同的最佳匹配Ｄ塊。使得Ｄ經空間位置變換和等距變換后，與Ｒ塊具有最小平方誤差。

步驟８：記錄每個Ｒ塊的如下參數：最佳匹配Ｄ塊的空間坐標（其左上角坐標ｄｘ，ｄｙ）、等距變換的編號ｉ、灰度對比度因子ｗ、灰度平移因子ｇ。

３．２實驗結果

本節將本文提出的算法和基本的Ｊａｃｑｕｉｎ算法進行了實驗比較，以期證明本文算法的有效性和正確性。在本實驗中機器配置為：ＯＳ為Ｗｉｎｄｏｗｓ ＸＰ，ＣＰＵ為Ｐ４ ３．０Ｇ，ＲＡＭ為２Ｇ。實驗環境為Ｍａｔｌａｂ ６．５，通過編程分別實現了這兩種算法。在本實驗中，基本Ｊａｃｑｕｉｎ算法的值域塊的大小定義為４ × ４，定義域塊的大小定義為８ × ８，定義域塊的水平和垂直移動步長均設定為４；根據客觀情況，為了獲得較好的重建圖像質量，方塊（定義域塊或值域塊）所允許的最小與最大尺寸分別定義為４ × ４和８ × ８。根據ＨＶＳ的特性，閾值Ｑ通常是幾十個數量級。以２５６ × ２５６ × ８的標準灰度圖像Ｌｅｎａ和Ｇｏｌｄｈｉｌｌ為測試對象，本實驗獲得了Ｑ為３０、６０、９０的實驗結果，如表１所示。

當采用Ｊａｃｑｕｉｎ的基本分形算法時，由于對圖像進行分割后所獲得的值域塊的總數是一個固定值，如在本實驗中即為：Ｓ ＝ ２５６／４ × ２５６／４ ＝ ４ ０９６，因而采用Ｊａｃｑｕｉｎ的基本分形算法時圖像的壓縮比為：Ｃ ＝ ２５６ × ２５６ × ８／（４ ０９６ × （６ ＋ ６ ＋ ３ ＋ ５ ＋ ７）） ＝４．７４。

而當采用本文算法時，壓縮比是會隨著閾值Ｑ的變化而變化的。表１中壓縮比Ｃ的計算公式是：Ｃ ＝ ２５６ × ２５６ × ８／（Ｓ × （６ ＋ ６ ＋ ３ ＋ ５ ＋ ７）），其中Ｓ表示值域塊的總數。其中，定義域塊左上角的坐標值ｄｘ和ｄｙ被量化為６ ｂｉｔｓ和６ ｂｉｔｓ，等距變換的矩陣號ｉ被量化為３ ｂｉｔｓ，灰度對比度因子ｗ被量化為５ ｂｉｔｓ，灰度平移因子ｇ被量化為７ ｂｉｔｓ。本實驗結果中的壓縮比Ｃ是在熵編碼前所獲得的。

４結論

本文將改進的四叉樹分割方案同時應用于定義域塊和值域塊的劃分上。同時，基于人類視覺系統理論，對傳統的定義域塊的搜索方法進行了改進，提出了一種新的搜索方法。最后，基于基本分形算法，提出并實現了一種基于視覺閾值分割的分形圖像壓縮算法，并將其與基本分形算法通過實驗進行了比較。實驗結果表明該算法是一種有效的圖像壓縮方法。

主要參考文獻

［１］ Ａ Ｅ Ｊａｃｑｕｉｎ． Ｉｍａｇｅ Ｃｏｄｉｎｇ Ｂａｓｅｄ ｏｎ ａ Ｆｒａｃｔａｌ Ｔｈｅｏｒｙ ｏｆ Ｉｔｅｒａｔｅｄ Ｃｏｎｔｒａｃｔｉｖｅ Ｉｍａｇｅ ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ，１９９２，１（１）：１８－３０．

［２］ Ｙ Ｆｉｓｈｅｒ． Ｆｒａｃｔａｌ Ｉｍａｇｅ Ｃｏｍｐｒｅｓｓｉｏｎ：Ｔｈｅｏｒｙ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎ［Ｍ］． Ｎｅｗ Ｙｏｒｋ，NY： Ｓｐｒｉｎｇｅｒ，１９９４．

［３］ 朱偉勇，于海，宋春林． 基于誤差閾值和分層搜索的快速分形圖像壓縮方法［Ｊ］． 小型微型計算機系統， ２００５，２６（２）：２７７－２８０．

［４］ 何傳江，黃席樾． 基于圖像塊叉跡的快速分形圖像編碼算法［Ｊ］． 計算機學報， ２００５， ２８（１０）： １７５３－１７５８．