基于Mean Shift算法的多目標識別與仿真

韓光威，顧力偉，劉 詠

(中國船舶重工集團公司第七二三研究所，江蘇 揚州225101)

0 引 言

隨著電子信息和計算機系統的迅猛發展，現代戰爭中的信息化作戰也越來越重要。目標識別是指利用光學儀器、雷達、聲納和計算機等設備對目標的敵我屬性、類型的判別[1]。目標識別系統作為現代信息化作戰平臺上進行區分敵我的重要手段，對目標識別系統進行多目標識別的研究具有重要的意義。

目標識別系統進行目標識別時影響因素較多，受外界地形環境的干擾復雜，不同影響因素間具有相互的干擾作用，因此基于規則或專家系統的方法也變得越來越困難[24]。基于聚類的方法能夠通過分析系統采集的數據來得到我方目標的數據信息，而通過分析實時數據和我方目標的差異可以進行目標的識別。同時，由于系統信號傳輸的不確定性和一些外界因素，導致采集的系統數據中會出現離群數據點，這些離群點導致一些傳統的聚類方法，如DBSCAN 等存在一些不足，影響聚類的效果。

本文針對目標識別系統的上述特性，提出了一種基于Mean Shift的改進聚類算法，能夠在聚類的同時診斷出離群數據點，避免其對分類效果造成不利影響；同時由于系統聚類比較的是通過Mean Shift算法得到的數據密度中心點，能夠進行精確的目標識別，避免了DBSCAN 的數據邊界點造成的聚類異常；在實際在線測試過程中，也能夠達到較好的識別結果。

1 基于Mean Shift算法的建模

1.1 基于Mean Shift的聚類算法

Mean Shift算法能夠自適應地搜索空間中樣本分布密度增加最大的方向，并最終收斂到此密度峰值點，進而識別出數據的局部聚類特征[56]。由于Mean Shift算法不需要具有任何先驗知識，并且能夠處理任意特征空間，只有移動窗口的參數需要調節，所以Mean Shift 算法比較適合處理復雜的數據。

Mean Shift向量的最基本形式可定義為：

式中：S h是一個半徑為h的高維球區域；(x i-x)是樣本點x i相對于基準點x的偏移量；M h(x)是落入區域S h中的t個樣本點相對于點x的偏移向量的均值。

如圖1所示，圖中圓形區域為S h，小圓圈代表落入S h區域的t個樣本點x i，黑點是Mean Shift的基準點x，箭頭表示樣本點相對于基準點x的偏移向量。由圖1可看出，偏移向量M h(x)會指向樣本分布密度最大的方向。經Mean迭代計算，不斷用M h(x)的向量計算結果更新基準點x，當滿足‖M h(x)‖小于某容許誤差條件時即可獲得收斂到的穩態聚類中心點[7]。

圖1 Mean Shift示意圖

由于各樣本點與基準點的距離不同，所以在處理偏移向量時要對不同的偏移距離取不同的權重。一般而言，離基準點越近的點對估計當前區域的密度具有較大的作用。為解決這一問題，在此引入高斯核函數G(x)。運用高斯核函數能夠單調地反映樣本點與基準點之間距離與樣本點的權重關系。此時，向量M h(x)化為：

1.2 離線建模流程

多目標識別系統的離線建模流程如下：

(1)采集目標識別系統的歷史數據，包括我方目標和敵方不同目標的數據信息作為建模數據，并標準化處理。

(2)將已知我方數據信息和某一類的敵方目標的數據信息作為輸入數據，運用Mean Shift方法得到2類輸入數據的密度中心點。

(3)將2類密度中心點作為聚類中心點，同時不斷擴大搜索半徑來賦予輸入數據標簽，直到2類數據發生重疊或者所有數據全部分類完畢。

(4)對比分類完成后的標簽和已知輸入標簽，如果標簽正確率在90%以上，則說明建模成功。此時對比分析聚類中心，找到中心距離最大的前n個特征，得到特征值的序號，作為目標的模型f k，每一個k對應一種敵方的目標，即：

