ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN




VŨ THANH HƯNG


SO KHỚP CHUỖI ẢNH MẶT NGƯỜI
TRÊN DỮ LIỆU VIDEO LỚN


Ngành: KHOA HỌC MÁY TÍNH
Mã số: 60.48.01


LUẬN VĂN THẠC SĨ
(Ngành Tin học)



NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS. TS. LÊ HOÀI BẮC
TS. LÊ ĐÌNH DUY




Thành phố Hồ Chí Minh - 2011
2

LỜI CẢM ƠN
Tôi xin gửi lời biết ơn tới PGS. TS. Lê Hoài Bắc, Thầy đã tận tính hướng dẫn,
định hướng, đồng thời chính Thầy là người đã tạo điều kiện thuận lợi cho tôi có thể
hoàn thành luận văn này.
Tôi xin chân thành biết ơn TS. Lê Đình Duy và GS. Shin’ichi Satoh ở viện tin
học quốc gia Nhật Bản đã giúp đỡ, chỉ bảo, hướng dẫn tôi không chỉ về kiến thức
chuyên môn mà còn về kĩ năng n
ghiên cứu trong suốt quá trình thực hiện luận văn
tại viện tin học quốc gia Nhật Bản.
Tôi cũng xin gửi lời cảm ơn tới các anh Ngô Đức Thành, Cáp Phạm Đình Thăng,
Hoàng Văn Hiệp đã đóng góp, thảo luận, góp ý cho luận văn này. Những đóng góp
nhiệt tình của mọi người đã hỗ trợ rất nhiều cho tôi trong quá trình thực hiện luận
văn.
Con xin cảm ơn ba mẹ, đấng sinh thành, nuôi dưỡng,
dạy dỗ con để con có được
ngày hôm nay. Mặc dù không tham gia trực tiếp vào quá trình làm luận văn nhưng
sự động viên, cảm thông, giúp đỡ về tinh thần của ba mẹ đã giúp con có thể vượt
qua khó khăn, vững tin để hoàn thành luận văn này.
Xin cảm ơn tất cả!
Người thực hiện
Vũ Thanh Hưng










3


MỤC LỤC
MỤC LỤC 3
Danh mục các kí hiệu và chữ viết tắt 5
Danh mục các bảng 6
Danh mục hình vẽ, đồ thị 7
Tóm tắt luận văn 8
Chương 1 Tổng quan 10
1.1 Giới thiệu 10
1.1.1 Định nghĩa face track (chuỗi ảnh) 11
1.1.2 Định nghĩa bài toán 11
1.1.3 Các bước xử lý chính 13
1.1.4 Những thách thức 14
1.2 Đóng góp của luận văn 17
1.3 Cấu trúc luận văn 17
Chương 2 Các công trình nghiên cứu liên quan 19
2.1 Hướng tiếp cận rút trích face track 19
2.2 Hướng tiếp cận biểu diễn ảnh mặt người 20
2.2.1 Local Binary Pattern (LBP) 21
2.2.2 Scale Invariant Feature Transform (SIFT) 23
2.2.3 Bộ lọc Gabor 25
2.2.4 Eigenfaces 27
2.2.5 Linear Discriminant Analysis (LDA) 28
2.3 Hướng tiếp cận so khớp face track 30
4

2.3.1

 Phương pháp dựa trên tập điểm 30
2.3.2 Phương pháp dựa trên phân bố xác suất 32
2.3.3 Phương pháp dựa trên bao 33
2.3.4 Phương pháp không gian con 35
2.4 Các công trình liên quan trong Khoa 38
Chương 3 Hệ thống tìm kiếm nhân vật dựa trên face track 40
3.1 Rút trích face track 40
3.2 Biểu diễn ảnh mặt người 41
3.3 Biểu diễn face track và so khớp 42
Chương 4 Kết quả thực nghiệm và phân tích 47
4.1 Cơ sở dữ liệu face track 47
4.2 Đánh giá 47
4.2.1 Đánh giá độ chính xác 47
4.2.2 Đánh giá tốc độ 51
4.3 Thực nghiệm 51
4.3.1 Lựa chọn tham số cho các thuật toán 51
4.3.2 Kết quả độ chính xác 53
4.3.3 Kết quả tốc độ 58
Chương 5 Kết luận và hướng phát triển 60
5.1 Kết luận 60
5.2 Hướng phát triển 61
Tài liệu tham khảo 62
Phụ lục A: Chi tiết danh mục các công trình 66
5


Danh mục các kí hiệu và chữ viết tắt
AP Average Precision
CMSM Constrained Mutual Subspace Method
HIK Histogram Intersection Kernel

KLT Kanade-Lucas-Tomasi
LBP Local Binary Pattern
LDA Linear Discriminant Analysis
MAP Mean Average Precision
MSM Mutual Subspace Method
PCA Principle Component Analysis
SIFT Scale Invariant Feature Transform
6


Danh mục các bảng
Bảng 4-1: Tính toán giá trị Precision(r) × rel(r) trong ví dụ Hình 4.1. 49
Bảng 4-2: Thực nghiệm chọn ngưỡng T cho phương pháp MSM 52
Bảng 4-3: Thực nghiệm chọn số chiều không gian con ràng buộc cho CMSM. 52
Bảng 4-4: Độ chính xác (MAP) của các thuật toán 53
Bảng 4-5: Tác dụng của bước chuẩn hóa. 55
Bảng 4-6: Thời gian thực thi và độ phức tạp tính toán của các phương pháp 59

