基于GA-LPA算法的船舶圖像識別方法研究

熊　勇,張俊麗，黃立文

(1.武漢理工大學航運學院仿真研究中心; 2.內(nèi)河航運技術(shù)湖北省重點實驗室， 湖北武漢430070;3.湖北工業(yè)大學經(jīng)濟與管理學院， 湖北武漢 430068)

?

基于GA-LPA算法的船舶圖像識別方法研究

熊勇1,2,張俊麗3，黃立文1,2

(1.武漢理工大學航運學院仿真研究中心; 2.內(nèi)河航運技術(shù)湖北省重點實驗室， 湖北武漢430070;3.湖北工業(yè)大學經(jīng)濟與管理學院， 湖北武漢 430068)

摘要：隨著海事監(jiān)管自動化的發(fā)展，大量船舶圖像需要進行自動標注和追蹤，傳統(tǒng)的圖像信息標注方式已經(jīng)不能適應(yīng)海事監(jiān)管的需求，基于內(nèi)容的圖像信息標注技術(shù)在海事監(jiān)管方面得到越來越多的應(yīng)用。標簽傳播算法(label propagation algorithm, LPA)是一種復(fù)雜度較低的模式分類方法，適合于處理船舶圖像的標注和追蹤問題，為此，分別介紹了標簽傳播算法和遺傳算法(genetic algorithm, GA)的原理，分析了LPA算法的參數(shù)確定問題，并針對此問題提出了基于GA的LPA算法，建立了GA-LPA算法用于船舶圖像識別的方法。通過實例進行計算分析，驗證了采用GA-LPA算法進行船舶圖像標注和識別的可行性和效率。

關(guān)鍵詞：海事監(jiān)管；船舶圖像識別；標簽傳播算法；遺傳算法

0引言

為了提高海事監(jiān)管的效率，節(jié)約人力和物力資源，在實際的海事監(jiān)管工作中越來越多的應(yīng)用視頻監(jiān)控技術(shù)，但僅僅攝錄了視頻并不能自動判斷船舶是否有違規(guī)操作等行為，海量的視頻和圖像信息資源需要分析處理，以便追蹤特定船舶的操縱行為，但前提是必需能夠標注特定的船舶，才能對其進行識別和跟蹤。從海量的視頻信息中人工標注特定的船舶，這是非常困難的任務(wù)，將耗費大量的人力和時間，因此如何采用智能方法自動的對視頻圖像中特定的船舶進行標注是一個非常有意義的工作，目前基于內(nèi)容的圖像信息標注已經(jīng)得到越來越多學者的關(guān)注，逐步成為圖像信息資源標注與檢索的關(guān)鍵技術(shù)之一。基本原理是按照一定的頻率從視頻流中采樣，獲得靜態(tài)的圖像樣本，從而提取圖像信息中的顏色、形狀、紋理等特征[1-4]，并將這些特征信息存儲在圖像特征庫中，利用機器學習方法，將這些特征進行相似度匹配，并賦予相應(yīng)的標注，從而實現(xiàn)對特定目標的追蹤。上述方法是將圖像的特征提取和識別過程作為兩個過程來處理，計算過程復(fù)雜，計算量也較大，根據(jù)對象本身的特點，每一個過程都有很多不同的方法可供選擇，并沒有一種通用的算法，所以需要有一種可以將二者結(jié)合并直接實現(xiàn)標注的方法。標簽傳播算法(label propagation algorithm, LPA)LPA是一種利用同一類對象的內(nèi)在特征進行自動標注的半監(jiān)督機器學習算法，適合于用來處理上述問題，但存在著如何確定最優(yōu)參數(shù)的問題，因此，結(jié)合問題的特點，提出一種基于遺傳算法的自動優(yōu)化參數(shù)的GA-LPA算法，并將其應(yīng)用于船舶圖像的自動識別與標準，仿真實驗顯示，該方法可行且具有較高的效率。

