ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
Vũ Minh Đức
XÂY DỰNG HỆ THỐNG TÌM KIẾM ẢNH THEO
NỘI DUNG
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
HÀ NỘI - 2015
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
Vũ Minh Đức
XÂY DỰNG HỆ THỐNG TÌM KIẾM ẢNH THEO
NỘI DUNG
Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60480104
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS. TS. Nguyễn Hải Châu
HÀ NỘI - 2015
Hà Nội, ngày 21 tháng 5 năm 2015
Học viên
Vũ Minh Đức
ii
TÓM TẮT LUẬN VĂN
Trong các chủ đề thuộc lĩnh vực xử lý nhận dạng hình ảnh, tìm kiếm ảnh theo
nội dung là một bài toán đƣợc đặt ra để thay thế cho phƣơng pháp tìm kiếm ảnh
thông thƣờng dựa trên các từ khóa hoặc các mô tả của ảnh.
Tìm kiếm theo nội dung tức là bản thân bức ảnh sẽ đƣợc phân tích để phục vụ
cho việc tìm kiếm (chứ không dựa vào các từ khóa, các tag hoặc các mô tả của bức
ảnh). Nội dung của bức ảnh ở đây có thể là các đối tƣợng, kết cấu, hoặc các đặc
trƣng khác đƣợc trích xuất từ chính bức ảnh. Việc hệ thống tìm kiếm ảnh theo nội
dung đƣợc cho là ƣu việt hơn tìm kiếm theo từ khóa ở chỗ trên thực tế ngƣời dùng
có thể không tìm đƣợc đúng và đủ từ khóa để mô tả bức ảnh. Trong một số trƣờng
hợp cụ thể (ví dụ nhƣ tìm kiếm các bức ảnh giống nhau về nội dung nhƣng khác về
kích thƣớc và màu sắc hoặc tìm kiếm các bức ảnh có cùng một vật thể hoặc đối
tƣợng ngƣời tìm kiếm chƣa biết tên gọi), thậm chí phƣơng pháp tìm kiếm theo từ
khóa không thể áp dụng hiệu quả đƣợc. Khi đó áp dụng phƣơng pháp tìm kiếm theo
nội dung sẽ có thể hiệu quả hơn.
Do số lƣợng các yếu tố có thể xem là nội dung của một bức ảnh rất đa dạng
theo nhu cầu của từng ngƣời tìm kiếm nhƣng thời gian nghiên cứu và hoàn thành
luận văn có hạn nên tôi xin phép giới hạn lại. Nội dung của một bức ảnh trong luận
văn này sẽ xoay quanh khuôn mặt trực diện của ngƣời và các động vật có vú. Theo
đó hệ thống tìm kiếm theo nội dung ảnh đƣợc xây dựng sẽ trích rút các nội dung
nhƣ: một bức ảnh có xuất hiện khuôn mặt hay không, số lƣợng khuôn mặt xuất hiện
trong bức ảnh là bao nhiêu, danh tính của các khuôn mặt trong bức ảnh và bản thân
mẫu huấn luyện không cần nhiều. Thực tế chỉ cần một ảnh của một ngƣời hoặc
động vật có vú là có thể ngay lập tức nhận diện khá chính xác ngƣời hoặc vật đó.
iv
MỤC LỤC
LỜI CẢM ƠN ........................................................................................................................ i
LỜI CAM ĐOAN .................................................................................................................ii
TÓM TẮT LUẬN VĂN ..................................................................................................... iii
MỤC LỤC ............................................................................................................................ v
DANH MỤC CÁC CÔNG THỨC .....................................................................................vii
DANH MỤC CÁC HÌNH VẼ .......................................................................................... viii
DANH MỤC CÁC BẢNG BIỂU........................................................................................ ix
BẢNG CÁC CHỮ VIẾT TẮT ............................................................................................. x
CHƢƠNG 1: TỔNG QUAN ................................................................................................ 1
1.1.
Đặt vấn đề ........................................................................................................................................1
1.2.
Mục tiêu đề tài..................................................................................................................................2
1.3.
Đối tƣợng và phƣơng pháp nghiên cứu ............................................................................................3
1.4.
CHƢƠNG 4: KẾT QUẢ THỰC NGHIỆM ....................................................................... 34
4.1. Thí nghiệm 1: ....................................................................................................................................34
4.1.1. Mục đích thực nghiệm:...............................................................................................................34
4.1.2. Bố trí thí nghiệm: .......................................................................................................................34
4.1.3. Kết quả thí nghiệm: ....................................................................................................................36
4.2. Thí nghiệm 2: ....................................................................................................................................36
4.2.1. Mục đích thực nghiệm:...............................................................................................................36
4.2.2. Bố trí thí nghiệm: .......................................................................................................................36
4.2.3. Kết quả thí nghiệm .....................................................................................................................39
4.3. Thí nghiệm 3: ....................................................................................................................................40
4.3.1. Mục đích thí nghiệm: .................................................................................................................40
4.3.2. Bố trí thí nghiệm: .......................................................................................................................40
4.3.3. Kết quả thực nghiệm ..................................................................................................................42
CHƢƠNG 5: KẾT LUẬN .................................................................................................. 43
5.1. Các kết quả đạt đƣợc và hạn chế .......................................................................................................43
5.2. Các công việc trong tƣơng lai ...........................................................................................................45
Tài liệu tham khảo .............................................................................................................. 47
vi
DANH MỤC CÁC CÔNG THỨC
Công thức 2.1: Công thức tính LBP của một điểm ảnh ....................................................... 8
Công thức 2.2: Công thức của bộ phân lớp yếu ................................................................. 12
Công thức 2.3: Công thức tính bảng các trọng số của các mã nhị phân tại điểm ảnh p..... 13
Công thức 2.4: Công thức tính biểu đồ tần xuất của một ảnh ............................................ 18
Công thức 2.5: Công thức tính biểu đồ tần xuất của một ảnh chia nhỏ thành các vùng .... 18
Công thức 2.6: Công thức tính độ tƣơng giao của hai biểu đồ tần xuất ............................. 19
Hình 4.2: các bƣớc thực hiện thí nghiệm 2 ........................................................................ 38
Hình 4.3: Các bƣớc thí nghiệm 3 ....................................................................................... 41
viii
DANH MỤC CÁC BẢNG BIỂU
Bảng 4.1: Kết quả thí nghiệm 1 ........................................................................................ 36
Bảng 4.2: Kết quả thí nghiệm 2 ........................................................................................ 39
Bảng 4.3: Kết quả thí nghiệm 3 ........................................................................................ 42
ix
BẢNG CÁC CHỮ VIẾT TẮT
Chữ
viết
tắt
SVM
PCA
LBP
MB-LBP
LBPH
Cách viết đầy đủ
Dịch nghĩa Tiếng Việt
Support Vector Machines
Khác với phƣơng pháp tìm kiếm ảnh bằng từ khóa, tìm kiếm theo nội dung tức
là bản thân bức ảnh sẽ đƣợc phân tích để phục vụ cho việc tìm kiếm (chứ không
dựa vào các từ khóa, các tag hoặc các mô tả của bức ảnh). Nội dung của bức ảnh ở
đây có thể là các đối tƣợng, kết cấu, hoặc các đặc trƣng khác đƣợc trích xuất từ
chính bức ảnh. Việc hệ thống tìm kiếm ảnh theo nội dung đƣợc cho là ƣu việt hơn
tìm kiếm theo từ khóa ở chỗ trên thực tế không phải bức ảnh nào cũng có thông tin
metadata đầy đủ hoặc có văn bản kèm theo. Thậm chí văn bản kèm theo các bức
ảnh có thể không có liên quan đến nội dung bức ảnh. Nhƣ vậy ngƣời dùng sẽ nhận
đƣợc kết quả tìm kiếm sai từ hệ thống tìm kiếm dựa trên từ khóa. Ngoài ra, trong
nhiều trƣờng hợp ngƣời dùng không tìm đƣợc đúng và đủ từ khóa để mô tả bức
ảnh. Trong một số loại hình tìm kiếm ảnh cụ thể (ví dụ nhƣ tìm kiếm các bức ảnh
giống nhau về nội dung nhƣng khác về kích thƣớc và màu sắc hoặc tìm kiếm các
bức ảnh có cùng một vật thể hoặc đối tƣợng ngƣời tìm kiếm chƣa biết tên gọi) thậm
1
chí phƣơng pháp tìm kiếm theo từ khóa không thể áp dụng hiệu quả đƣợc. Khi đó
có thể áp dụng phƣơng pháp tìm kiếm theo nội dung.
1.2. Mục tiêu đề tài
Những vấn đề đã nêu ở trên cho ta thấy đƣợc sự cần thiết của việc nghiên cứu,
xây dựng một hệ thống tìm kiếm ảnh dựa vào chính nội dung của ảnh. Do số lƣợng
các yếu tố có thể xem là nội dung của một bức ảnh rất đa dạng theo nhu cầu của
từng ngƣời tìm kiếm nhƣng thời gian nghiên cứu và hoàn thành luận văn có hạn
nên tôi xin phép giới hạn lại. Nội dung của một bức ảnh đƣợc đề cập trong luận văn
này sẽ xoay quanh khuôn mặt trực diện của ngƣời và các động vật có vú. Theo đó
hệ thống tìm kiếm theo nội dung ảnh đƣợc xây dựng trong luận văn sẽ trích rút các
nội dung nhƣ: một bức ảnh có xuất hiện khuôn mặt hay không, số lƣợng khuôn mặt
xuất hiện trong bức ảnh là bao nhiêu, danh tính của các khuôn mặt trong bức ảnh và
Phƣơng pháp nghiên cứu là dựa vào bộ công cụ xử lý ảnh OpenCV có sẵn để
xây dựng một công cụ cho phép khảo sát, thực nghiệm và cài đặt đƣợc một hệ
thống tìm kiếm ảnh xoay quanh khuôn mặt ngƣời và động vật có vú. Tuy vậy,
phƣơng pháp đƣợc trình bày có thể áp dụng để xây dựng các mô hình phân lớp cho
phép xác định các nội dung liên quan đến các các vật thể khác nhƣ logo của các
công ty hoặc các đồ vật khác ...
1.4. Cấu trúc khóa luận
Khóa luận đƣợc tổ chức thành các chƣơng nhƣ sau:
Chƣơng 1: Mở đầu
Chƣơng này nhằm nêu bật sự cần thiết, ý nghĩa thực tiễn, đối tƣợng,
phƣơng pháp nghiên cứu, mục tiêu của đề tài xây dựng hệ thống tìm kiếm
ảnh theo nội dung của bức ảnh.
Chƣơng 2: Các thuật toán nhận dạng khuôn mặt áp dụng trong hệ
thống tìm kiếm ảnh theo nội dung.
Chƣơng này nêu lên các thuật toán học máy có giám sát đƣợc áp dụng
để tìm kiếm và nhận dạng khuôn mặt ngƣời và động vật có vú. Từ đó, dựa
3
vào các thuật toán này để giải quyết bài toán tìm kiếm ảnh theo nội dung
trong ảnh.
4
Chƣơng này cũng đề xuất phƣơng pháp huấn luyện bán giám sát
Bootstrapping và cách thức kết hợp nó với các thuật toán học máy có giám
sát để xác định vị trí các đối tƣợng trong bức ảnh với một bộ dữ liệu huấn
qua những vùng khác nhau của bức ảnh. Mỗi lần trƣợt, bộ phân lớp sẽ đánh giá
xem cửa sổ đó có phải là một khuôn mặt hay không. Bộ phân lớp sử dụng ở đây có
thể là SVM (Máy vector hỗ trợ - Support Vector Machines), Mạng nơ ron (Neural
Netwworks), bộ phân lớp Bayes (Bayesian) hoặc mô hình Markov ẩn (Hiden
Markov Models). Trong đó có một vài cách tiếp cận nổi tiếng đƣợc để cập dƣới
đây.
Turk và Pentland đã đề xuất sử dụng PCA (phân tích thành phần chính –
Principal Component Analysis) để huấn luyện các ảnh khuôn mặt và sử dụng
eigenfaces (các khuôn mặt đặc biệt) làm các mẫu. Một khuôn mặt ngƣời sẽ đƣợc
coi là gần giống khuôn mặt mẫu 1, hơi giống khuôn mặt mẫu 2, hoặc hơi khác
khuôn mặt mẫu 3. Bộ phân lớp sẽ tính toán sự tƣơng đồng của một vùng ảnh (lấy
bởi cửa sổ trƣợt) với các mẫu khuôn mặt và từ đó quyết định đƣợc vùng ảnh đó có
phải một khuôn mặt hay không.
Viola và Jones thay vì sử dụng các thông tin của từng điểm ảnh, họ đề xuất
phƣơng pháp sử dụng một đại diện ảnh mới và một tập các đặc trƣng đơn giản trích
rút từ ảnh đại diện đó. Các đặc trƣng đó gọi là các đặc trƣng Haar. Các đặc trƣng
6
này đƣợc tính toán bằng cách cộng các điểm ảnh trong vùng sáng và trừ đi các
điểm ảnh trong vùng tối của ảnh.
Hình 2.1: Các đặc trƣng Haar
Tập các đặc trƣng đƣợc tạo lập bằng cách biến đổi kích thƣớc và vị trí của mỗi
loại đặc trƣng Haar. Các đặc trƣng sau đó đƣợc lựa chọn. Mỗi đặc trƣng sẽ đƣợc
huấn luyện trên tập các mẫu ảnh là các khuôn mặt hoặc các hình không phải khuôn
mặt (hay gọi là các hình nền). Sau quá trình huấn luyện, ngƣời ta sẽ chọn đặc trƣng
có số lƣợng kết quả nhận dạng sai là thấp nhất.
Với ic là giá trị độ xám của (xc, yc), in là giá trị độ xám của điểm ảnh (xn, yn) lân
cận của (xc, yc).
Hàm s(x) đƣợc định nghĩa nhƣ sau:
𝑠 𝑥 =
1 𝑛ế𝑢 𝑥 ≥ 0
0 𝑛ế𝑢 𝑥 ≤ 0
Ta có thể minh họa cách tính giá trị chuỗi nhị phân LBP (điểm có giá trị xám
là 57 ở
giữa ma trận) nhƣ sau:
83 82 63
38 57 46
28 19 23
1 1 1
0
0
0 0 0
11100000
Hình 2.3: Hình minh họa cách tính LBP
Ta có thể thấy nếu độ sáng thay đổi đồng đều thì trong lân cận cục bộ, thứ tự
của các điểm ảnh đƣợc bảo toàn. Nhƣ vậy, LBP cho phép miêu tả cục bộ rất tốt cho
từng điểm ảnh của bức ảnh.
Tuy vậy, do giá trị cấp xám ở đây đƣợc lấy trên từng điểm ảnh nên bị ảnh
hƣởng rất nhiều bởi nhiễu. Hơn nữa các ma trận nhỏ 3x3 chỉ đại diện cho từng
điểm ảnh chứ khó có thể sử dụng thông tin này để đại diện cho một vùng ảnh. Mặt
khác, số lƣợng các điểm ảnh trong một bức ảnh là rất lớn nên nếu sử dụng thông tin
9
1
Hình 2.4: Hình minh họa cách chia vùng 3x3 của MB-LBP
Do lấy giá trị trung bình của cả vùng nên thông tin LBP có thể đại diện cho
cả một vùng ảnh thay vì từng điểm ảnh nhƣ trƣớc. Độ nhạy cảm với nhiễu cũng
giảm đi nhiều. Các thông tin mang tính quá cục bộ bị loại bỏ nhƣng vẫn giữ lại các
giá trị cần thiết để có thể đại diện cho các vùng ảnh. Hình sau minh họa các bức
ảnh sau khi đã chia thành từng vùng và tính giá trị cấp độ xám trung bình của từng
vùng.
10
Hình 2.5: Hình minh họa các khuôn mặt sau khi áp dụng MB-LBP
(a1) (a2) là các ảnh gốc, (b1) (b2) là ảnh tính giá trị trung bình từng vùng 3x3, (c1)
(c2) là ảnh tính giá trị trung bình của từng vùng 9x9
Do phƣơng pháp tính giá trị MB-LBP của các vùng giống nhƣ cách tính giá
trị LBP nên ta có thể thấy mỗi vùng đƣợc đại diện bằng một chuỗi nhị phân 8 bit.
Tổng số lƣợng các chuỗi nhị phân có thể xuất hiện là 28 = 256. Ta có thể lập đƣợc
biểu đồ tần xuất xuất hiện của 256 chuỗi nhị phân này và do đó có thể sử dụng
chúng làm đặc trƣng để nhận dạng một ảnh có phải là ảnh của một khuôn mặt hay
không.
Tuy vậy nếu sử dụng cả 256 chuỗi nhị phân làm đặc trƣng thì sẽ làm tốc độ
huấn luyện và phân lớp rất chậm do số lƣợng đặc trƣng quá nhiều. Hơn nữa không
là đầu vào của bộ phân lớp yếu hp(x), tại vị trí p, đầu ra của hp(x) là giá trị của trọng
số tƣơng ứng với mã nhị phân x. Hn(X) là bộ phân lớp tổng hợp của tầng n:
𝐻𝑛 𝑋 =
𝑝 𝑥
(2.2)
𝑝 ∈ 𝑊𝑛
Công thức 2.2: Công thức của bộ phân lớp yếu
Trong đó, Wn là tập các điểm ảnh của tầng n.
2.1.3.2. Huấn luyện chồng tầng
Ý tƣởng của huấn luyện và phân lớp chồng tầng là bộ phân lớp sẽ là tổng
hợp của nhiều bộ phân lớp yếu (nhiều tầng). Trong đó xác suất phân lớp chính xác
của các bộ phân lớp yếu này chỉ cần tốt hơn so với việc phân lớp theo kiểu ngẫu
nhiên. Do vậy các bộ phân lớp yếu sẽ chỉ cần rất đơn giản và việc xây dựng nên các
12
bộ phân lớp yếu này không yêu cầu phải tính toán phức tạp. Tuy vậy kết quả cuối
cùng, bộ phân lớp tổng hợp từ nhiều tầng sẽ cho một kết quả rất chính xác.
Khi huấn luyện, thuật toán huấn luyện sẽ chọn ra những bộ phân lớp yếu
(tầng) sao cho kết quả phân lớp của bộ phân lớp yếu đó có lƣợng kết quả sai là ít
nhất. Ở đây ta đang phân lớp các ảnh là ảnh của một khuôn mặt hay không vì vậy
thuật toán sẽ chọn ra những vị trí vùng ảnh và và bảng các giá trị trọng số của các
mã nhị phân tƣơng ứng với vùng ảnh đó (nhƣ đề cập ở trên).
Cụ thể thuật toán nhƣ sau:
0 𝑡ạ𝑖 𝑐á𝑐 𝑡𝑟ườ𝑛𝑔 ợ𝑝 𝑘á𝑐
(2.3)
Công thức 2.3: Công thức tính bảng các trọng số của các mã nhị phân tại điểm ảnh p
Tới cuối cùng, mỗi mã nhị phân x tại điểm ảnh có vị trí p sẽ có trọng số là
tổng giá trị trọng số của Lp[x] tại mỗi vòng lặp và các bảng Lp đƣợc gộp lại một
bảng đƣợc tính theo công thức
13
Copyright: Tài liệu đại học ©