Luận án Phát triển mô hình tìm kiếm ảnh dựa trên cấu trúc KD-TREE

ử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 iv 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 v DANH MỤC KÝ HIỆU VÀ TỪ VIẾT TẮT Ký hiệu viết tắt Diễn giải tiếng Anh Diễn giải tiếng Việ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 using Relationship KD-Tree Hàm phân lớp mối quan hệ bằng Re KD- 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- Tree Thuật toán tạo RF KD-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 Matrix Ma trận đồng xuất hiện mức xám HOG Histograms of Oriented Gradients Biểu đồ định hướng Gradients iKD_Tree Improvement k-Dimensional Tree Cấu trúc KD-Tree cải tiến 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 vi 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 Neural Networks Mạng Nơ-ron tích chập dựa trên vùng đối tượng Re KD-Tree Relationship k-Dimensional Tree Cấu trúc KD-Tree phân lớp mối quan hệ 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 Characteristic Đồ thị đặc tính SB-iKDT Semantic-based Image Retrieval using iKD_Tree Hệ tìm kiếm ảnh sử dụng iKD_Tree SBIR Semantic-Based Image Retrieval Tìm kiếm ảnh theo ngữ nghĩa SB-KDT Semantic-based Image Retrieval using KD-Tree Hệ tìm kiếm ảnh sử dụng KD-Tree SB-NKDT Semantic-based Image Retrieval using Nested KD- Tree Hệ tìm kiếm ảnh sử dụng KD-Tree lồng nhau SG Scene Graph Đồ thị ngữ cảnh SIFT Scale Invariant Features Transform Đặc trưng bất biến SIFT SiKDT Search on iKD_Tree Thuật toán tìm kiếm ảnh trên iKD_Tree SKDO Search on KD-Tree and Ontology Thuật toán tìm kiếm trên KD-Tree và 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 vii SO-KDT Semantic-based Image Retrieval using KD-Tree and Ontology Hệ tìm kiếm ảnh theo ngữ nghĩa sử dụng KD-Tree và Ontology SR-KDF Semantic-based Image Retrieval using RF KD-Tree Hệ tìm kiếm ảnh sử dụng RF KD-Tree SR-KDT Semantic-based Image Retrieval using Relationship KD-Tree Hệ tìm kiếm ảnh theo ngữ nghĩa sử dụng Re KD-Tree SRKO Semantic-based Image Retrieval using KD-Tree and Ontology Thuật toán tìm kiếm ảnh sử dụng Re KD-Tree và Ontology SRRE Semantic-based Image Retrieval using Relationship KD-Tree Thuật toán tìm kiếm ảnh sử dụng Re KD-Tree SRRF Semantic-based Image Retrieval using Random Forest KD-Tree Thuật toán tìm kiếm ảnh sử dụng RF 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 KD-Tree Hàm huấn luyện trọng số trên RF KD- Tree WWW Word Wide Web Mạng toàn cầu viii 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 ix 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