1LPA算法

標簽傳播算法[5-8]是一種用于處理數(shù)據(jù)分類的機器學習方法，最早由Zhu X J提出，由于它的復(fù)雜度較低且易于實現(xiàn)，因此得到了較廣泛的傳播和應(yīng)用。它的基本原理是把采樣的數(shù)據(jù)點抽象為多維空間中的點，利用抽象距離來衡量點之間的相似性，然后利用已標注的數(shù)據(jù)點和其他未標注數(shù)據(jù)點之間的相似度對其進行分類標注和判別，從而完成整個數(shù)據(jù)標示和分類的過程[9-11]。由于上述特點，該算法的研究逐漸應(yīng)用工業(yè)、軍事、航運等不同的領(lǐng)域。

1.1LPA算法

令(x1,y1),…,(xl,yl)是已標注數(shù)據(jù)，YL={y1,…,yl}∈{1,…,C}是類別標簽，假設(shè)類別數(shù)C已知，且均存在于標簽數(shù)據(jù)中。令(xl+1,yl+1),…,(xl+u,yl+u)為未標注數(shù)據(jù)，YU={yl+1,…,yl+u}不可觀測，l?u，令數(shù)據(jù)集X={x1,…,xl+u}∈RD。問題轉(zhuǎn)化為從數(shù)據(jù)集X中，利用YL的學習，為未標注數(shù)據(jù)集YU的每個數(shù)據(jù)找到對應(yīng)的標簽。

以數(shù)據(jù)點為節(jié)點的完全連接圖，其邊的權(quán)重計算公式如下：

(1)

其中，dij為兩個數(shù)據(jù)點之間歐氏距離，σ是決定權(quán)重wij的參數(shù)。

T為概率傳遞矩陣，它表示節(jié)點由于相似程度造成的傳播概率，其維度是(l+u)(l+u)，定義：

(2)

其中Tij是節(jié)點j到i的傳播概率。

標注矩陣B維度是C(l+u)，定義為：

Bic=δ(yi,C),

(3)

Bic表示節(jié)點yi是否屬于C類。矩陣B的每行都進行歸一化化處理，確保權(quán)重值計算的準確性。

1.2算法描述

輸入：U為未標注數(shù)據(jù)個數(shù)，l為標注數(shù)據(jù)個數(shù)，C為數(shù)據(jù)種類數(shù)。

輸出：U個未標注信息的標注。

Step 1:利用公式(1)計算邊權(quán)重矩陣wij，得到數(shù)據(jù)間的相似度。

Step 2:根據(jù)wij，利用公式(2)計算節(jié)點j到i的傳播概率Tij。

Step 3:根據(jù)公式(3)定義一個C(l+u)維的標注矩陣B。

Step 4:根據(jù)式(4)重新計算節(jié)點標注矩陣的值，以觀察新的傳播概率頒布情況。

(4)

Step 5:固定已標注數(shù)據(jù)不變，返回step 4，直到Bij收斂。

Step 6:標注數(shù)據(jù)類別，矩陣B的每一行中，值最大的元素對應(yīng)的那一類為此行對應(yīng)的未標注數(shù)據(jù)的類別。

2LPA參數(shù)估計

LPA算法是一種基于完全圖的復(fù)雜度較低機器學習算法，由于它容易理解且便于編程實現(xiàn)，因此在多個領(lǐng)域都有應(yīng)用，目前的研究發(fā)展很快，盡管如此，但算法的標注效果很大程度上取決于其參數(shù)σ的設(shè)置。

根據(jù)標簽傳播算法，距離函數(shù)為：

(5)

wij的值決定于參數(shù)σ，因此如何估計參數(shù)σ的大小，是一個至關(guān)重要的問題。目前有兩種估計方法[12-13]，一是最小生成樹方法，它只能用來估計單參數(shù)，第二種是最小熵方法，可以用來估計單參數(shù)和多參數(shù)。

