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

: Cây phân cụm RG-Tree sau khi cập nhật 
 Function 푼푪푹푮 (Node) 
 Begin 
 If (Node.Element_parent != null) then 
 fcN = avg{ Node.E[i].f | i=1..count}; 
 Node.Element_parent.f = fcN; 
 EndIf 
 If ( Node.parent != null) then 
 37 
Lê Thị Vĩnh Thanh và CS. Tập 129, Số 2A, 2020 
 Node = Node.parent; 
 푈 푅 (Node); 
 EndIf 
 End 
 Mệnh đề 1. Thuật toán 푈 푅 có độ phức tạp là ( ℎ), với ℎ, lần lượt là chiều cao và 
số phần tử tối đa trong một nút của cây RG-Tree. 
 Chứng minh: Trường hợp xấu nhất, Thuật toán 푈 푅 phải cập nhật tâm cụm từ nút lá đến 
nút gốc tức là phải duyệt qua chiều cao ℎ. Mỗi lần cập nhật tâm, Thuật toán 푈 푅 duyệt qua tối 
đa phần tử của mỗi nút. Do đó, độ phức tạp của Thuật toán 푈 푅 là ( ℎ)∎ 
Thuật toán chèn một phần tử vào cây RG-Tree 
 Khi một phần tử Ei = được thêm vào cây RG-Tree, việc chèn được thực hiện bắt đầu 
từ nút gốc, lần lượt duyệt qua tất cả các nút con của nút gốc và tính khoảng cách Euclide của 
phần tử Ei với từng tâm cụm, chọn cụm có khoảng cách 푖푛 = 푖푛 { ( 푖, 푗), 푗 = 1. . }. Nếu 
 푖푛 > 휃 tạo một nhánh mới để lưu phần tử Ei ngược lại thì đi theo nhánh đó và lần lượt duyệt 
hết các nhánh của cây phân cụm RG-Tree cho đến khi tìm được nút lá. Sau đó, khoảng cách phần 
tử Ei đến tâm nút lá được tính nếu 푖푛 < 휀 thì chèn vào nút lá đó ngược lại tạo một nút lá mới 
đồng cấp để lưu Ei. 
Thuật toán 2: 푰푹푮 
 Đầu vào: phần tử 푡, nút gốc 표표푡, giá trị ngưỡng 휀, 휃 
 Đầu ra: cây RG-Tree sau khi thêm phần tử 푡 
 Function 퐈퐑퐆( 푡, 표표푡, 휀, 휃) 
 Begin 
 푵풐풅풆 = 표표푡; 
 If (푵풐풅풆 = 푛 푙푙) then 
 Initialize 표표푡 = {푙푖푛 푠 | 푙푖푛 푠 = 푛 푙푙; = 1. . 푛 }; 
 Create new 푙푣푛표 푒 =, 푙푖푛 푠 = 푛 푙푙; 
 표표푡. 푙푖푛 푠0 = 푙푣푛표 푒; 
 푈 푅 (푙푣푛표 푒); 
 ElseIf 
 푖 = 푖푛 {푒 푙푖 푒(푵풐풅풆. E[ ]. , . ), = 1. . count)}; 
 = 푙푖 푒(푵풐풅풆. E[푖]. , 푡. ); 
 If (푵풐풅풆.links=null) then 
 If < 휀 then 
 푵풐풅풆.count = 푵풐풅풆.count + 1; 
