Một cách đánh giá hiệu suất cho thuật toán đa giả thuyết theo dõi đa mục tiêu

Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CBES2, 04 - 2018 215
MỘT CÁCH ĐÁNH GIÁ HIỆU SUẤT CHO THUẬT TOÁN 
ĐA GIẢ THUYẾT THEO DÕI ĐA MỤC TIÊU 
Nguyễn Thị Hằng1,*, Nguyễn Văn Hùng2, Nguyễn Thị Hiền1, Lê Thị Hương Giang1 
Tóm tắt: Theo dõi mục tiêu là một yêu cầu thiết yếu cho hệ thống giám sát sử dụng 
một hoặc nhiều cảm biến cùng với các hệ thống máy tính thứ cấp. Theo dõi đa giả 
thuyết (MHT-Multiple Hypothesis Tracking) là phương pháp thường được sử dụng để 
giải quyết vấn đề liên kết dữ liệu trong bài toán theo dõi nhiều mục tiêu (MTT- 
Multiple Target Tracking) hiện đại. Trong bài báo này, chúng tôi đề xuất một phương 
pháp đánh giá hiệu suất của thuật toán đa giả thuyết theo dõi đa mục tiêu dựa vào 
xác suất phát hiện các mục tiêu, thể hiện qua các thông số quan trọng như: tỷ lệ tín 
hiệu trên nhiễu SNR, xác suất phát hiện quỹ đạo, ngưỡng phát hiện mục tiêu. 
Từ khóa: Thuật toán đa giả thuyết; Theo dõi đa mục tiêu; Quỹ đạo; Ngưỡng phát hiện; Hiệu suất thuật toán. 
1. ĐẶT VẤN ĐỀ 
Thuật toán theo dõi đa giả thuyết (MHT-Multiple Hypothesis Tracking) được giới thiệu 
lần đầu tiên vào cuối những năm 1970 [7]. Đã có không ít cải tiến nhằm cải thiện thuật 
toán, nhưng cho đến nay MHT vẫn là một trong những thuật toán quan trọng trong lĩnh 
vực theo dõi, bám mục tiêu. 
Việc đánh giá hiệu suất phát hiện quỹ đạo và mật độ báo động giả được thực hiện bằng 
cách sử dụng các mô hình chuỗi Markov [2]. Trong một hệ thống theo dõi thực tế, đường 
đi của một quỹ đạo phụ thuộc vào một cơ chế rất phức tạp. Các phân tích tiên nghiệm về 
hiệu suất theo dõi trong các quỹ đạo chuẩn đã được trình bày trong các tài liệu [4-6]. Tuy 
nhiên, các kết quả phân tích đạt được chủ yếu dựa trên sự đơn giản hoá các mô hình mục 
tiêu - cảm biến và các thuật toán. 
Thuật toán MHT đã được phổ biến kể từ công trình tiên phong của Reid [7] và được 
ứng dụng trong nhiều mô hình mục tiêu - cảm biến phức tạp [8] đã chỉ ra rằng trên thực tế 
thuật toán theo dõi đa giả thuyết tổng quát là phương án tối ưu trong một tập hợp các điều 
kiện nhất định, nếu như tài nguyên tính toán không giới hạn. Tuy nhiên, ngay cả khi tài 
nguyên là không giới hạn, việc tính toán hiệu suất của thuật toán này là rất khó khăn. Một 
số phân tích hiệu suất thông qua mô phỏng Monte Carlo đã được thực hiện trong [8], 
nhưng chỉ cho các mô hình mục tiêu - cảm biến rất đơn giản. 
Dữ liệu đầu vào cho thuật toán trong bài báo này được giả định nhận từ radar trong hệ 
thống giám sát. Hiệu suất theo dõi được đo bằng hai giá trị chính: 1) xác suất thiết lập quỹ 
đạo từ các dữ liệu đo thu được từ mục tiêu qua hệ thống radar, và 2) mật độ báo động giả 
trong một đơn vị giám sát trên một đơn vị thời gian. Hai đại lượng trên còn được gọi là 
đặc tính vận hành của hệ thống theo dõi, tồn tại song song với các đặc tính hoạt động của 
máy thu cảm biến hoặc hệ thống xử lý tín hiệu. 
Trong bài báo này, chúng tôi đề xuất một cách đánh giá hiệu suất của thuật toán MHT 
theo dõi đa mục tiêu dựa vào xác suất phát hiện các mục tiêu, phương pháp đánh giá hiệu 
suất này được thể hiện thông qua các thông số quan trọng là: 1) tỷ số tín hiệu trên nhiễu 
(SNR), 2) xác suất phát hiện quỹ đạo và 3) ngưỡng phát hiện mục tiêu. Bài báo gồm 4 
phần, phần 1 là phần đặt vấn đề, phần này giới thiệu lịch sử ra đời của thuật toán và hướng 
tiếp cận của nhóm tác giả. Phần 2 mô tả ngắn gọn thuật toán đa giả thuyết được sử dụng 
trong hệ thống theo dõi. Phần 3 trình bày cách thiết lập mô phỏng và các kết quả mô 
phỏng; phần 4 là kết luận và đề xuất hướng nghiên cứu tiếp theo. 
Toán học, Cơ học & Ứng dụng 
 N. T. Hằng, , L. T. H. Giang, “Một cách đánh giá hiệu suất  theo dõi đa mục tiêu.” 216 
