摘   要： 圖像稀疏化技術是利用圖像中稀少的且與具體應用相關的數據來表示原始圖像的技術。使用BSP和遺傳算法的方法在圖像中生成能夠近似圖像的自適應的網格，即用較少的包含重要信息的像素來表示圖像，實現圖像的稀疏化，達到壓縮之目的。該自適應網格能夠以很高的質量重構出原始圖像，在圖像處理和計算機視覺領域有很好的應用前景。
關鍵詞： 稀疏化；BSP；遺傳算法；自適應網格

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

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

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

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

    本文提出了結合BSP和遺傳算法的技術將圖像稀疏化表示，用BSP樹生成自適應的網格，用遺傳算法分割網格中的三角形，同時該網格能以很高的質量重構出原始圖像。所獲得的稀疏化圖像具有較高的壓縮比，可應用在圖像處理、計算機視覺等各個領域。
參考文獻
[1] 徐大宏.基于正則化方法的圖像復原算法研究[D].長沙：國防科技大學，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.計算機圖形學(第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.