Tổng quan luận án

Tính cấp thiết và khoảng trống nghiên cứu

Trong bối cảnh dữ liệu số phát triển nhanh chóng, dữ liệu đa phương tiện (bao gồm hình ảnh, âm thanh, video, văn bản) gia tăng với khối lượng rất lớn, đặt ra yêu cầu cấp thiết về việc xây dựng các cấu trúc lưu trữ và lập chỉ mục dữ liệu đa chiều nhằm hỗ trợ quá trình tìm kiếm nhanh chóng và chính xác. Các hệ thống tìm kiếm ảnh đã được ứng dụng trong nhiều lĩnh vực thực tiễn như nhận dạng tìm kiếm khuôn mặt trong điều tra hình sự, tìm kiếm ảnh hàng hóa thương mại, chẩn đoán hình ảnh y tế và xử lý ảnh vệ tinh.

Về phương pháp luận, hai hướng tiếp cận tìm kiếm ảnh truyền thống bao gồm:

  • Tìm kiếm ảnh dựa trên văn bản (Text-Based Image Retrieval - TBIR): Phương pháp này thực hiện tìm kiếm ảnh dựa trên việc lập chỉ mục, mô tả và gán nhãn chú thích từ người dùng. Tuy nhiên, TBIR bộc lộ hai hạn chế chính: (1) tốn kém chi phí tài nguyên nhân lực cho việc chú thích thủ công; (2) việc mô tả nội dung hình ảnh mang tính chủ quan của người gán nhãn.
  • Tìm kiếm ảnh theo nội dung (Content-Based Image Retrieval - CBIR): Phương pháp này giải quyết các hạn chế của TBIR thông qua việc trích xuất tự động các đặc trưng thị giác cấp thấp (low-level features) như màu sắc, kết cấu, hình dạng và vị trí không gian để mô tả hình ảnh dưới dạng các véc-tơ đặc trưng đa chiều, sau đó đối sánh bằng các độ đo tương tự. Mặc dù đạt nhiều kết quả khả quan, CBIR tồn tại hạn chế cốt lõi là khoảng cách ngữ nghĩa (semantic gap) giữa các đặc trưng thị giác cấp thấp và khái niệm ngữ nghĩa cấp cao mà người dùng mong muốn.

Bên cạnh đó, việc tổ chức lưu trữ dữ liệu đa chiều cho hệ thống tìm kiếm ảnh thường dựa trên cấu trúc cây phân vùng không gian R-Tree và các biến thể như R+-Tree, R*-Tree, SS-Tree, SR-Tree. Tuy nhiên, các cấu trúc này tồn tại một số hạn chế:

  • Cấu trúc R-Tree nguyên thủy sử dụng các hình chữ nhật bao đóng tối thiểu (Minimum Bounding Rectangle - MBR), dẫn đến vùng không gian bao phủ lớn, mức độ chồng lấp không gian cao, buộc thuật toán tìm kiếm phải duyệt nhiều đường dẫn từ gốc đến lá, làm giảm độ chính xác và tốc độ xử lý.
  • Cấu trúc R*-Tree và SS-Tree sử dụng thuật toán chèn lại phần tử (forced re-insertion) khi gặp nút tràn, dẫn đến việc tái cấu trúc cây tự động gây tốn kém chi phí tính toán. Cấu trúc SS-Tree chỉ hỗ trợ tìm kiếm láng giềng gần nhất mà không hỗ trợ tìm kiếm vùng không gian.
  • Cấu trúc SR-Tree kết hợp cả hình cầu và hình chữ nhật giới hạn trên mỗi nút, làm tăng kích thước nút, phức tạp hóa việc cập nhật và tiêu tốn nhiều dung lượng lưu trữ.

Khoảng trống nghiên cứu được tác giả xác định là: (1) Cần một cấu trúc cây phân cụm dữ liệu không gian tối ưu hóa chi phí tính toán và vùng bao đóng để nâng cao hiệu suất tìm kiếm nội dung; (2) Các công trình tìm kiếm ảnh theo ngữ nghĩa dựa trên đồ thị ngữ cảnh (Scene Graph) trước đây chủ yếu tập trung vào đối sánh đồ thị hoặc mạng nơ-ron đồ thị mà chưa kết hợp đồng bộ giữa tìm kiếm theo nội dung và tìm kiếm theo ngữ nghĩa; (3) Chưa có giải pháp khai thác ngôn ngữ truy vấn chuẩn hóa (như SPARQL) trên Đồ thị tri thức (Knowledge Graph - KG) kết hợp với cấu trúc cây dữ liệu đa chiều để truy vấn hình ảnh.

Mục tiêu nghiên cứu

Mục tiêu tổng quát của luận án là phát triển các mô hình tìm kiếm ảnh tương tự 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 đánh số theo văn bản luận án:

  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à RS-Tree; kết hợp RS-Tree và đồ thị tri thức.

