Một số cải tiến cho hệ truy vấn ảnh dựa trên cây S-tree

illi giây) 
 cây thử trung bình 
 H-MPEG7 10,374.0180 78,926 13 691 69.10% 0.727945007 0.728254451 0.728099696 4.470049638 42.51664255 
 HR-MPEG7 5,974.8081 84,305 14 654 65.40% 0.73675841 0.737549361 0.737153673 4.86606208 47.49235474 
 E-MPEG7 20,217.6365 8,425,717 16 578 57.80% 0.717266436 0.717538139 0.717402262 3.805543253 43.79238754 
 COREL 
 ER-MPEG7 15,958.8275 9,184,228 17 626 62.60% 0.739472843 0.739783073 0.739627926 4.535472364 48.64217252 
 EP-64 67,840.0957 25,123,957 22 512 51.20% 0.687480469 0.687487535 0.687484002 8.257046875 59.5859375 
 EP-256 587,575.1129 64,311,879 14 544 54.40% 0.843602941 0.843331798 0.843467348 26.81254688 60.05882353 
 H-MPEG7 56,788.2505 1,630,451 153 2,890 26.76% 0.756657439 0.577469804 0.655030209 39.57224948 337.7806228 
 HR-MPEG7 59,261.3933 1,553,154 155 2,611 24.18% 0.738521639 0.578869932 0.649021871 34.62357687 359.2830333 
 E-MPEG7 136,801.3689 107,776,364 177 2,500 23.15% 0.736752 0.578271586 0.647962138 36.33558544 345.4544 
 WANG 
 ER-MPEG7 148,198.4766 113,271,910 185 2,325 21.53% 0.724 0.566786346 0.635819112 28.65708374 355.2197849 
 EP-64 860,989.2461 269,556,572 191 2,736 25.33% 0.802697368 0.658330355 0.723381268 91.95805691 553.3815789 
 EP-256 12,202,465.4815 1,123,060,059 184 4,276 39.59% 0.908543031 0.834190753 0.869780803 298.5712446 692.9471469 
 H-MPEG7 534,160.5293 6,014,781 549 5,473 14.80% 0.889420793 0.542777417 0.674149035 164.9390066 1376.397771 
 HR-MPEG7 499,185.2694 6,893,898 715 5,289 14.30% 0.951796181 0.511041921 0.66501925 153.9208601 1518.078843 
 E-MPEG7 1,105,698.7514 399,628,572 627 3,286 8.88% 0.857577602 0.532540704 0.657059156 137.257453 1284.471394 
 ImgCollect 
 ER-MPEG7 1,002,223.7651 398,839,670 623 4,581 12.39% 0.871731063 0.59175723 0.704963834 130.9673552 1317.882558 
 EP-64 4,207,389.7730 931,274,257 647 6,348 17.16% 0.899774732 0.676759198 0.772493144 353.9520398 2045.435885 
 EP-256 48,544,118.4751 3,817,477,152 596 12,220 33.04% 0.955059738 0.859059351 0.904519448 1128.856025 2423.78036 
Văn Thế Thành, Lê Mạnh Thạnh 467 
 Trong thực nghiệm, bài báo thực hiện truy vấn trên các tập ảnh gồm COREL, Wang, ImgCollect ứng với 6 
phương pháp truy vấn ảnh dựa trên chữ ký nhị phân gồm: (1) Sử dụng độ đo Hamming kết hợp dải màu MPEG7 (H-
MPEG7); (2) Trích xuất vùng cục bộ và sử dụng độ đo Hamming kết hợp dải màu MPEG7 (HR-MPEG7); (3) Sử dụng 
độ đo EMD kết hợp dải màu MPEG7 (E-MPEG7); (4) Trích xuất vùng đặc trưng và sử dụng độ đo EMD kết hợp với 
dải màu MPEG7 (ER-MPEG7); (5) Sử dụng độ đo EMD kết hợp với 64 màu (EP-64); (6) Sử dụng độ đo EMD kết hợp 
với 256 màu (EP-256). 
 Trong Bảng 1 đã cho thấy phương pháp EP-256 có độ chính xác cao hơn các phương pháp còn lại. Từ đó cho 
