Chương 1 : Bài toán theo vết đối tượng 1. Giới thiệu Theo vết đối tƣợng thời gian thực là một công đoạn trong rất nhiều ứng dụng thị giác máy tính. Một trong những mục tiêu của theo vết đối tƣợng là để “hiểu” đƣợc những chuyển động của đối tƣợng, “hiểu” những thông tin về đối tƣợng gồm vị trí trong không gian, vận tốc chuyển động và những đặc trƣng vật lý khác. Mức khó khăn của vấn đề phụ thuộc vào loại đối tƣợng muốn phát hiện và theo vết.
Nếu nhƣ chỉ có một vài đặc trƣng chẳng hạn nhƣ màu sắc … đƣợc dùng để biểu diễn đối tƣợng, thì khá dễ dàng xác định tất cả các pixel cùng màu với đối tƣợng. Nhƣng thực tế hoàn toàn khác, ví dụ nhƣ một ngƣời cụ thể sẽ có đầy đủ các chi tiết và thông tin nhiễu chẳng hạn nhƣ các tƣ thế và sự chiếu sáng khác nhau, khó phát hiện, nhận diện và theo vết. Hầu hết các khó khăn này nảy sinh từ khả năng biến động của ảnh video bởi vì các đối tƣợng video thƣờng là các đối tƣợng chuyển động. Khi đối tƣợng chuyển động qua vùng quan sát của camera, hình ảnh về đối tƣợng có thể thay đổi.
Sự thay đổi này đến từ 3 nguồn chính: thay đổi tƣ thế đối tƣợng, sự biến dạng của đối tƣợng, thay đổi về độ chiếu sáng, và sự che khuất một phần hay toàn bộ đối tƣợng. Có rất nhiều phƣơng pháp để giải quyết bài toán trên, có thể phân thành bốn loại chính: dựa trên mô hình, dựa trên miền, dựa trên đƣờng viền và dựa trên đặc trƣng. • Dựa trên mô hình Dựa trên mô hình là phƣơng pháp tạo mô hình cấu trúc của đối tƣợng. Nhƣng vấn đề là quá trình khởi tạo tự động khó, chi phí tính toán cao do độ phức tạp của mô hình.
• Dựa trên miền Phƣơng pháp dựa trên miền là phƣơng pháp kết hợp một miền với mỗi đối tƣợng đang đƣợc theo vết. Miền đƣợc theo vết qua thời gian bằng 4 phép đo độ tƣơng tự. Lợi ích của PP này là khởi tạo khá dễ dàng, chỉ có vị trí và kích thƣớc của cửa sổ cần đƣợc định nghĩa. • Dự trên đường viền Phƣơng pháp dựa trên đƣờng viền bao gồm tìm đƣờng viền bao của đối tƣợng và sau đó cố gắng làm khớp đƣờng viền với các đối tƣợng trong các frame sau.
Quá trình này đƣợc lặp lại với mô hình đƣờng viền đƣợc cập nhật. Ƣu điểm của cách tiếp cận này là là khả năng xử lý hiệu quả sự che khuất một phần. Nhƣng vấn đề yêu cầu là khởi tạo chính xác, và điều này thì khó thực hiện tự động. • Dự trên đặc trưng Phƣơng pháp dựa trên đặc trƣng chỉ theo vết một tập các đặc trƣng của đối tƣợng.
Chẳng hạn chỉ theo vết các điểm ở góc của đối tƣợng, vị trí của đối tƣợng trong frame sau sẽ đƣợc tìm thấy bằng cách tìm các điểm góc mà khớp với các điểm của mô hình nhất. Ƣu điểm của cách tiếp cận này là xử lý đƣợc sự che khuất một phần. Khi đối tƣợng bị che khuất, một số đặc trƣng vẫn còn thấy đƣợc và có thể dùng trong quá trình theo vết. Khuyết điểm của phƣơng pháp này là chất lƣợng theo vết phụ thuộc nhiều vào việc chọn các đặc trƣng.
Các đặc trƣng phải đƣợc chọn sao cho chúng cung cấp sự nhận diện duy nhất cho đối tƣợng, đó không phải là một nhiệm vụ dễ. Quy trình theo vết đối tượng Một hệ thống theo dõi đối tƣợng thông thƣờng gồm 3 phần: • Phát hiện đối tƣợng • Phân vùng • Theo vết đối tƣợng 1. Phát hiện đối tượng Các hệ thống theo vết đối tƣợng thƣờng bắt đầu bằng quá trình phát hiện đối tƣợng. Phát hiện đối tƣợng đƣợc lặp lại trong chuỗi ảnh để hỗ trợ cho quá trình theo vết.
Một số phƣơng pháp phát hiện đối tƣợng thông dụng: a) Dự trên đặc trưng Phƣơng pháp này có nhiều cách chọn đặc trƣng nhƣ: dựa trên hình dáng, màu sắc. Trong đó, dựa trên màu sắc đƣợc xem là thông dụng nhất vì màu sắc thì dễ dàng lấy đƣợc và chi phí tính toán thấp. b) Dựa trên mẫu Nếu nhƣ có mẫu mô tả đối tƣợng, thì việc phát hiện đối tƣợng trở thành quá trình so khớp các đặc trƣng giữa mẫu và chuỗi ảnh. Việc so khớp chính xác các đặc trƣng thƣờng tốn nhiều chi phí và phụ thuộc vào chi tiết, mức độ chính xác của mẫu đối tƣợng.
c) Dựa trên chuyển động Hầu hết các hệ thống theo dõi đều quan tâm đến các đối tƣợng đang chuyển động. Có rất nhiều thuật toán phát hiện chuyển động đã đƣợc công bố. Trong đó, kỹ thuật lấy ngƣỡng đƣợc sử dụng nhằm chống nhiễu, gia tăng hiệu quả của thuật toán. Một số phƣơng pháp theo cách tiếp cận này là: phát hiện chuyển động dựa trên sự khác biệt theo thời gian, phát hiện chuyển động dựa trên trừ nền.
Phân vùng Phân vùng các chuỗi ảnh thành các đối tƣợng chuyển động khác nhau là bƣớc kế tiếp sau khi phát hiện đối tƣợng [10]. Việc phân vùng thƣờng dựa trên thông tin vận tốc chuyển động ví dụ nhƣ từ các đối tƣợng ở giai đoạn đầu, ta kết hợp các đối tƣợng có cùng vận tốc chuyển động theo một ràng buộc nào đó chẳng hạn là tính lân cận. Ta có các cách tiếp cận sau: • Phân vùng dựa trên các phép đo cục bộ • Phân vùng dựa trên phân cụm đơn giản hay sự mâu thuẫn với vận tốc nền • Phân vùng dựa trên các phép biến đổi ảnh phân tích • Phân vùng dựa trên quá trình quy tắc hóa • Phân vùng dựa trên phân cụm có sắp xếp toàn cục. Theo vết đối tượng Theo vết đối tƣợng là giám sát các thay đổi theo không gian và thời gian của đối tƣợng trong suốt chuỗi ảnh, bao gồm sự hiện diện, vị trí, kích thƣớc, hình dáng… của đối tƣợng.
Các phương pháp theo vết thông thường 1. So khớp mẫu (Template Matching) Một miền nhỏ chung quanh điểm cần đƣợc theo vết sẽ đƣợc dùng làm mẫu. Mẫu này sau đó dùng để tìm ra frame ảnh kế tiếp bằng cách sử dụng các kỹ thuật tƣơng quan [11]. Vị trí với kết quả cao nhất sẽ là so khớp tốt nhất giữa mẫu và ảnh.
Bằng cách cập nhật các mẫu theo chuỗi ảnh, các biến 7 dạng lớn cũng có thể đƣợc theo vết [3]. Sử dụng một trong 3 luật cập nhật cơ bản nhƣ sau: 1. Nếu có một sự thay đổi lớn giữa vị trí mẫu ban đầu và vị trí mới thì vị trí mẫu mới được chọn. Trong trường hợp này, các mẫu được hoán đổi hoàn toàn bởi hình dạng mới của chúng.
Nếu có các thay đổi nhỏ giữa vị trí ban đầu và mới của mẫu thì một phiên bản trung bình giữa mẫu mới và cũ sẽ được tính và được cập nhật như mẫu mới. Nếu chỉ có các thay đổi quá nhỏ giữa các vị trí ban đầu và mới, thì mẫu cũ sẽ được sử dụng. Điều này rất quan trọng cho các đối tượng tịnh tiến bởi các lượng nhỏ hơn một pixel: nếu như ta cập nhật lại thì sẽ bị mất các thông tin dịch pixel nhỏ. Ưu, khuyết điểm của PP So khớp mẫu • Ƣu điểm: không chịu ảnh hƣởng bởi nhiễu và hiệu ứng chiếu sáng, theo vết đƣợc các đối tƣợng biến dạng.
• Khuyết điểm: độ phức tạp tính toán cao, chất lƣợng so khớp phụ thuộc vào chi tiết và độ chính xác của mẫu đối tƣợng. Theo vết Meanshift Dorin Comaniciu đã công bố phƣơng pháp theo vết màu Meanshift [4]. Đây là một phƣơng pháp theo vết tối ƣu hóa tối thiểu cục bộ. Mỗi vị trí xi trong miền ứng viên của theo vết sẽ tƣơng ứng với một trọng số wi m qu Wi (b( xi ) u ) u 1 pu ( yo ) Với b(xi) là giá trị màu tại xi và là giá trị tại màu u của mô hình đích, và là giá trị tại màu u của mô hình ứng viên.
Vị trí mới của đối tƣợng là vị trí mà khoảng cách nhỏ nhất giữa mô hình đích và mô hình ứng viên và đƣợc tính bởi: y0 xi 2 i xi wi g h y1 y x 2 i wi g 0 h i Với g(x) = −k'(x) và k(x) là một hàm nhân (kernel function). Quá trình đƣợc lặp lại cho đến khi không có sự thay đổi trong vị trí mới. Meashift là một phƣơng pháp đơn giản và hiệu quả cho theo vết thời gian thực. Nhƣng nó chỉ tối ƣu hoá cục bộ chứ không toàn cục.
Khi màu nền và màu đối tƣợng giống nhau, phƣơng pháp này sẽ không còn tác dụng. Phương pháp Bayesian 1. Ước lượng Bayesian Tiếp cận theo phƣơng pháp Bayesian [5] là phƣơng pháp dựa trên xác suất, sử dụng các phƣơng trình dự đoán để dự đoán trạng thái của đối tƣợng 9 và phƣơng trình cập nhật để hiệu chỉnh lại các dự đoán trƣớc đó về trạng thái của đối tƣợng dựa trên những tri thức thu thập đƣợc từ các quan sát trên đối tƣợng. Mục tiêu của phƣơng pháp Bayesian là ƣớc lƣợng trạng thái Xk dựa trên Z1:k.
Ta ký hiệu, giá trị ƣớc lƣợng Xk dựa trên Z1:k là Xk|k. Dễ thấy, giá trị ƣớc lƣợng trên là một hàm phụ thuộc các quan sát: Xk|k=g(Z1:k) Mục tiêu của ƣớc lƣợng Bayesian là tìm dạng hàm g(.) sao cho giảm thiểu chi phí kỳ vọng. Ta có thể giảm thiểu chi phí kỳ vọng toàn thể bằng cách chọn g(.) sao cho giảm thiểu kỳ vọng điều kiện cho mỗi giá trị Z1:k. Chi phí kỳ vọng này có thể đƣợc viết nhƣ sau: E E Z 1:k X 0:k|Z 1:k Z 1:k C g Z 1:k , X k Phƣơng pháp lọc Bayesian đƣợc thực hiện đệ quy đối với p(Xk|Z1:k) qua hai bƣớc: Dự đoán: pX k|Z1:k 1 pZ k| X k 1 p X k 1|Z1:k 1dX k 1 Cập nhật: pZ k | X k p X k |Z 1:k 1 p X k |Z 1:k 1 pZ k | X k p X k 1|Z 1:k 1dX k 1 10 1.
Một số phương pháp dự trên ước lượng Bayesian Một số phƣơng pháp theo vết dựa trên ƣớc lƣợng Bayesian là: • Lọc Kalman • Lọc Particle Lọc Kalman đã đƣợc biết nhƣ là một phƣơng pháp cổ điển, nổi tiếng đƣợc phát minh từ năm 1960 bởi R. Nó là một thuật toán theo vết tối ƣu nhất trong trƣờng hợp hệ là tuyến tính và nhiễu có phân phối Gauss. Extended Kalman và Unscented Kalman tuy giải quyết đƣợc trƣờng hợp phi tuyến và không phải nhiễu Gauss nhƣng cũng chỉ giải quyết tốt bài toán trong trƣờng hợp phƣơng trình biến đổi có bậc 2.