7


Danh mục hình vẽ, đồ thị
Hình 1-1: Ví dụ về face track. Mỗi face track ứng với một người 11
Hình 1-2: Bài toán so khớp face track 13
Hình 1-3: Hệ thống tìm kiếm nhân vật trong video dựa trên face track 14
Hình 1-4: Các yếu tố chính ảnh hưởng tới bài toán so khớp face track 15
Hình 2-1: Gom nhóm face track dựa trên theo theo vết vùng đồng biến affine 20
Hình 2-2: Rút trích đặc trưng cho mỗi ảnh trong face track. 21
Hình 2-3: Toán tử LBP được áp tại một điểm trong ảnh 22
Hình 2-4: Rút trích LBP cho ảnh mặt người. 23

Hình 2-5: Tính toán bộ mô tả (descriptor) cho SIFT với lưới 2 x 2 24
Hình 2-6: Bộ lọc Gabor có tính chất của một bộ lọc cạnh 26
Hình 2-7: Tập 40 bộ lọc Gabor ứng với 5 scale và 8 hướng 26
Hình 2-8: Mặt riêng 28
Hình 2-9: Ví dụ về chọn mặt phẳng chiếu trong LDA 29
Hình 2-10: Khoảng cách giữa hai face track trong thuật toán min-min 31
Hình 2-11: Phương pháp k-Faces với k = 3. 32
Hình 2-12: Mô hình face track bằng GMM 33
Hình 2-13: Phương pháp MSM 36
Hình 2-14: Phương pháp CMSM. 38
Hình 3-1: Liên kết các vùng mặt được dò với face track 41
Hình 3-2: Vector trung bình xấp xỉ cho vector riêng thứ nhất 44
Hình 3-3: Tính toán khoảng cách cosin trước (a) và sau (b) khi chuẩn hóa 46
Hình 4-1: Tính toán giá trị AP cho mỗi truy vấn. 50
Hình 4-2: Đồ thị thực nghiệm chọn ngưỡng T cho phương pháp MSM 52
Hình 4-3: Đồ thị chọn số chiều không gian con ràng buộc cho CMSM 53
Hình 4-4: mean-cos xấp xỉ phương pháp không gian con 55
Hình 4-5: Một trường hợp không tốt của mean-cos 56
8

Hình 4-6: k-Faces có độ chính xác thấp hơn các phương pháp khác 57

Tóm tắt luận văn
Hiện nay, có rất nhiều video được quay hàng ngày khiến cho dữ liệu video trên
thế giới càng ngày càng đồ sộ. Với khối lượng video lớn và hỗn tạp như trên, việc
đánh chỉ mục video (video indexing) là một bước quan trọng giúp cho quản lý, tìm
kiếm, thống kê dữ liệu trên video một cách hiệu quả, nhanh chóng và dễ dàng hơn.
Một trong những đối tượng xuất hiện thường xuyên nhất trong các đoạn video là
mặt người nên việc đánh chỉ mục cho
mặt người luôn được các nhóm trên thế giới

ưu tiên nghiên cứu. Một khi việc đánh chỉ mục video cho đối tượng mặt người được
giải quyết sẽ dẫn tới hàng loạt những ứng dụng lớn trong thực tế như: tìm kiếm
nhân vật trong các đoạn video, thống kế những sự kiện những nhân vật có ảnh
hưởng trong giai đoạn nhất định,
v.v…Luận văn này tập trung vào ứng dụng tìm
kiếm nhân vật trong video vì đây là ứng dụng phổ biến hiện nay. Đối với ứng dụng
này có hai hướng tiếp cận chính là hướng tiếp cận sử dụng một ảnh khuôn mặt
(single face) để đại diện cho mỗi nhân vật và hướng tiếp cận sử dụng chuỗi ảnh
(face track). Cả hai hướng tiếp cận này đều phải đương đầu với nhữn
g thách thức
chung của bài toán tìm kiếm nhân vật trong video như: sự thay đổi liên tục của tư
thế đầu, biến đổi nét mặt, ảnh hưởng của các điều kiện chiếu sáng, sự che khuất do
các đối tượng khác và nhiễu từ môi trường. Tuy nhiên, hướng tiếp cận sử dụng face
track có lợi thế hơn hướng tiếp cận dùng ảnh đơn vì dùng nhiều ảnh để biểu diễn
nên c
ó khả năng bao phủ được vùng rộng hơn những biến đổi của mặt người. Chính
vì lợi thế trên mà luận văn đã chọn hướng tiếp cận dùng face track cho bài toán tìm
kiếm nhân vật trong video. Một vấn đề đối với hướng tiếp cận này là do dùng nhiều
ảnh để biểu diễn, khiến cho các thuật toán so khớp dùng face track phải xử lý với
khối lượng dữ liệu lớn. Trong khi đó,
những thuật toán hiện tại vẫn chưa có khả
năng cân bằng giữa độ chính xác và tốc độ: một số thuật toán có khả năng cho kết
quả tốt cần nhiều thao tác tính toán phức tạp dẫn tới tốc độ xử lý chậm, không thích
hợp khi xử lý với khối lượng dữ liệu lớn; một số thuật toán khác có thể đạt tốc độ
9