第一種方法采用克魯斯卡爾(Kruskal)算法來實現(xiàn)，它以所有待分類點作為節(jié)(頂)點，使生成樹的總權(quán)值之和最小。將不同的邊長度排序，然后盡可能每次選擇最小的邊，并且保證這些邊不構(gòu)成回路，只到最后不能減少總的回路長度為止。在執(zhí)行此算法時，當首次遇到一條邊，它的兩個頂點分別屬于不同類別的節(jié)點時，記此邊的“長度”為σ0，則參數(shù)σ=σ0/3，這種方法屬于啟發(fā)式算法，相對簡單粗糙，求得的參數(shù)精細程度不夠，標記效果略差。

(6)

圖1　熵函數(shù)H的圖像Fig.1　Image of entropy function H

根據(jù)前述H(σ1,…,σD)的公式，用Matlab符號計算工具箱可求得其函數(shù)。其圖像見圖1，可以直觀的看到，表面有很多局部極小值點是一個極其復(fù)雜的函數(shù)。

綜上所述，該方法原則上可以求解多參數(shù)的數(shù)據(jù)標記問題，但即使最簡單的二維數(shù)據(jù)標記問題，計算過程也很復(fù)雜，而且存在多個極小值點，所以這些方程組基本上很難求解，即使能求解得到的也是某一個局部極小值點，常規(guī)方法很難得到全局意義下的最小值點，因此如果是三維以至于更高維的數(shù)據(jù)采用這種方法是不可行的。

因此需要采用全局優(yōu)化算法直接求解熵函數(shù)的全局極值點，以避免求解多元偏微分方程的零點問題，獲得最佳的LPA參數(shù)，為此將遺傳算法與熵函數(shù)結(jié)合，設(shè)計基于遺傳算法的標簽傳播算法。

3基于遺傳算法的標簽傳播

3.1遺傳算法

遺傳算法[14](genetic algorithm, GA)是模擬達爾文生物進化論的遺傳選擇和自然淘汰機理的一種計算模型，是通過模擬自然界的進化過程從而獲取問題最優(yōu)解的一種方法，最初由美國Michigan大學Holland教授于1975年提出。該算法是一種全局優(yōu)化搜索算法，具有簡單易用、魯棒性強、適于并行處理、自動獲取優(yōu)化搜索空間、自適應(yīng)調(diào)整搜索路徑及應(yīng)用范圍廣等顯著特點，本文采用遺傳算法采用一種方法直接求解熵函數(shù)H的全局極小值點，并把這一點對應(yīng)的參數(shù)值作為最優(yōu)參數(shù)代入標簽傳播算法完成標記過程，這樣即可以避免對復(fù)雜的熵函數(shù)多次求偏導(dǎo)，又可以避免求解非線性代數(shù)方程組的問題。然后將得到最小熵函數(shù)對應(yīng)參數(shù)，再用此參數(shù)代入標簽傳播算法，從而獲得較好的標簽分類。

遺傳算法的基本思想[15]是用基因代表問題的參數(shù)，用染色體代表問題求解，從一個隨機的種群(初始染色體)開始，根據(jù)特定的適應(yīng)度函數(shù)，對每一代種群計算適應(yīng)度，并按適者生存的原則，從中選擇出適應(yīng)度高的“染色體”進行復(fù)制，再通過組合、交叉、變異等過程，產(chǎn)生更適應(yīng)環(huán)境的新“染色體”群，通過不斷的迭代和遺傳，并收斂到高“適應(yīng)度”值的染色體，這個高“適應(yīng)度”值的染色體便是問題的最優(yōu)解或者次優(yōu)解。

3.2基于遺傳算法的標簽傳播

基于遺傳算法的標簽傳播算法基本步驟為：

①首先計算邊權(quán)重矩陣wij(σ1,…,σD)，它是參數(shù)σ1,…,σD的函數(shù)，以下步驟中所有函數(shù)都是在此基礎(chǔ)上計算出來的，因此都是參數(shù)σ1,…,σD的函數(shù)。

