Đề tài Ứng dụng lọc particle trong bài toán theo vết đối tượng

TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN CÔNG NGHỆ TRI THỨC LÊ NGUYỄN TƯỜNG VŨ - NGUYỄN MINH TRANG ỨNG DỤNG LỌC PARTICLE TRONG BÀI TOÁN THEO VẾT ĐỐI TƯỢNG KHOÁ LUẬN CỬ NHÂN TIN HỌC TP. HCM, 2005 TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN CÔNG NGHỆ TRI THỨC LÊ NGUYỄN TƯỜNG VŨ - 0112082 NGUYỄN MINH TRANG - 0112159 ỨNG DỤNG LỌC PARTICLE TRONG BÀI TOÁN THEO VẾT ĐỐI TƯỢNG KHOÁ LUẬN CỬ NHÂN TIN HỌC GIÁO VIÊN HƯỚNG DẪN T.S LÊ HOÀI BẮC NIÊN KHÓA 2001 - 2005 LỜI CẢM ƠN Đầu tiên, chúng tôi xin chân thành gửi lời tri ân đến Thầy Lê Hoài Bắc. Luận này này sẽ không thể hoàn thành nếu không có sự hướng dẫn, tin tưởng và tạo cơ hội của thầy. Chúng em xin chân thành cảm ơn sự chỉ bảo của thầy. Chúng tôi cũng xin chân thành gửi lời tri ân đến Thầy Phạm Nam Trung. Thầy đã tận tình hướng dẫn, giúp đỡ, góp ý cho chúng em trong thời gian qua, cũng như tiếp thêm động lực và ý chí, giúp chúng em hoàn thành được luận văn. Chúng em xin trân trọng cảm ơn quý Thầy cô trong Khoa Công nghệ thông tin trường Đại học Khoa học Tự nhiên Tp.Hồ Chí Minh đã tận tình giảng dạy, truyền đạt những kiến thức quý báu và tạo điều kiện cho chúng em được thực hiện luận văn này. Đề tài này thuộc về một lĩnh vựa nghiên cứu mới trên thế giới là lại rất mới ở Việt Nam cộng thêm năng lực hạn chế của người thực hiện cho nên đề tài chắc chắn là chưa hoàn thiện và có nhiều sai sót. Chúng tôi mong nhận được nhiều ý kiến đóng góp và giúp để đề tài hoàn thiện hơn và được ứng dụng trong thực tiễn… Tp.HCM, 7/2005 Sinh viên thực hiện Lê Nguyễn Tường Vũ Nguyễn Minh Trang i Nhận xét của giáo viên hướng dẫn ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ii Nhận xét của giáo viên phản biện ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... iii TÓM TẮT LUẬN VĂN Lọc Particle là một phương pháp thành công trong bài toán theo vết đối tượng theo thời gian thực. Nó là một phương pháp mới đang là sự tập trung của nhiều nghiên cứu hiện nay bởi nó khắc phục được nhược điểm của các phương pháp cổ điển như lọc Kalman, so khớp mẫu (Template Matching)… Trong luận văn này, chúng tôi sẽ trình bày cơ sở lý thuyết của phương pháp lọc Particle, cũng như hai phương pháp mở rộng của lọc Particle: lọc Particle kết hợp với Mean shift ứng dụng cho bài toán theo vết 1 đối tượng, lọc Particle ứng dụng cho bài toán theo vết nhiều đối tượng. Qua khảo sát và cài đặt thử nghiệm cho thấy, hai phương pháp này thật sự là hai phương pháp mạnh mẽ và hiệu quả có thể là giải pháp cho các bài toán theo vết đối tượng thực tế. Một số từ khóa: lọc Particle (Particle Filter), theo vết đối tượng (object tracking), phát hiện chuyển động (motion detection), ước lượng Bayesian (Bayesian Estimation). iv MỞ ĐẦU Theo dõi đối tượng theo thời gian thực (real-time object tracking) là một công đoạn quan trọng trong rất nhiều ứng dụng thị giác máy tính (computer vision applications). Những hệ thống thuộc loại này có thể kể ra như là: hệ thống quan sát – theo dõi đối tượng, hệ thống giao diện người dùng dựa vào cảm nhận (perceptual user interface), những căn phòng thông minh, hệ thống nén video dựa vào đối tượng (object-based video compression) và những hệ thống thông minh hỗ trợ tài xế lái xe tự động. Mặc dù đã được nghiên cứu nhiều năm, bài toán “theo dõi đối tượng” vẫn là một vấn đề nghiên cứu mở cho đến ngày nay. Mức khó khăn của vấn đề này phụ thuộc nhiều vào đối tượng được phát hiện và theo vết như thế nào. Hiện nay, có rất nhiều phương pháp theo vết như: So khớp mẫu (Template Matching), Mean shift, lọc Kalman, lọc Particle … Mỗi phương pháp có điểm mạnh và điểm yếu riêng, tuy nhiên phương pháp lọc Particle có thể khắc phục được những nhược điểm của các phương pháp khác như: theo vết đối tượng theo thời gian thực, theo vết tốt các đối tượng trong trường hợp phi tuyến và không phải nhiễu Gauss … Với mong muốn tiếp cận một hướng nghiên cứu mới trên thế giới và có nhiều ứng dụng thực tế ngay tại Việt Nam, chúng tôi đã đầu tư thực hiện đề tài “ỨNG DỤNG LỌC PARTICLE TRONG BÀI TOÁN THEO VẾT ĐỐI TƯỢNG” với hai mục đích: • Tìm hiểu phương pháp theo vết mới “lọc Particle” • Ứng dụng phương pháp này trong bài toán theo vết đối tượng Luận này được trình bày gồm bốn chương: • Chương 1: Tổng quan về bài toán theo dõi đối tượng, giới thiệu chung về bài toán theo dõi đối tượng bao gồm: giới thiệu, các ứng dụng, các thách thức cùng với các hướng tiếp cận. Đồng thời đưa ra vấn đề mà đề tài tập trung: các phương pháp theo vết thông dụng. v • Chương 2: Lọc Particle, giới thiệu phương pháp mà đề tài hướng đến: lọc Particle. Trong chương này, sẽ trình bày từ tổng quan cho đến các cơ sở lý thuyết của phương pháp lọc Particle. • Chương 3: Ứng dụng lọc Particle trong bài toán theo vết đối tượng, giới thiệu về áp dụng phương pháp lọc Particle trong bài toán theo vết đối tượng thực tế, với hai phuơng pháp mở rộng của lọc Particle mà đề tài hướng đến: áp dụng phương pháp lọc Particle kết hợp với Mean shift trong bài toán theo vết một đối tượng; áp dụng phương pháp lọc Particle trong bài toán theo vết nhiều đối tượng (thuật toán ODAPF). • Chương 4: Kết luận, tổng kết lại những phần đã nghiên cứu, tóm tắt lại kết quả đạt được, đồng thời đưa ra một số hướng phát triển cho việc giải quyết bài toán. vi MỤC LỤC LỜI CẢM ƠN .............................................................................................................i Nhận xét của giáo viên hướng dẫn.............................................................................ii Nhận xét của giáo viên phản biện............................................................................ iii TÓM TẮT LUẬN VĂN ...........................................................................................iv MỞ ĐẦU ...................................................................................................................v MỤC LỤC ...............................................................................................................vii Danh mục hình vẽ ......................................................................................................x Danh mục bảng biểu ................................................................................................xii 1. Tổng quan về bái toán theo dõi đối tượng .............................................................1 1.1. Giới thiệu ........................................................................................................1 1.2. Hệ thống theo dõi đối tượng ...........................................................................3 1.2.1. Phát hiện đối tượng ..................................................................................3 1.2.2. Phân đoạn.................................................................................................5 1.2.3. Theo vết đối tượng...................................................................................6 1.3. Các phương pháp theo vết thông thường........................................................6 1.3.1. So khớp mẫu (Template matching)..........................................................6 1.3.2. Theo vết Meanshift ..................................................................................7 1.3.3. Tiếp cận Bayesian ....................................................................................9 1.4. Kết luận.........................................................................................................14 2. Lọc Particle ..........................................................................................................15 2.1. Giới thiệu ......................................................................................................15 2.2. Nền tảng toán học .........................................................................................17 2.2.1. Phương pháp Monte Carlo.....................................................................19 2.2.2. Phương pháp hàm tích lũy xác suất nghịch đảo ....................................22 vii 2.2.3. Phương pháp lấy mẫu loại trừ................................................................23 2.2.4. Phương pháp Metropolis-Hasting..........................................................24 2.2.5. Phương pháp lấy mẫu quan trọng ..........................................................27 2.3. Phương pháp lấy mẫu quan trọng tuần tự .....................................................31 2.4. Giả lập thuật toán SIS ...................................................................................34 2.5. Các vấn đề về thuật toán SIS ........................................................................37 2.5.1. Sự thoái hóa của thuật toán SIS .............................................................37 2.5.2. Vấn đề chọn hàm mật độ đề xuất...........................................................40 2.5.3. Tái chọn mẫu..........................................................................................43 2.6. Thuật toán lọc Particle ..................................................................................50 2.7. Giả lập thuật toán lọc Particle.......................................................................52 2.8. Nhận xét ........................................................................................................56 3. Mở rộng của lọc Particle và ứng dụng trong theo vết đối tượng dựa vào video .58 3.1. Mở rộng của lọc Particle...............................................................................58 3.1.1. Multi-modal Particle Filter ....................................................................60 3.1.2. Thuật toán ODAPF ................................................................................66 3.1.3. Thuật toán MeanShift Particle ...............................................................70 3.2. Ứng dụng ......................................................................................................75 3.2.1. Phát hiện đối tượng ................................................................................76 3.2.2. Theo vết đối tượng.................................................................................81 3.3. Kết quả ..........................................................................................................84 3.3.1. Kết quả định tính....................................................................................84 3.3.2. Kết quả định lượng ................................................................................90 3.4. Kết luận.........................................................................................................92 4. Kết luận và hướng phát triển................................................................................93 4.1. Kết luận.........................................................................................................93 viii 4.2. Hướng phát triển ...........................................................................................94 DANH MỤC TÀI LIỆU THAM KHẢO.................................................................96 ix Danh mục hình vẽ Hình 1 Ví dụ về phương pháp lấy mẫu loại trừ .......................................................23 Hình 2 Thuật toán Sequential Importance Sampling...............................................34 Hình 3 Dữ liệu giả lập thuật toán SIS ......................................................................35 Hình 4 Kết quả lọc bằng SIS....................................................................................36 Hình 5 Sự thoái hóa của thuật toán SIS ...................................................................37 Hình 6 Ví dụ về trường hợp dẫn đến sai lầm khi chọn hàm mật độ đề xuất tối ưu.43 Hình 7 Thuật toán tái chọn mẫu hệ thống................................................................47 Hình 8 Ví dụ về thuật toán tái chọn mẫu với 3 mẫu ................................................48 Hình 9 Thuật toán Particle Filter .............................................................................51 Hình 10 Dữ liệu giả lập thuật toán lọc Particle........................................................53 Hình 11 Kết quả lọc bằng Particle Filter .................................................................53 Hình 12 Hiện tượng thoái hóa mẫu đã được loại bỏ................................................54 Hình 13 Mật độ đề xuất kết hợp ..............................................................................67 Hình 14 Thuật toán ODAPF Tracker.......................................................................70 Hình 15 Thuật toán Mean Shift kết hợp Particle Filter ...........................................72 Hình 16 Kết quả lọc Particle qua các frame 2, 3, 4, 5, 6 (từ trái qua phải, từ trên xuống dưới) ....................................................................................................................73 Hình 17 Kết quả lọc MS+Particle qua các frame 2, 3, 4, 5, 6 (từ trái qua phải, từ trên xuống dưới).............................................................................................................73 Hình 18 Kết quả lọc Particle qua các frame 12, 13, 14, 15, 15 (từ trái qua phải, từ trên xuống dưới).............................................................................................................74 Hình 19 Kết quả lọc MS+Particle qua các frame 12, 13, 14, 15, 16 (từ trái qua phải, từ trên xuống dưới)................................................................................