Đối tượng và phạm vi nghiên cứu

  • Đối tượng nghiên cứu: Các cấu trúc cây phân cụm dữ liệu, tạo cấu trúc lưu trữ dữ liệu đa chiều phục vụ cho bài toán tìm kiếm ảnh; các thuật toán tạo cấu trúc dữ liệu và các thuật toán tìm kiếm ảnh; đồ thị tri thức; các tập dữ liệu ảnh phổ biến.
  • Phạm vi nghiên cứu:
    • Về mặt kỹ thuật: 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; các thuật toán xây dựng cây và tìm kiếm trên cây; 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; đồ thị tri thức, ngôn ngữ Web bản thể học OWL (Web Ontology Language), ngôn ngữ truy vấn SPARQL; mạng học sâu Faster-RCNN phục vụ phát hiện đối tượng.
    • Về dữ liệu thực nghiệm: 6 tập dữ liệu ảnh chuẩn gồm COREL, Oxford Flowers 17, Oxford Flowers 102, CUB-2011-200, Visual Genome và MS-COCO.

Tổng quan tài liệu và vị trí của luận án

Các hướng nghiên cứu trước được điểm lại trong văn bản

Tác giả đã hệ thống hóa các công trình nghiên cứu liên quan theo hai hướng tiếp cận chính:

1. Hướng tiếp cận lưu trữ dữ liệu đa chiều và tìm kiếm ảnh theo nội dung (CBIR)

  • Cấu trúc R-Tree và các biến thể:
    • Guttman (1984): Đề xuất cấu trúc R-Tree nguyên thủy dựa trên các hình chữ nhật bao đóng tối thiểu MBR. Hạn chế là mức độ chồng lấp không gian lớn, tốn chi phí cập nhật biên.
    • R+-Tree: Loại bỏ sự chồng lấp không gian bằng cách phân chia đối tượng vào nhiều MBR, nhưng gây trùng lặp dữ liệu và tăng chi phí tính toán khi chèn/xóa.
    • Beckmann và cộng sự (1990) / R*-Tree: Kết hợp tối ưu hóa diện tích, đường biên và độ chồng lấp, áp dụng kỹ thuật chèn lại phần tử khi nút tràn, dẫn đến chi phí tái cấu trúc cây cao.
    • White và Jain (1996) / SS-Tree: Cải tiến từ R*-Tree, thay thế MBR bằng khối cầu bao đóng tối thiểu (Minimum Bounding Sphere - MBS) với tâm là trung bình cộng của các phần tử. Hạn chế là vẫn giữ cơ chế chèn lại gây tái cấu trúc cây và không hỗ trợ tìm kiếm vùng không gian.
    • Katayama và Satoh (1997) / SR-Tree: Kết hợp giao điểm giữa hình cầu MBS và hình chữ nhật MBR. Hạn chế là kích thước nút lớn, chi phí cập nhật phức tạp.
  • Các ứng dụng R-Tree trong tìm kiếm ảnh:
    • Haldurai và cộng sự (2015): Sử dụng R-Tree lưu trữ véc-tơ đặc trưng màu sắc và kết cấu được mờ hóa để tìm kiếm ảnh tương tự.
    • Abd Aziz và cộng sự (2014): Đề xuất phương pháp giảm chiều véc-tơ đặc trưng bằng S-Map (Simple-Map) và tìm kiếm trên R-Tree bằng khoảng cách Euclid.
    • Sharma và cộng sự (2015): Ứng dụng R*-Tree cùng ma trận đồng xuất hiện màu cải tiến (MCCM) và bộ lọc Gabor trên tập dữ liệu hơn 300 ảnh thực vật.
    • Alfarrarjeh và cộng sự (2020): Lập chỉ mục trên R*-Tree phục vụ tìm kiếm ảnh không gian đường phố.
    • Ahmed và cộng sự (2019): Trích xuất đặc trưng màu từ ảnh RGB và đặc trưng hình dạng mức xám nhưng chưa xây dựng cấu trúc phân cụm lưu trữ tối ưu.
    • Kumar và cộng sự (2020): Sử dụng mạng nơ-ron tích chập CNN cho CBIR, đạt hiệu suất cao nhưng chi phí huấn luyện bộ nhớ lớn và chỉ thực nghiệm top-k ($k=1, 5$) dẫn đến độ phủ thấp.

2. Hướng tiếp cận tìm kiếm ảnh theo ngữ nghĩa dựa trên đồ thị ngữ cảnh và đồ thị tri thức

  • Justin Johnson và cộng sự (2015): Đề xuất khái niệm đồ thị ngữ cảnh (Scene Graph - SG) và mô hình trường ngẫu nhiên có điều kiện (CRF) để suy luận ngữ nghĩa hình ảnh trên 5.000 đồ thị ngữ cảnh.
  • Nhóm tác giả nghiên cứu đồ thị trực quan (2018): Xây dựng mô hình tìm kiếm ảnh kết hợp đồ thị ngữ cảnh trực quan (VSG) và đồ thị ngữ cảnh văn bản (TSG) dựa trên đối sánh đồ thị trên tập ảnh Flickr30k và MS-COCO.
  • Nhóm tác giả nghiên cứu mạng đồ thị (2019): Đề xuất phương pháp đo độ tương tự đồ thị ngữ cảnh bằng mạng tích chập đồ thị (Graph Convolutional Network - GCN) trên tập dữ liệu VG-COCO và Flickr30k.
  • Nhóm tác giả nghiên cứu biểu diễn nhị phân (2020): Đề xuất khung tìm kiếm ngữ cảnh đa phương thức dựa trên biểu diễn nhị phân và đồ thị ngữ nghĩa trên 4 tập dữ liệu.
  • Nhóm tác giả nghiên cứu tình huống trực quan (2020): Kết hợp mô hình phân cấp đối tượng với mô hình xác suất quan hệ đa đối tượng trên 500 ảnh từ Visual Genome.
  • Nhóm tác giả nghiên cứu mạng quan hệ (2021): Đề xuất mạng mối quan hệ tập trung (Attentive Relational Network - ARN) gồm mô-đun chuyển đổi ngữ nghĩa và mô-đun tự tập trung (Self-Attention) trên tập Visual Genome.

