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) (2019) 140-153<br /> <br /> <br /> <br /> <br /> MỘT PHƢƠNG PHÁP TRA CỨU DỮ LIỆU ẢNH<br /> DỰA TRÊN CÂY PHÂN CỤM ĐA NHÁNH CÂN BẰNG<br /> <br /> Nguyễn Phƣơng Hạc*, Văn Thế Thành<br /> Trường Đại học Công nghiệp Thực phẩm TP.HCM<br /> *Email: hacnp@hufi.edu.vn<br /> Ng y nh n i: 16/01/2019; Ng y h p nh n ng: 06/3/2019<br /> <br /> <br /> TÓM TẮT<br /> <br /> B i áo tiếp c n phương pháp tra cứu ảnh tương tự dựa trên ây a nhánh ân ằng lưu<br /> trữ á dữ liệu ặ trưng của hình ảnh dưới dạng chỉ mục nhằm mô tả hình dạng của ối<br /> tư ng ặ trưng. Để trí h xu t ặ trưng của hình ảnh, nhóm nghiên ứu ã thực hiện phân<br /> oạn ảnh dựa trên ặ trưng thị giá p th p gồm m u sắ v u trú ủa hình ảnh. Cá ặc<br /> trưng thị giá n y ư trí h xu t trên mỗi khối của hình ảnh bằng phép iến ổi Wavelet v<br /> không gian m u CIE L*a* *. Tiếp theo, nhóm nghiên ứu thực hiện gom cụm á iểm ảnh<br /> ể tạo th nh vùng liên thông trên ảnh ồng thời loại bỏ á vùng ó diện tí h không vư t<br /> ngưỡng ho trước. Trên ơ sở á ặ trưng ã ư trí h xu t, nhóm nghiên ứu ã tạo ra<br /> ộ tương phản của hình ảnh nhằm rút trí h m u nền v m u hính ủa mỗi hình ảnh. Dựa<br /> trên ảnh ã ư phân oạn, chỉ mụ ặ trưng ư c tạo ra nhằm thực hiện ối sánh á hình<br /> ảnh tương tự. Từ ó, nhóm nghiên ứu tạo ra ây a nhánh ân ằng nhằm lưu trữ chỉ mục<br /> mô tả ặ trưng hình ảnh v thực hiện tìm kiếm ảnh. Để minh chứng tính úng ắn cho<br /> phương pháp ề xu t, nhóm nghiên ứu xây dựng thực nghiệm v ánh giá kết quả trên á<br /> t p dữ liệu ảnh gồm Corel v CBIRimages. Kết quả thực nghiệm ư so sánh với á ông<br /> trình khá v cho th y tính hiệu quả của phương pháp ề xu t của nhóm.<br /> Từ khóa: Phương pháp phân oạn, ặ trưng, hỉ mụ hình ảnh.<br /> <br /> 1. GIỚI THIỆU<br /> <br /> Sự xu t hiện á ộ dữ liệu a phương tiện lớn ã dẫn ến yêu ầu phát triển á ông<br /> ụ truy v n thông tin thị giá . Vì v y, việ tìm kiếm á hình ảnh liên quan ến yêu ầu<br /> người dùng l i toán phù h p với nhu ầu xã hội hiện ại. Tra ứu hình ảnh từ ơ sở dữ<br /> liệu ảnh l một i toán quan trọng trong lĩnh vự thị giá máy tính v xử lý ảnh [1].<br /> Hệ truy v n ảnh ao gồm ối sánh ặ trưng ể tìm ra ứng viên sau ó truy hồi ể tìm<br /> ra á hình ảnh tương tự [2]. Hệ truy v n ảnh dựa trên nội dung CBIR (content-based image<br /> retrieval) ã ư giới thiệu v o khoảng th p niên 1980; trong hệ truy v n n y thự hiện á<br /> kỹ thu t tìm kiếm một t p hình ảnh liên quan từ ơ sở dữ liệu ảnh dựa trên trí h xu t tự ộng<br /> ặ trưng nội dung hình ảnh [3].<br /> Kiến trú hệ CBIR gồm 2 phần: (1) Trí h xu t ặ trưng thị giá ể tạo hỉ mụ ho<br /> hình ảnh; (2) Thự thi việ truy v n ảnh tương tự dựa trên hỉ mụ . Kết quả truy v n ảnh sẽ<br /> trả về k -ảnh tương tự nh t theo một ộ o ho trướ . Vì v y, trong hệ truy v n ảnh dựa trên<br /> nội dung l sự kết h p ủa nhiều lĩnh vự như: xử lý ảnh, thị giá máy tính, nh n dạng, xử lý<br /> dữ liệu, truy hồi thông tin [2, 4].<br /> Bướ ầu tiên ủa i toán truy v n ảnh dựa trên nội dung sẽ thự hiện tiền xử lý ảnh<br /> như: phân tí h m u, phân oạn ảnh, lọ ảnh, khử nhiễu ảnh,… Với một hình ảnh ã ư xử<br /> <br /> 140<br />  ph ng ph p a c iệ nh ựa nc ph n c a nh nh c n ng<br /> <br /> lý, thự hiện trí h lọ á ặ trưng thị giá ể tạo ra hỉ mụ mô tả hình ảnh [1, 2, 5], hữ<br /> ký n y ư dùng ể phân lớp tự ộng v phân loại ngữ nghĩa theo nội dung thị giá ủa<br /> hình ảnh.<br /> Vì v y, trí h xu t vùng ặ trưng l một tiền ề quan trọng ể tìm ra á hình ảnh<br /> tương tự trong hệ truy v n ảnh dựa trên nội dung CBIR. Có nhiều phương pháp trí h xu t<br /> vùng ặ trưng ã ư ề p như trí h xu t ối tư ng trung tâm ủa hình ảnh, trí h xu t<br /> thuộ tính ối tư ng ặ trưng [6, 7].<br /> B i áo tiếp n phương pháp phân oạn hình ảnh ể tạo hỉ mụ hình ảnh v ây a<br /> nhánh ân ằng trên không gian m u CIE L*a* * v phép iến ổi Wavelet. Tư ó, nhóm<br /> nghiên ứu xây dựng phương pháp tra ứu ảnh tương tự dựa trên u trú dữ liệu ây a<br /> nhánh ân ằng n y. Để giải quyết v n ề ã ặt ra, nội dung tiếp theo ủa i áo gồm<br /> những phần sau: Phần 2 ề p ến á ông trình liên quan ể minh hứng tính khả thi v<br /> sự ải tiến ủa phương pháp ề nghị; Phần 3 ề p á kiến thứ ơ sở ể l m nền tảng áp<br /> dụng ho phương pháp; Phần 4 trình y phương pháp phân oạn hình ảnh ể trí h xu t ối<br /> tư ng ặ trưng l m ơ sở tạo hỉ mụ hình ảnh; Phần 5 thự hiện truy v n ảnh ao gồm<br /> việ tạo ây a nhánh ân ằng v mô tả thự nghiệm; Phần 6 ưa ra kết lu n v hướng phát<br /> triển tiếp theo ủa i áo.<br /> <br /> 2. CÁC CÔNG TRÌNH LIÊN QUAN<br /> <br /> Nhiều ứng dụng liên quan ến truy v n ảnh ã ư phát triển v ứng dụng trong nhiều lĩnh<br /> vự khá nhau như ứng dụng trong thư viện số: CIRES, C-BIRD, PhotoFile, iMATCH [5]. Ứng<br /> dụng truy v n ảnh IRMA trong y họ dựa trên SVM, hệ truy v n ảnh y khoa CBMIR<br /> (Content-Based Medi al Image Retrieval) trên ảnh CT, hệ truy v n ảnh y khoa dựa trên phép<br /> iến ổi Wavelet, ứng dụng truy v n ảnh trên hệ thống GIS (Geographi Information<br /> System) [8-11].<br /> Một số ông trình liên quan ến truy v n nội dung ảnh ã ông ố gần ây như: trí h xu t<br /> ối tư ng trên hình ảnh dựa trên sự iến ổi giá trị histogram [12], truy v n ảnh tương tự dựa trên<br /> ối sánh á vùng ặ trưng v mối quan hệ tương tự ủa á vùng ặ trưng trên ảnh [13], truy<br /> v n ảnh m u dựa trên dò tìm á vùng ặ trưng ụ ộ ằng phương pháp Harris-Laplace<br /> [12], truy v n ảnh m u dựa trên mặt phẳng it v không gian m u L*a*b* [14], huyển ổi<br /> không gian m u v xây dựng h m m nhằm truy v n nội dung á ảnh m u [15],…<br /> Có nhiều phương pháp dò tìm ặ trưng ã ư giới thiệu, gồm: phương pháp dò gó<br /> v ạnh giới thiệu v o n m 1998 ởi Harris & M.Stephens, phương pháp dò tìm ặ trưng<br /> SIFT (Scale Invariant Features Transform) dựa trên phép lọ ủa mặt nạ tí h h p giữa hình<br /> ảnh v ạo h m DoG (Difference of Gaussians) ể x p xỉ toán tử Lapla ian ủa h m<br /> Gaussian ư D.Lowe giới thiệu n m 2003, phương pháp dò tìm ặ trưng SURF (Speeded<br /> Up Robust Features) ư Bay v ộng sự giới thiệu v o n m 2006, phương pháp dò iểm<br /> ặ trưng Harris Lapla ian dựa trên toán tử Lapla ian ủa h m Gaussian ư giới thiệu n m<br /> 2001 ởi Mikolaj zyk & C.S hmid [16].<br /> N m 1973, Harali k et al. ã giới thiệu ma tr n ồng xu t hiện (co-occurrence matrix)<br /> mô tả ặ tính u trú [5]. Trong phương pháp n y, ma tr n ồng xu t hiện ư xây dựng<br /> dựa trên hướng v khoảng á h giữa á iểm ảnh. Khi ó, ặ tính u trú ư trí h xu t<br /> từ ma tr n ồng xu t hiện ằng sự xu t hiện ó tính lặp lại ứng với á mứ xám.<br /> Acharya et al. ề xu t việ tính toán x p xỉ ối với ặ tính u trú dựa trên á nghiên<br /> ứu tâm lý trong nh n thứ thị giá về u trú . Cá thuộ tính u trú n y ho phân tí h<br /> theo ngữ nghĩa trự quan v ư sử dụng trong nhiều hệ truy v n ảnh dựa trên nội dung.<br /> Phép iến ổi Wavelet ã ư ứng dụng trong phân tí h u trú v phân lớp á hình ảnh<br /> <br /> <br /> 141<br />  g n h ng ạc n Th Thành<br /> <br /> dựa trên phép phân tá h a phân giải ủa á hình ảnh v mô tả u trú trên á t lệ khá<br /> nhau [1].<br /> C ng theo Acharya et al., n m 1962 Human ã xá ịnh ảy moment huẩn l m ặ<br /> trưng hình dạng v ng t iến ối với phép t lệ [1].<br /> Kumar et al. (2009) ã ề xu t phương pháp phân oạn ảnh tự ộng dựa trên phép iến<br /> ổi Wavelet nhằm tạo ra phân oạn nhanh v ơn giản. Trong i áo ã ho th y phương<br /> pháp hiệu quả tốt trên việ phân oạn á hình ảnh lớn v thự thi dễ d ng hơn á phương<br /> pháp khá [17].<br /> Tuy nhiên, nếu truy tìm hình ảnh dựa trên ối sánh trự tiếp nội dung ủa hình ảnh sẽ<br /> m t nhiều hi phí về thời gian ng như không gian truy v n. Do ó, ần ó phương pháp mô<br /> tả nội dung hình ảnh dưới dạng dữ liệu mô tả (metadata) ể từ ó thự hiện truy v n hình<br /> ảnh tương tự qua dữ liệu mô tả n y. Đối với nghiên ứu về ứng dụng hữ ký nhị phân tạo hỉ<br /> mụ ho hình ảnh, Yannis Manolopoulos ã mô tả hữ ký nhị phân ủa hình ảnh v thự<br /> hiện phân ụm hình ảnh dựa trên ây S-Tree [18]. Trong thự nghiệm ã ho th y tính hiệu<br /> quả khi áp dụng hữ ký nhị phân ối với dữ liệu hình ảnh.<br /> Nas imento v Chitkara ã tiếp n kỹ thu t truy v n ảnh dựa trên hỉ mụ nhị phân.<br /> Thự nghiệm ã ho th y tính hiệu quả khi truy v n trên á ơ sở dữ liệu ảnh lớn [19].<br /> N m 2013, Timothy Chappell v Shlomo Geva ã tiếp n tìm kiếm ảnh tương tự dựa<br /> trên hỉ mụ nhị phân, trong ông trình ã ưa ra tính hiệu quả v gia t ng tố ộ truy v n<br /> hình ảnh ứng dụng ộ o Hamming ho hữ ký nhị phân [20].<br /> Gần ây, á ông trình về truy v n ảnh dựa trên hỉ mụ nhị phân như: truy v n ảnh<br /> dựa trên hỉ mụ v ây hữ ký, truy v n ảnh dựa trên ộ o EMD v ây S-Tree, truy v n<br /> ảnh dựa trên hữ ký nhị phân, truy v n ảnh dựa trên ồ thị hữ ký [21-25].<br /> Việc truy v n ảnh dựa trên hỉ mụ mô tả l một hướng nghiên ứu khả thi v ó tính<br /> hiệu quả. Do ó, i áo tiếp c n phương pháp tạo ra chỉ mụ ho hình ảnh dựa trên á ặc<br /> trưng p th p như hình dạng, c u trú , m u sắc, vị trí ủa ối tư ng ặ trưng. Trên ơ sở<br /> n y, i áo thực hiện tạo ây a nhánh ân ằng v truy v n nhanh á hình ảnh tương tự.<br /> <br /> 3. CÁC LÝ THUYẾT CƠ SỞ<br /> <br /> 3.1. Các định nghĩa cơ sở<br /> 3.1.1. Kỳ vọng của các giá trị rời rạc<br /> Để trí h xu t u trú (texture) ủa á tín hiệu rời rạ , ướ ầu tiên ần tìm kỳ vọng ( ởi<br /> vì giá trị n y phản ánh ặ trưng ho xu hướng trung tâm ối với á giá trị rời rạ [26, 27]).<br /> Cho n tín hiệu ư mô tả ởi ve tor   (1 , 2 ,..., n ) , theo t i liệu [26, 27] giá trị kỳ<br /> 1 n<br /> vọng ư ịnh nghĩa:    i<br /> n i 1<br /> 3.1.2. Phương sai của các giá trị rời rạc<br /> Phương sai phản ánh mứ ộ phân tán ủa á giá trị iến ngẫu nhiên xung quanh giá<br /> trị kỳ vọng  . Từ ó, l m ơ sở trí h xu t ặ trưng u trú ủa á tín hiệu hình ảnh. Theo<br /> 1 n<br /> t i liệu [26, 27], phương sai ư ịnh nghĩa:    |  i   |2<br /> n  1 i 1<br /> <br /> <br /> <br /> <br /> 142<br />  ph ng ph p a c iệ nh ựa nc ph n c a nh nh c n ng<br /> <br /> 3.1.3. Độ lệch chuẩn của các giá trị rời rạc<br /> Khi ánh giá mứ ộ phân tán theo ơn vị o ủa á tín hiệu an ầu, ần tính ộ lệ h<br /> huẩn. Từ mứ ộ phân tán n y sẽ trí h xu t giá trị u trú ủa tín hiệu. Theo t i liệu [26, 27],<br />  <br /> ộ lệ h huẩn ư ịnh nghĩa l : .<br /> 3.2. Phép biến đổi Wavelet<br /> Phép iến ổi wavelet tạo ra sự phân tí h a t lệ l m ho tín hiệu ư phân rã v phân<br /> tí h hi tiết hơn [28]. Do ó, phép iến ổi wavelet sẽ phân tí h tín hiệu th nh tổng á tín<br /> hiệu ồng dạng ó t lệ thời gian trễ khá nhau.<br /> Vì v y, á th nh phần hi tiết mô tả u trú ủa tín hiệu khi h m wavelet ư họn ồng<br /> dạng với tín hiệu. Cá h m wavelet trự giao thường ư sử dụng ho phép iến ổi wavelet rời<br /> rạ v r t tiện dụng ho việ tái tạo lại tín hiệu an ầu sau quá trình nén dữ liệu [17].<br /> Khi thự hiện phép iến ổi wavelet, mỗi một tín hiệu ư phân tí h th nh hai th nh<br /> phần: th nh phần x p xỉ tương ứng với th nh phần tần số th p v th nh phần hi tiết tương<br /> ứng với th nh phần tần số ao, thông qua 2 ộ lọ thông th p v thông ao. Trong ó, ộ lọ<br /> thông ao sử dụng h m wavelet ψ(x) v ộ lọ thông th p sử dụng h m t lệ Φ(x) [28].<br /> Khi thự hiện phép iến ổi wavelet rời rạ ho một hình ảnh sẽ ó ư ốn dải tần on<br /> gồm LL, LH, HL, HH. Th nh phần LL l phiên ản thô ủa hình ảnh gố ; á th nh phần òn<br /> lại LH, HL, HH ứng với dải tần số ao hứa th nh phần thông tin hi tiết ủa hình ảnh [1].<br /> <br /> <br /> <br /> <br /> Hình 1. Minh họa phép iến ổi DFT<br /> 3.3. Phép biến đổi DWF<br /> Để nh n diện v ưa ra á ặ tính u trú ủa á iểm ảnh láng giềng ần sử dụng<br /> phép iến ổi DWF (Discrete Wavelet Frames) [28]. Đây l phương pháp tương tự với phép<br /> biến ổi wavelet rời rạ DWT (Discrete Wavelet Transform) dùng ể iến ổi ường ộ ảnh<br /> th nh á dải tần on. Sự khá iệt hính ủa 2 phương pháp n y ó l DWF sẽ ưa ra ộ lọ<br /> không ó mẫu on.<br /> Phép DWF thự thi trên ng tần lọ dựa trên phép lọ thông th p H ( z) ể phân giải<br /> mỗi th nh phần ường ộ ủa ảnh th nh một t p á ng tần on. Độ lệ h huẩn ủa t t ả<br /> á th nh phần hi tiết ư tính trong láng giềng ủa iểm ảnh p ể l m ặ trưng u<br /> trú . Phép lọ thông ao G( z )  zH ( z 1 ) ư ịnh nghĩa qua phép lọ thông th p H ( z) .<br /> Cá phép lọ ủa dãy ng tần lọ HV ( z ) , Gi ( z ) , i  1,...,V ư tạo ra từ H ( z) , G( z) sao<br /> cho: H k 1 ( z )  H ( z 2 ) H k ( z ) , Gk 1 ( z )  G ( z 2 ) H k ( z ) với k  0,...,V  1 , H 0 ( z)  1 .<br /> k k<br /> <br /> <br /> <br /> <br /> Trong thự nghiệm, phép lọ thông th p sử dụng phép iến ổi Haar Wavelet, tứ l<br /> H ( z )  12 (1  z 1 ) với iều kiện thông th p l H ( z) |z 1  1 . Khi ó, phép lọ thông ao ư<br /> ịnh nghĩa l G( z )  zH ( z 1 ) . Ve tor u trú ủa iểm ảnh p ư mô tả ằng ộ lệ h<br /> huẩn ủa t t ả th nh phần hi tiết v tính toán trên hình vuông láng giềng  ủa pixel p .<br /> Khi ó, ve tor ặ tính u trú ủa iểm ảnh p sẽ l : T ( p)  [1 ( p), 2 ( p),..., 9V ( p)] .<br /> <br /> <br /> <br /> 143<br />  g n h ng ạc n Th Thành<br /> <br /> <br /> <br /> <br /> Hình 2. Mô hình phép biến ổi DFW<br /> <br /> Ví dụ: ho ường ộ hình hữ nh t láng giềng ủa iểm ảnh p như sau:<br /> 5 4 2<br /> 2 6 3<br /> 3 4 2<br /> Ve tor u trú T ( p) với V  2 ứng với phép iến ổi Haar-Wavelet như sau:<br /> T ( p) = (2.50, 1.25, 2.00, 1.00, 1.00, 0.50, 1.00, 0.50, 3.00, 1.50, 1.50, 0.75, 1.50, 0.75,<br /> 2.00, 1.00, 1.00, 0.50).<br /> <br /> 4. PHÂN ĐOẠN ẢNH<br /> <br /> Để sử dụng hình dạng như l một ặ trưng ủa hình ảnh, ướ ơ ản l phân oạn<br /> hình ảnh ể tìm ối tư ng. Trong phương pháp n y, sẽ gom ụm á iểm ảnh thuộ về á<br /> vùng liên thông dựa trên m u sắ v u trú .<br /> B i áo sẽ tiếp n phân oạn hình ảnh sao ho mỗi hình ảnh ư phân oạn th nh á<br /> vùng ặ trưng ể từ ó l m ơ sở xây dựng hữ ký nhị phân nhằm mô tả nội dung hình ảnh.<br /> Ảnh phân oạn ư tạo ra từ việ nhóm á iểm ảnh trở th nh một vùng tương tự.<br /> B i áo tiếp n phương pháp phân oạn ảnh tự ộng dựa trên á thông tin p th p gồm<br /> m u sắ , u trú v vị trí á iểm ảnh.<br /> Để tính toán á giá trị n y, hình ảnh ư hia ra th nh á khối vuông f  f không<br /> giao nhau. Do ó, hình ảnh ư hia th nh L khối bl , l  1,..., L . Sau ó tính ve tor u<br /> trú v ve tor m u sắ ủa mỗi khối ằng giá trị trung ình ủa á iểm ảnh trong khối ó.<br /> <br /> <br /> <br /> <br /> Hình 3. Ví dụ hình ảnh tá h th nh 7 × 11 khối<br /> <br /> Kết quả phân oạn l mặt nạ phân oạn, tứ l một ảnh xám mô tả ối tư ng ặ trưng<br /> ủa hình ảnh. Dựa trên mặt nạ phân oạn, thự hiện tính toán vùng liên thông v loại ỏ á<br /> vùng liên thông ó diện tí h không vư t ngưỡng (trong thự nghiệm sẽ loại ỏ á vùng liên<br /> thông ó diện tí h nhỏ hơn 5% diện tí h ảnh).<br /> <br /> <br /> 144<br />  ph ng ph p a c iệ nh ựa nc ph n c a nh nh c n ng<br /> <br /> Thuật toán 1: Phân oạn ảnh<br /> Đầu vào: Ảnh m u I<br /> Đầu ra: Mặt nạ phân oạn M<br /> Bước 1: Trí h xu t ve tor u trú v ve tor ường ộ ho mỗi iểm ảnh.<br /> Bước 2: Tính tâm á khối ằng á h l y giá trị trung ình ve tor u trú v ve tor<br /> m u sắ ủa t t ả á iểm ảnh trong khối.<br /> Bước 3: Tính ộ tương phản C ủa hình ảnh ể tạo th nh ối tư ng nền v ối tư ng<br /> ặ trưng.<br /> Bước 4: Tìm á tâm ụm ho á ối tư ng ặ trưng ổ tr dựa trên ộ tương phản.<br /> Bước 5: Dựa trên t p á tâm ụm ủa á ối tư ng ặ trưng, thự hiện gom ụm á<br /> iểm ảnh.<br /> Bước 6: Tạo mặt nạ phân oạn M ứng với á iểm ảnh ã phân ụm.<br /> Bước 7: Loại ỏ á ối tư ng ó diện tí h nhỏ dựa trên mặt nạ phân oạn M<br /> Bước 8: Trả về mặt nạ phân oạn M .<br /> Đối với ve tor ặ trưng m u sắ ủa mỗi iểm ảnh I ( p)  ( I L ( p), I a ( p), Ib ( p)) ư<br /> xây dựng dựa trên không gian m u CIE L a b . Không gian m u CIE L a b ư<br /> * * *<br /> ông * * *<br /> <br /> nh n l huẩn quố tế v o th p niên 1970 ởi tổ hứ CIE v ồng nh t với nh n thứ on<br /> người. Khoảng á h Eu lidean giữa hai iểm trong không gian m u CIE L*a*b* tương ương<br /> với khoảng á h nh n thứ giữa 2 m u theo hệ thống thị giá ủa on người [1].<br /> Sau khi thự hiện trí h xu t u trú v m u sắ ủa hình ảnh, thự hiện quá trình gom<br /> ụm á iểm ảnh ằng phương pháp gom ụm K-Means. Bướ ầu tiên ủa quá trình gom<br /> ụm n y ó l họn ra tâm ụm dựa trên ộ tương phản C ủa hình ảnh. Để thự hiện nhanh<br /> quá trình n y, hình ảnh ư hia th nh L khối ảnh không giao nhau, mỗi khối ảnh n y ư<br /> xem l một iểm ảnh lớn (supper pixel). Do ó, ve tor u trú T b (bl ) v ve tor m u sắ I b (bl )<br /> ủa mỗi khối bl tương ứng với á giá trị trung ình ủa ve tor u trú v ve tor m u sắ ủa<br /> t t ả á iểm ảnh trong khối. Với bl , bn l 2 khối t kỳ, ộ tương phản ủa hình ảnh sẽ l :<br /> C  max{ || I b (bl )  I b (bn ) ||   || T b (bl )  T b (bn ) ||} (trong thự nghiệm     0.5 ). Sau khi tìm<br /> ư ộ tương phản C ủa hình ảnh, khối ó n ng lư ng th p hơn sẽ l tâm ụm nền<br /> (background) v khối ó n ng lư ng ao sẽ l tâm ụm ủa ối tư ng ặ trưng (foreground).<br /> Bướ tiếp theo sẽ thự hiện tìm tâm á ụm ủa á ối tư ng ặ trưng ổ sung, tứ<br /> l tìm á khối ó ộ o d gần với ối tư ng ặ trưng nh t (tương ứng sẽ l xa nh t ối với<br /> m u nền). Trong thự nghiệm sẽ tìm á tâm ụm ó ộ o d  C (với   0.4 ). Sau ó,<br /> thự hiện phép gom ụm ho t t ả á iểm ảnh.<br /> Bướ uối ùng l loại ỏ á vùng liên thông ó diện tí h không vư t ngưỡng  . Việ<br /> tính diện tí h vùng dựa trên thu t toán loang 4-liên thông ư tóm tắt như sau:<br /> Thuật toán 2: Tính diện tí h vùng<br /> Đầu vào: Mặt nạ phân oạn M v vị trí (r, )<br /> Đầu ra: Giá trị diện tí h S<br /> Bước 1: Khởi tạo S = 0;<br /> Stack = ;<br /> Bước 2: Push(Stack, r, c);<br /> Bước 3: while Stack   do<br /> <br /> 145<br />  g n h ng ạc n Th Thành<br /> <br /> (r,c) = Pop(Stack);<br /> S = S + 1;<br /> If (r > 1)&& (M(r,c) = M(r-1,c) then<br /> Push(Stack,r-1,c);<br /> If (r < rows)&&(M(r,c)= M (r+1,c) then<br /> Push(Stack,r+1,c);<br /> If (c > 1)&&M(r,c) == M (r,c-1) then<br /> Push(Stack,r,c-1);<br /> If (c < columns)&&M(r,c) = M(r,c+1) then<br /> Push(Stack,r,c+1);<br /> Bước 4: Return S;<br /> <br /> <br /> <br /> <br /> Hình 4. Một số kết quả mẫu phân oạn ảnh<br /> <br /> <br /> 5. TRUY VẤN ẢNH<br /> <br /> 5.1. Tạo chỉ mục nhị phân<br /> Đặ trưng ủa hình ảnh ó thể ư mô tả ằng một ve tor ặ tính a hiều gọi l l<br /> hữ ký ủa hình ảnh (image signature).<br /> <br /> <br /> <br /> <br /> Hình 5. Minh họa á h tạo chữ ký nhị phân<br /> <br /> Sau khi tạo hỉ mụ ho hình ảnh trong ơ sở dữ liệu, iều quan trọng l sử dụng một<br /> ộ o tương tự nhằm truy v n trong ơ sở dữ liệu.<br /> <br /> <br /> 146<br />  ph ng ph p a c iệ nh ựa nc ph n c a nh nh c n ng<br /> <br /> 5.2. Độ đo tƣơng tự<br /> Gọi sig I v sig J lần lư t l 2 hữ ký nhị phân ủa hai hình ảnh I v J . Độ trùng<br /> khớp di ư ối sánh trên mỗi phần tử ủa 2 hữ ký v ư ịnh nghĩa như sau:<br /> <br /> 1 if ( sig i  sig i )<br /> I J<br /> di  <br /> 0 if ( sig i  sig i )<br /> I J<br /> <br /> <br /> <br /> 1 n<br /> Độ o tương tự ủa 2 hình ảnh I v J ư ịnh nghĩa l :    di . Dễ d ng hứng<br /> n i 1<br /> minh  thỏa á tính h t ủa một huẩn, gồm:<br /> (1) Không âm:  (sigI , sig J )  0<br /> Nếu  (sigI , sig J )  0  sigI  sig J<br /> (2) Đối xứng:  (sig I , sig J )   (sig J , sigI )<br /> (3) B t ẳng thứ tam giá :<br />  (sigI , sig J )   (sigJ , sigK )   (sigI , sigK )<br /> <br /> 5.3. Cây đa nhánh cân bằng<br /> Nhằm giảm không gian v t ng tố ộ truy v n, nhóm nghiên ứu xây dựng ây a<br /> nhánh ân ằng lưu trữ á hỉ mụ mô tả hình ảnh. Mỗi một nút trong ây lưu trữ t p á<br /> phần tử { SIG, p} , với SIG l hữ ký v p l on trỏ tham hiếu ến nút on. Cá nút lá sẽ lưu<br /> trữ á phần tử { sig, oid } , với sig l hỉ mụ ủa mỗi hình ảnh v oid l ịnh danh ủa hình<br /> ảnh tương ứng. Quá trình tạo ây dựa trên thao tá hèn v tá h nút trong ây. Thu t toán tạo<br /> ây hữ ký ư ề xu t như sau:<br /> Input: t p á hỉ mụ S = {sig1,…,sign}<br /> Output: ây ây a nhánh T<br /> Algorithm1. Gen-Stree(S, Root)<br /> Begin<br /> Bước 1.<br /> v = Root;<br /> If S =  then STOP;<br /> Else Chọn  S v S = S \ ;<br /> Qua ướ 2;<br /> Bước 2.<br /> If (v l nút lá) then<br /> begin<br /> If v.count < M then v = v  ;<br /> Else SplitNode(v, sig);<br /> Quay lại ướ 1;<br /> end<br /> Else<br /> <br /> <br /> 147<br />  g n h ng ạc n Th Thành<br /> <br /> begin<br /> W = {SIGi | SIGi  v v SIGisig  sig = sig};<br /> EMD(SIG0sig, sig) = min{EMD(SIGisig,sig)| SIGi  W};<br /> v = SIG0p;<br /> Quay lại ướ 2;<br /> end<br /> End.<br /> Thu t toán Algorithm1 lần lư t ưa á hỉ mụ sig từ t p hữ ký S v o trong ây. Với<br /> mỗi hỉ mụ sig sẽ ư hèn v o nút lá phù h p, nếu nút lá ầy thì quá trình tá h nút sẽ<br /> ư thự hiện v ây a nhánh t ng trưởng hiều ao theo hướng gố ủa ây. Tại mỗi nút<br /> trong ủa ây, sẽ ưu tiên i theo hướng ó ộ tương tự nhiều hơn, quá trình n y sẽ ư<br /> duyệt ho ến khi tìm ra ư nút lá phù h p. Quá trình duyệt ây không nh t thiết phải<br /> duyệt qua t t ả á hướng ó hữ ký phù h p với hữ ký hình ảnh ần hèn, iều n y sẽ<br /> giảm một khoảng hi phí áng kể trong quá trình tìm ra á nút lá phù h p ể hèn hữ ký<br /> v o ây. Do ó, ứng với mỗi hữ ký ần hèn sẽ duyệt qua ường i ó hiều ao<br /> h  log m n  1 , với m l số hữ ký tối thiểu ủa một nút trong ây. Gọi k l hiều d i ủa<br /> mỗi hữ ký, mỗi một nút trong ủa ây sẽ ó tối a l M hữ ký, vì v y quá trình duyệt ây<br /> ể tìm ra nút lá phù h p sẽ ó hi phí tối a l k  M  log m n  1 . Tuy nhiên, khi tìm ra nút<br /> l phù h p nhưng ã ị ầy, ần phải thự hiện quá trình tá h nút. Việ tá h nút dựa trên ơ<br /> sở phép toán   seed ,   seed , ư thự hiện theo thu t toán ề xu t như sau:<br /> Input: Nút ần tá h v<br /> Output: Cây T sau khi thự hiện phép tá h nút<br /> Algorithm2. SplitNode(v)<br /> Begin<br /> Tạo nút v v v lần lư t hứa hữ ký   seed v   seed ;<br /> v = v \ {   seed ,   seed };<br /> For (SIGi  v)<br /> begin<br /> If(EMD(SIGisig,   seed ) < EMD(SIGisig,   seed ))then<br /> v = v  SIGi;<br /> Else<br /> v = v  SIGi;<br /> end<br /> s =  SIG , với SIG  v<br /> i i<br /> <br /> <br /> s =  SIG  , với SIG   v<br /> i i<br /> <br /> If ( v parent != null) then v parent  v parent  s ; v parent  v parent  s ;<br /> If ( v parent .count > M) then SplitNode( v parent );<br /> If ( v parent = null) then Root = { s , s };<br /> End.<br /> 148<br />  ph ng ph p a c iệ nh ựa nc ph n c a nh nh c n ng<br /> <br /> 5.4. Thuật toán truy vấn ảnh dựa trên cây S-tree<br /> Sau khi lưu trữ hỉ mụ v ịnh danh ủa hình ảnh tương ứng trên ây, quá trình truy<br /> v n sẽ tìm ra á hữ ký tương tự ủa hình ảnh dựa trên việ duyệt ây. Sau khi tìm ra á<br /> hữ ký hình ảnh, dựa v o ịnh danh ủa á hình ảnh sẽ tìm ra ụ thể á hình ảnh tương tự<br /> với hình ảnh truy v n. Do ó, i toán ần thự hiện l tìm ra hữ ký ủa hình ảnh v ịnh<br /> danh tương ứng, quá trình truy v n n y ư thự hiện theo thu t toán ề xu t như sau:<br /> Input: hữ ký truy v n sig v T<br /> Output: T p ác hữ ký ảnh v á ịnh danh tham hiếu ến hình ảnh tương ứng<br /> Algorithm3. Search-Image-Sig(sig, S-tree)<br /> Begin<br /> v = root; SIGOUT = ; Stack = ; Push(Stack, v);<br /> while(not Empty(Stack)) do<br /> begin<br /> v = Pop(Stack);<br /> If(v is not Leaf) then<br /> begin<br /> For(SIGi  v and SIGisig  sig = sig) do<br /> EMD(SIG0sig,sig)= min{EMD(SIGisig,sig)|SIGiv};<br /> Push(Stack, SIG0  next);<br /> end<br /> Else SIGOUT = SIGOUT{|SIGiv};<br /> end<br /> return SIGOUT;<br /> End.<br /> <br /> 5.5. Thực nghiệm truy vấn ảnh<br /> B i áo thự hiện quá trình truy v n ảnh tương tự trên dữ liệu thự nghiệm gồm Corel<br /> v Image O je t (MSRC). Cá hình ảnh trong á t p dữ liệu n y ư hia th nh á hủ ề<br /> khá nhau. Ứng với mỗi hình ảnh truy v n sẽ tìm ra á hình ảnh tương tự trong t p dữ liệu<br /> ảnh n y.<br /> Ứng dụng thự nghiệm ư xây dựng trên nền tảng ông ụ IPT (Image Pro essing<br /> Too ox) ủa Matla 2015. Thự nghiệm ư thự thi trên máy tính với ộ xử lý Intel(R)<br /> CoreTM i7-2620M, CPU 2.70GHz, RAM 4GB, Hệ iều h nh Windows 7 Professional 64 it.<br /> <br /> <br /> <br /> <br /> Hình 6. Mô hình truy v n ảnh<br /> <br /> 149<br />  g n h ng ạc n Th Thành<br /> <br /> Quá trình truy v n hình ảnh ư hia l m 2 giai oạn gồm: Giai oạn tiền xử lý gồm<br /> á ướ : (1) Phân oạn hình ảnh ứng; (2) Tạo hỉ mụ ể tạo th nh t p hữ ký ảnh; (3) Tạo<br /> ây a nhánh ân ằng. Giai oạn truy v n ảnh thự hiện: (1) Phân oạn ảnh truy v n; (2)<br /> Tạo hỉ mụ ho ảnh truy v n; (3) Thự hiện truy v n ảnh ể tìm á hình ảnh tương tự.<br /> <br /> <br /> <br /> <br /> Hình 7. Một số kết quả truy v n ảnh<br /> <br /> <br /> <br /> <br /> Hình 8. Độ phủ v ộ hính xá khi truy v n ảnh trên t p dữ liệu ảnh COREL<br /> <br /> Độ phủ (recall) = (số ảnh truy v n ó liên quan)/(Tổng số ảnh ó liên quan trong t p dữ<br /> liệu ảnh)<br /> Độ hính xá (precision) = (số ảnh truy v n ó liên quan)/(Ngưỡng xá ịnh số ảnh truy v n)<br /> <br /> 150<br />  ph ng ph p a c iệ nh ựa nc ph n c a nh nh c n ng<br /> <br /> <br /> <br /> <br /> Hình 9. Độ phủ v ộ hính xá khi truy v n ảnh trên t p dữ liệu ảnh CBIRinages<br /> <br /> <br /> <br /> <br /> Hình 10. Thời gian truy v n ảnh trung ình trên t p dữ liệu ảnh COREL<br /> <br /> <br /> <br /> <br /> Hình 11. Thời gian truy v n ảnh trên t p dữ liệu ảnh CBIRimages<br /> B ng 1. So sánh ộ hính xá truy v n giữa á phương pháp<br /> <br /> Độ hính xá Độ phủ Độ o F-measure Thời gian truy<br /> Phương pháp v n trung ình<br /> trung ình trung ình trung ình<br /> S-Tree 0,42 0,55 0,476289 186,25 I/Os<br /> Fuzzy Signatures N/A N/A N/A 20-50 I/Os<br /> Fuzzy color histogram 0,50688 0,61625 0,55624 4,41863 sec<br /> Interest region 0,85200 0,78375 0,81645 4,78516 sec<br /> Phương pháp ề xu t 0,687480469 0,687487535 0,687484002 ec<br /> <br /> 6. KẾT LUẬN<br /> B i áo ã tiếp c n quá trình tạo chỉ mục dựa trên phân oạn hình ảnh ể tạo th nh hữ<br /> ký nhị phân v ây a nhánh ân ằng ể từ ó thực hiện i toán truy v n ảnh tương tự dựa<br /> trên nội dung. B i áo ã mô tả quá trình phân oạn hình ảnh dựa trên không gian m u CIE<br /> <br /> 151<br />  g n h ng ạc n Th Thành<br /> <br /> L*a* * v phép iến ổi Wavelet ể l m tiền ề tạo chữ ký nhị phân. Theo thực nghiệm cho<br /> th y việc truy v n ảnh dựa trên hữ ký nhị phân mang lại nhiều hiệu quả ồng thời giúp ho<br /> việ tìm kiếm nhanh v giảm áng kể không gian truy v n trong quá trình ối sánh ảnh<br /> tương tự. Tuy nhiên, ối với phương pháp tạo chỉ mục nhị phân như trên sẽ cho kết quả<br /> hính xá th p nếu ảnh bị phân tán m u sắ v vị trí. Hơn nữa, nếu thực hiện truy v n trực<br /> tiếp trên dữ liệu mô tả n y ó thể tốn kém thời gian nếu như dữ liệu chữ ký ảnh lớn. Vì v y,<br /> hướng phát triển của i áo sẽ tạo ra chữ ký nhị phân ủa hình ảnh vừa mô tả hình dạng, vị<br /> trí v m u sắ . Đồng thời thực hiện tiền xử lý gom ụm chữ ký tương tự ể giúp ho quá<br /> trình truy v n nhanh v hiệu quả.<br /> Lờ n: Nghiên ứu n y ư Trường Đại họ Công nghiệp Thự phẩm TP.HCM t i<br /> tr v ư nhóm nghiên ứu SBIR-HCM, Trường Đại họ Sư phạm TP.HCM hỗ tr về<br /> huyên môn v ơ sở v t ch t.<br /> <br /> T I LIỆU THAM HẢO<br /> 1. Acharya T., Ray A.K - Image processing: principles and applications, John Wiley &<br /> Sons Inc. (2005).<br /> 2. Oge Marques Borko Furht - Content-based image and video retrieval, Springer<br /> Science + Business Media New York, 2002.<br /> 3. James Z. Wang - Integrated Region-Based Image Retrieval, Springer Science Business<br /> Media New York, 2001.<br /> 4. Michael. S. Lew - Principles of Visual Information Retrieval, Springer-Verlag London, 2001.<br /> 5. Muneesawang P. - Multimedia Database Retrieval: Technology and Applications,<br /> Springer Heidelberg New York, 2014.<br /> 6. Kim S. - Central Object Extraction for Object-Based Image Retrieval, Springer-<br /> Verlag, LNCS, 2728, (2003) 39-49.<br /> 7. Jianru Xue - Automatic salient object extraction with contextual cue and its app<br /> 8. Huang Y., Zhang J., Zhao Y., Ma D. - Medical image retrieval with query-dependent<br /> feature fusion based on one-class SVM, in ICCES: 13th IEEE International Conference<br /> on Computational Science and Engineering (2010) 176-183.<br /> 9. Jin L., Hong L. Lianzhi T. - A mapping modelling of visual feature and knowledge<br /> representation approach for Medical Image Retrieval, in: 2009 International<br /> Conference on Mechatronics and Automation (2009) 1778-1783.<br /> 10. Rajakumar K., Muttan S. - Medical image retrieval using energy efficient wavelet<br /> transform, in: 2010 Second International conference on Computing, Communication<br /> and Networking Technologies (2010) 1-5.<br /> 11. Shea G. Y. K., Cao J. - Geo-Planar Indexing (GPI) – An efficient indexing scheme for<br /> fast retrieval of raster-based geospatial data in mobile GIS application, Proc. of IEEE<br /> CISP (2012) 1047-1052.<br /> 12. Wang X. Y. - Robust Image Retrieval Based on Color Histogram of Local Feature<br /> Regions, Springer Science, Multimed Tools Appl. 49 (2010) 323-345.<br /> 13. Bartolini I., Ciaccia P., Patel M. - Query processing issues in region-based image<br /> databases, Knowledge and Information Systems 25 (2) (2010) 389-420.<br /> 14. Wang X.Y. - Robust color image retrieval using visual interest point feature of<br /> signifi ant it-planes, DSP 23 (4) (2013) 1136-1153.<br /> 15. Tang Z. - Robust Image Hash Function Using Local Color Features, Int. J. Electron.<br /> Commun. 67 (2013) 717-722.<br /> 16. Wang X.Y. - Robust color image retrieval using visual interest point feature of<br /> significant bit-planes, Digital Signal Processing 23 (4) (2013) 1136-1153.<br /> 152<br />  ph ng ph p a c iệ nh ựa nc ph n c a nh nh c n ng<br /> <br /> 17. Kumar H.C.S., Raja K.B., Venugopal K.R., Patnaik L.M. - Automatic Image<br /> Segmentation using Wavelets, IJCSNS International Journal of Computer Science and<br /> Network Security 9 (2) (2009) 305-313.<br /> 18. Manolopoulos Y. - Advanced Signature Indexing for Multimedia and Web<br /> Applications, Springer Science New York, 2003.<br /> 19. Nascimento M. A., Chitkara V. - Color-based image retrieval using binary signatures,<br /> SAC Madrid (2002) 687-692.<br /> 20. Timothy Chappell, Shlomo Geva - Effi ient Top-K retrieval with signatures,<br /> ADCS’13, Bris ane (2013) 10-17.<br /> 21. Nascimento M. A. - Image indexing and retrieval using signature trees, Data &<br /> Knowl. Engineering 43 (2002) 57-77.<br /> 22. Thanh Manh Le, Thanh The Van - Image retrieval system based on emd similarity<br /> measure and S-Tree, ICITES-2012, Springer Verlag, LNEE 234 (2013) 139-146.<br /> 23. Huang P.W. - Indexing pictures by key objects for large-scale image database, Pattern<br /> Recognition 30 (7) (1997) 1229-1237.<br /> 24. Thanh T.V., Thanh M. Le. - Image retrieval Based on Binary signature and S-kGraph,<br /> Jour. of Annales Univ. Sci. Budapest., Sect. Comp. 43 (2014) 105-122.<br /> 25. Thanh The Van, Thanh Manh Le - RBIR Based on Signature Graph, ICCCI-2014,<br /> IEEE Xplore (2014) 1-4.<br /> 26. Lê Sĩ Đồng - Xá su t v thống kê v ứng dụng, NXB Giáo dụ , 2004.<br /> 27. Feller W. - An introduction to probability theory and its applications, Vol. 1, 3rd Ed.,<br /> John Wiley & Sons Inc., New York (1968).<br /> 28. Unser M. - Texture lassifi ation and segmentation using wavelet frames, IEEE Trans.<br /> on Im. Processing 4 (11) (1995) 1549-1560.<br /> <br /> ABSTRACT<br /> <br /> A METHOD OF IMAGE RETRIEVAL USING BALANCE TREE<br /> <br /> Nguyen Phuong Hac*, Van The Thanh<br /> Ho Chi Minh City University of Food Insdustry<br /> *Email: hacnp@hufi.edu.vn<br /> <br /> The paper approaches a method of image retrieval using balance tree to store meta-data<br /> of image features by index to describe the shape of interest objects of image. In order to<br /> extract interest objects, we propose the image segmentation method on the base of low-level<br /> visual features including color and texture of image. The features are extracted at each block<br /> of image by Wavelet transformation and CIE L*a*b* color space. From there, we cluster all<br /> pixels to give connected regions; at the same time, we remove regions that have area less<br /> than threshold. Based on extracted features, we find out the contrast of image in order to<br /> extract background and foreground. On the base of segmented image, the feature indexes are<br /> created in order to match similar images. Then, we create the balance tree to store the feature<br /> indexes and search the set of similar images based on this structure. To illustrate the<br /> proposed method, the paper builds application and assesses experimental results on image<br /> databases including Corel and Image Object (MSRC). The results of our method are<br /> compared with others and show the effective of our proposed method.<br /> Keywords: Segmentation method, interest object, feature index.<br /> <br /> <br /> 153<br />