
ABSTRACT
Our thesis’ topic is object tracking using Particle Filter, which we will do
research how to track an object using Partcle Filter, building demo applications.
Object tracking in computer vision has been done research for many years, but
so far it is still considered an “open” problem. However, currently there is a method of
object tracking that its effectiveness has been proven in many studies around the world,
it is recognized as a "State of the art" - that is the Particle filte. So, we have carried out
to do resrearch interesting subject based on the guidance of teachers and the materials
of the university, the seminar on this subject.
In this thesis, we limit to introduce the theoretical basis of the Particle Filter,
and base on open source of the other research to improve of its experimental
application in the situation of tracking moving objects – selecting from the first frame
or a specific object (face, pedestrian ) and build the performace assessment to
demonstrate the effectiveness of the object tracking method.
SVTH: Chu Hoàng Nhật & Hà Thị Minh Phương
GVHD: ThS. Nguyễn Hữu Thương
CH Cáp Phạm Đình Thăng

LỜI MỞ ĐẦU
Đề tài luận văn của chúng tôi là theo vết đối tượng dùng Particle Filter, trong đó
chúng tôi sẽ nghiên cứu cách thức theo dõi một đối tượng bằng phương pháp sử dụng
Partcle Filter sau đó xây dựng một ứng dụng thực nghiệm.
Các phương pháp theo vết đối tượng trong công nghệ cảm quan máy tính
(computer vision) đã được nghiên cứu trong nhiều năm, nhưng cho tới nay nó vẫn
được xem là một vấn đề mở. Tuy nhiên, hiện nay đã có một phương pháp theo vết đối
tượng mà tính hiệu quả của nó đã được chứng minh trong nhiều nghiên cứu trên thế
giới, nó được công nhận là một “State of the art” – đó chính là Particle Filter. Vì vậy,
chúng tôi đã tiến hành nghiên cứu đề tài thú vị này dựa trên sự hướng dẫn của thầy cô
và các tài liệu của các trường đại học, các hội nghị chuyên đề về đề tài này.
Trong khóa luận này, chúng tôi giới hạn trong việc giới thiệu cơ sở lý thuyết của

SVTH: Chu Hoàng Nhật & Hà Thị Minh Phương
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………

…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
…………………………………………………………………………………
GVHD: ThS. Nguyễn Hữu Thương
CH Cáp Phạm Đình Thăng

MỤC LỤC
LỜI MỞ ĐẦU
SVTH: Chu Hoàng Nhật & Hà Thị Minh Phương
GVHD: ThS. Nguyễn Hữu Thương
CH Cáp Phạm Đình Thăng

DANH MỤC CÁC HÌNH, BẢNG, SƠ ĐỒ
HÌNH
SVTH: Chu Hoàng Nhật & Hà Thị Minh Phương
GVHD: ThS. Nguyễn Hữu Thương
CH Cáp Phạm Đình Thăng

BẢNG
SVTH: Chu Hoàng Nhật & Hà Thị Minh Phương
GVHD: ThS. Nguyễn Hữu Thương
CH Cáp Phạm Đình Thăng

Xác suất chuyển
trạng thái hay xác
suất chuyển tiếp
Là xác suất của trạng thái hiện tại so với trạng thái tại thời
điểm trước đó.
6.
Trạng thái đối
tượng
Là một vectơ đại diện cho vị trí đối tượng theo vết. Ngoài
các giá trị x, y – tọa độ của đối tượng, thường trạng thái đối
tượng có thêm giá trị scale (phụ thuộc vào sự thay đổi kích
thước của đối tượng).
SVTH: Chu Hoàng Nhật & Hà Thị Minh Phương
GVHD: ThS. Nguyễn Hữu Thương
CH Cáp Phạm Đình Thăng