Khoảng trống luận án lựa chọn giải quyết

Từ việc phân tích tổng quan, luận án tập trung giải quyết các khoảng trống sau:

  1. Cải tiến cấu trúc dữ liệu đa chiều dạng cây bằng cách xây dựng RS-Tree thuần khối cầu MBS, thay thế cơ chế chèn lại gây tái cấu trúc cây của SS-Tree/R*-Tree bằng thuật toán tách nút dựa trên độ lệch sai biệt, kết hợp phân cụm theo ngưỡng $\theta$.
  2. Xử lý hiện tượng chồng lấp không gian giữa các nút lá kề nhau trên cây phân cụm thông qua cấu trúc đồ thị cụm láng giềng NBGraphRST.
  3. Khắc phục khoảng cách ngữ nghĩa bằng cách xây dựng Đồ thị tri thức (KG) mô tả quan hệ ngữ nghĩa đa đối tượng dựa trên tập ảnh Visual Genome, kết hợp tìm kiếm nội dung trên RS-Tree với tìm kiếm ngữ nghĩa bằng câu truy vấn SPARQL trên KG.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết và khái niệm sử dụng

  1. Trích xuất đặc trưng thị giác cấp thấp kết hợp (242 chiều): Để nâng cao độ chính xác so với việc sử dụng đơn lẻ một loại đặc trưng, luận án kết hợp 4 nhóm đặc trưng:

    • Đặc trưng màu sắc MPEG7: 25 chiều.
    • Đặc trưng vị trí Shi-tomasi MPEG7: 25 chiều.
    • Đặc trưng vị trí và kết cấu MaxPooling Sobel: 48 chiều.
    • Đặc trưng hình dạng và kết cấu Sobel HOG (Histograms of Oriented Gradients): 144 chiều.
    • Tổng số chiều véc-tơ đặc trưng là 242 chiều, được chuẩn hóa về đoạn $[0, 1]$.

  2. Độ đo tương tự: Sử dụng độ đo khoảng cách Euclid giữa hai véc-tơ đặc trưng $f_I = (v_{I1}, v_{I2}, ..., v_{Im})$ và $f_J = (v_{J1}, v_{J2}, ..., v_{Jm})$: $$D_{Eu}(I, J) = \sqrt{\sum_{i=1}^m (v_{Ii} - v_{Ji})^2}$$

  3. Mô hình toán học của cấu trúc RS-Tree: RS-Tree là cây đa nhánh cân bằng, phân hoạch dữ liệu bằng các khối cầu bao đóng tối thiểu (Minimum Bounding Sphere - MBS).

    • Thực thể dữ liệu ($sp_{ED}$): Là bộ $\langle MBS, oid \rangle$ chứa véc-tơ đặc trưng $f_I = (v_{I1}, v_{I2}, ..., v_{Id})$ và định danh đối tượng $oid$.
      • Tâm khối cầu thực thể: $\vec{c}{sp} = (c{I1}, c_{I2}, ..., c_{Id})$ với $c_{Ij} = v_{Ij} - a_{Ij}$, trong đó $a_{Ij} = \frac{v_{Ij}}{k}$ ($k \ge 2$ là tham số điều chỉnh độ tịnh tiến của tâm về phía điểm dữ liệu).
      • Bán kính khối cầu thực thể: $r_{sp} = \sqrt{\sum_{j=1}^d (c_{Ij} - v_{Ij})^2}$.
    • Nút lá ($S_L$): Là bộ $\langle MBS, entity \rangle$, chứa từ $m$ đến $M$ thực thể ($1 < m \le M/2$).
      • Tâm nút lá: $\vec{c}L = \frac{1}{k} \sum{i=1}^k sp_i.\vec{c}_i$ ($k$ là số thực thể trong nút).
      • Bán kính nút lá: $r_L = \max_{i=1..k} (D_{Eu}(\vec{c}_L, sp_i.\vec{c}_i) + sp_i.r_i)$.
    • Nút trong ($S_N$): Là bộ $\langle MBS, p \rangle$, chứa từ $2$ đến $N$ con trỏ $p$ trỏ tới các nút con.
      • Tâm nút trong: $\vec{c}n = (c_1, c_2, ..., c_d)$ với $c_i = \frac{\sum{j=1}^k S_j.c_i \cdot S_j.w}{\sum_{j=1}^k S_j.w}$ (trong đó $S_j.w$ là số phần tử chứa trong nhánh cây con $S_j$).
      • Bán kính nút trong: $r_n = \max_{j=1..k} (D_{Eu}(\vec{c}_n, S_j.\vec{c}) + S_j.r)$.

  4. Đồ thị tri thức (Knowledge Graph - KG) và Đồ thị ngữ cảnh (Scene Graph - SG):

    • Đồ thị ngữ cảnh của một hình ảnh được định nghĩa là bộ $G = (O, E)$, trong đó $O = {o_1, ..., o_n}$ là tập các đối tượng ($o_i = (c_i, A_i)$ với $c_i$ là lớp đối tượng, $A_i$ là tập thuộc tính), $E \subseteq O \times R \times O$ là tập các quan hệ giữa các cặp đối tượng.
    • Đồ thị tri thức được tổ chức theo chuẩn Web ngữ nghĩa của W3C: sử dụng URI định danh tài nguyên, biểu diễn dữ liệu bằng bộ ba RDF (Subject - Predicate - Object), định nghĩa cấu trúc phân lớp và thuộc tính bằng ngôn ngữ bản thể học OWL, và thực hiện truy vấn bằng ngôn ngữ SPARQL.
    • Mạng Faster-RCNN được sử dụng để nhận dạng, phân loại và xác định vị trí các đối tượng trong ảnh đầu vào.