②計算節(jié)點j到i的傳播概率Tij。

③根據(jù)公式(3)定義一個C(l+u)維的標注矩陣B。

⑥采用遺傳算法對熵函數(shù)H進行優(yōu)化求解，找到其對應(yīng)的全局極小值點，及其對應(yīng)的參數(shù)σ1min,…,σDmin，將其代入權(quán)重矩陣wij(σ1,…,σD)，重復(fù)步驟①～④，算出BU的具體值。

⑦標注數(shù)據(jù)類別，根據(jù)最大概率分類的原則，矩陣B的每一行中，值最大的元素對應(yīng)的那一類為此行對應(yīng)的未標注數(shù)據(jù)的類別。

4算法實現(xiàn)及結(jié)果分析

4.1算法實現(xiàn)

以下實例分析了在圖像標記中基于遺傳算法的標簽傳播算法效果以及存在的問題。實驗中有四類圖像，分別是四艘不同的輪船，每一類圖像有四副不同背景不同姿態(tài)的圖組成，選擇每一類中，最上一行的圖作標記，其他三幅不做標記，采用標簽分類算法對剩下的12副未標記的圖像進行標記，并對實驗結(jié)果進行分析。

圖2　船舶追蹤的實驗圖像

利用標簽傳播算法對數(shù)字圖像進行分類，首先需要將它轉(zhuǎn)化為標簽傳播算法可以處理的矢量數(shù)組。不失一般性，只考慮灰度圖像的分類標記，彩色圖像可以先轉(zhuǎn)化為灰度圖像來處理，假定數(shù)字圖像由描述m×n個像素灰度值的矩陣完全決定，將此m×n矩陣按照行的次序依次首尾相接變成一個數(shù)組，這樣每個圖像就轉(zhuǎn)化為一個數(shù)組，在對此數(shù)組采用標簽傳播算法進行分類。例：

當計算出類別概率矩陣后，按概率分類原則，每一副圖像屬于那一類的概率最大，則將其歸于那一類。

4.2實驗結(jié)果分析

計算未標注的十二幅圖像的概率矩陣為，此矩陣的每一行的四個數(shù)對應(yīng)著該副圖像屬于四個類別船舶的概率，從上到下十二行對應(yīng)著圖2中除第一行之外的十二幅圖像，按縱列排列算出的類別概率：

采用20個基因組成的群體，一共迭代150次，粒子的初始范圍是[1.1121e+003，3.3364e+009]。結(jié)果發(fā)現(xiàn)，其標注正確率為75%，最小熵函數(shù)值2.470 5。

以上兩個圖分別是熵函數(shù)和每一代最大最好值隨著迭代步數(shù)變化的曲線，分析標注矩陣BU可以發(fā)現(xiàn)，三幅標記錯誤的圖都是在第一類圖像中，將第一類圖像錯誤的分類到第三類中，主要原因是第一類圖像中的船舶和第三類已標記的船舶外形輪廓比較接近，且沒有做特征提取，所以導(dǎ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é)語

通過上述實驗分析得出結(jié)論：

①標簽算法效果的好壞不僅取決于算法本身，還取決于數(shù)據(jù)之間的“距離”如何定義，對于圖像來說，這種特征可以是顏色特征，例如灰度或者是灰度的某種函數(shù)，或者是邊界特征，或者是紋理特征等等，不同距離定義下，算法的效果也會不一樣。

②標簽算法效果的好壞不僅取決于算法本身，也取決于待標記數(shù)據(jù)本身內(nèi)在的相關(guān)度，例如在其他條件都相同的情況下，幾個不同類別的待識別圖像都采用標簽算法，分類的準確率也會有差別。

