Ứng dụng lọc Particle trong bài toán theo vết đối tượng: Luận văn

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

Nhận xét của giáo viên hướng dẫn

.......................................................................................................................................

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).

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.

• 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.

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

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).........................................................................................................74

Hình 20 Hình nền và mặt nạ vùng chuyển động......................................................78

Hình 21 Kết quả học nền .........................................................................................79

Hình 22 Kết quả phát hiện đối tượng.......................................................................80

Hình 23 Thuật toán phát hiện đối tượng dựa trên luật.............................................81

Hình 24 Mô hình màu đa vùng ................................................................................83

Hình 25 Một kết quả thành công của ODAPF.........................................................86

Hình 26 Một kết quả thành công của ODAPF.........................................................87

Hình 27 Một kết quả theo dõi đa đối tượng.............................................................88

Hình 28 Thuật toán ODAPF bù lỗi cho thuật toán phát hiện đối tượng..................88

Hình 29 Thuật toán ODAPF bù lỗi cho thuật toán phát hiện đối tượng..................89

Hình 30 Thuật toán ODAPF bù lỗi cho thuật toán phát hiện đối tượng..................89

Hình 31 Trường hợp lỗi của ODAPF ......................................................................89

Hình 32 Trường hợp lỗi của ODAPF ......................................................................90

Hình 33 Trường hợp lỗi của ODAPF ......................................................................90

Danh mục bảng biểu

Bảng 1 Kết quả so sánh Mean Square Error của SIS và thuật toán lọc Particle (N =

50 mẫu)...........................................................................................................................54

Bảng 2 Kết quả so sánh Mean Square Error của SIS và thuật toán lọc Particle (N =

100 mẫu).........................................................................................................................55

Bảng 3 Kết quả so sánh Mean Square Error của SIS và thuật toán lọc Particle (N =

150 mẫu).........................................................................................................................55

Bảng 4 Kết quả so sánh Mean Square Error của SIS và thuật toán lọc Particle (N =

200 mẫu).........................................................................................................................55

Bảng 5 Kết quả phát hiện và theo dõi đối tượng dùng thuật toán ODAPF đối với

những đoạn video ở góc quay 1 .....................................................................................91

Bảng 6 Kết quả phát hiện và theo dõi đối tượng dùng thuật toán ODAPF đối với

những đoạn video ở góc quay 2 .....................................................................................91

xii

Luận văn tốt nghiệp

1. Tổng quan về bài toán theo dõi đối tượng

1.1. Giới thiệ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ột trong những mục tiêu quan trọng nhất của theo dõi đố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ó thể thực hiện các bước xử lý khác ở cấp cao hơn như nhận dạng đối

tượng, nhận dạng chuyển động, lý luận (reasoning) và tính toán trên những đặc trưng

vật lý này.

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 [Guo2001]. 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. Nếu như chỉ có

một vài đặc trưng thị giác, 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ế lại hoàn toàn khác, ví dụ như khuôn mặt của một người cụ thể sẽ có đầy đủ các

chi tiết tri giác và thông tin nhiễu chẳng hạn như các tư thế và sự chiếu sáng khác nhau,

rất khó để mà 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 một đối tượng chuyển động qua vùng quan sát của camera, hình ảnh

Luận văn tốt nghiệp

về đối tượng có thể thay đổi rất nhiều. Sự thay đổi này đến từ 3 nguồn chính: sự thay

đổi tư thế đối tượng đích hay sự biến dạng của đối tượng đích, sự thay đổi về độ chiếu

sáng, và sự che khuất (occlusion) một phần hay toàn bộ đối tượng đích.

Có rất nhiều phương pháp giải quyết bài toán này, ta có thể phân loại thành bốn

cách tiếp cận chính: tiếp cận dựa trên mô hình, tiếp cận dựa trên miền, tiếp cận dựa trên

đường viền và tiếp cận dựa trên đặc trưng.

• Tiếp cận dựa trên mô hình

Cách tiếp cận dựa trên mô hình bao gồm việc tạo mô hình hình học cấu

trúc của đối tượng. Các ràng buộc trên việc mô hình được cho phép biến

dạng như thế nào có thể được kết hợp vào quá trình so khớp. Vấn đề với

cách tiếp cận này là quá trình khởi tạo tự động thì khó và chi phí tính toán

cao do độ phức tạp của mô hình.

• Tiếp cận dựa trên miền

Cách tiếp cận dựa trên miền bao gồm việc 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 phép đo

độ tương tự. Lợi ích của cách tiếp cận 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. Các tham số của thuật toán

cũng có ý nghĩa vật lý, dễ dàng khái niệm hóa.

• Tiếp cận dựa trên đường viền

Cách tiếp cận dựa trên đường viền bao gồm tìm đường viền bao của một

đố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. Nơi khớp nhất sẽ là đường viền hiện tại, mô hình sẽ cập nhật

đường viền hiện tại để phản ánh hình dáng của đối tượng trong frame hiện

tại. 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

Luận văn tốt nghiệp

phần (partial occlusion). Tuy nhiên vấn đề với mô hình là nó yêu cầu sự khởi

tạo chính xác, và điều này thì khó để thực hiện tự động.

• Tiếp cận dựa trên đặc trưng

Khác với các cách tiếp cận trên đều theo vết toàn bộ đối tượng, cách tiếp

cận 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. Ví

dụ như 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ác đặc trưng vẫn còn

thấy được và có thể được 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, nó thì không phải là một nhiệm vụ dễ.

1.2. Hệ thống theo dõi đố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 (Object Detection)

• Phân đoạn (Segmentation)

• Theo vết đối tượng (Object Tracking)

Dưới đây, sẽ mô tả nhiệm vụ của mỗi phần và một số cách tiếp cận để giải quyết

các phần trên. Các hệ thống theo dõi hiệu quả thường kết hợp nhiều phương pháp khác

nhau.

1.2.1. Phát hiện đối tượng

Phát hiện đối tượng trong video [Guo2001] là xác minh sự hiện diện của một đối tượng

trong chuỗi ảnh và cũng có thể định vị chính xác. Các hệ thống theo dõi đối tượng

Luận văn tốt nghiệp

thường bắt đầu bằng quá trình phát hiện đối tượng, ngoài ra phát hiện đối tượng được

lặp lại trong chuỗi ảnh sau thường cần thiết hỗ trợ và xác minh cho quá trình theo vết.

Một số cách tiếp cận phát hiện đối tượng thông dụng:

a) Phát hiện đối tượng dựa trên đặc trưng

Tùy vào đặc trưng được chọn, ta có các cách tiếp cận khác nhau như:

dựa trên hình dáng, dựa trên màu sắc. Trong đó, cách tiếp cận dựa trên màu

sắc được xem là thông dụng nhất vì đặc trưng màu sắc thì dễ dàng lấy được

và chi phí tính toán thấp.

b) Phát hiện đối tượng dựa trên mẫu

Nếu như có một 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 dưới sự phân

tích. Phát hiện đối tượng với việc so khớp chính xác thường tốn nhiều chi

phí và chất lượng so khớp phụ thuộc vào chi tiết và mức độ chính xác của

mẫu đối tượng. Có hai kiểu so khớp mẫu, so khớp mẫu cố định và so khớp

mẫu biến dạng.

c) Phát hiện đối tượng chuyển động

Phần lớn các nghiên cứu về cách giải quyết bài toán theo dõi đối tượng

được tập trung trên vấn đề phát hiện đối tượng chuyển động trong thập kỷ

qua. Bởi hầu hết các hệ thống theo dõi thì 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 đề

nghị. Chúng được phân loại tương đối thành các nhóm sau.

• Dựa trên các kỹ thuật lấy ngưỡng

Cách tiếp cận này dựa trên việc phát hiện những thay đổi theo

thời gian tại mức pixel hay khối. 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

Luận văn tốt nghiệp

pháp theo cách tiếp cận này như: 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.

• Dựa trên các kiểm tra thống kê

Sự khác biệt giữa các frame được mô hình như hỗn hợp của phân

bố Gaussian và Laplacian.

• Dựa trên việc xây dựng hàm chi phí toàn cục

Vấn đề phát hiện chuyển động được đưa vào công thức nhằm

giảm thiểu hàm mục tiêu toàn cục. Mô hình được sử dụng rộng rãi là

các trường ngẫu nhiên Markov theo không gian (Spatial Markov

Random Fields) qua phân bố Gibbs. Phương pháp này thì mạnh,

nhưng cũng tốn khá nhiều chi phí.

1.2.2. Phân đoạn

Phân đoạn các chuỗi ảnh [Smith1997] 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. Việc phân đoạn này 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 đoạn dựa trên các phép đo cục bộ (Local Measurements)

• Phân đoạn dựa trên phân cụm đơn giản (Simple Clustering) hay sự mâu

thuẫn với vận tốc nền (Inconsistency with Background Flow)

• Phân đoạn dựa trên các phép biến đổi ảnh phân tích (Analytic Image

Transformations)

• Phân đoạn dựa trên quá trình quy tắc hóa (Regularization)

Luận văn tốt nghiệp

• Phân đoạn dựa trên phân cụm có sắp xếp toàn cục (Globally Organized

Clustering)

1.2.3. Theo vết đối tượng

Theo vết đối tượng [Guo2001] 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 video, bao gồm sự hiện diện, vị trí, kích thước, hình

dáng… của đối tượng.

Một số phương pháp theo vết thông thường:

• So khớp mẫu

• Theo vết Meanshift

• Tiếp cận 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)

Thủ tục trong so khớp mẫu như sau: 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 [Krattenthaler1994]. 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 dạng lớn cũng có thể được

theo vết [Jain1996]. 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, 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.

Luận văn tốt nghiệp

Bằng cách này, các đạo hàm nhỏ liên quan đến nhiễu sẽ là trung bình, do đó

gia tăng được khả năng theo vết tránh nhiễu.

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 đ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.

1.3.2. Theo vết Meanshift

Dorin Comaniciu đã giới thiệu phương pháp theo vết màu Meanshift [Comaniciu2003].

Đâ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ố

. iw

)

−

(1)

( ( xb δ

)

w i

∑

1 =

ˆ q u )ˆ(ˆ yp u 0

là giá trị tại màu u của mô hình đích, và

Với b(xi) là giá trị màu tại xi và

uqˆ

)ˆ(ˆ 0ypu

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:

Luận văn tốt nghiệp

gwx i i

∑

− h

⎞ ⎟ ⎟ ⎠

⎛ ⎜ ⎜ ⎝

(2)

1ˆ y

gw i

∑

− h

⎞ ⎟ ⎟ ⎠

⎛ ⎜ ⎜ ⎝

xg )(

xk )('

−=

Với

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.

Các bước tính toán cơ bản trong phương pháp theo vết Meanshift:

và vị trí của nó trong frame trước

Cho trước mô hình đích { }

ˆu q

0ˆy

1...

1. Khởi tạo vị trí của đích trong frame hiện tại với

, tính mô hình ứng viên

0ˆy

và tính

ρ [

ˆ q , ]

)