Phương pháp nghiên cứu thực tế

  • Phương pháp lý thuyết: Phân tích, mô hình hóa toán học các cấu trúc dữ liệu không gian; thiết kế các thuật toán tạo cây, tách nút, liên kết đồ thị láng giềng và thuật toán xây dựng đồ thị tri thức.
  • Phương pháp thực nghiệm: Hiện thực hóa các mô hình và thuật toán bằng ngôn ngữ lập trình C# trên nền tảng .NET Framework 4.8. Vẽ đồ thị và trực quan hóa kết quả bằng Matlab 2015b.
  • Môi trường phần cứng:
    • Pha tiền xử lý: Máy tính CPU Intel Core i9 thế hệ 9 (8 nhân, 2.3 GHz), bộ nhớ RAM 16GB (2666 MHz), ổ cứng 1TB flash storage.
    • Pha tìm kiếm: Máy tính CPU Intel Core i7-6500U @ 2.50GHz, bộ nhớ RAM, hệ điều hành Windows 10 Pro 64-bit.
  • Tiêu chuẩn và độ đo đánh giá định lượng:
    • Độ chính xác (Precision): $Precision = \frac{|\text{ảnh liên quan} \cap \text{ảnh tìm kiếm được}|}{|\text{ảnh tìm kiếm được}|}$
    • Độ phủ (Recall): $Recall = \frac{|\text{ảnh liên quan} \cap \text{ảnh tìm kiếm được}|}{|\text{ảnh liên quan}|}$
    • Độ đo dung hòa (F-measure): $F\text{-measure} = 2 \cdot \frac{Precision \cdot Recall}{Precision + Recall}$
    • Độ chính xác trung bình (Mean Average Precision - MAP): $MAP = \frac{1}{n} \sum_{i=1}^n P_i$
    • Đường cong đặc tính thu nhận (ROC) và Diện tích dưới đường cong (AUC).
    • Đường cong Precision-Recall (PR curve) và Diện tích dưới đường cong PR (PR-AUC).

Nguồn tư liệu và bộ dữ liệu thực nghiệm

Tác giả sử dụng 6 bộ dữ liệu ảnh thông dụng trong lĩnh vực thị giác máy tính:

STT Tên tập ảnh Số lượng ảnh Số lượng lớp ảnh Dung lượng Đặc điểm dữ liệu
1 COREL 1.000 10 30,3 MB Đơn đối tượng, mỗi chủ đề có đúng 100 ảnh tương tự.
2 Oxford Flowers 17 (OF17) 1.360 17 60,5 MB Đơn đối tượng, mỗi chủ đề chứa khoảng 80 ảnh về một loài hoa.
3 Oxford Flowers 102 (OF102) 8.198 (hoặc 8.788) 102 1,09 GB Đơn đối tượng, 102 loài hoa khác nhau.
4 CUB-2011-200 (CUB) 11.778 200 1,09 GB Đơn đối tượng, 200 loài chim chi tiết.
5 Visual Genome (VG) 108.077 NA 14,47 GB Đa đối tượng, trung bình 35 đối tượng, 50 vùng, 26 thuộc tính, 21 quan hệ/ảnh. Dùng xây dựng KG.
6 MS-COCO 118.287 80 17,9 GB Đa đối tượng, chụp từ các hoạt động hàng ngày. Dùng thực nghiệm tìm kiếm nội dung và ngữ nghĩa.

Nội dung chính theo từng chương

Chương 1: Tổng quan về tìm kiếm ảnh, cấu trúc R-Tree và đồ thị tri thức

