Luận án Kết hợp cấu trúc R-Tree với đồ thị tri thức cho mô hình tìm kiếm ảnh

ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC LÊ THỊ VĨNH THANH KẾT HỢP CẤU TRÚC R-TREE VỚI ĐỒ THỊ TRI THỨC CHO MÔ HÌNH TÌM KIẾM ẢNH 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 LÊ THỊ VĨNH THANH KẾT HỢP CẤU TRÚC R-TREE VỚI ĐỒ THỊ TRI THỨC CHO MÔ HÌNH TÌM KIẾM ẢNH 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 TẬP THỂ 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. 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ả Lê Thị Vĩnh Thanh ii LỜI CÁM ƠN Em xin gửi lời cảm ơn chân thành đế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 em để thực hiện tốt nhiệm vụ nghiên cứu và hoàn thành luận án này. Em xin gửi lời cảm ơn đến các thầy cô khoa Công nghệ thông tin của trường Đại học Khoa học đã chia sẻ và góp ý xác đáng trong quá trình thực hiện luận án. Em xin gửi lời cảm ơn sâu sắc đến Phòng Đào tạo Sau Đại học, lãnh đạo Trường Đại học Khoa học, lãnh đạo Đại học Huế đã tạo điều kiện thuận lợi cho em trong suốt quá trình học tập và thực hiện luận án. Tôi xin gửi lời cảm ơn đến Ban giám hiệu, các đồng nghiệp là cán bộ, giảng viên Trường Đại học Bà Rịa Vũng Tàu đã tạo mọi điều kiện thuận lợi, đã độ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 luôn chia sẻ, động viên trong những lúc khó khăn. Xin gửi lời cảm ơn và bày tỏ lòng biết ơn vô hạn đến những người thân yêu, ba mẹ, chồng và các con đã hỗ trợ, ủng hộ trong suốt quá trình học tập, nghiên cứu. Tác giả iii MỤC LỤC LỜI CAM ĐOAN ....................................................................................................... i LỜI CÁM ƠN ............................................................................................................ ii DANH MỤC KÝ HIỆU VÀ CHỮ VIẾT TẮT .......................................................... v DANH MỤC HÌNH ẢNH ....................................................................................... vii DANH MỤC BẢNG BIỂU ...................................................................................... ix PHẦN MỞ ĐẦU ......................................................................................................... 1 CHƯƠNG 1.TỔNG QUAN VỀ TÌM KIẾM ẢNH, CẤU TRÚC R-TREE VÀ ĐỒ THỊ TRI THỨC ......................................................................................................... 10 1.1. Giới thiệu........................................................................................................ 10 1.2. Tìm kiếm ảnh theo nội dung .......................................................................... 11 1.2.1. Đặc trưng hình ảnh ..................................................................................... 12 1.2.2. Độ đo tương tự giữa hai hình ảnh............................................................... 17 1.3. Cấu trúc R-Tree và các biến thể cho tìm kiếm ảnh ........................................ 19 1.4. Đồ thị tri thức ................................................................................................. 23 1.5. Đồ thị ngữ cảnh .............................................................................................. 24 1.6. Kiến trúc hệ thống tìm kiếm ảnh .................................................................... 26 1.7. Môi trường thực nghiệm và độ đo đánh giá ................................................... 28 1.8. Tổng kết chương ............................................................................................ 31 CHƯƠNG 2.TÌM KIẾM ẢNH DỰA TRÊN RS-TREE ........................................... 32 2.1. Giới thiệu........................................................................................................ 32 2.2. Cấu trúc RS-Tree ............................................................................................ 35 2.2.1. Mô tả cấu trúc RS-Tree ............................................................................... 35 2.2.2. Xây dựng cấu trúc RS-Tree ......................................................................... 41 2.3. Các thao tác trên cấu trúc RS-Tree ................................................................. 44 2.3.1. Tiêu chí lựa chọn nút lá phù hợp ................................................................ 44 2.3.2. Thêm phần tử vào cây ................................................................................ 47 2.3.3. Cập nhật tâm và bán kính khối cầu ............................................................ 49 2.3.4. Tách nút ...................................................................................................... 50 2.4. Tìm kiếm ảnh theo nội dung dựa trên RS-Tree .............................................. 54 2.4.1. Mô hình tìm kiếm ảnh dựa trên RS-Tree .................................................... 54 2.4.2. Thuật toán tìm kiếm ảnh ............................................................................. 55 2.5. Thực nghiệm và đánh giá ............................................................................... 56 2.6. Tổng kết chương ............................................................................................ 69 iv CHƯƠNG 3.KẾT HỢP RS-TREE VÀ ĐỒ THỊ TRI THỨC TRONG TÌM KIẾM ẢNH .......................................................................................................................... 70 3.1. Giới thiệu........................................................................................................ 70 3.2. RS-Tree kết hợp đồ thị láng giềng .................................................................. 72 3.2.1. Khái niệm cơ sở .......................................................................................... 72 3.2.2. Cấu trúc đồ thị cụm láng giềng .................................................................. 76 3.2.3. Thuật toán tạo đồ thị láng giềng ................................................................. 77 3.2.4. Tìm kiếm ảnh theo nội dung dựa trên cấu trúc NBGraphRST................... 79 3.3. Khung đồ thị tri thức cho dữ liệu hình ảnh .................................................... 80 3.3.1. Quy trình xây dựng đồ thị tri thức .............................................................. 80 3.3.2. Quá trình xây dựng đồ thị tri thức .............................................................. 83 3.3.3. Các thuật toán xây dựng đồ thị tri thức ...................................................... 91 3.4. Tìm kiếm ảnh kết hợp RS-Tree với đồ thị tri thức ......................................... 94 3.4.1. Nhận dạng đối tượng bằng Faster-RCNN .................................................. 94 3.4.2. Mô hình tìm kiếm ảnh kết hợp RS-Tree và đồ thị tri thức .......................... 96 3.4.3. Thuật toán tìm kiếm ảnh ............................................................................. 99 3.5. Thực nghiệm và đánh giá ............................................................................. 101 3.5.1. Mô tả bộ dữ liệu Visual Genome ............................................................. 101 3.5.2. Thực nghiệm ............................................................................................. 102 3.5.3. Đánh giá thực nghiệm .............................................................................. 114 3.6. Tổng kết chương .......................................................................................... 116 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN .............................................................. 118 DANH MỤC CÁC CÔNG TRÌNH NGHIÊN CỨU CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN ...................................................................................................... 120 TÀI LIỆU THAM KHẢO ....................................................................................... 121 v DANH MỤC KÝ HIỆU VÀ CHỮ VIẾT TẮT Ký hiệu Diễn giải tiếng Anh Diễn giải tiếng Việt ARN Attentive Relational Network Mạng mối quan hệ tập trung ARP Average Retrieval Precision Độ chính xác trung bình AUC Area Under the Curve Diện tích dưới đường cong CBIR Content-Based Image Retrieval Tìm kiếm ảnh theo nội dung CBIR_NBGraphRST Content-based Image Retrieval on RS-Tree and Neighbor Graph Tìm ảnh theo nội dung dựa trên RS-Tree và đồ thị láng giềng CBIR-RST Content-Based Image Retrieval on RS-Tree Tìm kiếm ảnh theo nội dung dựa trên RS-Tree CCM Color Co-occurrence Matrix Ma trận đồng xuất hiện màu CDH Color Difference Histogram Lược đồ màu CNN Convolutional Neural Network Mạng nơ-ron tích chập CRF Conditional Random Field Trường ngẫu nhiên có điều kiện CSD Color Structure Descriptor Bộ mô tả cấu trúc màu DCD Dominant Color Descriptor Bộ mô tả màu chủ đạo DWT Discrete Wavelet Transform Phép biến đổi Wavelet rời rạc EDH Edge Histogram Descriptor Bộ mô tả lược đồ biên FCM Fuzzy C-means Clustering Phân cụm mờ C-means GCN Graph Convolutional Network Mạng tích chập đồ thị GLCM Gray-level Co-occurrence Matrix Ma trận đồng xuất hiện mức xám GMM Gaussian Mixture Models Mô hình hỗn hợp Gauss HOG Histograms of Oriented Gradients Lược đồ theo hướng Gradient KG Knowledge Graph Đồ thị tri thức LBP Local Binary Pattern Mẫu nhị phân cục bộ LD Linked Data Dữ liệu liên kết tài nguyên MAP Mean Average Precision Độ chính xác trung bình vi Ký hiệu Diễn giải tiếng Anh Diễn giải tiếng Việt MBR Minimum Bounding Rectangle Hình chữ nhật bao đóng tối thiểu MBS Minimum Bounding Sphere Khối cầu bao đóng tối thiểu MLP Multi-layer Perceptron Mạng Perceptron đa tầng MRMD Multi-Resolution Multi- Directional Đa hướng đa độ phân giải NBGraphRST Neighbor Graph on RS-Tree Đồ thị cụm láng giềng trên RS- Tree OLD Open Linked Data Dữ liệu liên kết mở OWL Web Ontology Language Ngôn ngữ ontology web RDF Resource Description Framework Ngôn ngữ mô tả khung tài nguyên RF Relevance Feedback Phương pháp phản hồi liên quan ROC Receiver Operating Characteristic Đồ thị mô tả đặc tính RS-Tree Region Sphere Tree Cây phân cụm vùng khối cầu SBIR Semantic-Based Image Retrieval Tìm ảnh theo ngữ nghĩa SBIR_GraphRSTKG Semantic-based Image Retrieval on RS-Tree and Knowledge Graph Tìm ảnh theo ngữ nghĩa dựa trên RS-Tree và đồ thị tri thức SG Scene Graph Đồ thị ngữ cảnh SIFT Scale Invariant Features Transform Đặt trưng hình ảnh SIFT SURF Speeded Up Robust Feature Đặc trưng hình ảnh SURF SVM Support Vector Machine Máy vec-tơ hỗ trợ TBIR Text-Based Image Retrieval Tìm kiếm ảnh dựa trên văn bản TTF Tamura Texture Feature Đặc trưng kết cấu Tamura TVG Textual Scene Graph Đồ thị ngữ cảnh theo văn bản VG Visual Genome Tập dữ liệu ảnh Visual Genome VSG Visual Scene Graph Đồ thị ngữ cảnh theo thị giác vii DANH MỤC HÌNH ẢNH Hình 1.1. Mô hình tìm kiếm ảnh tương tự theo nội dung ......................................... 11 Hình 1.2. Đặc trưng màu sắc MPEG7 ....................................................................... 16 Hình 1.3. Đặc trưng vị trí Shi-tomasi MPEG7 ......................................................... 16 Hình 1.4. Đặc trưng vị trí và kết cấu MaxPooling Sobel .......................................... 16 Hình 1.5. Đặc trưng hình dạng và kết cấu Sobel HOG ............................................. 17 Hình 1.6. Cấu trúc R-Tree dạng phân cấp ................................................................. 19 Hình 1.7. Cấu trúc R-Tree dạng phẳng ..................................................................... 20 Hình 1.8. Ví dụ về đồ thị ngữ cảnh trong bộ dữ liệu VG [28] .................................. 25 Hình 1.9. Mô hình tìm kiếm ảnh theo nội dung dựa trên cấu trúc RS-Tree .............. 26 Hình 1.10. Mô hình tìm kiếm ảnh kết hợp RS-Tree và đồ thị tri thức ...................... 27 Hình 2.1. Cấu trúc RS-Tree dạng phẳng .................................................................... 35 Hình 2.2. Cấu trúc RS-Tree dạng phân cấp ............................................................... 36 Hình 2.3. Mô tả một nút thực thể dạng phẳng trên cấu trúc RS-Tree........................ 37 Hình 2.4. Mô tả một nút lá dạng phẳng trên cấu trúc RS-Tree .................................. 38 Hình 2.5. Mô tả một nút trong dạng phẳng trên RS-Tree .......................................... 39 Hình 2.6. Minh họa quá trình thêm một phần tử vào cấu trúc RS-Tree .................... 43 Hình 2.7. Mô tả thao tác thêm một phần tử vào nút lá .............................................. 44 Hình 2.8. Minh họa sự giãn nở không gian khi thêm mới một phần tử .................... 44 Hình 2.9. Minh họa các tiêu chí lựa chọn không gian phân bố phần tử ................... 45 Hình 2.10. Mô tả thuật toán tách nút dựa vào độ lệch sai biệt .................................. 50 Hình 2.11. Mô hình tìm kiếm ảnh CBIR-RST dựa trên RS-Tree .............................. 54 Hình 2.12. Giao diện tạo cấu trúc RS-Tree ................................................................ 57 Hình 2.13. Giao diện tìm kiếm ảnh dựa trên cấu trúc RS-Tree ................................. 57 Hình 2.14. Một kết quả tìm kiếm dựa trên cấu trúc RS-Tree .................................... 58 Hình 2.15. Thời gian tìm kiếm trung bình của tập ảnh COREL ............................... 60 Hình 2.16. Thời gian tìm kiếm trung bình của tập ảnh OF17 ................................... 60 Hình 2.17. Thời gian trung bình tìm kiếm của tập ảnh OF102 ................................. 60 Hình 2.18. Thời gian trung bình tìm kiếm của tập ảnh CUB-2011-200 ................... 61 Hình 2.19. So sánh hiệu suất giữa các tập dữ liệu ảnh trên cấu trúc RS-Tree ........... 61 Hình 2.20. Precision-Recall và ROC của bộ dữ liệu COREL .................................. 62 Hình 2.21. Precision-Recall và ROC của bộ dữ liệu Oxford Flowers 17 ................. 62 Hình 2.22. Precision-Recall và ROC của bộ dữ liệu Oxford Flowers 102 (1-51) .... 62 Hình 2.23. Precision-Recall và ROC của bộ dữ liệu Oxford Flowers 102 (52-102) 63 Hình 2.24. Precision-Recall và ROC của bộ dữ liệu CUB-2011-200 (1-100) ......... 63 Hình 2.25. Precision-Recall và ROC của bộ dữ liệu CUB-2011-200 (101-200) ..... 63 Hình 3.1. Tách nút có vùng không gian chồng lấp ................................................... 72 Hình 3.2. Tách nút có vùng không gian rời nhau ...................................................... 73 Hình 3.3. Mô tả tính chất chồng lấp không gian ....................................................... 73 Hình 3.4. Minh họa khoảng cách giữa hai nút lá ...................................................... 74 Hình 3.5. Mô tả đồ thị láng giềng của một nút lá ..................................................... 75 Hình 3.6. Cấu trúc đồ thị láng giềng NBGraphRST dạng phẳng ............................. 76 viii Hình 3.7. Cấu trúc đồ thị láng giềng NBGraphRST phân cấp .................................. 77 Hình 3.8. Một đồ thị ngữ cảnh con của ảnh 2371376.jpg ......................................... 81 Hình 3.9. Tiến trình xây dựng đồ thị tri thức ............................................................ 82 Hình 3.10. Dữ liệu mẫu các phân lớp ảnh ................................................................. 83 Hình 3.11. Mẫu dữ liệu các đối tượng ảnh ................................................................ 84 Hình 3.12. Mẫu dữ liệu mối quan hệ giữa các đối tượng ảnh ................................... 84 Hình 3.13. Mô hình của đồ thị tri thức ...................................................................... 85 Hình 3.14. Bộ ba định nghĩa lớp trong đồ thị tri thức ............................................... 86 Hình 3.15. Bộ ba định nghĩa các cá thể trong đồ thị tri thức .................................... 87 Hình 3.16. Bộ ba thể hiện mối quan hệ của các cá thể ............................................. 88 Hình 3.17. Thuộc tính dữ liệu của cá thể inclass ...................................................... 88 Hình 3.18. Thuộc tính dữ liệu của cá thể OBJ .......................................................... 89 Hình 3.19. Thuộc tính dữ liệu của đối tượng OBJ1068652 dưới dạng OWL .......... 89 Hình 3.20. Thuộc tính dữ liệu của cá thể IMG1........................................................ 90 Hình 3.21. Thuộc tính dữ liệu của ảnh IMG3 dưới dạng OWL ................................ 90 Hình 3.22. Các chú thích của mối quan hệ opREL2 ................................................. 90 Hình 3.23. Các đối tượng trong hình ảnh của bộ dữ liệu COCO .............................. 95 Hình 3.24. Minh họa quá trình phân lớp đối tượng bằng mạng Faster-RCNN ........ 95 Hình 3.25. Minh họa trích xuất đặc trưng cho ảnh đầu vào ...................................... 96 Hình 3.26. Mô hình tìm kiếm ảnh theo ngữ nghĩa kết hợp RS-Tree với KG ............ 97 Hình 3.27. Mô hình tìm kiếm ảnh trên CBIR_NBGraphRST ................................ 103 Hình 3.28. Một kết quả tìm kiếm ảnh trên CBIR-NBGraphRST ........................... 103 Hình 3.29. Tạo KG cho bộ dữ liệu Visual Genome ................................................ 104 Hình 3.30. Mô tả đồ thị ngữ cảnh của ảnh 285618.jpg trong tập ảnh VG .............. 105 Hình 3.31. Tìm kiếm và trích xuất đồ thị ngữ cảnh của hình ảnh trên KG............. 105 Hình 3.32. Mô tả ngữ nghĩa của hình ảnh ............................................................... 106 Hình 3.33. Một kết quả tìm kiếm ảnh trên SBIR-RSTKG ...................................... 106 Hình 3.34. Precision-Recall và ROC của bộ dữ liệu COREL ................................ 110 Hình 3.35. Precision-Recall và ROC của bộ dữ liệu OF17 .................................... 110 Hình 3.36. Precision-Recall và ROC của bộ dữ liệu OF102 .................................. 111 Hình 3.37. Precision-Recall và ROC của bộ dữ liệu CUB-2011-20....................... 111 Hình 3.38. Precision-Recall và ROC của bộ dữ liệu MS-COCO ........................... 111 Hình 3.39. Precision-Recall và ROC của bộ dữ liệu Dataset 1-VG ....................... 112 Hình 3.40. Precision-Recall và ROC của bộ dữ liệu Dataset 2-VG ....................... 112 Hình 3.41. Precision-Recall và ROC của bộ dữ liệu MS-COCO ........................... 113 Hình 3.42. Precision-Recall và ROC của bộ dữ liệu Dataset 1 -VG ...................... 113 Hình 3.43. Precision-Recall và ROC của bộ dữ liệu Dataset 2 -VG ...................... 114 ix DANH MỤC BẢNG BIỂU Bảng 1.1. Các giá trị véc-tơ đặc trưng được trích xuất ............................................. 15 Bảng 1.2. Các tập dữ liệu ảnh được thực nghiệm trong luận án ............................... 28 Bảng 2.1. Mô tả các tham số thực nghiệm xây dựng cấu trúc RS-Tree .................... 59 Bảng 2.2. Kết quả thực nghiệm xây dựng cấu trúc RS-Tree ..................................... 59 Bảng 2.3. Hiệu suất tìm kiếm của hệ tìm kiếm CBIR-RST trên tập ảnh COREL .... 64 Bảng 2.4. Hiệu suất tìm kiếm của hệ CBIR-RST trên tập ảnh OF17 ....................... 64 Bảng 2.5. Hiệu suất tìm kiếm của hệ CBIR-RST trên tập ảnh OF102 ..................... 65 Bảng 2.6. Hiệu suất tìm kiếm của hệ CBIR-RST trên tập ảnh CUB ........................ 66 Bảng 2.7. So sánh độ chính xác giữa các phương pháp trên tập ảnh COREL .......... 66 Bảng 2.8. So sánh độ chính xác giữa các phương pháp trên tập ảnh