張雪晶，孫作雷，曾連蓀（上海海事大學 信息工程學院，上海 201306）

基于聯(lián)合相容分支定界的關聯(lián)算法研究

張雪晶，孫作雷，曾連蓀
（上海海事大學 信息工程學院，上海 201306）

聯(lián)合相容分支定界算法（Joint Compatibility Branch and Bound，JCBB）充分考慮傳感器量測之間的相關性和重新匹配關聯(lián)的可能，但計算量隨觀測數(shù)目成指數(shù)增長。為優(yōu)化其計算復雜度和關聯(lián)準確度，以最近鄰算法（Nearest Neighbour，NN）進行關聯(lián)，對符合重復度和經過設定步數(shù)的情況使用JCBB進行特征匹配，并以互斥準則和最優(yōu)準則來提高關聯(lián)準確度。引入機器學習領域的評價測度對改進后算法和JCBB算法進行比較，結果表明，改進后的關聯(lián)算法能夠保證更好的關聯(lián)準確度。

聯(lián)合相容分支定界算法（JCBB）；數(shù)據關聯(lián)；特征匹配；準確度

0　引言

數(shù)據關聯(lián)源于目標跟蹤領域，用于確定傳感器量測信息和目標源之間的對應關系，錯誤的數(shù)據關聯(lián)不僅影響導航和定位精度，甚至會導致整個關聯(lián)算法不一致或者發(fā)散［1］。

Singer等人提出的最近鄰（Nearest Neighbor，NN）［2］算法是最早也是最簡單的數(shù)據關聯(lián)方法，當觀測量和特征之間的統(tǒng)計距離度量最小或者殘差概率密度最大時認為兩者可以關聯(lián)，在環(huán)境特征密度較大的情況下，容易發(fā)生關聯(lián)失敗現(xiàn)象。Bar-Shallom和Jaffer提出的概率數(shù)據關聯(lián)（Probability Data Association，PDA）算法充分利用過去一定時間內的數(shù)據信息，不依賴于過去數(shù)據關聯(lián)的正確性，提高了算法的收斂性，但對計算開銷要求有所提高。對 PDA改進后的聯(lián)合概率數(shù)據關聯(lián)（Joint Probability Data Association，JPDA）［3］算法對所有可能的關聯(lián)假設集合進行搜索，并以此為基礎尋找最優(yōu)關聯(lián)。針對 NN算法忽略環(huán)境特征之間相關性的問題，Jose Neira等人提出了聯(lián)合相容性檢驗（Joint Compatibility test，JC test）算法，檢驗一次觀測獲得的所有觀測和地圖特征之間的聯(lián)合相容性，聯(lián)合相容分支定界（Joint Compatibility Branch and Bound，JCBB）［4］算法能排除一些NN無法排除的關聯(lián)假設，結合分支定界法和相容性的遞增式計算搜索解釋樹的方法來獲得最優(yōu)解。數(shù)據關聯(lián)方法還有多假設數(shù)據關聯(lián)［5］、基于圖論的關聯(lián)算法［6］、惰性數(shù)據關聯(lián)［7］、基于信息理論關聯(lián)［8］等，它們都尋求在計算復雜度和關聯(lián)準確度之間獲得更好效果，在目標跟蹤、數(shù)據融合等領域［9-11］都有廣泛涉及。

在保證計算復雜度不增加的前提下，考慮算法計算復雜度和準確度兩要素，將最近鄰算法與聯(lián)合相容分支定界算法結合使用，并以互斥準則、最優(yōu)準則約束誤關聯(lián)情況，從而提高關聯(lián)準確度，降低錯誤關聯(lián)導致整個算法發(fā)散的可能，進而保證定位和更新精度。

1　問題定義

1.1特征關聯(lián)

移動機器人在導航過程中需要構建環(huán)境地圖并且確定自身在地圖中的位姿，數(shù)據關聯(lián)是機器人在觀測到環(huán)境特征之后對觀測量進行分類應用或整合的過程，用以確定當前的一個或者多個觀測量是否應該對應到地圖中的已有特征以及對應到哪一個特征。

圖1中三角形表示移動機器人，其頂點作為傳感器所在位置，以圓形表示機器人構建地圖中已有的特征點，記為 F1～F5，以方形表示當前傳感器的觀測量 z1～z5，橢圓表示以某種距離度量表示的地圖特征的匹配范圍，忽略傳感器所得觀測量是虛警信息的情況。z1和 z2分別落在F1和F2的可匹配范圍之內，兩對觀測—特征對可以進行匹配；對于z3和F3以及z3和F5均可視為匹配對，若僅以直觀距離最近原則選擇會舍去其與F5的匹配，因其與 F3距離更近；觀測量z4未落在任一特征的匹配范圍內，將其視作待加入地圖的新特征F6。對所有觀測量和特征點進行匹配即完成了數(shù)據關聯(lián)過程，如圖1右圖所示的關聯(lián)結果直接影響地圖創(chuàng)建中特征位置的更新，以及新特征的加入，進而影響機器人自身定位過程。

