thanhtamphung
New Member
Download miễn phí Khóa luận Ứng dụng lọc particle trong bài toán theo vết đối tượng
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. Sokhớ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àmtích lũy xác suất nghịch đảo.22
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àmmậ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ựavà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
4.2. Hướng phát triển.94
DANH MỤC TÀI LIỆU THAMKHẢO.96
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
từ phân phối bất kỳ. Tuy nhiên, do tính chất26
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 ( )1XF u−=x . Phương pháp lấy mẫu loại trừ cũng không hiệu quả vì nó giả định
rằng chúng ta đã biết trước được đại lượng ( )( )
|
max
|
p
π
⎧ ⎫⎪ ⎪⎨ ⎬⎪ ⎪⎩ ⎭
x z
x z
. Trong khi đó, phương phá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
( ) (, | 0 |D p )π∀ ∈ > ⇒x x z x z 0, nghĩa là tại mọi điểm tại đó thì x ( )|p >x z ( )|π x z
cũng tồn tại và có ( )| 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ủa , x ( | )π zi cũng có khả năng mô phỏng được ( )|p zi .
Với những giả định trên, tích phân (2.3) được viết thành
27
Luận văn tốt nghiệp
( ) ( ) ( )( ) ( )
|
|
|
p
I f f dππ= ∫ x zx xx z z x (2.11)
Suy ra
( ) ( ) ( ) ( ) ( ) ( )| | *pI f E f E f wπ⎡ ⎤ ⎡ ⎤⎣ ⎦ ⎣= =x z x zx x ⎦x (2.12)
Trong đó
( ) ( )( )
|
*
|
p
w π=
x z
x
x z
(2.13)
Và hay ký hiệu cho kỳ vọng tương ứng với hàm mật độ xác suất
. Từ giả định về hàm
( )|pE ⎡ ⎤⎣ ⎦zi i |pE ⎡ ⎤⎣ ⎦zi
( |p zi ) ( )|π x z , hiển nhiên ta có thể dễ dàng thu được một tập
mẫu ngẫu nhiên độc lập, đồng nhất ( ) ( ){ }1 , , Nx x… tương ứng với ( | )π x z . Như vậy,
biểu thức (2.11) có thể được ước lượng bằng tích phân Monte Carlo như sau
( ) ( )( ) ( )( )11 *N iN iI f f w iN =∑ x x (2.14)
Đặt ( ) ( )( ) ( )( ) ( )( )* * | |i i i iw w p π= =x x z x z , gọi là trọng số (Importance Weight)
tương ứng với các mẫu ngẫu nhiên, (2.14) trở thành
( ) ( )( ) ( )11 *N iiN iI f fN w=∑ x (2.15)
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 ( | )π x z có phương sai hữu hạn thì ( )NI f hội tụ về ( )I f với xác suất 1 khi
. Tuy nhiên, việc lượng giá biểu thức (2.15) không hoàn toàn đơn giản. Trong
những phần truớc, chúng ta chưa đề cập đến việc lượng giá
N →+∞
( )|p x z và hiểu ngầm rằng
ta có thể dễ dàng tính được ( )|p x z với cho trước. Thật không may, trong thực tế,
để tính được thường đòi hỏi nhiều phép tính xấp xỉ phức tạp.
x
( |p x z )
28
Luận văn tốt nghiệp
IS giải quyết vấn đề này bằng cách biến đổi ( )* iw và tránh trực tiếp ước lượng biểu
thức như sau ( |p x z )
( )
( )( )
( )( )
( )( ) ( )( )
( ) ( )( )
| | 1*
| |
i i i
i
i
p p p
w
pπ π= = ×
x z z x x
zx z x zi
(2.16)
Suy ra (2.11) trở thành
( ) ( ) ( ) ( )( ) ( ) ( )
|
|
|
p p
I f f d
p
ππ= ∫ z x xx z x z x z x (2.17)
Mặc dù ta khó có thể tính trực tiếp ( )|p x z nhưng ngược lại, ta có thể dễ dàng tính
likelihood và xác suất prior ( )( )| ip z x ( )( )ip x . Chỉ còn một vấn đề nữa là làm sao
lượng giá được . Thay ( )p z ( ) ( ) ( )|p p p d=z z x x x , ta có
( ) ( ) ( )
( ) ( )
( ) ( )
( ) ( ) ( )( ) ( )
( ) ( )
( ) ( ) ( )( ) ( )
( ) ( )
( ) ( )
|1 |
|
|
|
|
|
|
|
|
|
|
|
p p
I f f d
p
p p
f d
p p d
p p
f d
p p
d
ππ
ππ
ππ
ππ
=
=
=
∫
∫
∫
∫
∫
z x x
x x
z x z
z x x
x x z
x z
z x x x
z x x
x x z
x z
z x x
x z x
x z
z x
x
x
(2.18)
Suy ra
( ) ( ) ( ) ( )
( ) ( )
|
|
E f w
I f
E w
π
π
⎡ ⎤⎣ ⎦
⎡ ⎤⎣ ⎦
= x z
x z
x x
x
(2.19)
Trong đó
29
Luận văn tốt nghiệp
( ) ( ) ( )( )
|p p
w π=
z x x
x
z
(2.20)
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
Carlo trong (2.15) có thể được viết thành
( )
( )( ) ( )
( )
( )( )i( )1
1
1
1
N
i i
N iii
N N
i i
i
f w
NI f f w
w
N
=
=
=
∑ ∑∑
x
x (2.21)
Trong đó ( )iw ký hiệu cho ( )( )iw x và trọng số chuẩn hóa i( )iw được cho bởi
i ( )
( )
( )
( )( )
( )( )
1 1
ii
i
N N
j j
j j
www
w w
= =
=
∑ ∑
x
x
(2.22)
Theo luật mạnh số lớn, hiển nhiên trong (2.21), ( )NI f sẽ tiến về ( )I f với xác
suất 1 khi tiến đến vô cực. N
Nếu ta đặt
m ( ) i( ) ( ) ( )1| iiNN ip w δ==∑ xx z x (2.23)
Suy ra
( ) ( )m ( ) ( ) ( )|N NI f f p d f p d= ≈∫ ∫x x z x x x z x| (2.24)
(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
( ) ( )|f p∫ x x z dx )
)
mà còn là ước lượng của xác suất posterior qua một biến đổi
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
( |p x z
30
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ật độ xác suất mà không đòi hỏi phải thực sự có khả năng tạo tập mẫu ngẫu
nhiên từ . Trong khi đối với thuật toán lấy mẫu loại trừ và thuật toán
Metropolis-Hasting, các mẫu được phân phối theo hàm mật độ , thì đối với
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).
( |p x z )
)
)
( |p x z
( |p x z
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 truy cập và sử dụng tất cả mọi thông
tin trong trước khi có thể tính được
t
1:tz ( )0: 1:|t tp x z . Nói theo cách khác, mỗi khi dữ
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