2. CƠ SỞ LÝ THUYẾT CỦA THUẬT TOÁN THEO DÕI ĐA GIẢ THUYẾT 
(MULTIPLE-HYPOTHESIS TRACKING ALGORITHM) 
Giả sử chúng ta có một bộ dữ liệu 1 2, , ...Z Z . Mỗi tập dữ liệu là một bộ các giá trị 
đo từ một bộ cảm biến kS tại cùng thời điểm kt . Như vậy, mỗi tập dữ liệu kZ lần lượt là 
một chuỗi các phép đo hữu hạn: 
( ) ( ) ( )
1 2 , ( ), ,  k
k k k
k MZ y y y (1) 
trong bộ dữ liệu Zk có kM các giá trị đo. Ta đặt: 
 1
( ) , ... , k kZ Z Z (2) 
Chúng ta sẽ: 
- Tìm xác suất hậu nghiệm của các mục tiêu đã được phát hiện trong ( )kZ ; 
- Tìm phân bố xác suất hậu nghiệm của các trạng thái mục tiêu. 
Ta định nghĩa tập chỉ số độ đo: 
  1,..., k kJ M (3) 
Với mỗi k ta có tập chỉ số tích luỹ của tập chỉ số độ đo, ký hiệu là: 
 ( ) { | } K k kJ J k K (4) 
Một quỹ đạo tại k , trên ( )kZ hay ( )kJ là tập con bất kỳ nào đó của tập chỉ số tích luỹ 
của tập chỉ số độ đo. Ví dụ một quỹ đạo 1 3 , 1 ,3;  j j trên (3)J giả thuyết một 
mục tiêu được phát hiện trong lần quét đầu tiên 1 k , có chỉ số 1j , không được phát hiện 
trong lần quét thứ 2, 2 k , và sau đó lại được phát hiện trong lần quét thứ 3, 3 k , có 
chỉ số 3j . Một giả thuyết liên kết dữ liệu tại k , hoặc tương đương trong 
( )kZ hay ( )kJ , 
chỉ đơn thuần là một tập quỹ đạo tại thời điểm k . Một giả thuyết liên kết dữ liệu được gọi 
đơn giản là "giả thuyết". 
Giả sử: 1) Các đối tượng là phân biệt và chỉ xuất hiện một lần tại một thời điểm. 
2) Các đối tượng không chia tách hoặc hợp nhất tại mọi thời điểm. 
Giả sử rằng các mục tiêu là độc lập cùng phân phối và số các mục tiêu có phân phối 
Poisson, ta có công thức sau (xem[8]): 
 
   
( ) ( 1)( | ) . ( | ). ( | ) | (( , ) , , ) .
( ) | ( { }) ; ; . ( ) |{( , )} . ( ) | ( , )
k k
r r j
k NT j FA j
P Z C P Z L y i j
M J k y j k y i k
      
        
  
   

    
(5) 
trong đó: 
1) ( )kZ là tập tích luỹ của dữ liệu được tính đến thời điểm k bao gồm cả kZ . 
2)  là một giả thuyết tuỳ ý tại thời điểm thứ k . 
3) C là hằng số chuẩn hoá. 
4) Cho một quỹ đạo  trong ( )kZ ,  là một quỹ đạo trong ( 1) kZ và là tiền thân của quỹ 
đạo  , và được định nghĩa như sau: 
( 1)   kJ (6) 
ở đây, có thể trống. 
5) Cho một giả thuyết  trong ( )kZ ,  là một giả thuyết trong ( 1) kZ và là tiền thân của 
 , được định nghĩa như sau: 
( 1) ( 1){ | } \{ } { | ; }           k kJ J (7) 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CBES2, 04 - 2018 217
ở đây,  có thể trống. 
6) L(y | ) là hàm hợp lý của ky Z với điều kiện biết quỹ đạo ; theo 
nghĩa ( | )
 Y L y dy là xác suất của mục tiêu được giả định có quỹ đạo  và nhận giá trị 
y trong Y . Hàm hợp lý này được cho bởi: 
( 1)( | ) ( | ). ( ). ( , | , )  
k
M D kL y P y x P x P x t Z dx (8) 
7) |.MP x là hàm mật độ xác suất của giá trị đo (.) cho một trạng thái mục tiêu x , chính 
xác hơn ( | )
 Y L y x dy là xác suất có điều kiện của một trạng thái mục tiêu x có giá trị 