圖1　數(shù)據關聯(lián)過程

1.2馬氏距離與卡方檢驗

馬氏距離（Mahalanobis Distance）表示數(shù)據協(xié)方差之間的距離，是計算兩個未知樣本集之間相似程度的有效方法。其與歐氏距離的不同在于它考慮不同特征之間的相關性且與測量尺度無關。對均值為μ、協(xié)方差為Σ的

N維觀測量z，其馬氏距離的平方為：

利用Cholesky分解Σ=CCT替換變量，則以變量 y= C-1（z-μ），得：

由此得馬氏距離的平方服從自由度為N的卡方分布。以符合不同自由度和準確度要求的卡方分布檢驗兩個樣本集之間是否足夠相似，這種方法在關聯(lián)問題中得到廣泛應用。

2　算法

2.1聯(lián)合相容分支定界算法

JCBB算法的核心是聯(lián)合相容準則，用以檢驗所有觀測值與地圖特征點之間的相容性。相容性檢驗標準也采用馬氏距離，由于同時考慮所有特征與機器人之間的相關性，其匹配準確度高于最近鄰算法。對于一次關聯(lián)對應假設集為 Hk=｛j1，j2，…，jk｝時，擴展卡爾曼濾波過程中的聯(lián)合觀測方程表示為：

在當前估計狀態(tài)處的線性化過程為：

其中，

聯(lián)合信息及其協(xié)方差為：

聯(lián)合相容檢測準則為：

其中，d是聯(lián)合觀測量的維數(shù)，α是要求的置信度。如果馬氏距離滿足式（7），則認為關聯(lián)解Hk滿足聯(lián)合相容條件。然后對關聯(lián)解空間采用分支定界方法進行遍歷，以配對數(shù)目單調非減規(guī)則為定界條件，以聯(lián)合相容條件為分支準則，搜索并最終決定觀測值和地圖特征點之間的最佳關聯(lián)解。

2.2改進算法

初始使用最近鄰算法對多個觀測值進行數(shù)據關聯(lián)，若無多個觀測值對應同一個特征的情況，則接受所得關聯(lián)結果。若出現(xiàn)干涉現(xiàn)象則調用聯(lián)合相容分支定界算法完成關聯(lián)。若在JCBB關聯(lián)過程中仍出現(xiàn)干涉現(xiàn)象，則以一次關聯(lián)中僅允許一個地圖特征與一個觀測量完成關聯(lián)，若再有此特征關聯(lián)則被拒絕，避免多觀測量對同一地圖特征的重復匹配。

搜索解空間過程若有多個符合最大匹配數(shù)目的關聯(lián)解，最優(yōu)準則選定為：選擇其中 Mahalanobis距離最小的關聯(lián)解作為關聯(lián)結果。

改進算法針對關于計算復雜度的考慮，結合NN計算復雜度低的特點，并以相應準則解決JCBB可能存在的干涉現(xiàn)象和存在多個可能的最優(yōu)解的情況以保證關聯(lián)準確性。

3　實驗

3.1評定指標

引入機器學習中的評價測度對關聯(lián)性能進行評定。以真/假（true/false）說明判斷正誤，以正/負（positive/negative）表示判定結果，正例判定為正例稱為真正（true positive，TP），負例判定為負例稱為真負（true negative，TN），正例判定為負例稱為假負（false negative，F(xiàn)N），負例判定為正例稱為假正（false positive，F(xiàn)P）。準確率（Accuracy）反映關聯(lián)算法的整體判定能力（能將正例判定為正例，負例判定為負例），精確度（Precision）反映判定的正例中真正的正例樣本的比重，召回率（Recall）反映被正確判定的正例占總的正例的比重。用Precision和Recall評估一種算法，當兩者均更高時，才能說明分類算法的性能更優(yōu)于另一種算法。然而事實上兩者在某些情況下是矛盾的，采用評價測度 F Score（F Measure）可以綜合考慮精確度和召回率，它是二者的加權調和平均。Accuracy（記為 A）、Precision（記為 P）、Recall（記為R）、F Score（記為F），依次定義為：

特別地，當參數(shù)a=1時，成為最常見的F1 Score（F1 Measure）測度，即

3.2實驗參數(shù)設置

仿真實驗設置為機器人從世界坐標（0，0）出發(fā)，在規(guī)模為 180 m×250 m的環(huán)境中，沿規(guī)定路徑運動，依據激光測距儀傳回的觀測信息，對環(huán)境中的62個特征點進行定位，并最終返回起始點。仿真參數(shù)設置如下：將生成隨機噪聲的種子設置為23，運動噪聲和觀測噪聲的方差分別設定為：σν=0.7 m/s，σγ=3°；σρ=0.3 m，σb=4°。機器人運動速度為4 m/s，最大轉向角速度為±20°/s，最大轉向角±30°，激光最大掃描距離 30 m，掃描范圍 0°～180°，控制周期和觀測周期均為0.1 s，前后輪間距為4 m。

