應用粒子群優化算法的混合紋理合成
2009-01-01 00:00:00孫立鐫李峰丁博
計算機應用研究 2009年2期
（哈爾濱理工大學計算機科學與技術學院， 哈爾濱 150080）
摘 要：
應用粒子群優化算法作為像素尋優策略，應用于多樣圖紋理合成算法中，將群智能中經典的粒子群優化算法引入到紋理合成領域。應用粒子群優化多樣圖紋理合成方法是傳統的基于像素紋理合成方法和基于塊的紋理合成方法的折中，除能大大提高多樣圖紋理合成的速度，樣圖的質量也得到了很大改善。實驗證明，該算法有效解決了徐曉剛混合紋理合成中輸出紋理出現的條痕問題。
關鍵詞：紋理合成； 粒子群優化； 群智能； 適應值
中圖分類號：TP391 文獻標志碼：A
文章編號：1001-3695(2009)02-0772-03
PSO-based multi-samples texture synthesis
SUN Li-juan， LI Feng， DING Bo
(College of Computer Science Technology， Harbin University of Science Technology， Harbin 150080， China)
Abstract:Using the PSO method as a optimization strategy for the multi-samples texture synthesis，introducing the classical PSO method of swarm intelligence to the area of texture synthesis， multi-samples synthesis using PSO was an eclectic scheme between pixel based texture synthesis methods and patch-based texture synthesis methods.It improves the speed of synthesizing and the quality of the output image;the implementation of algorithm proves the effectiveness of this method.
Key words：texture synthesis； particle swarm optimization(PSO)； swarm intelligence； fitness value
本文針對大規模場景中對于多樣圖紋理合成的需求，以提高合成速度和質量為目的，在傳統點像素紋理合成的基礎上，提出了基于粒子群優化的多樣圖紋理合成方法，以粒子群算法來優化輸入樣圖點像素搜索策略，在提高合成速度的同時，也解決了合成質量條形化問題。
1 粒子群優化算法
粒子群優化算法(PSO)是由Kennedy等人[1]于1995年提出的，其起源于對簡單社會系統的模擬，可以利用群體智能建立一個簡化模型，用組織社會行為代替進化算法的自然選擇機制，通過種群間個體協作來實現對問題最優解的搜索。
1.1 基本原理及其演化
PSO算法也是根據周圍環境的適應度將群體中的個體移動到好的區域，不同之處在于它不像其他演化算法那樣對個體使用演化算子，而是將每個優化問題的潛在解都想象成d維搜索空間中的一個沒有體積沒有質量的微粒，稱之為粒子(particle)。其中的每個粒子所處的位置都表示問題的一個解[2]。每個粒子的適應值(fitness value)是由優化目標決定的，用于評價粒子的搜索性能，指導粒子種群的搜索過程，算法迭代停止時適應度函數最優的解變量即為優化搜索的最優解。每個粒子都將在搜索空間中以一定的速度飛行，粒子速度表示粒子在單位迭代次數位置的變化即為代表解變量的粒子在d維空間的位移，通過不斷調整自己的位置來搜索新解。每個粒子均能記住自己搜索到的最好解(particle best)，記做pbest，表示單個粒子從搜索初始到當前迭代對應的適應度最優的解，以及整個粒子群經歷過的最好位置，即目前搜索到的最優解(global best)，記做gbest，表示整個粒子種群從搜索開始到當前迭代對應的適應度最優的解，其值是為每個粒子的當前最好解pbest中最適應的那個。每個粒子使用下列信息改變自己的當前位置：a)當前位置；b)當前速度；c)當前位置與自己最好位置之間的距離；d)當前位置與群體最好位置之間的距離。優化搜索正是在這樣一群隨機初始化形成的粒子組成的一個種群中，以迭代的方式進行。
1. 2 數學描述
設粒子群優化算法的搜索空間為D維，總粒子數為n，第i個粒子位置表示為向量xi=(xi1，xi1，…，xin)，第i個粒子d個維度迄今為止搜索到的最優位置為pbesti=(pi1， pi2，…，piD)，整個粒子群迄今為止搜索到的最優位置為gbest=(g1，g2，…，gn)，第i個粒子的位置變化率(速度)為向量vi=(vi1，vi2，…，viD)。粒子的每維速度和位置按如下公式進行變化：
α1=σ1× rand()×(pid(t)-xid(t))
α2=σ2× rand()×(pgd(t)-xid(t))
vid(t+1)=w×vid(t)+α1+α2
xid(t+1)=xid(t)+vid(t+1)
其中：w為慣性權重；σ1、σ2為正常數；稱為加速因子，σ1調節粒子飛向自身最好位置方向的步長；σ2調節粒子向全局最好位置飛行的步長；rand()為[0，1]的隨機數。由公式可以看出，粒子的移動方向由三部分決定，自己原有速度vid、與自己最佳經歷的距離(pid-xid)，以及與全局最佳經歷位置的距離，并分別由權重系數σ1和σ2決定其相對重要性。
2 應用粒子群優化的混合紋理合成方法
本文提出的基于粒子群優化方法與Wei和Levoy算法類似，即采用L鄰域作為搜索區域。在多個樣本紋理中搜索區域像素點[3]，并直接復制到輸出紋理中，如圖1所示。
在匹配點查找策略上加以改進，采用一種流程簡單實現，算法參數簡潔，收斂快速的尋優算法——粒子群優化算法來提高搜索效率。算法中對于每一個輸入樣圖紋理Sin定義為用來搜索的解空間，將解空間內搜索到的匹配像素點作為要搜尋的通過PSO計算的樣本紋理空間中獲得的解來處理。
算法首先與基本的基于點的紋理合成算法一致，在每個輸入樣圖內各取一點，通過其比例參數調整計算后，生成一個輸出點復制到輸出紋理Sout上；然后在輸入樣本Sin(i)(i=0…n)上隨機選取幾個像素點，將其作為運動粒子，并賦予初始速度，每個粒子在輸入樣本紋理運動時，均會記住其L鄰域與待合成像素點L鄰域的匹配程度，同時記住本身決定個體的匹配程度。首先找出各個輸入樣本中的粒子察覺到決定的匹配程度最好的粒子，并對每個粒子根據自己的運動和速度進行適當調整；然后再將各個樣圖找出的最佳粒子進行比較，以獲得與當前已合成完紋理區域匹配的個體，并將該個體復制到輸出紋理Sout中。重復上面過程，直至紋理合成完畢。下面對PSO應用與多樣圖紋理合成的具體細節進行說明。
2.1 樣圖粒子屬性定義
對于二維多樣圖，粒子維度為二維。為使算法更易于理解，首先描述雙樣圖的紋理合成技術。不妨假設兩紋理樣圖W1in、W2in在合成紋理圖像中所占的比例分別為β1、β2(0≤β1≤1， 0≤β2≤1)。也就是說，統計意義上，結果紋理圖像中100β1%來自樣圖W1in， 100β2%來自樣圖W2in。在Wei和Levoy算法的L鄰域作為搜索區域基礎上，采用粒子群優化算法作為搜索策略。對于每一個輸入樣圖中，假設搜索空間有n個粒子，則第i個粒子的位置定義為在輸入的樣本紋理中對應像素點的位置，記為坐標(Present Xi，Present Yi)。粒子i經歷的最好位置記為坐標(Lbest Xi，Lbest Yi)，粒子在這個位置取得的適應值記為Lbesti，所有粒子經歷過的最好位置記為坐標(Gbest X，Gbest Y)，粒子在這個位置取得的適應值記為Gbest，顯然有Gbest=min{Lbest1，Lbest2，…，Lbestn}。每個粒子最初都有一個隨機的初始運動向量Vi=(Vix，Viy)，這樣就可以按照1.2節的粒子每維速度及位置變化公式進行粒子群的運動搜索過程。若記輸出圖象Wout中的每一像素點p在兩輸入樣圖中的匹配待選點分別為p1、p2，則根據像素點x處L鄰域與像素x1、x2處L鄰域的相似性檢測，就可決定出兩個樣圖中哪個點是像素p的最佳匹配點，從而確定在哪個紋理圖像中采樣，得到合成結果。當然，在相似性比較時，需要考慮用戶確定的樣圖混合比例，以保證合成紋理符合要求。
對于搜索空間中的每個粒子，在搜索過程中任一時刻都要計算其適應值。該適應值表示當前粒子所在位置的L鄰域與待合成像素L鄰域的匹配程度。定義D為待合成像素的L鄰域，S為粒子所在位置的L鄰域。則粒子適應值的計算公式如下：
d(D，S)=∑ki=1{[R(Di)-R(Si)]2+[G(Di)-G(Si)]2+[B(Di)-B(Si)]2}
其中：R()、G()、B()分別為像素點的R、G、B分量；Di為L鄰域D的第i個像素點；Si為L鄰域S的第i個像素點；k為L鄰域內像素點個數。
設θ(p)表示某一圖像中p 點L鄰域內的所有點集合，在對多個樣圖選取的各自最佳匹配點中選取樣圖最佳匹配點時，需要選取誤差最小的匹配點，這里誤差err可取為
err=(1-β1)×d(θ(p1)，θ(p))+(1-β2)×d(θ(p2)，θ(p))
2. 2 樣圖內匹配值選取
PSO算法在進行匹配搜索時是一個迭代的過程，由于樣本的多樣性，除了所要尋找的邊界區域在輸入樣本紋理中能搜索到完全匹配其L鄰域的點外，很難找到一個自適應的方法來結束算法。要通過PSO算法的通常結束條件來終止算法，即用迭代次數來控制算法的結束。本文設定了一個匹配度閾值dmin，以便找到一個與其L鄰域匹配的點作為匹配備選點。若某一時刻粒子群的最優適應值低于dmin，則可中止迭代過程，并將取得最優適應值的粒子所在像素點作為最優解返回；另外，還需設定一個最大迭代次數以保證算法的效率。dmin的定義如下：
dmin=η×sqrt[∑nk=1[R(Dk)2+G(Dk)2+B(Dk)2]
其中：Uk為L鄰域U的第k個像素點；k為L鄰域內像素點個數。η為誤差容忍系數，通過實驗發現了一些規律，對于規律性較強的紋理，如磚墻、布等，因為很小的誤差也會造成視覺上的不連續性，所以在實驗中容忍系數要選擇較大些。對于隨機性較強的紋理，如皮毛、草等，因為隨機性強，對誤差的要求不是很大，所以在實驗中容忍系數要選擇較小些。
2. 3 樣圖間匹配值選取
對于雙輸入紋理樣圖的紋理合成，首先需要對輸出樣圖進行初始化，并建立臨時圖像tImage，tImage中的初始化像素點tPixel以及圖像的各個屬性可以定義如下式所示：
tPixel. red=(sPixel1. red+sPixel2. red)/2
tPixel. green=(sPixel1. green+sPixel2. green)/2
t Pixel. blue=(sPixel1. blue+sPixel2.blue)/2
t Image. width =min(w1in， w2in)
t Image. height =min(w1in， w2in)
在選取匹配點時，首先從臨時圖像中隨機采樣，填充到輸出圖像，將采樣點像素位置寫到輸出樣圖相應點上。通過遍歷輸出樣圖中待填充點L鄰域內所有待選點，按照2.1節中提到的誤差計算公式計算各個輸入樣圖最佳匹配點與輸出樣圖待填充點L鄰域的誤差，選取誤差最小的點為匹配點，并將該匹配點值拷貝到輸出圖像，同時更新Wout值。
將雙樣圖紋理合成方法進行推廣，可以獲得多樣圖紋理合成結果。假設各紋理樣圖在結果紋理圖像中所占的比例βi（i=1，…，n），0≤βi≤1；最佳匹配點的位置記錄在S(p)中。將輸出圖像Wout中的每一點p與輸入樣圖中的點pi（i=1，…，n）進行比較，獲得最佳匹配點，根據匹配誤差決定在哪個紋理圖中采樣，得到合成結果。此時，控制誤差為
err=∑ni=1（1-βi）/（n-1）×d(θ(pi)，θ(p))
2.4 算法流程
綜合以上方法，應用PSO的多樣圖紋理合成算法的具體過程如下：
a)初始化各參數和輸出圖像。在每個輸入的樣本紋理Win（i=1，…，n）中，隨機選擇一點，并通過混合公式初始化輸出圖像，將各項參數復制到輸出紋理Wout中，令k=1。
b)在輸出紋理中確定待合成像素點的L鄰域D。在輸入的樣本紋理Win（i=1，…，n）中應用PSO算法尋找與之匹配的L鄰域S。
c)若粒子群的最優適應值低于dmin或已達到最大的迭代次數，則將每個輸入樣圖中得到的最優適應值的粒子進行誤差比較，將誤差最小的像素點作為最佳匹配點復制到輸出的紋理Wout中，k=k+l。轉步驟d)；否則，迭代次數增加，轉步驟b)。
d)若輸出紋理Wout已合成完畢，則輸出Wout；否則，將迭代次數清零，轉而繼續執行步驟b)。
3 系統實現
本文提出的應用粒子群優化算法的混合紋理合成經VC實現后，在PC機(Core T2400，1 GB內存，256 MB顯存)運行，設置粒子數為20，最大迭代數為500，讀入兩個42×42的輸入位圖，控制比例為1∶1；為了進行對比，同時將徐曉剛[4]的混合紋理合成的合成結果顯示作為比較，運行結果如圖2、3所示。
從運行結果可以看出，由于徐曉剛的混合紋理合成仍然是基于Ashikhmin的點合成的思想，需要對輸入樣圖內所有點的L鄰域進行掃描，消耗了大量時間，而本文提出的算法由于采用了粒子群優化的尋優策略，采用迭代的方法，無須逐點進行掃描，節省了大量時間，執行時間提高了許多，幾乎達到了塊拼貼的執行時間數量級。由于粒子群優化多樣圖紋理合成方法中不存在掃描的次序問題，對于徐曉剛算法中結構性較強的紋理產生的明顯條帶痕跡也進行了改善。由圖3可以看出，通過粒子群優化算法的多樣圖紋理合成，可得到更加自然的輸出樣圖，合成圖的質量有了很大提高。
4 結束語
本文在多樣圖紋理合成尋找匹配點的過程中采用尋優策略，有效提高了多樣圖紋理合成的合成速度和質量。
參考文獻：
[1]KENNEDY J， EBERHART R.Particle swarm optimization[C]//Proc of IEEE International Conference on Neural Networks. Perth Astralia: IEEE Press， 1995:1942-1948.
[2]張麗平.粒子群優化算法的理論及實踐[D].杭州：浙江大學，2005：18-27.
[3]XUE F， ZHANG Y S， JIANG J L. Real-time texture synthesis using S-Tile set[J]. Journal of Computer Science and Technology， 2007，22(4):590-596.
[5]MULLER G， MESETH J， SATTLER M. Synthesis， and rendering of bidirectional texture functions[J]. Computer Graphics Forum，2005，24(1):83-109.
[4]徐曉剛.紋理合成技術研究[D].杭州：浙江大學，2001:12-25.
[6]MATUSIK W， ZWICKER M， DURAND F. Texture design using a simplicial complex of morphable textures[C]//Proc of SIGGRAPH’05. New York: ACM， 2005:787-794.
