Study on the Hungarian algorithm for the maximum likelihood data association problem

被引：14

作者：

Wang Jianguo ^{[1
]}

He Peikun ^{[2
]}

Cao Wei ^{[1
]}

机构：

[1] China Aerosp Sci & Ind Corp, Acad 2, Beijing 100854, Peoples R China

[2] Beijing Inst Technol, Dept Elect Engn, Beijing 100081, Peoples R China

来源：

JOURNAL OF SYSTEMS ENGINEERING AND ELECTRONICS | 2007年 / 18卷 / 01期

关键词：

tracking; data association; linear programming; Hungarian algorithm;

D O I：

10.1016/S1004-4132(07)60045-0

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

A specialized Hungarian algorithm was developed here for the maximum likelihood data association problem with two implementation versions due to presence of false alarms and missed detections. The maximum likelihood data association problem is formulated as a bipartite weighted matching problem. Its duality and the optimality conditions are given. The Hungarian algorithm with its computational steps, data structure and computational complexity is presented. The two implementation versions, Hungarian forest (HF) algorithm and Hungarian tree (HT) algorithm, and their combination with the naive auction initialization are discussed. The computational results show that HT algorithm is slightly faster than HF algorithm and they are both superior to the classic Munkres algorithm.

引用

页码：27 / 32

页数：6