李巧蘭，盧永祥，盧榮輝

(武夷學(xué)院 信息技術(shù)與實(shí)驗(yàn)室管理中心，福建 龍巖 354300)

為辨識(shí)和分析目標(biāo)，需要將圖像中的目標(biāo)部分分割出來(lái)，在此基礎(chǔ)上才可對(duì)目標(biāo)進(jìn)一步分析利用，由此產(chǎn)生了圖像分割技術(shù)，即分割出圖像中存在目標(biāo)部分的區(qū)域的過(guò)程。因圖像分割的質(zhì)量對(duì)后續(xù)的分析產(chǎn)生直接的影響，所以分割技術(shù)算法的精度至關(guān)重要[1]。當(dāng)前，國(guó)內(nèi)外已經(jīng)提出上千種圖像分割的算法。安霆[2]提出利用遺傳算法處理圖像噪聲，結(jié)合進(jìn)化代數(shù)和個(gè)體的適應(yīng)度值提高了圖像分割的效率。高蕊[3]等學(xué)者提出基于螞蟻算法提取圖像的灰度、梯度和鄰域特征，實(shí)現(xiàn)圖像分割算法的外廓提取。但傳統(tǒng)算法存在分割效率低、精度差、穩(wěn)定性不佳等弊端。

針對(duì)傳統(tǒng)算法的不足，提出了基于改進(jìn)蟻群算法的圖像輪廓高精度分割算法研究，首先構(gòu)建一種圖像分割路徑幾何模型，基于蟻群算法進(jìn)行迭代尋優(yōu)找出最短路徑，并基于GPU技術(shù)修正偏差，完成對(duì)圖像分割的精確計(jì)算和控制。實(shí)驗(yàn)結(jié)果表明，提出的算法設(shè)計(jì)路徑最短、精度高、算法穩(wěn)定性好。

1 一種圖像輪廓目標(biāo)點(diǎn)間距分布式算法研究

1.1 圖像分割路徑幾何模型的構(gòu)建

通常采用圖像分割的圖像的構(gòu)造較為復(fù)雜，由曲線、圓弧、直線等多種元素組成。要準(zhǔn)確地計(jì)算圖像輪廓目標(biāo)點(diǎn)的間距，可以采用一種分布式的計(jì)算模式提高算法的精度[4-5]。首先來(lái)構(gòu)建圖像輪廓目標(biāo)點(diǎn)分割的幾何模型，為圖像分割設(shè)定好工作路徑[6-7]。設(shè)待分割加工的圖像幾何輪廓由直線和圓弧等元素組成，如圖1所示。

圖1 圖像輪廓的幾何圖形

如圖1所示，圖像輪廓由外環(huán)和2個(gè)內(nèi)環(huán)組合而成，外環(huán)和內(nèi)環(huán)都是由邊Ei和定點(diǎn)Ni組合而成，那么外環(huán)可以定義為N11-N16，兩個(gè)內(nèi)環(huán)可以分別定義為N21-N24和N31-N32。圖像輪廓分割時(shí)，要先分割內(nèi)環(huán)，再分割外環(huán)[8]，比如以點(diǎn)N21為開始的分割點(diǎn)，分割后再?gòu)脑擖c(diǎn)逐漸移動(dòng)到其他定點(diǎn)，并充分考慮圖像分割時(shí)對(duì)圖像輪廓形變的影響[9]。

將外環(huán)定義為L(zhǎng)1，內(nèi)環(huán)分別定義為L(zhǎng)2和L3，那么內(nèi)環(huán)L2和L3之間的最短間距，可以使用兩環(huán)定點(diǎn)之間的最短距離dij來(lái)定義[10]：

(1)

其中(xik,yik)和(xjk,yjk)分別為L(zhǎng)2和L3定點(diǎn)的坐標(biāo)。圖像輪廓分割過(guò)程中產(chǎn)生的空行程是外環(huán)與內(nèi)環(huán)距離及內(nèi)環(huán)之間的距離的和[11]，圖像輪廓分割的幾何模型D可以表示為：

D=dij+dik+dik+…+dmo

(2)

圖像輪廓目標(biāo)點(diǎn)間距分布式計(jì)算的目的就是要找到使總距離Dmin最短的路徑[12]?；趯?duì)最短路徑的分析，構(gòu)建圖像輪廓分割的幾何模型，此時(shí)需要找出一條確保空程最短的最優(yōu)行進(jìn)路徑。這是一個(gè)極為復(fù)雜的過(guò)程，需要確定目標(biāo)點(diǎn)的具體位置，并選擇分割順序[13]。不同的目標(biāo)點(diǎn)位置和不同的分割順序都會(huì)產(chǎn)生不同的空程長(zhǎng)度[14]。假設(shè)圖像的環(huán)數(shù)為n，每個(gè)環(huán)的頂點(diǎn)數(shù)量為m1，這時(shí)圖像輪廓分割路徑的條數(shù)ki可以表示為：

(3)

