熊 勇,張俊麗,黃立文
(1.武漢理工大學(xué)航運(yùn)學(xué)院仿真研究中心; 2.內(nèi)河航運(yùn)技術(shù)湖北省重點(diǎn)實(shí)驗(yàn)室, 湖北武漢430070;3.湖北工業(yè)大學(xué)經(jīng)濟(jì)與管理學(xué)院, 湖北武漢 430068)
?
基于GA-LPA算法的船舶圖像識別方法研究
熊勇1,2,張俊麗3,黃立文1,2
(1.武漢理工大學(xué)航運(yùn)學(xué)院仿真研究中心; 2.內(nèi)河航運(yùn)技術(shù)湖北省重點(diǎn)實(shí)驗(yàn)室, 湖北武漢430070;3.湖北工業(yè)大學(xué)經(jīng)濟(jì)與管理學(xué)院, 湖北武漢 430068)
摘要:隨著海事監(jiān)管自動化的發(fā)展,大量船舶圖像需要進(jìn)行自動標(biāo)注和追蹤,傳統(tǒng)的圖像信息標(biāo)注方式已經(jīng)不能適應(yīng)海事監(jiān)管的需求,基于內(nèi)容的圖像信息標(biāo)注技術(shù)在海事監(jiān)管方面得到越來越多的應(yīng)用。標(biāo)簽傳播算法(label propagation algorithm, LPA)是一種復(fù)雜度較低的模式分類方法,適合于處理船舶圖像的標(biāo)注和追蹤問題,為此,分別介紹了標(biāo)簽傳播算法和遺傳算法(genetic algorithm, GA)的原理,分析了LPA算法的參數(shù)確定問題,并針對此問題提出了基于GA的LPA算法,建立了GA-LPA算法用于船舶圖像識別的方法。通過實(shí)例進(jìn)行計(jì)算分析,驗(yàn)證了采用GA-LPA算法進(jìn)行船舶圖像標(biāo)注和識別的可行性和效率。
關(guān)鍵詞:海事監(jiān)管;船舶圖像識別;標(biāo)簽傳播算法;遺傳算法
0引言
為了提高海事監(jiān)管的效率,節(jié)約人力和物力資源,在實(shí)際的海事監(jiān)管工作中越來越多的應(yīng)用視頻監(jiān)控技術(shù),但僅僅攝錄了視頻并不能自動判斷船舶是否有違規(guī)操作等行為,海量的視頻和圖像信息資源需要分析處理,以便追蹤特定船舶的操縱行為,但前提是必需能夠標(biāo)注特定的船舶,才能對其進(jìn)行識別和跟蹤。從海量的視頻信息中人工標(biāo)注特定的船舶,這是非常困難的任務(wù),將耗費(fèi)大量的人力和時(shí)間,因此如何采用智能方法自動的對視頻圖像中特定的船舶進(jìn)行標(biāo)注是一個非常有意義的工作,目前基于內(nèi)容的圖像信息標(biāo)注已經(jīng)得到越來越多學(xué)者的關(guān)注,逐步成為圖像信息資源標(biāo)注與檢索的關(guān)鍵技術(shù)之一?;驹硎前凑找欢ǖ念l率從視頻流中采樣,獲得靜態(tài)的圖像樣本,從而提取圖像信息中的顏色、形狀、紋理等特征[1-4],并將這些特征信息存儲在圖像特征庫中,利用機(jī)器學(xué)習(xí)方法,將這些特征進(jìn)行相似度匹配,并賦予相應(yīng)的標(biāo)注,從而實(shí)現(xiàn)對特定目標(biāo)的追蹤。上述方法是將圖像的特征提取和識別過程作為兩個過程來處理,計(jì)算過程復(fù)雜,計(jì)算量也較大,根據(jù)對象本身的特點(diǎn),每一個過程都有很多不同的方法可供選擇,并沒有一種通用的算法,所以需要有一種可以將二者結(jié)合并直接實(shí)現(xiàn)標(biāo)注的方法。標(biāo)簽傳播算法(label propagation algorithm, LPA)LPA是一種利用同一類對象的內(nèi)在特征進(jìn)行自動標(biāo)注的半監(jiān)督機(jī)器學(xué)習(xí)算法,適合于用來處理上述問題,但存在著如何確定最優(yōu)參數(shù)的問題,因此,結(jié)合問題的特點(diǎn),提出一種基于遺傳算法的自動優(yōu)化參數(shù)的GA-LPA算法,并將其應(yīng)用于船舶圖像的自動識別與標(biāo)準(zhǔn),仿真實(shí)驗(yàn)顯示,該方法可行且具有較高的效率。
1LPA算法
標(biāo)簽傳播算法[5-8]是一種用于處理數(shù)據(jù)分類的機(jī)器學(xué)習(xí)方法,最早由Zhu X J提出,由于它的復(fù)雜度較低且易于實(shí)現(xiàn),因此得到了較廣泛的傳播和應(yīng)用。它的基本原理是把采樣的數(shù)據(jù)點(diǎn)抽象為多維空間中的點(diǎn),利用抽象距離來衡量點(diǎn)之間的相似性,然后利用已標(biāo)注的數(shù)據(jù)點(diǎn)和其他未標(biāo)注數(shù)據(jù)點(diǎn)之間的相似度對其進(jìn)行分類標(biāo)注和判別,從而完成整個數(shù)據(jù)標(biāo)示和分類的過程[9-11]。由于上述特點(diǎn),該算法的研究逐漸應(yīng)用工業(yè)、軍事、航運(yùn)等不同的領(lǐng)域。
1.1LPA算法
令(x1,y1),…,(xl,yl)是已標(biāo)注數(shù)據(jù),YL={y1,…,yl}∈{1,…,C}是類別標(biāo)簽,假設(shè)類別數(shù)C已知,且均存在于標(biāo)簽數(shù)據(jù)中。令(xl+1,yl+1),…,(xl+u,yl+u)為未標(biāo)注數(shù)據(jù),YU={yl+1,…,yl+u}不可觀測,l?u,令數(shù)據(jù)集X={x1,…,xl+u}∈RD。問題轉(zhuǎn)化為從數(shù)據(jù)集X中,利用YL的學(xué)習(xí),為未標(biāo)注數(shù)據(jù)集YU的每個數(shù)據(jù)找到對應(yīng)的標(biāo)簽。
以數(shù)據(jù)點(diǎn)為節(jié)點(diǎn)的完全連接圖,其邊的權(quán)重計(jì)算公式如下:
(1)
其中,dij為兩個數(shù)據(jù)點(diǎn)之間歐氏距離,σ是決定權(quán)重wij的參數(shù)。
T為概率傳遞矩陣,它表示節(jié)點(diǎn)由于相似程度造成的傳播概率,其維度是(l+u)(l+u),定義:
(2)
其中Tij是節(jié)點(diǎn)j到i的傳播概率。
標(biāo)注矩陣B維度是C(l+u),定義為:
Bic=δ(yi,C),
(3)
Bic表示節(jié)點(diǎn)yi是否屬于C類。矩陣B的每行都進(jìn)行歸一化化處理,確保權(quán)重值計(jì)算的準(zhǔn)確性。
1.2算法描述
輸入:U為未標(biāo)注數(shù)據(jù)個數(shù),l為標(biāo)注數(shù)據(jù)個數(shù),C為數(shù)據(jù)種類數(shù)。
輸出:U個未標(biāo)注信息的標(biāo)注。
Step 1:利用公式(1)計(jì)算邊權(quán)重矩陣wij,得到數(shù)據(jù)間的相似度。
Step 2:根據(jù)wij,利用公式(2)計(jì)算節(jié)點(diǎn)j到i的傳播概率Tij。
Step 3:根據(jù)公式(3)定義一個C(l+u)維的標(biāo)注矩陣B。
Step 4:根據(jù)式(4)重新計(jì)算節(jié)點(diǎn)標(biāo)注矩陣的值,以觀察新的傳播概率頒布情況。
(4)
Step 5:固定已標(biāo)注數(shù)據(jù)不變,返回step 4,直到Bij收斂。
Step 6:標(biāo)注數(shù)據(jù)類別,矩陣B的每一行中,值最大的元素對應(yīng)的那一類為此行對應(yīng)的未標(biāo)注數(shù)據(jù)的類別。
2LPA參數(shù)估計(jì)
LPA算法是一種基于完全圖的復(fù)雜度較低機(jī)器學(xué)習(xí)算法,由于它容易理解且便于編程實(shí)現(xiàn),因此在多個領(lǐng)域都有應(yīng)用,目前的研究發(fā)展很快,盡管如此,但算法的標(biāo)注效果很大程度上取決于其參數(shù)σ的設(shè)置。
根據(jù)標(biāo)簽傳播算法,距離函數(shù)為:
(5)
wij的值決定于參數(shù)σ,因此如何估計(jì)參數(shù)σ的大小,是一個至關(guān)重要的問題。目前有兩種估計(jì)方法[12-13],一是最小生成樹方法,它只能用來估計(jì)單參數(shù),第二種是最小熵方法,可以用來估計(jì)單參數(shù)和多參數(shù)。
第一種方法采用克魯斯卡爾(Kruskal)算法來實(shí)現(xiàn),它以所有待分類點(diǎn)作為節(jié)(頂)點(diǎn),使生成樹的總權(quán)值之和最小。將不同的邊長度排序,然后盡可能每次選擇最小的邊,并且保證這些邊不構(gòu)成回路,只到最后不能減少總的回路長度為止。在執(zhí)行此算法時(shí),當(dāng)首次遇到一條邊,它的兩個頂點(diǎn)分別屬于不同類別的節(jié)點(diǎn)時(shí),記此邊的“長度”為σ0,則參數(shù)σ=σ0/3,這種方法屬于啟發(fā)式算法,相對簡單粗糙,求得的參數(shù)精細(xì)程度不夠,標(biāo)記效果略差。
(6)
圖1 熵函數(shù)H的圖像Fig.1 Image of entropy function H
根據(jù)前述H(σ1,…,σD)的公式,用Matlab符號計(jì)算工具箱可求得其函數(shù)。其圖像見圖1,可以直觀的看到,表面有很多局部極小值點(diǎn)是一個極其復(fù)雜的函數(shù)。
綜上所述,該方法原則上可以求解多參數(shù)的數(shù)據(jù)標(biāo)記問題,但即使最簡單的二維數(shù)據(jù)標(biāo)記問題,計(jì)算過程也很復(fù)雜,而且存在多個極小值點(diǎn),所以這些方程組基本上很難求解,即使能求解得到的也是某一個局部極小值點(diǎn),常規(guī)方法很難得到全局意義下的最小值點(diǎn),因此如果是三維以至于更高維的數(shù)據(jù)采用這種方法是不可行的。
因此需要采用全局優(yōu)化算法直接求解熵函數(shù)的全局極值點(diǎn),以避免求解多元偏微分方程的零點(diǎn)問題,獲得最佳的LPA參數(shù),為此將遺傳算法與熵函數(shù)結(jié)合,設(shè)計(jì)基于遺傳算法的標(biāo)簽傳播算法。
3基于遺傳算法的標(biāo)簽傳播
3.1遺傳算法
遺傳算法[14](genetic algorithm, GA)是模擬達(dá)爾文生物進(jìn)化論的遺傳選擇和自然淘汰機(jī)理的一種計(jì)算模型,是通過模擬自然界的進(jìn)化過程從而獲取問題最優(yōu)解的一種方法,最初由美國Michigan大學(xué)Holland教授于1975年提出。該算法是一種全局優(yōu)化搜索算法,具有簡單易用、魯棒性強(qiáng)、適于并行處理、自動獲取優(yōu)化搜索空間、自適應(yīng)調(diào)整搜索路徑及應(yīng)用范圍廣等顯著特點(diǎn),本文采用遺傳算法采用一種方法直接求解熵函數(shù)H的全局極小值點(diǎn),并把這一點(diǎn)對應(yīng)的參數(shù)值作為最優(yōu)參數(shù)代入標(biāo)簽傳播算法完成標(biāo)記過程,這樣即可以避免對復(fù)雜的熵函數(shù)多次求偏導(dǎo),又可以避免求解非線性代數(shù)方程組的問題。然后將得到最小熵函數(shù)對應(yīng)參數(shù),再用此參數(shù)代入標(biāo)簽傳播算法,從而獲得較好的標(biāo)簽分類。
遺傳算法的基本思想[15]是用基因代表問題的參數(shù),用染色體代表問題求解,從一個隨機(jī)的種群(初始染色體)開始,根據(jù)特定的適應(yīng)度函數(shù),對每一代種群計(jì)算適應(yīng)度,并按適者生存的原則,從中選擇出適應(yīng)度高的“染色體”進(jìn)行復(fù)制,再通過組合、交叉、變異等過程,產(chǎn)生更適應(yīng)環(huán)境的新“染色體”群,通過不斷的迭代和遺傳,并收斂到高“適應(yīng)度”值的染色體,這個高“適應(yīng)度”值的染色體便是問題的最優(yōu)解或者次優(yōu)解。
3.2基于遺傳算法的標(biāo)簽傳播
基于遺傳算法的標(biāo)簽傳播算法基本步驟為:
①首先計(jì)算邊權(quán)重矩陣wij(σ1,…,σD),它是參數(shù)σ1,…,σD的函數(shù),以下步驟中所有函數(shù)都是在此基礎(chǔ)上計(jì)算出來的,因此都是參數(shù)σ1,…,σD的函數(shù)。
②計(jì)算節(jié)點(diǎn)j到i的傳播概率Tij。
③根據(jù)公式(3)定義一個C(l+u)維的標(biāo)注矩陣B。
⑥采用遺傳算法對熵函數(shù)H進(jìn)行優(yōu)化求解,找到其對應(yīng)的全局極小值點(diǎn),及其對應(yīng)的參數(shù)σ1min,…,σDmin,將其代入權(quán)重矩陣wij(σ1,…,σD),重復(fù)步驟①~④,算出BU的具體值。
⑦標(biāo)注數(shù)據(jù)類別,根據(jù)最大概率分類的原則,矩陣B的每一行中,值最大的元素對應(yīng)的那一類為此行對應(yīng)的未標(biāo)注數(shù)據(jù)的類別。
4算法實(shí)現(xiàn)及結(jié)果分析
4.1算法實(shí)現(xiàn)
以下實(shí)例分析了在圖像標(biāo)記中基于遺傳算法的標(biāo)簽傳播算法效果以及存在的問題。實(shí)驗(yàn)中有四類圖像,分別是四艘不同的輪船,每一類圖像有四副不同背景不同姿態(tài)的圖組成,選擇每一類中,最上一行的圖作標(biāo)記,其他三幅不做標(biāo)記,采用標(biāo)簽分類算法對剩下的12副未標(biāo)記的圖像進(jìn)行標(biāo)記,并對實(shí)驗(yàn)結(jié)果進(jìn)行分析。
圖2 船舶追蹤的實(shí)驗(yàn)圖像
利用標(biāo)簽傳播算法對數(shù)字圖像進(jìn)行分類,首先需要將它轉(zhuǎn)化為標(biāo)簽傳播算法可以處理的矢量數(shù)組。不失一般性,只考慮灰度圖像的分類標(biāo)記,彩色圖像可以先轉(zhuǎn)化為灰度圖像來處理,假定數(shù)字圖像由描述m×n個像素灰度值的矩陣完全決定,將此m×n矩陣按照行的次序依次首尾相接變成一個數(shù)組,這樣每個圖像就轉(zhuǎn)化為一個數(shù)組,在對此數(shù)組采用標(biāo)簽傳播算法進(jìn)行分類。例:
當(dāng)計(jì)算出類別概率矩陣后,按概率分類原則,每一副圖像屬于那一類的概率最大,則將其歸于那一類。
4.2實(shí)驗(yàn)結(jié)果分析
計(jì)算未標(biāo)注的十二幅圖像的概率矩陣為,此矩陣的每一行的四個數(shù)對應(yīng)著該副圖像屬于四個類別船舶的概率,從上到下十二行對應(yīng)著圖2中除第一行之外的十二幅圖像,按縱列排列算出的類別概率:
采用20個基因組成的群體,一共迭代150次,粒子的初始范圍是[1.1121e+003,3.3364e+009]。結(jié)果發(fā)現(xiàn),其標(biāo)注正確率為75%,最小熵函數(shù)值2.470 5。
以上兩個圖分別是熵函數(shù)和每一代最大最好值隨著迭代步數(shù)變化的曲線,分析標(biāo)注矩陣BU可以發(fā)現(xiàn),三幅標(biāo)記錯誤的圖都是在第一類圖像中,將第一類圖像錯誤的分類到第三類中,主要原因是第一類圖像中的船舶和第三類已標(biāo)記的船舶外形輪廓比較接近,且沒有做特征提取,所以導(dǎo)致其“距離較短”,總體來說,依靠如此粗糙的“距離”特征,能達(dá)到這樣的分類效果,說明標(biāo)簽傳播算法本身有良好的內(nèi)在穩(wěn)定性。
圖3熵函數(shù)隨迭代次數(shù)變化的圖像
Fig.3Entropy function image with
the number of iterations
圖4每一步迭代的最好、最差和平均熵函
Fig.4The best, worst and average entropy
function values of each iteration step
5結(jié)語
通過上述實(shí)驗(yàn)分析得出結(jié)論:
①標(biāo)簽算法效果的好壞不僅取決于算法本身,還取決于數(shù)據(jù)之間的“距離”如何定義,對于圖像來說,這種特征可以是顏色特征,例如灰度或者是灰度的某種函數(shù),或者是邊界特征,或者是紋理特征等等,不同距離定義下,算法的效果也會不一樣。
②標(biāo)簽算法效果的好壞不僅取決于算法本身,也取決于待標(biāo)記數(shù)據(jù)本身內(nèi)在的相關(guān)度,例如在其他條件都相同的情況下,幾個不同類別的待識別圖像都采用標(biāo)簽算法,分類的準(zhǔn)確率也會有差別。
③標(biāo)簽算法對于參數(shù)非常敏感,參數(shù)的設(shè)置除了依賴于優(yōu)化算法,更多的也依賴了先驗(yàn)知識,即使是采用遺傳算法也需要一個初始值來啟動計(jì)算,否則計(jì)算時(shí)間太長無實(shí)際意義,一般來說,這個參數(shù)與所在維度上的“距離”值在同一個數(shù)量級,圍繞著這個值來搜索。
④對于高維數(shù)據(jù),例如像圖像這樣幾萬或者幾十萬甚至上百萬個像素點(diǎn)的數(shù)據(jù),如果只有很少的幾類圖像進(jìn)行標(biāo)記,則數(shù)據(jù)的維數(shù)遠(yuǎn)遠(yuǎn)超過類別數(shù),而數(shù)據(jù)之間的差別特征又足夠多,這種情況下,為標(biāo)簽算法的每一維設(shè)置一個參數(shù)是不可能也不恰當(dāng)?shù)?,因?yàn)橛?jì)算量太大,而且也沒有必要。當(dāng)需要分類的圖像類別數(shù)較多,而每一個圖像的特征又經(jīng)過二次處理,例如經(jīng)過主成分分析,將像素?cái)?shù)目投影到一個較小維度的特征空間上,使得數(shù)據(jù)的維度和類別數(shù)相差不多時(shí),可以考慮采用多重參數(shù)。
綜上所述,采用標(biāo)簽傳播算法對船舶圖像進(jìn)行標(biāo)注和識別是可行的,但它僅涉及到圖像分類中的某一個環(huán)節(jié),要想實(shí)現(xiàn)其實(shí)際應(yīng)用,必須與其他的圖像處理前端算法,如濾波、去噪、特征提取等相結(jié)合,并采用強(qiáng)有力的大型計(jì)算機(jī)做并行計(jì)算,才能達(dá)到較高的效率,為海事監(jiān)管自動化提供一個新的渠道。
參考文獻(xiàn):
[1]劉小白.圖像及視頻語義解析的關(guān)鍵技術(shù)研究[D]. 華中科技大學(xué), 2012.
[2]MATSUMOTO Y.Ship image recognition using HOG[J]. Journal of Japan Institute of Navigation, 2013, 129:105-112.
[3]KAO C H, HSIEH S P, PENG C C.Study of feature-based image capturing and recognition algorithm[C]// Control Automation and Systems (ICCAS), 2010 International Conference on. Kunming, China: IEEE, 2010:1855-1861.
[4]ZHAO Z, JI K, XING X, et al.Adaptive CFAR detection of ship targets in high resolution SAR imagery[J]. Proceedings of SPIE——The International Society for Optical Engineering, 2013, 8917(3):89170L-89170L-8.
[5]ZHU X J, GHAHRAMANI Z.Learning from labeled and unlabeled data with label propagation: Technical report CMU-CALD-02-107[R]. Pittsburghers, USA: Carnegie Mellon University, 2002:1-8.
[6]孫潔.基于隱支持向量機(jī)模型的個性化圖像推薦和檢索[D]. 北京交通大學(xué), 2014.
[7]吳曉, 曹其新.基于顏色和區(qū)域運(yùn)動目標(biāo)識別的研究[J]. 廣西大學(xué)學(xué)報(bào)(自然科學(xué)版), 2009, 34(3):361-365.
[8]昝杰, 蔡宗琰, 郭瑞.一種基于特征檢測的機(jī)器人足球檢測識別方法[J]. 廣西大學(xué)學(xué)報(bào)(自然科學(xué)版), 2012, 37(5):913-920.
[9]胡太祥.大規(guī)模圖像標(biāo)注方法研究[D]. 華中科技大學(xué), 2014.
[10]錢小燕.基于K最鄰近的標(biāo)簽傳播模型檢測圖像型垃圾郵件的研究[D]. 南京郵電大學(xué), 2014.
[11]陳燁, 邵健, 朱科.基于社群隱含主題挖掘和多社群信息融合的自動圖像標(biāo)注[J]. 中國圖象圖形學(xué)報(bào), 2010, 15(6):944-950.
[12]邵遠(yuǎn)杰, 吳國平, 馬麗.屬類概率距離構(gòu)圖的半監(jiān)督高光譜圖像分類[J]. 測繪學(xué)報(bào), 2014,43(11):1182-1189.
[13]COOKE T, MARTORELLA M, HAYWOOD B, et al.Use of 3D ship scatterer models from ISAR image sequences for target recognition[J]. Digital Signal Processing, 2006, 16(5):523-532.
[14]馬利克, 彭進(jìn)業(yè), 馮曉毅.遺傳算法優(yōu)化LVQ網(wǎng)絡(luò)的監(jiān)控視頻關(guān)鍵幀內(nèi)容識別[J]. 西北大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015,45(4):573-578.
[15]谷雨,茍書鑫,熊文卓,等.可見光與紅外圖像區(qū)域級反饋融合算法[J]. 中國圖象圖形學(xué)報(bào), 2015, 20(4):506-513.
(責(zé)任編輯梁碧芬)
Study on ship image recognition based on GA-LPA algorithm
XIONG Yong1,2, ZHANG Jun-li3, HUANG Li-wen1,2
(1.Simulate Center of School of Navigation, Wuhan University of Technology;2.Hubei Key Laboratory of Inland Shipping Technology, Wuhan 430070,China;3.College of Economic and Management, Hubei University of Technology, Wuhan 430068, China)
Abstract:With the development of maritime supervision automation, a large number of ship images need automatic tagging and tracking. The traditional image information annotation could not meet the needs of maritime supervision, so image annotation technology based on content have been applied in maritime supervision. The label propagation algorithm (LPA) is a kind of semi supervised learning algorithm based on graph, suitable for treatment of ship image tagging and tracking problems. The principles of label propagation algorithm and genetic algorithm (GA) are introduced, and the LPA algorithm's parameters are analyzed, and the LPA algorithm based on GA (named GA-LPA) for ship image recognition is proposed. By the calculation and analysis of the examples, the feasibility and efficiency of the ship image annotation and recognition based on GA-LPA algorithm are verified.
Key words:marine supervision; ship image recognition; label propagation algorithm; genetic algorithm
中圖分類號:TP277
文獻(xiàn)標(biāo)識碼:A
文章編號:1001-7445(2016)02-0554-08
doi:10.13624/j.cnki.issn.1001-7445.2016.0554
通訊作者:張俊麗(1982—),女,湖北荊州人,湖北工業(yè)大學(xué)講師,博士;E-mail:elili62@126.com。
基金項(xiàng)目:國家自然科學(xué)基金資助項(xiàng)目(51379170);國家留學(xué)基金資助項(xiàng)目(201208420193)
收稿日期:2015-11-01;
修訂日期:2015-12-21
引文格式:熊勇,張俊麗,黃立文.基于GA-LPA算法的船舶圖像識別方法研究[J].廣西大學(xué)學(xué)報(bào)(自然科學(xué)版),2016,41(2):554-561.