Hi, xin chào các bạn, hôm này mình sẽ giới thiệu cho các bạn bài toán Multiple Object Tracking sử dụng Kalman Filter để theo vết đối tượng và thuật toán Hungary để giải bài toán credit assignment, nói nôm na là làm sao gán từng tracker vào mỗi object sao cho chi phí là ít nhất.
Ngoài ra, ở bài này, mình chỉ sử dụng phương pháp trừ nền (Background Subtraction) để detect đối tượng động. Các bạn có thể thay thế bằng các thuật toán object detection khác như YOLO, Faster RCNN, Centernet, etc.
Link code: Đây là code của thuật toán, đã được mình implement bằng C++, đây cũng là đồ án môn Computer Vision của mình hồi năm 3 tại trường đại học khoa học tự nhiên, Hồ Chí Minh. Code

Nội dung chính sẽ bao gồm các phần sau:
1. Giới thiệu bài toàn Multiple Object Tracking
2. Nguyên lý
3. Phương pháp

• 3.1 Background Generation
  
• 3.2 Object Detection
  
• 3.3 Kalman Filter
  
• 3.4 Hungary Algorithm
  

4. Ứng dụng
5. Tham khảo

Sau đó, ta sẽ dùng Kalman Filter (KF) để dự đoán vị trí tiếp theo của từng đối tượng.

Để có thể dự đoán được vị trí bằng KF chính xác, ta phải thực hiện so khớp (matching). Ở bước này, ta phải xác định được đối tượng nào là đối tượng nào ở frame trước đó, và ta sẽ giải quyết bằng thuật toán Hungary Algorithm.

Cuối cùng là lặp lại quá trình trên đến khi video kết thúc.

• 3.1 Background Generation
  Để sử dụng phương pháp trừ nền, yêu cầu là background của chúng ta phải khá tĩnh, nếu background động thì phương pháp không còn tác dụng vì phương pháp này mục đích là để trích xuất được những đối tượng động.
  Để trừ nền, ta đơn giản chỉ cần dùng background ở frame (t) - background ở frame (t-1). Tuy nhiên, mình đã thử và thấy có một phương pháp khác hay hơn, đó là Pixel Histrogram.
  Pixel Histogram là phương pháp tái tạo nền, input sẽ là một histogram, output là nền được tái tạo dưới dạng grayscale.
  Giả sử mỗi kích thước của một frame là w (width) và h (height). Ứng với mỗi pixel trên frame, ta sẽ có một histogram 256 chiều. Sau khi có được tất cả là (w x h) histogram, ta sẽ lấy ra giá trị màu lớn nhất ở mỗi histogram và đặt làm giá trị màu tại pixel tương ứng. Cuối cùng sẽ tái tạo được background.
  Để tạo ra được từng histogram đó, ta cần phải lướt qua K frame của video, ứng với mỗi frame ta sẽ lướt từng pixel, lấy ra giá trị màu ở pixel đó và cuối cùng là tăng thêm 1 cho bin màu tương ứng của histogram. Sau khi lướt hết K frame, ta sẽ có được (w x h) histogram.

• 3.2 Object Detection
  Sau khi có được nền, ta sẽ bước đến giai đoạn detection & tracking.
  Để detect những đối tượng động, mỗi lần process frame, ta sẽ lấy frame đó trừ cho nền đã được tái tạo bằng phương pháp ở trên. Phương pháp này rất đơn giản, nếu 2 đối tượng đi gần nhau quá sẽ bị dính và cho là 1 đối tượng nhưng được cái là nó cực kì nhanh =))
  Đây là phương pháp đơn giản, vì hồi đó mới sinh viên, có biết deep learning đâu nên làm cách này haha. Bây giờ các bạn có thể dùng YOLO hoặc Faster RCNN, CenterNet để detect cho chính xác hơn.

• 3.3 Kalman Filter
  Kalman Filter là một mô hình lọc nhiễu, nó bao gồm 2 phần đó là dự đoán (predict) và cập nhật (update). Ở bước predict, nó sẽ dự đoán vị trí của từng đối tượng, sau đó ở bước Update nó sẽ cập nhật, sửa lại cho đúng hơn.

• 3.4 Hungary Algorithm
  Đây là thuật toán dùng để giải quyết assignment problem. Assignment Problem là bài toán có N đối tượng, và M công việc, mỗi đối tượng khi làm một công việc nào đó sẽ có một chi phí nhất định. Và nhiệm vụ đó là làm sao gán mỗi đối tượng cho một công việc nào đó sao cho tổng chi phí là nhỏ nhất.
  

Ở bài viết này, mình chỉ viết trình bày đơn giản các bước, chưa trình bày kĩ thuật toán cũng như có code minh họa vì mình không có thời gian nhiều để làm kĩ, mong các bạn thông cảm. Để hiểu hơn về bài viết, các bạn có thể tham khảo link repo của mình nhé.
Nếu thấy hay, cho mình một star hoặc fork trên repo nhé. Thank you for reading.

Code