trong tập dữ liệu kZ , tạo ra một phép đo có giá trị y trong Y . 
8) ( )DP x là xác suất phát hiện mục tiêu x trong tập dữ liệu kZ . 
9) 
( 1)( , | , ) kkP x t Z là hàm mật độ xác suất của một mục tiêu được giả thuyết là có quỹ 
đạo  , được đo tại cùng thời điểm kt ( tức là phân bố dự đoán). 
10) ( )M là hàm hợp lý của quỹ đạo  không được kết hợp với bất kỳ phép đo nào trong 
tập dữ liệu kZ , mà trong thực tế xác suất của một mục tiêu được cho bởi giả thuyết theo 
quỹ đạo  không được phát hiện trong tập dữ liệu kZ , và do đó được cho bởi: 
 ( 1)( ) (1 ( )). ( , | , )  
k
D kM P x P x t Z dx (9) 
11) ( )NT y là hàm hợp lý của một độ đo trong kZ nhận giá trị y , có nguồn gốc từ một 
mục tiêu mới được phát hiện, nghĩa là ( )
 NTY y dy là số mục tiêu chưa được phát hiện 
trong tập dữ liệu ( 1)kZ nhưng đã được phát hiện (lần đầu tiên) trong tập dữ liệu hiện tại 
kZ , các giá trị y trong Y . Điều này được cho bởi 
( 1)( ) ( | ). ( ). ( , | , )   
k
NT M D UDT ky P y x P x x t Z dx (10) 
12) 
( 1)( , | , )  kUDT kx t Z là hàm mật độ xác suất của các mục tiêu không bị phát hiện 
trong các bộ dữ liệu quá khứ 1 1, ... , kZ Z , trong không gian trạng thái mục tiêu tại thời 
điểm kt , tức là 
( 1)( , | , )  
k
UDT kX
x t Z dx là số mục tiêu mà chưa được phát hiện trước 
đây (dữ liệu trước thời điểm k) và trạng thái x của nó nằm trong ΔX. 
13) ( )FA y là hàm hợp lý của ky Z với y là báo động giả (nghĩa là có gốc từ một mục 
tiêu không có thực), đó là mật độ các báo động giả trong tập dữ liệu hiện tại kZ , tức 
là ( )
 FAY y dy là kỳ vọng của các báo động giả được bao hàm trong miền ΔY. 
Phương trình (5) ở dạng đệ quy. Để đóng đệ quy chúng ta cần cập nhật lại trạng thái 
của thuật toán theo dõi. Với mỗi giả thuyết  và mỗi   , nếu ( , )  j k , thì 
( ) 1 ( 1)( , | , ) ( | ) . ( | ). ( ). ( , | , )   k kk j M j D kP x t Z L y P y x P x P x t Z (11) 
trái lại 
 ( ) 1 ( 1)( , | , ) ( ) .(1 ( )). ( , | , )   k kk D kP x t Z M P x P x t Z (12) 
 Với xác suất không phát hiện được mục tiêu, chúng ta có: 
( ) ( 1)( , | , ) (1 ( )). ( , | )   k kUDT k D UDT kx t Z P x x t Z (13) 
Toán học, Cơ học & Ứng dụng 
 N. T. Hằng, , L. T. H. Giang, “Một cách đánh giá hiệu suất  theo dõi đa mục tiêu.” 218 
Hơn nữa, nếu tk > tk-1, ta cần ngoại suy phương trình, 
( 1) ( 1)
1 1( , | , ) ( , | , ). ( , | , ) 
k k
k k k kP x t Z F x t x t P x t Z d x (14) 
Và ( 1) ( 1)
1 1( , | , ) ( , | , ). ( , | )  
k k
UDT k k k UDT kx t Z F x t x t x t Z d x (15) 
trong đó, (. | .)F là mật độ xác suất chuyển đổi cho các trạng thái mục tiêu, tức là, 
( , | , )
 X F x t x t dx là xác suất của trạng thái mục tiêu x tại thời điểm t trong X được 
cho bởi trạng thái tại thời điểm t t là x . 
Rõ ràng từ (11) - (14) chỉ ra lý thuyết về theo dõi đa mục tiêu thực sự là một sự mở 
rộng của lý thuyết ước lượng hoặc lý thuyết lọc chung. 
3. THIẾT LẬP MÔ PHỎNG VÀ CÁC KẾT QUẢ CHÍNH 
3.1. Mô hình mô phỏng 
Để thực hiện mô phỏng, chúng tôi đã chọn một bộ cảm biến điển hình, tức là một 
radar, nhằm quan sát các mục tiêu trong môi trường SNR thấp. Các mục tiêu được giả định 
là chuyển động theo các quỹ đạo có vận tốc không đổi. Chúng tôi giả định có một bộ cảm 
biến duy nhất, ví dụ, một radar được mô phỏng bởi: |MP y x và DP x như mô tả trong 
Phần II. 
 Xác suất phát hiện: 
{ , , , , }
( )
  iDD i