Chương 1 thiết lập nền tảng lý thuyết và tổng quan tài liệu cho toàn bộ luận án, bao gồm các nội dung trọng tâm:

  1. Phân tích nguyên lý tìm kiếm ảnh theo nội dung (CBIR): Trình bày 3 cấp độ tìm kiếm trong hệ CBIR theo Eakins: Cấp độ 1 (đặc trưng nguyên thủy), Cấp độ 2 (đối tượng suy luận sơ cấp), Cấp độ 3 (thuộc tính trừu tượng và ngữ nghĩa phức tạp). Luận án chỉ rõ nguồn gốc và bản chất của "semantic gap" giữa Cấp độ 1 và Cấp độ 3.
  2. Kỹ thuật trích xuất đặc trưng và độ đo: Giới thiệu chi tiết các phương pháp trích xuất đặc trưng màu sắc (MPEG7), vị trí (Shi-tomasi), kết cấu (MaxPooling Sobel) và hình dạng (Sobel HOG), hình thành véc-tơ đặc trưng tổng hợp 242 chiều. Khảo sát 5 độ đo khoảng cách: Euclid, Manhattan, Minkowski-Form, Hamming và EMD; xác định độ đo Euclid chuẩn hóa là phù hợp cho mô hình đề xuất.
  3. Cấu trúc R-Tree và các biến thể: Trình bày nguyên lý hình học, cấu trúc nút và thuật toán của R-Tree, R+-Tree, R*-Tree, SS-Tree, SR-Tree; chỉ ra các nhược điểm về chi phí tính toán biên MBR, hiện tượng chồng lấp không gian và chi phí tái cấu trúc cây của phép chèn lại.
  4. Đồ thị tri thức và đồ thị ngữ cảnh: Trình bày lịch sử phát triển từ Semantic Web (Berners-Lee 2001), RDF, OWL, Linked Data đến Knowledge Graph (Google 2012) và Scene Graph (Johnson 2015). Đồ thị ngữ cảnh cung cấp tri thức có cấu trúc biểu diễn đối tượng, thuộc tính và mối quan hệ trong không gian hình ảnh.
  5. Kiến trúc hệ thống tổng quát: Đề xuất sơ đồ kiến trúc cho hai hệ thống: (1) Hệ thống tìm kiếm theo nội dung CBIR-RST dựa trên RS-Tree; (2) Hệ thống tìm kiếm kết hợp nội dung và ngữ nghĩa SBIR_GraphRSTKG dựa trên RS-Tree và Đồ thị tri thức.
  6. Thiết lập thực nghiệm: Mô tả môi trường phần cứng, phần mềm, cấu trúc 6 bộ dữ liệu thực nghiệm và hệ thống các công thức tính toán độ đo hiệu năng ($Precision, Recall, F\text{-measure}, MAP, ROC, AUC, PR\text{-}AUC$).

Chương 2: Tìm kiếm ảnh dựa trên RS-Tree

Chương 2 trình bày chi tiết cấu trúc dữ liệu, các thuật toán thao tác và kết quả thực nghiệm của cấu trúc RS-Tree đề xuất:

  1. Cấu trúc RS-Tree: Là cây phân cụm đa nhánh cân bằng sử dụng hoàn toàn các khối cầu MBS để bao bọc dữ liệu đa chiều. Khối cầu MBS được xác định bởi tâm $\vec{c}$ và bán kính $r$, giúp giảm số biến tính toán so với hình chữ nhật MBR và loại bỏ thao tác tìm biên phức tạp khi cập nhật nút.
  2. Các thao tác và thuật toán trên RS-Tree:
    • Tiêu chí chọn nút lá: Khi thêm một phần tử mới, thuật toán duyệt từ gốc và chọn nút con/nút lá có tâm gần phần tử nhất và làm tăng bán kính khối cầu ít nhất.
    • Cập nhật tâm và bán kính: Cập nhật lại tọa độ tâm và bán kính theo công thức trung bình có trọng số của các phần tử con khi có sự giãn nở không gian.
    • Thuật toán tách nút dựa trên độ lệch sai biệt (variance): Khi một nút lá bị tràn (vượt quá $M$ phần tử), thay vì thực hiện chèn lại phần tử gây tái cấu trúc cây như SS-Tree/R*-Tree, thuật toán đề xuất tính toán độ lệch sai biệt của các phần tử so với hai tâm cụm mới để phân chia phần tử vào hai nút mới, giúp cây duy trì tính cân bằng và giảm thiểu chi phí tính toán.
    • Phân cụm theo ngưỡng $\theta$: Sử dụng ngưỡng tương tự $\theta$ để kiểm soát mức độ kết cụm của các véc-tơ đặc trưng tại từng nút lá.
  3. Mô hình và thuật toán tìm kiếm CBIR-RST: Kết hợp giữa tìm kiếm láng giềng gần nhất (k-NN) và tìm kiếm theo vùng không gian (range query) dựa trên bán kính khối cầu để truy xuất danh sách ảnh tương tự có khoảng cách Euclid nhỏ nhất.
  4. Kết quả thực nghiệm trên các bộ dữ liệu đơn đối tượng:
    • Thực nghiệm được tiến hành trên 4 bộ dữ liệu: COREL (1.000 ảnh), Oxford Flowers 17 (1.360 ảnh), Oxford Flowers 102 (8.198 ảnh) và CUB-2011-200 (11.778 ảnh).
    • Đánh giá thời gian xây dựng cây, thời gian tìm kiếm trung bình, biểu đồ Precision-Recall, đường cong ROC và chỉ số AUC.
    • Các bảng so sánh trong luận án chứng minh hệ thống CBIR-RST đạt thời gian truy vấn ổn định và độ chính xác trung bình (Precision, MAP) cao hơn so với các phương pháp CBIR truyền thống và các biến thể R-Tree trước đó trên cùng tập dữ liệu.

Chương 3: Kết hợp RS-Tree và đồ thị tri thức trong tìm kiếm ảnh

