多假設跟蹤中的高效匈牙利算法研究

趙偉康, 韓一娜, 張浩宇, 楊益新, 劉清宇

?

多假設跟蹤中的高效匈牙利算法研究

趙偉康1, 韓一娜1, 張浩宇1, 楊益新1, 劉清宇2

(1. 西北工業(yè)大學 航海學院, 陜西 西安, 710072; 2. 海軍研究院, 北京, 100073)

作為多假設跟蹤技術中的一項核心算法, 匈牙利算法占用了多假設跟蹤中大部分的運算時間?？紤]到多假設跟蹤中的指派問題具有其特殊性, 即其效率矩陣是稀疏的, 文中提出了一種對效率矩陣進行降維的處理方法, 給出了運算流程, 對比了該方法與傳統(tǒng)匈牙利算法在處理較大效率矩陣時的耗時, 結果表明, 在確保與傳統(tǒng)匈牙利算法結果一致的前提下, 該方法能夠大幅度降低運算量。

多假設跟蹤; 匈牙利算法; 指派問題

0 引言

在理想假設條件下, 多假設跟蹤(multiple hypothesis tracking, MHT)算法被認為是處理數據關聯的最優(yōu)方法[1]。區(qū)別于其他所有數據關聯技術, MHT算法對所有可能的關聯方案都維持一個假設, 并用一個樹狀結構來保存和管理這些假設, 該假設樹隨著掃描周期的推進進行橫向和縱向的生長, 總體規(guī)模呈指數增長的趨勢, 因此原始的MHT算法本質上是一種窮舉尋優(yōu)的方法。龐大的假設樹為MHT算法帶來了很大的運算量, 作為一種應用于工程實踐中的算法, 需要抑制這種極快的問題規(guī)模增長, 目前成熟的MHT架構中包含了基于Murty算法[2]的-best策略以及-scan的枝剪策略[3], 前者用于控制假設樹橫向規(guī)模, 后者用來限制假設樹深度。其中-best策略用以保留同一個假設下概率最大的個子假設而不是所有的子假設, 因此這就涉及到如何獲得關聯場景下概率最大分配的問題, 即MHT中的指派問題。匈牙利算法[4]目前在很多問題的求解中被應用[5-10], 也存在一些對匈牙利算法的改進策略。但MHT中的指派問題有其特殊性, 即其效率矩陣是稀疏的, 這提供了改進的空間。針對MHT中指派問題的特殊性, 文中提出了一種先將原效率矩陣降階并運行匈牙利算法然后再還原成原效率矩陣對應解的方法, 在不破壞MHT架構的基礎上可大幅度降低運算量。

1 指派問題與匈牙利算法

匈牙利算法最初由匈牙利數學家Edmonds于1965年提出, 用于解決二分圖匹配問題, 后來該方法被推廣應用到了帶有權值的二分匹配問題, 即指派問題中。指派問題指的是在一個矩陣中尋找若干個不沖突的元素, 使得他們的和最大或最小, 在求最大值的問題中該矩陣稱為效率矩陣。指派問題和匈牙利算法是運籌學中的經典案例。

圖1表示效率矩陣是方陣以及非方陣時的指派問題, 可以看出, 當問題規(guī)模上升后, 指派問題的復雜度增長很快。

匈牙利算法的基本步驟如下[5]。

步驟1:獲得指派問題的效率矩陣0(×);

步驟2: 首先從效率矩陣每行減去該行最小的元素, 再從每列減去該列最小的元素, 得到每行每列都至少有1個0元素的矩陣1;

步驟3: 尋找最少的直線覆蓋1中的0元素得到2, 如果最少直線數等于, 轉入步驟5, 否則轉入步驟4;

步驟4:2中未被覆蓋的元素減去這些元素中最小的元素, 同時在直線的交點加上該元素, 得到矩陣取代1轉入步驟3;

步驟5: 從0元素最少的行或列開始指派, 直到各行各列都存在指派, 得到最優(yōu)指派方案。