thấy sự hiệu quả của phương pháp truy vấn ảnh dựa trên cây Sig-Tree đã được đề xuất. Thời gian truy vấn của các 
phương pháp được đo trên milli giây, từ đó tính giá trị trung bình. Từ Bảng 1 cho thấy, thời gian truy vấn trung bình 
của phương pháp EP-256 trên tập ảnh COREL là 26.81254688 milli giây, trên tập ảnh Wang là 692.9471469 milli giây 
và trên tập ảnh ImgCollect là 2423.78036 milli giây. 
 Thời gian tạo cây Sig-Tree trong phương pháp EP-64 và EP-256 lâu hơn các phương pháp khác. Đối với tập dữ 
liệu COREL, thời gian tạo cây của hai phương pháp này lần lượt là 67,840.0957 milli giây và 587,575.1129 milli giây 
(tức là khoảng 67.840 giây và 587.575 giây). Đối với tập dữ liệu Wang, thời gian tạo cây của hai phương pháp này lần 
lượt là 860,989.2461 milli giây và 12,202,465.4815 milli giây (tức là khoảng 14.3498 phút và 203.3744 phút). Đối với 
tập dữ liệu ImgCollect, thời gian tạo cây của hai phương pháp này lần lượt là 4,207,389.7730 milli giây và 
48,544,118.4751 milli giây (tức là khoảng 1.168719 giờ và 13.48447735 giờ). Tuy nhiên, việc tạo cây Sig-Tree là pha 
chuẩn bị dữ liệu, không ảnh hưởng đến thời gian truy vấn ảnh. 
 Hình 6. Đồ thị recall-precision và đường cong ROC trên bộ dữ liệu COREL của các phương pháp 
 Hình 7. Đồ thị recall-precision và đường ROC trên bộ dữ liệu Wang của các phương pháp 
 Hình 8. Đồ thị recall-precision và đường ROC trên bộ dữ liệu ImgCollect của các phương pháp 
468 MỘT SỐ CẢI TIẾN CHO HỆ TRUY VẤN ẢNH DỰA TRÊN CÂY S-TREE 
 Mỗi đường cong trong Hình 6 mô tả chi tiết về độ chính xác truy vấn ảnh từng phương pháp trên tập ảnh 
COREL (1,000 ảnh). Theo như kết quả thực nghiệm tại Hình 6, phương pháp EP-256 có độ chính xác cao hơn tất cả 
các phương pháp còn lại. Điều này chứng tỏ sự hiệu quả của phương pháp truy vấn ảnh sử dụng chữ ký nhị phân và cây 
Sig-Tree, nghĩa là thời gian thực thi nhanh và có độ chính xác cao. Trong Hình 7, mỗi đường cong mô tả độ chính xác 
của từng phương pháp đã mô tả như trên theo bộ dữ liệu ảnh Wang (10,800 ảnh). Theo như kết quả thực nghiệm trên 
bộ dữ liệu ảnh Wang cho thấy độ chính xác của phương pháp EP-265 vẫn vượt trội so với các phương pháp khác. 
Trong Hình 8, biểu diễn đường cong mô tả độ chính xác- độ phủ và đường cong ROC của các phương pháp như đã mô 
tả trong Bảng 1 trên bộ dữ liệu ImgCollect (36,986 ảnh). Theo như kết quả cho thấy, độ chính xác của phương pháp 
EP-256 cao hơn so với các phương pháp khác cùng thể loại. Qua thực nghiệm trên ba bộ dữ liệu khác nhau cho thấy 
tính hiệu quả của các phương pháp truy vấn ảnh theo nội dung dựa trên chữ ký nhị phân và cây Sig-Tree. Vì vậy, các 
cải tiến trên cây Sig-Tree thể hiện tính đúng đắn và phù hợp cho bài toán truy vấn ảnh. 
C. So sánh kết quả thực nghiệm 
 Chúng tôi sử dụng hai phương pháp EP-64 và EP-256 để so sánh với các phương pháp khác đã công bố trên bộ 
