ửa
ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN THỊ ĐỊNH
PHÁT TRIỂN MÔ HÌNH TÌM KIẾM ẢNH
DỰA TRÊN CẤU TRÚC KD-TREE
LUẬN ÁN TIẾN SĨ NGÀNH KHOA HỌC MÁY TÍNH
HUẾ, NĂM 2023
ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN THỊ ĐỊNH
PHÁT TRIỂN MÔ HÌNH TÌM KIẾM ẢNH
DỰA TRÊN CẤU TRÚC KD-TREE
NGÀNH: KHOA HỌC MÁY TÍNH
MÃ SỐ: 9480101
LUẬN ÁN TIẾN SĨ NGÀNH KHOA HỌC MÁY TÍNH
NGƯỜI HƯỚNG DẪN KHOA HỌC
PGS. TS. LÊ MẠNH THẠNH
TS. VĂN THẾ THÀNH
HUẾ, NĂM 2023
i
LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các nội dung tham
khảo từ các công trình khác đều được trích dẫn rõ ràng. Các kết quả viết chung với các
tác giả khác đều được sự đồng ý trước khi đưa vào luận án. Các kết quả của luận án là
trung thực và chưa được công bố trong các công trình khác ngoài các công trình của
tác giả.
Tác giả
Nguyễn Thị Định
ii
LỜI CÁM ƠN
Đầu tiên, tôi xin chân thành gửi lời cảm ơn đến Thầy PGS. TS. Lê Mạnh Thạnh
và Thầy TS. Văn Thế Thành đã tận tình hướng dẫn, động viên, giúp đỡ tôi trong suốt
quá trình nghiên cứu để hoàn thành luận án này. Bên cạnh đó, tôi còn nhận được sự hỗ
trợ đầy nhiệt tình của các Thầy, Cô Khoa Công nghệ Thông tin đã trang bị thêm kiến
thức, góp ý cho tôi thực hiện các chuyên đề và trao đổi các ý kiến quý báu cho bản
thảo của luận án. Tôi xin ghi nhận và cảm ơn sâu sắc đến sự giúp đỡ quý báu này.
Tôi xin chân thành cảm ơn đến Phòng Đào tạo Sau Đại học, Ban Giám hiệu của
Trường Đại học Khoa học, Đại học Huế đã tạo điều kiện thuận lợi cho tôi trong suốt
quá trình học tập, nghiên cứu và thực hiện luận án.
Tôi xin gửi lời cảm ơn đến Ban Giám hiệu Trường Đại học Công nghiệp Thực
phẩm Tp. HCM; Ban Chủ nhiệm Khoa Công nghệ Thông tin, các đồng nghiệp là cán
bộ, giảng viên Trường Đại học Công nghiệp Thực phẩm Tp. HCM đã luôn tạo điều
kiện, cổ vũ động viên tôi trong quá trình học tập và nghiên cứu. Tôi xin gửi lời cảm ơn
đến tất cả bạn bè và những người xung quanh đã chia sẻ, động viên trong những lúc
khó khăn.
Xin bày tỏ lòng biết ơn vô hạn đến gia đình thân yêu, Ba mẹ hai bên, chồng và
các con đã hỗ trợ, ủng hộ, động viên để con/em/mẹ yên tâm quá trình học tập, nghiên
cứu.
Tác giả
Nguyễn Thị Định
iii
MỤC LỤC
LỜI CAM ĐOAN ......................................................................................................... i
LỜI CÁM ƠN .............................................................................................................. ii
DANH MỤC KÝ HIỆU VÀ TỪ VIẾT TẮT ............................................................. v
DANH MỤC HÌNH ẢNH ....................................................................................... viii
DANH MỤC BẢNG BIỂU ......................................................................................... x
PHẦN MỞ ĐẦU .......................................................................................................... 1
CHƯƠNG 1. TỔNG QUAN VỀ TÌM KIẾM ẢNH VÀ CẤU TRÚC KD-TREE
............................................................................................................ 9
1.1. Giới thiệu ........................................................................................................................ 9
1.2. Tìm kiếm ảnh theo nội dung ......................................................................................... 11
1.2.1. Đc trưng hình ảnh và trích xuất véc-tơ đc trưng ................................................ 11
1.2.2. Độ tương tự giữa hai hình ảnh ............................................................................... 17
1.3. Tìm kiếm ảnh theo tiếp cận ngữ nghĩa ......................................................................... 18
1.3.1. Đc trưng ngữ nghĩa .............................................................................................. 18
1.3.2. Mối quan hệ ngữ nghĩa .......................................................................................... 20
1.3.3. Các phương pháp tìm kiếm ảnh theo tiếp cận ngữ nghĩa ...................................... 21
1.4. Tìm kiếm ảnh dựa trên cấu trúc KD-Tree..................................................................... 22
1.4.1. Cấu trúc KD-Tree cho tìm kiếm ảnh ..................................................................... 22
1.4.2. Phân lớp hình ảnh dựa trên cấu trúc KD-Tree ....................................................... 23
1.4.3. Phân lớp mối quan hệ ngữ nghĩa dựa trên cấu trúc KD-Tree ................................ 24
1.4.4. Tìm kiếm ảnh dựa trên cấu trúc KD-Tree ............................................................. 24
1.5. Phương pháp thực nghiệm và đánh giá ......................................................................... 26
1.5.1. Môi trường và dữ liệu thực nghiệm ....................................................................... 26
1.5.2. Các đại lượng đánh giá hiệu suất ........................................................................... 27
1.6. Tổng kết chương ........................................................................................................... 29
CHƯƠNG 2. TÌM KIẾM ẢNH DỰA TRÊN CẤU TRÚC KD-TREE ............ 30
2.1. Giới thiệu ...................................................................................................................... 30
2.2. Cấu trúc KD-Tree đa nhánh cân bằng .......................................................................... 31
2.2.1. Xây dựng cấu trúc KD-Tree .................................................................................. 32
2.2.2. Thuật toán xây dựng cấu trúc KD-Tree ................................................................. 36
2.2.3. Quá trình gán nhãn nút lá ...................................................................................... 37
2.2.4. Huấn luyện trọng số trên cấu trúc KD-Tree .......................................................... 38
2.2.5. Tìm kiếm trên cấu trúc KD-Tree ........................................................................... 41
2.2.6. Hệ tìm kiếm ảnh dựa trên cấu trúc KD-Tree ......................................................... 41
2.3. Cấu trúc iKD_Tree ....................................................................................................... 46