Thuật Toán Hungary và Bộ Lọc Kalman trong Theo Dõi Đối Tượng

Các hệ thống theo dõi mục tiêu hiện đại chủ yếu áp dụng chiến lược Tracking-by-Detection, kết hợp phát hiện đối tượng từ YOLO hoặc SSD với cơ chế liên kết khung hình. DeepSORT là ví dụ tiêu biểu, sử dụng bộ lọc Kalman để dự đoán vị trí và thuật toán Hungary để liên kết đối tượng qua các khung hình. Vấn đề cốt lõi: Làm thế nào để xác định cùng một đối tượng xuất hiện ở vị trí khác nhau qua các thời điểm?

• Thuật toán Hungary giải quyết bài toán phân bổ tối ưu giữa khung hình hiện tại và trước đó
• Bộ lọc Kalman dự đoán vị trí tiếp theo dựa trên trạng thái trước, đồng thời hiệu chỉnh bằng dữ liệu phát hiện thực tế

Bài Toán Phân Bổ và Thuật Toán Hungary

Bài toán phân bổ tối ưu (Assignment Problem) yêu cầu phân công N nhiệm vụ cho N người sao cho tổng chi phí nhỏ nhất. Ma trận chi phí dưới đây minh họa trường hợp 4 người thực hiện 4 công việc:

Thuật toán Hungary xử lý qua các bước:

1. Trừ giá trị nhỏ nhất trên mỗi hàng
2. Trừ giá trị nhỏ nhất trên mỗi cột
3. Dùng tối thiểu đường thẳng phủ các số 0
4. Nếu số đường = N → kết thúc, ngược lại điều chỉnh ma trận và lặp

Thư viện Python cung cấp hai phương thức triển khai:

import numpy as np
from scipy.optimize import linear_sum_assignment

ma_tran_chi_phi = np.array([
    [25, 45, 50, 30],
    [30, 70, 40, 25],
    [35, 50, 30, 45],
    [40, 60, 25, 35]
])

ket_qua = linear_sum_assignment(ma_tran_chi_phi)
# Trả về (danh_sach_hang, danh_sach_cot) tối ưu

Trong DeepSORT, thuật toán Hungary liên kết tracks (đối tượng đang theo dõi) và detections (kết quả phát hiện) thông qua ma trận chi phí dựa trên khoảng cách Mahalanobis và đặc trưng hình ảnh:

def lien_ket_toi_uu(do_do_dai, nguong, danh_sach_tracks, danh_sach_phat_hien):
    ma_tran = tinh_chi_phi(danh_sach_tracks, danh_sach_phat_hien)
    ma_tran[ma_tran > nguong] = nguong + 1e-5
    
    hang, cot = linear_sum_assignment(ma_tran)
    
    ket_qua_lien_ket = []
    tracks_chua_lien_ket = []
    phat_hien_chua_lien_ket = []
    
    for i in range(len(danh_sach_tracks)):
        if i not in hang:
            tracks_chua_lien_ket.append(i)
    
    for j in range(len(danh_sach_phat_hien)):
        if j not in cot:
            phat_hien_chua_lien_ket.append(j)
    
    for h, c in zip(hang, cot):
        if ma_tran[h, c] <= nguong:
            ket_qua_lien_ket.append((h, c))
        else:
            tracks_chua_lien_ket.append(h)
            phat_hien_chua_lien_ket.append(c)
            
    return ket_qua_lien_ket, tracks_chua_lien_ket, phat_hien_chua_lien_ket

Bộ Lọc Kalman trong Dự Đoán Vị Trí

Bộ lọc Kalman hoạt động qua hai giai đoạn chính:

Giai Đoạn Dự Đoán (Predict)

Dựa trên trạng thái trước để ước lượng trạng thái hiện tại:

x' = Fx + Q

Trong đó:

• x: Vector trạng thái 8 chiều [cx, cy, tỷ_lệ, chiều_cao, vx, vy, v_tỷ_lệ, v_chiều_cao]
• F: Ma trận chuyển tiếp trạng thái (mô hình vận tốc hằng)
• Q: Ma trận nhiễu hệ thống

