摘   要： 圖像稀疏化技術(shù)是利用圖像中稀少的且與具體應(yīng)用相關(guān)的數(shù)據(jù)來表示原始圖像的技術(shù)。使用BSP和遺傳算法的方法在圖像中生成能夠近似圖像的自適應(yīng)的網(wǎng)格，即用較少的包含重要信息的像素來表示圖像，實(shí)現(xiàn)圖像的稀疏化，達(dá)到壓縮之目的。該自適應(yīng)網(wǎng)格能夠以很高的質(zhì)量重構(gòu)出原始圖像，在圖像處理和計(jì)算機(jī)視覺領(lǐng)域有很好的應(yīng)用前景。
關(guān)鍵詞： 稀疏化；BSP；遺傳算法；自適應(yīng)網(wǎng)格

　圖像的表示是尋求一種適合的方式來對(duì)圖像進(jìn)行更為方便的操作，就像把圖像表示為離散的矩陣形式是為了方便計(jì)算機(jī)操作一樣。圖像的稀疏表示在圖像處理[1]和計(jì)算機(jī)視覺[2]領(lǐng)域有著很好的應(yīng)用，它能壓縮圖像，加快處理過程，更有利于具體應(yīng)用領(lǐng)域的求解。用網(wǎng)格表示稀疏化的圖像在該領(lǐng)域中有著重要的研究地位，通常先去掉圖像中冗余的像素點(diǎn)，保留含有關(guān)鍵信息的像素，然后在這些像素點(diǎn)上生成網(wǎng)格來近似圖像。本文提出的稀疏化的方法是將圖像遞歸地劃分為一個(gè)個(gè)滿足要求的三角形，用三角形所構(gòu)成的網(wǎng)格來表示圖像。用遺傳算法聚類來劃分三角形，用BSP樹結(jié)構(gòu)來記錄圖像劃分的結(jié)構(gòu)，同時(shí)劃分的三角形要求能夠很好地表示其內(nèi)部的像素，即能重構(gòu)出其內(nèi)部的像素，否則該三角形需要進(jìn)行進(jìn)一步地劃分，因此三角形所形成的網(wǎng)格具有自適應(yīng)性。
1 使用BSP樹構(gòu)建自適應(yīng)網(wǎng)格
　給定一幅圖像，構(gòu)建一個(gè)圖像的自適應(yīng)網(wǎng)格來表示。從圖像中選取少量的包含圖像重要信息的像素作為網(wǎng)格的節(jié)點(diǎn)，為此選取BSP樹來保存該劃分的網(wǎng)格結(jié)構(gòu)。二叉空間劃分BPS[3](Binary Space Partition)是計(jì)算機(jī)圖形學(xué)中常用的畫家算法，在二維平面內(nèi)，一根直線可以將該平面劃分為兩個(gè)半平面，在半平面內(nèi)的直線還可以將該半平面劃分為更小的子平面，這一過程可以一直進(jìn)行。因此可以用BPS樹來存儲(chǔ)這一劃分的平面。在本文中，將要處理的圖像遞歸地劃分為一個(gè)個(gè)三角形，所劃分的三角形組成網(wǎng)格結(jié)構(gòu)，每一次遞歸劃分過程中要判斷所劃分的三角形是否滿足預(yù)定的標(biāo)準(zhǔn)，滿足標(biāo)準(zhǔn)則停止劃分該三角形，不滿足則繼續(xù)劃分。BPS樹用來保存這一迭代的劃分過程，其中非葉子節(jié)點(diǎn)保存用于劃分的分割線，所有的葉子節(jié)點(diǎn)則保存劃分后的三角形。
　首先，要確定三角形的劃分標(biāo)準(zhǔn)。要求網(wǎng)格中的三角形能重構(gòu)出其內(nèi)部的所有像素點(diǎn)，具有自適應(yīng)性，為此需要找到一個(gè)標(biāo)準(zhǔn)來量化原始圖像的像素并利用網(wǎng)格中節(jié)點(diǎn)重構(gòu)出圖像的對(duì)應(yīng)像素間的異度。本文選取峰值信噪比來衡量對(duì)應(yīng)像素點(diǎn)間灰度的差異度。一幅灰度圖像的峰值信噪比PSNR定義如下：

　其中，(xi,yi)是三角形3個(gè)頂點(diǎn)的坐標(biāo)，(xn,yn)是三角形內(nèi)部像素的坐標(biāo)，因此利用式(4)可求出wi，再代入式(3)計(jì)算出In的值，便可計(jì)算出PSNR了。很明顯重構(gòu)出的圖像越接近于原始圖像，三角形的PSNR值越大。為了讓網(wǎng)格高質(zhì)量地重構(gòu)出圖像,一般設(shè)立一個(gè)較高的PSNR閾值，例如30 dB~40 dB。如果劃分的三角形不滿足此閾值則繼續(xù)劃分，直到滿足條件為止。
　另外，選取三角形內(nèi)所包含像素點(diǎn)的多少作為三角劃分的另一終止的條件，以防止三角形過大、過稀疏化。當(dāng)然可以根據(jù)生成稀疏圖像的具體應(yīng)用場(chǎng)景來設(shè)置該閾值。用BPS構(gòu)建自適應(yīng)網(wǎng)格的流程圖如圖1所示。