38 
jos.hueuni.edu.vn Tập 129, Số 2A, 2020 
 푵풐풅풆.E[count+1].f = Ei.f; 
 푵풐풅풆.E[count+1].id = Ei.id; 
 푈 푅 (푵풐풅풆); 
 ElseIf 
 If ( ≥ 휀 && ≤ 휃) then 
 Create new 푙푣푛표 푒 =, 푙푖푛 푠푙푣 = 푛 푙푙; 
 푙푣. = 푡. ; 
 푙푣. 푖 = 푡. 푖 ; 
 Create new 푖푛푛표 푒 =, 푙푖푛 푠푖푛 = 푙푣푛표 푒 
 푵풐풅풆. 푙푖푛 푠 = 푖푛푛표 푒; 
 푈 푅 (푙푣푛표 푒); 
 ElseIf 
 Create new 푙푣푛표 푒 =, 푙푖푛 푠푙푣 = 푛 푙푙; 
 푵풐풅풆. 푙푖푛 푠 표 푛푡+1 = 푖푛푛표 푒; 
 푵풐풅풆.count = 푵풐풅풆.count + 1; 
 UCRG(푙푣푛표 푒); 
 EndIf 
 EndIf 
 ElseIf 
 If ( ≤ 휃) 
 푰푹푮( 푡, 푵풐풅풆. 푙푖푛 푠 , 휀, 휃); 
 ElseIf 
 Create new 푙푣푛표 푒 =, 푙푖푛 푠푙푣 = 푛 푙푙; 
 푵풐풅풆. 푙푖푛 푠 표 푛푡+1 = 푖푛푛표 푒; 
 푵풐풅풆.count = N.count + 1; 
 UCRG(푙푣푛표 푒); 
 EndIf 
 EndIf 
 Return RG-Tree; 
 End 
 Mệnh đề 2. Thuật toán 푅 có độ phức tạp là ( ℎ), với ℎ, lần lượt là chiều cao và số 
phần tử tối đa trong một nút của cây RG-Tree. 
 Chứng minh: Thuật toán 푅 lần lượt thực hiện duyệt từ nút gốc đến nút lá do đó duyệt 
qua chiều cao ℎ, mỗi lần duyệt qua phần tử, mỗi lần duyệt Thuật toán 푅 thực hiện phép cập 
 39 
Lê Thị Vĩnh Thanh và CS. Tập 129, Số 2A, 2020 
nhật tâm từ nút lá đến nút gốc tức là cập nhật qua chiều cao h và duyệt lại tối đa phần tử. Do 
đó, Thuật toán 푅 có độ phức tạp là ( ℎ) ◼ 
Thuật toán xóa phần tử trên cây RG-Tree 
 Các phần tử chỉ nằm ở nút lá của cây RG-Tree, nếu nút lá đó chỉ gồm 1 phần tử thì nút lá 
đó được xóa và cập nhật lại tâm cho nút cha. Trường hợp nút lá đó có nhiều hơn 1 phần tử thì 
phần tử bị xóa khỏi nút và cập nhật lại tâm cho nút lá. Thuật toán xóa một phần tử được thực 
hiện như sau: 
Thuật toán 2: DRG 
Đầu vào: phần tử 푡, nút gốc 표표푡, giá trị ngưỡng 휀, 휃 
Đầu ra: cây RG-Tree sau khi xóa phần tử 푡 
 Function 푅 ( 푡, 표표푡, 휀, 휃) 
 Begin 
 푵풐풅풆 = 표표푡; 
 If 푵풐풅풆 = 푛 푙푙 then 
 Return 푛 푙푙; 
 ElseIf 
 푖 = 푖푛 {푒 푙푖 푒(푵풐풅풆. E[ ]. , . ), = 1. . count)}; 
 = 푙푖 푒(푵풐풅풆. E[푖]. , . ); 
 If (푵풐풅풆.links=null) then 
 푵풐풅풆.count = 푵풐풅풆.count -1; 
 푵풐풅풆.E= 푵풐풅풆.E/{ 푡}; 
 If (푵풐풅풆.count > 0) then 
 UCRG(푵풐풅풆); 
 ElseIf 
 UCRG(푵풐풅풆.parent); 
 EndIf 
 ElseIf 
 If ( ≤ 휃) 
 푫푹푮( 푡, 푵풐풅풆. 푙푖푛 푠 , 휀, 휃); 
 EndIf 
 End If 
 End If 
 Return RG-Tree; 
 End. 
 Mệnh đề 2. Thuật toán 푅 có độ phức tạp là ( ℎ), với ℎ, lần lượt là chiều cao và số 
phần tử tối đa của một nút trong cây RG-Tree. 
40 
jos.hueuni.edu.vn Tập 129, Số 2A, 2020 
 Chứng minh: Thuật toán 푅 được chứng minh tương tự thuật toán 푅 . Do đó, Thuật toán 
 푅 có độ phức tạp là ( ℎ) ◼ 
4 Tìm kiếm ảnh tương tự trên cây RG-Tree 
4.1 Dữ liệu ảnh 
 Mỗi ảnh sẽ được chia thành nhiều vùng nhau theo phương pháp của Hugo Jair Escalante 