對(duì)于最優(yōu)路徑的選擇問(wèn)題，采用了改進(jìn)蟻群算法，基于螞蟻行進(jìn)路徑中遺留的信息素濃度和啟發(fā)因子的變化情況，進(jìn)行反復(fù)的迭代尋優(yōu)找出最優(yōu)的分割路徑，并提高圖像輪廓目標(biāo)點(diǎn)間距的控制精度。

1.2 基于改進(jìn)蟻群算法圖像輪廓目標(biāo)點(diǎn)間距分布式計(jì)算的實(shí)現(xiàn)

蟻群算法是一種仿生學(xué)算法，適用于路徑尋優(yōu)，蟻群算法易于與其他的方法相結(jié)合、魯棒性高[15]。改進(jìn)的蟻群算法，能夠在圖像輪廓分割過(guò)程中選擇一條最短路徑，并實(shí)現(xiàn)對(duì)圖像輪廓目標(biāo)點(diǎn)間距的最優(yōu)控制。螞蟻在覓食過(guò)程中，基于信息度濃度選擇最短路徑。如果路徑上的信息素的濃度越大，選擇這條路徑的概率就越大。路徑尋優(yōu)的過(guò)程，如圖2所示。

圖2 路徑尋優(yōu)示意圖

A點(diǎn)是蟻巢，F(xiàn)點(diǎn)是食物源，由于從A點(diǎn)到F點(diǎn)之間存在障礙物，因此有兩條繞過(guò)障礙物的路徑供選擇，分別是ABCDEF和ABGHEF，其中設(shè)定ABGHEF路徑中BG與HE段長(zhǎng)度是ABCDEF路徑中BC與DE段長(zhǎng)度的2倍。

假定在蟻巢和食物源之間移動(dòng)螞蟻個(gè)體數(shù)量是200，那么在初始時(shí)刻由于沒有螞蟻個(gè)體通過(guò)，各段路徑上的螞蟻信息素濃度指標(biāo)都為零。當(dāng)螞蟻開始在路徑上移動(dòng)時(shí)，這種行為是隨機(jī)的即在ABCDEF和ABGHEF兩條路徑上都有螞蟻存在。基于概率學(xué)原理，螞蟻個(gè)體選擇兩條路徑的概率是相等的。因此，存在于兩條路徑上的螞蟻數(shù)量是相同的。螞蟻個(gè)體在向前行進(jìn)的過(guò)程中，會(huì)在沿途釋放信息素，如果螞蟻留下的單位信息素相同，根據(jù)上述設(shè)定的ABGHEF與ABCDEF路徑長(zhǎng)度，得出路徑BG與HE段的信息素濃度是BC與DE段的2倍，而后再通過(guò)的螞蟻個(gè)體就會(huì)有較大的概率選擇ABCDEF路徑，這樣就找到了一條到達(dá)食物源的最短路徑。

基于改進(jìn)蟻群算法的圖像輪廓高精度分割算法具有分布式特點(diǎn)。分布式結(jié)構(gòu)[16-18]具有很強(qiáng)的適應(yīng)性，盡管依賴于系統(tǒng)中的個(gè)體行為，但其中某一個(gè)個(gè)體行為的失效又不會(huì)影響系統(tǒng)整體的結(jié)構(gòu)和功能。對(duì)于圖像輪廓分割的路徑優(yōu)化與選擇問(wèn)題，采用基于改進(jìn)蟻群算法的圖像輪廓目標(biāo)點(diǎn)間距計(jì)算模式，體現(xiàn)出了分布式算法的優(yōu)勢(shì)。

螞蟻根據(jù)路徑上的信息素濃度信息選擇路徑，路徑上的信息素隨著螞蟻的移動(dòng)而改變，同時(shí)隨著時(shí)間的推移而揮發(fā)，設(shè)在蟻群中的螞蟻個(gè)體的數(shù)量為a，在t時(shí)刻在路徑i，j上的信息量表示為ζij(t)，bi(t)表示t時(shí)刻在路徑i附近的螞蟻個(gè)體數(shù)量，則有：

(4)

(5)

式(5)中，sij(t)為螞蟻個(gè)體在路徑i，j行進(jìn)的過(guò)程中所釋放的信息量、α為啟發(fā)因子(對(duì)螞蟻行進(jìn)路徑的選擇起到了至關(guān)重要的作用)、β為期望啟發(fā)因子、ξik(t)是局部路徑啟發(fā)函數(shù)，可以表示為：

(6)

基于仿生學(xué)的原理，螞蟻個(gè)體在前進(jìn)過(guò)程中釋放的信息素的濃度會(huì)不斷地增強(qiáng)，同時(shí)隨著時(shí)間的推移，每條路徑的總信息素含量也會(huì)不斷地?fù)]發(fā)，即信息素的濃度是動(dòng)態(tài)可變的，t+n時(shí)刻在路徑i，j上的信息素變化過(guò)程如下：

(7)

