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

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

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

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

3 實驗結(jié)果
　本實驗對如圖3所示的512×512的Lena灰度圖像進行實驗,，使用基于BSP和遺傳算法技術(shù)對原始圖像稀疏化所生成的自適應(yīng)的網(wǎng)格如圖4所示。該網(wǎng)格由一個個三角形組成,，刪除了大量的冗余信息,，同時保存了圖像的重要信息。該稀疏圖像在PSNR=30 dB的條件下生成,，所生成三角形的數(shù)量約為3萬個,，相對于其他網(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)格中的三角形,，同時該網(wǎng)格能以很高的質(zhì)量重構(gòu)出原始圖像。所獲得的稀疏化圖像具有較高的壓縮比,，可應(yīng)用在圖像處理,、計算機視覺等各個領(lǐng)域。
參考文獻
[1] 徐大宏.基于正則化方法的圖像復(fù)原算法研究[D].長沙：國防科技大學(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.計算機圖形學(xué)(第2版)[M].高春曉,，譯.北京:人民郵電出版社,2007.
[4] 傅景廣，許剛,，王裕國.基于遺傳算法的聚類分析[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.