7. Mẫu (particle)
Nhằm ước lượng trạng thái đối tượng trong bài toán theo
vết, ta xây dựng một tập mẫu trong đó mỗi mẫu chứa một
giá trị về trạng thái đối tượng, sau đó dùng thuật toán để
xác định là mẫu nào “giống” đối tượng => giá trị trạng thái
đối tượng là giá trị chứa trong mẫu.
SVTH: Chu Hoàng Nhật & Hà Thị Minh Phương
GVHD: ThS. Nguyễn Hữu Thương
CH Cáp Phạm Đình Thăng

Chương 1. GIỚI THIỆU.
Theo vết đối tượng thông qua từng khung hình của một chuỗi hình ảnh là
một chức năng quan trọng trong các ứng dụng thị giác máy tính (computer vision
applications) bao gồm các ứng dụng trong lĩnh vực an ninh như hệ thống camera

được xác định bởi các đường bao quanh với một số thuộc tính xác định. Xây
dựng các mô hình hình dạng (đường viền), mô hình đường viền động học và các
thông số hình ảnh khác trong quá trình theo dõi. Điển hình nghiên cứu Yezzi and
Soatto (2003), Jackson et al. (2004), và Rathi et al. (2005). Yezzi and Soatto
(2003) đề xuất một định nghĩa cho sự biến dạng về chuyển động và hình dạng có
thể áp dụng cho đối tượng biến dạng hay di chuyển.
Theo vết dựa trên Filtering: phương pháp Kalman Filter và Particle Filter
được nghiên cứu. Kalman Filter giải quyết với việc theo dõi hình dạng và vị trí
theo thời gian trong các hệ thống tuyến tính (non-linear) và có xét nhiễu Gauss.
Ngược lại, Particle Filter có thể ứng dụng trong các hệ thống phi tuyến và phi
Gasuss, ý tưởng cơ bản của Particle Filter là ước lượng xác suất trong định lý
SVTH: Chu Hoàng Nhật & Hà Thị Minh Phương

Bayesian bằng một tập hợp của mẫu có trọng số. Đối với Kalman Filter thì chỉ có
thể áp dụng khi hệ tuyến tính và có xét nhiễu Gauss, đ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ì các tín hiệu
quan sát thu được thường là các đại lượng phi tuyến và có phân phối phi Gauss.
Do đó, Anderson và Moore (1979) đưa ra thuật toán 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 EKF 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ụ. Julier và
Uhlmann (1996) đề xuất một thuật toán theo hướng xấp xỉ một hàm phân phối
xác suất dạng Gauss chứ không 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, 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.
Do vậy, phương pháp tổng quát nhất hiện nay là phương pháp Particle Filter.

$%
& '6')
-
'0
$%
1,0((
0
0
/'),
$%
789)':
& *
;**#
$%
<",
 
!*$%
!*$%
/-0'
$%
3*'=,
&'
$%
>??'
&@$%
A *#
$%2'
#$%

;06')

GBE'("0((*
'*',"$HG1%
1,#
$%
;0G"B'
$;GB%,*
G"B'$IGB%
3'#$%
GBE'/ 
06$/2B%
J)
-)
$%
;G"B' -)#
$%
SVTH: Chu Hoàng Nhật & Hà Thị Minh Phương

GBE')0'"
,*
2'#
$%
/,"( 
$/3%
!*
/-0'
$%
*G"B'
$GB%
H ,0#
$%

