Luận án Tiến sĩ Khoa học máy tính: Phát triển mô hình tìm kiếm ảnh dựa trên cấu trúc KD-Tree

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:139

Thêm vào BST

Báo xấu

15
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận án Tiến sĩ Khoa học máy tính "Phát triển mô hình tìm kiếm ảnh dựa trên cấu trúc KD-Tree" trình bày các nội dung chính sau: Nghiên cứu cấu trúc dữ liệu đa chiều KD-Tree; xây dựng các thuật toán thao tác trên KD-Tree tổ chức lưu trữ véc-tơ đặc trưng hình ảnh; hát triển mô hình tìm kiếm ảnh bằng cách kết hợp các phương pháp học có giám sát, bán giám sát và rừng ngẫu nhiên để tạo ra mô hình phân lớp hình ảnh, gom cụm dữ liệu dựa trên cấu trúc KD-Tree.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án Tiến sĩ Khoa học máy tính: Phát triển mô hình tìm kiếm ảnh dựa trên cấu trúc KD-Tree

ĐẠI HỌC HUẾ ửa 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
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 i
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 ii
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 iii
2.3.1. Mô tả cấu trúc iKD_Tree ....................................................................................... 46 2.3.2. Xây dựng cấu trúc iKD_Tree ................................................................................ 47 2.3.3. Hệ tìm kiếm ảnh dựa trên cấu trúc iKD_Tree ....................................................... 50 2.4. Cấu trúc KD-Tree lồng nhau ........................................................................................ 54 2.4.1. Mô tả cấu trúc KD-Tree lồng nhau ........................................................................ 54 2.4.2. Xây dựng cấu trúc KD-Tree lồng nhau ................................................................. 55 2.4.3. Hệ tìm kiếm ảnh dựa trên cấu trúc KD-Tree lồng nhau ........................................ 56 2.5. Đánh giá các hệ tìm kiếm ảnh....................................................................................... 63 2.6. Tổng kết chương ........................................................................................................... 66 CHƯƠNG 3. PHÁT TRIỂN CẤU TRÚC KD-TREE THEO TIẾP CẬN NGỮ NGHĨA .......................................................................................................... 67 3.1. Giới thiệu ...................................................................................................................... 67 3.1.1. Xây dựng cấu trúc RF KD-Tree ............................................................................ 68 3.1.2. Huấn luyện RF KD-Tree ....................................................................................... 69 3.2. Ontology cho tìm kiếm ảnh theo tiếp cận ngữ nghĩa .................................................... 70 3.2.1. Cấu trúc Re KD-Tree ............................................................................................. 70 3.2.2. Phân lớp mối quan hệ các đối tượng bằng Re KD-Tree ........................................ 73 3.2.3. Mô tả cấu trúc và xây dựng Ontology ................................................................... 73 3.2.4. Phân cấp và bổ sung dữ liệu vào Ontology ........................................................... 77 3.2.5. Tìm kiếm trên Ontology ........................................................................................ 79 3.3. Hệ tìm kiếm ảnh dựa trên Re KD-Tree và Ontology .................................................... 81 3.3.1. Mô hình tìm kiếm ảnh dựa trên Re KD-Tree và Ontology.................................... 81 3.3.2. Thực nghiệm và đánh giá ...................................................................................... 83 3.4. Hệ tìm kiếm ảnh dựa trên RF KD-Tree ........................................................................ 85 3.4.1. Mô hình tìm kiếm ảnh dựa trên RF KD-Tree ........................................................ 85 3.4.2. Thực nghiệm và đánh giá ...................................................................................... 87 3.5. Hệ tìm kiếm ảnh dựa trên KD-Tree và Ontology ......................................................... 89 3.5.1. Mô hình tìm kiếm ảnh dựa trên KD-Tree và Ontology ......................................... 89 3.5.2. Thực nghiệm và đánh giá ...................................................................................... 91 3.6. Tổng kết chương ........................................................................................................... 97 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ............................................................... 98 TÀI LIỆU THAM KHẢO ...................................................................................... 101 PHỤ LỤC ................................................................................................................. 108 iv
DANH MỤC KÝ HIỆU VÀ TỪ VIẾT TẮT Ký hiệu Diễn giải tiếng Anh Diễn giải tiếng Việt viết tắt BST Binary Search Tree Cây tìm kiếm nhị phân CBIR Content-Based Image Retrieval Tìm kiếm ảnh theo nội dung CDF Centroid Distance Function Hàm tính khoảng cách trọng tâm CEO Create Extended Ontology Hàm xây dựng Ontology mở rộng CiKDT Create iKD_Tree Thuật toán tạo iKD_Tree CKDT Create KD-Tree Thuật toán tạo KD-Tree CLiKD Classification on iKD_Tree Hàm phân lớp ảnh trên iKD_Tree CLRKD Classification Relationship Hàm phân lớp mối quan hệ bằng Re KD- using Relationship KD-Tree Tree CNKDT Create Nested KD-Tree Thuật toán tạo KD-Tree lồng nhau CNN Convolutional Neural Network Mạng nơ-ron tích chập CRFKD Create Random Forest KD- Thuật toán tạo RF KD-Tree Tree CSQ Create SPARQL Query Hàm tạo câu truy vấn SPARQL DCD Dominant Color Descriptor Bộ mô tả màu chủ đạo DCL Deep Convolutional Learning Mạng tích chập học sâu DNN Deep Neural Network Mạng nơ-ron học sâu DoG Difference of Gaussian Đạo hàm Gaussian GLCM Gray-level Co-occurrence Ma trận đồng xuất hiện mức xám Matrix HOG Histograms of Oriented Biểu đồ định hướng Gradients Gradients iKD_Tree Improvement k-Dimensional Cấu trúc KD-Tree cải tiến Tree IR Image Retrieval Tìm kiếm ảnh KD-Tree k-Dimensional Tree Cấu trúc cây đa chiều KG Knownledge Graph Đồ thị tri thức kMiKDT K-Means on iKD_Tree Hàm tích hợp K-Means trên iKD_Tree v
k-NN k - Nearest Neighbors Thuật toán tìm kiếm theo k láng giềng gần nhất LoG Laplace of Gaussian Phép biến đổi Laplace Gaussian MAP Mean Average Precision Độ chính xác trung bình MRI Magnetic Resonance Imaging Ảnh y khoa MRI NN Nearest Neighbors Láng giềng gần nhất R-CNN Region-based Convolutional Mạng Nơ-ron tích chập dựa trên vùng Neural Networks đối tượng Re KD-Tree Relationship k-Dimensional Cấu trúc KD-Tree phân lớp mối quan hệ Tree RF Relevance Feedback Phương pháp phản hồi liên quan RF KD-Tree Random Forest KD-Tree Cấu trúc rừng ngẫu nhiên KD-Tree RNN Range Nearest Neighbors Kỹ thuật tìm kiếm láng giềng theo vùng ROC Receiver Operating Đồ thị đặc tính Characteristic SB-iKDT Semantic-based Image Hệ tìm kiếm ảnh sử dụng iKD_Tree Retrieval using iKD_Tree SBIR Semantic-Based Image Tìm kiếm ảnh theo ngữ nghĩa Retrieval SB-KDT Semantic-based Image Hệ tìm kiếm ảnh sử dụng KD-Tree Retrieval using KD-Tree SB-NKDT Semantic-based Image Hệ tìm kiếm ảnh sử dụng KD-Tree lồng Retrieval using Nested KD- nhau Tree SG Scene Graph Đồ thị ngữ cảnh SIFT Scale Invariant Features Đặc trưng bất biến SIFT Transform SiKDT Search on iKD_Tree Thuật toán tìm kiếm ảnh trên iKD_Tree SKDO Search on KD-Tree and Thuật toán tìm kiếm trên KD-Tree và Ontology Ontology SKDT Search on KD-Tree Hàm tìm kiếm trên KD-Tree SL2L Set Label To Leaf Hàm gán nhãn nút lá SNKDT Search on Nested KD-Tree Thuật toán tìm kiếm trên KD-Tree lồng nhau vi
SO-KDT Semantic-based Image Hệ tìm kiếm ảnh theo ngữ nghĩa sử dụng Retrieval using KD-Tree and KD-Tree và Ontology Ontology SR-KDF Semantic-based Image Hệ tìm kiếm ảnh sử dụng RF KD-Tree Retrieval using RF KD-Tree SR-KDT Semantic-based Image Hệ tìm kiếm ảnh theo ngữ nghĩa sử dụng Retrieval using Relationship Re KD-Tree KD-Tree SRKO Semantic-based Image Thuật toán tìm kiếm ảnh sử dụng Re Retrieval using KD-Tree and KD-Tree và Ontology Ontology SRRE Semantic-based Image Thuật toán tìm kiếm ảnh sử dụng Re Retrieval using Relationship KD-Tree KD-Tree SRRF Semantic-based Image Thuật toán tìm kiếm ảnh sử dụng RF Retrieval using Random Forest KD-Tree KD-Tree SVM Support Vector Machine Máy véc-tơ hỗ trợ TBIR Text-Based Image Retrieval Tìm kiếm ảnh theo từ khóa TVKD Training Véc-tơ on KD-Tree Thuật toán huấn luyện véc-tơ trọng số trên KD-Tree TWRF Train Weight Random Forest Hàm huấn luyện trọng số trên RF KD- KD-Tree Tree WWW Word Wide Web Mạng toàn cầu vii
DANH MỤC HÌNH ẢNH Hình 1.1. Minh họa trích xuất véc-tơ đặc trưng 81 chiều [CT1] ................................ 15 Hình 1.2. Minh họa trích xuất véc-tơ đặc trưng 189, 225 và 513 chiều ..................... 17 Hình 1.3. Mô tả đặc trưng ngữ nghĩa của hình ảnh [48] ............................................. 19 Hình 1.4. Xác định mối quan hệ không gian giữa các đối tượng bằng SG [46] ......... 20 Hình 1.5. Xác định mối quan hệ không gian giữa các đối tượng bằng KD-Tree ....... 21 Hình 1.6. Mô hình tìm kiếm ảnh theo nội dung dựa trên cấu trúc KD-Tree............... 25 Hình 1.7. Mô hình tìm kiếm ảnh theo tiếp cận ngữ nghĩa dựa trên KD-Tree ............. 25 Hình 2.1. Mô tả các thành phần nút gốc, nút trong và nút lá trên KD-Tree ............... 33 Hình 2.2. Minh họa quá trình tạo nhánh con tại 𝐍𝐨𝐝𝐞𝐢.............................................. 34 Hình 2.3. Cấu trúc KD-Tree đa nhánh, cân bằng ........................................................ 35 Hình 2.4. Mô hình xây dựng và huấn luyện KD-Tree theo từng 𝐄𝐩𝐨𝐜𝐡 dữ liệu ....... 39 Hình 2.5. Minh họa tập véc-tơ phân lớp trên KD-Tree cho bộ ảnh COREL ...... 40 Hình 2.6. Mô hình tìm kiếm ảnh dựa trên KD-Tree (SB-KDT) ........................... 42 Hình 2.7. Minh họa quá trình xây dựng tập từ thị giác ............................................... 43 Hình 2.8. Minh họa câu truy vấn SPARQL ................................................................ 44 Hình 2.9. Hệ tìm kiếm ảnh SB-KDT ........................................................................... 44 Hình 2.10. Kết quả tập ảnh tương tự của ảnh COREL101.jpg hệ SB-KDT ............... 45 Hình 2.11. Minh họa cấu trúc iKD_Tree .................................................................... 47 Hình 2.12. Minh họa thuật toán K-Means trên iKD_Tree .......................................... 47 Hình 2.13. Mô hình tìm kiếm ảnh dựa trên cấu trúc iKDTree [CT3] ......................... 50 Hình 2.14. Hệ tìm kiếm ảnh SB-iKDT........................................................................ 52 Hình 2.15. Kết quả tập ảnh tương tự với ảnh 52011.jpg (Wang) hệ SB-iKDT .......... 52 Hình 2.16. Minh họa cấu trúc KD-Tree lồng nhau [CT4] .......................................... 54 Hình 2.17. Mô hình tìm kiếm ảnh dựa trên KD-Tree lồng nhau (SB-NKDT) [CT4] . 56 Hình 2.18. Hệ tìm kiếm ảnh SB-NKDT ...................................................................... 58 Hình 2.19. Tập ảnh tương tự với ảnh 500.jpg [20] hệ SB-NKDT .............................. 58 Hình 2.20. Biểu đồ so sánh precision-recall, đường cong ROC bộ ảnh COREL của hệ tìm kiếm ảnh SB-KDT và SB-NKDT ......................................................................... 61 Hình 2.21. Biểu đồ so sánh precision-recall, đường cong ROC bộ ảnh Wang của hệ tìm kiếm ảnh SB-KDT, SB-iKDT và SB-NKDT .............................................................. 61 Hình 2.22. Biểu đồ so sánh precision-recall, đường cong ROC bộ ảnh Caltech-101 của hệ tìm kiếm ảnh SB-KDT, SB-iKDTvà SB-NKDT .................................................... 62 viii
Hình 2.23. Biểu đồ so sánh precision-recall, đường cong ROC bộ ảnh Caltech-256 của hệ tìm kiếm ảnh SB-KDT và SB-iKDT ...................................................................... 62 Hình 3.1. Mô tả cấu trúc RF KD-Tree ........................................................................ 68 Hình 3.2. Mô tả cấu trúc Re KD-Tree ......................................................................... 72 Hình 3.3. Minh họa ảnh đối tượng trích xuất từ ảnh gốc 1001773457.jpg (Flickr) .... 72 Hình 3.4. Minh họa cấu trúc Ontology........................................................................ 74 Hình 3.5. Cách tổ chức dữ liệu phân cấp lớp và lớp con trong bộ ảnh MS-COCO .... 75 Hình 3.6. Cấu trúc Class, SuperClass được bổ sung vào Ontology ............................ 75 Hình 3.7. Cấu trúc ảnh đối tượng sau khi phân đoạn và phân lớp ...................... 76 Hình 3.8. Minh họa cấu trúc ảnh đối tượng theo phân lớp ......................................... 76 Hình 3.9. Mô tả các thành phần ảnh đối tượng trên bộ ảnh Flickr ............................. 76 Hình 3.10. Cấu trúc Class, SuperClass trên bộ ảnh MS-COCO ................................. 77 Hình 3.11. Mô hình bổ sung dữ liệu vào Ontology tập ảnh đa đối tượng .................. 78 Hình 3.12. Minh họa Ontology bộ ảnh MS-COCO dạng N3...................................... 78 Hình 3.13. Minh họa câu truy vấn SPARQL từ ảnh đối tượng và mối quan hệ ......... 79 Hình 3.14. Tìm kiếm cho các ảnh đối tượng thuộc một cụm ................................ 80 Hình 3.15. Tìm kiếm cho các ảnh đối tượng thuộc nhiều cụm ................................... 80 Hình 3.16. Một kết quả tìm kiếm trên Ontology theo ID ảnh ..................................... 81 Hình 3.17. Mô hình tìm kiếm ảnh dựa trên Re KD-Tree và Ontology (SR-KDT) ..... 82 Hình 3.18. Hệ tìm kiếm ảnh SR-KDT ......................................................................... 83 Hình 3.19. Kết quả tập ảnh tương tự hệ SR-KDT (000000183675.jpg, MS-COCO). 84 Hình 3.20. Mô hình tìm kiếm ảnh dựa trên RF KD-Tree (SR-KDF) .......................... 86 Hình 3.21. Hệ tìm kiếm ảnh SR-KDF ......................................................................... 87 Hình 3.22. Kết quả tập ảnh tương tự hệ SR-KDF (000000100510.jpg, MS-COCO) . 88 Hình 3.23. Mô hình tìm kiếm ảnh dựa trên KD-Tree và Ontology (SO-KDT) .......... 90 Hình 3.24. Hệ tìm kiếm ảnh SO-KDT ........................................................................ 92 Hình 3.25. Kết quả tập ảnh tương tự hệ SO-KDT (11205420.jpg, Flickr) ................. 92 Hình 3.26. Biểu đồ so sánh precision-recall, đường cong ROC bộ ảnh MS-COCO của hệ tìm kiếm ảnh SR-KDT, SR-KDF và SO-KDT ....................................................... 94 Hình 3.27. Biểu đồ so sánh precision-recall, đường cong ROC bộ ảnh Flickr của hệ tìm kiếm ảnh SR-KDT, SR-KDF và SO-KDT .................................................................. 94 ix
DANH MỤC BẢNG BIỂU Bảng 1.1. Các giá trị véc-tơ đặc trưng hình ảnh (81 chiều) ........................................ 15 Bảng 1.2. Các giá trị véc-tơ đặc trưng được trích xuất (225 và 513 chiều) ................ 16 Bảng 1.3. Mô tả các bộ dữ liệu ảnh thực nghiệm ........................................................ 27 Bảng 1.4. Mô tả bộ ảnh đa đối tượng .......................................................................... 27 Bảng 2.1. Chi phí huấn luyện KD-Tree trên các bộ ảnh thực nghiệm ........................ 41 Bảng 2.2. Kết quả tìm kiếm ảnh tương tự hệ SB-KDT [CT2] .................................... 45 Bảng 2.3. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh COREL (SB-KDT) ......... 45 Bảng 2.4. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Wang (SB-KDT) ............ 45 Bảng 2.5. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Caltech-101 (SB-KDT) .. 46 Bảng 2.6. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Caltech-256 (SB-KDT) .. 46 Bảng 2.7. Kết quả tìm kiếm ảnh của hệ SB-iKDT ...................................................... 53 Bảng 2.8. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Wang (SB-iKDT) ........... 53 Bảng 2.9. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Caltech-101 (SB-iKDT) . 53 Bảng 2.10. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Caltech-256 (SB-iKDT)53 Bảng 2.11. Điều kiện để nút lá phát triển thành SubTree ........................................... 55 Bảng 2.12. Kết quả tìm kiếm ảnh của hệ SB-NKDT .................................................. 59 Bảng 2.13. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh COREL (SB-NKDT) .... 59 Bảng 2.14. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Wang (SB-NKDT)........ 59 Bảng 2.15. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Caltech-101 (SB-NKDT) ..................................................................................................................................... 60 Bảng 2.16. So sánh độ chính xác trung bình giữa các cải tiến cấu trúc KD-Tree ...... 63 Bảng 2.17. So sánh thời gian tìm kiếm trung bình (ms) giữa các cải tiến KD-Tree ... 63 Bảng 2.18. So sánh các phương pháp tìm kiếm ảnh sử dụng KD-Tree với những đề xuất trong luận án ........................................................................................................ 65 Bảng 3.1. Kết quả tìm kiếm ảnh hệ SR-KDT [CT5] ................................................... 84 Bảng 3.2. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh MS-COCO (SR-KDT) .... 84 Bảng 3.3. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Flickr (SR-KDT) ............ 85 Bảng 3.4. Kết quả thực nghiệm hệ tìm kiếm ảnh SR-KDF ......................................... 88 Bảng 3.5. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh MS-COCO (SR-KDF) .... 88 Bảng 3.6. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Flickr (SR-KDF) ............. 89 Bảng 3.7. Kết quả thực nghiệm hệ tìm kiếm ảnh SO-KDT ........................................ 91 x
Bảng 3.8. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh MS-COCO (SO-KDT).... 92 Bảng 3.9. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Flickr (SO-KDT) ............ 93 Bảng 3.10. So sánh kết quả giữa các hệ tìm kiếm ảnh đề xuất .................................. 93 Bảng 3.11. So sánh độ chính xác tìm kiếm ảnh giữa các phương pháp đề xuất ........ 95 Bảng 3.12. So sánh các phương pháp tìm kiếm ảnh theo ngữ nghĩa với những đề xuất trong luận án ................................................................................................................ 96 xi
PHẦN MỞ ĐẦU 1. Tính cấp thiết của luận án Việc số hóa dữ liệu đa phương tiện đã tạo ra các dữ liệu lớn là thách thức cho bài toán tìm kiếm ảnh về các yêu cầu khả năng lưu trữ, độ chính xác và thời gian tìm kiếm. Điều đó đã thúc đẩy sự ra đời của nhiều hệ tìm kiếm ảnh được thực hiện theo nhiều phương pháp khác nhau nhằm nâng cao độ chính xác, thời gian tìm kiếm ổn định đáp ứng nhu cầu người dùng [75], [77]. Sự đa dạng của ảnh số về thể loại cũng là một thách thức cho bài toán tìm kiếm ảnh. Vì vậy, một số cấu trúc được đề xuất như KD-Tree [84], S-Tree [38], C-Tree [52], v.v. đáp ứng nhu cầu đa dạng của dữ liệu là cấp thiết cho bài toán tìm kiếm ảnh. Trong luận án, cấu trúc dữ liệu đa chiều KD-Tree được nghiên cứu và xây dựng cho bài toán tìm kiếm ảnh đã mang lại kết quả khả quan về khả năng lưu trữ khi dữ liệu tăng trưởng theo thời gian, phù hợp với dữ liệu véc-tơ đặc trưng hình ảnh đa chiều và thời gian tìm kiếm ổn định. Quá trình đưa các kỹ thuật học máy vào cấu trúc KD- Tree đã mang lại hiệu quả tìm kiếm ảnh cao hơn so với một số phương pháp khác. 2. Tổng quan tình hình nghiên cứu Bài toán tìm kiếm ảnh đã được nghiên cứu và thực hiện bởi nhiều phương pháp khác nhau nhằm nâng cao độ chính xác đáp ứng nhu cầu người dùng. Một số công trình tìm kiếm ảnh được khảo sát trong luận án, bao gồm: Tìm kiếm ảnh sử dụng các kỹ thuật phân lớp và phân cụm Erwin và cộng sự [26] đề xuất hệ thống nhận dạng trái cây qua hình ảnh bằng cách kết hợp các thuật toán K-Means, k-NN để thực hiện phân lớp và gom cụm đặc trưng hình ảnh trước khi nhận diện đối tượng. Kết quả thực nghiệm phân lớp hình ảnh đạt được độ chính xác 92,5% cho ảnh đơn đối tượng và 90% cho ảnh đa đối tượng. Tuy nhiên, hệ thống chỉ nhận diện trên các bộ ảnh về trái cây; thuật toán K- Means được áp dụng theo phương pháp cập nhật tâm cụm khi dữ liệu thay đổi, chưa xử lý trường hợp số lượng láng giềng có số phân lớp bằng nhau trong thuật toán k- NN. Vì vậy, Shichao Kan và cộng sự [34] đã đề xuất phương pháp học có giám sát dùng thuật toán k-NN cải tiến để phân lớp hình ảnh, quá trình gán lại nhãn cho các 1
ảnh huấn luyện được đề xuất nhằm thiết lập mối quan hệ giữa các nhãn lớp. Kết quả thực nghiệm của hệ thống dùng phương pháp học có giám sát để tạo chỉ mục cho kết quả tốt hơn mô hình sử dụng phương pháp học không giám sát trên cùng bộ dữ liệu thử nghiệm. Sau đó, Shuang Jia và cộng sự [33] sử dụng thuật toán gom cụm K- Means để thực hiện tìm kiếm ảnh. Mỗi hình ảnh đầu vào được trích xuất đặc trưng và tính độ tương tự dựa trên đặc trưng túi từ để tìm tập ảnh tương tự. Trong phương pháp này, các túi từ là độc lập và chưa phân lớp được theo nội dung của mỗi ảnh đầu vào. Kỹ thuật học sâu được ứng dụng cho nhiều công trình tìm kiếm ảnh, cụ thể là: R. Rani và cộng sự [64] đã xây dựng mô hình tìm kiếm ảnh sử dụng kỹ thuật học sâu Deep Learning. Hình ảnh được trích xuất đặc trưng và phân lớp đối tượng bằng kỹ thuật DBN (Deep Belief Network). Phương pháp đề xuất được thực nghiệm thông qua mô phỏng so sánh, kết quả cho thấy độ lệch dương rất lớn với hiệu suất của hệ thống. Bên cạnh đó, Maria Tzelepi và cộng sự (2018) [70] đã tiếp cận kỹ thuật DCL cho bài toán tìm kiếm ảnh. Mô hình CNN được sử dụng để huấn luyện lại cho tập dữ liệu thực nghiệm. Kết quả huấn luyện trên các bộ dữ liệu độc lập đã chứng minh tính hiệu quả của phương pháp đề xuất là khá tốt. Pouria Sadeghi-Tehran [63] đã thực hiện một phương pháp đánh chỉ mục cho cơ sở dữ liệu tìm kiếm dựa vào kỹ thuật Deep Learning và cấu trúc cây phân cấp lồng nhau. Ngoài ra, tác giả đưa ra sơ đồ tối ưu hóa tìm kiếm dựa vào cấu trúc phân cấp lồng nhau và độ đo tương tự [63]. Tìm kiếm ảnh dựa trên cấu trúc cây Một số cấu trúc cây sử dụng cho bài toán tìm kiếm ảnh với hiệu suất cao như C- Tree [52], S-Tree [38], KD-Tree [30], [59]. Trong đó, cấu trúc KD-Tree được đề xuất ở một số công trình như: Wenfeng Hou và cộng sự (2018) [30] thực hiện phân lớp dữ liệu bằng thuật toán láng giềng k-NN trên cây KD-Tree. Để cải thiện những nhược điểm của thuật toán k-NN, tác giả đã kết hợp k-NN và cấu trúc dữ liệu KD-Tree nhằm giảm thời gian tìm kiếm và nâng cao độ chính xác tìm kiếm gọi là cấu trúc kNN- KDTree. Kết quả thực nghiệm trên 11 bộ dữ liệu ảnh cho thấy sự kết hợp giữa k-NN và KD-Tree đã mang lại hiệu suất cao hơn so với việc dùng kỹ thuật k-NN đơn lẻ. Parikshit Ram và cộng sự [59] sử dụng kỹ thuật tìm kiếm láng giềng k-NN dựa trên cấu trúc KD-Tree. Việc kết hợp này nhằm cải tiến hiệu suất tìm kiếm bằng cách 2
xây dựng cây phân vùng không gian ngẫu nhiên để thực hiện các lược đồ tìm kiếm theo cấu trúc KD-Tree. Yewang Chen và cộng sự [16] đã sử dụng hai kỹ thuật tìm kiếm láng giềng RNN (Range Nearest Neighbors) và NN (Nearest Neighbors) dựa trên cây KD-Tree. Trong đó, kỹ thuật RNN nhằm giảm các tính toán khoảng cách không cần thiết bằng cách kiểm tra vị trí của đối tượng đang xét nằm bên trong hay bên ngoài vùng lân cận của điểm cần tìm. Kỹ thuật NN được sử dụng để giảm các nút truy cập dư thừa bằng cách lưu chỉ số truy cập các điểm láng giềng. Thực nghiệm chứng minh cho việc kết hợp các thuật toán tìm kiếm láng giềng RNN, NN và k-NN trên cấu trúc KD-Tree hiệu quả. Fengquan Zhang [83] và cộng sự đã xây dựng cấu trúc Vocabulary-KDTree nhằm thực hiện bài toán đối sánh hình ảnh. Cấu trúc này được chia thành hai nhóm: (1) nhóm chứa các đặc trưng hình ảnh; (2) nhóm các nút lá cùng với việc điều chỉnh các trọng số liên quan quá trình huấn luyện để xây dựng cấu trúc Vocabulary-KDTree. Reid Pinkham và cộng sự (2020) [54] đã thực hiện một phương pháp tối ưu bộ nhớ và tăng tốc độ tìm kiếm trên KD-Tree. Cấu trúc KD-Tree được xây dựng gồm các bước: (1) dữ liệu được lưu vào bộ nhớ đệm nhằm tạo điều kiện tìm kiếm nhanh; (2) quá trình đọc ghi trên bộ nhớ đệm được thêm vào để thực hiện truy cập ngẫu nhiên để chuyển thành truy cập tuần tự; (3) xây dựng cấu trúc KD-Tree và tìm kiếm được thực hiện xen kẽ với các luồng truy cập dư thừa, băng thông được tối ưu hóa hỗ trợ quá trình tìm kiếm. Mahesha D. M và cộng sự [43] thực hiện bài toán tìm kiếm ảnh theo nội dung sử dụng cấu trúc Distributed KD-Tree là cấu trúc đa nhánh, cân bằng trên cơ sở phát triển KD-Tree nhị phân. Distributed KD-tree được xây dựng trên cơ sở phân tách nút gốc thành các nhánh con và đệ quy đến các tầng kế tiếp. Quá trình tìm kiếm trên Distributed KD-tree được thực hiện từ nút gốc đến nút lá dựa vào 𝑘 láng giềng của phần tử tìm kiếm để xác định nút lá chứa tập ảnh tương tự với ảnh đầu vào. Bên cạnh đó, dữ liệu lưu trữ trên Distributed KD-tree theo phương pháp lập chỉ mục nên quá trình tìm kiếm nhanh và hiệu quả. Tìm kiếm ảnh theo tiếp cận ngữ nghĩa 3
Tìm kiếm ảnh theo tiếp cận ngữ nghĩa sử dụng ontology là một trong những hướng tiếp cận mang lại nhiều kết quả khả quan trong thập niên vừa qua, một số công trình tiêu biểu như: Manzoor và công sự [44] đã đề xuất một phương pháp tìm kiếm ảnh theo ngữ nghĩa dựa trên ontology để truy xuất ngữ nghĩa hình ảnh có liên quan đến nội dung tìm kiếm của người dùng. Olfa Allani và cộng sự (2016) [4] đề xuất một hệ thống tra cứu ảnh tích hợp ngữ nghĩa với các đặc trưng thị giác để xây dựng một ontology cho việc tra cứu và tổ chức các thông tin ngữ nghĩa cũng như các đặc trưng thị giác dựa trên đồ thị. Kết quả thực nghiệm cho thấy hệ thống đã có những cải tiến so với phương pháp tìm kiếm ảnh dựa trên nội dung, góp phần làm tăng độ chính xác. Bên cạnh đó, Zahid Medmood và cộng sự [46], thực hiện bài toán tìm kiếm ảnh dựa trên nội dung và phân tích ngữ nghĩa hình ảnh; từ đó, nhóm tác giả sử dụng tập từ thị giác nhằm mô tả ngữ nghĩa hình ảnh. Trong công trình này, nhóm tác giả ứng dụng kỹ thuật từ điển dữ liệu để ánh xạ giữa ngữ nghĩa thị giác và đặc trưng hình ảnh. Tuy nhiên, nhóm tác giả chưa thực hiện tìm kiếm bằng cách tạo câu truy vấn SPARQL. Binbin Yu và cộng sự [81], đã đề xuất một cấu trúc ontology cho lưu trữ và truy xuất tài liệu văn bản dựa trên phân tích ngữ nghĩa văn bản. Nhóm tác giả đã thực nghiệm bằng cách trích xuất các khái niệm từ (word concepts) dựa vào 1000 bài báo khoa học để đưa vào ontology, tạo ra các khái niệm, literals gồm 10 nhóm, mỗi nhóm có 100 bài báo. Tuy nhiên, công trình chưa áp dụng cho bài toán tìm kiếm hình ảnh, chưa đề xuất mô hình xây dựng ontology nhằm khai thác dữ liệu. Đồng thời, M. N. Asim và cộng sự [7], đã thực hiện bài toán truy xuất thông tin văn bản và dữ liệu đa phương tiện (hình ảnh, video, audio) dựa trên ontology. Nhóm tác giả đã so sánh hiệu suất với các phương pháp tiếp cận trước đó về tìm kiếm văn bản, dữ liệu đa phương tiện. Tác giả sử dụng ngôn ngữ bộ ba RDF để lưu trữ dữ liệu và truy vấn trên ontology. Tuy nhiên, tác giả mới đề xuất mô hình sử dụng onotology để tìm kiếm dữ liệu ảnh đa đối tượng, chưa đề cập đến kết quả thực nghiệm để so sánh với các công trình trước đó. Botao Zhong và cộng sự [86] đã đề xuất phương pháp xác định mối quan hệ giữa các đối tượng trên hình ảnh thông qua chú thích và đặc trưng của hình ảnh. 4
Nhóm tác giả đã xây dựng một khung ontology để truy xuất mối quan hệ của hình ảnh thực hiện trên protégé nhằm phân lớp các ảnh đối tượng, phân lớp các thuộc tính, xác định mối quan hệ giữa các lớp hình ảnh và lớp đối tượng; đồng thời kết hợp các nguyên tắc phân lớp để xây dựng mối quan hệ giữa các đối tượng trên hình ảnh. Đây chính là cơ sở xây dựng ontology mở rộng cho bài toán tìm kiếm ảnh đa đối tượng dựa trên mối quan hệ giữa các đối tượng hình ảnh. Ở Việt Nam có một số nhóm nghiên cứu về tìm kiếm ảnh đã có nhiều công bố với kết quả tốt về tìm kiếm ảnh thực hiện bằng phương pháp phản hồi liên quan, ứng dụng học sâu để huấn luyện mô hình phân lớp ảnh và dự đoán bệnh trên cây trồng bằng hình ảnh, tìm kiếm ảnh sử dụng ontology [51]. Một số công trình đã ứng dụng vào các lĩnh vực của đời sống con người như chẩn đoán bệnh ung thư qua hình ảnh và một số lĩnh vực khác. Trên cơ sở khảo sát các công trình nghiên cứu liên quan, một số ưu và nhược điểm đó là: (1) Thực hiện bài toán tìm kiếm ảnh dựa trên các kỹ thuật học máy, cấu trúc cây và ontology với hiệu quả khá cao; ứng dụng được cho nhiều bộ ảnh thực nghiệm trong nhiều lĩnh vực; (2) Sự kết hợp nhiều kỹ thuật học máy trên mỗi công trình còn hạn chế; (3) Số công trình kết hợp một cấu trúc dữ liệu lưu trữ và học máy còn giới hạn; (4) Sự kết hợp ontology với các kỹ thuật khác để thực hiện qua nhiều bộ lọc nhằm nâng cao độ chính xác tìm kiếm ảnh chưa thực hiện ở nhiều công trình. Trên cơ sở này, một số định hướng được đề xuất và cải tiến nhằm nâng cao độ chính xác cho bài toán tìm kiếm ảnh dựa trên cấu trúc KD-Tree, kết hợp các kỹ thuật học máy và Ontology cho tìm kiếm ảnh theo tiếp cận ngữ nghĩa được triển khai trong đề tài luận án. 3. Định hướng nghiên cứu Trên cơ sở phân tích các công trình nghiên cứu liên quan bài toán tìm kiếm ảnh được thực hiện theo nhiều tiếp cận khác nhau. Số lượng công trình kết hợp nhiều kỹ thuật còn hạn chế. Vì vậy, định hướng nghiên cứu của luận án tập trung vào các vấn đề liên quan gồm: 5
− Nghiên cứu cấu trúc dữ liệu đa chiều KD-Tree cho tìm kiếm ảnh, cải tiến và đề xuất các thuật toán thao tác trên cấu trúc KD-Tree. − Phát triển Ontology và áp dụng cho tìm kiếm ảnh theo tiếp cận ngữ nghĩa. − Đề xuất các mô hình tìm kiếm ảnh, phương pháp kết hợp các kỹ thuật học máy và cấu trúc KD-Tree để nâng cao độ chính xác tìm kiếm ảnh. 4. Mục tiêu nghiên cứu của luận án Mục tiêu của luận án là phát triển mô hình tìm kiếm ảnh tương tự dựa trên cấu trúc dữ liệu KD-Tree kết hợp với tiếp cận ngữ nghĩa của đặc trưng thị giác hình ảnh nhằm nâng cao độ chính xác tìm kiếm ảnh. Mục tiêu cụ thể, gồm: (1) Nghiên cứu cấu trúc dữ liệu đa chiều KD-Tree; xây dựng các thuật toán thao tác trên KD-Tree tổ chức lưu trữ véc-tơ đặc trưng hình ảnh. (2) Phát triển cấu trúc KD-Tree, đồng thời xây dựng và bổ sung ngữ nghĩa cho các bộ dữ liệu thực nghiệm nhằm thực hiện mô hình tìm kiếm ảnh theo tiếp cận ngữ nghĩa trên các cấu trúc đã đề xuất. (3) Phát triển mô hình tìm kiếm ảnh bằng cách kết hợp các phương pháp học có giám sát, bán giám sát và rừng ngẫu nhiên để tạo ra mô hình phân lớp hình ảnh, gom cụm dữ liệu dựa trên cấu trúc KD-Tree. 5. Phương pháp nghiên cứu Phương pháp lý thuyết − Tổng hợp các công trình nghiên cứu liên quan đến tìm kiếm ảnh trong thời gian gần đây, đặc biệt quan tâm đến kết quả của các công trình sử dụng học máy, tìm kiếm ảnh theo ngữ nghĩa và các cấu trúc lưu trữ dạng cây. Phân tích ưu nhược điểm của các công trình, đặc điểm của cấu trúc KD-Tree và các biến thể của KD-Tree; nghiên cứu phương pháp làm giàu Ontology và phát triển mô hình tìm kiếm ảnh theo tiếp cận ngữ nghĩa dựa trên Ontology. 6
− Đề xuất mô hình tìm kiếm ảnh theo tiếp cận ngữ nghĩa và căn cứ vào đánh giá thực nghiệm, so sánh độ chính xác tìm kiếm ảnh với các công trình cùng lĩnh vực để có sự điều chỉnh và cải tiến thích hợp. Phương pháp thực nghiệm − Trên cơ sở mô hình và kỹ thuật đề xuất trong luận án, các chương trình được viết bằng ngôn ngữ cấp cao (C#), cài đặt thuật toán trên máy tính có cùng cấu hình. − Dữ liệu thực nghiệm là các bộ dữ liệu ảnh chuẩn đã được công bố và sử dụng trong các công trình có kết quả, sẽ được đối sánh với dữ liệu thực nghiệm. Một số công việc bổ sung cho các bộ dữ liệu này, bao gồm: trích xuất đặc trưng hình ảnh cho các bộ dữ liệu ảnh tiêu chuẩn: COREL [19], Wang [20], Caltech-101 [12], Caltech- 256 [13], phát hiện, phân đoạn ảnh đối tượng và trích xuất véc-tơ đặc trưng cho bộ ảnh đa đối tượng MS-COCO [21], Flickr [22]. − Xây dựng cấu trúc dữ liệu, cài đặt các thuật toán và mô hình đề xuất để thực nghiệm trên các bộ dữ liệu ảnh chuẩn; so sánh kết quả thực nghiệm trên cùng bộ dữ liệu với kết quả các công trình đã công bố, đồng thời so sánh kết quả thực nghiệm của cùng một bộ dữ liệu trên các mô hình đề xuất để minh chứng tính đúng đắn và hiệu quả của cơ sở lý thuyết. 6. Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu − Các phương pháp phân cụm và phân lớp dữ liệu. − Cấu trúc phân cụm dữ liệu đa chiều. − Cấu trúc Ontology và phương pháp xây dựng, phát triển Ontology. − Các tập ảnh đơn đối tượng và đa đối tượng. Phạm vi nghiên cứu − Các phương pháp học máy: học có giám sát, không giám sát và bán giám sát. − Cấu trúc dữ liệu đa chiều KD-Tree. − Các cải tiến: iKD_Tree, KD-Tree lồng nhau, Re KD-Tree, RF KD-Tree. − Cấu trúc Ontology và ngôn ngữ truy vấn SPARQL. − Các tập ảnh: COREL, Wang, Caltech-101, Caltech-256, MS-COCO, Flickr. 7. Nội dung và bố cục của luận án Nội dung chính của luận án được tổ chức thành ba chương như sau: 7