Tóm tắt Luận án Tiến sĩ Khoa học máy tính: 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

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

Thêm vào BST

Báo xấu

9
lượt xem 2
download

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

Tóm tắt Luận án Tiến sĩ Khoa học máy tính "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" được nghiên cứu với mục tiêu: Phát triển các mô hình tìm kiếm ảnh dựa trên cấu trúc R-Tree, đề xuất mô hình kết hợp cấu trúc này với biểu diễn quan hệ ngữ nghĩa giữa các đối tượng hình ảnh nhằm nâng cao độ chính xác tìm kiếm ảnh.

Chủ đề:

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

Lưu

Nội dung Text: Tóm tắt Luận án Tiến sĩ Khoa học máy tính: 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 Ngành: Khoa học máy tínhMã số: 9 48 01 01 LUẬN ÁN TIẾN SĨ 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
2 Công trình được hoàn thành tại: Khoa Công nghệ Thông tin,Trường Đại học Khoa học, Đại học Huế. Tập thể hướng dẫn khoa học: PGS. TS Lê Mạnh Thạnh TS. Văn Thế Thành Phản biện 1: PGS.TS. Nguyễn Thanh Bình, Trường Đại học Công nghệ thông tin và Truyền thông Việt Hàn, Đại học Đà Nẵng. Phản biện 2: PGS.TS. Đặng Văn Đức, Viện Công nghệ thông tin, Viện Hàn lâm Khoa học và công nghệ Việt Nam. Phản biện 3: TS. Phạm Thị Thu Thúy, Trường Đại học Nha Trang. Luận án sẽ được bảo vệ tại Hội đồng chấm luận án cấp Đại học Huế họp tại: ………………………………………... ……………………………………………………………….. Vào hồi:...….giờ….........ngày….........tháng….......năm......... Có thể tìm hiểu luận án tại thư viện: Trung tâm thông tin thư viện,Trường Đại học Khoa học, Đại học Huế.
3 MỞ ĐẦU 1. Lý do chọn đề tài Hiện nay, các hệ thống tìm kiếm ảnh đã được phát triển và đưa vào nhiều ứng dụng khác nhau như nhận dạng tìm kiếm khuôn mặt [1]; tìm kiếm ảnh hàng hóa [2]; tìm kiếm ảnh y tế [3], tìm kiếm ảnh vệ tinh [4], v.v. Có hai phương pháp tìm kiếm ảnh thông dụng bao gồm: tìm theo từ khóa TBIR (Text-based Image Retrieval) và tìm theo nội dung CBIR (Content-based Image Retrieval). Phương pháp CBIR tập trung vào việc trích xuất và so sánh các đặc trưng cấp thấp (low-level features) của các hình ảnh như màu sắc, kết cấu, hình dạng, vị trí và một số đặc trưng khác [7-9]. Các kết quả của nhiều công trình nghiên cứu trong thập kỷ qua đã minh chứng tính hiệu quả của các kỹ thuật dựa trên CBIR và đã ứng dụng trong nhiều hệ thống tìm kiếm ảnh [10]. Hệ thống CBIR hỗ trợ người dùng tìm kiếm tập các ảnh tương tự nhau về nội dung dựa trên các đặc trưng cấp thấp nhưng các hình ảnh kết quả có thể khác nhau về ngữ nghĩa [11]. Đây chính là khoảng cách giữa ngữ nghĩa cấp cao và các đặc trưng thị giác cấp thấp của hình ảnh, việc thu hẹp khoảng cách này là một trong những thách thức lớn trong các hệ tìm kiếm ảnh dựa trên nội dung [12, 13]. Do đó, bài toán phân tích và tìm kiếm ảnh theo tiếp cận ngữ nghĩa trong lĩnh vực thị giác máy tính đang rất được các nhà nghiên cứu quan tâm [14-16]. Với sự tăng trưởng dữ liệu đa phương tiện (bao gồm: hình ảnh, âm thanh, video, văn bản), các hệ thống xử lý cần lưu trữ một khối lượng dữ liệu rất lớn [17]. Vì vậy, việc tạo cấu trúc lưu trữ dữ liệu đa chiều cho các dạng dữ liệu đa phương tiện là cần thiết để giúp quá trình tìm kiếm nhanh chóng và hiệu quả. Trên cơ sở đó, luận án đề xuất thực hiện đề tài “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”.
4 2. Tổng quan tình hình nghiên cứu Trong những năm gần đây, các hệ thống tìm kiếm ảnh được thực hiện bởi nhiều phương pháp phân cụm dữ liệu khác nhau và mang lại những kết quả tốt. Trong đó, R-Tree là cấu trúc dùng để phân cụm và lưu trữ dữ liệu đa chiều dựa trên vùng không gian để phân hoạch dữ liệu và được ứng dụng hiệu quả trong lĩnh vực tìm kiếm ảnh [16, 18]. Có nhiều công trình đã áp dụng các cấu trúc R-Tree cho bài toán tìm kiếm ảnh tương tự nhằm nâng cao độ chính xác và giảm thời gian tìm kiếm ảnh. Haldurai và cộng sự (2015) đã đề xuất một hệ tìm kiếm ảnh tương tự theo nội dung sử dụng cấu trúc cây R-Tree [22]. Vanitha và cộng sự (2017) đã đề xuất một cấu trúc lưu trữ SR-Tree ứng dụng cho hệ thống tìm kiếm ảnh tương tự theo nội dung [24]. Shama và cộng sự (2015) đã đề xuất một hệ thống tìm kiếm ảnh tương tự sử dụng cấu trúc R*-Tree cho tập ảnh thực vật [23]. Alfarrarjeh và cộng sự (2020) đã đề xuất mô hình tìm kiếm ảnh dựa trên cấu trúc R*-Tree ứng dụng cho bài toán tìm kiếm ảnh tương tự với dữ liệu ảnh đường phố [21]. Các hệ thống tìm kiếm theo nội dung dựa trên các đặc trưng cấp thấp đã đạt được nhiều kết quả khả quan và được áp dụng vào thực tế. Tuy nhiên, hạn chế của các hệ thống này là tồn tại một độ sai lệch giữa các đặc trưng cấp thấp và ngữ nghĩa cấp cao của hình ảnh (semantic gap) [11]. Giải quyết “semantic gap” là một bài toán đầy thách thức của các hệ thống tìm kiếm ảnh dựa trên nội dung [12]. Các công trình nghiên cứu gần đây đã áp dụng đồ thị tri thức và đồ thị ngữ cảnh cho các hệ thống tìm kiếm theo tiếp cận ngữ nghĩa để giảm “semantic gap” giữa các đặc trưng cấp thấp và ngữ nghĩa cấp cao của hình ảnh [44-46], cụ thể như sau: Justin Jonhson và cộng sự đã đề xuất một khung tìm kiếm ảnh theo ngữ nghĩa dựa trên khái
5 niệm đồ thị ngữ cảnh [27]. Wang, S. và cộng sự đã giới thiệu một mô hình tìm kiếm ảnh sử dụng đồ thị ngữ cảnh bao gồm đồ thị ngữ cảnh trực quan và đồ thị ngữ cảnh văn bản [28]. Yoon, S. và cộng sự đã giới thiệu một cách tiếp cận mới để tìm kiếm ảnh dựa trên độ tương tự của đồ thị ngữ cảnh sử dụng mạng nơ-ron đồ thị [29]. Qi, M. và cộng sự đã đề xuất một khung mới để tìm kiếm ngữ cảnh trực tuyến đa phương thức dựa trên các biểu diễn nhị phân và đồ thị ngữ nghĩa [30]. Quinn, M. H. và cộng sự mô tả một kiến trúc tìm kiếm ảnh theo ngữ nghĩa dựa trên tình huống trực quan của hình ảnh [31]. Do đó phương pháp tìm kiếm ảnh kết hợp giữa đặc trưng cấp thấp và ngữ nghĩa cấp cao dựa trên đồ thị tri thức cho các tập ảnh lớn là một định hướng nghiên cứu phù hợp, mang tính cấp thiết và được ứngdụng hiệu quả trong các hệ thống tìm kiếm ảnh tương tự. 3. Mục tiêu của luận án Mục tiêu của luận án là phát triển các mô hình tìm kiếm ảnh dựa trên cấu trúc R-Tree, đề xuất mô hình kết hợp cấu trúc này với biểu diễn quan hệ ngữ nghĩa giữa các đối tượng hình ảnh nhằm nâng cao độ chính xác tìm kiếm ảnh. Các mục tiêu cụ thể của luận án bao gồm: (1) Nghiên cứu phương pháp lưu trữ dữ liệu đa chiều trên cấu trúc R-Tree, đồng thời kết hợp đồ thị láng giềng vào cấu trúc cải tiến RS-Tree nhằm nâng cao hiệu quả lưu trữ và tìm kiếm; (2) Đề xuất sử dụng đồ thị tri thức để biểu diễn thông tin ngữ nghĩa và các mối quan hệ ngữ nghĩa giữa các đối tượng trong hình ảnh; (3) Nghiên cứu các mô hình tìm kiếm ảnh dựa trên cấu trúc RS-Tree; kết hợp đồ thị láng giềng với RS-Tree; kết hợp RS-Tree với đồ thị tri thức. 4. Đối tượng và phạm vi nghiên cứu: Đối tượng nghiên cứu: (1) Các cấu trúc cây phân cụm dữ liệu, tạo véc-tơ đặc trưng đa chiều phục vụ cho bài toán tìm kiếm ảnh; (2) Các
6 thuật toán tạo cấu trúc lưu trữ dữ liệu và các thuật toán tìm kiếm ảnh; (3) Đồ thị tri thức; (4) Các tập dữ liệu ảnh phổ biến. Phạm vi nghiên cứu: (1) Tạo và cải tiến cấu trúc lưu trữ dữ liệu đa chiều dựa trên cấu trúc R-Tree; (2) Các thuật toán xây dựng và các thuật toán tìm kiếm trên cây; (3) Các phương pháp cải tiến cây phân cụm với đồ thị cụm láng giềng; (4) Đồ thị tri thức, ngôn ngữ OWL, truy vấn SPARQL; (5) Các tập dữ liệu ảnh bao gồm: COREL, Oxford Flowers 17, Oxford Flowers 102, CUB-200-2011, Visual Genome, MS-COCO. 5. Phương pháp nghiên cứu Phương pháp lý thuyết: Tổng hợp, phân tích các công bố liên quan đến tìm kiếm ảnh dựa trên cấu trúc R-Tree và tìm kiếm ảnh theo tiếp cận ngữ nghĩa; đánh giá ưu, khuyết điểm của các công trình nhằm đề xuất các cải tiến phù hợp. Phương pháp thực nghiệm: Xây dựng thực nghiệm trích xuất đặc trưng, cải tiến cấu trúc dữ liệu, đề xuất mô hình và cài đặt trên các tập dữ liệu ảnh phổ biến. Các tập dữ liệu ảnh được sử dụng cho cài đặt thực nghiệm bao gồm: COREL, Oxford Flowers 17, Oxford Flowers 102, CUB-2011-200, Visual Genome và MS-COCO. 6. Bố cục của luận án Luận án được trình bày trong 128 trang, mở đầu (09 trang), kết luận và hướng phát triển (02 trang), danh mục các công trình khoa học của tác giả liên quan đến luận án (01 trang), tài liệu tham khảo (09 trang), luận án chia thành 3 chương. Chương 1 (22 trang) trình bày các cơ sở lý thuyết về tìm kiếm ảnh và cấu trúc R-Tree. Chương 2 (38 trang) trình bày cấu trúc phân cụm dữ liệu RS-Tree và mô hình tìm kiếm ảnh theo nội dựa trên cấu trúc RS-Tree. Chương 3 (47 trang) đề xuất các cải tiến trên cấu trúc RS-Tree kết hợp đồ thị láng
7 giềng và đồ thị tri thức để nâng cao độ chính xác tìm kiếm ảnh. 7. Đóng góp của luận án (1) Đề xuất các cải tiến đối với cấu trúc R-Tree và thiết kế RS- Tree với các khối cầu dữ liệu kết hợp đồ thị láng giềng và xây dựng cấu GraphNB-RST để nâng cao độ chính xác tìm kiếm ảnh. Đồng thời, đề xuất các thuật toán và các mô hình tìm kiếm ảnh theo nội dung dựa trên các cấu trúc đã xây dựng; (2) Xây dựng đồ thị tri thức dựa trên tập dữ liệu ảnh Visual Genome và RS-Tree để lưu trữ và mô tả các thông tin ngữ nghĩa của hình ảnh, các mối quan hệ ngữ nghĩa giữa các đối tượng trong ảnh. Từ đó, xây dựng mô hình tìm kiếm ảnh theo tiếp cận ngữ nghĩa dựa trên sự kết hợp RS-Tree với đồ thị tri thức để nâng cao độ chính xác tìm kiếm ảnh. Chương 1. TỔNG QUAN VỀ TÌM KIẾM ẢNH, CẤU TRÚC R-TREE VÀ ĐỒ THỊ TRI THỨC 1.1. Giới thiệu Tìm kiếm ảnh theo nội dung được ứng dụng trong nhiều lĩnh vực khác nhau của đời sống. Hai vấn đề quan trọng trong bài toán tìm kiếm ảnh đó là (1) mô tả nội dung thị giác của hình ảnh bằng các đặc trưng cấp thấp; (2) tạo cấu trúc dữ liệu lưu trữ cho nội dung thị giác [16, 36]. Bên cạnh đó, nhiều phương pháp khác nhau được áp dụng cho bài toán tìm kiếm ảnh theo tiếp cận ngữ nghĩa để giảm độ sai lệch ngữ nghĩa giữa các đặc trưng cấp thấp và ngữ nghĩa cấp cao của con người [48]. Do đó, việc kết hợp các phương pháp khác nhau cho bài toán tìm kiếm ảnh cần được thực hiện nhằm nâng cao độ chính xác tìm kiếm.
8 1.2. Tìm kiếm ảnh dựa theo nội dung Tìm kiếm ảnh theo nội dung là phương pháp thực hiện tìm kiếm tập các hình ảnh tương tự dựa trên việc trích xuất tự động các đặc trưng cấp thấp của hình ảnh như màu sắc, kết cấu và hình dạng, vị trí, không gian. Hệ thống sẽ lưu trữ các đặc trưng cấp thấp của bộ dữ liệu hình ảnh dưới dạng các véc-tơ đặc trưng đa chiều và đối sánh các véc-tơ đặc trưng dựa trên một độ đo tương đồng [42]. Trong luận án này, các phương pháp trích xuất đặc trưng cấp thấp được kết hợp bao gồm: đặc trưng màu sắc MPEG7 (25 đặc trưng); đặc trưng vị trí Shi-tomasi MPEG7 (25 đặc trưng), đặc trưng vị trí và kết cấu MaxPooling Sobel (48 đặc trưng); đặc trưng hình dạng và kết cấu Sobel HOG (144 đặc trưng). Số đặc trưng của hình ảnh được trích xuất là 242 chiều. Bên cạnh đó, nhiều phương pháp tìm kiếm ảnh theo ngữ nghĩa được đề xuất để giải quyết độ sai lệch ngữ nghĩa giữa nội dung cấp thấp của hình ảnh với ngữ nghĩa cấp cao của con người: (1) Các kỹ thuật học máy được sử dụng để liên kết các đặc trưng cấp thấp với ngữ nghĩa của hình ảnh. (2) Tìm kiếm ảnh dựa trên đồ thị tri thức để mô tả ngữ nghĩa hình ảnh và các mối quan hệ của các đối tượng trong hình ảnh. 1.3. Cấu trúc R-Tree cho bài toán tìm kiếm ảnh Từ việc khảo sát cấu trúc R-Tree và các biến thể của chúng cho thấy rằng cấu trúc này được sử dụng để lưu trữ dữ liệu đa chiều và được áp dụng trong bài toán tìm kiếm dữ liệu ảnh nhằm nâng cao hiệu quả và tốc độ tìm kiếm. Trên cơ sở đó, trong luận án này, các mô hình tìm kiếm ảnh dựa trên cấu trúc RS-Tree được đề xuất trong phần 1.5. RS-Tree là một cấu trúc được cải tiến từ cấu trúc R-Tree nguyên thủy và các biến thể của nó, được trình bày trong chương 2.
9 1.4. Tổng quan đồ thị tri thức Đồ thị tri thức ngày càng được quan tâm vì cấu trúc trừu tượng của nó đã giúp cho việc quản lý dữ liệu và khái niệm một cách hiệu quả. Đồ thị tri thức mã hóa ngữ nghĩa và dữ liệu dưới dạng đồ thị bao gồm: (1) Tri thức (ngữ nghĩa): các khái niệm và mối quan hệ giữa các khái niệm là yếu tố quan trọng, chúng mã hóa tri thức để mô tả các miền dữ liệu trong thế giới thực; (2) Đồ thị (dữ liệu): một cấu trúc dữ liệu dựa trên các nút và cạnh cho phép tích hợp dữ liệu từ các nguồn dữ liệu không đồng nhất, từ không có cấu trúc đến có cấu trúc. 1.5. Đồ thị ngữ cảnh Đồ thị ngữ cảnh là một cấu trúc dữ liệu biểu diễn nội dung ngữ nghĩa của hình ảnh bao gồm: các đối tượng, các thuộc tính của đối tượng và mối quan hệ giữa các đối tượng [28]. Là một tri thức hữu ích mô tả ngữ nghĩa chi tiết của hình ảnh và các chú thích, đồ thị ngữ cảnh đã được ứng dụng trong nhiều nhiệm vụ bao gồm: chú thích hình ảnh [82], tìm kiếm ảnh [83], trả lời câu hỏi cho hình ảnh(VQA) [84] và tạo hình ảnh [85]. 1.6. Mô hình tìm kiếm ảnh Trong luận án này đề xuất mô hình tìm kiếm ảnh theo nội dung và ngữ nghĩa dựa trên sự kết hợp cấu trúc RS-Tree và đồ thị tri thức như trong Hình 1.10. Trong mô hình này gồm hai pha: Pha tiền xử lý và pha tìm kiếm. Trong pha tiền: (1) xây dựng cấu trúc dữ liệu lưu trữ và phân cụm dữ liệu ảnh; (2) xây dựng một đồ thị tri thức dùng để lưu trữ và mô tả mối quan hệ ngữ nghĩa của các đối tượng trong hình ảnh. Trong pha tìm kiếm ảnh: quá trình tìm kiếm ảnh theo nội dung và ngữ nghĩa dựa trên sự kết hợp cấu trúc RS-Tree với đồ thị tri thức.
10 Hình 1.10. Mô hình tìm kiếm ảnh kết hợp RS-Tree với đồ thị tri thức 1.7. Các phương pháp tổ chức thực nghiệm và đánh giá Để xác định hiệu quả của các mô hình được đề xuất, các phương pháp tổ chức thực nghiệm và đánh giá trong luận án bao gồm: môi trường thực nghiệm, các tập ảnh và các giá trị đánh giá hiệu suất. 1.8. Tổng kết chương Chương này trình bày tổng quan tìm kiếm ảnh theo nội dung và ngữ nghĩa dựa trên R-Tree và đồ thị tri thức. Các mô hình tìm kiếm ảnh theo tiếp cận cây R-Tree được đề xuất. Ngoài ra, các phương pháp tổ chức thực nghiệm được trình bày bao gồm: môi trường thực nghiệm, tập dữ liệu thực nghiệm và các giá trị đánh giá. Chương 2. TÌM KIẾM ẢNH DỰA TRÊN RS-TREE 2.1. Giới thiệu Trên cơ sở các cấu trúc R-Tree và các biến thể được ứng dụng trong lĩnh vực tìm kiếm ảnh, một cấu trúc cây phân cụm dữ liệu R S- Tree được đề xuất nhằm lưu trữ các véc-tơ đặc trưng cấp thấp của
11 hình ảnh. RS-Tree là cây đa nhánh cân bằng, mỗi nút trên cây được phân cụm dựa vào độ đo tương tự theo phương pháp phân hoạch và phân cấp, đảm bảo khả năng lưu trữ lớn trên cây. 2.2. Cấu trúc cây RS-Tree RS-Tree là cây đa nhánh cân bằng ứng dụng cho bài toán tìm kiếm ảnh tương tự. Cây RS-Tree là cây phân hoạch dữ liệu không gian bao gồm: một nút gốc, một tập nút trong và một tập nút lá. Cho hình ảnh I có véc-tơ đặc trưng ⃗𝐼 = (𝑣 𝐼1 , 𝑣 𝐼2 , 𝑣 𝐼3 , … , 𝑣 𝐼𝑑 ). 𝑓 Trong đó, 𝑣 𝐼𝑖 là các đặc trưng cấp thấp của ảnh I với 𝑖 = 1. . 𝑑 và 𝑣 𝐼𝑖 ∈ [0,1]. Một khối cầu 𝑀𝐵𝑆 của thực thể 𝑠𝑝𝐸𝐷 là khối cầu chứa đối tượng ⃗𝐼 gồm tâm ⃗ 𝑠𝑝 và bán kính 𝑟𝑠𝑝 như sau: 𝑓 𝑐 1) Tâm khối cầu thực thể: ⃗ 𝑠𝑝 = (𝑐 𝐼1 , 𝑐 𝐼2 , 𝑐 𝐼3 , … , 𝑐 𝐼𝑑 ) 𝑐 (2.1) Với 𝑐 𝐼𝑗 = max⁡(0, 𝑣 𝐼𝑗 − 𝑎 𝐼𝑗 ), 𝑗 = 1. . 𝑑 Trong đó, 𝑎 𝐼1 = ⁄ 𝑘 , 𝑎 𝐼2 = 𝑣 𝐼2⁄ 𝑘 , … , 𝑎 𝐼𝑑 = 𝑣 𝐼𝑑⁄ 𝑘, với⁡𝑘 ≥ 2. 𝑣 𝐼1 2) Bán kính khối cầu thực thể: 𝑑 1 𝑟𝑠𝑝 = √∑(𝑐 𝐼𝑗 − 𝑣 𝐼𝑗 )2 (2.2) 𝑑 𝑗=1 Một khối cầu MBS của nút lá 𝑆 𝑙 là khối cầu tối thiểu bao phủ tất cả các phần tử khối cầu thực thể chứa bên trong gồm tâm ⃗ 𝑙 và bán 𝑐 kính 𝑟𝑙 được mô tả như sau: 1) Tâm khối cầu nút lá 𝑆 𝐿 : 𝑘 1 ⃗𝑙 ⁡ = 𝑐 ∑ sp 𝑖 . ⃗ 𝑖 𝑐 (2.3) 𝑘 Trong đó, 𝑠𝑝1 , 𝑠𝑝2 , … 𝑠𝑝 𝑘 ⁡là các phần tử khối cầu thực thể bên 𝑖=1 trong nút lá 𝑆 𝐿 và sp 𝑖 . ⃗⃗⃗𝑖 là tâm của khối cầu sp 𝑖 , với 1 < 𝑖 < 𝑘. 𝑐 2) Bán kính khối cầu nút lá 𝑆 𝐿 : 𝑟𝑙 = Max 𝑖=1..𝑘 {𝑑 𝐸 (𝑐 𝑙 , 𝑠𝑝 𝑖 . ⃗ 𝑖 ) + 𝑠𝑝 𝑖 . 𝑟𝑖 } ⃗ 𝑐 (2.4) Trong đó, 𝑑 𝐸 (𝑐 𝑙 , 𝑠𝑝 𝑖 . ⃗ 𝑖 ) là khoảng cách Euclid từ véc-tơ tâm của ⃗ 𝑐
12 nút 𝑆 𝑙 đến véc-tơ tâm phần tử khối cầu thứ 𝑖 và 𝑠𝑝 𝑖 . 𝑟𝑖 là bán kính phần tử khối cầu thứ 𝑖. Một khối cầu MBS của nút trong 𝑆 𝑁 là khối cầu tối thiểu bao phủ tất cả các khối cầu của các nút trong nhánh cây con gồm véc-tơ tâm ⃗ 𝑛 = (𝑐1 , 𝑐2 , … 𝑐 𝑑 ) và bán kính 𝑟 𝑛 được mô tả như sau: 𝑐 1) Tâm khối cầu nút trong 𝑆 𝑁 : 𝑘 ∑1 𝑆 𝑗 .𝑐 𝑗 .𝑥 𝑖 ×𝑆 𝑗 .𝑤 ⃗ 𝑐𝑖 = 𝑘 ∑1 𝑆 𝑗 .𝑤 , 𝑖 = 1. . 𝑑 (2.5) Trong đó, 𝑗 là số nút con 𝑆1 , 𝑆2 , … , 𝑆 𝑘 của nút trong 𝑆 𝑁 , 𝑑 là số chiều của véc-tơ đặc trưng, 𝑆 𝑗 . ⃗𝑗 . 𝑥 𝑖 là đặc trưng thứ 𝑖 của véc-tơ tâm 𝑐 ⃗ 𝑖 ⁡nút con 𝑆 𝑗 , 𝑆 𝑗 . 𝑤 là số phần tử chứa trong nút 𝑆 𝑗 . 𝑐 2) Bán kính khối cầu nút trong 𝑆 𝑁 : 𝑟 𝑛 = Max 𝑗=1..𝑘 {𝑑 𝐸 (𝑐 𝑛 , 𝑆 𝑗 . ⃗𝑗 ) + 𝑆 𝑗 . 𝑟𝑗 }⁡ ⃗ 𝑐 (2.6) 2.3. Các nguyên tắc thực hiện thao tác trên cấu trúc RS-Tree Để đảm bảo cho việc lưu trữ các đối tượng dữ liệu hình ảnh gia tăng theo thời gian và nâng cao hiệu năng tìm kiếm ảnh. Việc thêm phần tử 𝑠𝑝𝐸𝐷 được thực hiện từ nút gốc theo các nguyên tắc sau: Nguyên tắc 1: Nếu nút 𝑟𝑜𝑜𝑡⁡ = 𝑁𝑢𝑙𝑙 Thực hiện tạo một nút gốc là nút lá gọi là 𝑆 𝐿𝑟 , đưa phần tử khối cầu 𝑠𝑝𝐸𝐷 vào 𝑆 𝐿𝑟 , cập nhật tâm và bán kính của khối cầu. Nguyên tắc 2: Nếu 𝑟𝑜𝑜𝑡⁡ ≠ 𝑁𝑢𝑙𝑙 và 𝑟𝑜𝑜𝑡 là nút lá Tính khoảng cách⁡𝑑𝑖𝑠𝑡 = 𝑑 𝐸 (𝑠𝑝𝐸𝐷. ⃗ 𝑠𝑝 , 𝑆 𝐿𝑟 . ⃗ 𝑟𝑙 ) + 𝑠𝑝𝐸𝐷. 𝑟𝑠𝑝 𝑐 𝑐 • Nếu 𝑑𝑖𝑠𝑡 ≤ 𝜃 + Nếu 𝑟𝑜𝑜𝑡. 𝑐𝑜𝑢𝑛𝑡 < 𝑀: Đưa 𝑠𝑝𝐸𝐷 𝑖 vào 𝑆 𝐿𝑟 , cập nhật tâm và bán kính của 𝑆 𝐿𝑟 . + Nếu 𝑟𝑜𝑜𝑡. 𝑐𝑜𝑢𝑛𝑡 = 𝑀, tiến hành tách nút. • Nếu 𝑑𝑖𝑠𝑡 > 𝜃 Tạo một nút lá mới 𝑆 𝐿𝑛𝑒𝑤 để lưu 𝑠𝑝𝐸𝐷, tạo một nút 𝑟𝑜𝑜𝑡 mới là
13 nút trong gọi là 𝑆 𝑁𝑟 liên kết đến 𝑆 𝐿𝑟 và 𝑆 𝐿𝑛𝑒𝑤 . Nguyên tắc 3: Nếu 𝑟𝑜𝑜𝑡⁡ ≠ 𝑁𝑢𝑙𝑙 và 𝑟𝑜𝑜𝑡 không phải nút lá. Chọn hướng đi từ nút hiện hành đến các nút kế cận và chọn nhánh phù hợp để đi cho đến khi gặp được nút lá hiện hành 𝑆 𝐿𝑐𝑟𝑡 . Tính khoảng cách 𝑑𝑖𝑠𝑡 = 𝑑 𝐸 (𝑠𝑝𝐸𝐷. ⃗ 𝑠𝑝 , 𝑆 𝐿𝑐𝑟𝑡 . ⃗ 𝑙𝑐𝑟𝑡 ) + 𝑠𝑝𝐸𝐷. 𝑟𝑠𝑝 . 𝑐 𝑐 • Nếu 𝑑𝑖𝑠𝑡 ≤ 𝜃 + Nếu 𝑆 𝐿𝑐𝑟𝑡 . 𝑐𝑜𝑢𝑛𝑡 < 𝑀 Đưa 𝑠𝑝𝐸𝐷 vào nút lá hiện hành, cập nhật tâm, bán kính của nút lá hiện hành và cập nhật đến nút gốc. + Nếu 𝑆 𝐿𝑐𝑟𝑡 . 𝑐𝑜𝑢𝑛𝑡 = 𝑀,⁡thực hiện tách nút. • Nếu 𝑑 > 𝜃 Tạo một lá mới 𝑆 𝐿𝑛𝑒𝑤 để lưu phần tử khối cầu 𝑠𝑝𝐸𝐷, thực hiện cập nhật tâm và bán kính khối cầu từ nút lá hiện hành. 2.4. Mô hình hệ tìm kiếm ảnh dựa trên cấu trúc RS-Tree Mô hình tìm kiếm ảnh theo nội dung với một ảnh tìm kiếm đầu vào dựa trên RS-Tree được minh họa như Hình 2.11. Quá trình tìm kiếm ảnh được thực hiện gồm hai pha, pha thứ nhất thực hiện phân cụm và lưu trữ dữ liệu ảnh trên cây RS-Tree, pha thứ hai thực hiện tìm kiếm các hình ảnh tương tự cho ảnh đầu vào. Hình 2.11. Mô hình tìm kiếm ảnh CBIR_RST dựa trên RS-Tree
14 2.5. Thực nghiệm và đánh giá hệ tìm kiếm ảnh CBIR_RST 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 Phương pháp MAP (%) Bibi, R., 2020 [94] 65,29 Ahmed, K. T., 2019 [21] 72,10 Chhabra P., 2020 [95] 77,11 N.T.U. Nhi [96] 67,76 CBIR_RST 79,45 Bảng 2.8. So sánh độ chính xác giữa các phương pháp trên tập ảnh OF17 Phương pháp MAP (%) Ahmed, 2019 [21] 77,10 S. Gao, 2014 [97] 73,43 CBIR_RST 78,69 Bảng 2.9. So sánh độ chính xác giữa các phương pháp trên tập ảnh OF102 Phương pháp MAP (%) Yang, J., 2017 [98] 73,20 Unar, S., 2019 [99] 71,00 Ahmed, K. T., 2019 [20] 71,40 CBIR_RST 73,16 Bảng 2.10. So sánh độ chính xác giữa các phương pháp trên tập ảnh CUB Phương pháp MAP (%) Wei, X. S., 2016 [100] 65,80 Wang, Z., 2018 [101] 66,57 Zeng, H., 2019 [26] 70,10 CBIR_RST 68,17 Hình 2.20. Precision-Recall và ROC của Hình 2.21. Precision-Recall và ROC bộ dữ liệu COREL của bộ dữ liệu OF17
15 Hình 2.22. Precision-Recall và ROC của Hình 2.23. Precision-Recall và ROC bộ dữ liệu OF 102 (1-51) của bộ dữ liệu OF102 (52-102) Hình 2.24. Precision-Recall và ROC của Hình 2.25. Precision-Recall và ROC bộ dữ liệu CUB-200 (1-100) của bộ dữ liệu CUB-200 (101-200) 2.6. Tổng kết chương Trong chương 2, cấu trúc RS-Tree được cải tiến để áp dụng cho bài toán tìm kiếm ảnh tương tự theo nội dung. Kết quả thực nghiệm trong chương 2 được thực hiện trên các tập dữ liệu ảnh đã minh chứng tính hiệu quả của cấu trúc RS-Tree. Tuy nhiên, quá trình tách nút trên cây xảy ra thường xuyên trong quá trình tạo cây dẫn đến một số phần tử tương tự nhau nằm trên các nút lá khác nhau. Điều này ảnh hưởng đến hiệu suất tìm kiếm ảnh. Do đó, các cải tiến trên cấu trúc RS-Tree được thực hiện trong chương 3 để nâng cao hiệu quả tìm kiếm ảnh về độ chính xác. Chương 3. KẾT HỢP RS-TREE VÀ ĐỒ THỊ TRI THỨC TRONG TÌM KIẾM ẢNH 3.1. Giới thiệu Các phương pháp cải tiến cây RS-Tree được đề xuất trong chương này bao gồm: (1) kết hợp RS-Tree và đồ thị cụm láng giềng để nâng
16 cao hiệu quả tìm kiếm ảnh theo nội dung; (2) kết hợp RS-Tree với đồ thị tri thức để nâng cao hiệu quả tìm kiếm ảnh theo ngữ nghĩa. 3.2. RS-Tree kết hợp đồ thị láng giềng Cấu trúc RS-Tree được được hình thành dựa trên tiến trình tách nút trong quá trình tạo cây. Quá trình tách nút thường xuyên sẽ ảnh hưởng đến hiệu quả phân cụm trên cây vì một số phần tử có thể bị tách ra và không được phân bố vào đúng cụm lá của nó. Do đó, để khắc phục khuyết điểm này, một cấu trúc đồ thị láng giềng được tạo ra trong quá trình tạo cấu trúc RS-Tree nhằm nâng cao hiệu quả tìm kiếm ảnh độ chính xác. Cho khối cầu nút lá 𝑆L1 (𝑐1 , 𝑟1 ), 𝑆L2 (𝑐2 , 𝑟2 ) có tâm lần lượt là ⃗1 , ⃗ ⃗ 𝑐 ⃗2 và bán kính lần lượt là 𝑟1 , 𝑟2 . Hai khối cầu 𝑆L1, 𝑆L2 gọi là chồng 𝑐 lấp không gian, ký hiệu là 𝑂𝑣𝑒𝑟𝑙𝑎𝑝(𝑆 𝐿1 , 𝑆 𝐿2 ), khi: 𝑑 𝐸 (𝑆L1 . ⃗1 , 𝑆L2 . ⃗2 ) < 𝑆 𝐿1 . 𝑟1 + 𝑆 𝐿2 . 𝑟2 𝑐 𝑐 (3. 1) với 𝑑 𝐸 là hàm khoảng cách Euclid. Cho hai khối cầu nút lá 𝑆L1 (𝑐1 , 𝑟1 ), 𝑆L2 (𝑐2 , 𝑟2 ) có tâm lần lượt là ⃗ ⃗ ⃗1 , ⃗2 và bán kính lần lượt là 𝑟1 , 𝑟2 . Giả sử 𝑆L1, 𝑆L2 không chồng lấp 𝑐 𝑐 không gian. Khoảng cách của hai vùng không gian 𝑆L1, 𝑆L2, ký hiệu 𝑑𝑖𝑠𝑡 𝑒𝑝𝑠 (𝑆 𝐿1 , 𝑆 𝐿2 ), dist eps = dE (SL1 . c1 , SL2 . c2 )-(SL1 . r1 + SL2 . r2 ) ⃗ ⃗ (3. 2) Cho một nút lá bất kỳ 𝑆Lk, gọi Ο = {𝑠𝑝𝐸𝐷𝑖, 𝑖⁡ = ⁡1. . 𝑀} là các phần tử dữ liệu được lưu trữ trong nút lá 𝑆Lk. Trong đó, M là số lượng phần tử của nút lá 𝑆Lk. Giả sử, labelα là nhãn lớp bất kỳ thuộc tập phân lớp của bộ dữ liệu thực nghiệm. Phân lớp của nút lá 𝑆Lk được xác định như sau: class(SLk ) =< labelα | max{count(spEDi)} , spEDi. label = labelα > (3. 3) Gọi 𝐶 𝑆𝐿 là tập các nút lá trên cấu trúc R -Tree, 𝑆 𝐿𝑘 là một nút lá S bất kỳ 𝑆 𝐿𝑘 ∈ 𝐶 𝑆𝐿 , một ngưỡng ε ∈ (0,1) cho trước, 𝑑 𝐸𝑢 là hàm
17 khoảng cách Euclid, class(𝑆 𝐿𝑘 ) là hàm phân lớp của nút lá 𝑆 𝐿𝑘 . Định nghĩa 3.1. (Các loại láng giềng) 1. Láng giềng 𝑜𝑣𝑒𝑟𝑙𝑎𝑝 của nút lá 𝑆 𝐿𝑘 là tập hợp No (SLk ) = {SL ∈ CSL ⁡\{SLk }|Overlap(SLk , SL )} (3. 4) 2. Láng giềng 𝑒𝑝𝑠𝑖𝑙𝑜𝑛 của nút lá 𝑆 𝐿𝑘 là tập hợp Ne (SLk ) = {SL ∈ CSL ⁡\{SLk }|dist esp (SLk , SL ) ≤ ε} (3. 5) 3. Láng giềng 𝑐𝑙𝑎𝑠𝑠𝑒𝑠 của nút lá 𝑆 𝐿𝑘 là tập hợp Nc (SLk ) = {SL ∈ CSL ⁡|class(SLk ) = class(SL )} (3. 6) 4. Láng giềng của một nút lá 𝑆 𝐿 𝑘 , ký hiệu 𝑁 𝑛 (𝑆 𝐿𝑘 ), là hội của tất cả các phần tử láng giềng overlap, epsilon và classes, có nghĩa là: Nn (SLk ) = No (SLk ) ∪ Ne (SLk ) ∪ Nc (SLk ) (3. 7) Trên cơ sở Định nghĩa 3.1, một đồ thị láng giềng của nút lá 𝑆 𝐿𝑘 được mô tả và được định nghĩa như sau: Định nghĩa 3.2. (Đồ thị láng giềng) Đồ thị láng giềng của nút lá 𝑆 𝐿𝑘 là một đồ thị ký hiệu là 𝐺 𝑁𝐵𝐿 ⁡ =⁡< 𝑉, 𝐸 > trong đó, 𝑉 = {𝑆 𝐿𝑘 } ∪ 𝑁 𝑛 (𝑆 𝐿𝑘 ), 𝐸 = {(𝑣, 𝑣 𝑖 )}|𝑣 = 𝑆 𝐿𝑘 , 𝑣 𝑖 ∈ 𝑉 ∖ {𝑆 𝐿𝑘 }. (3. 8) 3.3. Đồ thị tri thức từ bộ dữ liệu Visual Genome Phần này trình bày tiến trình xây dựng KG để mô tả ngữ nghĩa cho hình ảnh. Một đồ thị tri thức được tạo ra từ các thành phần này bằng cách sử dụng ngôn ngữ OWL bao gồm một tập hợp các đỉnh là các thực thể và tập các cạnh là mối quan hệ giữa chúng. Các đỉnh trên đồ thị tri thức bao gồm bốn loại (1) lớp; (2) cá thể lớp; (3) cá thể đối tượng; (4) cá thể ảnh. Các quan hệ của các đối tượng trong ảnh bao gồm quan hệ không gian, quan hệ hành động, quan hệ động từ miêu tả và quan hệ so sánh.
18 Hình 3.9. Tiến trình xây dựng đồ thị tri thức Một đồ thị tri thức là đồ thị được ký hiệu 𝐺 =< 𝑉, 𝐴, 𝐸 >, trong đó 𝑉 = {𝑣1 , 𝑣2 , … , 𝑣 𝑛 } là tập các đỉnh của đồ thị, 𝑣 i là các nhãn, hoặc các khái niệm, hoặc các thể hiện; 𝐴 = {𝑎1 , 𝑎2 , … , 𝑎 𝑛 } là tập các thuộc tính, 𝑎 𝑖 là tập các thuộc tính hoặc thể hiện; 𝐸 = {𝑒1 , 𝑒2 , … , 𝑒 𝑛 } là tập các cạnh của đồ thị, 𝑒 𝑖 là mối quan hệ giữa khái niệm và cá thể, hoặc mối quan hệ giữa khái niệm và thuộc tính, hoặc mối quan hệ giữa cá thể và thuộc tính hoặc giữa các cá thể. Hình 3.13 Mô hình của đồ thị tri thức Các thành phần trong cấu trúc KG bao gồm: (1) Các loại nút: Phân lớp (Classes), Cá thể (inClass, OBJ, IMG); (2) Các loại mối quan hệ: thuộc tính đối tượng (opOBJinv, opIMGinv, opIMGobj), mối quan hệ giữa các đối tượng (ON, IN, OF, WEAR, RIDE, …); (3) Thuộc tính dữ liệu: inClass, OBJ, IMG; (4) Các chú thích thuộc tính của mối quan hệ (anoRELSynsetID, anoRELPredicate, anoRELRelationID, anoRELWordNet, anoRELDescription).
19 3.4. Hệ tìm kiếm ảnh dựa trên RS-Tree và đồ thị tri thức Trong phần này, một mô hình tìm kiếm hình ảnh dựa trên ngữ nghĩa dựa trên cấu trúc RS-Tree kết hợp đồ thị láng giềng và đồ thị tri thức, đặt tên là SBIR_RSTKG, bao gồm hai pha: Pha thứ nhất: Quá trình xây dựng RS-Tree kết hợp đồ thị láng giềng và đồ thị tri thức; Pha thứ hai: Quá trình tìm kiếm hình ảnh dựa trên ngữ nghĩa được thực hiện trên RS-Tree và các mô tả dữ liệu hình ảnh và tập ảnh tương tự theo ngữ nghĩa. Hình 3.26. Mô hình tìm kiếm ảnh theo ngữ nghĩa sử dụng RS-Tree và KG 3.5. Thực nghiệm và đánh giá Hình 3.34. Precision-Recall và ROC Hình 3.35. Precision-Recall và ROC của bộ dữ liệu COREL của bộ dữ liệu OF17
20 Hình 3.36. Precision-Recall và ROC Hình 3.37. Precision-Recall và ROC của bộ dữ liệu OF102 của bộ dữ liệu CUB-2011-200 Hình 3.38. Precision-Recall và ROC của bộ dữ liệu MS-COCO Hình 3.39. Precision-Recall và ROC Hình 3.40. Precision-Recall và ROC của bộ dữ liệu Dataset 1-VG của bộ dữ liệu Dataset 2-VG Kết quả thực nghiệm trên cấu trúc Knowledge Graph được thể hiện như trong Hình 3.40-3.42. Hình 3.41. Precision-Recall và ROC của bộ dữ liệu MS-COCO Hình 3.42. Precision-Recall và ROC Hình 3.43. Precision-Recall và ROC của bộ dữ liệu Dataset 1 -VG của bộ dữ liệu Dataset 2 -VG