khuôn mặt khi xoay chuyển, tuy nhiên kết quả không tốt vì tỉ lệ nhận dạng khá
thấp. Support Vector Machines (SVMs) (Osuna et al, 1997, Shih và Liu, 2004)
sử dụng cấu trúc giảm thiểu rủi ro để giảm thiểu trên ràng buộc của các lỗi dự
kiến tổng quát. Những khó khăn chính của SVMs là tính toán nhiều và yêu cầu
bộ nhớ cao. Mô hình Hidden Markov (HMM) (Rabiner và Jung, 1993) cho rằng
các dạng face và non-face có thể được mô tả như là tham số ngẫu nhiên. Mục
đích của HMM là để ước tính các thông số thích hợp trong HMM nhằm tối đa
hóa khả năng quan sát dữ liệu được huấn luyện. Schneiderman và Kanade (1998)
trình bày một lớp phân loại Bayes thuần, trong đó dự tính xác suất xuất hiện và
vị trí của một mô hình khuôn mặt ở quy mô nhiều. Tuy nhiên, việc thực hiện
phân loại Bayes thuần là thấp. Để giải quyết vấn đề này, Schneiderman (2004) đề
xuất một mạng Bayesian hạn chế để phát hiện đối tượng. Phương pháp này tìm
kiếm các cấu trúc của một phân loại dựa trên mạng Bayes trong không gian rộng
lớn của cấu trúc mạng có thể xảy ra.
Bảng sau là các nghiên cứu có liên quan đến bài toán phát hiện đối tượng:
Phân loại Đặc điểm Nghiên cứu tiêu biểu
Phương thức dựa trên
các đặc trưng
Facial features with edges
and lines
Herpers et al.
(1996) Song et al.
(2002)
Gray scale
Yang and Huang
(1994) Graf et al.
(1995)
Skin color and elliptical edges Huang and Trivedi (2004)
McKenna et al. (1998)
Naseemand Deriche

type weak classifiers
Wu et al. (2004)
AdaBoost with Gabor features Yanget al. (2004)
Mạng nơ-ron
Multilayer neural networks
Rowleyet al. (1996;
1998) Curran et al.
(2005)
NN and Constrained
Generative
Model
Féraud et al.(2001)
Support
Vector
Machines
(SVM)
SVM with polynomial kernel Osuna et al.(1997)
SVM with Orthogonal Fourier
and Mellin Moments (OFMM)
Terrillon et al. (2000)
SVM with Discriminating
Feature Analysis
Shih and Liu (2004)
SVTH: Chu Hoàng Nhật & Hà Thị Minh Phương

Các thuật toán
khác
Hidden Markov Model
(HMM)
Rabiner and Jung (1993)

v_jumping_02_03 201 48.76
v_jumping_02_04 201 51.74
SVTH: Chu Hoàng Nhật & Hà Thị Minh Phương

bất kỳ
v_jumping_03_01 201 84.08
Khuô
n mặt
jam1 199 83.42
jim2 199 95.48
ssm1 199 100
Người
đi bộ
v_walk_dog_01_04 151 74.83
walk002 100 56
walk008 101 11.88
walk014 100 100
Bảng 3: Kết quả đánh giá sơ lược.
Trong các phần sau của bài luận văn được tổ chức như sau: chương hai
giới thiệu chung về bài toàn theo vết đối tượng: cách tiếp cận chung của bài, lý
thuyết về Particle Filter; chương ba giới thiệu về phương pháp phát hiện đối
tượng được áp dụng trong ứng dụng thực nghiệm; chương bốn giới thiệu về hai
thư viện OpenCV và GSL - hỗ trợ chính trong việc xây dựng ứng dụng thực
nghiệm; ứng dụng thực nghiệm được mô tả cụ thể trong chương năm, cuối cùng,
chương năm là phần đánh giá tính hiệu quả của ứng dụng thực nghiệm, công
thức để đánh giá, dữ liệu đánh giá đánh giá hiệu quả của thuật toán và chương
năm đưa ra kết quả đáng giá thực nghiệm dựa trên các công thức đã được chứng
minh trong các hội nghị khoa học.
SVTH: Chu Hoàng Nhật & Hà Thị Minh Phương