式中:表示效率矩陣;表示指派方案, 是與同階的邏輯矩陣, 其中邏輯1表示矩陣中對應位置的元素被算法選中, 0表示沒有選中;為方案對應的總效率。一般來說, 認為在對效率矩陣沒有任何先驗認識的條件下, 匈牙利算法是解決指派問題的精確且高效的方法。

2 MHT指派問題

MHT算法一般包含假設生成、假設組合和枝剪、假設管理等過程, 指派問題發(fā)生在假設的組合與枝剪過程, 此時MHT需要獲取當前測量值所有關聯情況的假設, 而將這些假設全部列舉出來是不現實的。針對這一點, 指派問題的效率矩陣提供了一種直觀表示所有假設的方法, 它依賴于MHT中的幾條基本假設: 1) 同一個測量只能關聯于當前的1個軌跡, 或成為雜波(虛警), 或成為新軌跡的起點; 2) 每個活動的軌跡在每個周期最多只關聯于1個測量, 或被判斷為漏報; 3) 所有雜波和新軌跡起點間沒有關聯性。

以上3個假設保證了MHT數據關聯問題為指派問題, MHT中習慣使用后驗的概率密度作為指派問題效率矩陣的關聯效率, 因此, 一般MHT問題的效率矩陣具有如圖2的形式[1]。

因此可以總結出, MHT的指派問題對應的效率矩陣是由1個完整矩陣和2個對角陣組成。另外考慮到MHT問題中每個周期的測量數量往往遠大于活動的軌跡個數, 因此效率矩陣的第1個部分常常是1個行數大于列數的矩陣。

3 MHT指派問題改進方法

3.1 問題的數學化

將效率矩陣從MHT情景中剝離出來, 重新表示成如下更為普遍的形式:

圖3中表示的矩陣最終是一個×(+2)的矩陣, 稱為原始效率矩陣, 將矩陣劃分成×的矩陣,階對角陣和, 即=[,,]。顯然將矩陣直接輸入到式(1)表示的標準匈牙利算法可以獲得最大效率和對應的指派方案, 但匈牙利算法在該類型的效率矩陣中產生了很多無意義的運算。主要原因是矩陣中大部分的信息集中在矩陣中, 而矩陣的規(guī)模常常遠大于矩陣, 考慮到匈牙利算法較大的運算復雜度, 直接對矩陣運行匈牙利算法效率很低。

3.2 改進的方法

首先對該效率矩陣定義一個數列

因此該方法包含了如下的步驟:

步驟1: 獲得原始效率矩陣;

步驟2: 將拆分成,,3個矩陣;

步驟3: 按照式(3)的規(guī)則獲得矩陣;

4 性能分析與比較

4.1 理論分析

4.2 仿真與結果

表示一次掃描獲得的量測數,表示huod2的軌跡數, 在最理想的跟蹤環(huán)境下效率矩陣的每一列會存在一個值遠大于其他值, 而且這些值不會出現在同一行, 此時匈牙利算法的意義并不明顯。仿真時考慮最不理想的情況, 即量測中沒有十分明顯與軌跡關聯的值, 矩陣,,中的元素為均勻分布的隨機數, 由此組成的原始效率矩陣是對2個方法最不友好的。

為了更加直觀地表示2種方法的運算量, 采用控制變量的思想, 在同一臺計算機上用同樣的編程語言使用2種方法解決同一個指派問題, 對比兩者的運算時間。

由表1可見, 在和比較接近時, 改進方法效率提升了近1倍, 在明顯小于時, 改進方法的優(yōu)勢更加明顯, 能大幅下降輸入匈牙利算法的矩陣規(guī)模, 效率上升了數十倍。

表1 不同規(guī)模問題的計算時間對比

5 結束語

文中提出了一種適合在MHT中使用的改進的匈牙利算法, 特點是運用在MHT中能保證獲得與匈牙利算法完全一致的指派結果, 而運算復雜度較后者有很大的降低。該方法嵌入到MHT算法中表現穩(wěn)定。