def du_doan(trang_thai, ma_tran_covariance):
    # Tính ma trận nhiễu Q
    sai_so_vi_tri = [0.05 * trang_thai[3]] * 3 + [0.05 * trang_thai[3]]
    sai_so_van_toc = [0.01 * trang_thai[3]] * 4
    ma_tran_Q = np.diag(np.square(sai_so_vi_tri + sai_so_van_toc))
    
    # Dự đoán trạng thái mới
    trang_thai_moi = np.dot(MA_TRAN_CHUYEN_TIEP, trang_thai)
    cov_moi = np.dot(MA_TRAN_CHUYEN_TIEP, 
                    np.dot(ma_tran_covariance, MA_TRAN_CHUYEN_TIEP.T)) + ma_tran_Q
    return trang_thai_moi, cov_moi

Giai Đoạn Cập Nhật (Update)

Hiệu chỉnh dự đoán bằng dữ liệu phát hiện thực tế:

y = z - Hx'

x = x' + Ky

Trong đó:

• z: Kết quả phát hiện [cx, cy, tỷ_lệ, chiều_cao]
• H: Ma trận đo lường
• K: Hệ số Kalman

def cap_nhat(trang_thai_du_doan, cov_du_doan, ket_qua_phat_hien):
    # Chuyển sang không gian đo lường
    trang_thai_do = np.dot(MA_TRAN_DO, trang_thai_du_doan)
    cov_do = np.dot(MA_TRAN_DO, np.dot(cov_du_doan, MA_TRAN_DO.T))
    
    # Tính hệ số Kalman
    ma_tran_R = np.diag([10, 10, 1, 10])  # Nhiễu đo lường
    ma_tran_S = cov_do + ma_tran_R
    he_so_K = np.dot(cov_du_doan, np.dot(MA_TRAN_DO.T, np.linalg.inv(ma_tran_S)))
    
    # Hiệu chỉnh trạng thái
    sai_so = ket_qua_phat_hien - trang_thai_do
    trang_thai_moi = trang_thai_du_doan + np.dot(he_so_K, sai_so)
    cov_moi = cov_du_doan - np.dot(he_so_K, np.dot(ma_tran_S, he_so_K.T))
    return trang_thai_moi, cov_moi

Luồng Xử Lý DeepSORT

Quy trình xử lý từng khung hình:

1. Phát hiện đối tượng: Sử dụng YOLO để xác định bounding box
2. Tạo detections: Chuyển đổi kết quả phát hiện sang định dạng chuẩn
3. Dự đoán vị trí: Áp dụng bộ lọc Kalman cho các track đang tồn tại
4. Liên kết đối tượng:
   • Cấp 1: Liên kết qua đặc trưng hình ảnh và khoảng cách Mahalanobis
   • Cấp 2: Xử lý trường hợp chưa liên kết bằng IOU
5. Cập nhật trạng thái: Hiệu chỉnh các track đã liên kết

Trong quá trình liên kết, DeepSORT sử dụng cơ chế cascade để xử lý các trường hợp:

def xu_ly_lien_ket(danh_sach_phat_hien):
    # Tách track đã xác nhận và chưa xác nhận
    tracks_xac_nhan = [i for i, t in enumerate(tracks) if t.da_xac_nhan]
    tracks_chua_xac_nhan = [i for i, t in enumerate(tracks) if not t.da_xac_nhan]
    
    # Cấp 1: Liên kết tracks đã xác nhận
    ket_qua_cap1, tracks_chua_cap1, phat_hien_con_lai = \
        lien_ket_cap_bac(do_do_dai, NGUONG_MAHA, MAX_TUOI, 
                        tracks, danh_sach_phat_hien, tracks_xac_nhan)
    
    # Cấp 2: Xử lý tracks chưa cập nhật
    ung_cuu = tracks_chua_xac_nhan + [k for k in tracks_chua_cap1 
                   if tracks[k].thoi_gian_chua_cap_nhat == 1]
    
    ket_qua_cap2, _, phat_hien_con_lai = \
        lien_ket_iou(tracks, phat_hien_con_lai, ung_cuu, NGUONG_IOU)
    
    return ket_qua_cap1 + ket_qua_cap2, phat_hien_con_lai

Với mỗi cặp liên kết thành công, hệ thống cập nhật trạng thái track bằng kết quả phát hiện mới. Các track không liên kết được đánh dấu "mất tích", trong khi phát hiện mới được khởi tạo thành track riêng.