i R A E D S
PP x x (16) 
ở đây: iD iP x là hàm đại diện cho mỗi thành phần i trong { , , , }R A E D , trong đó: R_cự 
ly (Range), A_góc phương vị (Azimuth), E_góc nâng (Elevation), D_độ dịch tần-(Doppler 
range rate- tốc độ biến đổi của khoảng cách từ mục tiêu đến máy thu), và S_tỷ lệ giữa tín 
hiệu và nhiễu (SNR). Với mỗi ix là giá trị đúng của mỗi thành phần i. 
- Với I trong { , , , }R A E D ta có: 
2
1 1
( ) exp
22  
i
i i i
D i iFOV
ii
y x
P x dy (17) 
trong đó: iFVO là vùng quan sát cho thành phần i , và  i là độ lệch chuẩn cho thành phần i . 
-Với i S , thì SNR tính như sau: 
 SNR
RCS
SNR
RCS
 (18) 
 RCS là thiết diện radar và là một biến ngẫu nhiên có phân bố mũ với trung bình là RCS , 
SNR là tỷ lệ tín hiệu/ nhiễu trung bình, tính như sau: 
4
0
( )
R RCS
SNR
R L R
 (19) 
với R là cự ly của mục tiêu, và R0, L(R) là các tham số radar khác và được truyền vào mô 
hình. Điều này có nghĩa là SNR là một biến ngẫu nhiên có phân bố mũ với trung bình là 
SNR . Giá trị độ đo của SNR là SNRy được tính như sau: 
2 21 (( 2 ) )
2
  SNRy SNR (20) 
Ở đây, ξ và η là hai tham số của phân bố Gauss có trung bình là 0, phương sai là 1. Có 
thể cho thấy rằng SNRy là một phân phối mũ với trung bình 1 + . Do đó, khi tín hiệu 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CBES2, 04 - 2018 219
trong ngưỡng SNRTH chúng ta có: 
 ( ) exp
1
S TH
D
SNR
P SNR
SNR
 (21) 
Như vậy, SNR có thể là một phần của trạng thái. Tuy nhiên, đối với mục đích là đánh 
giá hiệu suất, chúng tôi giả sử rằng SNR đã biết trong thuật toán theo dõi. 
 Giá trị của |MP y x trong mô hình được phân tích thành: 
{ , , , , }
,| |
 
i R
i
M
A E
M i
S
i
D
P y x P y x k (22) 
- Với i nhận giá trị trong { , , , }R A E D , ta có: 
2
2
'
'
1
exp
2
( | )
1
exp
2


i
i i
ii
M i i
i i
iFOV
i
y x
P y x
y x
dy
 (23) 
Ở đây,  i là độ lệch chuẩn của nhiễu, và minmax ,
2

 
  
 
 
i
i i
SNRy
 (24) 
 Với i là độ phân giải cảm biến cho thành phần i . Các tham số đo i và 
mini , 
được liệt kê trong bảng 1. 
Bảng 1. Các tham số của cảm biến (radar). 
Độ đo i σi σi
min 
Azimuth A 1,8° 0,03° 
Elevation E 5,1° 0,1° 
Range R 150 m 5 m 
Doppler D 1m/s 0,1 m/s 
- Với i = S, ta có: 
( )1
( | ) .exp
1 1
S SNR TH
M SNR
y SNR
P y SNR
SNR SNR
 (25) 
Xác suất báo động giả: exp FA THP SNR (26) 
với số các báo động giả trung bình là: 
{ , , , }
( )
 
  iFA FA
i R A E D i
FOV
v P (27) 
trong đó, ( ) iFOV là thể tích của vùng quan sát cho thành phần đo thứ i . Mật độ của báo 
động giả, nghĩa là độ đo của SNR khi một giá trị đo là báo động giả, được mô phỏng bằng 
một phân bố mũ như sau: 
 { } exp ( ) r SNR SNR THP y dy y SNR dy (28) 
Vì chúng ta giả sử rằng trung bình của SNR đã biết nên trạng thái mục tiêu như là 
một vector 6 chiều, tức là, có 3 chiều vị trí và 3 chiều vận tốc. 
Chúng ta cũng giả sử rằng phân bố trạng thái mục tiêu của tất cả các quỹ đạo cũ τ , có 
phân bố Gaussian (xấp xỉ), như sau: 
 1
2
( ) 1 1, | , .exp
2det(2 )

k
k
V
P x t Z x x
V
 (29) 
Toán học, Cơ học & Ứng dụng 
 N. T. Hằng, , L. T. H. Giang, “Một cách đánh giá hiệu suất  theo dõi đa mục tiêu.” 220 