Chương 3 trình bày các cải tiến nâng cao độ chính xác tìm kiếm thông qua việc kết hợp đồ thị láng giềng và Đồ thị tri thức:

  1. Cấu trúc NBGraphRST (Neighbor Graph on RS-Tree):
    • Bản chất: Trong cấu trúc RS-Tree, các nút lá kề nhau có thể có vùng không gian khối cầu chồng lấp hoặc có khoảng cách rất gần nhau, dẫn đến việc bỏ sót các phần tử tương tự nằm ở nút lá lân cận khi tìm kiếm.
    • Thuật toán: Xây dựng đồ thị cụm láng giềng liên kết các nút lá thỏa mãn điều kiện khoảng cách giữa hai tâm nhỏ hơn tổng bán kính của chúng ($D_{Eu}(\vec{c}{L1}, \vec{c}{L2}) \le r_{L1} + r_{L2}$). Cấu trúc này tạo thành hệ thống tìm kiếm CBIR_NBGraphRST, cho phép duyệt nhanh qua các cụm lân cận mà không cần quay lui lên nút cha.
  2. Khung Đồ thị tri thức (Knowledge Graph) cho dữ liệu hình ảnh:
    • Xây dựng Ontology: Thiết kế lược đồ bản thể học OWL định nghĩa các lớp thực thể (IMG - cá thể ảnh, OBJ - cá thể đối tượng, inclass - cá thể lớp phân loại) cùng hệ thống thuộc tính quan hệ (Object Properties biểu diễn quan hệ không gian, tương tác giữa các đối tượng) và thuộc tính dữ liệu (Data Properties biểu diễn tọa độ, kích thước, định danh).
    • Quy trình tạo KG từ Visual Genome: Khai thác 108.077 ảnh từ Visual Genome cùng các chú thích về đối tượng, vùng, thuộc tính và mối quan hệ để khởi tạo đồ thị tri thức dưới dạng các bộ ba RDF lưu trữ tập trung.
  3. Quy trình tìm kiếm ảnh kết hợp nội dung và ngữ nghĩa (SBIR_GraphRSTKG):
    • Pha 1 - Phát hiện đối tượng và trích xuất đặc trưng: Sử dụng mạng Faster-RCNN để phát hiện các đối tượng trong ảnh truy vấn; trích xuất véc-tơ đặc trưng 242 chiều của ảnh.
    • Pha 2 - Tìm kiếm nội dung sơ bộ: Sử dụng cấu trúc RS-Tree kết hợp đồ thị láng giềng (CBIR_NBGraphRST) để lọc ra tập ảnh ứng viên tương đồng về mặt thị giác cấp thấp.
    • Pha 3 - Khai thác ngữ nghĩa và truy vấn SPARQL: Trích xuất đồ thị ngữ cảnh (Scene Graph) của ảnh truy vấn (các đối tượng và mối quan hệ giữa chúng), chuyển đổi thành câu truy vấn SPARQL, sau đó thực thi truy vấn trên Đồ thị tri thức (KG) để chọn lọc và xếp hạng tập ảnh kết quả cuối cùng có sự tương đồng cao về mặt ngữ nghĩa đối tượng và ngữ cảnh.
  4. Kết quả thực nghiệm và đối sánh:
    • Thực nghiệm được triển khai trên tập dữ liệu hoa đơn đối tượng OF102 và hai tập dữ liệu đa đối tượng phức tạp gồm Visual Genome và MS-COCO.
    • Kết quả đánh giá định lượng thông qua các bảng biểu và đồ thị (PR curve, ROC curve, MAP, F-measure) khẳng định mô hình kết hợp SBIR_GraphRSTKG đạt độ chính xác và độ dung hòa vượt trội so với phương pháp chỉ tìm kiếm theo nội dung (CBIR-RST) và các phương pháp đối sánh đồ thị đơn thuần.

Kết quả và những đóng góp mới

Các đóng góp mới về lý luận và thuật toán

  1. Đề xuất cấu trúc cây phân cụm dữ liệu không gian đa chiều RS-Tree: Cải tiến từ SS-Tree và R-Tree bằng việc sử dụng thuần nhất các khối cầu bao đóng tối thiểu MBS, kết hợp tham số tịnh tiến tâm $k$ ($k \ge 2$) và ngưỡng tương tự $\theta$. Đề xuất thuật toán tách nút dựa trên độ lệch sai biệt (variance) thay thế cho cơ chế chèn lại phần tử, giúp loại bỏ hoàn toàn chi phí tái cấu trúc cây và giảm độ phức tạp tính toán khi cập nhật vùng bao.
  2. Đề xuất cấu trúc đồ thị cụm láng giềng trên RS-Tree (NBGraphRST): Giải quyết triệt để hạn chế suy giảm hiệu năng do sự chồng lấp không gian giữa các nút lá kề nhau, hỗ trợ mở rộng không gian tìm kiếm láng giềng trực tiếp giữa các nút lá mà không cần duyệt ngược lên các cấp nút trong.
  3. Xây dựng khung Đồ thị tri thức (KG) chuẩn hóa cho dữ liệu hình ảnh: Thiết lập mô hình bản thể học OWL và quy trình chuyển đổi dữ liệu chú thích đa đối tượng từ tập Visual Genome sang cấu trúc đồ thị tri thức RDF, cho phép lưu trữ và biểu diễn tường minh các mối quan hệ ngữ nghĩa không gian và tương tác giữa các đối tượng trong ảnh.
  4. Đề xuất mô hình tìm kiếm ảnh kết hợp đa mức (SBIR_GraphRSTKG): Thiết lập quy trình tích hợp giữa tìm kiếm đặc trưng cấp thấp dựa trên RS-Tree/NBGraphRST và tìm kiếm ngữ nghĩa cấp cao dựa trên truy vấn SPARQL trên Đồ thị tri thức kết hợp mạng Faster-RCNN, góp phần thu hẹp khoảng cách ngữ nghĩa (semantic gap) trong các hệ thống tìm kiếm ảnh.

