BỘ GIÁO DỤC VÀ ĐÀO TẠO
VIỆN HÀN LÂM KHOA HỌC
VÀ CÔNG NGHỆ VIỆT NAM
HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ
-----------------------------
NGÔ TRƯỜNG GIANG
NÂNG CAO HIỆU QUẢ TRA CỨU ẢNH
DỰA TRÊN HIỆU CHỈNH ĐỘ ĐO TƯƠNG TỰ
VÀ PHẢN HỒI LIÊN QUAN
LUẬN ÁN TIẾN SỸ TOÁN HỌC
HÀ NỘI – 2017
BỘ GIÁO DỤC VÀ ĐÀO TẠO
VIỆN HÀN LÂM KHOA HỌC
VÀ CÔNG NGHỆ VIỆT NAM
HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ
-----------------------------
NGÔ TRƯỜNG GIANG
NÂNG CAO HIỆU QUẢ TRA CỨU ẢNH
DỰA TRÊN HIỆU CHỈNH ĐỘ ĐO TƯƠNG TỰ
VÀ PHẢN HỒI LIÊN QUAN
LUẬN ÁN TIẾN SỸ TOÁN HỌC
Chuyên ngành: Cơ sở Toán học cho Tin học
Mã số: 62 46 01 10
Người hướng dẫn khoa học:
1. PGS. TS. Ngô Quốc Tạo
2. TS. Nguyễn Đức Dũng
Hà Nội – 2017
LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu do tôi thực hiện dưới sự hướng
dẫn của PGS.TS. Ngô Quốc Tạo và TS. Nguyễn Đức Dũng tại Học viện Khoa học
và Công nghệ - Viện hàn lâm Khoa học và Công nghệ Việt Nam. Các số liệu và
kết quả trình bày trong luận án là trung thực, chưa được công bố bởi bất kỳ tác
giả nào hay ở bất kỳ công trình nào khác.
Hà Nội, ngày 10 tháng 7 năm 2016
Tác giả
Ngô Trường Giang
i
LỜI CÁM ƠN
Luận án này được thực hiện tại Học viện Khoa học và Công nghệ, Viện Hàn lâm
Khoa học và Công nghệ Việt Nam dưới sự hướng dẫn khoa học của PGS.TS. Ngô
Quốc Tạo và TS. Nguyễn Đức Dũng. Tôi xin bày tỏ lòng biết ơn sâu sắc tới các
Thầy đã quan tâm, hướng dẫn từ các kỹ năng cơ bản đến định hướng khoa học,
tạo mọi điều kiện thuận lợi để tôi hoàn thành luận án.
Tôi xin cảm ơn tới tập thể Thầy Cô trong Viện Công nghệ Thông tin đã có
những ý kiến đóng góp và phản biện trong suốt quá trình nghiên cứu và hoàn
chỉnh luận án. Xin chân thành cảm ơn các nhà khoa học, tác giả các công trình
công bố được trích dẫn trong luận án vì đã cung cấp nguồn tư liệu quý báu, những
kiến thức liên quan trong quá trình nghiên cứu hoàn thành luận án.
Tôi xin trân trọng cảm ơn Lãnh đạo Viện Công nghệ Thông tin, Học Viện
Khoa học và Công nghệ đã tạo những điều kiện tốt nhất để nghiên cứu sinh có
được môi trường nghiên cứu và hoàn thành chương trình nghiên cứu của mình.
Xin chân thành cám ơn Phòng Nhận dạng và Công nghệ Tri thức, các phòng ban
của Viện Công nghệ Thông tin về sự hỗ trợ tạo điều kiện cho tôi trong suốt quá
trình thực hiện luận án.
Tôi xin gửi lời cảm ơn tới Ban giám hiệu Trường Đại học Dân lập Hải Phòng,
Khoa Công nghệ Thông tin đã tạo nhiều điều kiện thuận lợi hỗ trợ cho tôi có đủ
điều kiện thực hiện luận án. Xin cảm ơn tất cả bạn bè đồng nghiệp, những người
luôn chia sẻ, cổ vũ tôi trong những lúc khó khăn, động viên khích lệ để tôi thực
hiện và hoàn thành luận án.
Cuối cùng, tôi xin bày tỏ lòng biết ơn vô hạn đối với người thân trong gia
đình đã luôn ủng hộ động viên, tạo nguồn lực tinh thần to lớn để tôi có thể thực
hiện và hoàn thành được luận án này.
ii
Mục lục
Mục lục
iii
Danh sách hình vẽ
v
Danh sách bảng
vii
Danh sách chữ viết tắt
viii
MỞ ĐẦU
1
1 TRA CỨU ẢNH DỰA TRÊN NỘI DUNG
1.1 Một số vấn đề cơ bản trong CBIR . . . . . .
1.1.1 Trích chọn đặc trưng mức thấp . . .
1.1.2 Độ đo tương tự . . . . . . . . . . . .
1.1.3 Đánh giá hiệu năng hệ thống . . . .
1.2 Độ đo tương tự kết hợp các đặc trưng . . . .
1.3 Phản hồi liên quan trong CBIR . . . . . . .
1.3.1 Kỹ thuật cập nhật truy vấn . . . . .
1.3.2 Những kỹ thuật học thống kê . . . .
1.4 Tổng kết chương . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2 ĐỘ ĐO TƯƠNG TỰ HÌNH DẠNG DỰA TRÊN ĐỐI SÁNH ĐỒ
THỊ XƯƠNG
2.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Bài toán đối sánh đồ thị . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Biểu diễn đồ thị xương . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.1 Trục trung vị - Xương . . . . . . . . . . . . . . . . . . . . .
2.3.2 Biểu diễn đồ thị xương . . . . . . . . . . . . . . . . . . . . .
2.4 Độ đo tương tự hình dạng dựa trên đối sánh đồ thị xương . . . . .
2.4.1 Khoảng cách giữa các đỉnh sử dụng đường dẫn xương . . . .
2.4.2 Đối sánh đồ thị xương sử dụng cụm đỉnh cuối . . . . . . . .
2.4.3 Thực nghiệm đánh giá . . . . . . . . . . . . . . . . . . . . .
2.5 Tổng kết chương . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
8
12
22
25
28
29
33
34
37
38
39
42
46
46
50
52
52
54
64
69
3 TÍCH HỢP ĐẶC TRƯNG TRONG PHẢN HỒI LIÊN QUAN 72
3.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
iii
3.2
3.3
3.4
Độ đo mờ và tích phân Choquet . . . . . . . . .
3.2.1 Độ đo mờ (Fuzzy measures) . . . . . . .
3.2.2 Tích phân Choquet . . . . . . . . . . . .
Độ đo tương tự kết hợp nhiều đặc trưng . . . .
3.3.1 Phát biểu bài toán . . . . . . . . . . . .
3.3.2 Học trọng số liên quan của các đặc trưng
3.3.3 Thực nghiệm đánh giá . . . . . . . . . .
Tổng kết chương . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
75
75
77
78
78
82
85
92
4 HỌC CHỦ ĐỘNG SVM DỰA TRÊN PHẢN HỒI LIÊN QUAN 93
4.1 Học chủ động . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
4.2 Học chủ động SVM với phản hồi liên quan . . . . . . . . . . . . . . 94
4.2.1 Học chủ động SVM . . . . . . . . . . . . . . . . . . . . . . . 94
4.2.2 Các nghiên cứu liên quan . . . . . . . . . . . . . . . . . . . 97
4.3 Phản hồi liên quan trong CBIR . . . . . . . . . . . . . . . . . . . . 101
4.3.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . 101
4.3.2 Xây dựng hàm lựa chọn tập huấn luyện . . . . . . . . . . . . 101
4.3.3 Thực nghiệm đánh giá . . . . . . . . . . . . . . . . . . . . . 103
4.4 Tổng kết chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
KẾT LUẬN
108
Danh mục công trình của tác giả
111
Tài liệu tham khảo
112
iv
Danh sách hình vẽ
1.1
1.2
1.3
1.4
1.5
1.6
1.7
Kiến trúc chung của hệ thống CBIR . . . . . . . . . . . . . . . .
Không gian màu RGB . . . . . . . . . . . . . . . . . . . . . . . .
Không gian màu HSV . . . . . . . . . . . . . . . . . . . . . . . .
Ví dụ tính toán mẫu nhị phân [79]. Các điểm ảnh lân cận trên một
đường tròn với tâm là điểm ảnh khảo sát. Các điểm ảnh lân cận
không rơi chính xác vào lưới điểm ảnh được nội suy. . . . . . . . .
Recall và Precision cho các kết quả truy vấn . . . . . . . . . . . .
Ví dụ về khoảng cách ngữ nghĩa trong CBIR, cột (a) hai ảnh ngữ
nghĩa khác nhau nhưng có đặc trưng (biểu đồ màu) giống nhau,
cột (b) hai ảnh ngữ nghĩa giống nhau nhưng có đặc trưng (biểu đồ
màu) khác nhau . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Sơ đồ tổng quan của CBIR với phản hồi liên quan . . . . . . . . .
Hai đối tượng cùng một lớp nhưng có kiến trúc tô pô xương khác
nhau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Đối tượng (a) và (b) khác lớp nhưng có kiến trúc tô pô xương (c)
giống nhau. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Các láng giềng của điểm ảnh tại vị trí [i,j]: (a) 4-láng giềng và (b)
8-láng giềng. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4 Ảnh nhị phân với đường bao: (a) là ảnh gốc và (b) đường bao với
các điểm màu đen đậm. . . . . . . . . . . . . . . . . . . . . . . .
2.5 Ví dụ về xương. . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.6 Xương của ảnh bị nhiễu. Cột bên trái là ảnh đối tượng với dòng
trên là ảnh gốc, dòng dưới là ảnh bị nhiễu và cột bên phải là xương
tương ứng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.7 Xương thu được sau cắt tỉa với các ngưỡng khác nhau [4]. . . . .
2.8 Biểu diễn đồ thị xương. . . . . . . . . . . . . . . . . . . . . . . .
2.9 Sự không ổn định của các điểm xương giao nhau. . . . . . . . . .
2.10 Xây dựng siêu đồ thị xương. Bên trái là siêu đồ thị xương với các
đỉnh {v1 , ..., v7 } và các siêu cạnh {e1 , e2 , e3 }. Bên phải là ma trận
liên thuộc của siêu đồ thị xương . . . . . . . . . . . . . . . . . . .
2.11 Đối sánh bất biến tỷ lệ sử dụng độ tương tự bậc cao (δ = 3). Độ
tương tự bậc ba được tính toán bởi so sánh hai tam giác theo sin
của các góc tương ứng . . . . . . . . . . . . . . . . . . . . . . . .
. 9
. 14
. 15
. 19
. 26
. 30
. 32
2.1
v
. 40
. 40
. 46
. 47
. 48
.
.
.
.
48
49
50
52
. 55
. 57
2.12 Ví dụ xây dựng siêu đồ thị kết hợp [57]. (a) có hai đỉnh trên đồ thị
GP và 3 đỉnh trên đồ thị GQ . Có sáu mối tương quan giữa hai đồ
thị. (b) Siêu đồ thị kết hợp gồm sáu đỉnh tương ứng với sáu tương
quan. Có năm siêu cạnh được kết nối từ các tương quan tương ứng.
2.13 Một số ảnh mẫu trong tập dữ liệu Kimia99 . . . . . . . . . . . . . .
2.14 Một số ảnh mẫu trong tập dữ liệu Kimia216 . . . . . . . . . . . . .
2.15 Một số ảnh mẫu trong tập dữ liệu MPEG-7 . . . . . . . . . . . . .
2.16 Sự tương quan giữa hai hình dạng con ngựa, một con là sự biến đổi
từ con còn lại . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.17 Sự tương quan giữa hai hình dạng người với số chân khác nhau . .
2.18 Mối tương quan giữa hình dạng hai con voi có cấu trúc hình học
không giống nhau . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.19 Hiệu quả tra cứu của một số lớp riêng trên tập dữ liệu MPEG-7. . .
3.1
3.2
3.3
3.4
3.5
4.1
4.2
4.3
4.4
4.5
Kết hợp đặc trưng cho mục đích CBIR . . . . . . . . . . . . . . .
Hiệu quả tra cứu sử dụng các độ đo mờ khác nhau trên tập dữ liệu
Caltech101 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Hiệu quả tra cứu sử dụng các độ mờ khác nhau trên tập dữ liệu
Corel15K . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Hiệu quả tra cứu sử dụng các mô hình kết hợp khác nhau trên tập
dữ liệu Caltech101 . . . . . . . . . . . . . . . . . . . . . . . . . .
Hiệu quả tra cứu sử dụng các mô hình kết hợp khác nhau trên tập
dữ liệu Corel15K . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
64
65
65
66
66
67
70
. 74
. 89
. 90
. 91
. 91
Minh họa học chủ động SVM. Một bộ phân lớp tuyến tính được
tính toán để phân lớp dữ liệu liên quan(vòng trong rỗng) và không
liên quan (vòng tròn đặc). . . . . . . . . . . . . . . . . . . . . . . . 98
Kết quả tra cứu không có phản hồi . . . . . . . . . . . . . . . . . . 105
Kết quả tra cứu sau 4 vòng phản hồi . . . . . . . . . . . . . . . . . 106
Mối quan hệ giữa trung bình độ chính xác và tốp các ảnh trả về
của các vòng phản hồi: (a) Vòng phản hồi thứ nhất, (b) Vòng phản
hồi thứ hai, (c) Vòng phản hồi thứ ba, và (d) vòng phản hồi thứ bốn107
Mối quan hệ giữa trung bình độ chính xác và số lần lặp của tốp các
ảnh trả về: (a) Tốp 20 ảnh đầu tiên trả về, (b) Tốp 40 ảnh đầu tiên
trả về, (c) Tốp 60 ảnh đầu tiên trả về, và (d) tốp 80 ảnh đầu tiên
trả về . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
Danh sách bảng
2.1
2.2
2.3
3.1
3.2
3.3
Số lượng ảnh tra cứu đúng tại vị trí gần nhất với truy vấn trên tập
dữ liệu Kimia’s 99. Giá trị tốt nhất là 99. . . . . . . . . . . . . . . . 68
Số lượng ảnh tra cứu đúng tại vị trí gần nhất với truy vấn trên tập
dữ liệu Kimia’s 216. Giá trị tốt nhất là 216. . . . . . . . . . . . . . 68
Hiệu quả tra cứu trên một số lớp ảnh trên tập dữ liệu MPEG7 . . . 69
Độ đo tương tự kết hợp sử dụng
Độ đo tương tự kết hợp sử dụng
Các mô tả và các thuộc tính của
thí nghiệm . . . . . . . . . . . .
mô hình trong công thức (3–9) . . 79
tích phân Choquet . . . . . . . . . 82
các đặc trưng được sử dụng trong
. . . . . . . . . . . . . . . . . . . . 87
vii
Danh sách chữ viết tắt
Từ viết tắt
Diễn giải tiếng Anh
Diễn giải tiếng Việt
ARG
Attribute-Relational Graphs
Đồ thị quan hệ thuộc tính
AP
Average Precision
Độ chính xác trung bình
CBIR
Content-Based Image Retrieval
Tra cứu ảnh dựa trên nội dung
EM
Expectation–Maximization
Ước lượng EM
FSVM
Fuzzy Support Vector Machine
Máy véc tơ hỗ trợ mờ
GCM
Grid Color Moment
Mô men màu
GWT
Gabor Wavelets Texture
Biến đổi kết cấu dạng sóng
HSV
Hue Saturation Value
Không gian màu HSV
MAP
Mean Average Precision
ĐTrung bình của AP
MPEG-7
Moving
Picture
Experts Chuẩn MPEG-7
Group–7
MRBIR
Manifold Ranking Based Image Tra cứu ảnh dựa trên xếp hạng
Retrieval
đa tạp
MWR
Markov Random Walk
Bước ngẫu nhiên Markov
LBP
Local Binary Pattern
Mẫu nhị phân cục bộ
OSB
Optimal Subsequence Bijection
Chuỗi song ánh tối ưu
RGB
Red Green Blue
Không gian màu RGB
RF
Relevance Feedback
Phản hồi liên quan
RW
Random Walk
Bước ngẫu nhiên
RWR
Random Walk Restart
Bước ngẫu nhiên khởi động lại
SHG
Skeleton Hyper-Graph
Siêu đồ thị xương
SVM
Support Vector Machine
Phân lớp SVM
viii
MỞ ĐẦU
Trong xã hội hiện đại, việc tìm kiếm, truy cập các thông tin đã
trở thành nhu cầu không thể thiếu trong công việc của mọi người và
trong cuộc sống hàng ngày. Cùng với nhu cầu tìm kiếm văn bản, nhu
cầu tìm kiếm ảnh cũng nhận được nhiều quan tâm của người sử dụng.
Với số lượng ngày càng tăng của các hình ảnh kỹ thuật số trên Internet
và trong các thư viện kỹ thuật số, nhu cầu về các công cụ để quản lý
và khai thác hiệu quả cơ sở dữ liệu ảnh lớn đã phát triển nhanh chóng.
Việc phát triển các hệ thống tra cứu ảnh để tìm những ảnh quan tâm
trong trong số lượng lớn các ảnh được lưu trữ đã trở thành lĩnh vực
nghiên cứu nhận được nhiều sự quan tâm những năm gần đây.
Nói chung, có hai phương pháp tra cứu ảnh cơ bản, tra cứu ảnh
dựa trên từ khóa và tra cứu ảnh dựa trên nội dung. Tra cứu ảnh dựa
trên từ khóa nhằm mục đích tìm hình ảnh tương tự với ảnh truy vấn
theo các từ khóa hoặc chú thích. Phương pháp này đòi hỏi một lượng
lớn lao động thủ công để chú thích ảnh trong cơ sở dữ liệu thông qua
việc gán một số từ khóa có liên quan. Kết quả tra cứu dựa vào việc
đối sánh từ khóa được chú thích cho các ảnh trong cơ sở dữ liệu với
các từ khóa truy vấn dựa trên văn bản do người sử dụng đưa vào. Yêu
cầu cơ bản của hệ thống sử dụng phương pháp này là các ảnh phải
được chú thích trước khi chúng được thêm vào cơ sở dữ liệu lưu trữ.
Nếu không, chúng sẽ không bao giờ được tra cứu khi một truy vấn dựa
trên văn bản được yêu cầu. Tuy nhiên, để mô tả những ảnh với mức
độ một cách cụ thể và chi tiết thì cần phải có một hệ thống từ khoá
lớn và tinh vi. Một trở ngại khác của phương pháp này là cần phải có
1
nhân viên được đào tạo tốt không chỉ để chú thích từ khoá cho mỗi
ảnh mà còn phải lựa chọn những từ khoá thích hợp cho việc chú thích
này. Việc chú thích thủ công không những tiêu phí rất nhiều thời gian
công sức mà nó còn phụ thuộc nhiều vào sự cảm nhận chủ quan của
con người. Chẳng hạn như cùng nội dung ảnh nhưng với người dùng
khác nhau có thể cảm nhận nội dung trực quan của ảnh là khác nhau.
Sự cảm nhận chủ quan và sự chú thích không chính xác có thể dẫn
tới sự đối sánh không cân xứng trong quá trình tra cứu tiếp theo. Hơn
nữa, một hệ thống dựa trên từ khoá rất khó để thay đổi sau này. Vì
vậy, các nhà nghiên cứu đã xem xét đến kỹ thuật thực hiện chú thích
tự động cho ảnh số.
Các kỹ thuật chú thích tự động thường sử dụng các kỹ thuật học
máy thống kê để huấn luyện mô hình bằng cách sử dụng các ảnh đã
được chú thích đầy đủ. Với sự trợ giúp của các mô hình đã được huấn
luyện, hệ thống sau đó thực hiện chú thích tự động cho các ảnh khác.
Nhược điểm của kỹ thuật này là mô hình đào tạo phụ thuộc rất nhiều
vào chất lượng và số lượng của các ảnh được chú thích để huấn luyện.
Nếu các ảnh đã được chú thích không chính xác, không đầy đủ, phân
bố không đều, hoặc chất lượng chú thích thấp thì các mô hình thống
kê được huấn luyện sẽ không thể cung cấp chú thích chính xác cho các
ảnh khác. Hơn nữa, các mô hình thống kê được huấn luyện sẽ không
thể học khái niệm ngữ nghĩa của ảnh chính xác hơn nếu thông tin
phản hồi của con người về các từ khóa được chú thích tự động không
được cung cấp. Hệ thống thử nghiệm tra cứu ảnh kỹ thuật số đầu tiên
với các ảnh được chú thích tự động được các nhà nghiên cứu tại Viện
Công nghệ Massachusetts phát triển vào đầu những năm 1990 [83].
Từ đầu những năm 2000, lĩnh vực chú thích ảnh tự động đã trở thành
một chủ đề nghiên cứu phổ biến và thu hút ngày càng nhiều các nhà
2
nghiên cứu để xây dựng hệ thống tra cứu ảnh.
Song song với phương pháp tra cứu dựa trên kỹ thuật chú thích
tự động là sự ra đời của của phương pháp tra cứu ảnh dựa trên nội
dung (CBIR). Trong phương pháp này, ảnh được biểu diễn bởi các
đặc trưng thị giác với các kiểu đặc trưng cơ bản bao gồm màu sắc,
kết cấu và hình dạng. Các đặc trưng này được trích chọn một cách
tự động, do vậy, nội dung của ảnh được mô tả một cách nhất quán,
không phụ thuộc vào cảm nhận chủ quan của con người. Một số hệ
thống tra cứu ảnh dựa trên phương pháp CBIR đã được phát triển
như: QBIC [31] năm 1995, Virage [37] năm 1997 và NEC AMORE [72]
năm 1999. Đây là các hệ thống được phát triển sớm nhất cho mục
đích thương mại. Cũng trong khoảng thời gian này, một số hệ thống
CBIR khác đã phát triển cho mục đích nghiên cứu như MIT Photobook
[82], Columbia VisualSEEK và WebSEEK [98], UCSB Netra [64], và
Standford WBIIS [113]. Những ưu điểm của hệ thống CBIR đã được
các nhà nghiên cứu chỉ ra trong một số ứng dụng tiêu biểu [50]: kiến
trúc và thiết kế kỹ thuật, bộ sưu tập nghệ thuật, phòng chống tội
phạm, thông tin địa lý, sở hữu trí tuệ, điều trị nội khoa, quân sự, tìm
kiếm sản phẩm, . . .
Trong các hệ thống CBIR, các đặc trưng thị giác được trích chọn
từ mỗi ảnh và được lưu trữ trong cơ sở dữ liệu đặc trưng tương ứng.
Khi một ảnh truy vấn được yêu cầu, hệ thống trước tiên sẽ trích chọn
đặc trưng thị giác của ảnh truy vấn này. Sau đó một phương pháp
đối sánh sẽ được sử dụng để so sánh độ tương tự giữa các đặc trưng
thị giác của ảnh truy vấn với các đặc trưng thị giác của tất cả các
ảnh trong cơ sở dữ liệu. Những ảnh có giá trị độ tương tự cao được
sử dụng làm kết quả tra cứu trả về cho người dùng. Do vậy, để có
một hệ thống hiệu quả thì việc xây dựng độ đo tương tự phù hợp là
3
vấn đề cốt lõi. Tuy nhiên, xây dựng độ đo tương tự phù hợp là một
nhiệm vụ khó khăn do nghĩa của “tương tự” là khá mơ hồ. Những
người sử dụng khác nhau hoặc thậm chí cùng một người dùng nhưng
tại các thời điểm khác nhau có thể có các cảm nhận khác nhau về nội
dung của cùng một ảnh dựa trên cơ sở sự quan tâm của họ về đặc
trưng nào đó. Ngoài ra, có những ảnh có nội dung ngữ nghĩa tương tự
nhau nhưng lại rất khác nhau trong không gian đặc trưng trong khi có
những ảnh có nội dung ngữ nghĩa rất khác nhau nhưng tự nhau trong
không gian đặc trưng. Do đó, độ chính xác của hệ thống CBIR có thể
không được thỏa mãn do có khoảng cách giữa đặc trưng mức thấp và
các khái niệm ngữ nghĩa. Điều này đã thúc đẩy các nhà nghiên cứu
tìm các giải pháp để thu hẹp khoảng cách giữa đặc trưng mức thấp và
các khái niệm ngữ nghĩa trong các hệ thống CBIR. Đây cũng chính là
động lực cơ bản của luận án này.
Các phương pháp CBIR có thể được phân thành bốn loại chính
là các phương pháp dựa trên các đặc trưng toàn cục, các phương
pháp dựa trên đặc trưng mức vùng, các phương pháp dựa trên đặc
trưng mức đối tượng và các phương pháp dựa trên phản hồi liên quan
[22, 105, 122]. Các phương pháp dựa trên đặc trưng toàn cục thực
hiện trích chọn đặc trưng của toàn bộ ảnh mà không phân biệt các
vùng hoặc các đối tượng. Các chiến lược đối sánh khác nhau sẽ được
sử dụng để tìm các ảnh trong cơ sở dữ liệu mà liên quan nhất với ảnh
truy vấn dựa trên các đặc trưng toàn cục. Các phương pháp dựa trên
đặc trưng mức vùng thường phân ảnh thành các vùng và xử lý chúng
với các mức độ quan tâm khác nhau theo độ quan trọng của nội dung
trong mỗi vùng. Sau khi các đặc trưng thị giác của mỗi vùng được
trích chọn, các thuật toán đối sánh sẽ được áp dụng để tính toán độ
tương tự mức vùng giữa các vùng và sau đó kết hợp độ đo tương tự
4
mức vùng thành độ đo tương tự toàn bộ. So với các phương pháp dựa
trên đặc trưng mức vùng, các phương pháp dựa trên đặc trưng mức
đối tượng tập chung chi tiết hơn vào thông tin nội dung. Các phương
pháp này trước hết áp dụng phương pháp phân đoạn ảnh để thu được
các đối tượng độc lập trong ảnh, sau đó các đặc trưng của các đối
tượng sẽ được trích chọn và đối sánh để tính toán độ tương tự mức đối
tượng sử dụng để tìm các ảnh liên quan với ảnh truy vấn. Các phương
pháp dựa trên phản hồi liên quan sử dụng các phương pháp học trực
tuyến có giám sát để thu hẹp khoảng cách giữa đặc trưng mức thấp
và các khái niệm ngữ nghĩa. Các phương pháp này lặp đi lặp lại việc
thay đổi thông tin mô tả truy vấn theo phản hồi của người dùng trên
các kết quả tra cứu. Do đó, thông tin truy vấn được mô tả gần hơn
với mong muốn của người dùng và hiệu quả tra cứu sẽ được cải thiện.
Mục tiêu của luận án là cải tiến một số phương pháp CBIR để
nâng cao hiệu quả tra cứu ảnh dựa trên hiệu chỉnh độ đo tương tự và
phản hồi liên quan. Các mục tiêu cụ thể bao gồm tiến hành nghiên
cứu trên hai vấn đề cơ bản trong lĩnh vực CBIR đó là: 1) Xây dựng
độ đo tương tự, 2) Thu hẹp khoảng cách ngữ nghĩa dựa trên thông tin
phản hồi từ người dùng.
- Mục tiêu nghiên cứu đầu tiên là tiến hành nghiên cứu xây dựng
độ đo tương tự hiệu quả. Với mục tiêu này, luận án giải quyết hai
vấn đề cụ thể: 1) Cải tiến phương pháp tính toán độ đo tương tự
cho hình dạng dựa trên đối sánh xương của chúng và 2) xây dựng
mô hình phù hợp cho việc kết hợp nhiều đặc trưng để xây dựng
độ đo tương tự.
- Mục tiêu thứ hai là tiến hành nghiên cứu khai thác hiệu quả thông
tin phản hồi từ người dùng để điều chỉnh kết quả truy vấn. Trong
5
tra cứu ảnh với phản hồi liên quan, hệ thống cần phải thực hiện
một số vòng lặp. Trong mỗi vòng lặp, hệ thống sẽ trả lại một danh
sách các ảnh tương tự nhất với ảnh truy vấn dựa trên độ tương tự
giữa chúng. Sau đó, các ảnh này sẽ được đưa cho người sử dụng
gán nhãn liên quan hoặc không liên quan với ảnh truy vấn. Sử
dụng những ảnh đã được gán nhãn này như là những mẫu, những
kỹ thuật học sẽ được áp dụng để điều chỉnh độ đo tương tự sao
cho phù hợp với mong muốn của người dùng. Với mục tiêu này,
luận án sẽ tập trung giải quyết vấn đề làm thế nào để hệ thống
cho ra kết quả tốt sau ít vòng phản hồi nhất.
Những đóng góp của luận án này được tổng hợp như sau:
1) Cải tiến kỹ thuật đối sánh hình dạng đối tượng cải tiến dựa trên
đối sánh đồ thị xương nhằm tăng độ chính xác tìm kiếm ảnh theo
nội dung.
2) Đề xuất mô hình kết hợp nhiều đặc trưng trong việc xây dựng độ
đo tương tự để thu hẹp khoảng cách ngữ nghĩa trong tra cứu ảnh.
3) Đề xuất kỹ thuật lựa chọn dữ liệu trong học chủ động với phản
hồi liên quan để tăng độ chính xác tra cứu ảnh theo nội dung với
ít vòng phản hồi.
Luận án được trình bày như sau:
Chương 1. Trình bày một số vấn đề cơ bản trong tra cứu ảnh dựa
trên nội dung với phản hồi liên quan, trên cơ sở đó đưa ra một số
kết luận định hướng cho nghiên cứu tiếp theo.
Chương 2. Trình bày chi tiết về các thách thức trong đối sánh hình
dạng sử dụng xương, đề xuất phương pháp hiệu quả cho đối sánh
6
đồ thị xương thông qua việc nhúng thông tin cấu trúc vào bài
toán đối sánh đồ thị xương.
Chương 3. Trình bày mô hình tích hợp nhiều đặc trưng để xây dựng
độ đo tương tự cho tra cứu ảnh. Đề xuất mô hình kết hợp độ đo
tương tự của các đặc trưng dựa trên tích phân Choquet.
Chương 4. Giải quyết vấn đề thu hẹp khoảng cách ngữ nghĩa trong
CBIR với phản hồi liên quan dựa trên mô hình học chủ động.
Luận án đề xuất kỹ thuật xây dựng tập huấn luyện hiệu quả dựa
trên thông tin phản hồi từ người dùng để cải thiện hiệu năng tra
cứu.
Kết luận. Tổng kết các kết quả đã đạt được, những điểm tồn tại và
hướng nghiên cứu tiếp theo.
7
Chương 1
TRA CỨU ẢNH DỰA TRÊN
NỘI DUNG
Chương này giới thiệu tổng quan về CBIR và một số chủ đề liên
quan để cung cấp các kiến thức cơ sở cho các nghiên cứu của luận án
này. Các vấn đề nghiên cứu giải quyết trong luận án này có liên quan
chặt chẽ với hai chủ đề nghiên cứu trong các lĩnh vực CBIR, đó là tính
toán độ đo tương tự đặc trưng mức thấp và sử dụng thông tin phản
hồi liên quan từ người dùng. Phần 1.1 giới thiệu một số vấn đề cơ bản
trong CBIR. Phần 1.2 và 1.3 tổng hợp phân tích và đưa ra các vấn đề
để giải quyết trong luận án này. Và cuối cùng là tóm tắt nội dung của
chương.
1.1
Một số vấn đề cơ bản trong CBIR
Thuật ngữ tra cứu ảnh dựa trên nội dung đã được Kato sử dụng
đầu tiên vào năm 1992 để mô tả những thí nghiệm về lĩnh vực tra cứu
tự động những hình ảnh từ một cơ sở dữ liệu dựa trên đặc trưng hình
dạng và màu sắc. Từ đó, nó được sử dụng rộng rãi để mô tả quá trình
8
tra cứu những hình ảnh mong muốn từ một tập hợp lớn hình ảnh dựa
trên những đặc trưng thị giác như màu sắc, kết cấu và hình dạng, và
những đặc trưng này được trích chọn một cách tự động từ chính những
hình ảnh đó. Sơ đồ kiến trúc chung của hệ thống tra cứu ảnh dựa trên
nội dung được chỉ ra trong hình 1.1.
Được thực hiện offline
Ảnh truy
vấn
Các đặc trưng của
Cơ sở dữ liệu
Các đặc trưng
của truy vấn
Phân tích truy
vấn
Phản hồi của
người dùng
Kĩ thuật đối sánh
Người dùng
Kĩ thuật đánh chỉ mục
Tự động phản hồi
CƠ SỞ DỮ LIỆU ẢNH
Trích chọn đặc trưng
Ảnh được tra cứu
Hình 1.1: Kiến trúc chung của hệ thống CBIR
Trong một quy trình tra cứu thông thường, người dùng đầu tiên
đưa vào một ảnh mẫu để truy vấn hệ thống CBIR. Ảnh mẫu được sử
dụng để miêu tả những thông tin người dùng cần. Để trả lời truy vấn,
hệ thống CBIR tìm trong tập ảnh để đưa ra những ảnh tương tự với
ảnh mẫu. Trong ngữ cảnh của CBIR, độ tương tự được xác định dựa
trên các đặc trưng thị giác biểu diễn nội dung ảnh. Do đó, hệ thống
CBIR sẽ trích chọn các đặc trưng thị giác từ ảnh mẫu. Đo độ tương
tự được thực hiện dựa trên những đặc trưng thị giác của ảnh mẫu và
của mỗi ảnh trong CSDL ảnh. Việc trích chọn đặc trưng cho tập ảnh
9
thường được tiến hành trước. Cuối cùng, những ảnh trong CSDL ảnh
được xếp hạng theo sự tương đồng với ảnh truy vấn, và một số ảnh
được xếp hạng phía cao hơn sẽ được trả về trong kết quả tìm kiếm.
Như vậy, một hệ thống CBIR không chỉ liên quan tới các dạng khác
nhau của thông tin nguồn (ví dụ như văn bản, ảnh, video) mà còn liên
quan đến nhu cầu của người sử dụng. Về cơ bản nó phân tích cả nội
dung của nguồn thông tin cũng như truy vấn của người sử dụng và
sau đó đối sánh chúng để tìm ra những tiêu chí có liên quan. Một hệ
thống CBIR có các chức năng chính như sau:
- Phân tích và biểu diễn nội dung của thông tin nguồn: Thông tin
nguồn được phân tích và biểu diễn cho phù hợp với sự đối sánh
truy vấn của người sử dụng (không gian của thông tin nguồn
được chuyển đổi thành không gian đặc trưng với mục đích đối
sánh nhanh trong bước tiếp theo). Bước này thường là mất nhiều
thời gian để xử lý tuần tự các thông tin nguồn trong cơ sở dữ liệu.
Nó chỉ phải làm một lần và có thể thực hiện ngoại tuyến (offline).
- Phân tích và biểu diễn nội dung truy vấn của người dùng: Truy
vấn của người dùng được phân tích và biểu diễn thành các dạng
phù hợp cho việc đối sánh với cơ sở dữ liệu nguồn. Nhiệm vụ của
bước này giống với bước trước nhưng chỉ được áp dụng với những
ảnh truy vấn và được thực hiện trực tuyến (online).
- Đối sánh, tìm kiếm truy vấn với thông tin được lưu trữ trong cơ
sở dữ liệu. Bước này có thể thực hiện trực tuyến và thực hiện rất
nhanh. Các công nghệ đánh chỉ số được sử dụng để tăng tốc độ
xử lý đối sánh.
- Tạo ra sự điều chỉnh cần thiết trong hệ thống. Bước này thường
được thực hiện bằng cách đối chiếu và điều chỉnh các tham số
10
- Xem thêm -