[25], mỗi vùng được trích xuất một vec-tơ đặc trưng bao gồm đặc trưng vùng: diện tích, chiều 
rộng và chiều cao; đặc trưng về vị trí; đặc trưng về hình dạng; đặc trưng màu sắc trong không 
gian RGB và CIE-Lab. 
 Hình 3. Ảnh gốc và các ảnh phân vùng (20747.jpg) 
Hình 3 mô tả một ảnh gốc và 4 ảnh của các vùng thuộc về các lớp ảnh: mammal-other, group-of-persons, plant, plant 
 của ảnh 20747.jpg trong tập ảnh ImageCLEF. 
4.2 Thuật toán tra cứu ảnh tương tự trên cây RG-Tree 
 Từ cây phân cụm dữ liệu RG-Tree đã tạo, chúng tôi đề xuất thuật toán tra cứu ảnh tương 
tự. Quá trình tìm kiếm ảnh tương tự được thực hiện trên cây RG-Tree và được mô tả như sau: 
Thuật toán 4. RGIR 
 Đầu vào: vec-tơ đặc trưng 푖 của ảnh truy vấn 푞, cây RG-Tree, giá trị ngưỡng 휀 , 휃. 
 Đầu ra: tập ảnh tương tự 푆 
 Function 퐑퐆퐈퐑( 푖 , 표표푡, 휀 , 휃 ) 
 Begin 
 푵풐풅풆 = 표표푡; 
 If 푵풐풅풆 = 푛 푙푙 then 
 Return 푛 푙푙; 
 ElseIf 
 푖 = 푖푛 {푒 푙푖 푒(푵풐풅풆. E[ ]. , . ), = 1. . count)}; 
 = 푙푖 푒(푵풐풅풆. E[푖]. , . ); 
 If (N.links=null) then 
 SI= 푵풐풅풆.E; 
 41 
Lê Thị Vĩnh Thanh và CS. Tập 129, Số 2A, 2020 
 Return SI; 
 ElseIf 
 If ( ≤ 휃) 
 퐑퐆퐈퐑( 푖 , 푵풐풅풆. 푙푖푛 푠 , 휀, 휃); 
 EndIf 
 End If 
End If 
 Return 푆 ; 
End. 
 Mệnh đề 4. Thuật toán RGIR có độ phức tạp là (ℎ ), với ℎ, lần lượt là chiều cao và số 
phần tử tối đa của một nút trong cây RG-Tree. 
 Chứng minh: Thuật toán RGIR lần lượt duyệt từ gốc đến lá, mỗi lần duyệt một nút sẽ kiểm 
tra phần tử của nút đó. Vì vậy, thuật toán RGIR có độ phức tạp là (ℎ ) ◼ 
4.3 Mô hình truy vấn ảnh 
 Pha 1: Tiền xử lý
 Root(fc1, fc2, fc3)
 Trích xuất véc-tơ f1=(v1, v2, , vm)
 K-Means, k-NN R1(fc11, fc12, fc13) R2(fc21, fc22) R3(f8, f11, f12)
 đặc trưng f2=(v1, v2, , vm)
 Image Database
 fn=(v1, v2, , vm) R11(f1, f5, f9) R12(f2, f10, fc13) R21(f3, f6, f7) R22(f4, f14, fc15)
 Pha 2: Tìm kiếm ảnh
 Trích xuất véc-tơ fi1=(v1, v2, , vm)
 Phân đoạn ảnh đặc trưng fi2=(v1, v2, , vm)
 Tìm kiếm ảnh
 fik=(v1, v2, , vm)
 Tập ảnh tương tự
 Hình 4. Mô hình tìm kiếm ảnh theo nội dung dựa trên cây RG-Tree 
 Quá trình tìm kiếm ảnh được thực hiện gồm hai pha, pha thứ nhất thực hiện gom cụm và 
lưu trữ trên cây RG-Tree, pha thứ hai thực hiện tìm kiếm các hình ảnh tương tự. Quá trình thực 
hiện được mô tả như sau: 
42 
jos.hueuni.edu.vn Tập 129, Số 2A, 2020 
 Pha tiền xử lý: Kết quả của pha tiền xử lý là xây dựng được cây gom cụm RG- Tree dựa 