nhanh nhờ những tính toán đơn giản lại phải đánh đổi độ chính xác. Chính vì sự
thiếu đi những thuật toán có khả năng đảm bảo cả độ chính xác và tốc độ xứ lý nên
luận văn đã tiến hành đánh giá một số thuật toán tiên tiến hiện nay (k-Faces, min-
min, MSM, CMSM v.v…), tìm hiểu nguyên nhân và đề ra một thuật toán mới (gọi

là mean-cos) có thể đạt được độ chính xác tương đương với các thuật toán trên
nhưng vẫn đảm bảo tốc độ tính to
án. Thuật toán đề xuất sử dụng vector trung bình
để biểu diễn cho mỗi face track và sử dụng khoảng cách cosine để tính toán độ khác
biệt giữa các face track. Luận văn đã chỉ ra rằng vector trung bình có thể xấp xỉ
thành phần chính thứ nhất của dữ liệu, do đó chỉ cần sử dụng một vector biểu diễn
vẫn có đạt được kết quả tương đư
ơng với các thuật toán khác, trong khi đó sử dụng
khoảng cách cosine – được sử dụng thành công trong các phương pháp không gian
con như MSM, CMSM – giúp cho đạt kết quả tốt trong giai đoạn so khớp. Việc chỉ
cần sử dụng một vector để biểu diễn face track đã giúp thuật toán được đề xuất có
lợi thế lớn về tốc độ tính toán so với các hướng tiếp cận khác. Đánh giá đã được
thực hiện t
rên cơ sở dữ liệu 1510 face track rút trích từ 370 giờ video TRECVID.
Độ chính xác của các thuật toán được so sánh dựa trên độ đo MAP (Mean Average
Precision), trong khi đó tốc độ của các thuật toán được đánh giá dựa trên cả thời
gian thực thi và trên lý thuyết dùng độ phức tạp thuật toán O. Kết quả cho thấy thuật
toán mean-cos có độ chính xác vượt qua k-Faces, min-min, MSM và có thể so sánh
với CMSM trong khi đó tốc độ của mean-cos chỉ thua k-Faces. Kết quả này chứng
tỏ rằng thuật toán m
à luận văn đề xuất có khả năng đạt tốc độ truy vấn nhanh trên
cơ sở dữ liệu lớn trong khi vẫn đảm bảo được độ chính xác, điều mà các thuật toán
hiện tại chỉ có thể đảm bảo được một trong hai yếu tố trên.
10


Chương 1 Tổng quan
1.1 Giới thiệu
Trong những thông tin video thường tìm kiếm, mặt người là một trong những
đối tượng được quan tâm nhiều nhất. Đó là vì phần lớn những đoạn video do con

người thu thập có mục đích là ghi lại những hoạt động, những sự kiện trong đời
sống hàng ngày của con người nên tần xuất xuất hiện của con người trong những
đoạn video này là rất cao. Điều này cũng ngầm định rằng trong video, mặt n
gười là
đối tượng xuất hiện thường xuyên nhất. Việc tìm kiếm đối tượng mặt người trong
video cho ta nhiều ứng dụng quan trọng, chẳng hạn như chúng ta có thể tìm kiếm
những đoạn video liên quan đến George Bush thông qua việc tìm kiếm những đoạn
video có chứa mặt của Bush hoặc chúng ta có thể tìm kiếm sự những sự kiện nổi bật
nhất thường được nhắc tới trong năm
2011 dựa trên nhận xét rằng: thông thường
mỗi sự kiện thường gắn với một nhân vật cụ thể, từ đó việc tìm kiếm có thể thực
hiện dựa trên tần suất xuất hiện của nhân vật đó. Trong các ứng dụng trên thì tìm
kiếm nhân vật trong video là ứng dụng rất phổ biến trong thực tế và là một bài toán
đáng để quan tâm nghiên cứu.
Những nghiên cứu về bài toán tìm kiếm n
hân vật trong video có thể chia thành
hai nhánh chính: hướng tiếp cận dựa trên ảnh đơn và hướng tiếp cận dựa trên face
track (chuỗi ảnh). Trong đó, hướng tiếp cận dựa trên face track có một lợi điểm là
có khả năng bao quát những biến đổi lớn của khuôn mặt, những thay đổi do ảnh
hưởng bên ngoài (như chiếu sáng, che khuất). Chính lợi điểm này khiến cho hướng
tiếp cận dựa trên face track gần đây nhận đư
ợc sự quan tâm của nhiều nhóm nghiên
cứu. Cũng chính vì lý do trên mà luận văn này chọn hướng tiếp cận dựa trên face
track làm hướng giải quyết cho bài toán. Trong phần tiếp theo của Chương 1, luận
văn sẽ trình bày những khái niệm cơ bản của bài toán tìm kiếm nhân vật trong video
nói chung và hướng tiếp cận dùng face track nói riêng.
11

1.1.1 Định nghĩa face track (chuỗi ảnh)
Face track (hay chuỗi ảnh) là khái niệm cơ bản nhất trong hướng tiếp cận dựa