mặt.
• Nhóm các đối tượng có tập đặc tính chung trên nhưng kết hợp với một
thuộc tính cụ thể khác như xe ô tô chạy, người đi bộ.
• Nhóm các đối tượng có chung một thuộc tính cụ thể như các đối tượng di
chuyển, đối tượng bất kỳ được người dùng chọn trong khung hình đầu tiên.
Thuật toán theo vết đối tượng thực chất làm tìm một vùng ảnh di chuyển
từ khung hình này sang khung hình khác nên mỗi nhóm đối tượng sẽ có các đặc
điểm riêng nhưng tống quát ta có các bước chính như sau:
• Thứ nhất, ta cần xây dựng một “mô hình tham chiếu” (reference model)
để mô tả cho đối tượng cần theo vết.
• Sau đó trên mỗi khung hình đầu vào (input frame), dựa trên các hàm thực
thi so sánh (similarity measure) thuật toán tìm (localize) vùng nào mà gần
giống với “mô hình tham chiếu” (reference model) nhất.
Dựa trên cách tiếp cận chung thì mỗi phương pháp kĩ thuật được phát
triển sẽ có các biến thể và các cách thức áp dụng riêng.
2.2.1. Mô hình tham chiếu (Reference model).
Mô hình tham chiếu là mô hình mô tả các thông tin về “vẻ bề ngoài” của
đối tượng cần theo vết. Có nhiều cách xây dựng mô hình tham chiếu cho đối
tượng như các mẫu gray-level, mô hình đường viền, và cách thường dùng nhất
trong các ứng dụng theo vết đối tượng là dùng mô hình màu (color model), tuy
nhiên có một số vấn đề đặt ra:
• Hệ màu nào được dùng? RGB hay HSV, Lưu ý rằng khi chúng ta dùng
mô hình màu để làm mô hình tham chiếu có nghĩa là chúng ta đã chịu
thêm một giả sử là chúng ta chỉ theo vết được các đối tượng trên ảnh màu
chứ không phải là ảnh bất kì. Ngoài ra, cũng cần chọn kĩ hệ màu vì nó rất
nhạy cảm với độ sáng, khung cảnh. Hiện tại trong ứng dụng thực nghiệm
đang sử dụng với hệ màu Hue-Saturation-Value (HSV).
• Mô hình phân bố (distribution) như thế nào? Có nhiều cách để tạo mô
hình phân bố như Gaussian, hoặc Mixture Gaussian, hoặc chỉ đơn giản
SVTH: Chu Hoàng Nhật & Hà Thị Minh Phương


• Xác suất xảy ra B khi biết A xảy ra. Kí hiệu là P(B|A) và đọc là "xác suất
của B nếu có A". Đại lượng này gọi là khả năng (likelihood) xảy ra B khi
biết A đã xảy ra.
Khi biết ba đại lượng này, xác suất của A khi biết B cho bởi công thức
eq. 1
2.3.1.2. Định nghĩa theo khía cạnh ứng dụng.
Trước hết ta định nghĩa một số kí hiệu sau:
Đối với trạng thái đối tượng (mục tiêu cần xác định):
• : trạng thái của đối tượng ở thời điểm t. Các đại lượng vật lý đại diện cho
trạng thái của đối tượng thường là tọa độ x, y của trọng tâm khung chữ
nhật chứa đối tượng cần theo vết.
• : chuỗi các trạng thái của đối tượng từ thời điểm ban đầu đến thời điểm t.
Đối với quá trình quan sát (được xác định dựa trên các thông tin từ video):
• : các quan sát tại thời điểm t.
• : chuỗi các quan sát từ thời điểm ban đầu đến thời điểm t.
Mục tiêu của phương pháp Bayes là ước lượng trạng thái x
t
dựa trên chuỗi
quan sát Z
t
. Để ước lượng trạng thái x
t
cho một hệ thống, ta cần có 2 mô hình:
Mô hình động: mô hình sự tiến hóa của trạng thái theo thời gian:
eq. 2
với là vectơ nhiễu (ngẫu nhiên), xác suất chuyển trạng thái tính được từ mô
hình này.
Mô hình quan sát: mô tả mối quan hệ giữa các quan sát và trạng thái của
đối tượng tại một thời điểm: