主動輪廓線模型邊界點的尋優(yōu)

主動輪廓線模型邊界點的尋優(yōu)

0優(yōu)化問題的解決方法1987年，kass、witka和ter澤科提出的活躍模型（acm）被稱為sname模型。其基本思想是以一定形狀的一些控制點為輪廓線,通過輪廓線自身的彈性形變,與圖像局部特征相匹配,鎖定在圖像特征附近,從而達(dá)到某種能量函數(shù)的極小化,同時完成對圖像的分割與跟蹤。傳統(tǒng)的Snake模型主要存在以下兩個缺陷:1)初始輪廓線的位置必須接近于實際的目標(biāo)邊緣。如果主動輪廓在初始化時,控制點離所需要提取的邊緣的距離不夠近,那么它將無法收斂到目標(biāo)輪廓上。2)傳統(tǒng)Snake模型無法檢測到目標(biāo)的凹陷邊界處。針對這些缺點,不少文獻(xiàn)已經(jīng)提出了改進(jìn)的方法,如Cohen提出了歸一化圖像力場和Balloon力的Balloon模型,提高了曲線的演化速度和定位邊緣的精確性;Amini等提出基于動態(tài)規(guī)劃的算法Snakes(DP),把全局最優(yōu)估計問題的求解轉(zhuǎn)化為遞推求解一系列局部最優(yōu)估計問題,保證算法的全局收斂性;Xu等提出了梯度向量流(GradientVectorFlow,GVF)的Snake模型,該模型對圖像梯度場逼近構(gòu)造一種新的外力,通過嚴(yán)格地在內(nèi)力和外力的作用下達(dá)到平衡來得到目標(biāo)邊緣,可以更好地檢測深度凹陷區(qū),但對于長窄形的凹陷區(qū)目標(biāo)檢測效果仍不理想。粒子群優(yōu)化算法(ParticleSwarmOptimization,PSO)是一種進(jìn)化計算技術(shù),其基本思想是通過群體中個體之間的協(xié)作和共享來尋找最優(yōu)解。PSO同遺傳算法類似,是基于群體的優(yōu)化工具,但并沒有遺傳算法的交叉及變異操作,而是粒子(潛在最優(yōu)解)在解空間追隨最優(yōu)的粒子進(jìn)行搜索。與遺傳算法比較,PSO的優(yōu)勢在于概念簡單,易于實現(xiàn)。因此,PSO一經(jīng)提出,立刻引起演化計算領(lǐng)域?qū)W者們的廣泛關(guān)注,并在很多領(lǐng)域如目標(biāo)的自動檢測與跟蹤、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、解決多目標(biāo)優(yōu)化問題等方面得到廣泛應(yīng)用。李惠光、石磊等人提出將單一PSO方法用于主動輪廓線模型的蛇點尋優(yōu),取得了較好的效果。然而研究表明,PSO算法也存在一些缺點,如計算時間較長、容易陷入局部極值等,這是由于算法本身固有的隨機(jī)性決定的。并且在實際應(yīng)用中,系統(tǒng)的實時性能顯得尤為重要,因而采用單一PSO的Snake模型具有明顯的局限性。本文提出將多種群粒子群優(yōu)化算法應(yīng)用在主動輪廓線模型中,其輪廓線的每個控制點都與一個種群相對應(yīng),每個種群通過與其相鄰的兩個種群共享信息,可在較大的搜索窗口內(nèi)搜索到控制點的最佳位置,克服了傳統(tǒng)Snake模型初始化控制點必須離目標(biāo)區(qū)域很近的缺陷,避免了采用單一PSO算法計算時間較長而且容易收斂于局部極值的不足,并且該方法能在不花費額外執(zhí)行時間的基礎(chǔ)上,可快速收斂到目標(biāo)區(qū)域的凹陷邊界,實現(xiàn)對目標(biāo)輪廓的準(zhǔn)確分割。1生態(tài)性電圖像的局部建模傳統(tǒng)的Snake模型可以定義為一條閉合曲線,由一組排序的點的集合組成:p(s)=[x(s),y(s)]。s表示弧長,x(s),y(s)是輪廓點的x和y坐標(biāo)值,s∈,輪廓線的能量函數(shù)定義如下:ESnake=∫1001EInt(p(s))+EExt(p(s))ds(1)在式(1)中,EInt表示內(nèi)部能量,阻止曲線被拉伸和彎曲;而EExt表示外部能量,推動Snake朝著對象邊界或其他感興趣的特征移動。通常,這兩個能量被定義成如下的形式:EInt(p(s))=12α(s)|ps(s)|2+12β(s)|pss(s)|2(2)EΙnt(p(s))=12α(s)|ps(s)|2+12β(s)|pss(s)|2(2)EExt(p(s))=-γ|?I(p(s))|2(3)其中,α,β,γ是能量函數(shù)的權(quán)值;ps(s)是輪廓對于p(s)的一階導(dǎo)數(shù),它反映了輪廓的彈性,能夠反抗輪廓的拉伸;pss(s)是輪廓對于p(s)的二階導(dǎo)數(shù),它反映了輪廓的剛性,用于反抗彎曲;?I(p(s))是圖像在輪廓附近的梯度,用于吸引主動輪廓趨向于真實邊緣。通過迭代使能量函數(shù)極小化,使最終的主動輪廓線收斂在目標(biāo)的邊界處。換一種表述方式,能量函數(shù)可表示成:ESnake=∫1001F(p,ps,pss)ds(4)F(p,ps,pss)=EExt(p(s))+12α(s)|ps(s)|2+12β(s)|pss(s)|2(5)F(p,ps,pss)=EExt(p(s))+12α(s)|ps(s)|2+12β(s)|pss(s)|2(5)為得到式(4)的最優(yōu)解,可運用變分法,通過解下面的歐拉方程獲得:?EExt-αpss+βpssss=0(6)在仿真實驗中,Snake模型被刻畫成一組具有代表性的控制點,最小化能量函數(shù)的過程正是在這組控制點上迭代完成的。為計算相對位置在qi,j(x,y)周圍的第i個控制點pi的能量,定義該控制點的局部能量函數(shù)如下:Ei,j=EInt+EExt(7)EInt=12α(s)∥pi+1?qi,j∥22+12β(s)∥pi+1?2qi,j+pi?1∥22(8)EΙnt=12α(s)∥pi+1-qi,j∥22+12β(s)∥pi+1-2qi,j+pi-1∥22(8)EExt=-γ‖?I(qi,j)‖2222(9)最佳索引下標(biāo)ki通過計算下式得到:ki=argjminEi,jki=argjminEi,j;j∈Wi,其中Wi是先前指定的對于控制點pi在搜索區(qū)域中的索引集合。由于qi,ki是對于控制點pi的局部最優(yōu)位置,因此通過qi,ki更新第i個控制點pi的位置將使局部能量函數(shù)減少,在所有控制點都被處理以后,將會在目標(biāo)周圍形成一條新的輪廓線。假設(shè)控制點的數(shù)量是n,則總的能量函數(shù)可近似表示成:ESnake=∑i=1nEi,ki(10)ESnake=∑i=1nEi,ki(10)當(dāng)能量函數(shù)ESnake趨于穩(wěn)定時,將終止整個迭代過程。2標(biāo)準(zhǔn)pso算法在PSO算法中,粒子群在一個d維空間中搜索,其中每個粒子所處的位置都表示問題的一個解。粒子通過不斷調(diào)整自己的位置zl,d來搜索新解。PSO初始化為一組隨機(jī)粒子(隨機(jī)解),然后通過迭代找到最優(yōu)解。在每一次迭代中,粒子通過跟蹤兩個“極值”來更新自己:一個是粒子本身所找到的最優(yōu)解,稱之為局部最優(yōu)值PBEST;另一個極值是整個種群目前找到的最優(yōu)解,稱之為全局最優(yōu)值GBEST。設(shè)zl,d(t)和vl,d(t)分別代表在t時刻,粒子在d維空間的位置向量和第l個粒子在種群中的速率,則PSO模型可表示為:vl,d(t)=vl,d(t-1)+c1·φ1·(z*l,d-zl,d(t-1))+c2·φ2·(z#dd#-zl,d(t-1))(11)zl,d(t)=zl,d(t-1)+vl,d(t)(12)其中z*l(PEBST)代表第l個粒子直到t-1時刻的最佳位置,z#(GBEST)代表整個種群直到t-1時刻的最佳位置,φ1和φ2是隨機(jī)數(shù),c1和c2分別代表個體和社會系數(shù)。算法主要步驟描述如下:1)設(shè)定種群的大小,初始化每個隨機(jī)粒子的位置和速度;2)為每個粒子計算其適應(yīng)值,若該粒子的適應(yīng)值好于其歷史最好適應(yīng)值z*l,則將該適應(yīng)值賦予z*l;3)如果整個種群新的最佳位置的適應(yīng)值好于先前種群的,將所有粒子中的最好適應(yīng)值的和賦予z#,作為當(dāng)前全局最優(yōu)值;4)滿足程序終止條件,則終止程序;否則,返回2)通過步驟2)和3)更新粒子的位置和速度。通過近幾年的研究和實踐表明,PSO在動態(tài)目標(biāo)尋優(yōu)方面有著速度快、解質(zhì)量高、魯棒性好等優(yōu)點。對于次優(yōu)解的計算類似于尋找最佳匹配,它能夠獲得更精確的主動輪廓線。然而,如果該最佳解為一局部最優(yōu)點,則算法陷入了局部極值,從而出現(xiàn)其他算法(如遺傳算法)存在的早熟現(xiàn)象。因此本文將多種群PSO運用在ACM中搜索每個控制點的最佳位置。3群pso算法傳統(tǒng)主動輪廓線模型(ACM)的一個主要缺陷是不能收斂于目標(biāo)的凹陷邊界。較小的搜索范圍限制了收斂到目標(biāo)凹陷邊界的可能,但通過擴(kuò)大搜索的范圍,會增加搜索較大區(qū)域的時間開銷。為克服這些缺陷,在本文中用PSO在較大區(qū)域中尋求最佳控制點的位置,并引導(dǎo)控制點很快收斂于凹陷邊界處。多種群PSO用一個種群Oi與主動輪廓線的每個控制點pi相對應(yīng),每個種群運用自己的最佳歷史信息為每個控制點搜索最佳運動軌跡。在這個優(yōu)化過程中,時間代價被定義為局部能量函數(shù)Ei,j。在每次迭代中,基于鄰近種群Oi-1和Oi+1的全局最優(yōu)值和局部能量在每個種群中被計算。當(dāng)每個種群中這些粒子的運動被完成,Oi的全局最優(yōu)值就是pi新的控制點。程序繼續(xù)迭代執(zhí)行,直到ESnake趨于穩(wěn)定。初始化和隨后粒子在Oi中的運動都被限制在一個特定的搜索區(qū)域中。當(dāng)控制點一次次被進(jìn)化時,相應(yīng)的搜索區(qū)域也必須動態(tài)地改變。一個很簡單的方法是選擇一個每個控制點都不能超越的區(qū)域,如果一個粒子運動超出這個區(qū)域,它將被拉回到最近的邊界處,這樣將可避免因動態(tài)變化引發(fā)Snake模型的不正確進(jìn)化。該方法擴(kuò)大搜索窗口,使得目標(biāo)的凹陷邊界能被更加準(zhǔn)確地捕獲,且因個體和種群及相鄰種群間信息的共享,加快了收斂速度。多種群PSO應(yīng)用在主動輪廓模型中,用于搜索每個控制點的最佳位置的整個步驟描述如下:1)為每個控制點初始化一個種群,并為其PBEST和GBEST賦初值;2)為每個控制點pi(xi,yi)分配搜索區(qū)域并修剪出當(dāng)粒子超出搜索區(qū)時到達(dá)的最近區(qū)域邊界;3)為每個粒子z,通過最小化能量函數(shù)E執(zhí)行一趟優(yōu)化操作:4)更新PBEST和GBEST,并為新控制點的GBEST賦值;5)對所有控制點重復(fù)執(zhí)行步驟2)～4);6)計算總能量函數(shù)ESnake;7)當(dāng)ESnake趨于穩(wěn)定時終止程序執(zhí)行,否則轉(zhuǎn)步驟2)。上述算法在每代種群中,個體具有“自我”學(xué)習(xí)和向“他人”學(xué)習(xí)的雙重優(yōu)點并通過共享鄰近種群的信息,使其下一代有針對性地從先輩及鄰近種群那里繼承更多的信息,從而能在較短的時間內(nèi)找到最優(yōu)解,并且具有更好的并行性和全局尋優(yōu)的能力。該算法利用了PSO在尋優(yōu)過程中的優(yōu)勢,基于多種群PSO的主動輪廓線模型克服了傳統(tǒng)ACM對初始值敏感、不能收斂與凹陷邊界等缺點。4輪廓線基本信息本文的實驗環(huán)境為:P4(R)2.4GHzCPU、512MB內(nèi)存;WindowsXP操作系統(tǒng),程序用BorlandC++Builder5.0語言實現(xiàn)。通過對不同的3幅大小均為256×256的圖像的分割,可在圖1～3中看到實驗結(jié)果。在每組圖像中,(a)表示初始控制點,(b)、(c)和(d)分別表示用傳統(tǒng)Snake模型、基于單一PSO算法以及基于多種群PSO算法得到的結(jié)果。對于圖1和圖2的實驗,將ACM的參數(shù)賦值為α=0.2,β=0.65,γ=0.14;圖3的賦值為α=0.01,β=0.89,γ=0.08。圖1的主動輪廓線包含30個控制點,圖2和圖3包含50個控制點,每個控制點對應(yīng)一個種群,每個種群包含9個粒子。對于傳統(tǒng)的Snake模型,圖1是個很簡單的測試,傳統(tǒng)方法、文獻(xiàn)提出的基于單一PSO的方法,以及本文所提出的方法都能正確地收斂在目標(biāo)邊界。圖2是個帶有明顯凹陷邊界的星形圖案,在(b)中可以看到,傳統(tǒng)的Snake不能準(zhǔn)確地收斂于目標(biāo)凹陷邊界處;在(c)中,單一PSO算法較為準(zhǔn)確地收斂于目標(biāo)邊界,而在(d)中,多種群PSO算法卻能準(zhǔn)確地收斂于目標(biāo)凹陷邊界處。圖3是個帶有多目標(biāo)的真實圖像,在(a)中通過初始控制點選擇出目標(biāo)的近似輪廓,試驗中,對于傳統(tǒng)Snake模型方法,搜索區(qū)域設(shè)定為3×3的窗口,經(jīng)過0.023s的執(zhí)行時間,在(b)中可以明顯看到這種傳統(tǒng)的方法并不能準(zhǔn)確地收斂在目標(biāo)邊界。對于采用單一PSO算法進(jìn)行試驗,經(jīng)過0.021s的執(zhí)行時間,在(c)中的結(jié)果表明該方法有陷入局部極值的趨勢,從而無法得到平滑、連續(xù)的輪廓線。然而對于多種群PSO算法,每個種群在包含9個粒子的情況下,執(zhí)行時間卻僅為0.017s,并在(d)中看到所定位的目標(biāo)邊界更加準(zhǔn)確。由以上實驗數(shù)據(jù)可明顯看到,多種群PSO有效地將個體與社會結(jié)合在一起,提高了控制點搜索最優(yōu)位置的速度,將ACM每個控制點與一個種群相對應(yīng),基于鄰近種群的全局最優(yōu)值和每個種群的微粒間的相互作用將每個控制點準(zhǔn)確收斂到目標(biāo)的最佳凹陷邊界處。可見在不增加額外時間開銷的前提下,基于多種群PSO的主動輪廓線模型實現(xiàn)了對目標(biāo)的準(zhǔn)確分割。5主