[1] 翟海濤. 多假設跟蹤算法研究及其應用[J]. 信息化研究. 2010, 36(8): 25-27.Zhai Hai-tao. Reseach on Multiple Hypothesis Tracking Algorithm and Its Application[J]. Informatization Research, 2010, 36(8): 25-27.

[2] Murty K G. An Algorithm for Ranking All the Assignments in Order of Increasing of Cost[J]. Operations Research, 1968, 16: 682-687.

[3] Miller M L, Stone H S, Cox I J. Optimi-z-i-n-g Murty’s Ranked Assignment Method[J]. NEC Research Institute, Technical Report, 1997, 33(3): 851-862.

[4] 錢頌迪. 運籌學[M]. 北京: 清華大學出版社, 1998.

[5] Chin-Jung Huang. Integrate the Hungarian Method and Genetic Algorithm to Solve the Shortest Distance Problem[C]//2012 Third International Conference on Digital Manufacturi-ng & Automation. Guilin, China: IEEE, 2012: 496-499.

[6] Patel R R, Desai T T, Patel S J. Scheduling of Jobs based on Hungarian Method in Cloud Computing[C]//2017 International Conference on Inventive Communication and Computational Technologies(ICI-C-C-T). Coimbatore, India: IEEE, 2017: 6-9.

[7] Yan Chao-bo, Zhao Qian-chuan. Advances in Assignment Problem and Comparison of Algorithns[C]//27th Chinese Control Conference. Kunming, China: IEEE, 2008: 607-611.

[8] 張新輝. 任務多于人數的指派問題[J]. 運籌與管理. 1997, 6(3): 20-25.Zhang Xin-hui. Assignment Problem with Tasks More than the Number of Persons[J]. Operations Research and Manage- ment Science, 1997, 6(3): 20-25.

[9] 李延鵬, 錢彥嶺, 李岳. 基于改進匈牙利算法的多技能人員調度方案[J]. 國防科技大學學報, 2016, 38(2): 144-149.Li Yan-peng, Qian Yan-ling, Li Yue. Multi-skilled Labor Allocating Method Based on Improved Hungary Algorithm[J]. Journal of National University of Defense Technology, 2016, 38(2): 144-149.

[10] 馬曉娜.“人少任務多”型指派問題的一種新算法[J]. 重慶工商大學學報(自然科學版), 2014, 31(12): 68-75.Ma Xiao-na. A New Algorithm for Assignment Problems with “Tasks More Than the Number of Persons”[J]. Journal of Chongqing Technology and Business University: Natural Science Edition, 2014, 31(12): 68-75.

An Improved Hungarian Algorithm for Multiple Hypothesis Tracking

ZHAO Wei-kang1, HAN Yi-na1, ZHANG Hao-yu1, YANG Yi-xin1, LIU Qing-yu2

(1. School of Marine and Technology, Northwestern Polytechnical University, Xi’an 710072, China; 2. Naval Research Academy, Beijing 100073, China)

Hungarian algorithm is a core algorithm in multiple hypothesis tracking technology, and it takes up most of the computation time in multiple hypothesis tracking(MHT). Considering that the assignment problem in the MHT has particularity, i.e., the efficiency matrix is sparse, this paper proposes a method for reducing the dimension of the efficiency matrix, and the computation flow is given. Comparison of the time consumption between the proposed method and traditional Hungarian algorithm in dealing with larger efficiency matrix shows that the proposed method greatly reduces the amount of computation while ensuring consistency with the results of the Hungarian algorithm.

multiple hypothesis tracking(MHT); Hungarian algorithm; assignment problem

TJ67; O224

A

2096-3920(2018)05-0444-05

10.11993/j.issn.2096-3920.2018.05.011

2016-11-19;

2016-12-18.

國家重點研發(fā)計劃(2016YFC1400200); 國家自然科學基金面上項目(61671388).

趙偉康(1995-), 男, 在讀碩士, 主要研究融合跟蹤算法。

趙偉康, 韓一娜, 張浩宇, 等. 多假設跟蹤中的高效匈牙利算法研究[J]. 水下無人系統(tǒng)學報, 2018, 26(5): 444-448.

(責任編輯: 陳 曦)