Sau đó, từ (8), (16), (17), (21) - (23), và (25), và từ phương trình tuyến tính của 
phương trình đo phi tuyến, có 
1
21 1 1
( | ) .exp . .exp
21 1 det(2 )

SNR
RAED READ
S
y
L y y y
SNR SNR S
 (30) 
Trong đó: yRAED = (R,A,E,D) là vector của phép đo, RAED = ( , , , ) là phép chiếu 
phi tuyến của ước lượng trạng thái tại thời điểm x lên không gian đo của cảm biến, S là ma 
trận phương sai mới được định nghĩa bởi: 
 TS HV H (31) 
Với
1
3
3 3
1 0 0 0 0
00 .cos 0 0 0
. .
00 0 0
( )0 0 0
T
R
T
A
T
E
T T
S R
g
IR E g
H
g DI RIR
v v gR
 (32) 
Ở đây: 
cos cos sin cos sin
sin cos 0 .
cos sin sin sin cos
T T
R R
T T
A A
T T
E E
A E A E Eg l
g A A l
g lA E A E E
 (33) 
 Và Σ = diag(σ2R, σ
2
A, σ
2
E, σ
2
D) (34) 
Trong (32) là thành phần vận tốc của x , Sv là vector vận tốc cảm biến, I3 là ma trận 
vận tốc cỡ 3 x 3, và
 , , 
( )
R Ei Ai
l
là hệ thống điểm ảnh của cảm biến xác định phương vị và 
hướng cao. Bằng cách thay thế (16), (17) và (21) vào (9) và bỏ qua các điều khoản chéo 
giữa các thành phần đo, khả năng phát hiện lỗi có thể được tính như sau: 
2
{ , , , }
( )1 1
1 exp . . exp
21 2

 
i
i iTH
iFOV
i R A E D iiii
y ySNR
M dy
SSNR S
 (35) 
trong đó, Sii là phần tử chéo thứ i của ma trận S được định nghĩa bởi (31). 
Việc tính toán mật độ của mục tiêu mới được phát hiện βNT khá phức tạp. Ta cần tính 
được mật độ các mục tiêu không được xác định, βUDT. Đối với phân tích này, chúng tôi sử 
dụng công thức gần đúng sau: 
1
( ) .exp . ( )
1 1
 
SNR
UDTNT
y
y R
SNR SNR
 (36) 
Trong đó, là giá trị trung bình của mật độ các mục tiêu không được xác định: 
 {A, , }
( ) . 1 exp
( ) 1



HR R
T D
T TH
UDT
i
i E D
v SNR
R
FOV SNR
 (37) 
trong đó: vT là kỳ vọng xuất hiện mục tiêu trên vùng xác định trong một khoảng thời gian 
nhất định, RH là khoảng cách từ cảm biến đến đường chân trời, ΔT là thời gian giữa hai lần 
quét liên tiếp và là tỷ lệ trung bình của các mục tiêu. 
Cuối cùng, giả sử rằng mỗi thành phần khác của một báo động giả được phân phối 
đồng đều trên mỗi khoảng FOV, chúng ta có thể kết hợp (26)-(28) để có được mật độ báo 
động giả, như sau: 
{ , , , }
1
( )
exp .



FA
SNR i
i R A E D
y
y
 (38) 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CBES2, 04 - 2018 221
Để bắt đầu một quỹ đạo, ta cần một thuật toán (xấp xỉ) để sinh một phân bố Gaussian 
ở vế trái của (11) khi   . Phân bố trạng thái mục tiêu ( 1)( , | , )k
k
P x t Z  rất khó để 
tính. Bỏ qua thông tin phân bố trạng thái mục tiêu của các mục tiêu không bị phát hiện, 
một quỹ đạo được bắt đầu từ một bộ phép đo như sau: 
1) Tạo một phân bố Gauss từ ba phép đo vị trí là: cự ly, phương vị và cao độ. 
2) Tạo một phân bố Gauss của vector vận tốc từ thông tin vận tốc ban đầu. Trong trường 
hợp này phân bố phù hợp được chọn dựa trên thực tế có tốc độ nằm trong khoảng từ 150 
đến 300 m/s và mục tiêu là mục tiêu di động hướng đến trung tâm khu vực giám sát. 
3) Cập nhật phân bố trạng thái mục tiêu Gauss bằng phép đo Doppler (range rate). Sau khi 
một quỹ đạo được tạo, ứng dụng bộ lọc Kalman mở rộng (EKF) để cập nhật quỹ đạo. (11) 
được tính bằng: 
  ( ) RAED RAEDx x K y y (39) 