式(7)中，Δsij(t)表示信息素的增量，在初始時(shí)刻Δsij(t)為零，用常數(shù)κ表示螞蟻行進(jìn)過(guò)程中在沿途釋放信息素的揮發(fā)系數(shù)，κ?[0,1)，那么(1-κ)即為信息素的殘留系數(shù)。設(shè)lk為螞蟻k在路徑尋優(yōu)時(shí)，所走過(guò)的總路程長(zhǎng)度，τk表示螞蟻沿路釋放信息素的強(qiáng)度，這時(shí)Δsij(t)的求解公式為：

(8)

沿著信息素的增量路徑尋優(yōu)，能夠找到一條最佳的路徑，并能夠保證圖像輪廓目標(biāo)點(diǎn)間距精度最高。經(jīng)典蟻群算法的不足是迭代尋優(yōu)和整個(gè)計(jì)算耗時(shí)都較長(zhǎng)。采用GPU算法將尋優(yōu)過(guò)程中的數(shù)據(jù)進(jìn)行串行計(jì)算和連接，并在GPU上運(yùn)行，實(shí)現(xiàn)對(duì)經(jīng)典蟻群算法的加速。由于改進(jìn)蟻群算法中的全部個(gè)體行為都具有一致性，螞蟻個(gè)體依據(jù)相同的規(guī)則進(jìn)行路徑尋優(yōu)、互不干擾；但螞蟻個(gè)體之間并不直接聯(lián)系，而是采用遺留信息素的形式互相協(xié)作，這樣操作適用于并行運(yùn)算。

采用了改進(jìn)的蟻群算法，對(duì)圖像輪廓目標(biāo)點(diǎn)間距進(jìn)行分布式計(jì)算，基于螞蟻行進(jìn)路徑中的信息素含量來(lái)判定最優(yōu)路徑，并實(shí)現(xiàn)對(duì)圖像輪廓分割的精確控制。

2 實(shí)驗(yàn)部分

為驗(yàn)證所提方法在切割路徑尋優(yōu)和圖像輪廓分割的高精度，進(jìn)行了一組仿真實(shí)驗(yàn)，從實(shí)際路徑長(zhǎng)度、迭代次數(shù)和圖像輪廓分割精度等方面進(jìn)行對(duì)比驗(yàn)證。

2.1 算法參數(shù)設(shè)定

基于改進(jìn)蟻群算法的最優(yōu)路徑尋優(yōu)過(guò)程受到其幾何模型中各種參數(shù)的影響，各種差異化的參數(shù)組合會(huì)對(duì)算法的收斂性能、測(cè)量精度產(chǎn)生不同的影響。路徑尋優(yōu)過(guò)程中的最佳參數(shù)組合，如表1所示。

表1 基于改進(jìn)蟻群算法的參數(shù)組合設(shè)定

2.2 實(shí)驗(yàn)結(jié)果與分析

基于所提方法，在圖像輪廓分割的輪廓目標(biāo)點(diǎn)最短路徑選擇方面具有明顯的優(yōu)勢(shì)，與文獻(xiàn)[2]方法對(duì)比，實(shí)際的分割路徑曲線分別如圖3和圖4所示。

圖3 文獻(xiàn)[2]方法的路徑

圖4 所提方法路徑

兩種算法的路徑長(zhǎng)度統(tǒng)計(jì)，如表2所示。

表2 兩種算法的路徑統(tǒng)計(jì)/mm

分析圖3和圖4的路徑及表2的路徑統(tǒng)計(jì)，所提方法算法的路徑更短、無(wú)交叉、效率更高。文章分析了基于改進(jìn)蟻群算法圖像輪廓高精度切割路徑尋優(yōu)和圖像輪廓分割精度運(yùn)算控制時(shí)的迭代次數(shù)變化曲線，如圖5所示。

圖5 圖形間距精度與迭代次數(shù)的關(guān)系

如圖5所示，所提方法算法在迭代300次時(shí)就能夠?qū)ふ业阶顑?yōu)路徑，其迭代次數(shù)明顯優(yōu)于傳統(tǒng)尋優(yōu)方法。

在圖像輪廓分割精度控制方面，分別采用文獻(xiàn)[2]方法和所提方法算法進(jìn)行運(yùn)算，提取了兩種算法下的精度測(cè)量值與理論值的數(shù)據(jù)對(duì)比結(jié)果，如表3所示。

表3 圖像輪廓目標(biāo)點(diǎn)間距精度控制對(duì)比/mm

表3的數(shù)據(jù)對(duì)比顯示，所提方法更接近理論值，計(jì)算精度更高，說(shuō)明目標(biāo)點(diǎn)兼具精度的控制效果更理想。

3 結(jié)論

圖像分割技術(shù)在圖像識(shí)別分析領(lǐng)域有著十分廣泛的用途。基于此設(shè)計(jì)了一種基于改進(jìn)蟻群算法的圖像輪廓高精度分割算法研究，利用改進(jìn)蟻群算法在迭代尋優(yōu)方面的優(yōu)勢(shì)，識(shí)別出最優(yōu)路徑并提高圖像輪廓目標(biāo)點(diǎn)間距控制方面的精度。