Một phương pháp phân cụm dựa trên cây KD -Tree cho bài toán tìm kiếm ảnh

con trái và 
chiều cao cây con phải ℎ푙 = ℎ = . Vậy BKD-Tree được xây dựng là một cây nhị phân cân bằng, 
các phần tử trên cùng một nút lá thì phù hợp về độ đo tương tự, nghĩa là các phần tử thuộc một 
nút lá có độ tương tự nhiều hơn so với các phần tử khác nút lá. Mỗi véc-tơ đặc trưng 푖 của ảnh I 
có tính chất sau: 
 Định lý. Tồn tại duy nhất một nút lá trên cây BKD-Tree để lưu trữ véc-tơ đặc trưng 푖. 
 Chứng minh: 
 Tính tồn tại: Vì BKD-Tree là cây nhị phân cân bằng, dữ liệu chỉ lưu trữ tại nút lá. Do đó, 
tại mỗi nút trong của cây BKD-Tree luôn tồn tại một nhánh con trái hoặc một nhánh con phải để 
véc-tơ 푖 tìm đến vị trí của nút lá. Do đó, luôn tồn tại nút lá để lưu trữ véc-tơ 푖. 
 Tính duy nhất: Duyệt từ nút gốc của cây, tại mỗi nút trong thuộc cây BKD-Tree, ta chỉ chọn 
được duy nhất một hướng (trái hoặc phải) để tìm vị trí lưu trữ vec-tơ đặc trưng 푖. Do đó, ta chỉ 
chọn được một nút lá để lưu trữ vec-tơ 푖, nghĩa là vec-tơ 푖 chỉ thuộc về một nút lá duy nhất. 
3.3 Thuật toán tạo cây BKD-Tree 
 Input: Tập phần tử 푣 cần thêm vào cây BKD-Tree; 
 Output: Cây BKD-Tree; 
 Function IEBKT ( 푣, 퐾 − 푒푒, m) 
 Begin 
 퐾 − 푒푒 = ∅; 
 푡 = ( 푡 0, , 푡 1  , 푡 푙); 푡 푖 = 푣 { 푗푖: 푖 = 0. . ( − 1); 푗 = 0. . ( − 1)}; 
 53 
