Tài liệu Xây dựng hệ thống quan sát và theo vết đối tượng cho robot tự hành

TRƯỜNG ĐẠI HỌC LẠC HỒNG TRUNG TÂM THÔNG TIN TƯ LIỆU *** BÁO CÁO NGHIÊN CỨU KHOA HỌC ĐỀ TÀI: XÂY DỰNG HỆ THỐNG QUAN SÁT VÀ THEO VẾT ĐỐI TƯỢNG CHO ROBOT TỰ HÀNH TRẦN CÔNG CHIẾN BIÊN HÒA, 2012 TRƯỜNG ĐẠI HỌC LẠC HỒNG TRUNG TÂM THÔNG TIN TƯ LIỆU *** BÁO CÁO NGHIÊN CỨU KHOA HỌC ĐỀ TÀI: XÂY DỰNG HỆ THỐNG QUAN SÁT VÀ THEO VẾT ĐỐI TƯỢNG CHO ROBOT TỰ HÀNH CHỦ NHIỆM: HUỲNH CAO TUẤN THỰC HIỆN: TRẦN CÔNG CHIẾN TRẦN THANH VIỆT NGUYỄN ĐÌNH LIÊN BIÊN HÒA, 2012 Mục lục Mục lục ......................................................................................................................... i Các thuật ngữ và từ viết tắt .........................................................................................ii Danh mục hình vẽ ..................................................................................................... iii Mở đầu ........................................................................................................................ 1 Chương 1: Bài toán theo vết đối tượng 1.1. Giới thiệu.............................................................................................................. 3 1.2. Quy trình theo vết đối tƣợng ................................................................................ 5 1.2.1. Phát hiện đối tƣợng ........................................................................................... 5 1.2.2. Phân vùng .......................................................................................................... 6 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 ........................................................................................... 8 1.3.3. Phƣơng pháp Bayesian ...................................................................................... 8 1.3.3.1. Ƣớc lƣợng Bayesian ....................................................................................... 8 1.3.3.2. Một số phƣơng pháp dựa trên ƣớc lƣợng Bayesian ..................................... 10 1.3.3.3. Lọc Kalman .................................................................................................. 11 1.4. Kết luận .............................................................................................................. 12 Chương 2: Lọc hạt (Particle Filter) 2.1. Phƣơng pháp Lọc ............................................................................................... 13 2.2. Nền tảng toán học............................................................................................... 15 2.2.1. Phƣơng pháp Monte Carlo .............................................................................. 18 2.2.2. Phƣơng pháp hàm tích lũy xác suất nghịch đảo .............................................. 20 2.2.3. Phƣơng pháp lấy mẫu loại trừ ......................................................................... 21 2.2.4. Phƣơng pháp Metropolis-Hasting ................................................................... 23 2.2.5. Phƣơng pháp lấy mẫu quan trọng ................................................................... 25 2.2.6. Phƣơng pháp lấy mẫu quan trọng tuần tự ....................................................... 28 2.3. Vấn đề chọn hàm mật độ đề xuất ....................................................................... 31 2.4. Tái chọn mẫu ...................................................................................................... 34 2.4.1. Kích thƣớc mẫu hiệu dụng .............................................................................. 35 2.4.2. Thuật toán tái chọn mẫu .................................................................................. 37 2.5. Các phƣơng pháp quan sát (Observation Models) ............................................ 40 2.5.1. Quan sát dựa vào Hình dáng (Shape Information) ......................................... 41 2.5.2. Quan sát dựa vào Màu (Colour- histogram) ................................................... 42 2.5.3. Quan sát dựa vào Mẫu (Template-based) ....................................................... 45 2.6. Mô hình ƣớc lƣợng trạng thái ............................................................................ 47 2.7. Thuật toán lọc Particle ....................................................................................... 48 2.8. Nhận xét ............................................................................................................. 49 Chương 3: Sử dụng Particle Filter cho bài toán theo vết một đối tượng 3.1. Cài đặt thuật toán Particle Filter ........................................................................ 52 3.1.1. Thử nghiệm với mô hình quan sát dựa vào màu (Colour - histogram) .......... 58 3.1.2. Thử nghiệm với mô hình quan sát dựa vào mẫu (Template - based) ............. 66 3.2. Cải tiến thuật toán - kết hợp lọc Particle và Template Matching ..................... 72 3.2.1. Xây dựng thuật toán PTM (Particle & Template Matching) .......................... 74 3.2.2. Kết quả thử nghiệm ......................................................................................... 75 3.3. Nhận xét ............................................................................................................. 78 Kết luận .................................................................................................................... 79 Tài liệu tham khảo Các thuật ngữ và các từ viết tắt PP CPU RAM HMM SIS PTM Phƣơng pháp Control Processing Unit Random Access Memory Hidden Markov Model Sequential Importance Sampling Particle & Template Matching D nh mục các h nh v Hình 2.4 Hình 2.5 Hình 2.6 Hình 3.1 Hình 3.2 Mô tả Ví dụ về phương pháp lấy mẫu loại trừ Phương pháp lấy mẫu quan trọng tuần tự 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 Ví dụ về thuật toán tái chọn mẫu hệ thống Ví dụ về bộ lọc hạt để khởi tạo và lấy mẫu Biểu đồ màu của khung được chọn Biểu đồ mức độ chính xác của số lượng hạt Minh hoạ các bước tái chọn mẫu Hình 3.3 Hình 3.4 Kết quả sau khi tái chọn mẫu (Resampling) Video người đi bộ 57 68 69 62 Hình 3.5 Hình 3.6 Hình 3.7 Video người chạy xe Video chạy theo xe ôtô Video bình hoa 62 62 62 Hình Hình 2.1 Hình 2.2 Hình 2.3 Trang 23 32 36 42 45 48 D nh mục các ảng số liệu Bảng Bảng 3.1 Bảng 3.2 Bảng 3.3 Mô tả Thử nghiệm Colour-based, số lượng hạt là 50 Thử nghiệm Colour-based, số lượng hạt là 100 Thử nghiệm Colour-based, số lượng hạt là 300 Bảng 3.4 Thử nghiệm Colour-based, số lượng hạt là 500 Bảng 3.5 Bảng 3.6 Thử nghiệm Colour-based, số lượng hạt là 1000 Thử nghiệm Template-based, số lượng hạt là 50 Bảng 3.7 Bảng 3.8 Bảng 3.9 Thử nghiệm Template-based, số lượng hạt là 100 Thử nghiệm Template-based, số lượng hạt là 300 Thử nghiệm Template-based, số lượng hạt là 500 Bảng 3.10 Bảng 3.11 Bảng 3.12 Thử nghiệm Template-based, số lượng hạt là 1000 Thử nghiệm PTM, số lượng hạt là 100 Thử nghiệm PTM, số lượng hạt là 300 Bảng 3.13 Thử nghiệm PTM, số lượng hạt là 500 Trang 64 64 65 65 66 68 69 70 70 71 75 75 76 1 Mở đầu Trong giai đoạn khoa học và công nghệ đang phát triển hiện nay, việc chế tạo Robot nhằm giảm sức lao động cho con ngƣời luôn là mục tiêu của nhiều nghiên cứu trên thế giới. Từ lâu, chúng ta biết đến những Robot công nghiệp trong nhà máy sản xuất xe hơi, các nhà máy sản xuất linh kiện máy tính và một số nghành công nghiệp khác… Hiện nay, ngƣời ta chế tạo những Robot tiên tiến hơn, chúng có thể tự hành trên Sao Hoả để phân tích mẫu vật…Nhƣng nổi tiếng nhất đến giờ có lẽ là ngƣời máy Asimo của hãng Honda nó có thể di chuyển và thực hiện nhiều động tác giống con ngƣời. Một trong những bộ phận quan trọng nhất để Robot có thể tự hành đƣợc đó là hệ thống quan sát và theo vết một mục tiêu định trƣớc. Theo vết đối tƣợng thời gian thực 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 và nó đang là bài toán của nhiều nghiên cứu. Một trong những mục tiêu quan trọng nhất 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 nhƣ 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ột hệ thống thông minh có khả năng thực hiện các bƣớc xử lý ở cấp cao hơn nhƣ nhận dạng đối tƣợng, nhận dạng chuyển động và tính toán trên những đặc trƣng đã thu thập đƣợc. Mặc dù đã đƣợc nghiên cứu nhiều năm nhƣng bài toán “theo vết đối tƣợng” vẫn là vấn đề nghiên cứu thời sự. 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. Việc đặt Camera trên Robot (cùng di chuyển với Robot) khiến cho việc phát hiện và theo vết khó khăn hơn là những bài toán với Camera đặt cố định. Hiện nay, việc nghiên cứu, chế tạo Robot ở các ngành cơ khí và điện tử tại trƣờng Đại học Lạc Hồng đặt ra nhiều bài toán liên quan đến vấn đề xử lý ảnh giúp điểu khiển các Robot này. Đề tài “Xây dựng hệ thống quan sát và theo vết đối tượng cho Robot tự hành” đƣợc thực hiện với hy vọng sẽ góp phần đƣa lĩnh vực thiết kế, chế tạo Robot của trƣờng Lạc Hồng tiến xa hơn nữa trong tƣơng lai. 2 Bố cục của đề tài này bao gồm phần Mở đầu, phần Kết luận và ba chƣơng nội dung đƣợc tổ chức nhƣ sau: Chương 1: Tổng quan về bài toán theo vết đối tượng Chƣơng này đề cập đến các phƣơng pháp, các quy trình cơ bản của bài toán theo vết đối tƣợng. Phân tích, đánh giá ƣu khuyết điểm của từng phƣơng pháp từ đó rút ra kết luận nhằm chọn giải pháp tối ƣu. Chương 2: Lọc hạt (Particle Filter) Chƣơng này trình bày lý thuyết, khái niệm và cơ sở toán học gồm các thuật toán, hàm liên quan đến phƣơng pháp lọc hạt (Particle filter). Chương 3: Sử dụng Particle Filter cho bài toán theo vết một đối tượng Tiến hành thực nghiệm, đánh giá thuật toán thông qua việc chọn số lƣợng hạt và chọn phƣơng pháp quan sát thích hợp cho bài toán. Cải tiến thuật toán Particle filter bằng cách kết hợp với Template Maching nhằm giải quyết các trƣờng hợp lỗi không thể theo vết đƣợc. 3 Chương 1 : Bài toán theo vết đối tượng 1.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ễ. 5 1.2. 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.2.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. 6 1.2.2. 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. 1.2.3. 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. [12] Một số phƣơng pháp theo vết thông thƣờng: • So khớp mẫu • Theo vết Meanshift • Phƣơng pháp Bayesian (lọc Kalman, lọc Particle) 1.3. Các phương pháp theo vết thông thường 1.3.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. 2. 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. 3. 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. 8 1.3.2. 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 Wi   u 1 qu  (b( xi )  u ) 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  2  y x  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. 1.3.3. Phương pháp Bayesian 1.3.3.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      C g , X k Z 1 : k  Z 1:k  X 0:k|Z 1:k  Z 1: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: pX k|Z1:k 1   pZ k| X k 1 p X k 1|Z1:k 1dX k 1 Cập nhật: p X k |Z 1:k 1  pZ k | X k  p X k |Z 1:k 1  pZ k | X k  p X k 1|Z 1:k 1dX k 1 10 1.3.3.2. 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.E.Kalman. 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. Lọc Particle đƣợc phát minh nhằm giải quyết tốt hơn bài toán lọc, đặc biệt là nó có thể khắc phục đƣợc mọi nhƣợc điểm của lọc Kalman và cũng không yêu cầu hệ phải có tập trạng thái hữu hạn. 11 1.3.3.3. Lọc Kalman Vấn đề chung của Kalman Filter [6] là cố gắng ƣớc lƣợng trạng thái x  R m của một quá trình đƣợc kiểm soát theo thời gian rời rạc theo phƣơng trình “stochastic difference” tuyến tính xk  Axk 1  Buk 1  wk 1 với phép đo z  R m là zk  Hxk  vk Các tham số ngẫu nhiên wk và vk thể hiện nhiễu của quá trình và nhiễu của phép đo. Chúng đƣợc giả định là độc lập với nhau, trắng và với phân bố chuẩn. p(w)~N(0,Q) p(v)~N(0,R) Thực tế, các ma trận hiệp biến nhiễu quá trình Q và hiệp biến nhiễu phép đo R có thể thay đổi theo thời gian và phép đo, tuy nhiên chúng ta giả định rằng chúng là hằng số. Lƣu ý rằng các ma trận A,B,H có thể thay đổi theo mỗi bƣớc, nhƣng ta giả định rằng chúng là không đổi. Thuật toán Discrete Kalman Filter: Tóm lại, thuật toán Discrete Kalman Filter là quy trình lặp lại hai bƣớc sau: Bƣớc 1: Time Update (Dự đoán) Ta dự đoán trạng thái và hiệp biến lỗi ƣớc lƣợng tại bƣớc k từ bƣớc k1. 12 xˆk  Axˆk 1  buk 1 Pk  APk 1 AT  Q Bƣớc 2: Measurement Update (Hiệu chỉnh) Nhiệm vụ đầu tiên trong quá trình cập nhật là tính “gain” Kalman, Kk. Kk  Pk H T ( HPk H T  R)1 Kế tiếp, ta đo lƣờng thực tế để đạt đƣợc zk, và sau đó phát sinh ƣớc lƣợng trạng thái x̂k posteriori nhƣ sau: xˆk  xˆ k  K k ( zk  Hxˆ k ) Cuối cùng là ta tính hiệp biến lỗi posteriori: Pk  I  Kk H ) Pk Sau mỗi bƣớc “Dự đoán Hiệu chỉnh“, quá trình “sử dụng ƣớc lƣợng posteriori trƣớc xˆk 1 để dự đoán một ƣớc lƣợng priori mới x̂  lặp lại. Tính k chất đệ quy này là một trong những đặc điểm hấp dẫn của Kalman Filter dễ thực hiện hơn bởi vì nó không phải ƣớc lƣợng trạng thái mới dựa trên tất cả các dữ liệu trƣớc đó. 1.4. Kết luận Trong các phƣơng pháp theo vết hiện nay, mỗi phƣơng pháp có điểm yếu và điểm mạnh của nó. Tuy nhiên, phƣơng pháp lọc Particle có thể khắc phục đƣợc các nhƣợc điểm đó. Nó đƣợc biết nhƣ là phƣơng pháp theo vết tốt nhất hiện nay. Các chƣơng sau, sẽ đƣa ra chi tiết về phƣơng pháp lọc Particle cũng nhƣ ứng dụng lọc Particle vào bài toán theo dõi đối tƣợng. 13 Chương 2: Lọc hạt (Particle Filter) 2.1. Phương pháp Lọc Lọc là bài toán ƣớc lƣợng trạng thái của hệ thống ngay khi một tập các quan sát về hệ thống đó đƣợc thu nhận và có hiệu lực [9]. Các quan sát này có thể bao gồm các tín hiệu thu nhận từ: ra-đa, hệ thống định vị bằng sóng âm, thiết bị thu nhận hình ảnh (video), từ kế, gia tốc kế,… Bài toán này đóng vai trò cực kỳ quan trọng trong rất nhiều lĩnh vực khoa học, công nghệ và kinh tế, tài chính. Để giải bài toán này, chúng ta thực hiện mô hình hóa sự biến đổi của hệ thống và nhiễu trong các quan sát. Kết quả thu đƣợc từ quá trình này thƣờng là các đại lƣợng phi tuyến và có phân phối phi Gauss (NonGaussian). Nhƣ ta đã biết, hai phƣơng pháp tối ƣu đã đƣợc áp dụng là lọc Kalman và lọc HMM. Những phƣơng pháp này cho chúng ta một giải pháp hoàn chỉnh bằng giải tích. Tuy nhiên, để áp dụng, hệ cần phải thỏa những ràng buộc sau • Đối với lọc Kalman: Hệ tuyến tính và nhiễu Gauss. • Đối với lọc HMM: Hệ có tập trạng thái là xác định và hữu hạn. Điều này thực sự gây ra nhiều trở ngại trong việc giải quyết nhiều vấn đề trong thực tế vì nhƣ đã nói ở trên, các độ đo thu đƣợc thƣờng là các đại lƣợng phi tuyến và có phân phối phi Gauss. Vào năm 1979, Anderson và Moore đƣa ra thuật toán lọc Kalman mở rộng. Thuật toán này là một trong những thuật toán tốt nhất để giải bài toán phi Gauss và phi tuyến lúc bấy giờ. Thuật toán này hoạt động dựa trên ý tƣởng tuyến tính hóa các quan sát thu đƣợc bằng cách ƣớc lƣợng các đại lƣợng này bằng một chuỗi khai triển Taylor. Tuy nhiên, trong nhiều trƣờng hợp, chuỗi ƣớc lƣợng trong EKF mô hình hóa rất kém những hàm phi tuyến và phân phối xác suất cần quan tâm. Và kết quả là thuật toán sẽ không hội tụ. 14 Vào năm 1996, Julier và Uhlmann đề xuất một thuật toán lọc dựa trên quan điểm rằng để xấp xỉ một hàm phân phối xác suất dạng Gauss thì dễ hơn là phải xấp xỉ một hàm phân phối phi tuyến bất kỳ. Thuật toán này đƣợc đặt tên là Unscented Kalman Filter (UKF). Thuật toán này đã đƣợc chứng minh là có kết quả tốt hơn EKF. Tuy nhiên, một lần nữa, giới hạn của UKF là nó không thể đƣợc áp dụng trong các bài toán có phân phối phi Gauss tổng quát. Các bộ lọc kể trên đều hoạt động dựa vào nhiều giả định của hệ nhằm đảm bảo về khả năng giải quyết bài toán bằng các phƣơng trình giải tích. Tuy nhiên, nhƣ trên đã nói, dữ liệu trong thực tế có thể rất phức tạp, thông thƣờng bao gồm nhiều thành phần phi Gauss, phi tuyến và rất lớn. Điều này làm cho việc tìm ra một giải pháp hợp lý bằng phƣơng pháp giải tích là hầu nhƣ không thể. Vào khoảng năm 1998, sự ra đời của thuật toán CONDENSATION [2] và một loạt các thuật toán lọc tổng quát dựa vào phƣơng pháp Tuần Tự Monte Carlo (Sequential Monte Carlo – SMC) với nhiều tên gọi khác nhau nhƣ lọc Bootstrap (Bootstrap Filters), lọc Particle (Particle Filters), lọc Monte Carlo (Monte Carlo Filters) đƣợc ra đời, đã giúp giải quyết bài toán lọc tổng quát một cách triệt để. Các phƣơng pháp này không đòi hỏi phải đặt ra bất kỳ giả định nào về hệ, ngoài ra, chúng còn rất linh động, mềm dẻo, dễ cài đặt, có khả năng mở rộng để thực hiện trong môi trƣờng tính toán song song và đặc biệt là hoạt động rất hiệu quả trong trƣờng hợp bài toán tổng quát. Gần đây, các phƣơng pháp này đƣợc thống nhất gọi với tên gọi lọc Particle. Lọc Particle hiện đang đƣợc áp dụng trong rất nhiều lĩnh vực nhƣ mô hình hóa tài chính, kinh tế lƣợng (Econometrics), theo dõi đối tƣợng, dẫn đƣờng cho tên lửa (Missle Guidance), di chuyển dựa vào địa hình (Terrain Navigation), thị giác máy tính, mạng neuron, máy học, robot,... Ứng dụng của lọc Particle trong thị giác máy tính đang đƣợc rất nhiều ngƣời quan tâm, đặc biệt là trong lĩnh vực theo vết đối tƣợng dựa vào thông tin thị giác.