với: 1K TV H S và  (I KH). V V (40) 
Cập nhật và ước lượng ma trận phương sai sai số . Khi không có phép đo nào 
được chỉ định quỹ đạo được cập nhật theo (12). Xác suất phát hiện PD(x) được cho theo 
công thức (16), (17). Trong thực tế, một mục tiêu không bị phát hiện không ảnh hưởng 
nhiều đến phân bố trạng thái mục tiêu, và do đó, không cần cập nhật các quỹ đạo khi nó bỏ 
lỡ một phát hiện. 
Trạng thái mục tiêu có thể được biểu diễn bằng một vectơ sáu chiều x = (uT, vT)T với 
hệ tọa độ ba chiều u đo được trong quán tính tâm Trái Đất (ECI) và đạo hàm của nó, v = 
du/dt. Chúng tôi giả định rằng mục tiêu về cơ bản không thay đổi nhiều đường đi; tốc độ 
và độ cao biến đổi liên tục, có thể mô phỏng các thay đổi đó tương đương với việc bổ sung 
nhiễu trắng. Nói cách khác, mô hình động lực trạng thái mục tiêu được xác định bởi 
phương trình vi phân ngẫu nhiên sau: 
( ) ( ) du t v t dt 
 ( ) ( )( ) ( ). ( ) ( ). ( ) ( ) ( ). ( ). ( ) ( )
( )
T
T TH
H R R H H S R
v t e t
dv t e t e t e t e t v t dt e t e t e t Qdw t
u t
 (41) 
trong đó, ( )He t , ( )Se t và ( )Re t là các vectơ đơn vị, tức là: 
( ) ( ) ( )
( ) ( ) ( ); ( ) ; ( )
( ) ( ) ( )
T
H R S S R
v t u t u t
e t e t e t e t e t
v t u t u t
 (42) 
Với x là toán tử ngoài (chéo). Ma trận Q trong (42) là ma trận chéo với các phần tử 
chéo là , , và , trong đó, qH và qV là cường độ gia tốc trắng theo hướng 
ngang và dọc. Các hoạt động ngoại suy để thực hiện (14) với mô hình này cho một khoảng 
thời gian nhất định Δt giữa hai lần quét liên tiếp có thể được thực hiện theo các bước sau: 
1) Trong hệ toạ độ ECI, trước tiên chuyển chúng thành hệ tọa độ đề-các được xác định bởi 
các vector đơn vị cho bởi (42), tức là chiều dài, chiều rộng và chiều cao. 
2) Cho ( , ) là vector trung bình và ma trận hiệp phương sai thể hiện trong tọa độ này. 
Sau đó thực hiện phép ngoại suy tuyến tính, để có được và hiệp phương sai . 
3) Biến đổi , trở lại hệ tọa độ ECI. Khi Δt quá lớn nó làm cho xấp xỉ trên không hợp 
lý, chúng ta có thể chia khoảng thời gian thành các đoạn con nhỏ và lặp lại ngoại suy ở 
trên cho mỗi đoạn con. 

0
tI Ix x
I
 và 
3 2
2
0 3 2
0
2
t
t
T T
Q Q
II I
V V
I II T
Q TQ
 (43) 
Toán học, Cơ học & Ứng dụng 
 N. T. Hằng, , L. T. H. Giang, “Một cách đánh giá hiệu suất  theo dõi đa mục tiêu.” 222 
 Để đánh giá xem một quỹ đạo có được thiết lập hay không, chúng tôi đã chọn quy tắc 
sau: Mỗi quỹ đạo τ được liên kết với xác suất của nó bằng: 
( ) ( )( | ) ( | )
 
 
 k kr rP Z P Z (44) 
Một quỹ đạo được đánh giá sẽ được thiết lập nếu xác suất thiết lập quỹ đạo vượt quá 
ngưỡng cho trước (ngưỡng xác suất theo dõi). Trong một lần chạy nhất định, số lượng quỹ 
đạo được thiết lập có thể thay đổi từ 0 đến nhiều hơn. Sau đó, tính khoảng cách giữa trạng 
thái ước tính và trạng thái mục tiêu thực. Nếu khoảng cách giữa trạng thái ước tính của 
mục tiêu và trạng thái mục tiêu thực nằm trong ngưỡng nhất định, thì kết luận một quỹ đạo 
được thiết lập từ thông tin mục tiêu, sau đó được tính như xác suất thành lập quỹ đạo PET, 
sau khi chạy một số lượng đủ lớn Monte Carlo. Các quỹ đạo còn lại (có xác suất vượt quá 
ngưỡng xác suất theo dõi đã cho) được tuyên bố là các quỹ đạo giả và trung bình của số 
các quỹ đạo được lấy từ mô phỏng Monte Carlo để ước lượng mật độ quỹ đạo giả. 
3.2. Kết quả mô phỏng 
Tập các tham số chính được sử dụng trong chương trình mô phỏng là: 
 Giá trị SNR (tính theo dB), SNR = 6, 8, 10, 12, 14; 
 Xác suất báo động giả Pfa = 10
-5,10-4,10-3; 
 Ngưỡng phát hiện mục tiêu PTTH = 0.25, 0.5, 0.75; 
 Ngưỡng cắt tỉa giả thuyết PHTH = 0.01. 