trên face track. Thực chất, mỗi face track là chuỗi nhiều ảnh mặt người của cùng
một người. Nói cách khác, face track là một tập hợp ảnh mặt của cùng một người
có quan tâm tới thứ tự thời gian [10]. Số lượng các ảnh trong một face track là
không giới hạn, phụ thuộc vào thời gian xuất hiện của người đó trong video và hiệu
quả của g
iai đoạn rút trích face track. Do mỗi face track là chuỗi ảnh mặt người theo
thời gian nên mỗi face track thể hiện được cả những chuyển động của đầu, những
thay đổi trên nét mặt cũng như những thay đổi từ bên ngoài như điều kiện chiếu
sáng, che khuất v.v… Hình 1-1 là một số ví dụ về face track với số lượng ảnh cho
mỗi face track là khác nhau, có thể thấy trong mỗi face track, nét mặt v
à tư thế đầu
của các nhân vật biến đổi rất nhiều. Chính vì thế mà mỗi face track không chỉ đơn
giản lưu trữ ảnh mặt của một người mà còn cho biết những biến đổi trạng thái của
người đó, điều này khiến cho việc dùng face track có khả năng xử lý tốt hơn với
những biến đổi phong phú của mặt người.


Hình 1-1: Ví dụ về face track. Mỗi face track ứng với một người.

1.1.2 Phát biểu bài toán
Trong bài toán tìm kiếm nhân vật trong video, quá trình tìm kiếm không được
thực hiện trực tiếp trên dữ liệu video thô mà phải qua bước xử lý để loại bỏ những
thông tin dư thừa và tổ chức lại thông tin. Video sẽ qua một bước tiền xử lý để rút
trích thành những đối tượng video, sau đó quá trình tìm kiếm sẽ được thực hiện trên
12

những đối tượng video này. Những đối tượng video này có thể là những khung
hình, video shot hoặc những face track. Do luận văn tập trung vào bài toán tìm kiếm
nhân vật với hướng tiếp cận dùng face track nên đối tượng video được sử dụng là
face track. Như vậy quá trình tìm kiếm sẽ được thực hiện trên đối tượng face track,

có thể được mô tả như sau:
Cho trước một cơ sở dữ liệu gồm N face track, mỗi face track F
i
chỉ thuộc về
một người. Một hàm khoảng cách dis(F
i
, F
j
) để đánh giá độ khác biệt giữa hai face
track F
i
, F
j
trong đó hai face track F
i
và F
j
là trùng nhau khi dis(F
i
, F
j
) = 0. Với một
face track truy vấn G và một hàm khoảng cách, cần tính toán độ khác biệt giữa mỗi
face track F
i
và face track truy vấn G để trả về một danh sách xếp hạng
ở đây là hoán vị của 1, 2,…, N thỏa mãn
.
Như vậy, đầu ra của hệ thống tìm kiếm nhân vật trong video là danh sách xếp
hạng S. Danh sách xếp hạng thực chất là một danh sách những face track trong cơ

sở dữ liệu được sắp xếp theo thứ tự độ khác biệt tăng dần, theo nghĩa chúng ta
mong muốn những face track thuộc về cùng một người với face track truy vấn sẽ
xuất hiện đầu tiên trong danh sách. Những hệ thống tìm kiếm tốt phải trả về face

track của người đó tại những vị trí đầu của danh sách càng nhiều càng tốt. Hình 1-2
mô tả một cơ sở dữ liệu gồm N face track và một face track truy vấn thuộc về người
A, danh sách xếp hạng được xem là tốt nếu nó chứa những face track của người A
ngay đầu danh sách.

13


Hình 1-2: Bài toán so khớp face track.

1.1.3 Các bước xử lý chính
Một hệ thống tìm kiếm nhân vật trong video thường gồm ba mô-đun chính:
 Rút trích face track: thành phần này có nhiệm vụ rút trích ảnh mặt
người trong các video và tổ chức lại thành các face track. Đầu vào của
mô-đun này là một video nguyên bản và đầu ra sẽ là những face track
trong video đó.
 Biểu diễn ảnh mặt người: Sau giai đoạn rút trích mỗi face track chỉ đơn
giản là một chuỗi các ảnh, mô-đun này có nhiệm vụ biểu diễn mỗi ảnh
mặt n
gười trong face track thành những vector đặc trưng.
 Biểu diễn face track và so khớp: Dựa trên những vector đặc trưng đã
được rút trích cho mỗi ảnh từ bước trước, các face track sẽ được biểu
diễn thành những dạng thích hợp sao cho các face track phân biệt với
nhau nhiều nhất. Việc biểu diễn này được thực hiện cho cả face track truy
vấn G và mỗi face track trong cơ sở dữ liệu. Để so khớp, vector biểu
diễn face tr

ack truy vấn G sẽ lần lượt được tính toán sự sai biệt so với
14

mỗi vector biểu diễn face track trong cơ sở dữ liệu thông qua độ đo sự sai
biệt
để trả về danh sách xếp hạng cho người dùng. Mô-đun này
nhận vào vector biểu diễn face track truy vấn G, các face track trong cơ
sở dữ liệu và trả về một danh sách xếp hạng.


Hình 1-3: Hệ thống tìm kiếm nhân vật trong video dựa trên face track.

