Moving Target Tracking
You can find the code in my GitHub repository here.
Bài luận này tóm tắt từ đồ án tốt nghiệp của tôi thực hiện năm 2015 về việc phát hiện đối tượng chuyển động và bám vết đa mục tiêu trên video.
1. Bài toán bám vết đa mục tiêu
Một video không chỉ là một chuỗi hình ảnh liên tiếp xếp cạnh nhau. Khi đặt các khung hình theo trục thời gian, sự thay đổi của từng điểm ảnh mang theo thông tin về chuyển động. Từ góc nhìn của Computer Vision, câu hỏi thú vị không chỉ là “trong ảnh có gì?”, mà còn là “đối tượng đó đang đi đâu?”. Đó là điểm khởi đầu của bài toán object tracking.
Minh họa một hệ giám sát chiến trường
Bài toán của đồ án được phát biểu tương đối như sau: từ một camera quan sát cố định, phát hiện các đối tượng chuyển động trong chuỗi video và duy trì định danh cho từng đối tượng qua nhiều khung hình. Nói cách khác, hệ thống cần biến những vùng chuyển động rời rạc trong từng frame thành các track liên tục theo thời gian.
Điểm khó của bài toán nằm ở chỗ phép đo từ camera không hoàn hảo.
- Đối tượng có thể bị nhiễu, bị che khuất, xuất hiện ở nhiều vị trí khác nhau hoặc bị nhầm lẫn với các vùng chuyển động không quan tâm.
- Một frame có thể chứa đồng thời nhiều phép đo, trong đó không phải phép đo nào cũng thuộc về một đối tượng thực.
- Trong các vấn đề về target tracking, những phép đo không xuất phát từ mục tiêu được quan tâm có thể được xem là false alarm hoặc clutter. Ngoài ra, xác suất phát hiện mục tiêu $P_D$ không nhất thiết bằng 1, nghĩa là một mục tiêu có thật vẫn có thể không được camera phát hiện trong một số frame.
Applications of multi-object tracking system.
Vì vậy, tracking không thể chỉ được hiểu là việc nối hai điểm gần nhau. Hệ thống phải vừa dự đoán trạng thái tiếp theo của mục tiêu, vừa quyết định phép đo nào có khả năng thuộc về mục tiêu đó. Từ đây xuất hiện ba câu hỏi cốt lõi.
- Thứ nhất, mục tiêu hiện đang ở đâu và sẽ đi đâu tiếp theo?**
- Thứ hai, phép đo nào trong frame hiện tại thuộc về track nào?
- Thứ ba, khi một mục tiêu không được nhìn thấy trong vài frame, ta có tiếp tục giữ track hay xóa nó?
Đồ án tiếp cận 3 câu hỏi này bằng cách kết hợp các thành phần tương đối kinh điển: mô hình chuyển động, bộ lọc Kalman, bài toán phân công Hungarian và kỹ thuật khử nền video.
Lưu đồ xử lý nhận diện và theo dõi đối tượng từ một video
Trong phạm vi thực nghiệm, camera được giả định là cố định và mục tiêu chuyển động trong vùng quan sát.
Giả định này quan trọng vì khi camera cũng chuyển động, bản thân sự thay đổi của toàn bộ nền sẽ trở thành một nguồn chuyển động lớn, khiến bài toán khử nền trở nên khó hơn nhiều.
Đồ án không cố gắng giải quyết toàn bộ bài toán tracking hiện đại. Thay vào đó, mục tiêu là xây dựng một pipeline đủ rõ để nhìn thấy mối liên hệ giữa lý thuyết xác suất, xử lý ảnh và các thuật toán tối ưu tổ hợp. Một cách nhìn hữu ích là coi hệ thống như một vòng lặp. Mỗi frame tạo ra một tập detection mới. Tracker nhận các detection đó, dự đoán vị trí của những track đang tồn tại, giải bài toán ghép cặp và sau cùng cập nhật trạng thái.
Nếu không có detection phù hợp, tracker không nhất thiết phải quên mục tiêu ngay. Kalman có thể tiếp tục dự đoán trong một số frame, còn bộ quản lý track quyết định khi nào track đó cần bị loại bỏ. Chính vòng lặp này tạo nên sự khác biệt giữa “phát hiện vật thể” và “bám vết vật thể”. Phát hiện trả lời câu hỏi “có gì trong frame này?””. Tracking trả lời thêm câu hỏi: “đó có phải là chính đối tượng mà tôi vừa nhìn thấy ở frame trước hay không?”.
2. Phương pháp áp dụng và thực hiện
Pipeline xử lý được tóm gọn trong 6 layer chính.
Layer 1 — đọc video: camera hoặc video cung cấp chuỗi frame liên tục.
Layer 2 — phát hiện vùng chuyển động: thuật toán MOG2 tạo foreground mask dựa trên mô hình nền thích nghi.
Layer 3 — làm sạch ảnh nhị phân: các phép mở và đóng hình thái học làm giảm nhiễu và nối những vùng foreground phù hợp.
Layer 4 — trích xuất detection: contour được tìm trên foreground mask, sau đó mỗi vùng đủ lớn được biểu diễn bằng bounding box và tâm của đối tượng.
Layer 5 — dự đoán và ghép track: mỗi track sở hữu một bộ lọc Kalman; vị trí dự đoán được so với các detection mới thông qua ma trận chi phí.
Layer 6 — quản lý vòng đời: Hungarian giải bài toán assignment, sau đó hệ thống tạo track mới, cập nhật track cũ hoặc xóa track không còn được quan sát.
2.1. Phát hiện chuyển động
Với camera cố định, một hướng tiếp cận tự nhiên là mô hình hóa nền và tìm phần ảnh khác biệt so với nền. Đồ án khảo sát từ phương pháp sai khác giữa các frame đến nhóm Gaussian Mixture Model.
Phương pháp sai khác khung hình có ý tưởng rất đơn giản. Ta so sánh frame hiện tại với frame trước đó và đánh dấu pixel là foreground nếu độ chênh lệch vượt quá ngưỡng $T_h$. Cách này dễ hiểu nhưng nhạy với vận tốc của đối tượng, tốc độ khung hình và ngưỡng lựa chọn. Nó cũng phù hợp nhất khi camera cố định và nền tương đối ổn định.
Tiến trình lọc và xử lý nền
Một cách mạnh hơn là mô hình hóa mỗi pixel bằng một hỗn hợp các Gaussian.
Ở đó, một pixel có thể được xem là sinh ra từ nhiều trạng thái nền khác nhau thay vì chỉ có một giá trị nền duy nhất.
So sánh sai khác khung hình và mô hình nền Gaussian
Đồ án nghiên cứu cả MOG và MOG2. MOG2 được lựa chọn trong cài đặt vì khả năng thích nghi tốt hơn với biến đổi ánh sáng và cách cập nhật mô hình nền dựa trên lịch sử quan sát. Điểm quan trọng ở đây là foreground mask chưa phải là detection cuối cùng. Mask có thể chứa lỗ thủng, nhiễu điểm ảnh hoặc nhiều vùng nhỏ không phải là mục tiêu. Do đó, cần một bước xử lý hình thái trước khi trích xuất đối tượng.
Các challenge khi xử lý nhiễu với giải thuật GMM
2.2. Làm sạch foreground bằng hình thái học
Hình thái học xem ảnh nhị phân như một tập hợp và dùng một structuring element để biến đổi hình dạng. Hai toán tử cơ bản là erosion và dilation.
Erosion làm co vùng foreground và có xu hướng loại bỏ các chi tiết nhỏ. Dilation làm nở vùng foreground và có xu hướng nối các thành phần gần nhau. Kết hợp chúng để tạo phần mở đầu và phần kết thúc. Opening thường hữu ích để loại bỏ các đốm nhiễu nhỏ. Closing có thể lấp các khoảng trống nhỏ và nối các phần của cùng một đối tượng.
Trong cài đặt, foreground mask từ MOG2 được xử lý bằng phép mở với kernel hình chữ nhật $5 × 5$, sau đó đóng với kernel $7 × 7$.
Những tham số này là lựa chọn thực nghiệm của chương trình và cần được hiệu chỉnh dựa trên video đầu vào.
Ví dụ foreground mask trước và sau xử lý morphology
Sau bước này, hệ thống dùng findContours của OpenCV để tìm biên của các vùng foreground.
Diện tích contour trở thành một tiêu chí đơn giản để loại bỏ những vùng quá nhỏ.
Một tham số quan trọng là MIN_BLOB_AREA.
Nếu giá trị quá nhỏ, hệ thống có thể giữ lại nhiều nhiễu.
Nếu giá trị quá lớn, những mục tiêu nhỏ có thể bị bỏ qua.
Cuối cùng, mỗi contour hợp lệ được chuyển thành một bounding rectangle. Tâm của rectangle trở thành phép đo chính dùng cho tracker.
2.3. Mô hình hóa trạng thái bằng Kalman Filter
Sau khi có các detection, bài toán chuyển từ xử lý ảnh sang ước lượng trạng thái. Đồ án dùng vector trạng thái bốn chiều: $ X_k = [x, y, v_x, v_y]^T $
Trong đó $x, y$ là tọa độ và $v_x, v_y$ là vận tốc theo hai trục tọa độ. Mô hình động học được chọn là vận tốc gần như không đổi. Vì vậy, khi bỏ qua thành phần nhiễu, trạng thái có thể được hiểu trực giác là:
$ x_{k+1} = x_k + v_x y_{k+1} = y_k + v_y $ Điều này không có nghĩa là vật thể thực sự luôn đi thẳng. Nó chỉ là một mô hình cục bộ để dự đoán vị trí gần nhất trong khung hình tiếp theo.
Kalman Filter là một bộ ước lượng đệ quy cho hệ động lực học tuyến tính có nhiễu Gaussian. Nó gồm hai pha lặp đi lặp lại: predict và update. Ở pha predict, hệ thống dùng mô hình trạng thái để dự đoán vị trí tiếp theo và lan truyền ma trận hiệp phương sai. Ở pha update, detection mới được dùng để điều chỉnh dự đoán.
Chu trình Predict → Measurement → Update của Kalman Filter
Trong cài đặt, ma trận chuyển trạng thái tương ứng với vector $[x, y, v_x, v_y]$. Ma trận đo $H$ chỉ quan sát hai thành phần vị trí $x$ và $y$.
Điều này phản ánh đúng cách pipeline hoạt động. Camera không quan sát trực tiếp vận tốc. Vận tốc là một biến ẩn được Kalman suy ra từ chuỗi quan sát về vị trí. Hai ma trận $Q$ và $R$ đóng vai trò rất quan trọng. $Q$ thể hiện mức độ bất định của mô hình chuyển động. $R$ thể hiện mức độ bất định của phép đo từ ảnh.
Nói trực giác, nếu tin camera hơn thì bộ lọc sẽ bám phép đo mạnh hơn. Nếu nghi ngờ phép đo hoặc kỳ vọng chuyển động có thể thay đổi nhiều, bộ lọc sẽ dựa nhiều hơn vào dự đoán.
2.4. Từ single-target sang multi-target
Với một mục tiêu, việc lựa chọn detection có thể tương đối đơn giản.
Nhưng với nhiều mục tiêu, cùng một frame có thể chứa N tracks và M detections.
Lúc đó, bài toán trở thành một bài toán data association.
Một ý tưởng cơ bản là tạo gate xung quanh vị trí dự đoán.
Chỉ những phép đo nằm trong vùng có khả năng của track mới được xem xét.
Trong lý thuyết, gate có thể được xây dựng dưới dạng hình chữ nhật hoặc hình elip dựa trên độ bất định của dự đoán.
Khoảng cách Mahalanobis là một cách tự nhiên để đo độ phù hợp giữa trạng thái được đo và trạng thái dự đoán.
Một chiến lược đơn giản là Nearest Neighbor: chọn phép đo gần nhất với dự đoán. Tuy nhiên, khi có nhiều track ở gần nhau, lựa chọn cục bộ này có thể dẫn đến xung đột. Vì vậy, đồ án chuyển bài toán về dạng assignment problem. Mỗi phần tử của ma trận chi phí biểu diễn mức độ “không phù hợp” giữa một track và một detection.
Trong implementation, chi phí được tính bằng khoảng cách Euclid giữa vị trí dự đoán của Kalman và tâm của detection.
Cost[i][j] = distance(prediction_i, detection_j)
Sau đó, Hungarian algorithm được dùng để tìm assignment tối ưu toàn cục theo ma trận chi phí.
Ma trận chi phí giữa các track và detection
Điểm đáng chú ý là đây không chỉ là một thao tác kỹ thuật. Assignment là nơi hệ thống chuyển từ “tôi biết có những vị trí này” sang “tôi tin rằng vị trí này thuộc về track này”.
2.5. Quản lý vòng đời Track
Mỗi track trong chương trình được biểu diễn bởi một đối tượng có track_id, Kalman Filter, dự đoán vị trí, lịch sử quỹ đạo và số frame bị bỏ qua.
Khi chưa có track nào, mỗi detection được dùng để khởi tạo một track mới.
Ở mỗi frame tiếp theo, Kalman tạo dự đoán cho các track hiện tại.
Ma trận chi phí được xây dựng giữa các dự đoán và các phát hiện.
Hungarian trả lại assignment.
Nếu một assignment có khoảng cách vượt quá ngưỡng cho phép, cặp đó sẽ được coi là không hợp lệ.
Track không được gán detection sẽ làm tăng skipped_frames.
Nếu số frame bị bỏ qua vượt quá ngưỡng, track sẽ bị xóa.
Trong cài đặt của đồ án, ngưỡng mặc định được đặt là 10 frame.
Các detection chưa được gán cho track cũ sẽ trở thành ứng viên để tạo track mới.
Như vậy, vòng đời của một track có thể được mô tả đơn giản bằng 3 trạng thái: xuất hiện, được cập nhật và bị loại bỏ.
Sơ đồ vòng đời Track từ khởi tạo đến cập nhật và loại bỏ
3. Kết quả thực nghiệm
Phần thực nghiệm của đồ án tập trung vào việc chứng minh từng tầng của pipeline trước khi kết hợp toàn bộ hệ thống.
3.1. Kết quả khử nền (background subtraction)
Kết quả đầu tiên là foreground mask được tạo từ chuỗi frame của video.
Khi camera cố định và có đối tượng chuyển động, vùng thay đổi được tách ra khỏi phần nền tương đối ổn định.
Foreground mask tương ứng sau khi khử nền. Video.
Kết quả này cho thấy khử nền là phù hợp để tạo nguồn đo lường cho tracker. Tuy nhiên, foreground vẫn có thể chứa nhiễu và những vùng không hoàn toàn liên tục. Điều đó xác nhận vai trò của bước morphology và contour filtering.
3.2. Kết quả của Kalman Filter
Thực nghiệm tiếp theo ghi nhận quỹ đạo của các đối tượng và so sánh vị trí quan sát với vị trí sau khi đã được lọc.
Áp dụng thuật toán MOG2 và sử dụng hàm findContours của OpenCV. So sánh quỹ đạo quan sát với quỹ đạo được làm trơn bằng bộ lọc Kalman. Video.
Một kết quả đáng chú ý là khi đối tượng bị che khuất, Kalman vẫn có thể tiếp tục tạo prediction trong các frame không có measurement.
Minh họa Kalman filter tiếp tục dự đoán trong thời gian đối tượng bị che khuất. Video.
Khi đối tượng xuất hiện trở lại, measurement mới được đưa vào pha update và quỹ đạo dự đoán được điều chỉnh. Đây chính là một trong những giá trị thực tế của tracking so với việc chỉ vẽ detection độc lập trên từng frame.
3.3. Kết quả bám vết đơn mục tiêu
Với một đối tượng, pipeline có thể duy trì một track qua các frame liên tiếp.
Mỗi frame cung cấp detection mới; Kalman cung cấp prediction, sau đó state được cập nhật.
Minh họa kết quả bám vết của một mục tiêu đơn. Video.
Thực nghiệm này đóng vai trò như một bước kiểm chứng trung gian. Nếu single-target tracking không ổn định, việc mở rộng sang multi-target sẽ chỉ khiến lỗi association khó quan sát hơn.
3.4. Kết quả bám vết đa mục tiêu
Khi nhiều đối tượng xuất hiện đồng thời, hệ thống phải xây dựng ma trận chi phí giữa tất cả các dự đoán và các phát hiện.
Hungarian sau đó tìm assignment để duy trì định danh của các track.
Minh họa kết quả bám vết đa mục tiêu và foreground mask. Video.
Kết quả thực nghiệm cho thấy pipeline có thể duy trì nhiều track đồng thời trong các tình huống chuyển động phù hợp với các giả định của mô hình. Quan trọng hơn, thực nghiệm làm rõ vai trò của từng thuật toán.
- MOG2 chịu trách nhiệm biến video thành foreground.
- Morphology làm sạch foreground.
- Contour extraction biến vùng ảnh thành vùng được phát hiện.
- Kalman biến chuỗi detection thành prediction có trạng thái.
- Hungarian giải quyết bài toán “detection này thuộc track nào?”.
- Track manager quyết định track nào được giữ lại, track nào được tạo mới hoặc track nào được xóa.
4. Key takeaways
5.1. Giới hạn của giả định camera cố định
Background subtraction hoạt động tốt nhất khi camera quan sát cố định. Nếu camera rung hoặc di chuyển, rất nhiều pixel nền sẽ trở thành “foreground giả”.
Trong thực tế, cần thêm bước ước lượng chuyển động của camera, image registration hoặc một cách mô hình hóa background khác để xử lý tình huống này.
5.2. Giới hạn của mô hình vận tốc không đổi
Trong implementation, Kalman dùng mô hình $[x, y, v_x, v_y]$ với vận tốc gần như không đổi. Mô hình này hợp lý khi chuyển động tương đối mượt và không thay đổi hướng quá đột ngột. Nếu đối tượng tăng tốc mạnh, quay đầu hoặc chuyển động theo hướng phi tuyến, dự đoán có thể bị lệch đáng kể.
Một hướng mở rộng là thử constant acceleration, coordinated turn hoặc các mô hình động học phù hợp hơn cho từng loại chuyển động.
5.3. Khoảng cách Euclid là một cost function đơn giản
Implementation sử dụng khoảng cách Euclid giữa prediction và detection. Đây là một tiêu chí trực quan nhưng chưa tận dụng đầy đủ tính không chắc chắn của Kalman. Một cải tiến tự nhiên là sử dụng khoảng cách Mahalanobis, qua đó tính đến cả ma trận hiệp phương sai của dự đoán.
Khi prediction có độ bất định lớn, một detection xa hơn theo khoảng cách Euclid nhưng vẫn hợp lý theo covariance có thể được giữ lại.
5.4. Hungarian không tự giải quyết identity switch
Hungarian tối ưu assignment theo cost matrix đã cho. Nó không tự hiểu semantic identity của một người, một chiếc xe hay một vật thể. Nếu hai đối tượng cắt ngang nhau hoặc đi rất gần nhau, chỉ dựa vào khoảng cách vị trí có thể dẫn đến việc đổi ID.
Các hệ thống hiện đại thường bổ sung các feature appearance, motion model tốt hơn hoặc cơ chế multi-hypothesis để giảm hiện tượng này.
5.5. Xử lý occlusion hiện tại còn đơn giản
Cơ chế skipped_frames giúp theo dõi các frame không có detection trong một số trường hợp.
Tuy nhiên, đây vẫn là một heuristic dựa trên số lượng frame.
Một mục tiêu bị che khuất vài frame và một mục tiêu thực sự biến mất đều được xử lý theo cùng một cơ chế đếm thời gian.
Future work có thể bổ sung confidence score, logic xác nhận track theo nhiều giai đoạn hoặc appearance model để quyết định tốt hơn khi nào một track nên được giữ.
5.6. Threshold còn phụ thuộc vào video đầu vào
Các tham số như MIN_BLOB_AREA, ngưỡng khoảng cách assignment, tốc độ cập nhật background và covariance của Kalman ảnh hưởng trực tiếp đến kết quả.
Một video về vật thể nhỏ sẽ cần các tham số khác so với video về con người.
Điều này cho thấy hệ thống vẫn phụ thuộc khá nhiều vào việc tinh chỉnh thủ công.
Một hướng nghiên cứu tiếp theo là xây dựng cơ chế tự thích nghi tham số dựa trên thống kê của scene hoặc calibration tự động trước khi bắt đầu tracking.
5.7. Chưa có đánh giá định lượng đầy đủ
Đây có lẽ là khoảng trống lớn nhất khi nhìn từ chuẩn nghiên cứu computer vision hiện đại. Thực nghiệm cho thấy hệ thống chạy được, nhưng chưa trả lời đầy đủ câu hỏi “chạy tốt đến mức nào?”. Một phiên bản tiếp theo nên có ground truth và các metric chuẩn cho multi-object tracking. Ví dụ, có thể đo độ chính xác detection, số lần mất track, số lần tạo nhầm track, ID switch và thời gian xử lý cho từng frame.
Khi đó, ta có thể thay đổi từng thành phần của pipeline và đo được tác động của chúng, thay vì chỉ quan sát bằng mắt.
5.8. Từ tracking hình học đến tracking đa phương thức
Pipeline của đồ án chủ yếu dựa trên hình học vị trí và chuyển động. Nhưng trong các bài toán thực tế, hai đối tượng có thể có vị trí tương tự nhưng có hình ảnh hoặc đặc trưng ngoại hình khác nhau. Điều này mở ra hướng kết hợp motion + appearance. Một tracker có thể dùng Kalman để dự đoán vị trí, Hungarian để giải assignment và thêm embedding hình ảnh để kiểm chứng danh tính.
Tài liệu tham khảo
- Linköping University, Lectures Target Tracking, 2014.
- S. Blackman and R. Popoli, Design and Analysis of Modern Tracking System, Artech House, 1999.
- D. B. Reid, “An algorithm for tracking multiple targets,” IEEE Transactions on Automatic Control, 1979.
- S. S. Blackman, “Multiple hypothesis tracking for multiple target tracking,” IEEE Transactions on Aerospace and Electronic Systems, 2004.
- R. Kalman, “A new approach to linear filtering and prediction problems,” Journal of Basic Engineering, 1960.
- Greg Welch and Gary Bishop, An Introduction to the Kalman Filter, 2006.
- D. Bruff, The Assignment Problem and the Hungarian Method, 2005.
- R. A. Pilgrim, Munkres Assignment Algorithm — Modified for Rectangular Matrices.
- Stauffer and Grimson, Mixture of Gaussians, 1999.
- Z. Zivkovic, “Improved Adaptive Gaussian Mixture Model for Background Subtraction,” ICPR, 2004.
- B. D. Lucas and T. Kanade, “An iterative image registration technique with an application to stereo vision,” 1981.
- B. K. P. Horn and B. G. Schunck, “Determining optical flow,” Artificial Intelligence, 1981.
- The OpenCV Tutorials, Release 3.0.0-beta, 2014.
- Anton Andriyenko and Konrad Schindler, “Multi-target Tracking by Continuous Energy Minimization,” CVPR, 2011.
