基于聯合相容分支定界的關聯算法研究

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

基于聯合相容分支定界的關聯算法研究

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

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

聯合相容分支定界算法（JCBB）；數據關聯；特征匹配；準確度

0　引言

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

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

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

1　問題定義

1.1特征關聯

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

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

圖1　數據關聯過程

1.2馬氏距離與卡方檢驗

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

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

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

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

2　算法

2.1聯合相容分支定界算法

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

在當前估計狀態處的線性化過程為：

其中，

聯合信息及其協方差為：

聯合相容檢測準則為：

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

2.2改進算法

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

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

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

3　實驗

3.1評定指標

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

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

3.2實驗參數設置

仿真實驗設置為機器人從世界坐標（0，0）出發，在規模為 180 m×250 m的環境中，沿規定路徑運動，依據激光測距儀傳回的觀測信息，對環境中的62個特征點進行定位，并最終返回起始點。仿真參數設置如下：將生成隨機噪聲的種子設置為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針對不同指標比較結果可知，當改進前關聯算法的準確率和精確度變低時，改進后算法的準確率和精確度仍保持較高；以召回率和精確度都較高或者以綜合了精確度和召回率的F1 Score作為評價原則，改進后算法關聯性能都優于改進前。調整噪聲參數，改進后算法仍能保持更優的關聯性能。

4　結束語

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

圖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

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

2015-04-06）

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

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

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