dữ liệu ảnh COREL, gồm: (1) Phương pháp KD-Tree [32]; (2) Phương pháp S-Tree [15]; (3) Phương pháp QBIC, 
Fuzzy Signature [25]; (4) Phương pháp color histogram, fuzzy-color histogram, bit-planes [30]; (5) Phương pháp đối 
sánh histogram vùng đặc trưng [29]. 
 Bảng 2. So sánh độ chính xác truy vấn giữa các phương pháp 
 Độ chính xác Độ phủ Độ đo F-measure Thời gian truy vấn 
 Phương pháp 
 trung bình trung bình trung bình trung bình 
 KD-Tree [32] 0.876031667 N/A N/A 93; 63; 46 (msec) 
 S-Tree [15] 0.42 0.55 0.476289 186.25 I/Os 
 QBIC [25] N/A N/A N/A 2-40 sec 
 Fuzzy Signatures [25] N/A N/A N/A 20-50 I/Os 
 Color histogram [30] 0.29125 0.06400 0.104940 4.43750 sec 
 Fuzzy-color histogram [30] 0.37438 0.08100 0.133184 4.25625 sec 
 Bit-planes[30] 0.52938 0.12125 0.197308 4.18516 sec 
 Interest point [29] 0.65688 0.70500 0.68009 4.70938 sec 
 Sub-color histogram [29] 0.49125 0.61063 0.54447 4.43638 sec 
 Fuzzy color histogram [29] 0.50688 0.61625 0.55624 4.41863 sec 
 Interest region [29] 0.85200 0.78375 0.81645 4.78516 sec 
 EP-64 0.687480469 0.687487535 0.687484002 8.257 msec 
 EP-256 0.843602941 0.843331798 0.843467348 26.813 msec 
 Theo số liệu so sánh từ Bảng 2 cho thấy phương pháp truy vấn ảnh theo nội dung dựa trên chữ ký nhị phân và 
cây Sig-Tree có thời gian truy vấn nhanh hơn các phương pháp khác đồng thời vẫn đảm bảo độ chính xác cao. Từ đó 
cho thấy phương pháp đã đề xuất hiệu quả đối với bài toán truy vấn ảnh tương tự. 
 VI. KẾT LUẬN 
 Trong bài báo đã tiếp cập xây dựng hệ truy vấn ảnh theo nội dung dựa trên chữ ký nhị phân và cây Sig-Tree. Bài 
báo đã mô tả cách tạo chữ ký nhị phân để tạo thành chỉ mục cho hình ảnh, đồng thời bài báo đã thiết kế cấu trúc cây 
Sig-Tree cũng như các thao tác tương ứng. Trên cơ sở lý thuyết đã đề xuất, bài báo mô tả ứng dụng thực nghiệm qua 
nhiều phương pháp biến thể khác nhau nhằm minh chứng rằng phương pháp đề xuất là một giải pháp đúng đắn. Kết 
quả thực nghiệm của hai phương pháp chính đó là EP-64 và EP-256 cũng được so sánh với các phương pháp khác. 
Theo như kết quả thực nghiệm cho thấy phương pháp đã đề xuất là giải pháp tốt để giải quyết bài toán truy vấn ảnh 
theo nội dung, hơn nữa đây cũng là một giải pháp hiệu quả. Trong phần phát triển tiếp theo, nhóm tác giả kết hợp 
phương pháp gom cụm không phân cấp với cấu trúc Sig-Tree để thực hiện các thao tác tách/ghép cụm tại các nút của 
cây, hơn nữa các cụm tại nút trong cây liên kết láng giềng với nhau để từ đó tăng tốc độ truy vấn ảnh. 
 VII. LỜI CẢM ƠN 
 Nhóm tác giả xin chân thành cám ơn Khoa Công nghệ Thông tin, Trường ĐH Khoa Học – Đại học Huế là nơi 