Kiến nghị và giải pháp đề xuất

  • Áp dụng mô hình cấu trúc cây phân cụm khối cầu RS-Tree và đồ thị láng giềng NBGraphRST vào các hệ thống quản trị cơ sở dữ liệu đa phương tiện quy mô lớn để nâng cao tốc độ lập chỉ mục và truy xuất dữ liệu đa chiều.
  • Khai thác khung đồ thị tri thức hình ảnh và ngôn ngữ truy vấn SPARQL trong các bài toán thị giác máy tính đòi hỏi suy luận ngữ nghĩa như chú thích ảnh tự động, trả lời câu hỏi dựa trên hình ảnh (VQA) và phân tích tình huống trực quan.

Hạn chế và hướng nghiên cứu tiếp

Hạn chế của luận án

Dựa trên phạm vi nghiên cứu và các điều kiện thực nghiệm được trình bày trong văn bản:

  1. Chi phí thời gian và không gian bộ nhớ trong pha tiền xử lý xây dựng Đồ thị tri thức từ tập dữ liệu quy mô lớn (như Visual Genome với 108.077 ảnh) là tương đối lớn.
  2. Độ chính xác của pha tìm kiếm ngữ nghĩa phụ thuộc một phần vào hiệu năng phát hiện đối tượng của mô hình Faster-RCNN; các trường hợp đối tượng bị che khuất nhiều hoặc kích thước quá nhỏ có thể ảnh hưởng đến chất lượng sinh đồ thị ngữ cảnh.
  3. Phạm vi thực nghiệm của luận án tập trung vào dữ liệu ảnh tĩnh (đơn đối tượng và đa đối tượng), chưa mở rộng kiểm thử trên các luồng dữ liệu đa phương tiện biến đổi theo thời gian thực như video.

Hướng nghiên cứu tiếp

  1. Nghiên cứu mở rộng cấu trúc RS-Tree và Đồ thị tri thức để áp dụng cho bài toán tìm kiếm và phân đoạn video (dữ liệu chuỗi khung hình theo thời gian).
  2. Tối ưu hóa các thuật toán tạo và cập nhật động Đồ thị tri thức khi có sự gia tăng liên tục của các tập dữ liệu ảnh mới mà không cần xây dựng lại toàn bộ đồ thị.
  3. Nghiên cứu nâng cao hiệu năng xử lý của các câu truy vấn SPARQL và thuật toán đối sánh đồ thị con trên các đồ thị tri thức có kích thước cực lớn.

Giá trị tham khảo

Đối tượng thụ hưởng

  • Nghiên cứu sinh, học viên cao học và nhà nghiên cứu: Trong các chuyên ngành Khoa học máy tính, Hệ thống thông tin, Thị giác máy tính, Xử lý ảnh và Web ngữ nghĩa.
  • Giảng viên đại học: Sử dụng làm tài liệu tham khảo chuyên sâu cho các môn học về Cấu trúc dữ liệu nâng cao, Cơ sở dữ liệu đa phương tiện, Xử lý ảnh số và Biểu diễn tri thức.
  • Kỹ sư phát triển phần mềm và kiến trúc sư hệ thống: Các chuyên gia xây dựng các hệ thống tìm kiếm ảnh quy mô lớn trong thương mại điện tử, quản lý hồ sơ y tế, an ninh giám sát và nhận dạng đối tượng.

Các nội dung đáng tham khảo trong luận án

  • Chương 1: Tổng quan chi tiết về cơ chế trích xuất đặc trưng kết hợp 242 chiều và phân tích so sánh lý thuyết giữa các biến thể cây phân vùng không gian (R-Tree, R+-Tree, R*-Tree, SS-Tree, SR-Tree).
  • Chương 2: Hệ thống công thức toán học xác định tâm, bán kính khối cầu MBS ($sp_{ED}, S_L, S_N$), thuật toán chọn nút lá và thuật toán tách nút dựa trên độ lệch sai biệt của cấu trúc RS-Tree.
  • Chương 3: Thiết kế bản thể học OWL, cấu trúc bộ ba RDF biểu diễn ngữ nghĩa hình ảnh, thuật toán tạo đồ thị láng giềng NBGraphRST và mô hình kết hợp Faster-RCNN với truy vấn SPARQL trên Đồ thị tri thức.

Câu hỏi thường gặp

1. Cấu trúc RS-Tree có những cải tiến kỹ thuật cụ thể nào so với R-Tree, SS-Tree và SR-Tree?