trên vector đặc trưng của tập dữ liệu ảnh gồm 2 bước như sau: 
 Bước 1. Trích xuất tập véc-tơ đặc trưng fi của tập dữ liệu ảnh. 
 Bước 2. Dựa trên độ đo tương tự đề xuất và tạo cấu trúc cây gom cụm chỉ mục với mỗi nút 
 lá của cây RG-Tree là tập các véc-tơ fi mô tả đặc trưng thị giác của hình ảnh. 
 Pha tìm kiếm: Việc tìm kiếm ảnh tương tự được thực hiện với đầu vào là một hình ảnh 
truy vấn và đầu ra là tập ảnh tương tự dựa trên cây gom cụm chỉ mục RG-Tree. Quá trình tìm 
kiếm ảnh tương tự được thực hiện theo các bước như sau: 
 Bước 1. Trích xuất véc-tơ đặc trưng của ảnh cần truy vấn. 
 Bước 2. Thực hiện truy vấn ảnh tương tự dựa trên cây RG-Tree. 
 Bước 3. Tra cứu tập ảnh tương tự dựa trên tập chỉ mục đã được truy vấn. 
5 Kết quả thực nghiệm 
 Pha tiền xử lý được thự hiện trên máy PC CPU 2.3GHz 8-core 9th-generation Intel Core i9, 
16GB 2666MHz memory, 1TB flash storage. Pha tìm kiếm được thực nghiệm trên máy PC CPU 
Intel Core i7-6500U CPU @ 2.50GHz, 8.0GB RAM, hệ điều hành Windows 10 Pro 64 bit. Kết quả 
thực nghiệm được đánh giá trên bộ dữ liệu imageCLEF chứa 20,000 ảnh, được chia thành 276 lớp 
và lưu trữ trong 41 thư mục (từ thư mục 0 đến thư mục 40); bộ dữ liệu của kích thước 1.64 GB. 
Để đánh giá hiệu quả của phương pháp tìm kiếm ảnh, phần thực nghiệm được đánh giá các giá 
trị gồm: độ chính xác (precision), độ phủ (recall) và độ đo dung hòa F-measure. 
 Hình 5. Giao diện truy vấn ảnh dựa trên cây RG-Tree 
 43 
Lê Thị Vĩnh Thanh và CS. Tập 129, Số 2A, 2020 
 Hình 6. Một kết quả truy vấn dựa trên cây RG-Tree 
 Hình 7. Biểu đồ Precision-Recall và ROC của hệ truy vấn trên cây RG-Tree 
 Hình 8. Giá trị trung bình của Precision, Recall, F-measure của tập dữ liệu ImageCLEF 
44 
jos.hueuni.edu.vn Tập 129, Số 2A, 2020 
 Bảng 1. Hiệu suất truy vấn ảnh của phương pháp đề xuất trên tập ảnh ImageCLEF 
 Tập ảnh Số ảnh Precision Recall F-Measure 
 00-10 3790 0.7050 0.4555 0.5496 
 11-20 2198 0.7455 0.4809 0.5812 
 21-30 1742 0.7262 0.5142 0.5904 
 31-40 2573 0.6800 0.4355 0.5281 
 10303 0.7110 0.4659 0.5579 
 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 Mean Average Precision (MAP) 
 Hakan Cevikalp, 2017 [18] 0.4678 
 C.A. Hernández-Gracidas, 2013 [19] 0.5826 
 Nguyễn Minh Hải, 2019 [14] 0.6753 
 Nguyễn Thị Uyên Nhi, 2019 [13] 0.6510 
 Phương pháp đề xuất của chúng tôi 0.7110 
 45 