Hình 1-3 mô tả các mô-đun của hệ thống tìm kiếm nhân vật trong video dựa
trên face track. Mô hình được mô tả trên đây chỉ là mô hình tổng quát và chung
nhất. Trong thực tế, tùy thuộc vào yêu cầu của bài toán cụ thể cũng như ứng dụng
thực tế mà các hệ thống tìm kiếm có thể có thêm hoặc bỏ qua một số bước nào đó.
1.1.4 Những thách thức
Mặc dù bài toán tìm kiếm nhân vật dựa trên face track đã được nghiên cứu nhiều
trong những năm vừa qua, tuy nhiên đây vẫn là bài toán thách thức do những biến
đổi của mặt người và điều kiện thu video ảnh hưởng tới kết quả tìm kiếm. Những
nhân tố này không chỉ tác động một cách độc lập mà còn có thể đồng thời cùng ảnh
hưởng làm cho ảnh mặt người bị biến đổi rất lớn. Những nhân tố ảnh hưởng c
hính
đến bài toán so khớp face track gồm:

15

 Tư thế đầu người
Do chuyển động của cổ và góc quay camear nên mặt người có thể được nhìn
thấy tại những góc khác nhau. Kết quả so khớp thường chỉ tốt đối với ảnh chính

diện, khi đầu nhân vật bị nghiêng (sang trái, phải hoặc đang ngước lên, cúi xuống)
thì kết quả so khớp sẽ bị ảnh hưởng. Nguyên nhân là do khi mặt không ở tư thế nhìn
chính diện, việc lấy đặc trưng mặt n
gười sẽ trở nên khó khăn và không chính xác,
hơn thế nữa một số bộ phận của mặt sẽ bị che khuất hoặc nhìn không rõ, do đó ảnh
hưởng đến quá trình so khớp.
 Nét mặt
Khi nhân vật ở những trạng thái cảm xúc khác nhau hoặc đang thực hiện công
việc nhất định thì biểu hiện của nét mặt sẽ khác nhau. Khi vui, mắt người sẽ mở to

hơn trong khi đó khi buồn, mí mắt đóng lại. Một người khi ở trạng thái nói liên tục
sẽ dẫn tới sự thay đổi không ngừng về hình dạng của miệng, không những thế thỉnh
thoảng mắt sẽ nhắm lại. Sự thay đổi của nét mặt là một trong những trở ngại lớn
nhất do đây là những thay đổi diễn ra khá thường xuyên, ở những bộ phận khá nhỏ
tr
ên mặt như mắt, miệng nên khó phát hiện.

Hình 1-4: Các yếu tố chính ảnh hưởng tới bài toán so khớp face track.

16

 Chiếu sáng
Ánh sáng là nhân tố luôn tồn tại trong quá trình thu thập video. Với những điều
kiện ánh sáng khác nhau, ảnh thu thập được sẽ có độ sáng tối khác nhau. Nếu ta thu
video trong môi trường trong nhà, ít ánh sáng thì ảnh mặt người sẽ trở nên tối hơn
so với khi quay trong môi trường ngoài trời có nhiều ánh sáng. Đối với những đoạn
video quay trong môi trường thực tế (video tin tức, phóng sự, giám sát v.v…)
thường ánh sáng không được kiểm soát bởi con người, do đó đây là yếu tố có
thể
ảnh hưởng rất lớn đến hệ thống tìm kiếm nhân vật trên video. Hình 1-4 cho thấy

ánh sáng ảnh hưởng đến mức độ sáng tối của nhân vật Geogre Bush trong ảnh.
 Che khuất
Hiện tượng che khuất diễn ra khi có một đối tượng khác nằm phía trước nhân
vật, che đi một phần mặt của nhân vật. Hiện tượng che khuất không chỉ khiến cho
camera chỉ có thể thu
được một phần mặt người mà đối tượng xuất hiện trong ảnh
có thể ảnh hưởng tới kết quả của hệ thống truy tìm do không thể phân biệt được
vùng nào là mặt người và vùng nào là của đối tượng. Những đối tượng gây ra hiện
tượng che khuất có thể là micro, một người đứng trước hoặc do phát thanh viên vừa
ghi hình vừa di chuyển ngang qua một vật nào đó (cột điện, cánh cửa,
v.v…).
 Nhiễu
Một số yếu tố khác ảnh hưởng tới ảnh mặt người là nhiễu. Nhiễu có thể do thiết
bị thu gây ra, do đối tượng chuyển động quá nhanh hoặc do các hiệu ứng khi biên
tập video (các hiệu ứng chuyển cảnh).
Hình 1-4 cho thấy một số ví dụ về ảnh hưởng của các yếu tố trên đối với ảnh
mặt người trong video. Có thể thấy những yếu tố này ảnh hưởng rất lớn đến ảnh mặt
người. V
ì vậy, nếu chỉ sử dụng một ảnh để biểu diễn cho một người thì sẽ không thể
nào bao phủ được những biến đổi này. Mặc dù việc sử dụng face track cũng chỉ có
thể bao phủ phần nào những biến đổi trên, tuy nhiên đây có vẻ là hướng tiếp cận
hợp lý và đan
g được quan tâm nghiên cứu gần đây.
17

1.2 Đóng góp của luận văn
Luận văn đã đề xuất một thuật so khớp face track cho bài toán tìm kiếm nhân vật
trong video. Khác với đa số các thuật toán so khớp dựa trên face track khác chỉ có
thể thỏa mãn một trong hai yếu tố độ chính xác hoặc tốc độ. Thuật toán được đề
xuất có khả năng cân bằng được hai yếu tố này. Điều này rất quan trọng đối với