{

( ˆ ˆ p y

ˆ ˆ( p y u

}0 )

ˆ ˆ ˆ p y q ( u u 0

= m 1...

= ∑

= 1

theo (1)

2. Tính được các trọng số

3. Tìm vị trí đích ứng viên kế tiếp theo (2)

và

tính

được

4. Tính

mô

hình

mới

{

ˆ ˆ( p y u

}1 )

= m 1...

ρ [

ˆ q , ]

)

( )1 ˆ ˆ p y

ˆ ˆ ˆ p y q ( u u 1

= ∑

= 1

ˆ y

←

5. Trong khi

, thực hiện

(

( ˆˆ[ yp

) ]ˆ, q

ˆ y 1

) ( ˆˆ[ ]ˆ, qyp 1

1 2

ε<

6. Nếu

thì dừng, nếu không

ˆ y ← , tiếp tục bước 2. 0

ˆ y 1

ˆ y − 0

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.

Luận văn tốt nghiệp

1.3.3. Tiếp cận Bayesian

1.3.3.1. Ước lượng Bayesian

Tiếp cận theo phương pháp Bayesian [Morrell2003] 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 (prediction) để dự đoán trạng thái của đối tượng và

phương trình cập nhật (updation) - hay còn gọi là hàm trơn (smoothing) - để 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 (observation) trên đối tượng.

Quy ước một số ký hiệu sau:

Đối với trạng thái (quá trình không được biết):

• Chuỗi các trạng thái từ thời điểm 0 đến k:

0:k

X , X ,...,X 1

• Chuỗi các giá trị trạng thái từ thời điểm 0 đến k:

0:k

x , x ,..., x 1

• Hàm mật độ của

: kX

)k ( p x

đến

• Hàm mật độ ghép từ

( p x

)

0:k

( p x , x ,..., x 1

Tương tự, đối với quá trình quan sát

• Chuỗi các quan sát từ thời điểm 1 đến k:

1:k

Z , Z ,..., Z 2

• Giá trị quan sát tại thời điểm k:

• Hàm mật độ của

: kZ

)kp z (

đến

• Hàm mật độ ghép từ

)

( p z

)

1:k

( p z ,z ,...,z 2

Mục tiêu của phương pháp Bayesian là ước lượng trạng thái

dựa trên

. Ta

1:kZ

ký hiệu, giá trị ước lượng

dựa trên

là

ˆX

1:kZ

k|k

Dễ thấy, giá trị ước lượng trên là một hàm phụ thuộc các quan sát:

ˆX

( g Z=

)

k|k

1:k

Luận văn tốt nghiệp

Lỗi ước lượng:

(cid:4) X

ˆ X

= − X k

k|k

Hàm chi phí như là bình phương cho lỗi ước lượng:

−

ˆ x

− ˆ x

)

(

) (

)

( ˆ C x , x k|k

k|k

Mục tiêu của ước lượng Bayesian là tìm dạng hàm

sao cho giảm thiểu chi phí

( )g .

kỳ vọng:

C g Z ,X

(

)

(

1:k

( ˆ C X ,X k|k

⎡ ⎢ ⎣

⎤ ) ⎥ ⎦

⎡ ⎢ ⎣

⎤ ) ⎥ ⎦

X ,Z 0:k

1:k

0:k

sao cho giảm

Ta có thể giảm thiểu chi phí kỳ vọng toàn thể bằng cách chọn

( )g .

thiểu kỳ vọng điều kiện cho mỗi giá trị

. Chi phí kỳ vọng này có thể được viết như

1:kz

, X

)

( ( C g z

1:k

⎡ ⎢ ⎣

⎤ ) ⎥ ⎦

1:k

X | 0:k

1:k

= z 1:k

⎡ ⎢ ⎢ ⎣

⎤ ⎥ ⎥ ⎦

Lúc này, hàm

sẽ tối ưu khi

[

]

( g Z

)

1:k

X |z k

1:k

Đó là nguồn gốc cho việc tính mật độ xác suất sau (posterior density) (

)

p x | z k

1:k

trong phương pháp lọc Bayesian.

qua hai bước:

Phương pháp lọc Bayesian được thực hiện đệ quy đối với (

)

p x | z k

1:k

Dự đoán:

| z

)

) ( p x

)

( p x | z k

− 1:k 1

( p x | x k

− k 1

− 1:k 1

− k 1

= ∫

Cập nhật:

) (

)

( p z | x p x | z k

− 1:k 1

)

( p x | z k

1:k

) (

)

( p z | x p x | z k

− 1:k 1

∫

Luận văn tốt nghiệp

1.3.3.2. Một số phương pháp dựa trên ước lượng Bayesian

Một số phương pháp theo vết thông dụng dựa trên ước lượng Bayesian là:

• Lọc Kalman

• Lọc HMM

• 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 HMM (Hidden Markov Model) là thuật toán lọc tối ưu rời rạc. Nó không đòi

hỏi những yêu cầu về tuyến tính cũng như phân phối của hệ. Tuy nhiên, lọc HMM chỉ

có thể được áp dụng trong trường hợp hệ có trạng thái hữu hạn và xác định.

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.

1.3.3.3. Lọc Kalman

Vấn đề chung của Kalman Filter [Welch2003] là cố gắng ước lượng trạng thái

x ∈R

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

− 1

− 1k

là

với phép đo

z ∈R

z Hx =

vk +

Luận văn tốt nghiệp

Các tham số ngẫu nhiên

và

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 Q ) ) ~ (0,

(

p v

( ) ~ (0,

N R )

và hiệp biến nhiễu phép đo

Thực tế, các ma trận hiệp biến nhiễu quá trình

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 k-1.

−

ˆ x

ˆ Ax

1 −

−

AP A Q +

1 −

Bước 2: Measurement Update (Hiệu chỉnh)

Nhiệm vụ đầu tiên trong suốt quá trình cập nhật là tính “gain” Kalman,

kK .

−

1 −

P H HP H (

)

, và sau đó phát sinh ước lượng trạng

Kế tiếp, ta đo lường thực tế để đạt được

thái posteriori

ˆkx như sau:

−

(

)

ˆ x

ˆ K z Hx

−

Cuối cùng là ta tính hiệp biến lỗi posteriori:

I K H P −

)

(

−

Luận văn tốt nghiệp

Sau mỗi bước Dự đóan_Hiệu chỉnh, quá trình “sử dụng ước lượng posteriori trước

” lặp lại. Tính chất đệ quy này là một

1ˆkx − để dự đoán một ước lượng priori mới ˆkx −

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.3.3.4. Lọc Kalman mở rộng(Extended Kalman)

Lọc Kalman ban đầu không thể áp dụng được cho trường hợp phi tuyến tính. Vì thế

một số nghiên cứu mở rộng được thực hiện trên lọc Kalman nhằm giải quyết các các

vấn đề phi tuyến và không phải nhiễu Gauss. Phương pháp thông dụng nhất đã được

biết là lọc Extended Kalman [Welch2003] (Gelb 1996; Grewal và Andrew 1993;

Jazwinski 1970). Đây là hệ thống phi tuyến tính được định nghĩa bởi:

) ,u ,w

( x = f x k

k -1

)

( z = h x ,vk

và

thể hiện nhiễu của quá trình và nhiễu của phép

Các tham số ngẫu nhiên

đo như trong thuật toán lọc Kalman trên.

Trong thực tế, dĩ nhiên ta không biết các giá trị nhiễu tại mỗi bước. tuy nhiên, ta có

thê tính xấp xỉ vector trạng thái và phép đo mà không cần giá trị nhiễu.

( (cid:4)k ˆ x = f x

k -1

) ,u ,0 k

( ) (cid:4) (cid:4)k z = h x ,0 k

Với ˆkx là ước lượng posterior của trạng thái (từ thời điểm trước bước

Thuật toán Extended Kalman Filter:

Thuật toán Extended Kalman là quy trình lặp lại của 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 k-1.

( (cid:4)k ˆ x = f x

k -1

) ,u ,0 k

Luận văn tốt nghiệp

−

− 1

P k

T A P A W Q W k

+T k

và

là các Jocobian quá trình tại bước

là hiệp biến nhiễu quá trình

Với

tại bước

Bước 2: Measurement Update (Hiệu chỉnh)

Nhiệm vụ đầu tiên trong suốt quá trình cập nhật là tính “gain” Kalman,

kK .

−

− 1

)

P H H P H ( k

T k

V R V T k k

Kế tiếp, ta đo lường thực tế để đạt được

, và sau đó phát sinh ước lượng trạng

thái posteriori

ˆkx như sau:

−

ˆ x

ˆ h x (

))

ˆ = + x k

K z ( k

Cuối cùng là ta tính hiệp biến lỗi posteriori:

−

= − (

)

P k

I K H P k

và

là các Jacobian phép đo tại bước

là hiệp biến nhiễu phép đo

Với

tại bước

Tuy phương pháp Extended Kalman Filter khắc phục được nhược điểm của phương

pháp lọc Kalman, nhưng nó cũng thường không chính xác trong giai đoạn khởi tạo và

thiếu mạnh mẽ.

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.

Luận văn tốt nghiệp

2. Lọc Particle

2.1. Giới thiệu

Lọc (Filtering) 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 [Merwe2000]. 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 phép đo

(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 (Non-Gaussian).

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

(Analytical Solution). 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

(Extended Kalman Filter - EKF). 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 (Linearization) 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ụ.

Luận văn tốt nghiệp

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 (theo nghĩa dữ liệu có rất nhiều chiều). Đ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, cùng với sự ra đời của thuật toán CONDENSATION

[Blake1998], một loạt các thuật toán lọc tổng quát dựa vào phương pháp Monte Carlo

Tuần Tự (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 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

Luận văn tốt nghiệp

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.

2.2. Nền tảng toán học

Trước khi tiếp tục xem xét về lọc Particle, sẽ là cần thiết nếu chúng ta nhắc lại một số

các quy ước toán học và phát biểu của bài toán lọc cần quan tâm. Không mất tính tổng

quát, ta xét một hệ (có thể là một hệ tín hiệu; hệ cơ học trong đó có các đại lượng vị trí, vận tốc, gia tốc;...) có không gian trạng thái được mô hình hóa bởi một hàm phân phối1

phi tuyến, phi Gauss, thỏa 2 giả định của bài toán lọc Bayes đệ quy như sau

(2.1)

|t x x

| x x t

• Chuỗi trạng thái (xích trạng thái) của hệ thỏa giả định về hệ Markov bậc I )

(

)

(

t 0: 1 −

1 −

bất kỳ chỉ phụ thuộc vào trạng thái

• Các giá trị độ đo có được tại một thời điểm

của hệ tại thời điểm đó

(2.2)

(

z x ) |

(

)

z t 1:

x t 1:

= ∏

1 =

x

X của hệ có phân phối xác suất ban đầu

;

t ∈

∈

Các trạng thái {

} x(cid:96) ,

)0 ( p x và

xác suất chuyển trạng thái

z

Y là các quan sát tương ứng

;

t ∈

∈

, {

} z(cid:96) * ,

|t x x

(

−

với các thời điểm. Đồng thời, ta định nghĩa

x

(cid:22) … và ,

(cid:22) … lần , z

{

}

{

tx 0:

tz 1:

1, z

lượt là chuỗi trạng thái và chuỗi quan sát cho đến thời điểm t .

Vậy hệ đang xét có thể được đặc trưng bởi các hàm phân phối xác suất sau

1 Kể từ phần này trở đi, để tiện cho việc ký hiệu và nếu không có gì quá nhầm lẫn về ngữ nghĩa, chúng ta sẽ

trong trường hợp không gian trạng thái rời

dùng qua lại giữa thuật ngữ phân phối xác suất

x

z

(

)

trong trường hợp không gian trạng thái liên tục. Bên cạnh đó, các ký hiệu

rạc và mật độ xác suất

( p x z

)

( )p i

của mật độ xác suất sẽ được sử dụng như ký hiệu chung của hai khái niệm này.

Luận văn tốt nghiệp

x

) ,

≥

( p

≥

) )

( | x x t t 1 − ( | z x t

Mục tiêu của bài toán lọc là tìm được lời giải cho phân phối xác suất posterior

, các đại lượng đặc trưng của nó (quan trọng nhất là phân phối lề

( p x

)

|t 0:

z 1: t

, còn được gọi là mật độ lọc – filtering distribution) và kỳ vọng toán học

p x z ) ( |t

1: t

(cid:22)

x

= Ε

(

)

(

)

(

)

(

)

0: t

z 1: t

tx d 0:

x

(

)

⎡ ⎣

⎤ ⎦

z 1: t

t 0:

∫

(

với

(cid:92) là hàm khả tích bất kỳ, tương ứng với

. Các ví dụ

)1 t + →X

( p x

)

|t 0:

z 1: t

về hàm này bao gồm trung bình có điều kiện (Conditional Mean)

x

x hoặc

(

)0:

t 0:

hiệp

phương

sai

có

điều

kiện

(Conditional

Covariance)

x

−

(

)

T x x t t

T p

⎡ ⎣

⎤ ⎦

⎡ ⎣

⎤ ⎦

(

)

(

)

x z | t t 1:

Tại một thời điểm

bất kỳ, hàm phân phối xác suất posterior được cho bởi quy tắc

Bayes như sau

x

t 0:

x

t 0:

z 1: t

(

)

z t 1: x |

) p

( x

p (

)

p (

)

( z 1: t

t 0:

) t 0: x td 0:

∫

Và phương trình đệ quy để tính phân phối xác suất đồng thời

được

x

(

)

0: 1 t +

z 1: 1 t +

cho bởi

z

x

(

)

1 +

x

(

)

(

)

t 0:

z t 1:

t 0: 1 +

z t 1: 1 +

| 1 + p

x t 1 + ( z

x )

( p | z t 1:

1 +

Ta cũng có thể tính hàm phân phối lề

bằng các phương trình đệ quy như

( p x z |t

)1:

• Phương trình dự đoán

x

x z | t

x x | t

(

)

(

)

(

)

1: 1 t −

1 −

z 1: 1 t −

x − td 1

= ∫

• Phương trình cập nhật

Luận văn tốt nghiệp

1: 1 t −

x z | t 1: t

(

)

) p )

( z x | t t ( z x | p t

( x z | t ( x z | p t

) )

1: 1 t −

p ∫

Những phương trình và biểu thức đệ quy ở trên tuy có vẻ đơn giản nhưng trong

thực tế, chúng ta không thể tính được chúng bởi để tính được

và

(

)

z x | t

x z | t

(

)

1: 1 t −

∫

, đòi hỏi phải thực hiện phép tính tích phân trong đó dữ liệu có

x

(

)

(

)

t 0:

z |t 1:

x td 0:

t 0:

∫ số chiều rà rất lớn và rất phức tạp.

Không giống như các phương pháp dựa vào giải tích, trong đó mỗi phương pháp

luôn cố gắng tìm kiếm một lời giải cho các phương trình trên thông qua một hoặc nhiều

phương trình khác, các phương pháp Monte Carlo dựa vào sự mô phỏng và xấp xỉ các

hàm phân phối và các tích phân trên bằng một tập các mẫu dữ liệu được sinh ra bởi

chính các hàm phân phối trong các tích phân này. Đây là lý do chính giúp cho các thuật

toán lọc dựa vào phương pháp Monte Carlo, cụ thể là lọc Particle, có thể giải quyết

được vấn đề phi tuyến và phi Gauss một cách triệt để và rất hiệu quả.

2.2.1. Phương pháp Monte Carlo

Trong phần này, chúng ta sẽ xem xét một trong những nền tảng lý thuyết quan trọng

nhất – phương pháp Monte Carlo – của lọc Particle. Không mất tính tổng quát, ta xem

xét bài toán tính tích phân trong đó dữ liệu rất lớn, nhiều chiều (High-Dimensional

Intergral) như sau

(2.3)

x

x z |

x

(

)

(

)

(

)

Trong đó,

= ∫ )

( ) i là một hàm

( p x z - khả tích. Giả sử ta có thể sinh ngẫu nhiên

mẫu ngẫu nhiên phân phối độc lập và đồng nhất (Independent and Identically

( ) i

Distributed – i.i.d)

;

… N từ phân phối xác suất

i =

( p x z . Như vậy, phân phối

)

{ x

}

có thể được ước lượng như sau

xác suất

p x z) ( |

Luận văn tốt nghiệp

x

(2.4)

(

)

( ) (

) x d

P N

1 = ∑ x δ N

1 =

Trong đó,

( )ix . Vậy,

có thể được

) x ký hiệu hàm delta-Dirac có tâm tại

(

)

( ) ( i dδ x

xấp xỉ bằng tích phân Monte Carlo (Monte Carlo Integration) như sau

( ) i

(2.5)

x

(

)

(

)

(

)

P N

)

(

∫

1 N = ∑ N = i 1

Biểu thức ướng lượng trong (2.5) hợp lệ vì theo luật mạnh số lớn, nếu phương sai

(cid:22)

x

< +∞

được cho

thì phương sai của

của

(

)

(

)

) ( f x thỏa

(

)

2 δ f

| x z

(

)

⎡ ⎣

⎤ ⎦ −

var

bởi

. Vậy ta có

(

)

(

)

2 δ f N

, với xác suất 1.

(2.6)

(

)

(

)

.a s → →+∞

là ký hiệu của “hội tụ hầu chắc chắn” (Almost Sure Convergence).

Trong đó

.a s →

Hơn nữa, vì

fδ < +∞ (hữu hạn) nên định lý giới hạn trung tâm được thỏa, nghĩa là

−

(2.7)

(

)

(

)

)20, ( N δ f

⎡ N I ⎣

⎤ ⎦

⇒ →+∞

Trong đó

ký hiệu cho hội tụ trong phân phối xác suất. Từ những lập luận trên,

⇒

( ) i

ta thấy, dùng tập các mẫu ngẫu nhiên

;

… N , ta có thể dễ dàng ước lượng

i =

{ x

}

. Dựa vào ước lượng này, kết hợp với phương trình (2.7), ta cũng có thể dễ

được

(

)

dàng tính được mức độ hội tụ của phép ước lượng, hay mức độ lỗi của nó.

Không những thế, điểm mạnh của phương pháp tích phân Monte Carlo còn nằm ở

chỗ nó không phụ thuộc vào số chiều của dữ liệu. Thật vậy, nếu ta phải tính (2.3) bằng

1/ n x

hóa bằng một phương trình giải tích, độ chính xác của phéwp xấp xỉ sẽ là

phương pháp xấp xỉ tích phân Riemann, trong đó không gian trạng thái được mô hình )

( O N −

đối với tích phân trên miền dữ liệu có số chiều là

, nghĩa là mức độ hội tụ của phép

Luận văn tốt nghiệp

xấp xỉ càng giảm khi số chiều của phép tính tích phân càng tăng. Trong khi đó, áp dụng

phương pháp tích phân Monte Carlo, phương pháp mô phỏng ngẫu nhiên không gian

1/ 2

và

trạng thái từ phân phối xác suất của nó, độ chính xác của phép xấp xỉ là

( O N −

)

của dữ liệu. Điều này có nghĩa là, phương pháp tích

không phụ thuộc vào số chiều

phân Monte Carlo độc lập với số chiều của phép tính tích phân.

Tuy nhiên, một vấn đề gặp phải khi áp dụng phương pháp tích phân Monte Carlo

chính là làm sao để có thể tạo ra một tập các mẫu ngẫu nhiên từ phân phối xác suất

đích

bất kỳ một cách hiệu quả. Thật không may là chúng ta thường không có

p x z) ( |

cách nào để sinh ra tập mẫu này một cách trực tiếp từ phân phối xác suất đích

) ( p x z , |

vì

, trong trường hợp tổng quát, thường là đa biến và không có một dạng chuẩn

p x z) ( |

nhất định (non-standard) mà chúng ta có thể biết trước (dạng của

có thể biến

( p x z

)

đổi theo thời gian).

Vì vậy, nhiều phương pháp gián tiếp để sinh ra tập các mẫu dữ liệu này đã được

phát triển. Trong đó có các phương pháp chính yếu sau

• Phương pháp hàm tích lũy xác suất nghịch đảo (Inversed CDF).

• Phương pháp lấy mẫu loại trừ (Rejection Sampling).

• Thuật toán Metropolis-Hastings (Metropolis Hastings Algorithm).

• Phương pháp lấy mẫu quan trọng (Importance Sampling - IS).

Trong đó, phương pháp lấy mẫu quan trọng chính là phương pháp được sử dụng

trong lọc Particle. Chúng ta sẽ xem xét một cách tóm tắt các phương pháp trên, phân

tích các điểm mạnh điểm yếu của chúng, và tại sao IS lại được sử dụng trước khi đi vào

nội dung chính của phương pháp lọc Particle.

Luận văn tốt nghiệp

2.2.2. Phương pháp hàm tích lũy xác suất nghịch đảo

Phương pháp này (Inversed CDF - ICDF) là phương pháp cổ điển và đơn giản nhất

được sử dụng để sinh một mẫu ngẫu nhiên từ một hàm mật độ (phân phối) xác suất bất

kỳ. Phương pháp này được phát biểu như sau. Cho trước một biến ngẫu nhiên X , có

hàm mật độ xác suất

. Bài toán đặt ra là sinh các giá trị ngẫu nhiên tương ứng

x

(

)

với biến ngẫu nhiên nói trên.

Gọi

là hàm tích lũy xác suất của

x

(

)

(

) x dx

(

) x . Giả sử tồn tại hàm

F X

nghịch đảo

f= ∫ ) (

XF − x của hàm tích lũy xác suất này. Vậy mẫu ngẫu nhiên có thể được

sinh ra bằng thuật toán sau

• Bước 1: Sinh ngẫu nhiên

∼ u U ⎡

0,1 ⎤ ⎦

⎣

• Bước 2: Giải

)

( u−=x XF

x

thu được từ thuật toán chính là mẫu ngẫu nhiên được sinh

Bằng cách này, giá trị

ra từ hàm mật độ xác suất

x

(

)

(

) x dx , tương ứng

(

) x và tích lũy xác suất

F X

f= ∫

với biến ngẫu nhiên X .

Thoạt nhìn, phương pháp ICDF có thể được sử dụng trong nhiều ứng dụng và bài

toán thực tế vì sự ngắn gọn của thuật toán. Tuy nhiên, vấn đề lại nằm ở chính sự đơn

giản của nó. Trong thực tế, ngoại trừ một vài trường hợp đơn giản trong đó hàm tích

lũy xác suất

có dạng đơn giản và có thể giải được, ngoài ra, việc giải

)

( XF x

thường dẫn đến nhiều bài toán giải tích và xấp xỉ nghiệm phức tạp khác khi

)

( u−=x XF

là một hàm tổng quát, phức tạp và hàm nghịch đảo

của nó không có

)

( 1 u−

)

( XF x

dạng đủ đơn giản để có thể tính toán hiệu quả.

Luận văn tốt nghiệp

2.2.3. Phương pháp lấy mẫu loại trừ

Cho trước một hàm mật độ xác suất

|π x z , giả sử chúng ta có thể tìm được một hằng

(

)

số C sao cho

| x z

≥

( π

)

(

) x z |

x

với mọi

. Như vậy, thuật toán lấy mẫu loại trừ được thực hiện như sau:

( )ix từ

• Bước 1: sinh mẫu

) |π x z và tính

(

( ) i

z

≤

( ) i

x

) z

)

( x ( Cπ

, trong đó

là phân phối đều trên

• Bước 2: Sinh số ngẫu nhiên

∼ u U ⎡

0,1U ⎡

0,1 ⎤ ⎦

⎣

⎤ ⎦

khoảng đóng

0,1⎡ ⎤ ⎦ ⎣

, chọn

( )ix ; ngược lại, loại trừ

( )ix .

r≤

• Bước 3: nếu

( )ix được sinh ra đều tuân

Chúng ta có thể chứng minh được, các mẫu ngẫu nhiên

theo mật độ xác suất

( p x z . |

)

Hình 1 Ví dụ về phương pháp lấy mẫu loại trừ

Luận văn tốt nghiệp

Hình 1 cho chúng ta thấy một ví dụ đơn giản về phương pháp lấy mẫu loại trừ.

Trong ví dụ này, hàm mật độ xác suất

( p x z có miền xác định

)

∼

. Rõ ràng, mẫu

( x p x z

)

( π

) x z U

(

x max

)max x

{

} 0

⎡⎣

⎤⎦ ; ta chọn hàm mật độ

∼

đã chọn. Trong

ngẫu nhiên

( )ix được sinh ra từ hàm mật độ

( π

) x z U

(

)max x

∼

trường hợp này, xác suất để chấp nhận một mẫu

là

( ) ix

max

( U x 0,

)

( ) i

x max

) z C

( p x

Trong trường hợp tổng quát, xác suất chấp nhận mẫu là

accept z

accept x z

(2.8)

(

)

(

) ( π

) x z dx

∫

1 C

Dễ thấy, khi C càng tăng, phương pháp này càng trở nên kém hiệu quả vì xác suất

chấp nhận một mẫu là rất nhỏ, thuật toán phải thực hiện nhiều lần thì mới có thể chọn

được một mẫu mong muốn. Ngoài ra, để tìm được giá trị hợp lý của

, thuật toán đòi

max

hỏi phải tính được

| |

) )

( ⎧ p x z ⎪ ⎨ ( x zπ ⎪ ⎩

⎫ ⎪ ⎬ . Bài toán này lại dẫn đến bài toán tìm nghiệm, trong ⎪ ⎭

đó đòi hỏi nhiều tính toán xấp xỉ phức tạp vì

( p x z thường là phi tuyến và có dạng

)

bất kỳ. Hơn nữa, nếu áp dụng phương pháp tìm C tăng dần, ta cũng không thể đảm

bảo được tính hiệu quả của thuật toán. Một cách tổng quát, cũng như thuật toán tích lũy

xác suất nghịch đảo, thuật toán lấy mẫu loại trừ cũng gặp phải nhiều vấn đề về chi phí

tính toán mà không thể được áp dụng trong những ứng dụng thời gian thực, trong đó

đòi hỏi dữ liệu phải được xử lý cực nhanh, ngay khi dữ liệu về quan sát được thu nhận.

2.2.4. Phương pháp Metropolis-Hasting

Thuật toán Metropolis-Hasting, thuật toán dựa vào phương pháp Monte Carlo xích

Markov (Markov Chain Monte Carlo - MCMC), được đề xuất bởi Metropolis năm

1953 và được Hasting cải tiến vào năm 1970. Ý tưởng chính của thuật toán này dựa

Luận văn tốt nghiệp

x

, sao cho mật

trên việc mô phỏng một xích Markov trong không gian trạng thái của

độ (phân phối) xác suất tĩnh (Stationary Distribution) của xích là

( p x z

)

Trong hầu hết các bài toán dựa vào mô phỏng (Simulation), vấn đề cần quan tâm là

ước lượng biểu thức

(

) x ⎤

} x… độc n

1, x

XfE

g⎡ ⎣

⎦ . Nếu đã có một tập mẫu ngẫu nhiên {

lập, đồng nhất từ biến ngẫu nhiên có mật độ xác suất

( ) i , ta có thể ước lượng biểu

thức này bằng

x

(2.9)

(

)

(

) x i

1 =

⎡ ⎣

1 ⎦ = ∑ ⎤ n

Như những phần trên đã đề cập, theo luật mạnh số lớn, ước lượng trong (2.9) là

hợp lý. Trong thực tế, từ

( ) i khó có thể trực tiếp sinh ra các mẫu độc lập và đồng

nhất. Nhưng bằng cách giảm bớt ràng buộc về tính độc lập giữa các mẫu dữ liệu, thuật

toán Metropolis-Hasting vẫn đảm bảo tính đúng đắn của ước lượng này.

Cho một xích Markov được đặc trưng bởi

x , trong đó, tại mỗi thời điểm

)

1 |

( tπ +x

được sinh ra phụ thuộc vào

trước đó và

là giá trị khởi tạo của xích (hàm

1t+x

( )π i còn được gọi là hàm mật độ đề xuất như sẽ được đề cập trong phần sau). Để sinh

ra các mẫu ngẫu nhiên, thuật toán Metropolis-Hasting dùng hàm

x nhằm sinh

)

1 |

( tπ +x

ra một mẫu mới và tương tự như trong thuật toán loại trừ, nó dùng một luật phân loại

nhằm quyết định xem có chọn mẫu mới này hay vẫn giữ nguyên giá trị cũ. Đây cũng

chính là điểm cải tiến của thuật toán Metropolis-Hasting so với thuật toán lấy mẫu loại

trừ.

∼

và tính

i |

• Bước 1: Sinh ngẫu nhiên (cid:105)

Thuật toán này có thể được tóm tắt như sau )

( ( ) iπx x

Luận văn tốt nghiệp

( ) (cid:105) i x |

)

( ) i

(2.10)

min 1,

(cid:105) x x ,

)

(

( ) i

(cid:105)( x z | x

(cid:105) x x |

)

( ) x π ) ( z π

p (

⎧ ⎪ ⎨ ⎪ ⎩

⎫ ⎪ ⎬ ⎪ ⎭

, trong đó

là phân phối đều trên

• Bước 2: Sinh số ngẫu nhiên

∼ u U ⎡

0,1U ⎡

0,1 ⎤ ⎦

⎣

⎤ ⎦

khoảng đóng

0,1⎡ ⎤ ⎦ ⎣

(

) 1 +

( ) i

(cid:105)

x

( ) i x .

) 1i + =

(cid:105) x x ,

x

• Bước 3: Nếu

x= . Ngược lại,

)

(

So với phương pháp lấy mẫu loại trừ, phương pháp Metropolis-Hasting không đòi

hỏi ta phải tính được cực đại của hàm số

x z . Hơn nữa, tại mỗi bước thực

| x z

(

)

( π

)

(

( ) i

x

(cid:105) x hoặc

x , điều

hiện của thuật toán, ta đều chọn được tối thiểu một mẫu

) 1i+ =

) 1i + =

này thực sự là một cải tiến đáng kể về hiệu suất so với thuật toán lấy mẫu loại trừ, vì ta

có thể biết được khi nào thì nên dừng thuật toán để đảm bảo về thời gian thực hiện.

Tuy nhiên, thuật toán Metropolis-Hasting gặp phải hai vấn đề khiến nó cũng không

thể được sử dụng trong các ứng dụng thời gian thực.

• Một là, thuật toán này đòi hỏi phải được thực hiện rất nhiều lần (có thể lên

đến hàng nghìn lần) trước khi xích Markov đủ khả năng mô phỏng được mật

độ xác suất tĩnh cần quan tâm, hay nói cách khác, mẫu ngẫu nhiên kết quả

thực sự được sinh ra bởi

) ( p x z . |

• Hai là, trên lý thuyết, khi số lần lặp của thuật toán tiến đến vô cực, thuật

toán sẽ hội tụ và các mẫu ngẫu nhiên sinh ra là độc lập nhưng trong thực tế,

số lần lặp của thuật toán là hữu hạn. Do đó, các mẫu ngẫu nhiên kết quả hiển

nhiên là phụ thuộc nhau. Điều này chúng ta không mong muốn trong phép

tính tích phân Monte Carlo, trong đó các mẫu ngẫu nhiên đòi hỏi phải độc

lập và đồng nhất với nhau.

Vì những lý do kể trên, mặc dù Metropolis-Hasting là thuật toán rất hiệu quả để

giải quyết bài toán sinh mẫu ngẫu nhiên từ phân phối bất kỳ. Tuy nhiên, do tính chất

Luận văn tốt nghiệp

tuần tự của nó, thuật toán phải thực hiện rất nhiều lần để có thể sinh ra được một mẫu

ngẫu nhiên mong muốn. Điểm yếu này cũng làm cho Metropolis-Hasting trở nên

không phù hợp với bài toán lọc trực tuyến của chúng ta.

2.2.5. Phương pháp lấy mẫu quan trọng

Trong phần trên, chúng ta đã xem xét 3 phương pháp sinh mẫu ngẫu nhiên từ một phân

phối xác suất bất kỳ. Phương pháp hàm tích lũy xác suất nghịch đảo tuy đơn giản về ý

tưởng và ý nghĩa toán học nhưng lại gặp phải vấn đề khi phải giải phương trình tính

nghiệm

. Phương pháp lấy mẫu loại trừ cũng không hiệu quả vì nó giả định

)

( u−=x XF

max

rằng chúng ta đã biết trước được đại lượng

. Trong khi đó, phương pháp

| x z x z |

) )

( ⎧ p ⎪ ⎨ ( π ⎪ ⎩

⎫ ⎪ ⎬ ⎪ ⎭

Metropolis-Hasting lại đòi hỏi quá nhiều vòng lặp của thuật toán trước khi nó thực sự

hội tụ và sinh ra mẫu ngẫu nhiên của phân phối xác suất tĩnh. Vì thế, cả 3 phương pháp

này đều không thích hợp cho bài toán lọc trực tuyến trong các ứng dụng thời gian thực

chúng ta cần quan tâm.

Trong phần này, chúng ta sẽ cùng xem xét phương pháp lấy mẫu quan trọng

(Importance Sampling - IS) – phương pháp luận của lọc Particle – và tìm hiểu xem tại

sao phương pháp này lại rất phù hợp với bài toán của chúng ta.

Cho trước hàm mật độ xác suất

|π x z , gọi là hàm mật độ đề xuất (Proposal

(

)

Density). Trong đó,

( )π i là một hàm mật độ có dạng đơn giản (theo nghĩa chúng ta có

thể dễ dàng sinh ra các mẫu ngẫu nhiên tương ứng với nó) và thỏa điều kiện

x

, nghĩa là tại mọi điểm

tại đó

thì

D p ,

| x z

x ∀ ∈

0 > ⇒

(

)

( π

)

(

)

) |π x z

(

. Nói cách khác, tại bất kỳ điểm nào trong miền xác định

cũng tồn tại và có

| x z

( π

)

của

, x

cũng có khả năng mô phỏng được

zi

)π zi ( |

( |p

)

Với những giả định trên, tích phân (2.3) được viết thành

Luận văn tốt nghiệp

(2.11)

x

z

x d

(

)

(

)

= ∫

| x z x z |

( p ( π

) ( π )

Suy ra

x

(2.12)

(

)

(

)

(

)

(

| x z

E ( π

)

(

)

⎡ ⎣

⎤ ⎦

⎡ ⎣

) ⎤ ⎦x

Trong đó

(2.13)

x

(

)

| x z | x z

( p ( π

) )

hay

ký hiệu cho kỳ vọng tương ứng với hàm mật độ xác suất

Và

zi

i ⎡ ⎤⎣ ⎦

pE ⎡ ⎣

⎦zi | ⎤

)|pE (

. Từ giả định về hàm

|π x z , hiển nhiên ta có thể dễ dàng thu được một tập

( |p zi

)

(

)

(

mẫu ngẫu nhiên độc lập, đồng nhất

tương ứng với

( ) 1 ,

x… ,

π x z . Như vậy,

)

(

}

{ x biểu thức (2.11) có thể được ước lượng bằng tích phân Monte Carlo như sau

( ) i

(cid:22)

x

(2.14)

(

)

(

1 N

( ) i

Đặt

( ) i *

z

x

( =∑ x f ) z , gọi là trọng số (Importance Weight)

)

(

( π

( ) i

(cid:22)

(2.15)

)

(

( ) i w *

) tương ứng với các mẫu ngẫu nhiên, (2.14) trở thành )

( =∑ x f

1 N

Như ta đã thấy ở mục 2.2.1, biểu thức (2.15) là hợp lệ, nghĩa là, theo luật mạnh số

lớn, nếu

hội tụ về

với xác suất 1 khi

π x z có phương sai hữu hạn thì

(

)

(

)

(

)

. Tuy nhiên, việc lượng giá biểu thức (2.15) không hoàn toàn đơn giản. Trong

N → +∞

những phần truớc, chúng ta chưa đề cập đến việc lượng giá

( p x z và hiểu ngầm rằng

)

x

cho trước. Thật không may, trong thực tế,

ta có thể dễ dàng tính được

) ( p x z với

để tính được

thường đòi hỏi nhiều phép tính xấp xỉ phức tạp.

p x z) ( |

Luận văn tốt nghiệp

( )* iw và tránh trực tiếp ước lượng biểu

IS giải quyết vấn đề này bằng cách biến đổi

thức

như sau

p x z) ( |

( ) i

x

z

x

z x |

)

(

( ) i *

(2.16)

( ) i

) p ( ) z

x

z

x

1 ( ) zi |

) )

)

( ( π

( π

Suy ra (2.11) trở thành

x

(2.17)

(

)

(

)

( π

) x z x d

= ∫

p p

( p x x z |

( (

) z x | ) ( z π

) )

( p x z nhưng ngược lại, ta có thể dễ dàng tính

( ) i

( )

likelihood

và xác suất prior

. Chỉ còn một vấn đề nữa là làm sao

( p z x |

. Thay

lượng giá được

x

x , ta có

| z x

Mặc dù ta khó có thể tính trực tiếp ) )

( ) =z

( p z

(

( p x )

) )i (

)

x

)

x

z

x

( π

)

(

)

(

)

∫

1 ( ) z

( ) p ) x z | )

x z |

d x

x

( π

)

(

)

∫

(2.18)

∫ p

( x

) d x x )

x z |

d x

x

( π

)

(

)

∫

( z x | ( π ( x ) p ( ) )

x z |

x

( π

)

∫

) ( p z x | ( x z | π ) ( p z x | ) ( p z x | ( x z | π ( ) ( x z x | p ( ) x z | π

Suy ra

)

⎡ ⎣

⎤ ⎦

(2.19)

(

)

f x x I f = x

x z |

)

) ( ( ⎡ w ⎣

( w ) ⎤ ⎦

Trong đó

E ( x z | π E ( π

Luận văn tốt nghiệp

x

(

)

(2.20)

x

(

)

) z

| z x ( π

p )

Hiển nhiên đến lúc này, biểu thức trong (2.20) có thể được tính dễ dàng vì các biểu

thức con trong nó đều đã được biết trước và có dạng đơn giản. Vậy, tích phân Monte

( ) i

x

)

Carlo trong (2.15) có thể được viết thành (

1 N

( ) i

(cid:22)

(2.21)

x

(

)

∑

) (cid:105)( ) w

(

( ) i

1 =

∑

( )

Trong đó

( )iw ký hiệu cho

và trọng số chuẩn hóa (cid:105)( )i

w được cho bởi

∑ 1 = 1 N )iw x (

( ) i

)

(cid:22)

(2.22)

(cid:105)( ) i w

(

)

( w

x

w N ∑

∑

)

x (

1 =

sẽ tiến về

với xác

Theo luật mạnh số lớn, hiển nhiên trong (2.21),

(

)

(

)

suất 1 khi

tiến đến vô cực.

Nếu ta đặt

(2.23)

x z |

(cid:109) ( p

)

( ) (

) x

1 =

= ∑

(cid:105)( ) i w δ x

Suy ra

(2.24)

x

x z |

x

| x z

x

≈

(

)

(

)(cid:109) ( p

)

(

)

(

)

∫

(2.24) cho thấy kết quả của thuật toán IS không chỉ là ước lượng của tích phân

mà còn là ước lượng của xác suất posterior

qua một biến đổi

x

)

(

) x z dx

( p x z

)

∫ của hệ. Đây cũng chính là tâm điểm của lọc Bayes trong đó mục tiêu chính là mật độ

xác suất posterior

qua các biến đổi của hệ.

( p x z

)

Luận văn tốt nghiệp

Qua những trình bày trên, ta thấy IS cung cấp cho ta một phương pháp để xấp xỉ

mà không đòi hỏi phải thực sự có khả năng tạo tập mẫu ngẫu

mật độ xác suất

p x z) ( |

. Trong khi đối với thuật toán lấy mẫu loại trừ và thuật toán

nhiên từ

( p x z

)

, thì đối với

Metropolis-Hasting, các mẫu được phân phối theo hàm mật độ

( p x z

)

thuật toán lấy mẫu quan trọng, các mẫu được phân phối theo hàm mật độ đề xuất. Sau

đó, các trọng số sẽ được cập nhật để phản ánh đúng ước lượng trong (2.21).

Từ những nhận xét trên, ta thấy IS là thuật toán duy nhất có thể được áp dụng trong

các bài toán lọc thời gian thực vì tính hiệu quả và chi phí thấp của nó. Nó không đòi

hỏi quá trình sinh mẫu – chọn lựa cũng như thời gian thực thi đủ lâu để thuật toán hội

tụ. Đây chính là lý do phương pháp lấy mẫu quan trọng trở thành phương pháp luận

chủ yếu của lọc Partilce. Tên của lọc Particle có lẽ cũng xuất phát từ phương pháp luận

này: dùng các phần tử mẫu (tương tự như các phần tử nhỏ, các hạt) để mô phỏng phân

phối xác suất của chúng qua những lần biến đổi của hệ.

2.3. Phương pháp lấy mẫu quan trọng tuần tự

Phương pháp lấy mẫu quan trọng IS là một phương pháp tích phân Monte Carlo tổng

quát. Tuy nhiên, tại mỗi thời điểm

, ta cần phải truy cập và sử dụng tất cả mọi thông

tin trong

trước khi có thể tính được

. Nói theo cách khác, mỗi khi dữ

( p x

)

1:tz

|t 0:

z t 1:

liệu về quan sát mới có hiệu lực, ta phải tính toán lại trọng số đối với toàn bộ không

gian trạng thái. Chi phí tính toán này sẽ tăng theo thời gian, khi mà dữ liệu tích lũy

ngày càng nhiều. Trong phần này, chúng ta sẽ xem xét thuật toán lấy mẫu quan trọng

tuần tự (Sequential Importance Sampling – SIS) và các tính chất của nó để có thể giải

quyết vấn đề nêu trên.

Như đã trình bày, thuật toán IS cho ta một phương pháp để ước lượng mật độ xác

) x được cho bởi tập mẫu-trọng số

suất posterior bằng (cid:109) ( Np

x . Trong đó, (cid:109) ( ) Np

Luận văn tốt nghiệp

( )ix

, với (cid:105)( )i

. Áp dụng vào

w là trọng số chuẩn hóa tương ứng với các mẫu

( ) (cid:105)( ) i i w ,

x

{

} 1

được cho bởi tập mẫu-trọng số

với

bài toán lọc của chúng ta,

x

(cid:109) ( p

)

t 0:

z t 1:

( ) (cid:105)( ) i i w , t 0: t

{

}

1 =

các trọng số chưa chuẩn hóa cho bởi

( ) i t 0:

)

(

(2.25)

( ) i w t

( ) i t 0:

p p x z t 1: = x

) | z t 1:

( x )

| ( π

Mục tiêu của thuật toán lấy mẫu quan trọng tuần tự SIS là tính toán xấp xỉ

của

một cách đệ quy mà không cần tác động đến những thông

x

)

(cid:109) ( p

)

t 0:

z t 1:

|t 0:

z t 1:

tin cũ về trạng thái

… N . Điều này có nghĩa là hàm mật độ đề xuất tại thời

x

( ) i i− 0: 1; t

( p x {

}

điểm t phải thỏa

(2.26)

x

|t x x

( π

)

( π

) ( π

)

t 0:

z t 1:

t 0: 1 −

z t 1: 1 −

t 0: 1 −

Nghĩa là

x

(2.27)

( π

)

( π

)

t 0:

z t 1:

x x | k

k 0:

k 1:

1 −

( π

z )

∏

1 =

dựa vào thủ tục

Dựa vào ràng buộc trên, ta có thể sinh một mẫu

x

(

)

( ) i ∼ tπx t 0: 0:

z t 1:

đơn giản sau:

∼

mới.

x

( ) i t

x x | t

)

z t 1:

t 0: 1 −

• Bước 2: Đặt

x

( ) x i t

( ) i =x 0: t

( ) i 0: 1, t −

( π }

, ta

Không có điều kiện như trong (2.27), để sinh ra một mẫu

( π x

)

( ) i tx mới từ 0:

|t 0:

• Bước 1: Sinh ra một {

z t 1:

cần phải tái tạo lại toàn bộ các mẫu

trước đó. Thay (2.26) vào (2.25), ta có

( ) i t−x 0: 1

Luận văn tốt nghiệp

x

z 1: t

( ) i 0: t

)

( ) i w t

( x

x

( ) i t

z 1: t

( ) i 0: 1 t −

)

x

) p ) ( π |

( ) i t

( ) i t 0: 1 −

z t 1: 1 −

( ) i t 0: 1 −

)

, (

z 1: 1 t − (

(

(2.28)

x

( ) i t

z t 1:

( ) i t 0: 1 −

) z t 1: 1 −

)

x )

( π

x

( ) i t

( ) i t 1 −

)

(

( ) i w t 1 −

x

) | ) x |

( ) i t

z t 1:

( ) i t 0: 1 −

x )

( π ( z x | t ( π ( z x | t ( π

Từ dòng 1 xuống dòng 2 của biểu thức, ta sử dụng giả định 2 về sự độc lập của các

và công

thức Bayes

(

)

(

)

(

)

z t 1:

x t 1:

z t 1: 1 −

x t 1: 1 −

. Từ dòng 2 xuống dòng 3 của biểu thức,

x

( ) i t

( ) i 0: t

( ) i 0: 1 t −

( ) x i 0: 1 t−

quan sát )

thu được )

= )

| z x t )

(

ta sử dụng giả định 1 về chuỗi trạng thái

| x x t

(

)

(

)

t 0: 1 −

1 −

Như trên đã nói, thuật toán SIS tìm kiếm một giải pháp đệ quy trong đó không cần

phải sử dụng những thông tin trước đó về trạng thái cũng như các quan sát. Để thực

hiện điều này, hàm mật độ đề xuất trong tử số của (2.28) cần phải được biến đổi một

chút. Thứ nhất, ta không muốn lưu trữ toàn bộ thông tin về những độ đo đã có trước

nên hàm mật độ đề xuất chỉ cần phụ thuộc duy nhất vào quan sát tại thời điểm

1: 1t−z

. Thứ hai, ta cũng không muốn ghi lại những thông tin về trạng thái trước

. Điều

( ) i t−x 0: 1

này có nghĩa là hàm mật độ đề xuất chỉ cần phụ thuộc duy nhất vào trạng thái tại thời

điểm

. Như vậy, (2.27) trở thành

1t −

x

(2.29)

( π

)

( π

)

t 0:

z t 1:

| x x k

1 −

( π

z )

∏

1 =

Thay (2.29) vào (2.28) ta có

x

( ) i t

( ) i t 1 −

)

(

(2.30)

( ) i w t

( ) i w t 1 −

x

z

) |

( ) i t

( ) i t 1 −

x )

z x | t ( π

Luận văn tốt nghiệp

Như có thể thấy trong (2.30), biểu thức tính trọng số lúc này không còn yêu cầu các

lưu trữ về trạng thái

cũng như quan sát

. Phương trình trong (2.30) như vậy

1: 1t−z

( ) i t−x 0: 1

có thể được sử dụng trong các cài đặt thực tế đòi hỏi các tính toán thời gian thực. Một

cách tóm tắt, thuật toán lấy mẫu quan trọng tuần tự có thể được trình bày như trong

Hình 2. Như ta có thể thấy, thuật toán SIS thực sự có ý tưởng và cấu trúc rất đơn giản,

điều này khiến cho nó trở thành thuật toán rất phổ biến trong các bài toán xấp xỉ bằng

lọc Bayes đệ quy.

Thuật toán 1 Sequential Importance Sampling

x

SIS

( ) i w t

( ) (cid:105) ( ) i i , w t t 0:

( ) i t 0:

}

{

}

1 =

⎤ z ⎥ t ⎦

⎡ ⎢ ⎣

⎡ ⎢ ⎣ N= 1:

⎤ ⎥ ⎦ 1 = i • FOR

{ x

∼

x x |

( ) ,i 1 t −

) tz .

o Sinh ra ( ) x o Tính ( )i

x

( ) i t

( tπ tw theo công thức ( ) i t 1 −

)

(

( ) i w t

( ) i w t 1 −

x

z

) |

( ) i t

( ) i t 1 −

x )

z x | t ( π

• END FOR i = N 1: • FOR

, chuẩn hóa trọng số của các mẫu

(cid:105)( ) i w t

( ) i w t N

)

( w t

1 =

∑

Hình 2 Thuật toán Sequential Importance Sampling

2.4. Giả lập thuật toán SIS

Trong phần này, chúng ta sẽ xem xét một ví dụ trực quan về thuật toán SIS bằng cách

mô phỏng sự hoạt động của nó trên một chuỗi dữ liệu mẫu sinh ngẫu nhiên của hệ cho

bởi các phương trình sau

Luận văn tốt nghiệp

∼

(2.31)

x

;

x

x x | t

(

)

(

)

1 −

kQ − 1

(

)

∼

;

z

(2.32)

(

)

| z x t

2 x t 20

⎛ ⎜ ⎝

⎞ , R ⎟ k ⎠

trong đó

x

(2.33)

( os 1.2

)

(

)

− 1

x t − 1 2

x 25 t − 1 2 x 1 + t − 1

là hàm Gauss tương ứng với biến

có kỳ vọng là

x

và

µ và phương sai δ.

2 N µδx ;

(

)

Hình 3 Dữ liệu giả lập thuật toán SIS

Hình 3 cho ta thấy kết quả từ việc mô phỏng sự biến đổi của hệ được mô tả bởi 2

phương trình (2.32) và (2.33). Đường màu xanh tương ứng với trạng thái thực của hệ

Luận văn tốt nghiệp

thống. Đường màu đỏ tương ứng với nhữrng quan sát thu được. Một cách trực quan, ta

có thể thấy các giá trị của trạng thái và độ đo thu được là những giá trị phi tuyến rất rõ

rệt.

Hình 4 Kết quả lọc bằng SIS

Hình 4 cho thấy kết quả sau khi thực hiện thuật toán SIS trên dữ liệu mô phỏng

bên trên. Đường màu xanh trong hình vẫn là dữ liệu về trạng thái thực của hệ. Đường

màu đỏ là giá trị trạng thái của hệ sau khi ước lượng bằng thuật toán SIS. Kết quả thu

được chưa hoàn toàn tốt, vẫn còn có nhiều điểm, giá trị ước lượng của trạng thái còn

khác nhiều so với giá trị thực của hệ. Nguyên nhân chủ yếu của hiện tượng này là do

thuật toán SIS gặp phải vấn đề thoái hóa của các giá trị trọng số trong quá trình hoạt

động của nó như sẽ được trình bày trong phần tiếp theo. Tuy nhiên, qua những đánh

Luận văn tốt nghiệp

giá sơ bộ, ta có thể thấy được thuật toán lọc SIS hoàn toàn phù hợp với những ứng

dụng thời gian thực của chúng ta và quan trọng hơn nữa, các kết quả cũng cho thấy nền

tảng lý thuyết của lọc Particle – phương pháp Monte Carlo – là đúng đắn và là cơ sở áp

dụng cho các ứng dụng theo dõi, xử lý tính hiệu số, thị giác máy tính mà chúng ta cần

quan tâm.

2.5. Các vấn đề về thuật toán SIS

2.5.1. Sự thoái hóa của thuật toán SIS

Thuật toán SIS chính là bộ khung của các ứng dụng lọc Bayesian theo hướng Particle.

Tuy nhiên, một vấn đề thường gặp đối với thuật toán SIS chính là hiện tượng thoái hóa

trong tập mẫu, tất cả những phần tử còn lại đều có trọng số rất nhỏ, không đáng kể.

mẫu (Degeneracy of SIS), trong đó sau một vài vòng lặp, ngoại trừ một mẫu duy nhất

Hình 5 Sự thoái hóa của thuật toán SIS

Luận văn tốt nghiệp

Qua thực nghiệm với dữ liệu giả lập, ta có thể thấy rất rõ hiện tượng thoái hóa này.

Hình 5 cho ta thấy biểu đồ trọng số của các mẫu theo thời gian. Thuật toán được thực

hiện với 200 mẫu, và với 200 vòng lặp. Trục đứng

trên hình biểu thị cho giá trị của

các trọng số. Trục nằm ngang bên trái hình biểu thị cho số lần lặp. Trục nằm ngang bên

phải hình biểu thị cho các trọng số của các mẫu. Trên hình, ta có thể thấy, trong những

vòng lặp đầu tiên, các mẫu vẫn còn tương đối “tốt”, theo nghĩa, hầu như các trọng số

vẫn mang giá trị đồng đều, tất cả các mẫu đều góp phần quyết định giá trị của hàm

. Tuy nhiên, chỉ trong vòng vài vòng lặp, rõ ràng có

phân phối đích posterior

p x z ) ( |t

t 1:

sự khác biệt giữa các trọng số này. Có rất nhiều điểm mẫu tại đó giá trị của trọng số rất

lớn, gần bằng 1, thường hoán đổi vị trí cho nhau, trong khi tất cả những điểm còn lại,

trọng số hầu như bằng 0. Và cho đến vòng lặp khoảng 100, chỉ có duy nhất một mẫu có

trọng số, tất cả các mẫu còn lại trọng số hầu như không có. Điều này cho thấy phương

sai của các trọng số tăng dần theo các bước thực hiện của thuật toán.

Trên lý thuyết, hiện tượng này có thể được chứng minh thông qua bổ đề sau

Bổ đề 2.1 Sự thoái hóa của các trọng số

Phương sai không điều kiện của trọng số thực sự tăng dần theo thời gian,

* w t

* tw − 1

(2.34)

x

var ( π

)

var ( π

)

t 0:

z t 1:

z , 0: 1 1: 1 −

−

⎡ ⎣

⎤ ⎦ ≤

⎡ ⎣

⎤ ⎦

trong đó, chỉ số dưới dòng ở biểu thức phương sai chỉ ra rằng những giá trị kỳ vọng là

được tính tương ứng với chuỗi độ đo và chuỗi trạng thái tương ứng.

Hơn nữa, ta lại có

* w t

(2.35)

z t 1:

x

(

)

z 1: t

var ( π

)

var ( π

)

t 0:

z 1: t

t 0:

z 1: t

⎡ ⎣

⎤ ⎦

⎡ ⎣

⎤ ⎦

⎡ ⎢ ⎣

⎤ ⎥ ⎦

1:tz

, phương sai có điều kiện của trọng số nghĩa là, với một chuỗi quan sát cho trước

có xu hướng tăng dần.

Chứng minh

Ta định nghĩa một hàm mật độ hỗ trợ như sau

Luận văn tốt nghiệp

(cid:22)

(2.36)

x z x t

| x x t

| z x t

(cid:105) ( π

)

( π

) ( π

)

z t 1:

− t 0: 1

z − t 1: 1

− t 0: 1

z − t 1: 1

− t 0: 1

(2.37)

z

| x x t

| z z t

( π

)

(

)

1 −

1: 1t −

là hàm mật độ xác suất trong đó trạng thái và quan sát hiện tại được sinh ra, dựa vào

điều kiện về trạng thái ngay trước và các độ đo trong quá khứ. Từ (2.36) đến (2.37), ta

sử dụng giả thiết rằng quan sát thật ra không được sinh ra từ hàm mật độ đề xuất

mà được sinh ra từ hàm mật độ kiểm soát quá trình quan sát của hệ. Hơn nữa, quan

sát chỉ phụ thuộc vào trạng thái của hệ tại thời điểm tương ứng nên ta có

| z x t

| z z t

(

)

(

)

z t 1: 1 −

t 1: 1 −

t 0: 1 −

Sử dụng phương trình trong (2.16) và (2.37) ta có

* w t

(2.38)

x z x t

x zt

(cid:105) ( * w π t

)

t 0: 1 −

z t 1: 1 −

E (cid:105)( π

)

x z x , t

0: 1 t −

z 1: 1 t −

⎡ ⎣

⎤ ⎦ = ∫ ∫

t 0:

) x

( |

t 0:

(2.39)

x z 1: t

= ∫ ∫

x | 0: t ) ( π x z x , t

x z d d t

( z p 1: t ( z p 1: t (cid:105) ( π

)

) ) z 1: 1 t −

0: 1 t −

1 −

∗ w 1 t −

∫ ∫

) ,

( x x | t t x x |

z

(2.40)

( p z x | t z z | t

)

0: t

1: 1 t −

1 −

( x z x | t

(cid:105) ( π

) p ( ) π ) x z d d t

z 1: 1 t −

0: 1 t −

(

)

(2.41)

z x | t

x x | t

x z d d t

(

)

∗ tw −= 1

t − 1

∫ ∫

(2.42)

x z x t

x z d d t

(

)

∗ w t 1 −

1 −

∗ − w 1t

∫ ∫

X Y |

Cho một biến ngẫu nhiên X , ta có

var

(

)

(

)

⎡ ⎣

⎤ ⎦

⎡ ⎣

⎤ ⎦

(2.43)

Dùng (2.42) ta có

∗ w t

∗ tw 1 −

(2.44)

x

x z x , t t

var ( π

)

var ( π

)

E (cid:105)( π

⎡ ⎣

⎤ ⎦

⎡ ⎣

⎤ ⎦

t 0: 1 −

z t 1: 1 −

t 0: 1 −

z t 1: 1 −

t 0: 1 −

z t 1: 1 −

⎡ ⎢ ⎣

⎤ ⎥ ⎦

Sử dụng tiếp (2.43), suy ra

Luận văn tốt nghiệp

−

w∗ t

∗ w t

∗ w 1 t −

x

, x z x t t

var ( π

)

var ( π

var (cid:105)( π

)

⎡ ⎣

⎤ ⎦

⎡ ⎣

⎤ ⎦

⎡ ⎣

⎤ ⎦

0: t

z 1: t

| z 0: 1 1: 1 −

−

0: 1 t −

z 1: 1 t −

⎡ ⎢ ⎣

⎤ ⎥ ⎦

≤

∗ w t

(2.45)

x

⎡ ⎣

⎤ ⎦

)

var ( π

0: t

z 1: t

t 0:

Như vậy, Bổ đề 2.1 đã được chứng minh. Hơn nữa

(2.46)

x

( π

)

z t 1:

t 0:

z t 1:

t 0:

* ⎡ E w ⎣ t

⎤ ⎦

∫

x x

| |

( p ( π

) )

t 0:

z 1: t z t 1:

var

w∗ t

∗ tw

Áp dụng (2.43), suy ra . Như vậy, đối với một chuỗi độ đo

z 1: t

⎡ ⎣

⎤ ⎦

⎡ ⎣

⎤ ⎦

cho trước, phương sai có điều kiện của các trọng số có xu hướng tăng theo thời gian,

Sự thoái hóa này là không tránh khỏi trong các bộ lọc dựa trên phương pháp Monte

Carlo. Do đó, vấn đề quan tâm hàng đầu của chúng ta là làm sao giảm bớt ảnh hưởng

của hiện tượng này.

gây ra sự thoái hóa của ước lượng (ĐPCM).

2.5.2. Vấn đề chọn hàm mật độ đề xuất

Như đã nói trong các phần trước, sự hợp lý của phương pháp xấp xỉ tích phân Monte

Carlo đặt nền tảng trên phát biểu của luật mạnh số lớn. Để thuật toán hội tụ, chúng ta

cần phải có một số lượng mẫu rất lớn

trong khi chỉ có thể xử lý một lượng mẫu

N → ∞

hữu hạn.

Chúng ta đều biết các mẫu trong thuật toán SIS không thực sự được sinh ra bởi mật

độ xác suất

mà là từ hàm mật độ đề xuất. Một cách trực quan, ta nhận thấy vị

p x z) ( |

trí của các mẫu được sinh ra có ảnh hưởng rất lớn đến kết quả ước lượng, hay nói cách

khác, mật độ đề xuất càng “tốt” chừng nào thì kết quả ước lượng càng “tốt” chừng ấy.

Bổ đề 2 Mật độ đề xuất tối ưu

là

( ) i tw

Hàm mật độ đề xuất làm cực tiểu hóa phương sai

z

⎡ ⎣

⎤ ⎦

( ) i x x | t t 1 −

var ⎛ π ⎜ ⎝

⎞ ⎟ ⎠

Luận văn tốt nghiệp

(2.47)

z

opt

x x | t

( ) i t 1 −

( ) i z1 , t −

)

(

Chứng minh

Ta có

x

( ) i t

( ) i t − 1

)

(2.48)

( ) i w t

( ) i w t − 1

p p =

x

( x

z

( π

opt

( ) i t

( ) i t − 1

x )

| z x t (

x

( ) i t

| z x t

( ) i t − 1

(2.49)

( ) i w t − 1

x

z

( ) i t

( ) i t − 1

) )

( (

(2.50)

( ) i w p t

z x | t

( ) i t −

(

( )i

tw độc lập với giá trị của mẫu được sinh ra của trạng thái hiện

Như vậy, trọng số

( ) i tw

tại, nghĩa là

z

⎡ ⎣

⎤ ⎦

( ) i x x | t t 1 −

var ⎛ π ⎜ ⎝

⎞ ⎟ ⎠

Có hai vấn đề đối với cách tiếp cận sử dụng hàm mật độ đề xuất này. Một là, nó đòi

hỏi phải có khả năng tạo mẫu ngẫu nhiên từ hàm mật độ

, hàm mật độ

x x | t

zt

( ) ,i 1 t −

)

(

( )i

này có thể là không chuẩn. Hai là, việc tính

tw trong (2.50) đòi hỏi phải thực hiện một

phép tính tích phân

(2.51)

x

z x | t

( ) i t

) ( ) i d− 1 t

(

) ( ) i − = ∫ 1 t

) mà có thể cũng trở nên rất phức tạp vì không thể giải bằng các biểu thức giải tích

thông thường.

Tuy nhiên, có cũng có hai trường hợp trong đó ta có thể sử dụng được

( ) optπ i .

Trường hợp đầu tiên là đối với bài toán có không gian trạng thái

rời rạc, hữu hạn.

Khi đó, tích phân trong (2.51) trở thành tổng hữu hạn cũng như việc phát sinh mẫu từ

Luận văn tốt nghiệp

là có thể thực hiện được. Trường hợp thứ hai, tương tự như mô hình hệ

zt

x x | t

( ) ,i t 1 −

)

( thống của lọc Kalman, là bài toán trong đó nhiễu của hệ thống có dạng Gauss và quan

sát có được từ hệ thống có dạng tuyến tính. Với trường hợp này, (2.51) cũng có thể tính

được vì cả hai biểu thức trong tích phân đều có dạng Gauss. Hơn nữa, vì quan sát có

dạng tuyến tính nên

cũng có dạng tuyến tính và có thể phát sinh mẫu từ

x x | t

zt

( ) ,i t 1 −

)

(

hàm này tương đối đơn giản.

Việc sử dụng hàm mật độ đề xuất nào đóng vai trò rất quan trọng, quyết định đến

hiệu suất của hệ thống. Vì vậy có rất nhiều nghiên cứu quan tâm đến vấn đề cải tiến

hàm mật độ đề xuất. Những cải tiến gần đây bao gồm các bộ lọc như lọc Particle hỗ

trợ (Auxiliary Particle Filter), lọc Unscented Particle (Unscented Particle Filter),…

Trong thực tế, vì nhiều vấn đề về cài đặt và hiệu suất, hàm mật độ đề xuất thường

(2.52)

z

x x | t

( ) i t 1 −

)

được chọn trong các ứng dụng là ( π

(

thuật toán. Giả sử trong một hệ

là nhiễu, để phát sinh ngẫu

u , với

x

(

Bằng cách này, chúng ta có thể dễ dàng phát sinh các mẫu trong quá trình thực hiện )1

−

nhiên một mẫu mới, ta chỉ đơn giản là phát sinh một mẫu khác từ phân phối của nhiễu

. Hơn nữa, bằng cách sử dụng hàm mật độ đề xuất như trên, biểu thức tính

( )i tw

( p u

trong (2.30) có thể được rút gọn thành

(2.53)

( ) i z xt | t

( ) i w t

( ) i w p−= 1 t

)

( Tuy nhiên, một vấn đề cần chú ý khi sử dụng hàm này là nó có thể làm cho bộ lọc

hoạt động kém hiệu quả. Hình 6 cho ta thấy một cách trực quan trường hợp này. Ở đây,

hàm likelihood

có dạng tập trung tại một điểm, trong khi hàm mật độ đề xuất

)

( p z x |t

Luận văn tốt nghiệp

lại có mật độ trải đều khắp trên miền xác định. Như vậy, sẽ có rất nhiều mẫu

( )i tx sẽ có

trọng số rất nhỏ, không đáng kể và kết quả là làm giảm kết quả ước lượng.

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

Như đã được chỉ ra trong [Okuma2004], một hàm mật độ đề xuất tốt thường là hàm

có khả năng sử dụng những thông tin có từ những độ đo về hệ thồng ở những thời điểm

gần nhất. Đây chính là nguyên nhân làm cho hàm

kém hiệu

z

x x | t

( ) i 1 t −

)

( π

(

quả trong một số trường hợp.

2.5.3. Tái chọn mẫu

Trong phần này trình bày về phương pháp thứ hai để giảm bớt tác dụng của hiện tượng

thoái hóa mẫu, đó là phương pháp tái chọn mẫu (Resampling). Trong những phần trên,

ta đã biết

( ) (

) x t

(cid:109) ( p

)

x z | t 1: t

1 =

= ∑

(cid:105)( ) i w δ t x

. Sau một vài lần thực hiện,

chính là một ước lượng rời rạc của hàm mật độ

( p x z |t

)1:

tất cả các mẫu đều có trọng số rất nhỏ, ngoại trừ một mẫu duy nhất có trọng số bằng 1.

Tuy nhiên, ta nhận thấy không phải tất cả các mẫu đều thực sự góp phần quyết định

vào giá trị của hàm mật độ posterior

mà chỉ có những mẫu tương đối gần

( p x z |t

)1:

Luận văn tốt nghiệp

với kỳ vọng

mới có đóng góp đáng kể trong việc quyết định giá trị của hàm.

(

)

Phương pháp tái chọn mẫu giải quyết vấn đề này bằng cách sắp xếp và điều chỉnh lại

mẫu đã có sẵn để xấp xỉ tốt hơn hàm mật độ này. Gọi (cid:105)( )i

tx là vector trạng thái trước khi tái chọn mẫu và

( )i tx là vector trạng thái sau

khi bước tái chọn mẫu được thực hiện. Vậy thủ tục tái chọn mẫu chính là ánh xạ

x

(cid:105)( ) (cid:105) ( ) i , x w t t

(2.54)

→

( ) i t

{

}

1 N

1 =

⎧ ⎨ ⎩

⎫ ⎬ ⎭ i

1 =

sao cho

)

x

(cid:105)( x t

(cid:105)( w t

( ) i t

⎛ ⎜ ⎝

⎞ ⎟ ⎠

Bằng cách sắp xếp lại các mẫu và đặt lại các trọng số mới, thuật toán tránh được

hiện tượng thoái hóa (tại mỗi thời điểm, trọng số của các mẫu đều như nhau và bằng

1 N ) và giúp cho thuật toán SIS tập trung vào những vị trí “hứa hẹn” nhất trong không

gian trạng thái tại đó có đối tượng cần quan tâm.

Cho rằng ta đã có một ánh xạ như trong (2.54), vấn đề đặt ra là làm sao biết được

mức độ thoái hóa của các trọng số, hay nói cách khác, khi nào ta cần phải mẫu. Trong

[Kong1994], Kong đã đề xuất một độ đo mới để tính sự thoái hóa, gọi là kích thước

mẫu hiệu dụng (Effective Sample Size), ký hiệu

. Độ đo này cho phép ta biết được

effN

số mẫu trong thuật toán có ảnh hường chủ yếu đến kết quả ước lượng và từ đó, ta biết

được khi nào cần phải lại các mẫu trong thuật toán của mình.

2.5.3.1. Kích thước mẫu hiệu dụng

Phần này trình bày về cách tính kích thước mẫu hiệu dụng và cách sử dụng nó trong

thuật toán SIS. Ta gọi

var π

z t 1:

(cid:22)

(2.55)

)

( , η π t

var

(cid:109) ( I ( I

) )

z t 1:

⎡ ⎣ ⎡ ⎣

⎤ ⎦ ⎤ ⎦

Luận văn tốt nghiệp

là ước lượng của tích phân

)

là hệ số hiệu dụng (Efficiency Ratio). Trong đó (cid:109) ( NI

x

dx , được bằng phương pháp lấy mẫu quan trọng với các mẫu được

(

)

x z | t

(

)1:

∫

là ước lượng Monte Carlo của tích

sinh ra từ hàm mật độ đề xuất. Tương tự,

(

)

phân trên, tuy nhiên, các mẫu được sinh ra từ hàm mật độ thực

( p x z |t

)1:

Nhận thấy

tăng tỉ lệ thuận với sự thoái hóa của các trọng số trong

(cid:109) ( I

)

var π

⎡ ⎣

z ⎤ t 1: ⎦

thuật toán SIS. Do đó,

pη π chính là độ đo để tính mức độ không hiệu quả của ước

(

)

lượng. Từ lập luận này, ta có thể dễ dàng tính được kích thước mẫu hiệu dụng bằng

công thức

pη π . ,

)

(

Tuy nhiên, chúng ta không thể tính được chính xác

pη π dựa vào (2.55) và chỉ

(

)

có thể ước lượng nó thông qua bổ đề sau.

Cho một hàm

biến thiên chậm tương ứng với

, ta có

( g x

Bổ đề 3 Xấp xỉ của hệ số hiệu dụng )t

z t 1:

var π

z t 1:

⎤ ⎦

⎡ ⎣

⎤ ⎦

(2.56)

≈

⎡ var π ⎣ var

* w t N

) z t 1:

(cid:109) ( I g ⎡ ⎣

⎤ ⎦

Với kết quả này, suy ra

var

z 1: t

(2.57)

≈

)

N ( , η π t

N ∗ w | t

var π

z 1: t

( I (cid:109) ( I

) )

f ⎡ ⎣ p (cid:109) ( I

var π

z 1: t

z ⎤ ⎦ 1: t ) z | 1: t

⎡ ⎣

⎤ + ⎦

⎡ ⎣ ⎡ ⎣

⎤ ⎦ ⎤ ⎦

⎡ ⎣

⎤ ⎦

Vậy, kích thước mẫu hiệu dụng được cho bởi

(cid:22)

(2.58)

eff

var

z 1: t

N ∗⎡ | wπ ⎣ t

⎤ ⎦ +

Mặc khác, ta có

và (cid:105)( ) N w t

(có được từ (2.15)

1 + =

( ) w∗≈ i t

∗ w t

var π

z t 1:

⎡ ⎣

⎤ ⎦

∗⎡ E w ⎣ t π

⎤ ⎦

và (2.21)). Suy ra

Luận văn tốt nghiệp

(2.59)

(cid:110) N eff

(cid:105)( ) i N w t

1 (cid:105)( ) i w t

∑

⎛ ⎜ ⎝

⎞ ⎟ ⎠

⎛ ⎜ ⎝

1 ∑ N = 1 i

1 =

Đến đây, ta đã có thể sử dụng (cid:110)

effN như một độ đo để tính mức độ thoái hóa của

các mẫu trong SIS. Rõ ràng, trong trường hợp tốt nhất, các mẫu được phân phối đều,

. Trong trường hợp xấu nhất, tất cả các trọng số đều gần

(cid:105)( ) i tw = N , suy ra(cid:110) effN

bằng

, ngoại trừ một mẫu duy nhất có trọng số gần bằng 1 , khi đó

. Điều này

(cid:110) 1 effN =

hoàn toàn phù hợp với những lập luận của chúng ta về kích thước mẫu hiệu dụng.

Một khi có (cid:110)

effN , ta sử dụng độ đo này bằng cách tại mỗi thời điểm hoạt động của

thuật toán, khi có các dữ liệu về quan sát mới hiệu lực, ta tính (cid:110)

effN và so sánh nó với

một ngưỡng

cho trước. Nếu

, thuật toán SIS đã bị thoái hóa ở một

threshN

(cid:110) N eff

thresh

mức tương đối và đó là dấu hiệu cho ta biết nên bắt đầu quá trình tái chọn mẫu và làm

mới lại các trọng số. Ngược lại, thuật toán SIS vẫn còn ở một mức lỗi chịu được và

không cần thiết phải tái chọn mẫu.

2.5.3.2. Thuật toán tái chọn mẫu

Trong phần trước, chúng ta đã xem xét về độ đo mức thoái hóa của một thuật toán. Độ

đo này cho ta biết các mẫu đã bị thoái hóa như thế nào thông qua số lượng các mẫu còn

. Qua đó,

đóng góp tương đối vào giá trị của hàm mật độ xác suất posterior

p x z ) ( |t

1: t

ta có thể biết được khi nào các mẫu cần phải được làm mới lại để cải thiện kết quả ước

lượng. Tiến trình làm mới này gọi là tái chọn mẫu (Resample).

Trong nhiều nghiên cứu ban đầu về các phương pháp Monte Carlo, tái chọn mẫu đã

đóng một vai trò quan trọng trong việc mô hình hóa sự biến đổi trạng thái của hệ theo

thời gian [Liu1998]. Tái chọn mẫu cũng là một trong những vấn đề được rất nhiều nhà

khoa học quan tâm trong thời gian gần đây. Có nhiều thuật toán cho phép tái chọn mẫu,

Luận văn tốt nghiệp

tuy nhiên thuật toán phổ biến nhất là tái chọn mẫu hệ thống (Systematic Resampling).

Thuật toán này được chọn vì nó có đơn giản, dễ cài đặt, có độ phức tạp cỡ

)O N và

(

quan trọng là nó giảm thiểu được phương sai trong xấp xỉ của tích phân Monte Carlo.

Thuật toán 2 Systematic Resampling

x

RESAMPLE

(cid:105)( ) (cid:105)( ) i x w , t t

( ) i t

( ) i w t

{

}

{

1 =

⎡ ⎢ ⎣

⎤ ⎥ ⎦

⎡ ⎢ ⎣ )0

• Khởi tạo CMF ( N= 1: • FOR o Tính ( ) c i

( c i

) (cid:105)( ) 1 w − + t

và đặt

1j = .

0,1 N

⎤⎦

c = . 0

(

) 1 i + − ⋅

u 0

(

o WHILE j

(cid:131)

• END FOR • Sinh 0 ∼ u U ⎡⎣ N= 1: • FOR

1 N )j c> iu j= + . 1 o END WHILE (cid:105)( )j o Gán ( ) i x t =x t o Gán ( ) 1 i N= tw

• END FOR

Hình 7 Thuật toán tái chọn mẫu hệ thống

;

= … là N ,

( ){ ic

}

Hình 7 trình bày chi tiết về thuật toán tái chọn mẫu. Trong đó

( ) i

(cid:105)( ) j w i ; t

… , N

( )

1 =

∑

)

( ( ) i CDF i CDF w = t

tập các giá trị của hàm tích lũy xác suất

Luận văn tốt nghiệp

( )0 c =

0,1⎡ ⎤ ⎦ ⎣

và với 0 . Thuật toán này diễn ra như sau: trong miền giá trị của hàm

( ) CDF i N

1 N ; sau đó, tại mỗi điểm

tích lũy xác suất , điểm cách đều nhau sẽ được chọn ngẫu nhiên với khoảng

j thỏa

(

)

này, ta chọn một điểm

)j tx .

min

tx bằng với mẫu cũ tại điểm (cid:4) ( ( )i

u≥ i

}

và gán mẫu mới cách giữa các điểm là { c

Hình 8 Ví dụ về thuật toán tái chọn mẫu với 3 mẫu

… như trong hình. Vị trí của các vạch chấm chấm

Hình 8cho ta thấy một ví dụ về thuật toán tái chọn mẫu hệ thống. Cho trước một

;

tập gồm 3 mẫu

x

( ) (cid:105)( ) i i t w i = , t

{

}

0,1⎡⎣ ⎤⎦

chính là vị trí của các điểm được chọn ngẫu nhiên trong miền giá trị của hàm

( ) CDF i

. Một cách trực quan, ta nhận thấy, các mẫu còn lại trong thuật toán tái chọn

mẫu chính là những mẫu mà có vạch chọn đi ngang qua nó. Trong trường hợp ví dụ

. Ngược lại, các mẫu không có vạch này, các mẫu có vạch chọn ngang qua là

(cid:105)( ) (cid:105)( ) 1 3 x x , t t

{

}

)

nào đi qua nó chính là những mẫu không được chọn. Trong ví dụ này, mẫu không có

. Như vậy, sau khi tái chọn mẫu, tập mẫu của chúng ta

{ vạch chọn nào đi qua nó là (cid:105)( tx

}2

1 t

x

{ sẽ là (cid:105)( ) (cid:105)( ) (cid:105)( ) x x ,

}

Luận văn tốt nghiệp

Sự đúng đắn của thuật toán tái chọn mẫu hệ thống được cho bởi định đề sau

Định đề 2.1 Sự giảm phương sai của thuật toán tái chọn mẫu hệ thống.

(cid:105)( ) i

Thuật toán tái chọn mẫu hệ thống tạo ra một tập hợp các lần chọn

( ) iN i ;

( ) (cid:105)( ) i i E N w |

N w

= .

{

} = … ,

⎡ ⎢ ⎣

⎤ ⎥ ⎦

( ) i

của các mẫu thỏa mãn và

var

( ) (cid:105)( ) i i w |

N = ∆

N − ∆

)

( 1

⎤ ⎥ ⎦

⎡ ⎢ ⎣

(cid:105)( ) i

với mọi i trong đó

( ) i ∆ =

−

(cid:105)( )i w N

⎢ ⎢ ⎢ ⎣

⎥ ⎥ ⎥ ⎦

N N w (2.60)

Như vậy thuật toán tái chọn mẫu đã được chứng minh là có khả năng làm giảm bớt

hiện tượng thoái hóa của các mẫu trong thuật toán SIS. Tuy nhiên, trong thực tế, chúng

• Một là, việc áp dụng thuật toán tái chọn mẫu làm giảm khả năng mở rộng

ta gặp phải hai vấn đề khi sử dụng thuật toán này.

( )i

cho tính toán song song của thuật toán vì nó đòi hỏi phải tính tổng tất cả các

tw trước khi chuẩn hóa.

• Hai là, sau khi tái chọn mẫu, không có gì để đảm bảo tính độc lập của các

trọng số

mẫu trong khi điều này là một trong những ràng buộc để thuật toán hội tụ.

Bên cạnh đó, còn một vấn đề khác không kém phần quan trọng, đó là sự kiệt quệ

mẫu (Sample Impoverishment). Hiện tượng này xảy ra khi có một mẫu có trọng số rất

lớn, được chọn rất nhiều lần qua các lần tái chọn mẫu. Nếu ta nghĩ về các mẫu như các

giả thuyết (giả thiết về vị trí, màu sắc, vận tốc, hình dáng,…), thuật toán SIS và các

thuật toán lọc Particle có thể được xem như là một tổng hợp của một tập các giả thuyết

sau khi chúng được kiểm chứng qua các độ đo và quan sát từ hệ. Như vậy, khi một

mẫu nào đó được chọn quá nhiều lần, số lượng các giả thuyết sẽ bị giảm và làm giảm

tính đa dạng giả thuyết của thuật toán. Nghĩa là, nó có khả năng dẫn thuật toán theo

một “giả thuyết lối mòn” nào đó.

Luận văn tốt nghiệp

Trong thực tế, mặc dù gặp phải các vấn đề kể trên nhưng thuật toán tái chọn mẫu

vẫn được sử dụng rất phổ biến và là một trong những thành phần chính trong hầu hết

các cài đặt của SIS vì nó là phương pháp hiệu quả nhất để làm giảm ảnh hưởng của

hiện tượng thoái hóa không tránh khỏi trong các thuật toán này.

2.6. Thuật toán lọc Particle

Các phần trên đã trình bày rất nhiều về cơ sở toán học của lọc Particle, phương pháp

Monte Carlo và những vấn đề lý thuyết liên quan đến thuật toán SIS và đôi khi chúng

ta đã nhắc đến lọc Particle. Vậy, thế nào là lọc Particle? Với sự ra đời của khái niệm

kích thước mẫu hiệu dụng và thuật toán tái chọn mẫu, mô hình thuật toán SIS kết hợp

với tái chọn mẫu đã được sử dụng rất nhiều và rất phổ biến qua các năm gần đây và

được biết với nhiều tên khác nhau lọc Bootstrap (Bootstrap Filters), thuật toán

Condensation, lọc Monte Carlo (Monte Carlo Filters) và lọc Particle (Particle Filters).

Những vấn đề lý thuyết ta đã trình bày ở trên về thuật toán SIS cũng chính là

những gì liên quan đến lọc Particle, dưới một tên khác. Thuật toán lọc Particle chi tiết

được trình bày như trong Hình 9. Như ta có thể thấy, mô hình thuật toán lọc Particle

chính là sự kết hợp giữa thuật toán SIS và thuật toán tái chọn mẫu.

Luận văn tốt nghiệp

Thuật toán 3 Particle Filter

x

z

( ) i t

( ) i w t

( ) ( ) i i w− , 1 1 t t −

{

}

1 =

⎡ ⎢ ⎣

⎤ ⎥ ⎦

⎡ ⎢ ⎣ N= 1:

⎤ } ⎥ ⎦ i • FOR

{ x

∼

x x |

( ) ,i t 1 −

( tπ

) tz

o Sinh ngẫu nhiên ( ) x o Tính ( )i

x

( ) i t

( ) i t − 1

)

tw theo công thức ( ( ) i t

(

( ) i w t

( ) i w t − 1

p p |

x

z

) |

( ) i t

( ) i t − 1

x )

• END FOR N= 1: • FOR

o Tính các trọng số chuẩn hóa (cid:105)( ) w t

( ) i w t N

( ) i w t

∑

1 =

• END FOR • Tính kích thước mẫu hiệu dụng theo công thức

(cid:110) N eff

(cid:105)( ) i N w t

⎛ ⎜ ⎝

⎞ ⎟ ⎠

1 (cid:105)( ) i ∑ ⎞ ⎛ w ⎟ ⎜ t ⎠ ⎝

1 ∑ N = i 1

1 =

| z x t ( π

• IF (cid:110)

eff

thresh

N N<

x

RESAMPLE

(cid:105)( ) (cid:105)( ) i x w , t t

( ) i t

( ) i w t

{

}

1 =

{

}

1 =

⎡ ⎢ ⎣

⎤ ⎥ ⎦

(cid:4) ( ) (cid:105) ( ) i x w , t t

( ) i t

( ) i w t

}

1 =

{

}

1 =

END IF

• ELSE { x

Hình 9 Thuật toán Particle Filter

Luận văn tốt nghiệp

2.7. Giả lập thuật toán lọc Particle

Trong phần này trình bày về một ví dụ trực quan của thuật toán lọc Particle. Tương tự

như trong phần 2.4, đây là những kết quả thu được từ việc áp dụng lọc Particle cho dữ

liệu ngẫu nhiên sinh bởi hệ cho bởi phương trình (2.31) và (2.32). Trong đó, phương

trình động của hệ theo thời gian cũng được cho bởi phương trình (2.33). Chương trình

giả lập hoạt động với 100 mẫu và chạy trong 200 vòng lặp.

Với cùng một hệ như trong phần 2.4, ta có thể thuật toán lọc Particle hoạt động tốt

hơn nhiều so với thuật toán SIS thuần túy. Hình 11 cho thấy kết quả ước lượng đã được

cải thiện nhiều. Nếu như trong thuật toán SIS vẫn còn rất nhiều thời điểm, ước lượng

hầu như sai khác hoàn toàn so với giá trị thực thì thuật toán Particle chỉ còn rất ít. Điều

này có thể lý giải được sự hiệu quả của thuật toán tái chọn mẫu và khử thoái hóa mẫu.

Tương tự trong Hình 5, Hình 12 cũng cho thấy giá trị của các trọng số của các mẫu

theo thời gian. Sự “hỗn loạn” trong hình cho thấy các mẫu ngẫu nhiên sau khi được tái

chọn đều góp phần quyết định giá trị của hàm mật độ xác suất đích. Hiện tượng thoái

hóa mẫu cũng đã được giảm bớt.

Bảng 1, Bảng 2, Bảng 3, Bảng 4 cho ta thấy những đánh giá định lượng về khả

năng của hai thuật toán. Sự so sánh được thực hiện bằng cách tính trung bình lỗi bình

phương (Mean Square Error - MSE) của từng thuật toán qua các trường hợp. Đánh giá

được thực hiện với 4 trường hợp của số lượng mẫu là 50, 100, 150 và 200 mẫu. Mỗi

thuật toán được thực hiện 5 lần với số bước lặp là 50, 100, 150, 200 và 250 bước. Các

kết quả cho thấy ước lượng bằng lọc Particle có mức lỗi nhỏ hơn nhiều so với SIS

trong tất cả các trường hợp.

Luận văn tốt nghiệp

Hình 10 Dữ liệu giả lập thuật toán lọc Particle

Hình 11 Kết quả lọc bằng Particle Filter

Luận văn tốt nghiệp

Hình 12 Hiện tượng thoái hóa mẫu đã được loại bỏ

Bảng 1 Kết quả so sánh Mean Square Error của SIS và thuật toán lọc Particle

(N = 50 mẫu)

Số lần thực hiện SIS Particle

105.2278

9.2173

95.6232

31.1151

100

105.33

22.317

150

119.248

37.1625

200

101.6698

13.4901

250

Luận văn tốt nghiệp

Bảng 2 Kết quả so sánh Mean Square Error của SIS và thuật toán lọc Particle

(N = 100 mẫu)

Số lần thực hiện SIS Particle

59.133

13.9137

101.3038

21.6555

100

98.0985

21.7638

150

100.5438

35.0454

200

146.4217

22.4156

250

Bảng 3 Kết quả so sánh Mean Square Error của SIS và thuật toán lọc Particle

(N = 150 mẫu)

Số lần thực hiện SIS Particle

59.6064

17.2199

100.1757

24.5694

100

88.9783

18.0681

150

164.8156

16.2254

200

134.503

22.6628

250

Bảng 4 Kết quả so sánh Mean Square Error của SIS và thuật toán lọc Particle

(N = 200 mẫu)

Số lần thực hiện SIS Particle

72.5385

13.7844

88.499

15.3092

100

125.1595

21.7936

150

129.8847

28.7288

200

137.5032

29.7926

250

Luận văn tốt nghiệp

2.8. Nhận xét

Chương này đã trình bày rất nhiều những vấn đề cơ sở về lọc Particle và những đánh

giá về nó. Trong đó, những khái niệm chính và quan trọng nhất của lọc Particle đã

được trình bày là

• Phương pháp lấy mẫu quan trọng tuần tự.

• Tầm quan trọng của việc lựa chọn hàm mật độ đề xuất.

• Thuật toán tái chọn mẫu.

Cả 3 khái niệm trên chính là những yếu tố chính góp phần làm nên một bộ lọc

Particle hoàn chỉnh. Trong đó, quan trọng nhất là việc lựa chọn hàm mật độ đề xuất và

thuật toán tái chọn mẫu. Hiện có rất nhiều phiên bản của lọc Particle như lọc Particle

có hỗ trợ (Auxiliary Sampling Importance Resampling - ASIR), Regularized Partilce

Filter (RPF),… được phát triển và tất cả đều tập trung vào hai vấn đề kể trên.

Thuật toán lọc Particle và những phương pháp mô phỏng Monte Carlo là một trong

những thuật toán đang được quan tâm rất nhiều trong thời gian gần đây. Nó được phổ

biến không chỉ bởi vì sự đơn giản trong ý tưởng và cài đặt mà còn bởi vì tính hiệu quả

của nó khi phải mô hình hóa những hệ thống tín hiệu phi tuyến, phi Gauss phức tạp,

biến đổi theo thời gian.

Ngoài ra, mô hình mở trong thuật toán lọc Particle cũng là yếu tố giúp nó trở nên

rất phổ biến. Có nhiều nghiên cứu tập trung vào cải thiện kết quả của lọc Particle tổng

quát. Trong khi đó, lại có nhiều nghiên cứu nhằm ứng dụng lọc Particle vào các ứng

dụng cụ thể trong xử lý tín hiệu số, theo dõi đối tượng, thị giác máy tính và mạng

neuron.

Lọc Particle cũng gặp phải một số trở ngại trong đó quan trọng nhất là chi phí tính

toán của nó. Nhằm đảm bảo mô phỏng được tốt hệ thống đích, ta cần sinh ra rất nhiều

mẫu tương ứng và đánh giá lại mức độ hợp lý của các mẫu này. Việc này thực sự là

Luận văn tốt nghiệp

một vấn đề không nhỏ cho các hệ thống áp dụng lọc Particle, nhất là trong lĩnh vực thị

giác máy tính và theo dõi đối tượng thông qua video. Tuy nhiên, vấn đề này có thể

được giải quyết bằng cách triển khai lọc Particle trên các hệ thống tính toán song song,

đa xử lý.

Như vậy, tùy vào bài toán cụ thể, chúng ta phải cân nhắc nên chọn lọc Particle nào

và ứng dụng nó ra sao cho phù hợp với ngữ cảnh của bài toán để đạt được hiệu suất cao

nhất. Trong chương sau, chúng ta sẽ cùng xem xét mở rộng của lọc Particle cũng như

ứng dụng của nó trong một bài toán thực tế đang được rất nhiều người quan tâm: theo

dõi đối tượng trên video trong giao thông đô thị.

Luận văn tốt nghiệp

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

Chương trước đã trình bày về lọc Partilce và các vấn đề liên quan đến nó. Qua đó,

chúng ta thấy được lý do vì sao lọc Particle trở thành một công cụ mạnh mẽ và phổ

biến trong các bài toán về ước lượng phi tuyến và phi Gauss. Chương này sẽ tập trung

vào một mở rộng của lọc Particle đó là cách dùng lọc Particle trong các ứng dụng ước

lượng nhiều đối tượng, trạng thái đồng thời nhằm tạo ra cơ sở lý thuyết cho bài toán

thực tế mà đang được quan tâm: bài toán theo dõi nhiều phương tiện giao thông di

chuyển trên đường phố dựa vào thông tin thị giác có được từ camera.

3.1. Mở rộng của lọc Particle

Những năm gần đây, lọc Particle đã trở thành một trong những công cụ không thể thiếu

trong các ứng dụng theo dõi và ước lượng, đặc biệt là trong bài toán theo dõi đối tượng

bằng thị giác máy tính. Nhiều bài báo cáo đã tập trung vào hai vấn đề đã nêu ra trong

chương trước, đó là

• Cách lựa chọn hàm mật độ đề xuất.

• Cải tiến thuật toán tái chọn mẫu.

Bên cạnh những vấn đề kể trên, bài toán được quan tâm trong thời gian gần đây

chính là theo dõi, ước lượng đa đối tượng bằng lọc Particle. Vấn đề này thường phát

sinh trong các ứng dụng theo dõi bằng thị giác máy tính và các hệ thống ước lượng,

dẫn đường trong quân sự và robot. Trong đó, tồn tại một môi trường có rất nhiều đối

tượng và nhiều nguồn quan sát (độ đo tại một điểm thường xuất phát từ nhiều đối

tượng. VD: hai đối tượng gần nhau, một cách tương đối, vùng không gian giữa chúng

sẽ có màu sắc và hình dạng chung của hai đối tượng). Chúng tương tác với nhau và tạo

thành một không gian hỗn loạn (clutter). Đây chính là nguồn gốc tạo ra rất nhiều lỗi

Luận văn tốt nghiệp

trong các ứng dụng của lọc Particle. Bên cạnh đó, các bài toán theo dõi bằng thị giác

cũng đòi hỏi hệ thống phải có khả năng phải nắm bắt được tương đối đầy đủ số lượng

các đối tượng trong một khung cảnh và sự tương tác giữa chúng để đảm bảo tính đúng

đắn cho các quyết định của hệ thống dựa trên những ước lượng trên. Ngoài ra, sẽ là

không hiệu quả nếu ta sử dụng từng bộ lọc cho từng đối tượng riêng lẻ mà không tận

dụng sự tương tác vốn có giữa các đối tượng thực tế. Vì vậy, bài toán lọc đa đối tượng

đồng thời trong một môi trường có nhiều nguồn quan sát trở thành một vấn đề quan

trọng trong các ứng dụng theo dõi đối tượng hiện nay.

Đã có rất nhiều thuật toán theo dõi đa đối tượng đã được đề xuất. Hầu hết tất cả

những thuật toán này đều thuộc về một trong hai nhóm sau

• Nhóm đầu tiên bao gồm những thuật toán được xây dựng trên cơ sở mô hình

hóa sự tương tác của nhiều bộ lọc riêng rẽ. Trong đó, mỗi bộ lọc ứng với

một đối tượng cần theo dõi, ước lượng. Chúng tương tác với nhau thông qua

một mô hình xác suất mô phỏng lại sự tương tác của các đối tượng trong

thực tế của hệ thống.

• Nhóm thứ hai bao gồm những thuật toán được xây dựng trên cơ sở mở rộng

không chỉ bao gồm không gian trạng thái. Trong đó, mỗi vector trạng thái

những đặc trưng của một đối tượng là sự tổng hợp đặc trưng của tất cả các

đối tượng. Hệ thống quản lý các đối tượng bằng cách thay đổi kích thước, số

chiều của vector đặc trưng; hoặc chỉ đơn giản là thay chỉ số đối tượng của

một thành phần nào đó trong vector đặc trưng.

Luận văn này chọn hướng mở rộng thứ hai cho bài toán theo dõi đa đối tượng và sử

dụng ý tưởng của hai thuật toán theo dõi đa đối tượng rất thành công hiện nay là Multi-

modal Particle Filter (MPF) và Boosted Particle Filter (BPF) để áp dụng vào bài toán

theo dõi giao thông.

Luận văn tốt nghiệp

Bên cạnh đó, một cải tiến khác của lọc Paricle sẽ được trình bày như là một nghiên

cứu riêng rẽ nhằm tăng cường khả năng của bộ lọc này đó chính là thuật toán kết hợp

Mean Shift và lọc Particle. Đây cũng là một trong những nỗ lực nhằm đưa ra hàm mật

độ đề xuất tốt hơn.

Phần tiếp theo sẽ trình bày sơ lược về MPF, một số vấn đề lý thuyết liên quan đến

nó và sau đó là thuật toán theo dõi có hỗ trợ của phát hiện đối tượng (Object Detection

Aided Particle Filter – ODAPF), một thuật toán được tổng quát hóa dựa trên ý tưởng

của thuật toán Boosted Particle Filter. Cuối cùng, thuật toán kết hợp giữa Mean Shift

và Particle sẽ được trình bày.

3.1.1. Multi-modal Particle Filter

3.1.1.1. Giới thiệu

Một trong những điểm yếu của lọc Particle và những phưong pháp Monte Carlo nói

chung là chúng rất yếu trong việc duy trì tính đa mô hình (Multi-modality) trong phân

phối xác suất đích. Trong một môi trường hỗn loạn, độ đo tại một điểm thường xuất

phát từ nhiều nguồn khác nhau, phân phối xác suất đích rõ ràng tồn tại sự đóng góp của

nhiều mô hình khác nhau. Trong đó, mô hình được hiểu theo nghĩa mô hình biến đổi

của từng đối tượng. Ví dụ: trong một cảnh video có 2 đối tượng cạnh nhau hoặc chồng

lên nhau, tại vị trí cục bộ, giữa hai đối tượng, ta sẽ thu được một ảnh trong đó là sự kết

hợp của cả hai đối tượng; lúc đó độ đo về màu sắc, đường biên,… tại vị trí này cũng là

sự kết hợp của cả 2 đối tượng.

Thuật toán MPF là một phương pháp dùng để ước lượng và giải quyết sự nhập

nhằng này. Nó hoạt động bằng cách giả định mô hình xác suất đích là sự kết hợp

(mixture) của nhiều phân phối xác suất thành phần. Trong đó, mỗi xác suất thành phần

chính là phân phối đích của từng đối tượng khác nhau và chúng tương tác với nhau

thông qua trọng số kết hợp (mixture weight).

Luận văn tốt nghiệp

3.1.1.2. Cơ sở toán học

Để mô hình hóa tính đa mô hình của phân phối đích, MPF xem phân phối đích là sự

kết hợp của nhiều phân phối thành phần

(

)

(

(3.1)

x z ) |

| x z t t 1:

t 1:

= ∑

pπ m t m , 1 =

,m tπ là trọng số kết hợp của

với M là số thành phần, hay nói các khác là số đối tượng;

phân phối thành phần thứ tại thời điểm . Tại bất kỳ thời điểm nào, các trọng số

m t ,

π 1 =

∑

kết hợp thỏa mãn điều kiện . Và không cần bất cứ ràng buộc nào khác

Cũng như mọi thuật toán dựa trên phương pháp lọc Bayes, thuật toán MPF cũng

• Dự đoán

trải qua hai bước

(3.2)

x

x z | t

x x | t

xt

(

)

(

)

(

z t 1: 1

t 1: 1 −

1 −

) d−

= ∫

• Cập nhật

t 1: 1 −

(3.3)

| x z t t 1:

(

)

) p

) xd

p (

( | z x t ) | z x t

( | x z t | x z t

p (

)

t 1: 1 −

∫

, ta đã biết hàm mật độ xác suất kết hợp ở thời Giả sử tại thời điểm

x

(

)

1 −

z 1: 1 t −

1t −

điểm trước đó. Như vậy, thay vào (3.2), ta được phương trình của hàm mật độ xác

suất dự đoán kết hợp mới như sau

x

x z | t

x x | t

td x

(

)

(

)

(

)

m t

t 1: 1 −

, 1 −

1 −

z t 1: 1 −

∑

∫

π m 1 = M

p m

(3.4)

x z | t

(

)

m t

t 1: 1 −

, 1 −

∑

π 1 =

Trong đó là mật độ xác suất dự đoán

x

p m

x z | t

x x | t

p m

(

)

(

)

(

z t 1: 1

t 1: 1 −

1 −

t 0: 1 −

) xd−

= ∫

. Như vậy, mật độ xác suất dự đoán kết hợp tại mỗi thời điểm có của thành phần thứ

thể có được bằng cách đơn giản là tính mật độ xác suất dự đoán cho từng thành phần

Luận văn tốt nghiệp

một cách độc lập và kết hợp chúng lại thông qua trọng số kết hợp tại thời điểm trước

đó.

p m

Tương tự, để có được mật độ xác suất đích, ta thay (3.4) vào (3.3)

x z | t

m t

, 1 −

1: 1 t −

∑

(

)

x z | t 1: t

) x d

p (

z x | t )

( z x | t

) p n

( x z | t

(

)

, 1 −

1: 1 t −

π 1 m = π n t 1 =

∫

p m

)

m t

, 1 −

1: 1 t −

∫

∑

1 =

(3.5)

x d

z x | t (

)

) z x | t

( p n

x z | t

x z | t (

x )

, 1 −

1: 1 t −

π n t 1 =

π M ∑

( ∫

∑ ⎡ ⎢ ⎢ ⎣

⎤ ⎥ ⎥ ⎦

p m

1: 1 t −

) x d

p (

( z x | t ) z x | t

) p m

( x z | t x z | t

(

)

1: 1 t −

∫

⎡ ⎢ ⎢ ⎣

⎤ ⎥ ⎥ ⎦

Ta nhận thấy biểu thức sau dấu × trong dòng thứ 3 chính là phân phối posterior

p m

1: 1 t −

của thành phần thứ m

p m

(3.6)

x z | t 1: t

(

)

) xd

p (

( z x | t ) z x | t

) p m

( x z | t x z | t

(

)

1: 1 t −

∫

, do đó, được sử dụng làm trọng số Biểu thức trước dấu × độc lập với trạng thái

kết hợp mới

)

m t

, 1 −

1: 1 t −

∫

, m t

)

p p m = π p d x

) z x | t

( p n

, 1 −

1: 1 t −

)

( ∫ ( p n

x z | t x z | t ( x d ) (3.7) p m =

1: 1 t − z z | t

)

, 1 −

1: 1 t −

, 1 m t − π n t 1 =

z x | t ( z z | t ( π M ∑ π n t 1 n = π M ∑

Như vậy, mật độ xác suất kết hợp lại trở thành kết hợp của các mật độ xác suất

thành phần. Mật độ xác suất kết hợp sẽ được duy trì, miễn là tại mỗi bước, mỗi mật độ

thành phần được cập nhật và các trọng số kết hợp đều được tính lại theo (3.7).

Luận văn tốt nghiệp

3.1.1.3. Xấp xỉ bằng Monte Carlo

Trong phần trước đã trình bày thuật toán MPF trong trường hợp lý tưởng. Trong đó chỉ

có một số trường hợp ta có thể giải được (tương ứng với các trường hợp trong lọc

Kalman và lọc HMM). Để bài toán có thể giải được trong trường hợp tổng quát, ta phải

đưa các phương trình trong phần 3.1.1.2 về dạng xấp xỉ Monte Carlo của chúng.

N M ,

∏

P t

X W C t t

{

}

là một tập biểu diễn cho phân phối kết hợp trong Gọi

M là số lượng các phân phối thành

phương trình (3.1). Trong đó, là số lượng mẫu,

1, , = … M là tập các trọng số kết hợp, phần,

x

;

, ;

( ) i t

{ m t mπ∏ =

}

{

} … N là tập

;

= … là tập chỉ số thành phần của các mẫu với

C t

( ){ c t

}

các mẫu, và

( )i tc =

( )i tx thuộc về thành phần thứ m .

}

( ) i { tc ∈ …M 1

- nghĩa là m nếu mẫu

(cid:105)( ) i w t

Vậy xấp xỉ Monte Carlo của phân phối xác suất đích có dạng

x

(

)

( ) (

(3.8)

x x | t

, m t

= ∑ ∑ x δ

π 1 =

i I ∈

{ … 1

( ) i } N c : t

{ i = ∈

} m

Với là tập chỉ số của các mẫu thuộc thành phần thứ .

(cid:105)( ) i =∑ w t

i I ∈

Hiển nhiên, ta có theo chứng minh ở các phần trước.

1t −

1tP− của phân phối kết hợp tại thời điểm

Cho trước một tập biểu diễn , mục tiêu

của chúng ta là tìm tập biểu diễn mới tại thời điểm của phân phối này. Trong phần

trước, ta đã nói các phân phối thành phần được biến đổi độc lập và tương tác với nhau

thông qua các trọng số kết hợp. Như vậy, đối với mỗi thành phần, tập các mẫu của nó

cũng biến đổi độc lập theo thời gian và cũng tương tác với các mẫu của thành phần

khác thông qua tập các trọng số kết hợp.

Luận văn tốt nghiệp

Xét thành phần thứ trong mô hình. Thành phần này được biểu diễn bởi tập các

mẫu-trọng số . Gọi là hàm phân phối đề xuất của hệ.

x

I∈

x x | t

zt

( ) (cid:105)( ) i i w i ; , t t

( ) ,i 1 t −

)

( π

{

}

được cho bởi các phương Phương trình biến đổi của các mẫu của thành phần thứ

trình sau

( ) i t

( ) i t 1 −

)

(

( ) (cid:105)( ) i i w w = t 1 − t

) |

( ) i t

( ) i t 1 −

(cid:105)( ) i w t

x p p | (3.9) x x z , x ) z x | t ( π

)

( ) i w t ( ∑ w t

j I ∈

(3.10)

trong phương Mức hợp lý của các thành phần (Component Likelihood)

|t z z

(

)

1: 1 t −

trình (3.7) được xấp xỉ bằng phương trình sau

x

z

p m

z z | t

p m

x x | t

z x | t

t 0: 1 −

1 −

t 0: 1 −

1 −

td − x x t 1

(

)

(

)

∫

x

( ) i t

) ( ) i t 1 −

( p )

| (

( (

≈

(cid:105)( ) i w t 1 −

∑

i I ∈

) ∫ ) ( ) i t |

(3.11)

x

z

( ) i t

( ) i t 1 −

x )

z x | t ( π

≈

( ) i w t

∑

i I ∈

(cid:105)( ) i w m t ,

m t

, 1 −

Thay vào (3.7), ta có xấp xỉ của trọng số kết hợp được cho bởi phương trình sau

m t ,

π M

(cid:105)( ) i w , n t

π n t

, 1 −

∑

1 =

(3.12)

(cid:105)( ) i w , m t

( ) i = ∑ w t

i I ∈

Với

Như vậy, (3.12) cho ta một công cụ để duy trì sự kết hợp giữa các phân phối thành

phần trong phân phối xác suất đích.

Luận văn tốt nghiệp

3.1.1.4. Tái chọn mẫu trong MPF

Trong suốt quá trình hoạt động của thuật toán, như đã chỉ ra trong những phần trước,

MPF cũng cần phải liên tục làm mới và tái chọn các mẫu. Nhưng thuật toán tái chọn

mẫu chuẩn không thể được sử dụng trong MPF vì nó sẽ bỏ qua thông tin về quan hệ

nhóm của các mẫu. Tuy nhiên với cách tiếp cận dùng mô hình phân phối xác suất kết

hợp, thuật toán chỉ cần tái chọn mẫu cho từng thành phần riêng biệt của phân phối

đích.

3.1.1.5. Tái sắp xếp mẫu

Một vấn đề quan trọng đối với thuật toán MPF đó chính là vấn đề tái sắp xếp mẫu.

Trong phần trước đã đề cập đến những vấn đề liên quan đến ước lượng sự biến đổi của

tập biểu diễn phân phối kết hợp nhưng câu hỏi đặt ra là làm sao biết được sự “tương

tác” giữa các mẫu và các thành phần, hiểu theo nghĩa, trong quá trình hoạt động của hệ

thống, mối liên hệ giữa một mẫu cho trước và một thành phần bất kỳ là gì?

Trong các hệ thống theo dõi đối tượng trong thị giác máy tính, số lượng đối tượng

thường dễ dàng biến đổi trong quá trình hoạt động của hệ thống do liên tục có người di

chuyển vào ra trong khung hình. Một cách trực quan, ta nhận thấy thuật toán phải có

khả năng điều chỉnh để phân phối các mẫu vào các thành phần nhằm tránh những xử lý

không cần thiết đối với những mẫu tương ứng với các thành phần quá yếu trong khi lại

thiếu mẫu để biểu diễn các thành phần mạnh.

Vì vậy, qua từng bước hoạt động của hệ thống, chúng ta cần phải tính toán lại biểu

diễn của phân phối kết hợp nhằm xử lý các biến đổi này. VD: kết hợp các thành phần

quá gần nhau hoặc tách một thành phần thành nhiều thành phần khác khi nó quá phân

tán.

′ , C M t

F X C M,t , t

) ′ =

(

)

là ánh xạ tái gom nhóm Trong hệ thống dùng MPF, gọi (

không gian (Spatial Reclustering Procedure). Ánh xạ này sẽ chịu trách nhiệm việc sắp

xếp và phân phối các mẫu qua quá trình biến đổi của hệ thống và tính toán biểu diễn

Luận văn tốt nghiệp

kết hợp mới cho phân phối đích. Ánh xạ này có thể là kết hợp của bất kỳ những toán tử

nối, phân chia và gom nhóm,v.v… tùy vào yêu cầu của bài toán và hệ thống.

( )F i kể trên và biểu diễn ảnh qua ánh xạ này là

′

N M ,

′ ,

∏

Giả sử đã có ánh xạ

P t

′ t

{

} ′ X W C t t

(cid:105)( ) i w t

. Vậy, trọng số kết hợp mới được cho bởi

, m t

′ = ∑

π ( ) ,i c t t

i I ∈ ′ m

(3.13)

( )F i có thể là bất kỳ hàm nào, tùy vào yêu cầu của bài

Hàm ánh xạ tái sắp xếp

( )F i , ta sẽ

toán. Đây chính là điểm mở của thuật toán MPF. Bằng cách thay đổi ánh xạ

có được hệ thống như mong muốn.

MPF là thuật toán theo dõi đa đối tượng có mô hình tương đối đơn giản. Nó có thể

được sử dụng trong nhiều ứng dụng thực tế, đặc biệt là bài toán theo dõi bằng thị giác

máy tính. Tuy nhiên, điểm yếu của MPF nằm ở chỗ sự tương tác giữa các đối tượng

bên trong mô hình chưa đủ chặt chẽ. Các đối tượng, các nguồn tín hiệu trong mô hình

chỉ tương tác với nhau thông qua trọng số kết hợp nên cũng làm giảm đi phần nào sự

mềm dẻo của hệ thống.

3.1.2. Thuật toán ODAPF

3.1.2.1. Giới thiệu

Phần 3.1.1 đã trình bày những vấn đề lý thuyết liên quan đến MPF. MPF không đưa ra

một thuật toán cụ thể mà bản thân nó là một khung thuật toán mở, trong đó trọng tâm là

vấn đề duy trì biểu diễn của xác suất kết hợp đích.

Dựa trên ý tưởng của thuật toán Boosted Particle Filter [Okuma2004], trong đó tiến

trình tái lựa chọn và tái sắp xếp mẫu được hỗ trợ bởi thuật toán AdaBoost, chúng tôi

đưa ra một thuật toán theo dõi đa đối tượng tổng quát, hoạt động dưới sự hỗ trợ của

thuật toán phát hiện đối tượng (Object Detection Aided Particle Filter – ODAPF).

Cũng như thuật toán BPF, ODAPF cũng có hai ưu điểm so với MPF.

Luận văn tốt nghiệp

• Một là nó sử dụng thuật toán phát hiện đối tượng và dùng kết quả này trong

hàm mật độ đề xuất. Bằng cách này, ODAPF thực sự tăng cường hiệu suất

• Hai là kết quả phát hiện đối tượng cung cấp cho chúng ta một phương pháp

của thuật toán lọc Particle rất rõ rệt.

khác để duy trì biểu diễn kết hợp. Phương pháp này hiệu quả hơn phương

pháp tái sắp xếp có trong MPF.

Thuật toán ODAPF hoạt động dựa trên ý tưởng cải tiến hàm mật độ đề xuất. Trong

đó, nó kết hợp thông tin của bước phát hiện đối tượng vào hàm mật độ đề xuất để cải

thiện khả năng của thuật toán. Những thông tin này sẽ được sử dụng để tính toán số đối

tượng có trong một thời điểm nào có của thuật toán. Nó cũng được dùng để phát hiện

ra những đối tượng mới, đồng thời tìm ra những đối tượng đi ra khỏi tầm kiểm soát của

hệ thống (VD: trong theo dõi đối tượng bằng thị giác máy tính, khi đối tượng đi ra khỏi

khung nhìn hoặc vào khung nhìn).

Hình 13 Mật độ đề xuất kết hợp

Luận văn tốt nghiệp

Gọi , với ý nghĩa

| x x t

1t−x

1 −

(

)t z là hàm mật độ dạng Gauss có tâm tại

detect

( ) i chứa đựng những thông tin của bước phát hiện đối tượng. Theo

detectπ

(3.14)

z

απ

| x x t

( 1 + −

ODAPF

1 −

−

( ) α π

)

(

detect

[Okuma2004], hàm mật độ đề xuất kết hợp có dạng (xem Hình 13) )

Trong (3.14), tham số α có thể được biến đổi mà không ảnh hưởng đến sự hội tụ

0α= , thuật toán trở thành một trường hợp của MPF. Khi α tăng

của lọc Particle. Khi

dần, thuật toán của chúng ta sẽ càng đặt nhiều “niềm tin” vào trong kết quả phát hiện

α.

đối tượng. Như vậy, tùy vào ngữ cảnh, chúng ta có thể tùy biến, thay đổi giá trị của của

3.1.2.2. Thuật toán

… M là tập các đối tượng tại thời điểm t . Trong đó, M là số đối

m t m , ;

{

}

x x 1, , Gọi

tượng có trong hệ thống, M có thể thay đổi theo thời gian. Gọi

x

∗ t

d t d , ;

{ ∗= x

} … , D

…

là tập biểu diễn kết quả phát hiện đối tượng của hệ tại thời điểm t tương ứng. Ta có

x

z

(

)

∗ t

∗ d t d , ;

{

} D DETECT

với D là số đối tượng phát hiện được.

, với ngưỡng cho trước , là tập Gọi

x

; min

x

∈

−

≤

∗ t

m t

, 1 −

thresh

∗ old t ,

∗ d t ,

thresh

{

}

các kết quả phát hiện “cũ”, được hiểu theo nghĩa, nếu một phát hiện trong thời điểm

1t − thì nó sẽ được xem là trùng với đối

quá gần với một trạng thái đã có tại thời điểm

tượng đó. Một cách gần đúng, ta giả định những phát hiện này xuất phát từ đối tượng

1t −

trước đó. đã có từ thời điểm

là tập những phát hiện “mới”, được hiểu Tương tự, ta định nghĩa

x

∗ new t ,

∗ x x t

∗ old t ,

theo nghĩa chúng có khoảng cách tương đối so với những trạng thái cũ và được xem là

những thông tin mới.

Luận văn tốt nghiệp

Tại mỗi thời điểm thực hiện, ODAPF liên tục kiểm tra qua lại giữa những thông tin

có được từ bước phát hiện đối tượng và những thông tin về trạng thái có được trước đó

để duy trì một tập những đối tượng tại thời điểm hiện tại.

Không giống như MPF, trong đó, số mẫu cho toàn bộ hệ thống là không đổi qua

thời gian, ODAPF cho phép số lượng mẫu thay đổi để phù hợp với số lượng đối tượng

có trong hệ thống.

PN là số lượng mẫu của một đối tượng. Như vậy, tập mẫu của hệ thống cho

…

Gọi

= … với M

1, , bởi .

x

X m , ; m t

m t ,

( ) i , ; m t

{

}

{

}

Với những định nghĩa trên, ta có chi tiết thuật toán ODAPF được trình bày như

INITIALIZE NEW MODE i là hàm khởi tạo trạng

( )

trong Hình 14. Trong đó, hàm

thái cho các phát hiện mới. Hàm này chịu trách nhiệm phát sinh các mẫu xung quanh vị

( ) REMOVE WEAK MODE i chịu trách nhiệm loại bỏ

trí phát hiện. Ngược lại, hàm

những đối tượng quá “yếu”, hiểu theo nghĩa phân phối thành phần của nó đã không còn

đóng góp gì nhiều trong phân phối đích. Ta có thể thực hiện cài đặt hai hàm này theo

một phương pháp bất kỳ, miễn là chúng vẫn giữ được ngữ nghĩa của chúng trong thuật

toán ODAPF.

Luận văn tốt nghiệp

Thuật toán 4 ODAPF Tracker

(

) z t

P ODAPF P − 1, t t

DETECT

• Phát hiện đối tượng

(

∗ =x t

) z . t

• Tìm

những

tượng

cũ

x

; min

x

∈

−

≤

∗ t

m t

, 1 −

∗ old t ,

∗ d t ,

thresh

{

đối }

x

• Tìm những đối tượng mới

∗ new t ,

∗ x x t

∗ old t ,

• Khởi tạo trạng thái cho các đối tượng mới

x

INITIALIZE NEW MODE ∗ x

new t

− = , 1

(

x

= x

• Gán

new t

M − 1 t

t . 1 −

1 −

, 1 −

{ x

}

= … 1,

• FOR

M − t 1

X W , , m t

m t ,

m t

W− , , 1

, 1 −

{

}

{ PF X

}

với hàm mật độ đề xuất ODAPFπ

• END FOR

• Tính toán các trọng số kết hợp theo (3.12).

• Xóa bỏ các trạng thái yếu

REMOVE WEAK MODE P .

(

)

Hình 14 Thuật toán ODAPF Tracker

3.1.3. Thuật toán MeanShift Particle

3.1.3.1. Thuật toán

Trong hai phần trên, chúng ta đã xem xét những mở rộng của lọc Particle cho nhiều đối

tượng. Trong phần này sẽ xem xét một trường hợp khác nhằm cải tiến hàm mật độ đề

xuất. Đó chính là kết hợp kết quả của thuật toán MeanShift vào lọc Particle.

Luận văn tốt nghiệp

Như đã được trình bày ở phần trên, Mean shift được biết là phương pháp theo vết

tối ưu hóa cục bộ. Do đó ta có thể ứng dụng nó trong giai đoạn lấy mẫu quan trọng của

thuật toán lọc Particle.

Chi tiết về các bước cơ bản của thủ tục tính toán Lọc Particle kết hợp với Mean

Shift như sau:

Khởi tạo (t=0)

Với i = 1,...,N

iw = N

~ (

)

( ) 0

ix ( ) 0

p x 0

và sinh ra Gán

Với t = 1, 2,...

)

Meanshift x −

ˆ x meanshift

ˆ( t

Bước lấy mẫu Importance -

)

xp (

)

1( −+

) α

Với i = 1,...,N

( ˆ xN

)

i t

meanshift

1 −

xzp |

(

)

Sinh ra

( DN

i t

)2 ,0, σz

- Likelihood , với Dz is khoảng cách Bhattacharyya

( zp

)

)( i t 1 −

~ )( i w t

)( i w t 1 −

) |

)( i t ,

x )

i )( | x t t )( i ( xq t

( xp )( i x t 1 −

- Tính các trọng số Importance (chưa được chuẩn hóa)

Với i = 1,...,N

i )( w t

~ i )( w t ~ j )( w t

= N ∑

1 =

- Chuẩn hóa các trọng số Importance

- Bước lấy mẫu lại

Ước lượng kích thước mẫu hiệu dụng

Luận văn tốt nghiệp

ˆ N

eff

(

2)( ) k

= N ∑

1 =

ˆ N < eff

)

Nếu th

( j ix k

= bởi việc lấy mẫu N lần và thay thế { }N

}N =

)

- Đạt được các mẫu mới {

}

{ ( j x i k

)( j k

/1=

sao cho

wi k

N - Khởi tạo

)( i xw t

)( i t

|ˆ x

∑

1 =

- Bước đưa ra kết quả

Kết thúc

Hình 15 Thuật toán Mean Shift kết hợp Particle Filter

3.1.3.2. Một số kết quả thực nghiệm dùng Mean Shift Particle

Để so sánh hiệu quả giữa thuật toán Particle thông thường (dựa trên mô hình màu)

và Particle kết hợp với Mean Shift. Dưới đây là một số hình ảnh kết quả theo vết quả

bóng bàn:

Luận văn tốt nghiệp

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)

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)

Luận văn tốt nghiệp

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)

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)

Nhận xét:

Luận văn tốt nghiệp

Qua các hình ảnh trên, rõ ràng ta thấy phương pháp Lọc Particle kết hợp với Mean

shift hiệu quả hơn hẳn phương pháp Lọc Particle thông thường (dựa trên mô hình

màu), đặc biệt là trong trường hợp đối tượng chuyển động nhanh.

3.2. Ứng dụng

Trên cơ sở những lý thuyết về lọc Particle cũng như mở rộng của lọc Particle cho theo

dõi đa đối tượng, phần này sẽ trình bày ứng dụng của chúng trong việc theo dõi đối

tượng trên video, cụ thể là trong bài toán theo dõi sự lưu thông của các phương tiện

giao thông 2 bánh trên đường phố.

Mô hình áp dụng của bài toán được mô tả như sau. Một camera sẽ được đặt ở một

vị trí cao, cách mặt đường từ 3-5m. Hướng nhìn của camera song song với hướng của

mặt đường. Dưới đây là một cảnh quay trích được từ camera đặt ở vị trí này

Như đã đề cập, một hệ thống theo dõi dựa vào video tổng quát bao gồm 3 phần

Luận văn tốt nghiệp

• Phát hiện đối tượng.

• Phân đoạn đối tượng.

• Theo vết đối tượng.

Trong đó, hai phần đầu có thể được kết hợp và xem như bước phát hiện đối tượng

duy nhất. Trong những phần sau, các vấn đề liên quan đến phát hiện đối tượng và theo

vết đối tượng để áp dụng vào ứng dụng thực tế.

3.2.1. Phát hiện đối tượng

Đây là một trong những giai đoạn chính trong một hệ thống theo dõi bằng video. Phát

hiện đối tượng giúp tìm ra các đối tượng cần quan tâm trong hệ thống và bỏ qua được

nhiều chi phí tính toán không cần thiết. Đặc biệt, đối với bài toán dùng ODAPF, kết

quả phát hiện đối tượng là cơ sở cho hàm mật độ đề xuất, là “kim chỉ nam” cho những

dự đoán về đối tượng của thuật toán này. Do đó, việc phát hiện đối tượng đóng vai trò

rất quan trọng.

Hiện có rất nhiều phương pháp được nghiên cứu để giải quyết bài toán phát hiện

đối tượng, trên video lẫn trên hình tĩnh (still image). Đáng kể nhất hiện nay có các tiếp

cận dựa trên AdaBoost, mạng neuron, tiếp cận dùng Bayesian-Localization và các

phương pháp tiếp cận ở cấp thấp hơn như khử nền kết hợp với những xử lý trên dữ liệu

video như khử bóng, tính vector chuyển động dùng Graphical Model.

Trong luận văn này, phương pháp tiếp cận dựa vào học nền và khử nền được áp

• Trong quá trình nghiên cứu các dữ liệu, điều kiện thực tế của môi trường

dụng vì những lý do sau

giao thông ở Tp. Hồ Chí Minh, chúng tôi đã thử sử dụng AdaBoost trong

giai đoạn phát hiện đối tượng. Tuy nhiên, do tính chất phức tạp của các đối

tượng xe hai bánh (nhìn từ phía sau, chúng có nhiều hình dạng, nhiều màu

sắc khác nhau, đồng thời, cách ngồi trên xe của người điều khiển cũng góp

phần làm tăng sự phức tạp của đối tượng) thuật toán phát hiện đối tượng

Luận văn tốt nghiệp

dùng AdaBoost tỏ ra không hiệu quả. AdaBoost chỉ hoạt động tốt khi có

những đặc trưng quan trọng xuất hiện trên chính đối tượng cần quan tâm

(VD: màu sắc của vùng giữa hai mắt, vùng miệng và mũi trên một gương

• Thuật toán học nền và khử nền là thuật toán duy nhất đảm bảo cho tính thời

mặt người,…).

gian thực của hệ thống. Sau bước phát hiện đối tượng, hệ thống phải đầu tư

chi phí cho việc xử lý theo dõi đối tượng bằng các bộ lọc. Như vậy, cần phải

có thuật toán phát hiện đối tượng nhanh, điều này không có được khi ta sử

dụng AdaBoost.

Trong luận văn này, vì thời gian có hạn và mục tiêu chính là vấn đề sử dụng lọc

Particle trong ước lượng nên phần này chỉ xem xét ra một phương pháp phát hiện đối

tượng đơn giản, dựa chủ yếu vào các kỹ thuật heuristic.

3.2.1.1. Học nền và khử nền

Bài toán học nền (Background Learning) là một trong những bài toán quan trọng

trong xử lý video ngày nay. Mục tiêu của học nền là tìm ra những đặc trưng quan trọng

nhất của ảnh nền trong một loạt những frame ảnh học để làm cơ sở cho bước khử nền.

• Parametric: mỗi điểm ảnh trong ảnh nền sẽ được mô hình hóa bằng một

Có hai cách tiếp cận chính để học nền

phân phối xác suất. Sau đó phân phối này sẽ được dùng làm cơ sở cho các

phép tính sự biến đổi, phân loại điểm ảnh này có phải là tĩnh hay không,…

Cách tiếp cận cổ điển nhất là dùng một hoặc nhiều hàm Gauss để mô hình

• Non-parametric: mỗi điểm ảnh cũng được mô hình hóa bằng một phân phối

hóa.

xác suất nhưng không có dạng chuẩn mà được ước lượng bằng một hàm

nhân (Kernel Function).

Luận văn tốt nghiệp

Luận văn này sử dụng một phương pháp khác để học nền. Với nhận xét: đối với

một khung cảnh cố định, giá trị xuất hiện nhiều nhất của một điểm trong khung cảnh

F t

= … f , t

{

}

f + t S

đó dao động xung quanh giá trị thực của nó. Như vậy, ta gọi là tập

các frame ảnh học. Vậy ảnh nền học được từ chuỗi dữ liệu này cho bởi

{ MEDIAN f

}

f + t N

(cid:108) BGf

… , , (3.15)

Hình 21 cho ta thấy kết quả học nền từ thuật toán cho bởi phương trình trong (3.15)

. Kết quả này cho thấy phương pháp học nền này tương đối hiệu quả. Gần như những

vùng lòng đường được tái tạo lại hoàn hảo, ngoại trừ những vùng có tán cây thì ảnh

học được hơi mờ. Điều này xảy ra là do có sự lắc lư của tán cây. Lúc đó, xác suất xuất

hiện của màu sắc tại những tán cây này phân bố đều, dẫn đến ảnh nền tại những vị trí

này không rõ ràng. Tuy nhiên, vi chúng ta chỉ quan tâm đến những đối tượng phương

tiện giao thông lưu chuyển trong lòng đường nên điều này có thể giải quyết bằng cách

dùng một mặt nạ (mask) cho biết những vùng lòng đường nào cần quan tâm như trong

Hình 20.

Hình 20 Hình nền và mặt nạ vùng chuyển động

Luận văn tốt nghiệp

Hình 21 Kết quả học nền

3.2.1.2. Phát hiện chuyển động

tf bất kỳ, ta có ảnh hiệu được tính như sau

(cid:108) f

Việc phát hiện chuyển động được thực hiện bằng cách trừ ảnh. Tại một frame ảnh

−

diff t ,

(3.16)

Như vậy, tại một điểm ảnh bất kỳ, để biết nó có thuộc về đối tượng chuyển động

yes f ,

and f

x y ,

≥

(

)

T thresh

mask

(

)

motion x y t

, diff t no otherwise

⎧⎪ ⎨ ⎪⎩

hay không, ta có một luật quyết định như sau

Luận văn tốt nghiệp

3.2.1.3. Phát hiện đối tượng

Những đối tượng trong bài toán của chúng ta là phương tiện xe gắn máy hai bánh. Với

nhận xét rằng nhìn từ phía sau, ảnh của xe gắn máy hai bánh có thể được xấp xỉ đường

biên bằng một ellipse, thuật toán phát hiện đối tượng được cho bởi Hình 23. Trong đó,

threshH

thresh

và là hai ngưỡng cho trước.

Trong Hình 22 là một số kết quả thu được từ thuật toán phát hiện đối tượng. Kết

quả thực nghiệm cho thấy thuật toán hoạt động tương đối hiệu quả đối với dữ liệu

video thu được trong thực tế

Hình 22 Kết quả phát hiện đối tượng

Luận văn tốt nghiệp

Thuật toán 5 Phát hiện đối tượng

( DETECT f

)

∗ =x t

• Tính ảnh chuyển động

motion

• Đánh nhãn thành phần liên thông trên

motion

• Với mỗi thành phần liên thông

o Tìm đường bao c của thành phần liên thông.

o Xấp xỉ đường bao bằng một ellipse e .

o Chọn e là một đối tượng nếu

AND L

≥

≤

e width

e height

thresh

e height e widht

⎛ ⎜ ⎜ ⎝

⎞ ⎟ ⎟ ⎠

• Nếu được chọn, gán

{ ∗=x ∗ x x , t t

} ( ) e

Hình 23 Thuật toán phát hiện đối tượng dựa trên luật

3.2.2. Theo vết đối tượng

Trong phần này trình bày về ứng dụng của lọc Particle và thuật toán ODAPF trong bài

toán theo vết đối tượng trong giao thông. Đối với bài toán lọc Particle, ngoài những

• Mô hình quan sát và mô hình đối tượng.

• Mô hình động của hệ.

vấn đề đã nêu trong các phần trước, một vấn đề mà chúng ta chưa bàn đến đó chính là

Mô hình quan sát và mô hình đối tượng chính là cơ sở cho những phép đo và tính

xác suất của chúng ta trong các phương trình xác suất của hệ. Trong đề tài, chúng tôi

sử dụng mô hình màu cho đối tượng và quan sát của nó. Mô hình màu là một trong

những mô hình được sử dụng nhiều nhất trong các ứng dụng theo vết đối tượng trên

video, bên cạnh các đặc trưng về đường biên, chuyển động,…

Luận văn tốt nghiệp

Mô hình động của đối tượng chính là những phương trình xác suất mô tả chuyển

động, biến đổi của các đối tượng trong hệ

3.2.2.1. Mô hình màu của đối tượng

Sử dụng ý tưởng của [Hue2002], chúng tôi sử dụng mô hình quan sát dựa vào

8 8 8 512

bins

N = × × =

histogram màu trong hệ màu RGB. Trong đó, một histogram là phân phối xác suất của

(8 bin cho mỗi hệ màu Red,Green và Blue).

(

) { ∈d … N 1

}

)

( ty k

Gọi là chỉ số của bin tương ứng với vector màu của pixel ở

vị trí

d tại

(cid:22)

thời . Như vậy, ước lượng mật độ nhân

x

;

… của phân phối màu ở thời điểm t được cho bởi

(

)

( ; k n

)

{

điểm }

x

d

−

( k n ;

)

(

)

b t

⎡ ⎣

⎤ ⎦

(3.17)

∑ η δ x d R ∈ t

là một phân trong đó δ là hàm Dirac-delta, η là hệ số chuẩn hóa để đảm bảo

x

( k n ;

)

(

)tR x là lân cận của

1 =

∑

, và , hay chính là vùng ảnh mà phối xác suất,

∗

(cid:22)

chứa đối tượng.

x

;

N… là mô hình màu tham khảo và

(

)

( ∗ k n ;

)

)tK x là mô

{

}

Gọi

hình màu ứng viên. Để tính mức hợp lý giữa hai mô hình màu, chúng tôi sử dụng

khoảng cách Bhattacharyya như sau

K K ,

(3.18)

x

(

)

( ∗ k n ;

)

( k n ;

)

ξ ∗ ⎡ ⎣

⎤ ⎦

1 =

⎡ = −∑ 1 ⎢ ⎣

⎤ ⎥ ⎦

Từ (3.18), ta có phương trình mật độ đo như sau

x

; K K

exp

∝

(

)

(

)

(3.19)

z x | t

{

2 λξ ∗ ⎡ − ⎣

} ⎤ ⎦

Trong đó λ là hệ số kiểm soát, giúp điều chỉnh hàm mật độ đo. Độ đo vừa trình

bày ở trên đã được chứng minh là phù hợp với nhiều ứng dụng. Tuy nhiên, ước lượng

Luận văn tốt nghiệp

của chúng ta sẽ chính xác hơn nếu kết hợp thêm thông tin về không gian của phân phối

màu.

)tR x (

Giả sử, lân cận của là tổng của vùng con khác nhau

(

)

R i

1 =

) = ∑x

, như vậy, phương trình trong (3.19) trở thành

x

exp

∝

(

)

(3.20)

z x | t

(

)

∑

λξ ∗ ⎡ ; K K − ⎣ i

⎤ ⎦

1 =

⎧ ⎨ ⎩

⎫ ⎬ ⎭

Hình 24 Mô hình màu đa vùng

3.2.2.2. Mô hình động của đối tượng

x y w h , ,

(

)

=x t

,w h

Ta định nghĩa vector trạng thái của một đối tượng trong hệ như sau

trong đó lần lượt là chiều rộng và chiều cao của ,x y là vị trí tâm của đối tượng,

đối tượng. Mô hình động của đối tượng được cho bởi hệ phương trình

Luận văn tốt nghiệp

x t

2 δ x

x t

1 −

y t

2 δ y

y t

1 −

) )

w t

) ) )

w t

1 −

)

0, ( 0,

h t

)

( ( ( (

h t

1 −

2 δ h

( 0, ( N (

2 δ w )

(3.21)

( ,N

)µδ là hàm phân phối Gauss có tâm tại µ và phương sai δ. Như

Trong đó

vậy, trạng thái của đối tượng tại thời điểm t cho bởi

x

(

)

(

)

(

)

x t

y t

( f w w t

1 −

1t−

( f h h

(

)

(3.22)

3.3. Kết quả

3.3.1. Kết quả định tính

Phần này trình bày một số kết quả thực hiện thuật toán theo dõi đa đối tượng

ODAPF trên dữ liệu thực tế. Thực nghiệm được tiến hành trên máy Pentium IV

1.6GHz, 512MB RAM. Các dữ liệu video thu được tại cầu vượt Văn Thánh, vào thời

điểm 12h trưa.

Hình 27 cho thấy các đối tượng đi vào và đi ra khung cảnh đều được theo dõi trọn

vẹn. Một đặc điểm đáng chú ý là bất chấp số lượng đối tượng vào và ra khỏi khung

nhìn, biểu diễn của mật độ xác suất kếp hợp không bị ảnh hưởng và thuật toán nhanh

chóng thích nghi với những thay đổi này. Nhờ có sự hỗ trợ của thuật toán phát hiện đối

tượng, ODAPF có thể tự động phân phối các mẫu đến từng đối tượng này và bắt đầu

thuật toán theo vết nó.

Hình 25, Hình 26 cho thấy hai trường hợp thuật toán ODAPF rất thành công. Tất

cả các đối tượng phương tiện giao thông khi đi vào vùng nhìn của camera đều được hệ

thống phát hiện và theo dõi thành công.

Một đặc điểm quan trọng của thuật toán ODAPF là nó có thể khắc phục những lỗi

do thuật toán phát hiện đối tượng tạo ra. Trong Hình 28, Hình 29, Hình 30 cột bên trái

Luận văn tốt nghiệp

là kết quả phát hiện đối tượng, cột bên phải là kết quả theo dõi tại khung hình tương

ứng. Ta dễ dàng nhận thấy các kết quả phát hiện đối tượng bị lỗi, các đối tương không

được phát hiện đầy đủ và bị chồng lên nhau (Hình 30). Nhờ có thuật toán theo dõi, hiện

tượng này được khắc phục dễ dàng nhờ thuật toán đã biết thông tin về trạng thái đối

tượng tại thời điểm trước đó và sử dụng nó để tìm kiếm đối tượng tại thời điểm sau.

Ở trên, ta giả định rằng các kết quả trong thuật toán phát hiện đối tượng là đáng tin

cậy tuyệt đối. Nhưng trong thực tế, một hệ thống phát hiện đối tượng như vậy còn là

bài toán mở. Trong chương trình thực nghiệm, chúng tôi chỉ sử dụng một thuật toán

phát hiện đối tượng dựa trên luật tương đối đơn giản, độ tin cậy không cao nên còn một

số giới hạn.

Hình 31 cho thấy một trường hợp thuật toán ODAPF bị “lừa” vì những kết quả

phát hiện đối tượng. Ở góc trên, bên trái của hình, hình chữ nhật xanh cho thấy vị trí

của phát hiện sai. Nhưng ODAPF vẫn tin vào kết quả này. Do đó dẫn đến sai lầm.

Tương tự, Hình 32, Hình 33 cho ta thấy trường hợp sai lầm khác của ODAPF. Khi

các đối tượng xe di chuyển ra xa, kết quả phát hiện đối tượng bằng trừ ảnh hoạt động

kém hiệu quả dần. Kết quả là nhiều đối tượng bị hiểu thành một và gây ra nhiễu như

trong hình.

Luận văn tốt nghiệp

Hình 25 Một kết quả thành công của ODAPF

Luận văn tốt nghiệp

Hình 26 Một kết quả thành công của ODAPF

Luận văn tốt nghiệp

Hình 27 Một kết quả theo dõi đa đối tượng

Hình 28 Thuật toán ODAPF bù lỗi cho thuật toán phát hiện đối tượng

Luận văn tốt nghiệp

Hình 29 Thuật toán ODAPF bù lỗi cho thuật toán phát hiện đối tượng

Hình 30 Thuật toán ODAPF bù lỗi cho thuật toán phát hiện đối tượng

Hình 31 Trường hợp lỗi của ODAPF

Luận văn tốt nghiệp

Hình 32 Trường hợp lỗi của ODAPF

Hình 33 Trường hợp lỗi của ODAPF

3.3.2. Kết quả định lượng

Để đánh giá thuật toán một cách định lượng, chúng tôi đã thử nghiệm kết quả trên

những đoạn video quay sẵn, mỗi đoạn dài 4s (giây). Kết quả được tính bằng tỉ số giữa

số đối tượng (xe gắn máy 2 bánh) phát hiện và theo dõi được trong quá trình thực hiện

thuật toán và số đối tượng thực xuất hiện trên những đoạn video này. Các đoạn video

Luận văn tốt nghiệp

được chia làm 2 nhóm, tương ứng với 2 góc quay khác nhau (góc so với mặt đường) ở

cùng một vị trí.

Bảng 5 Kết quả phát hiện và theo dõi đối tượng dùng thuật toán ODAPF đối

với những đoạn video ở góc quay 1

Clip trong góc quay 1 Số đối tượng thực Số đối tượng phát hiện Tỉ lệ

7 test01.avi 7 100%

5 test02.avi 5 100%

5 test03.avi 5 100%

4 test04.avi 4 100%

4 test05.avi 4 100%

3 test06.avi 3 100%

9 test07.avi 8 88.8%

9 test08.avi 8 88.8%

15 test09.avi 12 80%

Bảng 6 Kết quả phát hiện và theo dõi đối tượng dùng thuật toán ODAPF đối

với những đoạn video ở góc quay 2

Clip trong góc quay 2 Số đối tượng thực Số đối tượng phát hiện Tỉ lệ

11 test01.avi 10 90.9%

6 test02.avi 6 100%

10 test03.avi 9 90%

5 test04.avi 5 100%

5 test05.avi 5 100%

6 test06.avi 6 100%

6 test07.avi 6 100%

Luận văn tốt nghiệp

Các kết quả cho thấy thuật toán hoạt động tốt khi số lượng đối tượng có trong

khung cảnh tương đối vừa phải. Kết quả này ta có thể dự đoán được vì trong những

trường hợp nhiều đối tượng, chúng sẽ đè lên nhau và kết quả là gây nhiều nhầm lẫn

trong thuật toán.

3.4. Kết luận

Cách tiếp cận ODAPF qua thực nghiệm đã chứng tỏ là một cách tiếp cận hiệu quả đối

với bài toán theo dõi đa đối tượng trên video. Nó có khả năng thích nghi tốt với trường

hợp số lượng đối tượng trong khung cảnh biến đổi bất thường theo thời gian. Đồng

thời, thuật toán có khả năng thực hiện nhanh, có khả năng đáp ứng cho những bài toán

xử lý thời gian thực. Bên cạnh đó, thuật toán ODAPF, dựa trên MPF, là thuật toán có

khả năng mở rộng cao, có khả năng thích ứng với nhiều bài toán trong thực tế.

Tuy nhiên, một trong những vấn đề đối với ODAPF chính là nó đặt “niềm tin” vào

thuật toán phát hiện đối tượng. Sự thành công hay thất bại của thuật toán ODAPF được

quyết định rất nhiều bởi thuật toán này. Nó chịu trách nhiệm phát hiện những đối tượng

mới trong khung cảnh và những đối tượng cũ, đi khỏi khung cảnh. Vì vậy những tri

thức nó đem lại phải tuyệt đối chính xác. Do đó, làm ảnh hưởng đến quá trình hoạt

động và áp dụng của thuật toán ODAPF.

Ở đây, chúng tôi chỉ đưa ra một đánh giá định lượng mang tính chủ quan về hiệu

quả của thuật toán này vì đây là một hệ thống mở. Nó có khả năng thích ứng với nhiều

ứng dụng khác nhau bằng cách điều chỉnh những thông số và những thủ tục cụ thể

trong từng bước hoạt động của thuật toán. Nhưng thông qua các đánh giá trực quan,

chúng ta có thể thấy được tiềm năng ODAPF và các cải tiến khác của lọc Particle trong

các ứng dụng thực tế.

Luận văn tốt nghiệp

4. Kết luận và hướng phát triển

4.1. Kết luận

Trong luận văn này, chúng tôi đã trình bày những cơ sở lý thuyết của các phương

pháp lọc Bayes nói chung và lọc Partilce nói riêng. Qua các chứng minh trong chương

2, lọc Particle cho thấy tiềm năng của nó là một trong những phương pháp được quan

trọng và hiệu quả nhất hiện nay trong nhiều lĩnh vực khoa học như vật lý, điện tử, kinh

tế, quân sự, máy tính,… đặc biệt là các bài toán ước lượng và xấp xỉ tín hiệu.

Chúng tôi đã thử nghiệm các lý thuyết trình bày thông qua hai chương trình giả lập

• Thuật toán SIS: mô phỏng các lý thuyết về xấp xỉ tích phân Monte Carlo và

và hai chương trình thực nghiệm trên dữ liệu video:

• Thuật toán lọc Particle: mô phỏng các chứng minh nhằm giải quyết vấn đề

chứng minh sự đúng đắn của các cơ sở toán học cho thuật toán Particle.

• Áp dụng thuật toán ODAPF cho bài toán theo dõi đa đối tượng, cụ thể là bài

thoái hóa mẫu trong lọc Particle.

toán theo dõi trong giao thông: thử nghiệm khả năng ứng dụng của lọc

• Áp dụng MeanShift cho lọc Particle: thử nghiệm một nghiên cứu nhằm tăng

Particle trong bài toán theo vết đối tượng dựa vào video.

cường hiệu suất của lọc.

Các kết quả giả lập cho thấy các lý thuyết đã chứng minh là đáng tin cậy và phù

• Thuật toán ODAPF đã chứng tỏ thuật toán lọc Particle hoàn toàn có thể

hợp với nhiều bài toán thực tế:

được áp dụng vào các bài toán theo vết dùng thị giác máy tính, đặc biệt là

vấn đề theo dõi đa đối tượng thời gian thực mà nhiều cách tiếp cận dựa vào

phương pháp so khớp mẫu cổ điển thường không giải quyết được.

Luận văn tốt nghiệp

• Thuật toán Mean Shift kết hợp lọc Particle lại cho thấy một khía cạnh khác

của lọc Particle: các kết quả cho thấy Mean Shift Particle có khả năng thích

ứng tốt với bài toán theo dõi trong đó các đối tượng di chuyển nhanh. Nó

cũng chứng tỏ thuật toán Particle có thể được mềm dẻo sử dụng trong nhiều

mô hình khác nhau.

Nếu xét riêng bài toán theo dõi đối tượng, thuật toán Particle cho ta một lựa chọn

tốt hơn so với những thuật toán dạng so khớp mẫu Template Matching theo nghĩa có

thể áp dụng cho nhiều trường hợp, mô hình khác nhau bằng cách thay đổi các hàm mật

độ đo, phương pháp đo và các tham số về nhiễu. Bên cạnh đó, các kết quả thực nghiệm

cho thấy ODAPF có thể giải quyết bài toán theo dõi đa đối tượng mà các thuật toán so

khớp mẫu không giải quyết được khi gặp phải môi trường hỗn loạn. Bên cạnh đó, lọc

Particle còn có thể được áp dụng cho nhiều bài toán khác nhau nhau trong nhiều ứng

dụng khác nhau như xử lý tín hiệu số, máy học, mạng neuron, quân sự, robot và kinh tế

lượng. Hơn nữa, điểm mạnh của lọc Particle còn ở chỗ nó có khả năng mở rộng cao

cho các ứng dụng đòi hỏi xử lý song song.

4.2. Hướng phát triển

Trong quá trình thực hiện đề tài, do các điều kiện khách quan của môi trường, điều

kiện giao thông ở Việt Nam, do những hạn chế về trình độ và thời gian thực hiện đề tài

có hạn, hệ thống chúng tôi xây dựng chỉ gói gọn trong một ngữ cảnh hẹp của bài toán

theo dõi đối tượng dựa vào video. Hy vọng trong tương lai, những phát triển dưới đây

• Tập trung cải tiến thuật toán phát hiện đối tượng: hệ thống ODAPF cho thấy nó

sẽ giúp đề tài hoàn thiện hơn

hoạt động tốt khi kết quả phát hiện đối tượng tốt. Như vậy, ta có thể áp dụng

nhiều phương pháp khác hơn để cải tiến thuật toán này như dùng thuật toán

AdaBoost, sử dụng các mô hình xác suất khác nhau để mô tả đối tượng,…

Luận văn tốt nghiệp

• Kết hợp nhiều đặc trưng từ nhiều nguồn thu khác nhau: hệ thống sẽ họat động

tốt hơn nếu có càng nhiều tri thức về các độ đo. Có nhiều hướng phát triển để

• Sử dụng các hệ thống 3-D: kết hợp nhiều camera, ta sẽ có được những thông tin

kết hợp các độ đo này như kết hợp màu sắc, đường viền, kết hợp âm thanh,…

• Xử lý bài toán che lấp đối tượng: nhằm tạo kết quả theo dõi tốt hơn trong các

chính xác về tính chất vậy lý của đối tượng như vận tốc, độ sâu, khoảng cách,…

• Triển khai thêm các khả năng ước lượng về vận tốc, phát hiện xe chạy ngược

môi trường clutter.

• Triển khai khả năng ra quyết định dựa vào các ước lượng có được.

chiều, các vi phạm giao thông,…

Luận văn tốt nghiệp

DANH MỤC TÀI LIỆU THAM KHẢO

Algorithm - Conditional Density Propagation and Applications to Visual

Tracking. NIPS 1996: 361-367.

Andrew Blake, Michael [Blake1998] Isard: The CONDENSATION

filter sensor fusion, Asian Conference on Computer Vision (ACCV),

[Chen2004] Yunquiang Chen, Yong Rui, Speaker tracking using Particle

2004.

Based Object Tracking, Real-Time Vision and modeling Department,

[Comaniciu2003] Dorin Comaniciu, Visvanathan Ramesh, Peter Meer, Kernel-

Siemens Corporate Research, Princeton, NJ, USA, 2003.

Carlo samplingmethods for Bayesian filtering. Statistics and Computing,

[Doucet2000] A. Doucet, S. J. Godsill, and C. Andrieu. On sequentialMonte

10(3):197–208, 2000.

Monte Carlo in Practice, Springer-Verlag, January 2001 - ISBN: 0-387-

Arnaud Doucet, Nando de Freitas, Neil Gordon, Sequential [Doucet2001]

95146-6.

parametric Model for Background Subtraction, Computer Vision Lab,

[Elgammal2001] Ahmed Elgammal, David Harwood, Larry Davis, Non-

2001.

the Kalman Filter, Artech House, 2004.

[Gordon2004] Neil Gordon, Branko Ristic, Sanjeev Arulampalam, Beyond

[Guo2001] Zhong Guo, Object Detection and Tracking in Video,

Department of Computer Science, Kent State University, Nov 2001.

Luận văn tốt nghiệp

objects with particle filtering. IEEE Transactions on Aerospace and

[Hue2002] C. Hue, J.-P. Le Cadre, and P. P´erez. Tracking multiple

Electronic Systems, 38(3):791–812, 2002.

blob tracker. In Proc. Int. Conf. Computer Vision, pages II: 34–41, 2001.

[Isard2001] M. Isard and J. MacCormick. BraMBLe: A Bayesian multiple-

Using Deformable Templates. IEEE Trans. Pattern Analysis and

[Jain1996] A.K. Jain, Y. Zhong, and S. Lakshmanan, Object Matching

Machine Intelligence, vol. 18, no. 3, pp. 267–278, Mar. 1996.

Correlation: A Reduced-Cost Template Matching Technique. Proc. ICIP,

[Krattenthaler1994] W. Krattenthaler, K.J. Mayer, and M. Zeiller, Point

pp. 208–212, 1994.

Generation, February 26, 2004.

[Lang2004] Duncan Temple Lang, Approaches for Random Number

Dynamic Systems, 1998.

[Liu1998] Jun S. Liu, Rong Chen, Sequential Monte Carlo Methods for

Rudolph van der Merwe, Arnaud Doucet, Nando de Freitas, [Merwe2000]

Eric A. Wan: The Unscented Particle Filter. NIPS 2000: 584-590.

Processes, Department of Electrical Engineering, Arizona State

[Morrell2003] Darryl Morrell, EEE 581 - Lecture 2 : Filtering of Stochastic

University, USA, 2003.

Tracking with an Adaptive Color-based Particle Filter, Image and Vision

[Nummiaro2002] Katja Nummiaro, Esther Koller-Meier, Luc Van Gool, Object

Computing, to appear (2002).

Kenji Okuma, Ali Taleghani, Nado De Freitas, James J. Little, [Okuma2004]

Tracking, ECCV 2004.

David G. Lowe, A Boosted Particle Filter: Multitarget Detection and

Luận văn tốt nghiệp

probabilistic tracking. In Proc. Europ. Conf. Computer Vision, pages I:

[Perez2002] P. Perez, C. Hue, J. Vermaak, and M. Gangnet. Colorbased

661–675, 2002.

Visual Tracking with Particles, February 2004.

[Perez2004] Patrick Perez, Jaco Vermaak, Andrew Blake, Data Fusion for

Segmentation, Edge finding and Corner Finding, Department of Clinical

[Smith1997] Stephen M. Smith, Reviews of Optic Flow, Motion

Neurology, Oxford University, Oxford, UK, Image Segmentation and

Object Tracking 1997.

Object Localisation in Images, April 2001.

[Sullivan2001] J, Sullivan, A. Blake, M. Isard, J. Maccormick, Bayesian

Filter, Department of Computer Science, University of North Carolina at

[Welch2003] Greg Welch, Gary Bishop, An introduction to the Kalman

Chapel Hill, 2003.

Luận văn:ứng dụng lọc particle trong bài toán theo vết đối tượng

Chủ đề:

Đồ án môn khoa học dữ liệu

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

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

Nhận xét của giáo viên hướng dẫn

Nhận xét của giáo viên phản biện

TÓM TẮT LUẬN VĂN

MỞ ĐẦU

MỤC LỤC

Danh mục hình vẽ

Danh mục bảng biểu

1. Tổng quan về bài toán theo dõi đối tượng

1.1. Giới thiệu

1.2. Hệ thống theo dõi đối tượng

1.2.1. Phát hiện đối tượng

a) Phát hiện đối tượng dựa trên đặc trưng

b) Phát hiện đối tượng dựa trên mẫu

c) Phát hiện đối tượng chuyển động

1.2.2. Phân đoạn

1.2.3. Theo vết đối tượng

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)

1.3.2. Theo vết Meanshift

1.3.3. Tiếp cận Bayesian

1.3.3.1. Ước lượng Bayesian

1.3.3.2. Một số phương pháp dựa trên ước lượng Bayesian

1.3.3.3. Lọc Kalman

1.3.3.4. Lọc Kalman mở rộng(Extended Kalman)

1.4. Kết luận

2. Lọc Particle

2.1. Giới thiệu

2.2. Nền tảng toán học

|t x x

| x x t

z x ) |

z t 1:

x t 1:

x

X của hệ có phân phối xác suất ban đầu

} x(cid:96) ,

z

Y là các quan sát tương ứng

} z(cid:96) * ,

|t x x

x

x

(cid:22) … lần , z

1, z

x

z

x

( | x x t t 1 − ( | z x t

z 1: t

x

x

x

z 1: t

x

z 1: t

z 1: t

x

x hoặc

x

x

x