1.3 多目標的在線識別

由1.2可知，本文的多目標識別系統的輸入是一批已知的我方目標的數據信息和在線的未知的一個批次的數據。在線識別時需要采集1 個批次(1個時間段)的在線數據與一批我方目標的數據進行輸入分析，運用基于Mean Shift的算法進行在線聚類分析，如果輸入的2類數據能夠成功聚成2類，即聚類后的標簽與輸入標簽一致，即說明輸入的2類數據具有一定的差異性，同時得到一個與離線建模類似的模型向量f。對在線診斷得到的模型向量f匹配已離線建模的模型向量f k，這里匹配f和f k中相同的項，進而進行系統的多目標識別。

2 實驗結果仿真分析

這里結合相關資料給出4組離線實驗數據，其中1組我方目標，3組其他目標的數據，這里定義為敵方目標A，敵方目標B，敵方目標C。在每組數據中隨機取20個作為建模數據，其余數據作為測試數據。Mean Shift算法選取的核函數的主要參數為帶寬h。

經過多次實驗比較，當選取h=3 時能夠取得較好的聚類效果。圖2顯示了我方目標與敵方目標A 數據的聚類結果分析。敵方目標A與我方目標的密度中心點距離(采用歐氏距離)d1，樣本數據與目標A數據的密度中心點距離d2，隸屬度即d2/(d1+d2)，在一定程度上反映了數據與我方目標的相似程度。

圖2 基于Mean Shift算法的敵方目標A 聚類結果

和傳統的Kmeans和DBSCAN 算法對比發現，如果采用傳統Kmeans聚類算法會出現分類異常的情況。如圖3所示，可以看到由于第25個樣本點是離群數據，與其他數據的距離較大，采用Kmeans算法進行聚類時，會把離群數據單獨分為一類，無法有效進行聚類。

圖3 敵方目標A 的Kmeans聚類結果

和基于密度的經典算法DBSCAN相比，DBSCAN 算法雖然也能有效處理噪聲離群點，但是需要反復調試來確定鄰域半徑和半徑內包括的最小樣本點數。圖4給出了在2個維度上的聚類結果。

圖4 敵方目標A 的DBSCAN 聚類結果

同時DBSCAN在某些情況下效果不佳，DBSCAN 利用密度的連通性，本質上是通過尋找某一點周圍距離較近的點來進行算法迭代，如果某一目標與我方目標類似，導致數據與我方之間的差異不明顯，這時會導致出現某些數據與我方目標某些數據距離較近，導致分類效果不佳[8]。以敵方目標B為例來進行說明。圖5給出所有樣本點與第5個樣本點的距離，圖中前20個為我方目標數據，其余為敵方目標B 的數據，可以看到第21和29個樣本點距離第1個樣本點很近。所以無論如何選取鄰域半徑都無法得到較好的聚類結果。

圖5 敵方目標B樣本點距離比較結果

而采用基于Mean Shift的改進聚類算法，本質上是通過比較樣本數據與密度中心點的距離，可以有效地處理這種情況，聚類結果如圖6所示。

從圖2和圖6可以看到，基于Mean Shift的改進聚類算法，能夠有效處理離群點問題，避免其對聚類造成不利影響，同時診斷出離群點，方便對離群點的干擾信息進行分析。

圖6 基于Mean Shift算法的敵方目標B聚類結果

通過選取訓練數據進行基于Mean Shift聚類建模，可以得到敵方目標A、敵方目標B、敵方目標C的模型庫，再選取各類測試數據進行測試，目標識別結果如表1所示。

表1 多目標識別結果分析

3 結束語

本文針對目標識別系統的多目標識別問題，提出了一種基于Mean Shift原理的改進聚類算法，能夠對目標進行良好的聚類，同時診斷出離群點，避免離群數據對聚類效果的不利影響，相比于傳統的Kmeans和DBSCAN，具有更好的聚類效果。并且通過對比分析密度中心點，得到不同目標的模型向量，在在線識別時，通過聚類得到的模型向量進行匹配，能夠準確地進行在線的多目標識別。