những hệ thống tìm kiếm người trên video trước sự bùng nổ của dữ liệu video khiến
c
ho yêu cầu về một thuật toán so khớp nhanh và hiệu quả trên dữ liệu video lớn là
cần thiết.
Thuật toán đã được so sánh với các phương pháp so khớp tiên tiến (min-min [3,
4, 5], k-Faces [9], MSM [7] và CMSM [8]) cả về độ chính xác và tốc độ dựa trên
cách thức đánh giá tin cậy và được sử dụng rộng rãi trong cộng đồng. Độ chính xác
của các thuật toán đã được so sánh dựa trên độ đo
MAP (Mean Average Precision)
thường dùng trong lĩnh vực truy vấn thông tin và phân loại đối tượng, trong khi đó
tốc độ được so sánh không chỉ dựa trên kết quả thực nghiệm mà còn bằng lý thuyết
dựa trên tính toán độ phức tạp của thuật toán. Kết quả đánh giá cho thấy, thuật toán
được đề xuất có thể thực hiện so khớp trên dữ liệu face track lớn một cách nhanh
chóng trong khi đó vẫn đạt được độ chính xác tương đương với các thuật to
án khác.
1.3 Cấu trúc luận văn
Bố cục luận văn gồm 5 chương như sau:
Chương 1: Giới thiệu tổng quan (định nghĩa, các ứng dụng, các thành phần hệ
thống, thách thức) về bài toán tìm kiếm nhân vật trên video dựa trên face track và
trình bày những đóng góp chính của luận văn.
Chương 2: Giới thiệu cách hướng tiếp cận chính cho hệ thống tim kiếm người
trong video dựa trên face track. Trong phần này các hướng tiếp cận để xây dựng các
mô-đun (rút trích face track, biểu diễn ảnh mặt người,
biểu diễn face track và so
khớp) của hệ thống sẽ được giới thiệu.
Chương 3: Mô tả các bước trong hệ thống tìm kiếm nhân vật trong luận văn.
18

Chương 4: Trình bày quá trình thực nghiệm trên thuật toán được đề xuất. Những
phân tích, đánh giá và so sánh với những thuật toán khác cũng được trình bày trong

phần này.
Chương 5: Đưa ra kết luận từ nghiên cứu và những hướng nghiên cứu mở rộng
trong tương lai.
19


Chương 2 Các công trình nghiên cứu liên quan
Do một hệ thống tìm kiếm nhân vật trên video dựa trên face track gồm 3 thành
phần chính là: rút trích face track từ video, biểu diễn ảnh mặt người, biểu diễn face
track và so khớp nên hệ thống tìm kiếm sẽ được xây dựng dựa trên việc kết hợp
những thành phần này lại với nhau. Với mỗi thành phần riêng lẻ lại có nhiều hướng
tiếp cận khác nhau để xây dựng, những hướng tiếp cận này không chỉ được giới
th
iệu riêng cho bài toán tìm kiếm nhân vật trong video mà còn có thể xuất hiện
trong những lĩnh vực khác. Chẳng hạn việc xây dựng mô-đun biểu diễn ảnh mặt
người có thể sử dụng các kĩ thuật biểu diễn ảnh mặt người trong những bài toán
nhận dạng mặt người, nhận dạng đối tượng hoặc phân loại ảnh. Vì vậy luận văn
trình bày những những hướng tiếp cận cho
toàn hệ thống tìm kiếm nhân vật dựa
trên những hướng tiếp cận được dùng để giải quyết từng mô-đun.
2.1 Hướng tiếp cận rút trích face track
Trong hệ thống tìm kiếm nhân vật dựa trên face track, một trong những bước
quan trọng đầu tiên là làm thế nào để rút trích các face track trong những đoạn
video. Có một số hướng tiếp cận đã được đề xuất để thực hiện việc này. Sivic và
cộng sự [5] rút trích face track bằng cách sử dụng thuật toán Adaboost để dò tìm
khuôn mặt người tại mỗi khung hình. Tiếp đó, những vùng ảnh dò ra được xem là
của cùng một người bằng cách theo vết những vùng đồng biến affi
ne (Hình 2-1).
Phương pháp này có thể đạt được kết quả tốt, tuy nhiên việc sử dụng bộ dò vùng
đồng biến là rất phức tạp và tốn chi phí. Everingham và cộng sự [3] cũng dùng bộ

dò mặt người Adaboost để tìm ra những vùng mặt người trong mỗi khung hình
video, tuy nhiên khác với phương pháp trong [5]-sử dụng cách theo vết các vùng
đồng biến affine để liên kết các vùng mặt lại với nhau, các tác giả trong [3] lại dùng
bộ theo vết Kanade-Lucas-Tom
asi (KLT) để theo vết các điểm quan tâm (interest
point) trong mỗi khung hình. Hai vùng mặt tại hai khung hình liên tiếp được xem là
20