cố vấn chuyên môn cho nghiên cứu này. Nhóm tác giả xin gửi lời cám ơn đến Trung tâm Công nghệ Thông tin, Trường 
ĐH Công nghiệp Thực phẩm Tp.HCM là nơi bảo trợ cho nghiên cứu này. 
 TÀI LIỆU THAM KHẢO 
[1] T. Acharya, A. K. Ray, Image Processing: Principles and Applications, John Wiley & Sons Inc. Publishers, Hoboken, New 
 Jersey, 2005. 
[2] Aci,  2015. 
[3] A. Alzu’bi, A. Amira, N. Ramzan, Semantic content-based image retrieval: A comprehensive study, Journal of Visual 
 Communication and Image Representation, 32, pp. 20-54, 2015. 
Văn Thế Thành, Lê Mạnh Thạnh 469 
[4] A. Bhagyalaksluni, V. V. Ayachamundeeswari, A Survey on Content Based Image Retrieval Using Various Operators, 
 International Conference on Computer Communication and Systems, IEEE, pp. 018-023, Chennai, 2014. 
[5] Y. Chen, On the signature trees and balanced signature trees, 21st International Conference on Data Engineering, ICDE'05, 
 IEEE, pp. 742-753, 2005. 
[6] Y. Chen, Y. Chen, On the Signature Tree Construction and Analysis, IEEE Transactions On Knowledge And Data 
 Engineering, 18(9), pp. 1-18, 2006. 