Dữ liệu đầu vào được giả định từ 12 mục tiêu, ở khoảng cách từ 3km đến 4km so với 
vị trì thu của radar, tốc độ di chuyển nằm trong khoảng 100m/s đến 300m/s. Mỗi điểm thu 
được là giá trị trung bình của 300 lần chạy mô phỏng Monte Carlo. 
Hình 1 cho thấy xác suất thiết lập quỹ đạo một mục tiêu (PET) là một hàm của các giá 
trị SNR, , với ngưỡng phát hiện của radar SNR, xác suất báo sai Pfa = 10
-4. Có ba 
dòng tương ứng với ba giá trị ngưỡng PTTH là 0.25, 0.5, và 0.75, cho xác suất theo dõi cần 
thiết của việc thành lập quỹ đạo. 
Hình 1. Xác suất phát hiện quỹ đạo 
với Pfa = 10
-4. 
Hình 2. Xác suất phát hiện quỹ đạo 
 với Pfa = 10
-5. 
Hình 2 thể hiện kết quả các đường cong hiệu suất với ngưỡng phát hiện cao hơn, Pfa = 10
-5. 
So sánh kết quả trong các bộ số liệu khác nhau, ta thấy: 
- Hiệu suất PET là một giá trị đơn điệu tăng của . Các đường cong thường đạt đến 
điểm bão hòa, nghĩa là PET = 1, tại = 12 dB. 
- Độ nhạy phát hiện quỹ đạo giảm đáng kể theo ngưỡng xác suất theo dõi PTTH. 
- Trong trường hợp ngưỡng phát hiện SNRTH cao, nó hầu như không nhạy cảm với 
hiệu suất phát hiện PET. 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CBES2, 04 - 2018 223
Hình 3, hình 4 thể hiện số lượng trung bình các quỹ đạo và số lượng trung bình các giả 
thuyết đối với các giá trị SNR = 6, 8, 10, 12, 14 dB. 
Hình 3. Số lượng trung bình các quỹ đạo-
ứng với các mốc Pfa. 
Hình 4. Số lượng trung bình các giả thuyết-
ứng với các mốc Pfa. 
Đối với các trường hợp SNR thấp, số lượng trung bình các quỹ đạo và trung bình các 
giả thuyết của trường hợp Pfa = 10
-4 tương ứng nhỏ hơn so với trường hợp Pfa = 10
-5. Có 
điều này là do với SNR thấp, mục tiêu thật hiếm khi được phát hiện, đặc biệt khi ngưỡng 
phát hiện cao (nghĩa là mật độ báo động giả là thấp). 
4. KẾT LUẬN 
Trên đây, chúng tôi sử dụng phương pháp mô phỏng Monte Carlo để đánh giá hiệu 
suất của thuật toán theo dõi đa giả thuyết. Phạm vi mô phỏng được giảm bớt bằng cách 
loại bỏ các phần không cần thiết và tránh lặp lại thống kê trong mỗi lần chạy mô phỏng, 
nhưng vẫn thu được các tương tác thiết yếu giữa cảm biến, quỹ đạo và giả thuyết. 
Hiệu suất của thuật toán đa giả thuyết theo dõi nhiều mục tiêu được mô tả thông qua 
Xác suất thiết lập quỹ đạo PET (probability of establishing a track) và Xác suất báo động 
sai. Yếu tố chính để xác định các giá trị này là SNR trung bình (được tính toán ra bởi các 
loại radar khác nhau), xác suất báo động giả Pfa và ngưỡng phát hiện mục tiêu PTTH. Thông 
qua việc mô phỏng, chúng ta đã rút ra một số kết luận trong phần kết quả thực nghiệm. 
Để có những áp dụng cụ thể hơn trong thực tế, chúng tôi mong muốn được thực hiện 
các tính toán cho các tập dữ liệu thực tế đủ lớn, trên cơ sở đó khẳng định thêm tính ổn định 
của thuật toán và có thể phát triển cải tiến để đem lại lợi ích thiết thực cho vấn đề an ninh, 
quốc phòng. 
TÀI LIỆU THAM KHẢO 
[1]. Sea, R. G, “An efficient suboptimal decision procedure for associating sensor data 
with stored tracks in real-time surveillance systems”, In Proceeding of the IEEE 
Conference on Decision and Control, Miami Beach, Dec.1971, 33-37. 
[2]. Blackman, S.S, “Multiple-Target Tracking with Radar Applications”, Dedham, MA: 
Artech House, 1986, ch. 7. 
[3]. Bar-Shalom, Y., Campo, L., and Luh, P. B, “From receiver operating characteristic 
to system operating characteristic; Evaluation of a large scale surveillance system”, 
IEEE Transactions on Automatic Control, 35 (Feb. 1990), 172-179. 
[4]. Mori, S., Chang, K. C., Chong, C. Y., and Dunn, K. P,”Tracking performance 
evaluation—Prediction of track purity”,In Proceedings of 1989 SPIE Technical 
Symposium on Aerospace Sensing, Orlando, FL, Mar. 1989. 
[5]. Mori, S., Chang, K. C., Chong, C. Y, and Dunn, K. P,”Tracking performance 
evaluation—Hack accuracy in dense target environments”, In Proceedings of SPIE 
Technical Symposium on Aerospace Sensing, Orlando, FL, Apr. 1990. 
Toán học, Cơ học & Ứng dụng 
 N. T. Hằng, , L. T. H. Giang, “Một cách đánh giá hiệu suất  theo dõi đa mục tiêu.” 224 