3.3實驗結果分析

通過圖2～圖5針對不同指標比較結果可知，當改進前關聯(lián)算法的準確率和精確度變低時，改進后算法的準確率和精確度仍保持較高；以召回率和精確度都較高或者以綜合了精確度和召回率的F1 Score作為評價原則，改進后算法關聯(lián)性能都優(yōu)于改進前。調整噪聲參數(shù)，改進后算法仍能保持更優(yōu)的關聯(lián)性能。

4　結束語

針對聯(lián)合相容分支定界算法計算復雜度較高的缺點，為改進其關聯(lián)性能，考慮最近鄰算法計算復雜度低及可能出現(xiàn)的干涉現(xiàn)象和搜索最優(yōu)解可能出現(xiàn)的匹配數(shù)相同的情況，將其與最近鄰算法和最優(yōu)及互斥準則融合，改進算法提高了關聯(lián)準確度，降低了錯誤關聯(lián)引起算法發(fā)散的概率，進而減少機器人對自身位姿和構圖的不確定性。在更復雜環(huán)境下的關聯(lián)方法選擇和計算復雜度處理是待研究的問題。

圖2　實驗準確率結果比較

圖3　實驗精確度結果比較

圖4　實驗召回率結果比較

圖5　實驗F1 Score結果比較

［1］DURRANT-WHYTE H，BAILEY T.Simultaneous localization and mapping：part I［J］.Robotics＆amp；Automation Magazine，IEEE，2006，13（2）：99-110.

［2］BEIS J S，LOWE D G.Shape indexing using approximate nearest-neighbour search in high-dimensional spaces［C］.Proceedings of the IEEE 1997 Computer Society Conference on Computer Vision and Pattern Recognition，1997：1000-1006.

［3］FORTMANN T E，BAR-SHALOM Y，SCHEFFE M.Sonar tracking of multiple targets using joint probabilistic data association［J］.Oceanic Engineering，IEEE Journal of，1983，8 （3）：173-184.

［4］NEIRA J，TARDóS J D.Data association in stochastic mapping using the joint compatibility test［J］.Robotics and Automation，IEEE Transactions on，2001，17（6）：890-897.

［5］COX I J，LEONARD J J.Modeling a dynamic environment using a Bayesian multiple hypothesis approach［J］.Artificial Intelligence，1994，66（2）：311-344.

［6］BAILEY T，NEBOT E M，ROSENBLATT J，et al.Data association for mobile robot navigation：a graph theoretic approach［C］.Robotics and Automation，2000.Proceedings.ICRA′00.IEEE InternationalConference on.2000：2512-2517.

［7］H?HNEL D，THRUN S，WEGBREIT B，et al.Towards lazy data association in SLAM［C］.Robotics Research.2005，Springer：421-431.［8］KAESSM，DELLAERTF.Covariancerecoveryfrom a square rootinformation matrix for data association［J］.Robotics and Autonomous Systems，2009，57（12）：1198-1210.

［9］CHONG C Y，KUMAR S P.Sensor networks：evolution，opportunities，and challenges［J］.Proceedings of the IEEE，2003，91（8）：1247-1256.

［10］DALLIL A，OUSSALAH M，OULDALI A.Sensor fusion and target tracking using evidential data association［J］.Sensors Journal，IEEE，2013，13（1）：285-293.

［11］WU Z，THANGALI A，SCLAROFF S，et al.Coupling detection and data association for multiple object tracking［C］.Computer Vision and Pattern Recognition（CVPR），2012 IEEE Conference on.2012：1948-1955.

Study on association algorithm based on joint compatibility branch and bound

Zhang Xuejing，Sun Zuolei，Zeng Liansun
（College of Information Engineering，Shanghai Maritime University，Shanghai 201306，China）

Joint Compatibility Branch and Bound Algorithm （JCBB）takes full account of the relevance and possible re-match association between sensor measurements，but the amount of computation increases exponentially with the number of observations.To optimize its computational complexity and association accuracy，we use the Nearest Neighbor algorithm（NN）to associate，when meet the repeatability and get to the number of steps set，employ JCBB for feature matching，and use exclusive criteria and optimal criteria to improve the relevance accuracy.we introduce evaluation measures in the field of machine learning to compare the improved algorithm and JCBB algorithm.The results show that the improved association algorithm ensures better association accuracy.

Joint Compatibility Branch and Bound algorithm（JCBB）；data association；feature matching；accuracy

TP242

A

1674-7720（2015）15-0082-03

張雪晶，孫作雷，曾連蓀.基于聯(lián)合相容分支定界的關聯(lián)算法研究［J］.微型機與應用，2015，34（15）：82-84，88.

2015-04-06）

張雪晶（1989-），女，碩士，主要研究方向：移動機器人導航。

孫作雷（1982-），男，博士，副教授，主要研究方向：移動機器人導航、多傳感器融合、機器學習。

曾連蓀（1962-），男，教授，主要研究方向：定位導航系統(tǒng)。