của cùng một người nếu số điểm theo vết chung đi qua hai vùng mặt liên tiếp lớn
hơn số điểm không chung thì hai vùng mặt được xem là thuộc một face track của
cùng một người. Tuy nhiên, bộ dò KLT lại thường bị ảnh hưởng bởi sự thay đổi của
ánh sáng, che khuất và lỗi của bộ dò mặt người, do đó có thể khiến cho việc theo
vết các điểm quan tâm bị ngắt
quãng và dẫn tới các face track có thể bị phân mảnh.
Điều này có thể khắc phúc bằng cách dùng phương pháp được đề nghị bởi Ngo và
cộng sự [10], các tác giả trong [10] cũng dùng bộ dò KLT như trong [3] nhưng khác
với [3] những điểm quan tâm chỉ được theo vết trong các vùng ảnh mặt người thay
vì trong một shot và tính toán lại mỗi khung hình. Phương pháp này đã cho thấy cho
thấy hiệu quả hơn phương pháp của Everingham và cộng sự trong [10].


Hình 2-1: Gom nhóm face track dựa trên theo theo vết vùng đồng biến affine.

2.2 Hướng tiếp cận biểu diễn ảnh mặt người
Các face track sau khi được rút trích chỉ đơn giản là chuỗi những ảnh mặt người.
Quá trình biểu diễn ảnh mặt người được thực hiện cho mỗi ảnh trong face track.
Mỗi ảnh sẽ được rút trích đặc trưng và biểu diễn dưới dạng vector (Hình 2-2). Việc
này nhằm mục đích rút trích ra những thông tin thật sự quan trọng, mô tả những nét
đặc trưng nhất cho ảnh mặt người, nhờ đó giúp quá trình so khớp hiệu quả và c
hính

xác hơn. Có nhiều phương pháp rút trích đặc trưng khác nhau, phần lớn trong số
21

chúng là những kĩ thuật được sử dụng cho bài toán nhận dạng mặt người. Ở đây
luận văn chỉ giới thiệu một số đặc trưng mặt người được sử dụng rộng rãi và cho kết
quả tốt bao gồm: bộ lọc Gabor, đặc trưng SIFT, đặc trưng LBP, phương pháp biểu
diễn bằng Eigenfaces, phương pháp dựa trên LDA.


Hình 2-2: Rút trích đặc trưng cho mỗi ảnh trong face track.

2.2.1 Local Binary Pattern (LBP)
Mẫu nhị phân cục bộ (Local Binary Pattern-LBP) được đề xuất bởi Ojala [21]
năm 1994 là đặc trưng dùng cho bài toán phân loại vân (texture). Tuy nhiên, khi áp
dụng cho bài toán nhận dạng mặt người, nó trở nên phổ biến và tiếp tục được
nghiên cứu, mở rộng [16, 20]. LBP không những là một đặc trưng tốt biểu diễn mặt
người mà còn tính toán rất hiệu quả so với các loại đặc trưng khác. Kí hiệu
mô tả toán tử LBP gồm P điểm lân cận nằm trên đường tròn bán kính R.
Toán tử LBP sẽ được áp dụng lên mỗi điểm trong ảnh, giá trị cường độ sáng của
những điểm lân cận sẽ được so sánh với điểm đó. Nếu độ khác biệt này lớn hơn
hoặc bằng 0 thì sẽ nhận giá trị 1, ngược lại nhân giá trị 0. Kết quả của toán tử LBP

tại một điểm sẽ là một chuỗi bit 0, 1. Mỗi chuỗi này sẽ tương ứng với một số
nguyên duy nhất nằm trong đoạn từ 0 đến
:
22






Hình 2-3 cho thấy một ví dụ toán tử
với P = 8. Hình 2-3.1 là cường độ
pixel tại điểm đang xét và các điểm lân cận, Hình 2-3.2 hiệu số được tính toán tại
mỗi điểm lân cận so với điểm đang xét, Hình 2-3.3 là giá trị nhị phân tương ứng.
Mỗi giá trị nhị phân này sẽ được chuyển thành một giá trị số nguyên duy nhất (còn
gọi là một mẫu) như Hình 2-3.4.


Hình 2-3: Toán tử LBP được áp tại một điểm trong ảnh (Nguồn [20]).

Một biến thế khác của LBP là mẫu đồng nhất (uniform pattern) được giới thiệu
trong [20]. Mẫu đồng nhất xem xét số lần dịch chuyển từ 0-1 hoặc 1-0 trong chuỗi
bít (xoay vòng), những chuỗi bit nào có số lần dịch chuyển bé hơn hoặc bằng 2 sẽ
được xem như cùng một mẫu gọi là mẫu đồng nhất. Do đó, với chuỗi 8
bit thì sẽ có
59 mẫu (khác với LBP thông thường sẽ có 2
8
mẫu).
23

Để rút trích đặc trưng LBP cho ảnh mặt người, ảnh sẽ được chia thành lưới
. Tại mỗi vùng nhỏ trong ảnh, một histogram sẽ được xây dựng bằng cách áp
toán tử LBP tại mỗi pixel trong ô. Đặc trưng LBP cho ảnh có được bằng cách nối
các histogram này lại với nhau (Hình 2-4).


Hình 2-4: Rút trích LBP cho ảnh mặt người (Nguồn [20]).

2.2.2 Scale Invariant Feature Transform (SIFT)

