Một phương pháp phân lớp trên cấu trúc KD-Tree cho bài toán tìm kiếm ảnh theo ngữ nghĩa

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

Thêm vào BST

Báo xấu

30
lượt xem 3
download

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

Bài viết trình bày việc thực hiện một phương pháp phân lớp đối tượng theo tiếp cận KD-Tree và áp dụng cho bài toán tìm kiếm ảnh theo ngữ nghĩa. Cấu trúc KD-Tree được xây dựng nhằm phân lớp cho một đối tượng đầu vào dưới dạng véctơ đặc trưng.

Chủ đề:

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

Lưu

Nội dung Text: Một phương pháp phân lớp trên cấu trúc KD-Tree cho bài toán tìm kiếm ảnh theo ngữ nghĩa

Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XIV về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR), TP. HCM, ngày 23-24/12/2021 DOI: 10.15625/vap.2021.0075 MỘT PHƯƠNG PHÁP PHÂN LỚP TRÊN CẤU TRÚC KD-TREE CHO BÀI TOÁN TÌM KIẾM ẢNH THEO NGỮ NGHĨA Nguyễn Thị Định1,3, Văn Thế Thành2, Lê Mạnh Thạnh3* 1 Khoa Công nghệ thông tin, Trường ĐH Công nghiệp thực phẩm TP. Hồ Chí Minh 2 Phòng Quản lý khoa học và đào tạo sau Đại học, Trường ĐH Công nghiệp thực phẩm TP. Hồ Chí Minh 3 Trường Đại học Khoa học, Đại học Huế {dinhnt, thanhvt}@hufi.edu.vn, 3lmthanh@hueuni.edu.vn TÓM TẮT: Trong bài báo này, chúng tôi thực hiện một phương pháp phân lớp đối tượng theo tiếp cận KD-Tree và áp dụng cho bài toán tìm kiếm ảnh theo ngữ nghĩa. Cấu trúc KD-Tree được xây dựng nhằm phân lớp cho một đối tượng đầu vào dưới dạng véctơ đặc trưng. Vì vậy, thuật toán xây dựng cây và phương pháp phân lớp đối tượng dựa trên cấu trúc KD-Tree được đề xuất. Sau đó, chúng tôi thực hiện phân lớp cho mỗi hình ảnh đầu vào, đồng thời tìm tập ảnh tương tự theo ngữ nghĩa. Mỗi ảnh truy vấn được trích xuất véctơ đặc trưng nhằm thực hiện phân lớp trên cấu trúc KD-Tree và tạo câu truy vấn SPARQL để thực hiện tìm kiếm tập ảnh tương tự theo ngữ nghĩa dựa trên Ontology. Trên cơ sở này, chúng tôi đề xuất mô hình tìm kiếm ảnh theo ngữ nghĩa và thực nghiệm trên bộ ảnh COREL, Wang, Image CLEF với độ chính xác lần lượt là 79,98%, 78,10%, 70,16%. Theo kết quả thực nghiệm, phương pháp đề xuất của chúng tôi được so sánh với các công trình được công bố gần đây, đánh giá tính hiệu quả và áp dụng được trong các hệ tìm kiếm dữ liệu đa phương tiện. Từ khóa: KD-Tree, image classification, image retrieval, similar image, Ontology. I. GIỚI THIỆU Phân lớp đối tượng là bài toán được ứng dụng trong nhiều lĩnh vực như nhận dạng mẫu, nhận dạng ký tự, phân loại khách hàng, dự đoán thị trường chứng khoán, phát hiện thư Spam, chẩn đoán y khoa, v.v. giúp con người đưa ra quyết định với từng đối tượng dựa trên các đặc trưng mô tả. Để thực hiện bài toán phân lớp cần xây dựng một mô hình (Model) để phân loại cho một đối tượng đầu vào. Hiện nay, có nhiều phương pháp phân lớp đối tượng được sử dụng như phương pháp tìm kiếm láng giềng gần nhất k-NN (k - Nearest Neighbors) [1, 2], thuật toán SVM (Support Véctơ Machine) [3], thuật toán Navie Bayes [4, 6], cây quyết định (Decision Tree) [5],... đã có những kết quả khả quan. Trong bài báo này, chúng tôi thực hiện một phương pháp phân lớp đối tượng dựa trên cấu trúc KD-Tree (k - Dimensional Tree) được đánh giá là hiệu quả. Theo thống kê của tập đoàn dữ liệu quốc tế IDC (International Data Group) [7] dữ liệu ảnh số tăng lên theo cấp số nhân trong mỗi giây, điều này cho thấy sự cần thiết phải phân loại đối tượng bằng hình ảnh nhằm tăng khả năng tiếp cận và xử lý thông tin. Ảnh số ngày càng gia tăng theo số lượng, điều này đã mang lại cơ hội và thách thức cho lĩnh vực tra cứu ảnh. Bài toán tìm kiếm ảnh tương tự theo ngữ nghĩa là một trong những bài toán quan trọng của nhiều hệ tra cứu dữ liệu đa phương tiện được nhiều nhóm nghiên cứu quan tâm. Trong cách tiếp cận của chúng tôi, một phương pháp phân lớp dữ liệu hình ảnh dựa trên cấu trúc KD-Tree nhằm tạo ra một quá trình phân lớp theo mô hình cây; kết quả phân lớp được ứng dụng cho bài toán tìm kiếm ảnh tương tự theo ngữ nghĩa dựa trên Ontology. Đóng góp của bài báo gồm: (1) Đề xuất một phương pháp phân lớp dữ liệu dựa trên cấu trúc KD-Tree; (2) Đề xuất các thuật toán xây dựng cấu trúc KD-Tree đa nhánh cân bằng, thuật toán gán nhãn cho nút lá, thuật toán huấn luyện trọng số và thuật toán tìm kiếm tập ảnh tương tự dựa trên cấu trúc KD-Tree; (3) Đề xuất mô hình tìm kiếm ảnh theo ngữ nghĩa dựa trên cấu trúc KD-Tree và Ontology; (4) Xây dựng thực nghiệm và chứng minh tính đúng đắn của phương pháp đề xuất dựa trên các bộ dữ liệu ảnh COREL [8], Wang [9], Image CLEF [10]. Phần còn lại của bài báo gồm: Phần II, khảo sát và phân tích ưu nhược điểm của một số công trình liên quan để minh chứng tính khả thi cho bài toán phân lớp dữ liệu dựa trên cấu trúc KD-Tree và tìm kiếm ảnh theo ngữ nghĩa; phần III, trình bày thuật toán xây dựng cấu trúc KD-Tree đa nhánh cân bằng, thuật toán gán nhãn nút lá, thuật toán huấn luyện trọng số cho mô hình phân lớp KD-Tree và thuật toán tìm kiếm tập ảnh tương tự dựa trên cấu trúc KD-Tree; Phần IV trình bày mô hình tìm kiếm ảnh theo ngữ nghĩa dựa trên cấu trúc KD-Tree kết hợp Ontology; Phần V, trình bày kết quả thực nghiệm được đánh giá trên bộ dữ liệu ảnh; Phần VI là kết luận và hướng phát triển tiếp theo. II. CÁC CÔNG TRÌNH LIÊN QUAN Phân lớp đối tượng bằng hình ảnh để áp dụng cho bài toán tìm kiếm ảnh được nhiều công trình công bố dựa trên các kỹ thuật học máy như: sử dụng cấu trúc cây quyết định (Decision Tree) để phân loại cá ngừ đại dương bằng hình ảnh [5]; sử dụng kỹ thuật phân lớp bằng Naïve Bayes [4, 6] để phân loại bạch hầu một cách tự động; nhận diện khuôn mặt bằng cấu trúc KD-Tree kết hợp với thuật toán k-NN [11],... và nhiều công trình khác, cụ thể như sau: Wijayanti Nurul Khotimah và cộng sự (2015) [5] đã thực hiện một phương pháp phân loại cá ngừ đại dương bằng thuật toán cây quyết định (Decision Tree) dựa trên đặc trưng hình ảnh được trích xuất như kết cấu (độ tương phản, sự tương quan, tính đồng nhất,...), hình dạng như tỷ lệ giữa diện tích đầu và diện tích hình tròn, tỷ lệ hình tròn của đầu cá ngừ. Kết quả thực nghiệm đánh giá trên 60 mẫu ảnh cá ngừ loại mắt to, vây vàng và cá vằn. Kết quả đánh
328 MỘT PHƯƠNG PHÁP PHÂN LỚP TRÊN CẤU TRÚC KD-TREE CHO BÀI TOÁN TÌM KIẾM ẢNH THEO NGỮ NGHĨA giá là khá cao với độ chính xác phân lớp là 88%. Tuy nhiên, công trình này chỉ dừng lại ở mức phân loại cá ngừ đại dương và tập ảnh thực nghiệm chưa lớn. Anjali Gautam và cộng sự (2016) [4] thực hiện một phương pháp phân loại tự động bạch cầu bằng cách sử dụng đặc điểm hình thái đối tượng bằng thuật toán Navie Bayes thông qua hình ảnh. Trong công trình này, nhóm tác giả đã sử dụng một ngưỡng đo để phân loại bạch cầu; sau đó sử dụng toán học để loại bỏ các thành phần không giống bạch cầu. Cuối cùng tác giả đã sử dụng thuật toán Navie Bayes để phân loại bạch cầu bằng hình ảnh. Kết quả thực nghiệm với độ chính xác phân loại cho 68 mẫu hình ảnh thì độ chính xác phân lớp là 80,88% và thời gian phân lớp cho mỗi đối tượng bằng hình ảnh trung bình là 22 giây. Tuy nhiên, công trình này chưa áp dụng cho tập mẫu dữ liệu lớn. Yuqian Zhang và cộng sự (2016) [11] sử dụng phương pháp phân lớp ảnh số để nhận diện khuôn mặt. Trong công trình này, mỗi hình ảnh trong tập dữ liệu tại pha huấn luyện được chia thành nhiều vùng; cấu trúc KD-Tree được xây dựng dựa trên tập ảnh phân vùng nhằm phân lớp dữ liệu hình ảnh. Tại pha kiểm thử, mỗi ảnh được chia thành nhiều phân vùng và cấu trúc KD-Tree được sử dụng trong quá trình tìm kiếm theo thuật toán láng giềng gần nhất (k- NN) bằng cách đối sánh các vùng ảnh tìm kiếm với ảnh gốc. Trong công trình này, cây KD-Tree được xây dựng theo cấu trúc chỉ mục đa chiều nhằm giảm thời gian tìm kiếm. Thực nghiệm trên bộ ảnh CUFS (Chinese University Face Sketch) chứng minh rằng phương pháp đề xuất của nhóm tác giả là hiệu quả. Ứng dụng kết quả phân lớp đối tượng vào bài toán tìm kiếm ảnh nhằm mang lại hiệu suất truy vấn cao được nhiều công trình công bố. Trong đó, các công trình tìm kiếm ảnh theo ngữ nghĩa trong thời gian gần đây được nhiều nhóm nghiên cứu quan tâm. Một trong các hướng tiếp cận để thực hiện bài toán tìm kiếm ảnh theo ngữ nghĩa là sử dụng Ontology [12, 13, 15]. Zahid Medmood và cộng sự (2017) [14] thực hiện bài toán tìm kiếm ảnh dựa trên nội dung và phân tích ngữ nghĩa hình ảnh. Từ đó, nhóm tác giả sử dụng véctơ từ thị giác nhằm mô tả ngữ nghĩa thị giác của hình ảnh. Trong công trình này, nhóm tác giả ứng dụng kỹ thuật từ điển dữ liệu để ánh xạ giữa ngữ nghĩa thị giác cấp cao và đặc trưng cấp thấp của hình ảnh. Công trình đã thực nghiệm trên bộ ảnh COREL nhằm minh chứng tính hiệu quả của phương pháp đề xuất. Bên cạnh đó, M. N. Asim và cộng sự (2019), đã thực hiện phương pháp truy xuất thông tin dựa trên Ontology áp dụng cho truy vấn văn bản, dữ liệu đa phương tiện (hình ảnh, video, audio). Trong công trình này, tác giả sử dụng ngôn ngữ bộ ba RDF để thực hiện truy vấn trên Ontology [15], đồng thời so sánh hiệu suất với các phương pháp tiếp cận trước đó được đánh giá là hiệu quả. Từ các công trình nghiên cứu trên cho thấy phương pháp phân lớp dữ liệu ảnh số theo mô hình dạng cây hoặc sử dụng các kỹ thuật học máy (k-NN, SVM,...) kết hợp với cấu trúc KD-Tree là hoàn toàn khả thi và mang lại hiệu suất phân lớp cao. Tuy nhiên, các công trình này mới thực hiện phân lớp dữ liệu hình ảnh dựa trên các kỹ thuật học máy đơn lẻ và chưa thực hiện phân lớp nhiều lần cho một đối tượng theo mô hình Deep Learning. Bên cạnh đó, công trình [21] tác giả đã thực hiện một phương pháp phân lớp hình ảnh theo tiếp cận KD-Tree nhị phân là khả thi và hiệu quả; bên cạnh đó, một số hạn chế còn tồn tại như: (1) cấu trúc KD-Tree xây dựng là cây nhị phân, do đó việc phân lớp với độ chính xác chưa cao nếu quá trình phân lớp của một ảnh bị sai ngay từ nút gốc dẫn đến việc huấn luyện trọng số tốn nhiều chi phí về mặt thời gian; (2) chiều cao cây khá lớn cho các bộ dữ liệu huấn luyện có số phân lớp lớn, điều này ảnh hưởng đến tốc độ tìm kiếm trên cây; (3) cấu trúc KD-Tree xây dựng chưa tăng trưởng theo số phân lớp để phù hợp với các bộ dữ liệu huấn luyện tăng trưởng. Để cải tiến những hạn chế trên, trong bài báo này chúng tôi đề xuất một phương pháp phân lớp đối tượng theo mô hình dạng cây KD-Tree đa nhánh cân bằng, đồng thời ứng dụng tìm kiếm tập ảnh tương tự theo ngữ nghĩa dựa trên cấu trúc KD-Tree và Ontology. Cấu trúc KD-Tree là một dạng phân lớp dữ liệu đa tầng nhằm phân lớp nhiều lần cho một đối tượng, tại mỗi nhánh trên KD-Tree thực hiện một lần phân lớp. Việc phân lớp này dùng để phân cụm dữ liệu và có thể phát hiện được các cụm lân cận nhằm ứng dụng cho bài toán tìm kiếm ảnh. Kết quả của quá trình phân lớp để hình thành các cụm dữ liệu tương đồng tại các nút lá để tìm ra tập ảnh tương tự theo nội dung; trích xuất véctơ từ thị giác, tạo câu truy vấn SPAQL để tra cứu tập ảnh tương tự theo ngữ nghĩa dựa trên Ontology đã xây dựng. III. PHƯƠNG PHÁP XÂY DỰNG CẤU TRÚC KD-TREE CẢI TIẾN A. Mô tả cấu trúc KD-Tree cải tiến Dựa trên tính chất cây KD-Tree nguyên thủy [16], cấu trúc KD-Tree cải tiến được xây dựng là một cây đa nhánh cân bằng, gồm một nút gốc (Root), tập nút trong {Node} và tập nút lá {Leaf} được mô tả như sau: 1) Nút gốc (Root) là nút không có nút cha, lưu trữ véctơ trọng số (w0), có tập nút con trái {left}, tập nút con phải {right} và có một mức trên cây (level): Root = 2) Nút trong (Nodei) là nút có một nút cha (parent), lưu trữ một véctơ trọng số (wi), có tập nút con trái {left}, tập nút con phải {right} và có một mức trên cây (level): Nodei = 3) Nút lá (Leafi) là nút có một nút cha (parent), không có nút con, lưu trữ tập véctơ đa chiều {f1, f2, …, fk}, có một mức trên cây (level) và được gán một nhãn (label): Leafi = 4) Hai nút Nodei và Nodej có quan hệ anh em nếu chúng có cùng một nút cha: Nodei.parent = Nodej.parent 5) Hai nút Nodei và Nodej có quan hệ cha con nếu Nodej.parent = Nodei hoặc Nodei.parent = Nodej 6) Hai nút Nodei và Nodej là đồng cấp nếu Nodei.level = Nodej.level 7) Số nút con trái {left} và số nút con phải {right} tại Nodei là khác nhau: Nodei. {left} ≠ Nodei. {right}
Nguyễn Thị Định, Văn Thế Thành, Lê Mạnh Thạnh 329 Để xây dựng cấu trúc KD-Tree cải tiến cần xác định giá trị đầu ra tại các nút không phải là nút lá. Do đó, tại mỗi Nodei khi truyền vào một véctơ đa chiều fj = (xj1, xj2, …, xjn) giá trị đầu ra được xác định bởi công thức (1) và hàm truyền Sigmoid(x) liên tục tăng và có đạo hàm tại mọi điểm trên miền giá trị [0, 1] được sử dụng xác định bởi công thức (2) nhằm giảm chi phí cho quá trình huấn luyện trọng số lưu trữ tại các nút trong. yij = Sigmoid ( wi * f j ) (1) 1 (2) Sigmoid ( wi * f j ) = −( wi * f j ) 1+ e Điểm cải tiến và đóng góp chính về cấu trúc KD-Tree trong bài báo này là xây dựng cấu trúc KD-Tree cải tiến theo phương pháp phân lớp dữ liệu hình ảnh. Quá trình xây dựng cây nút gốc và các nút trong chỉ lưu véctơ trọng số ban đầu là khởi tạo ngẫu nhiên. Sau đó quá trình huấn luyện trọng số theo thuật toán TWKDT nhằm thực hiện quá trình phân lớp nhiều lần cho một đối tượng tại các tầng trên cây. Nút lá lưu trữ tập ảnh tương tự gọi là các cụm tương đồng. Trong khi đó, cấu trúc KD-Tree nguyên thủy được công bố bởi các công trình trước đây dữ liệu được lưu tại tất cả các nút trên cây hoặc chưa thực hiện phân lớp cho đối tượng nhiều lần và cũng chưa huấn luyện trọng số theo phương pháp học có giám sát theo mô hình phân lớp để hình thành các cụm trên cây. Các quá trình này được trình bày trong phần III.C, III.D, III.E. B. Nguyên tắc xây dựng cấu trúc KD-Tree cải tiến Quá trình xây dựng cấu trúc KD-Tree cải tiến được thực hiện theo các nguyên tắc và ràng buộc sau: Bước 1: Khởi tạo chiều cao cây bằng h, khởi tạo số nhánh tối đa tại mỗi nút trong Nodei KD-Tree là n. Khi đó số nút lá tối đa là nk. Bước 2: Khởi tạo tập véctơ trọng số ngẫu nhiên W = , wi = (wi1, wi2, …, win); trong đó mỗi véctơ wi lưu trữ tại Nodei thuộc tầng thứ i trên cây. Bước 3: Tại mỗi Nodei khởi tạo ngưỡng wi.left = 0.5 và wi.right = 0.5 để cây cân bằng. Bước 4: Giá trị đầu ra của véctơ fj tại Nodei được tính theo công thức (1) và xác định đường đi cho fj đến nhánh kế tiếp theo quy tắc (1). Bước 5: Quá trình ở bước 3, bước 4 lặp lại cho đến khi gặp nút lá Leafk thì chèn fj vào Leafk. Quy tắc 1: Quá trình tạo nhánh con trái, nhánh con phải và tìm nhánh gần nhất được minh họa bởi hình 1; cấu trúc KD-Tree cải tiến hình thành tập véctơ phân lớp từ gốc tới tầng nút trong cuối cùng để tạo thành phân cụm tại nút lá, minh họa bởi Hình 2. Quy tắc này được thực hiện như sau: a) Nếu yij > wi .right thì tạo nhánh con phải; cập nhật ngưỡng phải wi .right = yij . b) Nếu yij < wi .left thì tạo nhánh con trái; cập nhật ngưỡng trái wi .left = yij . c) Nếu wi .left ≤ yij ≤ wi .right thì tìm nhánh có khoảng cách ngắn nhất (dmin) tính từ vị trí yij đến các giá trị ngưỡng wi.left, wi.right thuộc mỗi nút Nodei để xác định đường đi cho véctơ fj. Hình 1. Minh họa quá trình tạo nhánh tại Nodei Hình 2. Minh họa cấu KD-Tree cải tiến C. Thuật toán xây dựng cấu trúc KD-Tree cải tiến Dựa trên mô tả các thành phần của KD-Tree cải tiến trình bày trong phần III.A và nguyên tắc xây dựng được mô tả ở phần III.B, thuật toán xây dựng cấu trúc KD-Tree cải tiến được trình bày như sau:
330 MỘT PHƯƠNG PHÁP PHÂN LỚP TRÊN CẤU TRÚC KD-TREE CHO BÀI TOÁN TÌM KIẾM ẢNH THEO NGỮ NGHĨA Thuật toán xây dựng cấu trúc KD-Tree cải tiến - CKDT 0B Input: Tập véc-tor F = {fi: fi = (xi0, xi1, …, xin); i = 1 ... k}; chiều cao h; số nhánh tối đa n. Bộ trọng số khởi tạo Wkt = {Wi: Wi = (xi0, xi1, …, xin); i = 0 … h-1}; Output: KD-Tree Function CKDT (F,𝑊𝑘𝑡 , ℎ, n) Begin Int h, n; KD-Tree = ∅; For (int i = 0; i
Nguyễn Thị Định, Văn Thế Thành, Lê Mạnh Thạnh 331 Begin ListLeavesAddedLabel = null; Foreach (Leafi in ListLeaves) do Foreach (Labelj in ListLabels) do TS = Count (Labelj, Leafi); EndForeach; EndForEach; For (int i = 0; i < n; i++) do For (int j = 0; j < m; j++) do MT (n, m) = CreateMatrix (NumberofLabel, NumberofLeaf); EndFor; EndFor; For (int i = 0; i < n; i++) do For (int j = 0; j < m; j++) do Repeat SearchMax = VTi , j ; MaxLabel = Value(VTi , j ) ; Leaf j .Label = SetLabel ( Leaf j , Label ,MaxLabel) ; i ListLeafNotAdd = ListLeaf − {Leaf j }; ListLableNotAdd = ListLable − {Lablei } ; ForEach (Labelk in Leafj) do VT (k, j) = 0; EndForeach; ForEach (Leafk in ListLeafNotAdd) do VT (i, k) = 0; EndForeach; Until ( VT (i, j) = 0); EndFor; EndFor; Return {ListLeavesAddedLabel}; End. Độ phức tạp của Thuật toán SL2L là O(l*k). Trong đó, l là số nhãn lớp và k là nút lá trên cây. Khi thực hiện gán nhãn cho nút lá, thuật toán SL2L lần lượt duyệt qua k nút lá trên cây. Trong khi đó, tập dữ liệu ảnh xây dựng cây ban đầu có l nhãn lớp. Mỗi nhãn lớp li trong tập dữ liệu ảnh cần được duyệt để gán cho nút lá Leafj. Do đó, độ phức tạp của Thuật toán SL2L là O(l*k). E. Huấn luyện trọng số Quá trình xây dựng cấu trúc KD-Tree cải tiến với bộ trọng số khởi tạo ban đầu là ngẫu nhiên thu được kết quả phân lớp chưa cao, vì vậy cần phải huấn luyện trọng số để nâng cao kết quả phân lớp hình ảnh. Mô hình phân lớp dạng cây dựa trên cấu trúc KD-Tree cải tiến được huấn luyện theo từng bộ dữ liệu (Ebol) diễn ra song song với quá trình tạo cây. Véctơ trọng số wi = (xi1, xi2, …, xin) tại Nodei được huấn luyện theo đạo hàm ngược hướng Gradient nhằm giảm sai số trung bình dựa trên hàm truyền Sigmoid(x). Trọng số wi tại Nodei được cập nhật theo công thức (3) như sau: ∂ (σ (W * f ) Wi = Wi − σ (Wi * fi ) *η * i i = W − σ (W * f ) *η * σ (W * f ) * (1 − σ (W * f ) i i i i i i i (3) ∂ (W ) i Thuật toán huấn luyện trọng số - TWKDT Input: Bộ trọng số khởi tạo InitWeight Output: Bộ trọng số huấn luyện Weight Function TWKDT (InitWeight, Eboli) Begin Weight = InitWeight; Repeat CKDT (Eboli, InitWeight, h, n); SL2L (KD-Tree, ListLabels); Pi = SumofVectorRightLabel ()/ SumofVectorinEboli (); Road (f.wrong) = LeafWrong.Road; Road (f.right) = LeafRight.Road; Get(Nodew) in Roadf,w; NewWeight = UpdateWeight(Nodew, Roadf,w); CKDT (Eboli, New𝑊eight, h, n); SL2L (KD-Tree, ListLabels); Pj = SumofVectorRightLabel ()/ SumofVectorinEboli (); Until (Pj
332 MỘT PHƯƠNG PHÁP PHÂN LỚP TRÊN CẤU TRÚC KD-TREE CHO BÀI TOÁN TÌM KIẾM ẢNH THEO NGỮ NGHĨA TWKDT là độ phức tạp quá trình tạo cây và gán nhãn cho nút lá. Vì vậy, độ phức tạp của thuật toán TWKDT là O(p*h*m). Trong thuật toán TWKDT, hàm UpdateWeight(Nodew, Roadf,w) nhằm thực hiện huấn luyện trọng số wi = (xi1, xi2, …, xin) tại Nodei theo công thức (4). Tức là thực hiện quá trình điều chỉnh giá trị véctơ trọng số wi và cập nhật giá trị véctơ trọng số mới so với véctơ trọng số cũ trong quá trình huấn luyện với tại Nodei theo công thức (4). Khi đó, véctơ fj sau khi điều chỉnh trọng số wi trên đường đi sẽ được chèn đúng vị trí nút lá Leafk. Kết quả phân lớp trên các tập dữ liệu COREL, Wang, Image CLEF được trình bày trong Bảng 1. Bảng 1. Kết quả huấn luyện hiệu suất phân lớp trên cấu trúc KD-Tree cải tiến Bộ dữ liệu Số ảnh Hiệu suất phân lớp (%) COREL 1.000 82,21 Wang 10.800 80,65 Image CLEF 20.000 79,54 F. Thuật toán tìm kiếm trên cấu trúc KD-Tree cải tiến Quá trình tìm kiếm trên cấu trúc KD-Tree cải tiến để trích xuất tập ảnh tương tự theo nội dung và tạo véctơ từ thị giác làm cơ sở cho quá trình tạo câu truy vấn SPARQL để tìm kiếm ảnh theo ngữ nghĩa dựa trên Ontology. Tập ảnh tương tự là tập các ảnh có độ đo tương tự nhỏ nhất và thuộc về nút lá chứa ảnh đầu vào. Thuật toán tìm kiếm ảnh dựa trên cấu trúc KD-Tree - SKDT Input: Véctơ đặc trưng f j của ảnh I j , KD − Tree Output: Tập ảnh tương tự CI, Véctơ từ VisualWordVector; Function SKDT( f j , KD − Tree ) Begin CI = ∅; VisualWordVector = ∅; For ( int i = 0; i < h-1; i++) do LeftRightofWi = [m..n]; ChildofWi = [Nodem..Noden]; S = Sigmoid(Product(Wi,fj); Foreach (k in LeftRightofWi) do d(S,k) = TinhKC(S,k); If (d(S,k) = dmin)) then SKDT(fj,KD-Tree.Nodek); EndForeach; EndFor; If ( LNode .leaf = true) then CI = CI ∪ LNode .{ f }; i i k VisualWordVector = ExtractVectorWord (CI ); Return {CI,VisualWordVéctơ}; End. Độ phức tạp của thuật toán SKDT là O(h*b). Trong đó, h là chiều cao cây và b là số nhánh tối đa tại Nodei. Thuật toán SKDT lần lượt duyệt qua các tầng của cây KD-Tree cải tiến với chiều cao h từ nút gốc đến nút lá. Tại mỗi Nodei của tầng thứ i, trong trường hợp xấu nhất thì thuật toán SKDT phải duyệt qua danh sách b nhánh con của Nodei. Do đó, độ phức tạp của thuật toán SKDT là O(h*b). Tập ảnh ảnh tương tự của ảnh đầu vào được lưu trữ tại nút lá và được tính theo hàm độ đo tương tự khoảng cách Euclide là ngắn nhất từ ảnh đầu vào với các ảnh tương tự cần tìm kiếm. IV. MÔ HÌNH TÌM KIẾM ẢNH THEO NGỮ NGHĨA DỰA TRÊN CẤU TRÚC KD-TREE CẢI TIẾN VÀ ONTOLOGY Trong mô hình tìm kiếm ảnh theo ngữ nghĩa, một Ontology được sử dụng. Vì vậy, chúng tôi đề cập véctơ từ thị giác, câu truy vấn SPARQL cũng như quá trình tạo Ontology cho bộ dữ liệu thực nghiệm trên phần mềm Protégé. A. Véctơ từ thị giác và câu truy vấn SPARQL Mỗi hình ảnh được biểu diễn bởi một véctơ đặc trưng, gán một nhãn sau khi thực hiện phân lớp trên cấu trúc KD-Tree tức là mỗi ảnh thuộc một phân lớp. Quá trình truy vấn hình ảnh trên cây KD-Tree cải tiến tạo ra tập ảnh tương tự và từ thị giác đại diện cho ảnh truy vấn; đồng thời véctơ từ thị giác được xây dựng dựa vào từ thị giác đã trích xuất. Véctơ từ thị giác là cơ sở tạo câu truy vấn SPARQL nhằm thực hiện tìm kiếm ảnh theo ngữ nghĩa dựa trên Ontology. Véctơ từ thị giác với ảnh truy vấn đầu vào 797.jpg (bộ ảnh COREL) và câu truy vấn SPARQL được xây dựng từ phép toán UNION, AND được minh họa trong Hình 8.
Nguyễn Thị Định, Văn Thế Thành, Lê Mạnh Thạnh 333 B. Ontology cho tập dữ liệu ảnh Mục đích của Ontology là đại diện và mô tả ngữ nghĩa cho hình ảnh; đồng thời để giảm khoảng cách giữa đặc trưng cấp thấp và ngữ nghĩa cấp cao. Dựa vào các phân lớp của các bộ dữ liệu ảnh, phân lớp con được xây dựng. Mỗi hình ảnh là một cá thể/thể hiện (individual/ instance) của một hay nhiều phân lớp trong Ontology. Trong bài báo này, chúng tôi minh họa Ontology bộ ảnh COREL bằng ngôn ngữ bộ ba RDF bởi hình 3, hình 4 bằng phần mềm Protégé. Hình 3. Phân lớp trên bộ ảnh COREL Hình 4. Ontology bộ dữ liệu ảnh COREL xây dựng bởi phần mềm Protégé C. Mô hình truy vấn ảnh theo ngữ nghĩa dựa trên cấu trúc KD-Tree cải tiến và Ontology Hình 5. Mô hình tìm kiếm ảnh theo ngữ nghĩa dựa trên KD-Tree cải tiến Mô hình hệ tìm kiếm ảnh theo nghữ nghĩa dựa trên cấu trúc KD-Tree và Ontology được gồm hai pha: Pha tiền xử lý: Trích xuất đặc trưng và xây dựng cấu trúc KD-Tree cải tiến và Ontology: Bước 1: Trích xuất véctơ đặc trưng của tập dữ liệu ảnh (1). Bước 2: Xây dựng cấu trúc KD-Tree bằng cách huấn luyện trọng số tại nút trong và lưu trữ dữ liệu ảnh tại nút lá (2). Bước 3: Xây dựng Ontology bằng phần mềm Protégé với tập ảnh từ WWW (3), (4). Pha truy vấn: Tìm kiếm tập ảnh tương tự dựa trên cấu trúc KD-Tree, trích xuất véctơ từ thị giác của ảnh truy vấn và thực hiện truy vấn theo ngữ nghĩa dựa trên Ontology bằng câu truy vấn SPARQL. Bước 4: Trích xuất véctơ đặc trưng ảnh cần truy vấn (5); thực hiện tìm kiếm tập ảnh tương tự theo nội dung dựa trên cấu trúc KD-Tree (6). Bước 5: Trích xuất tập ảnh tương tự theo nội dung và véctơ từ thị giác (7), tạo câu truy vấn SPARQL (8). Bước 6: Truy vấn trên Ontology tìm kiếm tập ảnh tương tự theo ngữ nghĩa dựa vào câu SPARQL (9). Bước 7: Trích xuất tập tập ảnh tương tự theo ngữ nghĩa và ngữ nghĩa hình ảnh (10). D. Thuật toán truy vấn ảnh theo ngữ nghĩa Khi truyền một ảnh đầu vào, hệ thống thực hiện tìm kiếm trên cấu trúc KD-Tree kết quả trả về là tập ảnh tương tự theo nội dung, đồng thời trích xuất véctơ từ thị giác để tạo câu truy vấn SPARQL, từ đó làm cơ sở truy vấn ảnh theo
334 MỘT PHƯƠNG PHÁP PHÂN LỚP TRÊN CẤU TRÚC KD-TREE CHO BÀI TOÁN TÌM KIẾM ẢNH THEO NGỮ NGHĨA ngữ nghĩa dựa trên Ontology. Vì vậy, thuật toán truy vấn ảnh theo ngữ nghĩa dựa trên KD-Tree cải tiến và Ontology được trình bày như sau: Thuật toán truy vấn ảnh theo ngữ nghĩa - SOKDT Input: Véctơ từ VisualWordVéctơ của ảnh Ii Output: Tập ảnh tương tự theo ngữ nghĩa SI và phân lớp ngữ nghĩa SC của ảnh Ii Function SOKDT(VisualWordVéctơ) Begin SI = ∅; SC = ∅; SPARQL( I i ) = CreateSPARQL(VisualWordVector ); ( SI , CS ) = Query ( SPARQL( I i ), Ontology); Return {SI , SC}; End. Độ phức tạp của thuật toán SOKDT là O(c*l). Trong đó, c là số phân lớp của ảnh đầu vào (xét trường hợp một ảnh thuộc nhiều phân lớp như bộ ảnh Image CLEF) và l là số phân lớp của tập dữ liệu ảnh xây dựng Ontology. Để tìm kiếm tập ảnh tương tự theo ngữ nghĩa của ảnh đầu vào, thuật toán SOKDT thực hiện tạo câu truy vấn SPARQL từ véctơ từ thị giác (VisualWordVéctơ) đã tìm được từ thuật toán SKDT. Sau đó, câu truy vấn SPARQL được thực hiện truy vấn trên Ontology đã xây dựng để trích xuất tập ảnh tương tự theo ngữ nghĩa của ảnh đầu vào. Vì vậy, độ phức tạp của thuật toán SOKDT là O(c*l). V. THỰC NGHIỆM A. Môi trường xây dựng thực nghiệm Thực nghiệm trích xuất đặc trưng cho tập dữ liệu ảnh minh họa bởi hình 6 được kế thừa từ công trình [21] của cùng nhóm tác giả. Mỗi véctơ đặc trưng được trích xuất gồm 81 thành phần đó là: Đặc trưng màu sắc theo MPEG-7; Đặc trưng cường độ của đối tượng, hình nền, diện tích, hình dạng, biên ảnh; Đặc trưng vị trí tương đối của đối tượng, hình nền theo trục X, Y, theo phép lọc Sobel, phép lọc Laplacian. Xây dựng cây KD-Tree cải tiến minh họa bởi Hình 7 và hệ tìm kiếm ảnh tương tự SB-KDTree minh họa bởi Hình 8, được xây dựng trên nền tảng dotNET Framework 4.5, ngôn ngữ lập trình C#. Các đồ thị được xây dựng trên Mathlab 2015. Cấu hình máy tính: Intel(R) Core™ i5-5200U, CPU 2.2GHz, RAM 16GB và hệ điều hành Windows 10 Professional. Trong bài báo này, chúng tôi tiến hành thực nghiệm trên 3 bộ dữ liệu. Bộ ảnh COREL (gồm 1000 ảnh, 10 phân lớp), bộ ảnh Wang (gồm 10800 ảnh, 80 phân lớp), bộ ảnh Image CLEF (gồm 20000 ảnh, 276 phân lớp). Hình 6. Thực nghiệm trích xuất đặc trưng ảnh Hình 7. Thực nghiệm xây dựng cây KD-Tree cải tiến COREL797.jpg Hình 8. Hệ truy vấn SB-KDTree ảnh COREL101.jpg Hình 9. Kết quả tập ảnh tương tự theo ngữ nghĩa của ảnh COREL101.jpg
Nguyễn Thị Định, Văn Thế Thành, Lê Mạnh Thạnh 335 Kết quả thực nghiệm của phương pháp đề xuất được trình bày trong bảng 2. Trong đó, mỗi bộ ảnh được sử dụng để xây dựng cấu trúc cây KD-Tree cải tiến là khác nhau về chiều cao và số nhánh trên cây; bộ COREL chiều cao cây bằng 2, số nhánh bằng 4 nên thời gian tìm kiếm nhanh hơn so với bộ dữ liệu Wang và Image CLEF. Bảng 2. Hiệu suất tìm kiếm ảnh của phương pháp đề xuất trên các bộ dữ liệu Tập ảnh Độ chính xác Độ phủ trung bình Độ dung hòa Thời gian truy vấn trung bình (%) (%) trung bình (%) trung bình (ms) COREL 79,98 70,43 74,24 28,77 Wang 78,10 65,08 68,69 361,00 Image CLEF 70,16 55,22 60,61 37,60 B. Đánh giá kết quả thực nghiệm Mỗi đường cong trên đồ thị mô tả kết quả truy vấn với độ chính xác (precision) và độ phủ (recall) một chủ đề ảnh trong bộ dữ liệu COREL, Wang và Image CLEF. Đồng thời, đường cong tương ứng trong đồ thị ROC cho biết tỷ lệ kết quả truy vấn đúng và sai, nghĩa là diện tích dưới đường cong này đánh giá được tính đúng đắn của các kết quả truy vấn. Hình 10 - 13 mô tả hiệu suất và tính đúng đắn của kết quả truy vấn trên các bộ ảnh COREL, Wang và Image CLEF. Đồ thị cho thấy tính chính xác của hệ truy vấn tập ảnh COREL nằm tập trung ở vùng [0,72; 1,0]; độ chính xác của tập ảnh Wang nằm tập trung ở vùng [0,68; 1,0] và độ chính xác của tập ảnh Image CLEF nằm tập trung ở vùng [0,65; 1,0]. Đồ thị đường cong ROC biểu diễn các giá trị true positive và false positive theo độ phủ Recall, các giá trị nằm tập trung trên đường cơ sở, nhiều giá trị nằm trong vùng true positive hơn vùng false positive. Hình 10. Precision-Recall và đường cong ROC Hình 11. Precision-Recall và đường cong ROC bộ ảnh Wang (1-40) bộ ảnh COREL Hình 12. Precision-Recall và đường ROC bộ ảnh Wang Hình 13. Precision-Recall và đường cong ROC (41-80) bộ ảnh Image CLEF Thời gian truy vấn trên bộ COREL (ms) Thời gian truy vấn trên bộ ảnh Wang (ms) 70 500 60 50 400 40 300 30 20 200 10 0 100 0 1-10 11- 21- 31- 41- 51- 61- 71- 20 30 40 50 60 70 80 Hình 14. Thời gian truy vấn trung bình trên bộ ảnh COREL Hình 15. Thời gian truy vấn trung bình trên bộ ảnh Wang
336 MỘT PHƯƠNG PHÁP PHÂN LỚP TRÊN CẤU TRÚC KD-TREE CHO BÀI TOÁN TÌM KIẾM ẢNH THEO NGỮ NGHĨA Thời gian truy vấn trên bộ ảnh Image CLEF (ms) 600 500 400 300 200 100 0 00 02 04 06 08 10 12 14 16 18 20 22 24 26 30 32 34 36 38 40 Hình 16. Thời gian truy vấn trung bình bộ ảnh Image CLEF Để minh chứng cho mô hình truy vấn ảnh theo ngữ nghĩa đề xuất là hiệu quả, chúng tôi so sánh kết quả thực nghiệm với một số công trình gần đây trên cùng bộ dữ liệu trong Bảng 3 - Bảng 5. Kết quả so sánh này cho thấy, việc ứng dụng cấu trúc KD-Tree cải tiến nhằm phân lớp dữ liệu hình ảnh và ứng dụng cho bài toán tìm kiếm ảnh theo ngữ nghĩa là hoàn toàn khả thi và hiệu quả. Bảng 3. So sánh hiệu suất truy vấn giữa các phương pháp trên bộ dữ liệu COREL Phương pháp Bộ dữ liệu Độ chính xác trung bình (%) B_SHIFT, 2016 [17] COREL 72,00 CBIR-CKDT, 2021 [21] COREL 76,40 SB-KDTree COREL 79,98 Bảng 4. So sánh hiệu suất truy vấn giữa các phương pháp trên bộ dữ liệu Wang Phương pháp Bộ dữ liệu Độ chính xác trung bình (%) P. CHHABRA, 2020 [18] Wang 63,20 CBIR-CKDT, 2021 [21] Wang 73,27 SB-KDTree Wang 78,10 Bảng 5. So sánh hiệu suất truy vấn giữa các phương pháp trên bộ dữ liệu Image CLEF Phương pháp Bộ dữ liệu Độ chính xác trung bình (%) H. Cevikalp, 2017 [19] Image CLEF 46,78 MLP, 2018 [20] Image CLEF 42,20 SB-KDTree Image CLEF 70,16 Theo kết quả thực nghiệm cho thấy, hệ truy vấn ảnh SB-KDTree với hiệu suất truy vấn các hơn các công trình cùng bộ dữ liệu là bởi các lý do sau: 1) Hệ truy vấn ảnh SB-KDTree thực hiện phân lớp ảnh trước khi tìm kiếm ảnh. 2) Quá trình phân lớp theo cấu trúc KD-Tree được thực hiện nhiều lần cho từng đối tượng, tại mỗi tầng trên cây thực hiện phân lớp một lần nên hiệu suất phân lớp cao. 3) Kết hợp một cấu trúc dữ liệu lưu trữ và Ontology đã nâng cao hiệu suất tìm kiếm ảnh theo ngữ nghĩa. 4) Thời gian tìm kiếm nhanh hơn các hệ truy vấn khác do quá trình thực hiện tìm kiếm ổn định trên cấu trúc KD- Tree. VI. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Trong bài báo này, chúng tôi đã thực hiện một phương pháp phân lớp đối tượng bằng câu trúc KD-Tree đa nhánh cân bằng; đồng thời ứng dụng cho bài toán tìm kiếm ảnh theo ngữ nghĩa. Cấu trúc KD-Tree cải tiến được xây dựng làm cơ sở cho việc phân lớp đầu vào và tìm kiếm tập ảnh tương tự theo nội dung. Câu truy vấn SPARQL được xây dựng trên cơ sở phân lớp ảnh đầu vào và thực hiện truy vấn trên Ontology. Thực nghiệm được xây dựng trên các bộ ảnh COREL, Wang và Image CLEF để minh chứng tính khả thi của phương pháp được chúng tôi đề xuất. Kết quả thực nghiệm được đánh giá dựa trên độ chính xác, độ phủ, độ dung hòa và so sánh với các công trình đã công bố. Kết quả độ chính xác trung bình tương ứng từng bộ ảnh lần lượt là: 79,98%, 78,10% và 70,16%. Kết quả này minh chứng cho phương pháp đề xuất là hiệu quả và có thể áp dụng được cho các hệ thống tìm kiếm ảnh thuộc các lĩnh vực khác
Nguyễn Thị Định, Văn Thế Thành, Lê Mạnh Thạnh 337 nhau. Hướng phát triển tiếp theo, chúng tôi sẽ xây dựng một mô hình phân lớp trong đó cấu trúc KD-Tree tại các nút lá phát triển thành một cây KD-Tree nhằm tăng hiệu suất phân lớp trên mô hình này; đồng thời áp dụng cho bài toán tìm kiếm ảnh theo ngữ nghĩa. VII. LỜI CẢM ƠN Chúng tôi xin trân trọng cám ơn Khoa Công nghệ thông tin - Trường Đại học Khoa học - Đại học Huế, nhóm nghiên cứu SBIR-HCM đã góp ý chuyên môn cho nghiên cứu này. Chúng tôi xin trân trọng cảm ơn Trường Đại học Công nghiệp thực phẩm TP. HCM, Trường Đại học Sư phạm TP. HCM đã tạo điều kiện về cơ sở vật chất giúp chúng tôi hoàn thành bài nghiên cứu này. TÀI LIỆU THAM KHẢO [1] Hou, Wenfeng, et al. “An advanced k nearest neighbor classification algorithm based on KD-tree”, IEEE International Conference of Safety Produce Informatization (IICSPI). IEEE, 2018. [2] Setiawan, Dedi. “Mosque Search with Kd-Tree Nearest Neighbor Case Studies and Field District of Johor”, 2020. [3] Gao, Dan, Yan-Xia Zhang, and Yong-Heng Zhao. “Support véctơ machines and KD-tree for separating quasars from large survey data bases”, Monthly Notices of the Royal Astronomical Society 386.3: 1417-1425, 2008. [4] Gautam, Anjali, et al. “Automatic classification of leukocytes using morphological features and naïve Bayes classifier”, region 10 conference (TENCON). IEEE, 2016. [5] Khotimah, Wijayanti Nurul, et al. “Tuna fish classification using decision tree algorithm and image processing method”, 2015 International Conference on Computer, Control, Informatics and its Applications (IC3INA). IEEE, 2015. [6] McCann, Sancho, and David G. Lowe. “Local naive bayes nearest neighbor for image classification”, Conference on Computer Vision and Pattern Recognition. IEEE, 2012. [7] A Patrizio, “Data center explorer”, Network World, 03/12/2018, https://www.networkworld.com/article/3325397/idc-expect- 175-zettabytes-of-data-worldwide-by-2025.html. [8] Corel 1k Database, http://wang.ist.psu.edu/docs/related/. (n.d.). [9] Wang, J. Z. (n.d.). James Z. Wang Group. http://wang.ist.psu.edu/docs/home.shtml. [10] Image CLEF Database, https://www.imageclef.org/datasets. [11] Zhang, Yuqian, et al., “Fast face sketch synthesis via KD-tree search”, European Conference on Computer Vision. Springer, Cham, 2016. [12] Zhong, Botao, et al., Ontology-based semantic modeling of knowledge in construction: classification and identification of hazards implied in images, Journal of Construction Engineering and Management, 146.4: 04020013, 2020. [13] Shati, Narjis Mezaal; Khalid Ibrahim, Noor; Hasan, Taha Mohammed, A review of image retrieval based on Ontology model, Journal of Al-Qadisiyah for Computer Science and Mathematics, 2020, 12.1: pp. 10-14. [14] Mehmood, Zahid; Mahmood, Toqeer; Javid, Muhammad Arshad. Content-based image retrieval and semantic automatic image annotation based on the weighted average of triangular histograms using support véctơ machine. Applied Intelligence, 48.1: 166-181, 2018. [15] Asim, Muhammad Nabeel, et al., The use of Ontology in retrieval: a study on textual, multilingual, and multimedia retrieval, IEEE Access, 7: 21662-21686, 2019. [16] Bentley, Jon Louis. “Multidimensional binary search trees used for associative searching”, Communications of the ACM 18.9 (1975): 509-517. [17] Douik, Ali, Mehrez Abdellaoui, and Leila Kabbai. “Content based image retrieval using local and global features descriptor”, 2nd International Conference on Advanced Technologies for Signal and Image Processing (ATSIP). IEEE, 2016. [18] Chhabra, Payal, Naresh Kumar Garg, and Munish Kumar. “Content-based image retrieval system using ORB and SIFT features”, Neural Computing and Applications 32.7: 2725-2733, 2020. [19] Cevikalp, H., Elmas, M., & Ozkan, S., Large-scale image retrieval using transductive support vector machines. Computer Vision and Image Understanding, 173, 2-12, 2018. [20] Seymour, Z., & Zhang, Z., Image annotation retrieval with text-domain label denoising. Proceedings of the 2018 ACM on International Conference on Multimedia Retrieval, pp. 240-248, 2018, June. [21] Nguyễn Thị Định, Văn Thế Thành, Lê Mạnh Thạnh, “Phân lớp ảnh bằng cây KD-Tree cho bài toán tìm kiếm ảnh tương tự”, Chuyên san Các công trình nghiên cứu, phát triển và ứng dụng công nghệ thông tin và truyền thông, tập 2021, số 1, 2021.
338 MỘT PHƯƠNG PHÁP PHÂN LỚP TRÊN CẤU TRÚC KD-TREE CHO BÀI TOÁN TÌM KIẾM ẢNH THEO NGỮ NGHĨA A METHOD OF IMAGE CLASSIFICATION BASE ON KD-TREE STRUCTURE FOR SEMANTIC-BASED IMAGE RETRIEVAL SYSTEM Nguyen Thi Dinh, Van The Thanh, Le Manh Thanh ABSTRACT: In this paper, we perform an object classification method accords with the KD-Tree (K - Dimensional Tree) and apply to the semantic-based image retrieval system. KD-Tree structure is built to classify an input object as the feature véctơ. Therefore, the tree construction algorithm and object classification method based on KD-Tree structure are proposed. Then, we perform classification for each input image, and also retrieve a similar images by semantic. Each queried image is extracted a feature véctơ to classify on KD-Tree structure and generated SPARQL query to retrieve a similar images by semantic based on Ontology. On the base of this theory, we propose a semantic-based image retrieval model and experiment it on COREL, Wang, Image CLEF. According to the experimental results, our proposed method is compared with the recent published work, evaluated its effectiveness, and also applied in the data multimedia retrieval systems.