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

?

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

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

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

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

多假設(shè)跟蹤; 匈牙利算法; 指派問(wèn)題

0 引言

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

1 指派問(wèn)題與匈牙利算法

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

圖1表示效率矩陣是方陣以及非方陣時(shí)的指派問(wèn)題, 可以看出, 當(dāng)問(wèn)題規(guī)模上升后, 指派問(wèn)題的復(fù)雜度增長(zhǎng)很快。

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

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

步驟2: 首先從效率矩陣每行減去該行最小的元素, 再?gòu)拿苛袦p去該列最小的元素, 得到每行每列都至少有1個(gè)0元素的矩陣1;

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

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

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

式中:表示效率矩陣;表示指派方案, 是與同階的邏輯矩陣, 其中邏輯1表示矩陣中對(duì)應(yīng)位置的元素被算法選中, 0表示沒(méi)有選中;為方案對(duì)應(yīng)的總效率。一般來(lái)說(shuō), 認(rèn)為在對(duì)效率矩陣沒(méi)有任何先驗(yàn)認(rèn)識(shí)的條件下, 匈牙利算法是解決指派問(wèn)題的精確且高效的方法。

2 MHT指派問(wèn)題

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

以上3個(gè)假設(shè)保證了MHT數(shù)據(jù)關(guān)聯(lián)問(wèn)題為指派問(wèn)題, MHT中習(xí)慣使用后驗(yàn)的概率密度作為指派問(wèn)題效率矩陣的關(guān)聯(lián)效率, 因此, 一般MHT問(wèn)題的效率矩陣具有如圖2的形式[1]。

因此可以總結(jié)出, MHT的指派問(wèn)題對(duì)應(yīng)的效率矩陣是由1個(gè)完整矩陣和2個(gè)對(duì)角陣組成。另外考慮到MHT問(wèn)題中每個(gè)周期的測(cè)量數(shù)量往往遠(yuǎn)大于活動(dòng)的軌跡個(gè)數(shù), 因此效率矩陣的第1個(gè)部分常常是1個(gè)行數(shù)大于列數(shù)的矩陣。

3 MHT指派問(wèn)題改進(jìn)方法

3.1 問(wèn)題的數(shù)學(xué)化

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

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

3.2 改進(jìn)的方法

首先對(duì)該效率矩陣定義一個(gè)數(shù)列

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

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

步驟2: 將拆分成,,3個(gè)矩陣;

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

4 性能分析與比較

4.1 理論分析

4.2 仿真與結(jié)果

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

為了更加直觀地表示2種方法的運(yùn)算量, 采用控制變量的思想, 在同一臺(tái)計(jì)算機(jī)上用同樣的編程語(yǔ)言使用2種方法解決同一個(gè)指派問(wèn)題, 對(duì)比兩者的運(yùn)算時(shí)間。

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

表1 不同規(guī)模問(wèn)題的計(jì)算時(shí)間對(duì)比

5 結(jié)束語(yǔ)

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

[1] 翟海濤. 多假設(shè)跟蹤算法研究及其應(yīng)用[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] 錢(qián)頌迪. 運(yùn)籌學(xué)[M]. 北京: 清華大學(xué)出版社, 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] 張新輝. 任務(wù)多于人數(shù)的指派問(wèn)題[J]. 運(yùn)籌與管理. 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] 李延鵬, 錢(qián)彥嶺, 李岳. 基于改進(jìn)匈牙利算法的多技能人員調(diào)度方案[J]. 國(guó)防科技大學(xué)學(xué)報(bào), 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] 馬曉娜.“人少任務(wù)多”型指派問(wèn)題的一種新算法[J]. 重慶工商大學(xué)學(xué)報(bào)(自然科學(xué)版), 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.

國(guó)家重點(diǎn)研發(fā)計(jì)劃(2016YFC1400200); 國(guó)家自然科學(xué)基金面上項(xiàng)目(61671388).

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

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

(責(zé)任編輯: 陳 曦)