Lê Thị Vĩnh Thanh và CS. Tập 129, Số 2A, 2020 
6 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 RG-Tree áp dụng cho bài toán 
tìm kiếm ảnh tương tự theo nội dung. Đây là một cấu trúc cải tiến của cây R-Tree nhằm nâng cao 
hiệu quả cho kỹ thuật lưu trữ dữ liệu trên cây và áp dụng được cho bài toán có tập dữ liệu tăng 
trưởng. Trong bài báo này, cây RG-Tree được cải tiến từ cây R-Tree và thực nghiệm trên bộ ảnh 
ImageCLEF có độ chính xác là 71.10%, độ phủ 46.59%, độ đo dung hòa 55,79%. 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 RG-Tree. Phương pháp đề xuất của chúng tôi 
đã làm tăng đáng kể hiệu suất truy vấn ảnh theo nội dung. Hướng phát triển tiếp theo, chúng tôi 
sẽ cân bằng cây RG-Tree và áp dụng phương pháp phân hoạch ngữ nghĩa hình ảnh trên mỗi nút 
lá của cây để từ đó thực hiện truy vấn ảnh trên cơ sở tiếp cận theo ngữ nghĩa. 
 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í. Chúng tôi trân trọng cám ơn Trường Đại học Bà Rịa Vũng Tàu, 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 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. Chandresh Pratap Singh, " R-Tree implementation of image databases ". Signal & Image Processing : An 
 International Journal (SIPIJ) Vol.2, No.4, December 2011. 
 2. Nam N.V, Bac L.H, " Simple Spatial Clustering Algorithm Based on R-Tree". C. Sombattheera et al. 
 (Eds.): MIWAI 2012, LNCS 7694, pp. 236–245, Berlin Heidelberg, 2012. 
 3. N. Amoda and R. K. Kulkarni, “Efficient image retrieval using region based image retrieval,” in Signal 
 Image Processing : An International Journal (SIPIJ), vol. 4, no. 3, pp. 17–22, 2013. 
 4. Shama P.S, Badrinath K, Anand Tilugul, " An Efficient Indexing Approach for Content based Image 
 Retrieval". International Journal of Computer Applications (0975 – 8887) Volume 117 – No. 15, May 
 2015. 
 5. Van T. T. , Le M. T., “Một số cải tiến cho hệ truy vấn ảnh dựa trên cây S-Tree”. Proceeding of Publishing 
 House for Science and Technology, 2017. 
 6. Maher Alrahhal ; K.P. Supreethi, "Content-Based Image Retrieval using Local Patterns and Supervised 
 Machine Learning Techniques". Amity International Conference on Artificial Intelligence (AICAI), 2019. 
 7. A Guttman, "R-Tree: a dymanic index structure for spatial searching". In proc. ACM SIGMOD, 1984. 
 8. Gurchetan Singh, "Introductory guide to Information Retrieval using kNN and KDTree", November 28, 
 2017. 
 9. Jayashree Das and Minakshi 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. 
46 
jos.hueuni.edu.vn Tập 129, Số 2A, 2020 
10. 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. 
11. Vignesh Ramanathan, Shaunak Mishra and Pabitra Mitra, "Quadtree Decomposition based Extended 
 Vector Space Model for Image Retrieval", Indian Institute of Technology, Kharagpur - 721302, 978-1-
 4244-9497-2/10/ IEEE, 2010. 
12. A. Alzu’bi, A. Amira, N. Ramzan, "Semantic Content-based Image Retrieval: A Comprehensive Study", 
 J. Vis. Commun. Image R, 2015. 
13. 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: tr.xx-xx, 2019. 
14. 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. 
15. Thanh Manh Le, Thanh The Van - Image retrieval system based on emd similarity measure and S-Tree, 
 ICITES-2012, Springer Verlag, LNEE 234, 139-146, 2013. 
16. 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. 
17. Nguyễn Phương Hạc, Văn Thế Thành, "Một phương pháp tra cứu dữ liệu ảnh dựa trên cây phân cụm 
 đa nhánh cân bằng", Tạp chí Khoa học Công nghệ và Thực phẩm 18 (1), 140-153, 2019. 
18. H. Cevikalp, M. Elmas, S. Ozkan (2017), "Large-scale image retrieval using transductive support vector 
 machines", Computer Vision and Image Understanding, vol. no. pp.1-11. 
19. C.A. Hernández-Gracidas, Sucar, L.E. & Montes-y-Gómez (2013), "Improving image retrieval by using 
 spatial relations", Multimed Tools Application, vol. 62, no. 2, pp. 479–505. 
 Abstract. In this paper, we present an improvement of R-Tree, denoted RG-Tree (Region 
 Growth Tree), to improve the efficiency of finding content-based similar images. In this 
 improvement, the feature vectors of the images are stored on each leaf node of the RG-Tree 
 by the proposed partition rules. RG-Tree can grow to store and distribute data areas on the 
 leaf nodes to create data clusters. The more elements are similar, the more elements belong to 
 one of the branches on the RG-Tree. We designed an image retrieval model on RG-Tree and 
 tested it on ImageCLEF image sets and compared it’s retrieval performance to several recent 
 methods on the same data set. 
 Keywords: RG-Tree, CBIR, Similar Images, Similarity Measure, Image Retrieval. 
 47