TÌM KIẾM ẢNH THEO NGỮ NGHĨA DỰA TRÊN CẤU TRÚC iRS-TREE VÀ ONTOLOGY

jos.hueuni.edu.vn Tập 131, Số 2A, 2022 167 Mô tả cấu trúc cây phân cụm iRS-Tree RS-Tree [21] được xây dựng dựa trên cấu trúc SS-Tree [22]. Cách tính véc-tơ tâm của khối cầu nút lá và nút trong trên RS-Tree tương tự với SS-Tree. Các cải tiến trên RS-Tree bao gồm: (1) tạo một khối cầu không gian để lưu trữ véc-tơ đặc trưng của hình ảnh; (2) cải tiến thuật toán tách nút dựa trên một độ đo sai biệt giữa các phần tử; (3) đề xuất một ngưỡng để gom cụm các dữ liệu tương tự; (4) kết hợp truy vấn láng giềng gần nhất và truy vấn vùng không gian. 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ự. Việc gom nhóm dữ liệu được thực hiện trên từng nút của cây RS-Tree dựa vào độ đo tương tự giữa các véc- tơ đặc trưng ảnh ngưỡng θ cho trước nhằm tạo ra một cây đa nhánh cân bằng để giảm thời gian tìm kiếm. 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á. Mỗi nút trong 𝑆node trên cây là một khối cầu MBS (Minimun Bounding Sphere) bao phủ tất cả khối cầu các nút thuộc nhánh cây con. Mỗi nút lá 𝑆leaf trên cây gồm một tập các thực thể; mỗi thực thể 𝑠𝑝𝐸𝐷 là một khối cầu chứa không gian đối tượng dữ liệu và định danh đối tượng. Việc tách nút thường xuyên sẽ làm chậm quá trình tạo cây. Do đó, để nâng cao hiệu quả gom cụm và cải thiện thời gian tạo cây, chúng tôi xây dựng cấu trúc iRS-Tree, được cải tiến từ RS- Tree. Các cải tiến trong cấu trúc iRS-Tree bao gồm: Thứ nhất, việc thêm một phần tử spEDi vào iRS-Tree được thực hiện theo các nguyên tắ c

tương tự RS-Tree. Tuy nhiên, khi gặp một nút lá đầy, thay vì thực hiện tách nút, một phần tử xa tâm nhất của nút lá hiện hành nhất, ký hiệu là 𝑠𝑝𝐸𝐷𝑘, được chọn để thêm vào một nút lá khác có cùng cha. Nút lá được chọn để thêm vào thỏa mãn hai tiêu chí sau: (1) nút lá được chọn có số phần tử nhỏ hơn 𝑀; (2) khoảng cách Euclidean từ tâm của phần tử 𝑠𝑝𝐸𝐷𝑘 đến tâm của phần tử nút lá được chọn nhỏ hơn hoặc bằng Trường hợp có nhiều nút lá thõa mãn hai tiêu chí trên nút lá có khoảng cách Euclidean ngắn nhất sẽ được chọn. Ngược lại, nếu không tồn tại nút lá nào thỏa mãn hai tiêu chí này thì thực hiện tách nút. Quá trình thêm phần tử iRS-Tree vào được mình họa trên Hình 7. Hình 7 mô tả quá trình thêm phần tử spEDi vào cây iRS-Tree. Sleaf5 là nút lá được lựa chọn để thêm phần tử spEDi. Trong trường hợp nút lá Sleaf5 đầy, phần tử spEDk là phần tử xa nhất được chọn để thêm vào nút lá gần nhất Sleaf2. Thứ hai, khi một nút lá bị tràn, phương pháp k-Means được sử dụng để thực hiện tách nút thành k cụm (𝑘 ≥ 2). Việc này nhằm tối ưu hóa độ tương tự của các đối tượng không gian trong một cụm, đồng thời giảm thiểu độ tương tự giữa các cụm khác nhau. Các phần tử trong nút tràn sẽ được phân hoạch thành 𝑘 cụm theo độ đo tương đồng (Hình 8).