RS-Tree sử dụng hoàn toàn các khối cầu bao đóng tối thiểu (MBS) thay vì hình chữ nhật MBR (như R-Tree) hoặc mô hình lai kết hợp cả hai (như SR-Tree), giúp giảm số lượng biến tính toán khi mở rộng không gian và loại bỏ chi phí tìm biên trái/phải khi cập nhật nút. So với SS-Tree, RS-Tree thay thế cơ chế chèn lại phần tử (forced re-insertion) bằng thuật toán tách nút dựa trên độ lệch sai biệt (variance) so với hai tâm cụm mới, loại bỏ chi phí tái cấu trúc cây tự động, đồng thời hỗ trợ cả tìm kiếm láng giềng gần nhất (k-NN) lẫn tìm kiếm vùng không gian.

2. Véc-tơ đặc trưng thị giác 242 chiều trong luận án được tổng hợp từ những thành phần nào?

Véc-tơ đặc trưng 242 chiều được trích xuất từ 4 thành phần thị giác cấp thấp:

  • Đặc trưng màu sắc MPEG7: 25 chiều.
  • Đặc trưng vị trí Shi-tomasi MPEG7: 25 chiều.
  • Đặc trưng vị trí và kết cấu MaxPooling Sobel: 48 chiều.
  • Đặc trưng hình dạng và kết cấu Sobel HOG: 144 chiều. Tất cả các giá trị đặc trưng đều được chuẩn hóa về đoạn $[0, 1]$ trước khi tính toán độ đo khoảng cách Euclid.

3. Cấu trúc đồ thị láng giềng NBGraphRST giải quyết vấn đề gì trong tìm kiếm ảnh?

Trong cấu trúc RS-Tree, các nút lá kề nhau có thể có không gian khối cầu chồng lấp hoặc khoảng cách giữa các tâm rất gần nhau. Khi thực hiện tìm kiếm láng giềng gần nhất, nếu chỉ duyệt cây theo cấu trúc phân cấp thông thường, hệ thống có thể bỏ sót các phần tử tương tự nằm ở nút lá lân cận hoặc phải duyệt ngược lên các nút cha gây tốn thời gian. Cấu trúc NBGraphRST tạo các liên kết trực tiếp giữa các nút lá thỏa mãn điều kiện $D_{Eu}(\vec{c}{L1}, \vec{c}{L2}) \le r_{L1} + r_{L2}$, cho phép thuật toán mở rộng tìm kiếm trực tiếp sang các cụm lân cận.

4. Mô hình SBIR_GraphRSTKG kết hợp tìm kiếm nội dung và tìm kiếm ngữ nghĩa theo quy trình như thế nào?

Mô hình hoạt động theo 3 bước: (1) Ảnh truy vấn được đưa qua mạng Faster-RCNN để nhận dạng đối tượng và đồng thời trích xuất véc-tơ đặc trưng 242 chiều; (2) Hệ thống tìm kiếm theo nội dung trên cấu trúc NBGraphRST để lọc ra tập ảnh ứng viên tương đồng về đặc trưng thị giác cấp thấp; (3) Hệ thống trích xuất đồ thị ngữ cảnh (Scene Graph) của ảnh đầu vào, chuyển đổi thành câu truy vấn SPARQL và thực thi trên Đồ thị tri thức (KG) xây dựng từ Visual Genome để chọn lọc và xếp hạng tập ảnh kết quả có độ chính xác cao về mặt ngữ nghĩa và quan hệ giữa các đối tượng.

5. Vai trò của các bộ dữ liệu Visual Genome và MS-COCO trong luận án là gì?

Tập dữ liệu Visual Genome (108.077 ảnh với các thông tin chi tiết về đối tượng, vùng, thuộc tính và mối quan hệ) được sử dụng làm nguồn dữ liệu nền tảng để xây dựng khung Đồ thị tri thức (KG) bằng ngôn ngữ OWL/RDF. Tập dữ liệu MS-COCO (118.287 ảnh hoạt động thường ngày với 80 lớp đối tượng) được sử dụng để thực nghiệm đánh giá hiệu năng tìm kiếm ảnh đa đối tượng của các mô hình đề xuất (CBIR-RST, CBIR_NBGraphRST và SBIR_GraphRSTKG).

Kết luận

Luận án tiến sĩ của tác giả Lê Thị Vĩnh Thanh đã nghiên cứu và phát triển thành công giải pháp kết hợp cấu trúc dữ liệu đa chiều cải tiến RS-Tree với Đồ thị tri thức nhằm giải quyết bài toán tìm kiếm ảnh tương tự. Bằng việc đề xuất cấu trúc cây khối cầu RS-Tree, cấu trúc đồ thị láng giềng NBGraphRST và mô hình bản thể học OWL biểu diễn ngữ nghĩa hình ảnh trên nguồn dữ liệu Visual Genome, công trình đã tối ưu hóa hiệu suất lập chỉ mục đa chiều và thu hẹp khoảng cách ngữ nghĩa giữa đặc trưng thị giác cấp thấp và khái niệm cấp cao. Các kết quả thực nghiệm toàn diện trên 6 bộ dữ liệu ảnh chuẩn (COREL, OF17, OF102, CUB-2011-200, Visual Genome, MS-COCO) đã chứng minh tính đúng đắn, độ chính xác và tính khả thi của các mô hình và thuật toán được đề xuất trong luận án.