Hungarian Algorithm

Thuật toán Hungary là một phương pháp tối ưu hóa chính xác, tìm cách ghép cặp một-một có chi phí thấp nhất sao cho mọi phần tử trong tập hợp nhỏ hơn được ghép với một phần tử của tập hợp còn lại. Thuật toán tối ưu hóa tổng chi phí của tất cả các cặp được chọn. Trong thị giác máy tính, thuật toán kết nối các kết quả phát hiện với đối tượng được theo dõi hoặc các dự đoán với mục tiêu huấn luyện.

Harold W. Kuhn giới thiệu thuật toán này vào năm 1955 trong Phương pháp Hungary cho bài toán phân công. Phương pháp Hungary và thuật toán Kuhn–Munkres là các tên gọi khác nhau của cùng một họ thuật toán. Tên gọi này vinh danh các nhà toán học Hungary Dénes Kőnig và Jenő Egerváry, những người có công trình đặt nền tảng cho phương pháp.

Cách hoạt động của thuật toán Hungary#

Đầu vào là một ma trận chi phí: mỗi hàng biểu diễn một phần tử từ tập hợp này, mỗi cột biểu diễn một phần tử từ tập hợp kia, và mỗi ô cho biết chi phí ghép cặp chúng. Với ma trận vuông, lời giải chọn chính xác một ô trong mỗi hàng và mỗi cột. Chiến lược tham lam chọn các cặp riêng lẻ có vẻ hấp dẫn; phép ghép Hungary tìm tổng chi phí tối thiểu trên toàn cục.

Trong quy trình rút gọn ma trận kinh điển, hãy trừ giá trị nhỏ nhất của mỗi hàng khỏi tất cả phần tử trong hàng đó, rồi trừ giá trị nhỏ nhất của mỗi cột khỏi tất cả phần tử trong cột đó. Các phép rút gọn này giữ nguyên phép gán đầy đủ tốt nhất vì mỗi phép gán sử dụng mỗi hàng và cột đúng một lần. Che tất cả các số 0 bằng số đường ngang và dọc ít nhất có thể. Nếu cần n đường để che một ma trận n x n, hãy chọn n số 0 sao cho không có hai số nào cùng hàng hoặc cùng cột. Nếu không, hãy trừ giá trị nhỏ nhất chưa được che khỏi các phần tử chưa được che, cộng giá trị đó tại các giao điểm của các đường che, rồi lặp lại bước kiểm tra. Tính chi phí của phép gán bằng ma trận ban đầu.

Các cách triển khai thuật toán Hungary hiệu quả chạy trong thời gian O(n³) với ma trận vuông, so với n! phép gán đầy đủ có thể có.

Ứng dụng trong computer vision#

Theo dõi nhiều đối tượng. Thiết kế SORT ban đầu kết hợp phép gán Hungary với bộ lọc Kalman, dùng để dự đoán vị trí của từng vệt theo dõi. Giao điểm trên hợp đo mức độ chồng lấp giữa các hộp giới hạn được dự đoán và được phát hiện. Bản triển khai tham chiếu của SORT giải bài toán gán bằng LAPJV hoặc SciPy, loại bỏ các liên kết có độ chồng lấp thấp và tạo định danh cho các kết quả phát hiện chưa được ghép.

Huấn luyện phát hiện đối tượng. DETR sử dụng phép ghép Hungary để ghép các dự đoán không có thứ tự với các đối tượng được gán nhãn. Transformer tạo ra các vị trí dự đoán, còn phép ghép kết hợp chi phí phân loại và chi phí định vị hộp. Khi có đủ vị trí, mỗi mục tiêu nhận được một dự đoán, nhờ đó hàm mất mát không phụ thuộc vào thứ tự chú thích; các vị trí không được ghép sẽ học lớp "không có đối tượng". Ultralytics áp dụng công thức gán này trong RT-DETR: HungarianMatcher kết hợp chi phí phân loại, khoảng cách tọa độ L1 và chi phí IoU tổng quát. Backend gán tuyến tính sử dụng bộ giải Jonker–Volgenant đã được sửa đổi để chọn các cặp huấn luyện.

Ghép cặp Hungary trong Python#

Gói Python munkres triển khai phương pháp Hungary. Cài đặt gói bằng pip install munkres, sau đó giải ma trận chi phí mẫu:

from munkres import Munkres

costs = [
    [5, 9, 1],
    [10, 3, 2],
    [8, 7, 4],
]
solver = Munkres()
assignments = solver.compute(costs)
# Read costs from the original matrix.
minimum_cost = sum(costs[row][col] for row, col in assignments)
print(f"Minimum total cost: {minimum_cost}")

Đầu ra là Minimum total cost: 12, tổng nhỏ nhất có thể đạt được khi chọn một ô trong mỗi hàng và mỗi cột.

Các phương pháp liên quan và đối tượng chưa được ghép#

Bài toán phân công là bài toán cần giải; thuật toán Hungary là một bộ giải. Triệt tiêu phi cực đại loại bỏ các kết quả phát hiện cạnh tranh trong cùng một ảnh. Tái định danh đối tượng cung cấp thông tin ngoại hình để liên kết, thường thông qua các vector nhúng được so sánh bằng độ tương đồng cosine. Các điểm số này có thể được dùng làm chi phí ghép cặp.

Kích thước hai nhóm không bằng nhau sẽ tạo ra ma trận hình chữ nhật. Việc theo dõi cũng cần các quy tắc từ chối hoặc phần tử giả có chi phí chưa ghép được xác định để xử lý các kết quả phát hiện bị thiếu và đối tượng mới xuất hiện. Liên kết sai gây ra hiện tượng chuyển đổi định danh: ID của một vệt theo dõi được chuyển sang đối tượng khác.

Bộ giải gán tuyến tính của SciPy giải cùng bài toán tối ưu hóa bằng thuật toán Jonker–Volgenant đã được sửa đổi. Với ma trận hình chữ nhật r x c, bộ giải trả về chính xác min(r, c) cặp khi tồn tại phép gán đầy đủ khả thi.