③標簽算法對于參數(shù)非常敏感，參數(shù)的設(shè)置除了依賴于優(yōu)化算法，更多的也依賴了先驗知識，即使是采用遺傳算法也需要一個初始值來啟動計算，否則計算時間太長無實際意義，一般來說，這個參數(shù)與所在維度上的“距離”值在同一個數(shù)量級，圍繞著這個值來搜索。

④對于高維數(shù)據(jù)，例如像圖像這樣幾萬或者幾十萬甚至上百萬個像素點的數(shù)據(jù)，如果只有很少的幾類圖像進行標記，則數(shù)據(jù)的維數(shù)遠遠超過類別數(shù)，而數(shù)據(jù)之間的差別特征又足夠多，這種情況下，為標簽算法的每一維設(shè)置一個參數(shù)是不可能也不恰當?shù)模驗橛嬎懔刻螅乙矝]有必要。當需要分類的圖像類別數(shù)較多，而每一個圖像的特征又經(jīng)過二次處理，例如經(jīng)過主成分分析，將像素數(shù)目投影到一個較小維度的特征空間上，使得數(shù)據(jù)的維度和類別數(shù)相差不多時，可以考慮采用多重參數(shù)。

綜上所述，采用標簽傳播算法對船舶圖像進行標注和識別是可行的，但它僅涉及到圖像分類中的某一個環(huán)節(jié)，要想實現(xiàn)其實際應(yīng)用，必須與其他的圖像處理前端算法，如濾波、去噪、特征提取等相結(jié)合，并采用強有力的大型計算機做并行計算，才能達到較高的效率，為海事監(jiān)管自動化提供一個新的渠道。

參考文獻：

[1]劉小白.圖像及視頻語義解析的關(guān)鍵技術(shù)研究[D]. 華中科技大學, 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]孫潔.基于隱支持向量機模型的個性化圖像推薦和檢索[D]. 北京交通大學, 2014.

[7]吳曉, 曹其新.基于顏色和區(qū)域運動目標識別的研究[J]. 廣西大學學報(自然科學版), 2009, 34(3):361-365.

[8]昝杰, 蔡宗琰, 郭瑞.一種基于特征檢測的機器人足球檢測識別方法[J]. 廣西大學學報(自然科學版), 2012, 37(5):913-920.

[9]胡太祥.大規(guī)模圖像標注方法研究[D]. 華中科技大學, 2014.

[10]錢小燕.基于K最鄰近的標簽傳播模型檢測圖像型垃圾郵件的研究[D]. 南京郵電大學, 2014.

[11]陳燁, 邵健, 朱科.基于社群隱含主題挖掘和多社群信息融合的自動圖像標注[J]. 中國圖象圖形學報, 2010, 15(6):944-950.

[12]邵遠杰, 吳國平, 馬麗.屬類概率距離構(gòu)圖的半監(jiān)督高光譜圖像分類[J]. 測繪學報, 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]馬利克, 彭進業(yè), 馮曉毅.遺傳算法優(yōu)化LVQ網(wǎng)絡(luò)的監(jiān)控視頻關(guān)鍵幀內(nèi)容識別[J]. 西北大學學報(自然科學版), 2015，45(4)：573-578.

[15]谷雨,茍書鑫,熊文卓,等.可見光與紅外圖像區(qū)域級反饋融合算法[J]. 中國圖象圖形學報, 2015, 20(4):506-513.

(責任編輯梁碧芬)

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

文獻標識碼：A

文章編號：1001-7445(2016)02-0554-08

doi:10.13624/j.cnki.issn.1001-7445.2016.0554

通訊作者：張俊麗(1982—),女，湖北荊州人，湖北工業(yè)大學講師，博士；E-mail：elili62@126.com。

基金項目：國家自然科學基金資助項目(51379170);國家留學基金資助項目(201208420193)

收稿日期：2015-11-01；

修訂日期：2015-12-21

引文格式：熊勇,張俊麗，黃立文.基于GA-LPA算法的船舶圖像識別方法研究[J].廣西大學學報(自然科學版)，2016，41(2)：554-561.