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

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

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

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

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

0　引言

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

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

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

1　問題定義

1.1特征關(guān)聯(lián)

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

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

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

1.2馬氏距離與卡方檢驗

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

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

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

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

2　算法

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

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

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

其中，

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

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

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

2.2改進算法

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

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

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

3　實驗

3.1評定指標

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

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

3.2實驗參數(shù)設(shè)置

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

3.3實驗結(jié)果分析

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

4　結(jié)束語

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

圖2　實驗準確率結(jié)果比較

圖3　實驗精確度結(jié)果比較

圖4　實驗召回率結(jié)果比較

圖5　實驗F1 Score結(jié)果比較

［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)合相容分支定界的關(guān)聯(lián)算法研究［J］.微型機與應(yīng)用，2015，34（15）：82-84，88.

2015-04-06）

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

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

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