Nguyễn Thị Định và CS. Tập 129, Số 2A, 2020 
 표표푡. = 푡 0; 푙0 = 0; 
 If ( 푣. 푣푖 < 푡 . 푡 푖) then BKD-Tree = BKD-Tree ∪ IEBKT ( 푣, BKD-Tree.left, m+1) 
 Else BKD-Tree = BKD-Tree ∪ IEBKT (( 푣, BKD-Tree.right, m+1) 
 EndIf 
 Return BKD-Tree; 
 End. 
 Mệnh đề 1. Độ phức tạp của thuật toán IEBKT là (푛). Với n số phần tử trên cây BKD-
Tree. 
 Chứng minh: Gọi m, n lần lược là chiều cao và số phần tử cần chèn vào cây BKD-Tree. Mỗi 
phần tử 푣 cần chèn vào cây, thuật toán IEBKT duyệt qua m mức của cây nhằm tìm được nút lá 
phù hợp để lưu trữ phần tử. Do đó, số phép toán so sánh của thuật toán là m*n. Trong trường 
hợp này, chiều cao của cây BKD-Tree giới hạn là m = k (với k là một số cho trước). Vậy độ phức 
tạp của Thuật toán IEBKT là (푛) ◼ 
4 Truy vấn ảnh dựa trên cây BKD-Tree 
4.1 Mô hình truy vấn ảnh dựa trên cây BKD-Tree 
 Các vùng ảnh phân đoạn của ảnh 2092.JPG được minh họa như Hình 3. 
 Hình 3. Ảnh gốc và các vùng của ảnh đã phân đoạn 
 Trên cở sở xây dựng thuật toán tạo cây BKD-Tree (IEBKT), thuật toán truy vấn ảnh trên 
cây được thực hiện bằng cách: Mỗi vùng ảnh được trích xuất một véc-tơ đặc trưng, quá trình truy 
vấn để tìm ra tập ảnh tương tự của hình ảnh được thực hiện dựa vào véc-tơ đặc trưng từng vùng 
của ảnh cần truy vấn. Hệ thống thực hiện tìm kiếm ảnh tương tự bằng cách so sánh véc-tơ đặc 
trưng = ( 0, , 1  , ( −1)) của mỗi vùng ảnh truy vấn với các thành phần tương ứng của vec-
tơ trung bình 푡 = ( 푡 0, , 푡 1  , 푡 ( −1)) trên cây BKD-Tree theo hướng từ nút gốc đến nút lá và 
theo quy tắc xây dựng cây BKD-Tree. Kết quả của quá trình này là tập hợp các nút lá chứa véc-tơ 
đặc trưng của từng vùng thuộc ảnh cần truy vấn. 
54 
jos.hueuni.edu.vn Tập 129, Số 2A, 2020 
 Thuật toán IRBKD (truy vấn ảnh trên cây BKD-Tree ) 
 Input: Tập véc-tơ 푖 của ảnh 푄, cây BKD-Tree 
 Output: Tập nút lá 퐿푖 chứa phần tử 푖 
 Function IRBKT ( 푖, BKD-Tree, m) 
 Begin 
 푅푒푠 푙푡 = ∅ ; 
 Foreach ( 푖 ∈ ) do 
 If ( 푖 ∈ 푙푒 ) then 푅푒푠 푙푡 = 푅푒푠 푙푡 ∪ 퐿푖; 
 ElseIf 
 If ( 푖. 푖 < 푡 . 푡 ) then IRBKT ( 푖, BKD-Tree.left, m+1); 
 ElseIf IRBKT ( 푖, BKD-Tree.right, m+1); 
 EndIf 
 End Foreach 
 Return Result; 
 End. 
 Mệnh đề 2. Độ phức tạp của thuật toán IRBKT là (푙표 (푛)). Với 푛 là số phần được lưu trữ 
trên cây BKD-Tree. 
 Chứng minh: Thuật toán IRBKT lần lượt duyệt qua m mức của cây từ nút gốc đến nút lá 
thì độ phức tạp là ( ). Tại mỗi mức trên cây thực hiện so sánh giá trị tại nút trong của cây với 
thành phần thứ i của vec-tơ 푗. Hơn nửa BKD-Tree là cây nhị phân tìm kiếm cân bằng, chiều cao 
là m = k (với k là một số cho trước). Do đó, với cây BKD-Tree có n phần tử thì độ phức tạp khi tìm 
kiếm một phần tử trên cây là (푙표 (푛)). ◼ 
 Mô hình tìm kiếm ảnh tương tự dựa trên cây BKD-Tree được đề xuất như sau: 
 55 
Nguyễn Thị Định và CS. Tập 129, Số 2A, 2020 
 Hình 4. Mô hình truy vấn ảnh theo nội dung dựa trên cây BKD-Tree 
 Pha tiền xử lý: 
 Bước 1. Trích xuất tập véc-tơ đặc trưng 푣 của bộ dữ liệu ảnh, mỗi véc-tơ đặc trưng có n 
thành phần, mỗi thành phần là một giá trị mô tả một đặc trưng của hình ảnh. 
 Bước 2. Gom cụm các véc-tơ đặc trưng 푣 trên cây BKD-Tree. Nghĩa là, mỗi véc-tơ đặc trưng 
 푣 = ( 푣0, , 푣1  , 푣( −1)), thành phần 푣푖 được so sánh với giá trị nút trong tại mức 푖. Nếu 푣푖 ≥
 푡 푖 thì 푣 thuộc cây con bên phải; ngược lại 푣 thuộc cây con bên trái. Do đó, véc-tơ 푣 được chọn 
hướng ngay nút lá tại mỗi mức trên cây. 
 Pha truy vấn: 
 Bước 1. Với mỗi hình ảnh truy vấn, trích xuất các véc-tơ đặc trưng 푣푖. Trong đó 푣푖 là véc-
tơ có n thành phần, mỗi thành phần là một giá trị mô tả đặc trưng của ảnh phân đoạn. 
 Bước 2. Sử dụng véc-tơ 푣푖 truy vấn ảnh tương tự trên cây BKD-Tree. Kết quả của quá trình 
truy vấn này là một tập 푄 chứa các véc-tơ tương tự với véc-tơ 푣푖. 
 Bước 3. Truy hồi tập ảnh tương tự dựa trên tập 푄 tại bước 2. Sau đó sắp xếp tập các ảnh 
tương tự với ảnh cần truy vấn. 
4.2 Tổ chức thực nghiệm 
 Để đánh giá phương pháp tiếp cận của bài toán trên cơ sở các thuật toán đã đề xuất, chúng 
tôi xây dựng thực nghiệm trên bộ dữ liệu ImageCLEF được lưu trữ trong 41 thư. Mỗi ảnh được 
56 
jos.hueuni.edu.vn Tập 129, Số 2A, 2020 
phân đoạn thành các vùng, có một véc-tơ đặc trưng và thuộc một phân lớp. Bộ dữ liệu có 99.535 
vùng, phân thành 276 lớp. 
 Thực nghiệm truy vấn ảnh CBIR-BKD-Tree đượ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 thực nghiệm: Intel(R) Core™ i5-5200U, CPU 2.2GHz, RAM 8GB và hệ điều hành 
Windows 10 Professional. 
 Hình 5. Hệ truy vấn ảnh CBIR_BKD-Tree 
 Để đánh giá hiệu suất của phương pháp, các giá trị thực nghiệm gồm: độ chính xác 
(precision), độ phủ (recall) và độ đo dung hòa F-measure. Công thức tính các giá trị này như sau: 
 |풓풆풍풆풗 풏풕 풊 품풆풔 ∩ 풓풆풕풓풊풆풗풆풅 풊 품풆풔|
 풑풓풆 풊풔풊풐풏 = 
 |풓풆풕풓풊풆풗풆풅 풊 품풆풔|
 |풓풆풍풆풗 풏풕 풊 품풆풔 ∩ 풓풆풕풓풊풆풗풆풅 풊 품풆풔|
 풓풆 풍풍 = 
 |풓풆풍풆풗 풏풕 풊 품풆풔|
 57 
Nguyễn Thị Định và CS. Tập 129, Số 2A, 2020 
 (풑풓풆 풊풔풊풐풏 × 풓풆 풍풍)
 푭 − 풆 풔풖풓풆 = × 
 (풑풓풆 풊풔풊풐풏 + 풓풆 풍풍)
 Trong đó, relavant images là tập ảnh tương tự với ảnh truy vấn, retrieved images là tập 
ảnh tìm kiếm được. Các giá trị độ chính xác, độ phủ và độ dung hòa được tính theo tỷ lệ % và 
được quy đổi thành giá trị trên đoạn [0, 1]. Kết quả thực nhiệm thể hiện trong Bảng 1. 
 Bảng 1. Hiệu suất truy vấn ảnh theo phương pháp đề xuất trên bộ ImageCLEF 
 Trung bình độ Trung bình Trung bình độ Thời gian truy vấn 
 Chủ đề Số ảnh 
 chính xác độ phủ dung hòa trung bình (ms) 
 00-10 1832 0.598713 0.446594 0.503931 30.73533 
 11-20 1796 0.586611 0.434149 0.498994 29.60023 
 21-30 1957 0.615845 0.488197 0.544642 24.51016 
 31-40 2194 0.698048 0.520518 0.599148 27.50432 
 AVG 7779 0.624804 0.472365 0.536815 28.08751 
 Hình 6. Đồ thị Precision, Recall, đường cong ROC của hệ CBIR_BKD-Tree trên bộ ImageCLEF 
 Đồ thị Precision-Recall bộ dữ liệu ImageCLEF cho thấy diện tích nằm dưới đường cong 
Precision-Recall chưa cao, do tính chính xác của hệ truy vấn nằm tập trung ở vùng 0.4 đến 0.7. 
Đồ thị đường cong ROC biểu diễn các giá trị true positive và false positive chủ yếu nằm tập trung 
trên đường baseline. 
58 
jos.hueuni.edu.vn Tập 129, Số 2A, 2020 
 Hiệu suất thực thi của hệ thống CBIR_BKD-Tree trên tập dữ liệu 
 ImageCLEF
 Precision
 measure) 0.8
 -
 0.6
 Recall
 0.4
 0.2
 Các trịgiá hiệusuất 
 F-measure
 0
 (Precision,Recall,F 0 10 20 30 40 50
 Các chủ đề trong tập dữ liệu ImageCLEF
 Hình 7. Trung bình Precision, Recall, F-measure hệ CBIR_BKD-Tree trên tập dữ liệu ImageCLEF 
 Các đồ thị trong Hình 6 và Hình 7 mô tả giá trị trung bình của độ chính xác, độ phủ, độ 
dung hoà. Từ các đồ thị này cho thấy, tính chính xác của truy vấn nằm ở mức trung bình, cần cải 
thiện thêm để nâng cao hiệu suất truy vấn. Độ phủ của truy vấn khá thấp nên độ dung hoà của 
truy vấn chưa cao. Tuy nhiên tốc độ truy vấn khá nhanh, cho thấy hệ thống truy vấn ảnh 
CBIR_BKD-Tree được đánh giá là khá tốt về thời gian truy vấn. Giá trị trung bình độ chính xác 
MAP của hệ truy vấn CBIR_BKD-Tree được so sánh với các phương pháp khác trên cùng bộ dữ 
liệu ImageCLEF, thể hiện trong Bảng 2. 
 Bảng 2. So sánh độ chính xác giữa các phương pháp trên bộ dữ liệu ImageCLEF 
 Phương pháp Giá trị trung bình độ chính xác (MAP) 
 H. Cevikalp, 2017 [20] 0.4678 
 M. Jiu, 2017 [21] 0.5970 
 CBIR_BKD-Tree 0.6248 
 Từ kết quả so sánh ở Bảng 2, cho thấy hệ truy vấn hình ảnh CBIR-BKD-Tree có độ chính 
xác khá tốt so với các nghiên cứu gần đây trong cùng lĩnh vực trên thực nghiệm cùng bộ dữ liệu. 
5 Kết luận 
 Trong bài báo này, chúng tôi đã xây dựng một cấu trúc cây BKD-Tree áp dụng cho bài toán 
tìm kiếm ảnh tương tự. Đây là một cải tiến của cây KD-Tree nguyên thủy nhằm nâng cao kỹ thuật 
lưu trữ dữ liệu trên cây, đồng thời cải thiện thời gian tìm kiếm đến các nút lá gần bằng nhau. 
 59 
Nguyễn Thị Định và CS. Tập 129, Số 2A, 2020 
Chúng tôi đã đề xuất mô hình truy vấn ảnh dựa trên cây BKD-Tree và thực nghiệm trên bộ ảnh 
ImageCLEF có độ chính xác là 62.48%, độ phủ 47.23%, độ dung hòa 53.68% và thời gian truy vấn 
trung bình là 28.08 (ms). Kết quả thực nghiệm đã được so sánh với các công trình khác trên cùng 
một tập dự liệu ảnh, đồng thời so sánh với các phương pháp dựa trên cấu trúc lưu trữ cây KD-
Tree. Thực nghiệm cho thấy tính đúng đắn và hiệu quả của phương pháp đề xuất. Hướng phát 
triển tiếp theo của chúng tôi là tạo một cây chỉ mục với mỗi nút liên kết tới một phần tử của bảng 
tra cứu, với bảng tra cứu này được xây dựng một cách độc lập với cây BKD-Tree để từ đó tăng 
tính hiệu quả trong việc phân lớp trên cây BKD-Tree. 
 Lời cảm ơn 
 Chúng tôi trân trọng cám ơn Trường Đại học Công nghiệp Thực phẩm TP.HCM đã bảo trợ 
và cấp kinh phí, nhóm nghiên cứu SBIR-HCM và Trường Đại học Sư phạm TP.HCM đã tạo điều 
kiện về chuyên môn, 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. Y. He, G.Lu and S. Teng, "An Investigation of Using K-d Tree to Improve Image Retrieval Efficiency". Digital 
 Image Computing Techniques and Application, 21--22 January 2002, Melbourne, Australia. 
 2. B.S. Banerjee M., Pal S.K, "Content-Based Image Retrieval using SURF and Colour Moments", 
 Global Journal of Computer Science and Technology, Volume XI Issue X Version. 
 
 3. J. Mohammed Otair, "Approximate K-Nearest Neighbour Based Spatial Clustering Using K-D Tree". 
 International Journal of Database Management Systems ( IJDMS ) Vol.5, No.1, February 2011. 
 4. L. K. Punitha. S. C, "Density Based Clustering using Enhanced KD Tree", International Journal of Computer 
 Science Engineering and Technology( IJCSET), Vol 4, Issue 11, 314-318, November 2014. 
 5. Y. H. S. Kumar, "KD-Tree Approach in Sketch Based Image Retrieval", International Conference on 
 Mining Intelligence and Knowledge Exploration, pp 247-258, 2015 
 
 6. J. H. Zouaki, B.Abdelkhalak, " Indexing and content-based image retrieval", 2011 International 
 Conference on Multimedia Computing and Systems, 10.1109/ICMCS.2011.5945587, 12 July, 2011. 
 7. J. Das and M. Gogoi, " Indexing of Voluminous Data Using K-D Tree with Reference to CBIR", 
 International Journal of Computer Sciences and Engineering, Volume-4, Special Issue-7, Dec 2016. 
 8. Thanh Manh Le, Thanh The Van, “Image retrieval system based on emd similarity 
 measure and S-Tree”, ICITES-2012, Springer Verlag, LNEE 234 (2013) 139-146, 
 9. N.V.T. Thanh The Van, Thanh Manh Le, "The Method Proposal of Image Retrieval Based on K-Means 
 Algorithm", Advances in Intelligent Systems and Computing, vol. 746, no. 2, pp. 481–490, 2018. 
10. Nguyễn Thị Uyên Nhi, Văn Thế Thành, Lê Mạnh Thạnh, "A Self-Balanced Clustering Tree apply for 
 Semantic-Based Image Retrieval", Fundamental and Applied IT Reseach (FAIR), Hue University, NXB 
 Khoa học Tự nhiên và Công nghệ, ISBN, 2019. 
11. Nguyễn Minh Hải, Lê Thị Vĩnh Thanh, Văn Thế Thành, Trần Văn Lăng, "Tra cứu ảnh theo ngữ nghĩa dựa 
 trên cây phân cụm phân cấp", Kỷ yếu Hội thảo Quốc gia về Nghiên cứu cơ bản và ứng dụng CNTT 
 (FAIR), ĐH Huế, Nhà xuất bản Khoa học Tự nhiên và Công nghệ, ISBN: xx, tr.xx-xx, 2019. 
12. Văn Thế Thành, Lê Mạnh Thạnh, "Truy vấn ảnh tri thức dựa trên chữ ký nhị phân", Jos.hueuni.edu.vn, 
 Tập. 97; Số. 9; Năm 2014. 
60 
jos.hueuni.edu.vn Tập 129, Số 2A, 2020 
13. Hasan Al-Jabbouli, "Data clustering using the Bees Algorithm and the Kd-Tree structure", Intelligent 
 Systems Research Laboratory, Manufacturing Engineering Centre, Cardiff University, United 
 Kingdom, 2009. 
14. Shadi Abudalfa, Mohammad Mikki, "A Dynamic Linkage Clustering using KD-Tree", the International 
 Arab Journal of Information Technology, Vol. 10, No. 3, May 2013. 
15. Stephen J. Redmond, Conor Heneghan. "A method for initialising the K-means clustering algorithm 
 using kd-trees " ScienceDirect, Pattern Recognition Letters 28 (2007) 965–973. 
16. Zhi-chun huang, patrick p. K. Chan, wing w. Y. Ng, daniel s. Yeung. "Content-Based Image Retrieval 
 Using Color Moment And Gabor Texture Feature". Proceedings of the Ninth International Conference 
 on Machine Learning and Cybernetics, Qingdao, 11-14 July 2010. 
17. S. Mangijao Singh, K. Hemachandran, "Content-Based Image Retrieval using Color Moment and Gabor 
 Texture Feature ", IJCSI International Journal of Computer Science Issues, Vol. 9, Issue 5, No 1, 
 September 2012. 
18. Cevikalp H., Elmas M., Ozkan S., “Large-scale image retrieval using transductive support vec-tơ 
 machines”, Computer Vision and Image Understanding, vol. no. pp.1-11, 2017. 
19. Jiu M., Sahbi H., “Nonlinear Deep Kernel Learning for Image Annotation”, IEEE Transactions on Image 
 Processing, vol. 26, no.4, pp.1820-1832, 2017. 
20. Thinh N.V., Thanh T.V., Thanh M.L., "The Method Proposal of Image Retrieval Based on K-Means 
 Algorithm", Advances in Intelligent Systems and Computing, vol. 746, no. 2, pp. 481–490, 2018. 
 Abstract. The paper proposes the data clustering model based on the BKD-Tree, an 
 improvement of KD-Tree for the image retrieval. This model includes: (1) storing multi-
 dimensional data objects at the leaf nodes of the tree to create data clusters based on semi-
 supervised learning method; (2) create a balanced tree structure to increase the efficiency of 
 image search. We use BKD-Tree to make experiment on ImageCLEF image set (including 
 20,000 images). Our experimental results are compared with several recent works on the same 
 data set to demonstrate the effectiveness of the proposed method. This shows that our method 
 is effective and can be applied to similar image retrieval systems by content. 
 Keywords: BKD-Tree, clustering, similar image, similar measure, image retrieval. 
 61