[6]. Mori, S., Chang, K. C., and Chong, C. Y, “Performance analysis of optimal data 
association with application to multiple target tracking”, In Multitarget-Multisensor 
Tracking: Applications and Advances, Vol. II.Dedham, MA: Artech House, 1992, ch. 7. 
[7]. Reid, D. B, “An algorithm for tracking multiple targets”, IEEE Transactions on 
Automatic Control, AC-24 (Dec. 1979), 843-854. 
[8]. Mori, S., Chong, C. Y., Tse, E., and Wishner, R. P, “Hacking and classifying multiple 
targets without a priori identification”, IEEE Transactions on Automatic Control, AC-
31, 5 (May 1986), 401-409. 
[9]. Daum, F. E, “Bounds on performance for multiple target tracking”, IEEE 
Transactions on Automatic Control, AC-35, 4 (Apr. 1990). 
[10]. Iverson, D., Chang, K. C, and Chong, C. Y, “Performance assessment for airborne 
surveillance systems incorporating sensor fusion”, In Proceeding of 1989 SPIE 
Conference on Signal and Data Processing of Small Targets, Orlando, FL, Mar. 1989. 
[11]. Morefield, C. L, “Application of 0-1 integer programming to multitarget tracking 
problems, IEEE Transactions on Automatic Control, AC-22, 3 (June 1977), 3-2-312. 
[12]. Bar-Shalom, Y., Fortmann, T. E., and Scheffe, “Joint probabilistic data association 
for multiple targets in clutter”, In Proceedings of the 1980 Conference on Information 
Science and Systems, Princeton University, Mar. 1980. 
[13]. Kuo-Chu Chang, Shozo Mori, Chee-Yee Chong, “ Evaluating a Multiple-Hypothesis 
Multitarget Tracking Algorithm”, IEEE Transactions on Aerospace and Electronic 
Systems (Volume: 30, Issue: 2, Apr 1994). 
[14]. Darin T. Dunham, Robert J. Dempster, Samuel S. Blackman, “Tracking algorithm 
speed comparisons between MHT and PMHT”, Proceedings of the Fifth International 
Conference on Information Fusion. FUSION 2002. (IEEE Cat.No.02EX5997). 
[15]. Angelos Amditis, George Thomaidis, Pantelis Maroudis, Panagiotis Lytrivis and 
Giannis Karaseitanidis, “Multiple Hypothesis Tracking Implementation”, Laser 
Scanner Technology, InTech, 2012, 199-220. 
[16]. Nguyễn Kiều Hưng, Phạm Thượng Cát, “Xây dựng phương pháp bám đa mục tiêu 
trên cơ sở kết hợp bộ lọc PHD sử dụng bộ lọc phần tử và phương pháp kết hợp dữ liệu 
GRAPH trong hệ tọa độ hỗn hợp 3 chiều”, Kỷ yếu Hội nghị toàn quốc lần thứ 3 về 
Điều khiển và Tự động hoá - VCCA-2015. 
ABSTRACT 
A PERFORMANCE EVALUATING OF MULTIPLE HYPOTHESIS TRACKING 
ALGORITHM FOR MULTIPLE TARGET TRACKING 
Target tracking is an essential requirement for surveillance systems employing one 
or more sensors, together with computer subsystems. Multiple hypothesis tracking 
(MHT) is generally accepted as the preferred method for solving the data association 
problem in modern multiple target tracking (MTT) systems. In this paper, we will 
evaluate performance of multiple hypothesis algorithm for multiple target tracking 
based on target discovering through important parameters, such as: signal-to-noise 
ratio, probability of establishing a track, and track probability threshold. 
Keywords: Multiple hypothesis tracking; MHT; Performance of algorithm; Detection threshold; Track. 
Nhận bài ngày 26 tháng 02 năm 2018 
 Hoàn thiện ngày 18 tháng 3 năm 2018 
 Chấp nhận đăng ngày 02 tháng 4 năm 2018 
Địa chỉ: 1 Khoa Khoa học cơ bản, Trường Đại học Mỏ - Địa chất; 
 2 Viện CNTT, Viện KH&CN quân sự. 
 * Email: nguyenthihang@humg.edu.vn.