2 用遺傳算法進(jìn)行三角劃分
　對(duì)于達(dá)不到閾值、不滿足條件的三角形，要進(jìn)一步進(jìn)行劃分。本文提出用遺傳算法聚類[4]的方法來劃分三角形。遺傳算法是借鑒生物界進(jìn)化規(guī)律演化而來的一種隨機(jī)化的搜索算法，其主要特點(diǎn)是:直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作，不存在求導(dǎo)和函數(shù)連續(xù)性的限定；具有內(nèi)在的隱形并行性和更好的全局尋優(yōu)能力；采用概率化的尋優(yōu)方法，能自動(dòng)獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向。
　本文利用遺傳算法將三角形內(nèi)部像素聚為兩類，通過三角形頂點(diǎn)和兩個(gè)類中心的中點(diǎn)的連線劃分三角形?；蚓幋a采用浮點(diǎn)數(shù)編碼，用像素點(diǎn)的二維坐標(biāo)表示。首先，建立n個(gè)種群(可調(diào)整n的值與三角形包含像素個(gè)數(shù)的多少成正比)，每個(gè)種群隨機(jī)地選取三角形內(nèi)的兩個(gè)像素點(diǎn)c1、c2作為種群的個(gè)體，即初始的兩個(gè)類中心。適應(yīng)度函數(shù)定義為三角形內(nèi)所有像素點(diǎn)到離它們最鄰近的類中心的平均歐氏距離，定義如下：
    
其中，c1和c2是種群的個(gè)體，pi是三角形內(nèi)的像素點(diǎn)，D是歐式距離，T是三角形內(nèi)像素的個(gè)數(shù)。很顯然，F(xiàn)值越小適應(yīng)度越高。
    要求計(jì)算出所有種群的適應(yīng)度函數(shù)，然后采用輪盤賭選擇算法選取m個(gè)種群進(jìn)入下一代，適應(yīng)度越高的種群進(jìn)入下一代的概率越大。對(duì)剩下的n-m個(gè)種群進(jìn)行交叉和變異操作。交叉操作是選取未進(jìn)入下一代的某一種群中的一個(gè)類中心，與其他任意一個(gè)種群的類中心進(jìn)行交換，保存交換后的兩個(gè)個(gè)體，并將該種群放入下一代。變異操作是以小概率的事件發(fā)生選取未進(jìn)入下一代的某一種群中的一個(gè)類中心，將其坐標(biāo)值朝任意方向增長(zhǎng)隨機(jī)步長(zhǎng)，保存其值，然后進(jìn)入下一代。再重新計(jì)算出下一代的每個(gè)種群的適應(yīng)度，此過程一直迭代，直到滿足終止條件為止。本文以迭代次數(shù)作為遺傳算法的終止條件，所有迭代進(jìn)行完后，選取適應(yīng)度最高的種群作為最優(yōu)解，即找到了三角形內(nèi)的兩個(gè)類中心。

3 實(shí)驗(yàn)結(jié)果
　本實(shí)驗(yàn)對(duì)如圖3所示的512×512的Lena灰度圖像進(jìn)行實(shí)驗(yàn)，使用基于BSP和遺傳算法技術(shù)對(duì)原始圖像稀疏化所生成的自適應(yīng)的網(wǎng)格如圖4所示。該網(wǎng)格由一個(gè)個(gè)三角形組成，刪除了大量的冗余信息，同時(shí)保存了圖像的重要信息。該稀疏圖像在PSNR=30 dB的條件下生成，所生成三角形的數(shù)量約為3萬個(gè)，相對(duì)于其他網(wǎng)格表示[5-6]技術(shù)，本文提出的方法在壓縮率上有近30%的提高。用該網(wǎng)格重構(gòu)出的近似圖像(PSNR=30 dB) 如圖5所示，從視覺直觀判斷，重構(gòu)出的圖像稍有平滑的效果，質(zhì)量今人滿意。

    本文提出了結(jié)合BSP和遺傳算法的技術(shù)將圖像稀疏化表示，用BSP樹生成自適應(yīng)的網(wǎng)格，用遺傳算法分割網(wǎng)格中的三角形，同時(shí)該網(wǎng)格能以很高的質(zhì)量重構(gòu)出原始圖像。所獲得的稀疏化圖像具有較高的壓縮比，可應(yīng)用在圖像處理、計(jì)算機(jī)視覺等各個(gè)領(lǐng)域。
參考文獻(xiàn)
[1] 徐大宏.基于正則化方法的圖像復(fù)原算法研究[D].長(zhǎng)沙：國(guó)防科技大學(xué)，2009.
[2] SARKIS M, DIEPOLD K. Sparse stereo matching using belief propagation[C].Image Processing. ICIP 2008.15th IEEE International Conference on. San Diego,CA.2008:1780-1783.
[3] SHIRLEY P.計(jì)算機(jī)圖形學(xué)(第2版)[M].高春曉，譯.北京:人民郵電出版社,2007.
[4] 傅景廣，許剛，王裕國(guó).基于遺傳算法的聚類分析[J].計(jì)算機(jī)工程,2004,30(4):123-124
[5] YANG Y,WERNICK M N, BRANKOV J G. A fast approach for accurate content-adaptive mesh generation[J]. IEEE Transactions on Image Processing, 2003,12(8):866-880.
[6] RAMPONI G, CARRATO S. An adaptive sampling algorithm and its application on image coding[J]. Image and  Vision Computing,2001,19(7):451-460.