Xem mẫu
- 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.
nguon tai.lieu . vn