[7] C. Chute, Worldwide Digital Image 2015–2019 Forecast: The Image Capture and Share Bible, International Data 
 Corporation, pp. 13 pages, (February 2015 # 254256). 
[8] W. Dejonge, P. Scheuermann, A. Schijf, S+-Trees: An Efficient Structure for the Representation of Large Pictures, CVGIP: 
 Image Understanding, 59(3), pp. 265-280, 1994. 
[9] L. Deligiannidis, H. R. Arabnia, Emerging Trends in Image Processing, Computer Vision, and Pattern Recognition, Morgan 
 Kaufmann, Elsevier, Waltham, MA 02451, USA, 2015. 
[10] U. Deppisch, S-tree: a dynamic balanced signature index for office retrieval, Proceedings of the 9th annual international ACM 
 SIGIR conference on Research and development in information retrieval, ACM, pp. 77-87, New York, NY, USA, 1986. 
[11] M. Hilbert, A review of large-scale 'How much information?' inventories: variations, achievements and challenges, 
 Information Research, 20(4), pp. paper 688, 2015. 
[12] Idc, https://www.idc.com, 2016. 
[13] K. Jenni, S. Mandala, M. S. Sunar, Content Based Image Retrieval Using Colour Strings Comparison, Procedia Computer 
 Science, 50, pp. 374-379 2015. 
[14] R. Ji, Y. Gao, L.-Y. Duan, H. Yao, Q. Dai, Learning-Based Local Visual Representation and Indexing, Elsevier, Radarweg 29, 
 PO Box 211, 1000 AE Amsterdam, Netherlands, 2015. 
[15] Y. Manolopoulos, A. Nanopoulos, E. Tousidou, Advanced Signature Indexing for Multimedia and Web Applications, Kluwer 
 Academic Publishers, Springer Science+Business Media New York, 2003. 
[16] O. Marques, B. Furht, Content-Based Image and Video Retrieval, Kluwer Academic Publishers, Springer Science+Business 
 Media New York, 2002. 
[17] V. Mezaris, I. Kompatsiaris, M. G. Strintzis, Still Image Segmentation Tools for Object-based Multimedia Applications, Int. 
 Journal Of Pattern Recognition And Artificial Intelligence, 18(4), pp. 701-725, 2004. 
[18] P. Muneesawang, L. Guan, Multimedia Database Retrieval: A Human-Centered Approach, Springer Scicnce+Busincss Media, 
 New York, NY 10013, USA, 2006. 
[19] P. Muneesawang, N. Zhang, L. Guan, Multimedia Database Retrieval: Technology and Applications, Springer International 
 Publishing Switzerland, Springer Cham Heidelberg New York Dordrecht London, 2014. 
[20] M. A. Nascimento, E. Tousidou, V. Chitkara, Y. Manolopoulos, Image indexing and retrieval using signature trees, Data & 
 Knowledge Engineering, 43, pp. 57-77, 2002. 
[21] J. Platos, P. Kromer, V. Snasel, A. Abraham, Searching similar images - Vector Quantization with S-tree, Fourth International 
 Conference on Computational Aspects of Social Networks, CASoN 2012, IEEE, pp. 384-388, Sao Carlos, 2012. 
[22] R. Priya, T. N. Shanmugam, A comprehensive review of significant researches on content based indexing and retrieval of 
 visual information, Front. Comput. Sci., 7(5), pp. 782-799, 2013. 
[23] R. Raieli, Multimedia Information Retrieval: Theory and techniques, Chandos Publishing, Oxford OX28 4BN UK, 2013. 
[24] I. E. Shanthi, Y. Izaaz, R. Nadarajan, On the SD-tree construction for optimal signature operations, Proceedings of the 1st 
 Bangalore Annual Compute Conference, COMPUTE '08, ACM, Article No. 14, New York, NY, USA, 2008. 
[25] V. Snášel, Fuzzy Signatures for Multimedia Databases, Advances in Information Systems, ADVIS 2000, Springer Berlin 
 Heidelberg, 1909, pp. 257-264, Izmir, Turkey, 2000. 
[26] V. Snasel, Z. Horak, M. Kudelka, A. Abraham, Fuzzy Signatures Organized Using S-Tree, IEEE International Conference on 
 Systems, Man, and Cybernetics (SMC), IEEE, pp. 633 - 637, Anchorage, AK, 2011. 
[27] E. Tousidou, A. Nanopoulos, Y. Manolopoulos, Improved methods for signature-tree construction, The Computer Journal, 
 43(4), pp. 300-313, 2000. 
[28] J. Z. Wang, Integrated Region-Based Image Retrieval, Kluwer Academic Publishers, Springer Science Business Media New 
 York, 2001. 
[29] X.-Y. Wang, J.-F. Wu, H.-Y. Yang, Robust Image Retrieval Based on Color Histogram of Local Feature Regions, Springer 
 Science, Multimed Tools Appl, 49, pp. 323-345, 2010. 
[30] X.-Y. Wang, H.-Y. Yang, Y.-W. Li, F.-Y. Yang, Robust color image retrieval using visual interest point feature of significant 
 bit-planes, Digital Signal Processing, 23(4), pp. 1136-1153, 2013. 
[31] C. Wengert, M. Douze, H. Jégou, Bag-of-colors for Improved Image Search, Proceedings of the 19th ACM international 
 conference on Multimedia, ACM, pp. 1437-1440, Scottsdale, Arizona, USA, 2011. 
[32] H. Zouaki, B. Abdelkhalak, Indexing and content-based image retrieval, International Conference on Multimedia Computing 
 and Systems (ICMCS), IEEE, pp. 1-5, Ouarzazate, 2011. 
470 MỘT SỐ CẢI TIẾN CHO HỆ TRUY VẤN ẢNH DỰA TRÊN CÂY S-TREE 
IMPROVING FOR CONTENT-BASED IMAGE RETRIEVAL USING S-TREE 
 Van The Thanh, Le Manh Thanh 
ABSTRACT— Digital image has been becoming the popular things in the life of people, so the image retrieval problem is a need of 
modern society. This paper approaches the CBIR (Content-Based Image Retrieval) based on binary signature and S-Tree. To create 
the binary signature, we apply K-mean method to create the color palette from a set including 36,986 images. Next, the paper gives 
the Sig-Tree data structure rely on S-Tree, then we describle the operators on this tree. The paper uses Hamming, EMD distance 
(Earth Mover Distance) and CIE-Lab color space to assess the similarity measure between images. In order to show the proposed 
theory, we build the applications to assess the experimental results on the image databases including COREL (1,000 images), Wang 
(10,800 images), ImgCollect (36,986 images).