Một đặc trưng khác gần đây cũng được áp dụng cho biểu diễn mặt người là phép
biến đổi đặc trưng bất biến tỉ lệ (Scale Invariant Feature Transform - SIFT). SIFT
được đề nghị bởi Lowe [22] cho bài toán so khớp đối tượng trong ảnh (object
matching). Từ khi được giới thiệu, đặc trưng SIFT đã được thử nghiệm cho hầu hết
các bài toán hiện có trong lĩnh vực thị giác máy tính. Có thể nói đây là một trong
những đặc trưng ảnh nổi tiếng và
sử dụng rộng rãi nhất trong cả lĩnh vực thị giác
máy tính tới thời điểm hiện tại. SIFT bao gồm hai giai đoạn chính: giai đoạn tìm
kiếm các điểm quan tâm (interest point) – giai đoạn này được thực hiện bởi bộ dò
tìm (detector) và giai đoạn mô tả điểm quan tâm được thực hiện bởi bộ mô tả
(descriptor). Trong thuật toán SIFT được mô tả bởi Lowe, bộ dò
tìm được dùng là
bộ dò DoG (Difference of Gaussian). Các điểm quan tâm (x, y, s) được trả về từ bộ
dò thông thường là những góc cạnh hoặc những điểm có sự chênh lệch sáng tối
nhiều, các tham số x, y mô tả tọa độ và s mô tả tỉ lệ của điểm quan tâm. Những
24

điểm nay sau đó sẽ được mô tả bởi bộ mô tả qua hai bước chính: tính toán hướng
chính và mô tả điểm quan tâm.
Tính toán hướng chính:
 Tính toán độ lớn và hướng gradient của các pixel nằm trong bán kính s
quanh điểm (x, y) và đánh trọng số theo hàm Gaussian tâm tại (x, y).
 Các giá trị gradient này sẽ được gán vào histogram hướng 36 khoảng.
Khoảng với giá trị cao nhất sẽ được chọn làm hướng chính, những đỉnh cục
bộ lớn hơn 80% giá
trị đỉnh cao nhất cũng được chọn để tạo ra bộ mô tả
(descriptor) với hướng chính mới. Với mỗi đỉnh được chọn, 2 khoảng kế nó
cũng sẽ được dùng để nội suy ra giá trị hướng chính chính xác hơn.
Mô tả:
 Vùng ảnh sẽ được chuẩn hóa theo tỉ lệ và hướng chính.

 Độ lớn gradient và hướng sẽ được đánh trọng số dựa trên hàm Gaussian.
 V
ùng ảnh được chia thành thành vùng con và tính toán histogram
hướng 8 khoảng cho mỗi vùng con. Histogram hướng của mỗi vùng con sẽ
được nối lại với nhau để tạo thành đặc trưng
chiều.


Hình 2-5: Tính toán bộ mô tả (descriptor) cho SIFT với lưới 2×2 (Nguồn [22]).

Giai đoạn mô tả vùng được thể hiện trong Hình 2-5, vùng được chia thành vùng
con
(ở đây ). Gradient sẽ được đánh trọng số dựa theo hàm Gaussian -
25

được mô tả bằng đường tròn màu xanh (hình trái); histogram hướng sẽ được lấy
theo mỗi vùng (hình phải) và được nối lại với nhau để tạo thành đặc trưng SIFT.
Đặc trưng SIFT khi sử dụng mô tả mặt người đều có bước mô tả các điểm quan
tâm giống như trong [22]. Các hướng tiếp cận khác nhau ở cách lựa chọn những
điểm trên khuôn mặt để biễu diễn đặc trưng SIFT. Rosenberger và Brun [15] cũng
dùng bộ dò DoG
để chọn những điểm quan tâm. Nhược điểm lớn nhất của cách
dùng bộ dò tìm là số lượng điểm quan tâm trả về thường nhiều, thêm nữa có thể
chứa nhiều vị trí không thật sự quan trọng nên một số tác giả đã chọn sẵn những vị
trí quan trọng trên khuôn mặt để mô tả như: mũi, khóe miệng, giữa miệng, hốc mắt
v.v… như Sivic và
cộng sự trong [5]. Với cách làm này, Sivic sử dụng ít điểm quan
tâm hơn nhưng sẽ thu được kết quả tốt hơn do chỉ những điểm quan trọng nhất đã
được sử dụng để mô tả cho mặt người.
2.2.3 Bộ lọc Gabor

Bộ lọc Gabor là một trong những phương pháp tiêu biểu cho hướng sử dụng bộ
lọc. Ý tưởng chính của hướng sử dụng bộ lọc là thiết kế nhiều bộ lọc với những tính
chất khác nhau và xem xét phản hồi của ảnh khi cho tiếp xúc với mỗi bộ lọc. Tập
kết quả trả về này có thể cho ta thấy tính chất của ảnh. Một trong những bộ lọc đư
ợc
dùng thành công để biểu diễn ảnh mặt người là bộ lọc Gabor [17, 18, 19, 23]. Một
bộ lọc Gabor hai chiều có scale và hướng v được định nghĩa trong [17, 19] như
sau:

Trong đó z = (x, y) là vị trí áp bộ lọc,
là vector sóng với
và . là tần số tối đa và f là yếu tố khoảng cách giữa các
kernel trong miền tần số. Như vậy chúng ta có thể thấy bộ lọc Gabor là tích của hàm
sin hai chiều với hàm Gaussian, hay nói cách khác đây là hàm sin được đánh trọng