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

郭慧 賀杰

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

［關(guān)鍵詞］ 視覺(jué)閾值； 分形； 圖像壓縮； 四叉樹； 人類視覺(jué)系統(tǒng)

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

［中圖分類號(hào)］TP391［文獻(xiàn)標(biāo)識(shí)碼］A［文章編號(hào)］1673 - 0194（2012）02- 0055- 02

１引言

在信息技術(shù)領(lǐng)域，圖像壓縮已經(jīng)成為一個(gè)十分重要的課題。目前出現(xiàn)的圖像壓縮技術(shù)已達(dá)到上百種，但是壓縮比和壓縮效果不佳，且編碼、解碼時(shí)間過(guò)長(zhǎng)，遠(yuǎn)不能滿足當(dāng)前信息時(shí)代的需要。分形圖像編碼技術(shù)是一種思想新穎的圖像壓縮技術(shù)，具有壓縮比率高、解碼分辨率無(wú)關(guān)、解碼速度快等優(yōu)點(diǎn)，受到了國(guó)際科學(xué)界的廣泛關(guān)注。但是，分形編碼技術(shù)具有不對(duì)稱性，雖然具有很高的壓縮比且能快速解碼，但是編碼時(shí)間非常長(zhǎng)，使得該技術(shù)一直沒(méi)有得到廣泛應(yīng)用。因此對(duì)如何加快分形編碼速度方面的研究將具有重要的理論意義和實(shí)際意義。

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

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

２．１經(jīng)典的分形圖像壓縮算法

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

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

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

步驟３：對(duì)于每一個(gè)值域塊Ｒ，記錄下面５個(gè)參數(shù)：

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

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

（３） 灰度對(duì)比度因子ｗ，灰度平移因子ｇ。

以上參數(shù)便為原始圖像的ＩＦＳ碼，解碼時(shí)可從任意一個(gè)初始圖像出發(fā)，利用這些ＩＦＳ碼，經(jīng)過(guò)１０次迭代生成不變集，得到與原圖近似的重建圖像。

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

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

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

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

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

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

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

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

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

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

步驟１：給定視覺(jué)閾值Ｑ，將Ｇ分割為４個(gè)尺寸相同的正方形子塊，對(duì)每個(gè)子塊進(jìn)行一致性標(biāo)準(zhǔn)檢測(cè)，即檢測(cè)子塊內(nèi)像素灰度值的取值范圍不超過(guò)閾值Ｑ。

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

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

步驟４：循環(huán)執(zhí)行步驟３，當(dāng)全部方塊的像素灰度值范圍均不超過(guò)Ｑ時(shí)（即滿足一致性標(biāo)準(zhǔn)），退出循環(huán)，得到所有Ｒ塊。

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

步驟６：重復(fù)步驟３，直到所有的方塊都滿足一致性標(biāo)準(zhǔn)才結(jié)束。得到多種尺寸的Ｄ塊，形成Ｄ塊池。

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

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

３．２實(shí)驗(yàn)結(jié)果

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

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

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

４結(jié)論

本文將改進(jìn)的四叉樹分割方案同時(shí)應(yīng)用于定義域塊和值域塊的劃分上。同時(shí)，基于人類視覺(jué)系統(tǒng)理論，對(duì)傳統(tǒng)的定義域塊的搜索方法進(jìn)行了改進(jìn)，提出了一種新的搜索方法。最后，基于基本分形算法，提出并實(shí)現(xiàn)了一種基于視覺(jué)閾值分割的分形圖像壓縮算法，并將其與基本分形算法通過(guò)實(shí)驗(yàn)進(jìn)行了比較。實(shí)驗(yàn)結(jié)果表明該算法是一種有效的圖像壓縮方法。

主要參考文獻(xiàn)

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

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

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

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