Hệ truy vấn ảnh sử dụng chữ ký mờ và cây FS-TREE

TẠP CHÍ KHOA HỌC CÔNG NGHỆ SỐ 02/2014 
 7 
H TRUY V	N NH S
 DNG CH KÝ M VÀ CÂY FS-TREE 
VN TH THÀNH 
Trung tâm Công ngh
 Thông tin - Trng ðH Công nghi
p Thc phm Tp.HCM 
TÓM TT 
Việc truy vấn ảnh sẽ tìm ra các hình ảnh tương tự về nội dung với hình ảnh cần truy 
vấn. Vấn đề đặt ra là cần xây dựng một hệ thống tìm kiếm các hình ảnh tương tự nhưng 
vẫn đảm bảo về tốc độ và không gian truy vấn. Để giải quyết bài toán tìm kiếm ảnh tương 
tự này, bài báo sẽ trích xuất vùng đặc trưng màu sắc trên mỗi hình ảnh dựa trên phương 
pháp Harris-Laplace, đồng thời xây dựng cấu trúc chữ ký mờ để mô tả các đặc trưng về nội 
dung màu sắc của hình ảnh theo chuẩn MPEG7. Trên cơ sở chữ ký mờ, bài báo tiến hành 
đánh giá độ đo tương tự giữa các chữ ký mờ của hình ảnh qua độ đo mờ Hamming, từ đó 
đánh giá độ tương tự giữa các hình ảnh. Hơn nữa, nhằm gia tăng tốc độ truy vấn, bài báo 
đề xuất cấu trúc dữ liệu cây FS-Tree (fuzzy S-Tree) để lưu trữ các chữ ký mờ dựa trên độ 
đo FHD (fuzzy Hamming distance). Tiếp theo, bài báo xây dựng thuật toán truy vấn hình 
ảnh trên cây FS-Tree và kết xuất ra các hình ảnh tương tự với hình ảnh cần truy vấn. Sau 
cùng, bài báo đưa ra mô hình thực nghiệm và đánh giá phương pháp dựa trên dữ liệu hình 
ảnh mẫu Corel gồm 10,800 hình ảnh. 
Từ khóa: Truy vấn ảnh, FHD, FS-Tree, Chữ ký mờ 
IMAGE RETRIEVAL SYSTEM USING FUZZY SIGNATURE AND 
FS-TREE 
ABSTRACT 
To query image will find out the similar images in content with the query image. The 
problem need to build the image retrieval system to find the similar images which ensure 
the speed and space to query. In order to solve this problem, the paper extracts the color 
feature regions in each image on the base of Harris-Laplace detector, at that time to build 
the fuzzy signature structure to describe the feature region in color content of image with 
the MPEG7 standard. According to the fuzzy signature, the paper evaluates the similar 
measure between the fuzzy signatures of images through the Hamming fuzzy measure, 
from there to assess the similarity between the images. Moreover, in order to speed up 
query image, the paper provides the data structure FS-Tree (fuzzy S-Tree) to store the 
fuzzy signatures on the base of FHD measure (fuzzy Hamming distance). Next, the paper 
builds the image retrieval algorithm in FS-Tree and shows the similar images with the 
query image. Finally, the paper gives the experimental model and assesses the propose 
method on the base of the Corel’s sample image dataset which have 10,800 color images. 
Keywords: Image Retrieval, FHD, FS-Tree, Fuzzy Signature 
KHOA HỌC QUẢN LÝ 
 8 
1. Gi
i thiu 
Tìm kiếm hình ảnh trong một tập lớn các hình ảnh là một bài toán khó. Một cách giải 
quyết là gán nhãn các hình ảnh [6, 7] nhưng sẽ tốn nhiều chi phí, tiêu tốn nhiều thời gian 
và không khả thi cho nhiều ứng dụng khác nhau. Hơn nữa, quá trình xử lý gán nhãn phụ 
thuộc vào ngữ nghĩa mô tả hình ảnh. Vì vậy hệ truy vấn ảnh dựa trên nội dung được phát 
triển nhằm rút trích các thuộc tính thị giác để mô tả nội dung của hình ảnh [6, 8]. Một số hệ 
thống truy vấn ảnh số đã xây dựng như: QBIC, ADL, DBLP, Virage, Alta Vista, SIMPLY 
city, 
Các công trình về truy vấn hình ảnh dựa trên nội dung như: Hệ truy vấn ảnh dựa trên 
histogram màu [6], lượng tử hoá và so sánh độ tương tự của hình ảnh dựa trên histogram 
màu [7], độ đo tương tự hình ảnh dựa trên việc kết hợp màu sắc và cấu trúc hình ảnh [9], 
truy vấn hình ảnh dựa trên màu sắc [10], truy vấn hình ảnh dựa trên độ tương tự của hình 
ảnh [8], truy vấn ảnh dựa trên histogram và cấu trúc hình ảnh [11], kỹ thuật truy vấn ảnh 
VBA (Variable-Bin Allocation) dựa trên chữ ký dạng chuỗi bit nhị phân và cây chữ ký 
S-Tree [8], lượng tử hoá màu sắc để giảm số chiều không gian màu sắc [12], 
Trong cách tiếp cận của bài báo sẽ tạo ra chữ ký mờ của một hình ảnh, là cách mô tả 
trừu tượng về phân bố màu sắc của hình ảnh. Nội dung của bài báo sẽ hướng đến việc truy 
vấn hiệu quả các “hình ảnh tương tự” trong một hệ thống dữ liệu lớn về hình ảnh. Trong 
bài báo này sẽ tiếp cận việc mô tả ngữ nghĩa về mặt nội dung của hình ảnh thông qua chữ 
ký mờ, đồng thời xây dựng lưu trữ chữ ký này lên cây FS-Tree. Cấu trúc dữ liệu FS-Tree 
sẽ mô tả mối quan hệ giữa các chữ ký mờ, từ đó mô tả mối quan hệ giữa các nội dung của 
hình ảnh. Dựa trên việc mô tả mối quan hệ ngữ nghĩa nội dung hình ảnh của cấu trúc dữ 
liệu FS-Tree, bài báo sẽ tiến hành tìm ra các hình ảnh tương tự theo nội dung trên các cơ sở 
dữ liệu ảnh Corel. [16] 
Bài báo thực hiện việc xây dựng hệ truy vấn ảnh tương tự dựa trên vùng đặc trưng 
cục bộ RBIR (region-based image retrieval). Trước hết, bài báo sẽ trích xuất các điểm đặc 
trưng dựa vào phương pháp Harris-Laplace, từ đó tạo ra các vùng đặc trưng cho hình ảnh. 
Dựa trên các vùng đặc trưng này bài báo sẽ tạo ra các chữ ký mờ và đánh giá độ tương tự 
của hình ảnh. Nhằm gia tăng tốc độ truy vấn, bài báo xây dựng cây FS-Tree lưu trữ các 
chữ ký nhị phân để từ đó xây dựng thuật toán truy vấn hình ảnh tương tự trên cây FS-Tree. 
Bài báo sẽ đóng góp được hai phần chính đó là giảm khối lượng không gian truy vấn và 
làm tăng tốc độ truy vấn các đối tượng ảnh trên một cơ sở dữ liệu ảnh lớn. 
Đóng góp của bài báo trong việc xây dựng chữ ký mờ dựa trên histogram của hình 
ảnh và xây dựng độ tương tự giữa các hình ảnh dựa trên độ đo mờ Hamming. Qua đó, bài 
báo đóng góp thuật toán và phương pháp truy vấn ảnh tương tự dựa trên việc xây dựng cấu 
trúc dữ liệu cây FS-Tree. Mục tiêu của bài báo nhằm giảm không gian và làm tăng tốc độ 
truy vấn ảnh trên dữ liệu ảnh lớn. 
TẠP CHÍ KHOA HỌC CÔNG NGHỆ SỐ 02/2014 
 9 
2. Các kin thc cơ s 
2.1. Ch ký nh phân 
Chữ ký nhị phân là vector bit được tạo thành bằng phép băm các đối tượng dữ liệu 
[5], chữ ký sẽ có k bit 1 và ( )m k− bit 0 trong dãy bit [1.. ]m , với m là chiều dài của chữ 
ký. Các đối tượng dữ liệu và các đối tượng truy vấn được mã hóa trên cùng một thuật toán 
mã hóa chữ ký. Khi các bit trong chữ ký đối tượng dữ liệu is hoàn toàn phủ các bit trong 
chữ ký truy vấn qs , thì đối tượng dữ liệu này là một ứng viên thỏa câu truy vấn. Theo tài 
liệu [5], kết quả truy vấn sẽ có ba trường hợp xảy ra, gồm: 
(1) Đối tượng dữ liệu phù hợp với câu truy vấn. Khi đó mọi bit trong qs được phủ bởi 
các bit trong chữ ký is của đối tượng dữ liệu (nghĩa là q i qs s s∧ = ); 
(2) Đối tượng không phù hợp với câu truy vấn (nghĩa là q i qs s s∧ ≠ ); 
(3) Chữ ký được đối sánh và cho ra một kết quả phù hợp, nhưng đối tượng dữ liệu 
không phù hợp với điều kiện tìm kiếm trong câu truy vấn. Để loại ra trường hợp này, các 
đối tượng phải được kiểm tra sau khi các chữ ký đối tượng được đối sánh phù hợp. 
2.2. Ch ký m 
Chữ ký mờ F có chiều dài m là một vector 1 2( , ,..., )mf f f , với [0,1]if ∈ , 1,...,i m= [2]. 
Phép kết nối chữ ký mờ iF và jF là một chữ ký mờ: [2] 
1 1 2 2( , ,..., )∧ = ∧ ∧ ∧i j i j i j i jm mF F f f f f f f , với min{ , }∧ =i j i jr r r rf f f f , 1,...,r m= 
Phép kết hợp chữ ký mờ iF và jF là một chữ ký mờ: [2] 
1 1 2 2( , ,..., )∨ = ∨ ∨ ∨i j i j i j i jm mF F f f f f f f , với max{ , }∨ =i j i jr r r rf f f f , 1,...,r m= 
2.3. Cây ch ký S-Tree 
S-Tree [5, 8] là cây nhiều nhánh cân bằng, mỗi một nút của S-Tree nhiều cặp phần tử 
,s p〈 〉 , với s là một chữ ký nhị phân, p là con trỏ tham chiếu đến nút con. Nút gốc của cây 
chứa ít nhất là hai cặp phần tử và nhiều nhất là M cặp phần tử ,s p〈 〉 . Mỗi nút trong của 
cây chứa ít nhất là m cặp phần tử ,s p〈 〉 và nhiều nhất là M cặp phần tử ,s p〈 〉 , với 
1 2
Mm≤ ≤ . Mỗi một nút lá của cây S-Tree chứa tập các phần tử ,s oid〈 〉 , với oid là định 
danh của đối tượng, s là chữ ký của đối tượng tương ứng. Mỗi chữ ký tại một nút cha là tổ 
hợp tất cả các chữ ký của nút con. Chiều cao tối đa của cây S-Tree có n chữ ký sẽ là 
log 1
m
h n=  −  . 
Quá trình xây dựng cây S-Tree được thực hiện dựa trên thao tác chèn và tách nút. Tại 
thời điểm bắt đầu, cây S-Tree chỉ chứa một nút lá rỗng, sau đó từng chữ ký sẽ được chèn 
KHOA HỌC QUẢN LÝ 
 10 
vào trong cây S-Tree. Khi nút lá v trở nên đầy sẽ được tách thành hai nút, đồng thời nút 
cha parenv sẽ được tạo ra (nếu chưa tồn tại) và hai chữ ký mới sẽ được đặt vào nút parenv . 
Hình 1. Mt ví d# v$ cây S-Tree [8] 
2.4. ð ño m Hamming 
Cho hai vector giá trị thực n-chiều x và y , gọi tập mờ về độ khác nhau là ( , )D x yα , 
với hàm thuộc là 
2( )
( , ) 1
x y
D x y e
α
αµ − −= − . Theo tài liệu [4], khoảng cách mờ Hamming FHD 
giữa x và y được ký hiệu là ( , )FHD x yα là lực lượng mờ của tập mờ ( , )D x yα và có 
hàm thuộc ứng với tham số α là: ( , ) ( ) :{0,1,...,n} [0,1]FHD x yµ α → . Mức độ khác nhau của x 
và y tại thành phần thứ k , ứng với hằng số điều chỉnh α sẽ là: 
( , ) ( ( , ))( ; ) ( )FHD x y Card D x yk k
α
µ α µ= , với {0,1,..., }, | ( ( , )) |∈ =k n n Support D x yα . 
2.4. Trích xu$t vùng ñ(c trưng c*a hình ,nh 
Để trích xuất đặc trưng thị giác của hình ảnh, bước đầu tiên cần phải chuẩn hóa kích 
thước hình ảnh, tức là chuyển đổi các hình ảnh đầu vào có kích thước khác nhau trở thành 
hình ảnh có kích thước ×k k để từ đó rút trích các đặc trưng màu sắc của hình ảnh. Vì ảnh 
theo chuẩn JPEG được mô tả trên không gian màu YCbCr, do đó cần sử dụng không gian 
màu YCbCr để trích xuất thông tin đặc trưng của ảnh. Gọi Y, Cb, Cr lần lượt là cường độ 
sáng, thành phần màu Blue, thành phần màu Red. Theo tài liệu [13], phép chuyển đổi từ 
không gian màu RGB sang không gian màu YCbCr như sau: 
65.481 128.553 24.996 16
37.797 74.203 112 128
112 93.786 18.214 128
Y R
Cb G
Cr B
       
       
= − − +       
       
− −       
, , , [0,1]R G B∈ 
Theo tài liệu [14], [15], phép biến đổi Gaussian theo hệ thống thị giác của con người 
như sau: 
1( , , ) [6. ( , , )* 2. ( , , )* 2. ( , , )* ]
10
= + +D D D DL x y G x y Y G x y Cb G x y Crδ δ δ δ với 
2 2
2
1( , , ) .exp( )
2.2 .
+
=D
DD
x yG x y δ δpi δ
TẠP CHÍ KHOA HỌC CÔNG NGHỆ SỐ 02/2014 
 11 
Cường độ đặc trưng 0 ( , )I x y
cho ảnh màu được tính theo phương trình: 
2
0 ( , , , ) ( ( , , , )) . ( ( , , , ))= −I D I D I DI x y Det M x y Tr M x yδ δ δ δ α δ δ 
Trong đó, ( ), ( )Det Tr• •
lần lượt là định thức và vết của ma trận, ( , , , )I DM x y δ δ là 
ma trận moment bậc hai, được định nghĩa như sau: 
2
2
2( , , , ) . ( )*
 
=  
 
x x y
I D D I
x y y
L L L
M x y G
L L L
δ δ δ δ 
Trong đó, ,I Dδ δ là các giá trị vi phân, Lα là đạo hàm theo hướng α . Các điểm đặc 
trưng của ảnh màu được rút trích theo công thức: 
0 0( , , , ) ( ', ', , )>I D I DI x y I x yδ δ δ δ , với ', '∈x y A 
0 ( , , , ) ≥I DI x y δ δ θ , với A là tập các điểm láng giềng của ( , )x y
và θ là giá trị 
ngưỡng. 
Tập các đường tròn đặc trưng 1 2{ , ,..., }nI I I IO o o o= có tâm là các điểm đặc trưng và tập 
bán kính của đường tròn đặc trưng 1 2{ , ,..., }nI I I IR r r r= . 
Các giá trị của bán kính đặc trưng được trích xuất theo phương pháp LoG (Laplace-
of-Gaussian) và có miền giá trị là [0, min( , ) 2 ]M N , với ,M N là chiều cao và chiều rộng 
của hình ảnh. 
Hình 2. Trích xu/t vùng ñ3c trưng trên 6nh theo phương pháp Harris-Laplace 
3. Xây d>ng c/u trúc d@ liu và thuBt toán truy v/n 6nh 
3.1. T-o ch ký m 
Mỗi vùng đặc trưng iI Io O∈ của hình ảnh I sẽ được tính histogram dựa trên dải màu 
chuẩn C , thực hiện phương pháp phân cụm dựa trên độ đo Euclide trong không gian màu 
RGB để phân loại các màu sắc của từng điểm ảnh trên hình ảnh. Gọi p là một điểm trên 
ảnh I và có vector giá trị màu trong không gian RGB là ( ) , , p p p pV R G B= . Gọi 
( ), , m m m mV R G B= là vector màu thuộc tập dải màu chuẩn C , sao cho: 
 min{|| ||, }
m p i iV V V V C= − ∈ . Khi đó, tại điểm p sẽ được chuẩn hóa theo vector màu mV . 
Theo thực nghiệm, bài báo sẽ sử dụng tập dải màu theo chuẩn MPEG7 để tính histogram 
cho các ảnh màu trên dữ liệu ảnh Corel. 
KHOA HỌC QUẢN LÝ 
 12 
B6ng 1. Danh m#c màu theo chuFn MPEG7 
Index Color R G B Index Color R G B 
0 Black 0 0 0 13 Plum 146 109 0 
1 Sea Green 0 182 0 14 Teal 146 182 170 
2 Light Green 0 255 170 15 Dark Red 182 0 0 
3 Olive Green 36 73 0 16 Magenta 182 73 170 
4 Aqua 36 146 170 17 Yellow Green 182 182 0 
5 Bright Green 36 255 0 18 Flouro Green 182 255 170 
6 Blue 73 36 170 19 Red 219 73 0 
7 Green 73 146 0 20 Rose 219 146 170 
8 Turquoise 73 219 170 21 Yellow 219 255 0 
9 Brown 109 36 0 22 Pink 255 36 170 
10 Blue Gray 109 109 170 23 Orange 255 146 0 
11 Lime 109 219 0 24 White 255 255 255 
12 Lavender 146 0 170 
Quá trình tạo chữ ký mờ cho mỗi hình ảnh được thực hiện như sau: 
Bước 1. Chọn tập dải màu 1 2{ , ,..., }nC c c c= theo chuẩn MPEG7 làm cơ sở cho việc 
tính histogram của hình ảnh, gọi I là ảnh màu cần tính histogram. Lượng tử hoá các màu 
chiếm ưu thế của ảnh I sẽ được tập màu 1 2{ , ,..., }
I
I I I
I nC c c c= , vector histogram của ảnh I sẽ 
là 1 2{ , ,..., }
I
I I I
I nH h h h= . 
Bước 2. Thực hiện việc chuẩn hoá histogram của ảnh I
trên dải màu C sẽ được 
vector histogram chuẩn hoá 1 2{ , ,..., }nH h h h= , với mỗi giá trị [0,1]ih ∈ được chuẩn hoá: 
I I
ji j jh h h= ∑ nếu i Ic C C∈ ∩ , ngược lại 0ih = . 
Bước 3. Mỗi màu Ijc sẽ được mô tả thành một chữ ký mờ có chiều dài m
là 
1 2 ,...,
j j j
m
f f f . Do đó, chữ ký mờ của ảnh I là: 1 1 1 2 2 21 2 1 2 1 2,..., ,..., ... ,...,n n nm m mf f f f f f f f f , trong 
đó: 
100
0 100
i i
j
i
i
ih i h
mf
ii h
m

=  × × 
= 
 ≠  × × 

Đặt 1 2 ...
j j j j
m
F f f f= , chữ ký mờ của ảnh I sẽ là: 1 2 ... nFuzzySig F F F= 
3.2. ð ño tương t/ FHD 
Mỗi chữ ký mờ 1 2... nIFuzzySig F F F=
của hình ảnh I sẽ được chuyển thành vector 
1 2( , ,..., )I nV v v v= , trong đó 
1
( ) mi ii k
k
v weight F w
=
= = ∑ , với 1 2 ...
i i i i
m
F f f f= , và: 
TẠP CHÍ KHOA HỌC CÔNG NGHỆ SỐ 02/2014 
 13 
0 0
100 0
i
k
i
k i i
k k
f
w kf f
m
=

= 
+ × ≠
Gọi J là hình ảnh cần tính độ tương tự so với ảnh I , do đó cần tính khoảng cách 
mờ Hamming giữa hai vector 1 2( , ,..., )I I II nV v v v= và 1 2( , ,..., )J J JJ nV v v v= . 
Khoảng cách mờ FHD là tập mờ lực lượng của tập mờ ( , )I JD V Vα , nghĩa là: 
( ( , ))
0
( , ) ( ( , )) ( ( ))
I J
n
I J I J Card D V V
i
FHD V V Card D V V i i
α
α α µ
=
= = ∑
Trong đó, ( ( , )) ( ) ( ) (1 ( 1)) min{ ( ),(1 ( 1)}
I J
Card D V V i i i i i
α
µ µ µ µ µ= ∧ − + = − + , ( )iµ
là giá trị 
lớn nhất thứ i của hàm thuộc iµ ứng với tập mờ 
1
( , ) nI J i
i
D V V iα µ
=
= ∑ và 
(0) 1, ( 1) 0nµ µ= + = . Khi đó, mức độ khác nhau của IV và IV trên k thành phần sẽ là: 
( , ) ( ( , ))( , ) ( )
I J I J
FHD V V Card D V Vk k
α α
µ α µ= , với {0,1,..., }, | ( ( , )) |k n n Support D x yα∈ = . 
3.3. T-o cây FS-Tree 
Nhằm giảm không gian và tăng tốc độ truy vấn, bài báo tiến hành xây dựng cây chữ 
ký FS-Tree lưu trữ các chữ ký mờ của hình ảnh. Mỗi một nút trong cây FS-Tree sẽ lưu trữ 
tập các phần tử { , }FuzzySig next〈 〉 , với FuzzySig là chữ ký mờ và next là con trỏ tham 
chiếu đến nút con. Các nút lá sẽ lưu trữ các phần tử { , }FuzzySig Oid〈 〉 , với FuzzySig
là 
chữ ký mờ của mỗi hình ảnh và Oid là định danh của hình ảnh tương ứng. Quá trình tạo 
cây FS-Tree được thực hiện dựa trên thao tác chèn và tách nút trong cây [5, 8]. Thuật toán 
tạo cây chữ ký FS-Tree lưu trữ chữ ký mờ được thực hiện như sau: 
Input: tập các chữ ký FS = { | i = 1,,n} 
Output: cây chữ ký FS-Tree 
Algorithm1. Gen-FSTree(S, Root) 
Begin 
Bước 1. v = Root; 
 If FS = ∅ then STOP; 
 Else Chọn ∈ S và S = S \ ; 
 Qua bước 2; 
Bước 2. If v là nút lá then 
 begin 
 v = v ⊕ ; 
 UnionSignature(v); 
 If v.count > M then SplitNode(v); 
 Quay lại bước 1; 
 end 
 Else 
 begin 
 FHD(SIG0→FuzzySig, Fuzzysig) 
 = min{FDH(SIGi→FuzzySig,FuzzySig)| SIGi ∈ v}; 
 v = SIG0→next; 
 Quay lại bước 2; 
 end 
End. 
KHOA HỌC QUẢN LÝ 
 14 
Thuật toán Algorithm1 sẽ lần lượt đưa các chữ ký FuzzySig từ tập chữ ký FS vào 
trong cây FS-Tree. Với mỗi chữ ký FuzzySig sẽ được chèn vào nút lá phù hợp, nếu nút lá 
đầy thì quá trình tách nút sẽ được thực hiện và cây FS-Tree sẽ tăng trưởng chiều cao theo 
hướng gốc của cây. Tại mỗi nút trong của cây FS-Tree, sẽ ưu tiên đi theo hướng có độ 
tương tự FHD nhiều hơn, quá trình này sẽ được duyệt cho đến khi tìm ra được nút lá phù 
hợp. 
Ứng với mỗi chữ ký cần chèn sẽ duyệt qua đường đi có chiều cao log 1
m
h n=  −  , 
với m là số chữ ký tối thiểu của một nút trong cây S-Tree. Gọi k là chiều dài của mỗi chữ 
ký, mỗi một nút trong của cây sẽ có tối đa là M chữ ký, vì vậy quá trình duyệt cây để tìm 
ra nút lá phù hợp sẽ có chi phí tối đa là log 1
m
k M n× ×  −  . Tuy nhiên, khi tìm ra nút là 
phù hợp nhưng đã bị đầy, cần phải thực hiện quá trình tách nút, việc tách nút dựa trên cơ 
sở phép toán seedα − , seedβ − được thực hiện như sau: 
Input: Nút v 
Output: Cây FS-Tree sau khi thực hiện phép tách nút 
Algorithm2. SplitNode(v) 
Begin 
Tạo nút vα và vβ lần lượt chứa chữ ký seedα − và seedβ − 
v = v \ { seedα − , seedβ − } 
For (SIGi ∈ v) 
If (FHD(SIGi→FuzzySig, seedα − )< FHD(SIGi→Fuzzysig, seedβ − ))then 
 vα = vα ⊕ SIGi; 
Else vβ = vβ ⊕ SIGi; 
sα = iSIG
α∨ , với iSIG v
α
α∈ ; sβ = iSIG
β∨ , với iSIG v
β
β∈ ; 
If ( parentv != null) then parent parentv v sα= ⊕ ; parent parentv v sβ= ⊕ ; 
If ( .parentv count > M ) then SplitNode( parentv ); 
If ( parentv = null) then Root = { sα , sβ }; 
End. 
Procedure UnionSignature( v ) 
Begin 
s = iSIG∨ , với iSIG v∈ ; 
If( parentv != null) then 
begin 
v
SIG = { iSIG | iSIG next→ = v , }i parentSIG v∈ ; parentv → ( )vSIG FuzzySig→ = s ; 
 UnionSignature( parentv ); 
end 
End. 
3.4. Thu2t toán truy v$n ,nh trên cây FS-Tree 
 Sau khi lưu trữ chữ ký và định danh của hình ảnh trên cây chữ ký FS-Tree, quá 
trình truy vấn sẽ đưa ra các chữ ký của hình ảnh dựa trên việc duyệt cây FS-Tree với độ đo 
tương tự FHD. Sau khi tìm ra các chữ ký hình ảnh tương tự, dựa vào định danh của các 
TẠP CHÍ KHOA HỌC CÔNG NGHỆ SỐ 02/2014 
 15 
hình ảnh sẽ tìm ra cụ thể các hình ảnh tương tự với hình ảnh truy vấn. Do đó, bài toán cần 
thực hiện là tìm ra chữ ký của hình ảnh và định danh của hình ảnh tương ứng, quá trình 
truy vấn này được thực hiện như sau: 
Input: chữ ký truy vấn FuzzySig và FS-Tree 
Output: Tập chữ ký mờ và tập Oid tham chiếu ñến hình ảnh tương ứng 
Algorithm3. Search-Image-Sig(FuzzySig, FS-Tree) 
Begin 
v = root; SIGOUT = ∅; Stack = ∅; Push(Stack, v); 
while(not Empty(Stack)) do 
begin 
 v = Pop(Stack); 
 If(v is not Leaf) then 
 begin 
 For(SIGi ∈ v and SIGi→FuzzySig ∧ FuzzySig = FuzzySig) do 
 FHD(SIG0→Fuzzysig, FuzzySig) 
 = min{FHD(SIGi→FuzzySig, FuzzySig)| SIGi ∈ v}; 
 Push(Stack, SIG0 → next); 
 end 
 Else 
 SIGOUT = SIGOUT ∪ { | SIGi ∈ v}; 
end 
return SIGOUT; 
End. 
Vì FS-Tree là cây nhiều nhánh cân bằng, hơn nữa tại mỗi nút của cây sẽ được duyệt 
theo hướng tiếp theo có độ tương tự tốt nhất, do đó sẽ tốn chi phí tối đa duyệt cây là 
log 1
m
h n=  −  . Quá trình tìm kiếm trên cây được thực hiện tương tự quá trình duyệt cây, 
do đó chi phí của quá trình truy vấn trên cây FS-Tree cũng sẽ là log 1
m
k M n× ×  −  , với k 
là chiều dài của mỗi chữ ký, m là số chữ ký tối thiểu, M là số chữ ký tối đa của một nút 
trong cây FS-Tree. 
4. Kng d#ng th>c nghim 
4.1. Mô hình th/c nghi7m 
Quá trình xây dựng ứng dụng thực nghiệm gồm hai pha, pha thứ nhất sẽ thực hiện 
quá trình tiền xử lý nhằm chuyển đổi dữ liệu hình ảnh trở thành dạng chữ ký mờ và đưa 
vào cây chữ ký FS-Tree dựa trên độ đo tương tự FHD. Pha thứ hai sẽ thực hiện quá trình 
truy vấn, ứng với một hình ảnh cần truy vấn sẽ được chuyển đổi thành chữ ký mờ và sẽ 
được thực hiện truy vấn trên cây chữ ký FS-Tree dựa trên độ đo tương tự FHD. Sau khi tìm 
ra các chữ ký của hình ảnh tương tự, sẽ truy xuất hình ảnh cụ thể và sắp xếp theo thứ tự ưu 
tiên của độ đo tương tự FHD. 
KHOA HỌC QUẢN LÝ 
 16 
Hình 3. Mô hình h truy v/n 6nh d>a trên ñ ño FHD và cây FS-Tree 
Pha 1: Thực hiện tiền xử lý 
Bước 1. Lượng tử hoá hình ảnh trong dữ liệu ảnh và chuyển thành histogram. 
Bước 2. Chuyển đổi các histogram của hình ảnh thành chữ ký mờ. 
Bước 3. Lần lượt tính khoảng cách FHD của các chữ ký mờ và chèn các chữ ký mờ 
vào cây FS-Tree. 
Pha 2: Thực hiện truy vấn 
Bước 1. Với mỗi hình ảnh truy vấn, sẽ được tính histogram và chuyển thành chữ ký 
mờ. 
Bước 2. Thực hiện truy vấn chữ ký nhị phân trên cây FS-Tree gồm các chữ ký hình 
ảnh tương tự tại nút lá của cây qua độ đo FHD. 
Bước 3. Sau khi có các hình ảnh tương tự, tiến hành sắp xếp theo độ tương tự từ cao 
đến thấp và đưa ra danh sánh các hình ảnh trên cơ sở độ tương tự FHD. 
4.2. K9t qu, th/c nghi7m 
Quá trình thực nghiệm sẽ truy vấn trên dữ liệu mẫu Corel [16] gồm có 10,800 hình 
ảnh chia thành 80 chủ đề khác nhau. Với mỗi hình ảnh truy vấn sẽ được trích lọc trên dữ 
liệu ảnh Corel và tìm ra các hình ảnh có độ tương tự nhiều nhất với hình ảnh truy vấn, từ 
đó đối sánh với danh mục chủ đề hình ảnh nhằm đánh giá độ chính xác của phương pháp. 
TẠP CHÍ KHOA HỌC CÔNG NGHỆ SỐ 02/2014 
 17 
B6ng 2. Mt sN kt qu6 ñánh giá mPu v$ quá trình truy v/n 6nh trên d@ liu Corel 
có 10,800 6nh 
ID ID Image Recall Precision ID ID Image Recall Precision ID ID Image Recall Precision 
1 644000.jpg 0.990 0.990 18 303024.jpg 0.402 0.390 35 275007.jpg 0.420 0.420 
2 569062.jpg 0.440 0.440 19 312001.jpg 0.430 0.430 36 275002.jpg 0.850 0.850 
3 135032.jpg 0.580 0.580 20 318003.jpg 0.380 0.380 37 280014.jpg 0.920 0.920 
4 113014.jpg 0.340 0.340 21 345002.jpg 0.833 0.500 38 387015.jpg 0.303 0.300 
5 212001.jpg 0.365 0.840 22 377003.jpg 0.357 0.350 39 470083.jpg 0.383 0.310 
6 280000.jpg 0.355 0.710 23 283000.jpg 0.850 0.850 40 487005.jpg 0.917 0.770 
7 476034.jpg 0.330 0.330 24 435000.jpg 0.810 0.810 41 569015.jpg 0.520 0.520 
8 40000.jpg 0.740 0.740 25 569012.jpg 0.800 0.640 42 569095.jpg 0.650 0.650 
9 84000.jpg 0.350 0.350 26 435011.jpg 0.660 0.660 43 856089.jpg 0.233 0.700 
10 114000.jpg 0.876 0.780 27 644099.jpg 0.990 0.990 44 409061.jpg 0.350 0.350 
11 124000.jpg 0.370 0.370 28 225000.jpg 0.350 0.350 45 135072.jpg 0.680 0.680 
12 131000.jpg 0.400 0.400 29 186000.jpg 0.410 0.410 46 136045.jpg 0.778 0.280 
13 150000.jpg 0.350 0.350 30 343000.jpg 0.420 0.420 47 75050.jpg 0.760 0.760 
14 167001.jpg 0.338 0.760 31 350000.jpg 0.600 0.600 48 113026.jpg 0.520 0.520 
15 208000.jpg 0.400 0.400 32 473000.jpg 0.350 0.350 49 84049.jpg 0.420 0.420 
16 221001.jpg 0.350 0.350 33 546000.jpg 0.650 0.650 50 221009.jpg 0.660 0.660 
17 247000.jpg 0.380 0.380 34 817000.jpg 0.300 0.300 51 113090.jpg 0.720 0.720 
0
0.2
0.4
0.6
0.8
1
1.2
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51
Recall Average Recall
Hình 4. ð chính xác truy v/n hình 6nh theo th>c nghim 
0
0.2
0.4
0.6
0.8
1
1.2
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51
Precision Average Precision
Hình 5. Kh6 năng truy v/n thành công hình 6nh theo th>c nghim 
KHOA HỌC QUẢN LÝ 
 18 
0
20000000
40000000
60000000
80000000
100000000
120000000
140000000
160000000
180000000
200000000
22 25 30 45 47 48 48 48 48 49 83 11
5
25
5
26
6
10
00
10
80
0
Số lượng hình ảnh
Số
ph
ép
to
án
so
sá
n
h
Hình 6. SN phép toán so sánh khi tZo cây FS-Tree 
0
2000000
4000000
6000000
8000000
10000000
12000000
22 25 30 45 47 48 48 48 48 49 83 11
5
25
5
26
6
10
00
10
80
0
Số lượng hình ảnh
Th
ờ
i g
ia
n
(m
ill
i-s
ec
o
n
ds
)
Hình 7. Th[i gian tZo cây FS-Tree (tính theo milli gi/y) 
Các chữ ký nhị phân được đưa vào hai dạng cấu trúc truy vấn gồm cấu trúc tập tin 
chữ ký SSF (sequential signature file) và cây FS-Tree. Hình 8 và Hình 9 mô tả số liệu thực 
nghiệm về quá trình truy vấn hình ảnh tương tương trên dữ liệu ảnh Corel. 
0
200000
400000
600000
800000
1000000
1200000
1400000
1600000
1800000
2000000
10
00
10
00
10
00
10
00
10
00
10
00
10
00
10
00
10
80
0
10
80
0
10
80
0
10
80
0
10
80
0
Số lượng hình ảnh
Th
ờ
i g
ia
n
tr
u
y 
v
ấn
(m
ill
i-s
ec
o
n
ds
)
Truy vấn tuyến tính Truy vấn trên FS-tree
Hình 8. Th[i gian (tính theo mili giây) truy v/n 6nh trên cây FS-Tree 
TẠP CHÍ KHOA HỌC CÔNG NGHỆ SỐ 02/2014 
 19 
0
100000
200000
300000
400000
500000
600000
700000
800000
900000
10
00
10
00
10
00
10
00
10
00
10
00
10
00
10
00
10
00
10
00
10
00
10
00
10
00
10
00
10
00
10
80
0
10
80
0
10
80
0
10
80
0
10
80
0
10
80
0
10
80
0
10
80
0
10
80
0
10
80
0
Số lượng hình ảnh
Số
ph
ép
to
án
so
sá
n
h SSF FS-tree
Hình 9. SN phép toán so sánh khi th>c hin truy v/n 6nh 
Hình 10. Mt sN kt qu6 truy v/n 6nh trên d@ liu 6nh Corel 
5. Kt luBn 
Trong bài báo đã đưa ra phương pháp đánh giá độ tương tự giữa hai hình ảnh dựa 
trên chữ ký nhị phân, đồng thời mô phỏng ứng dụng thực nghiệm trên dữ liệu ảnh phân 
loại của Corel. Theo thực nghiệm cho thấy sự hiệu quả của phương pháp đã đưa ra và hệ 
thống này thực thi tốt trên các hệ thống Online và Offline, đồng thời đã cải thiện đáng kể 
về tốc độ truy vấn hình ảnh rất nhiều lần so với phương pháp đối sánh trực tiếp cũng như 
phương pháp SSF (signature sequence file). Tuy nhiên, việc sử dụng các đặc trưng về màu 
sắc sẽ cho kết quả chưa chính xác theo ý nghĩa về nội dung hình ảnh. Do đó, hướng phát 
triển tiếp theo của bài báo sẽ thực hiện trích xuất đối tượng trên các hình ảnh, từ đó sẽ tiến 
hành xây dựng chữ ký nhị phân để mô tả các đối tượng cũng như mô tả nội dung cho hình 
ảnh, đồng thời tạo ra một cấu trúc dữ liệu mô tả mối quan hệ dựa trên độ tương tự về nội 
dung của các chữ ký với mỗi hình ảnh. 
Li cám ơn 
Chúng tôi xin cám ơn Trung tâm Công nghệ Thông tin, trường Đại học Công nghiệp 
Thực phẩm Tp.HCM là nơi bảo trợ cho chúng tôi thực hiện nghiên cứu này. 
KHOA HỌC QUẢN LÝ 
 20 
TÀI LIU THAM KHO 
1. Heba Aboulmagd, Neamat EI-Gayar, Hoda Onsi (2008), “A new approach in 
content-based image retrieval using fuzzy”, Springer Science, Telecommun Syst, 40, 55-66 
2. Vaclav Snasel, Zdenek Horak, Milos Kudelka, Ajith Abraham (2011), “Fuzzy 
Signatures Organized Using S-Tree”, Proceedings of the IEEE International Conference 
on Digital Object Identifier, 633-637 
3. K. Konstantinidis, A. Gasteratos, I. Andreadis (2005), “Image retrieval based on 
fuzzy color histogram processing”, Optics Communications, 248(4-6), 375-386 
4. Mircea M. Ionescu, Anca L. Ralescu (2005), “Image Clustering for a Fuzzy 
Hamming Distance Based CBIR System”, Proceedings of the Sixteen Midwest Artificial 
Intelligence and Cognitive Science Conference, 102-108 
5. Yangjun Chen and Yibin Chen (2006), “On the Signature Tree Construction and 
Analysis”, IEEE Trans. Knowl. Data Eng., 18(9), 1207-1224 
6. Neetu Sharma. S, Paresh Rawat. S, Jaikaran Singh. S., (2011) “Efficient CBIR Using 
Color Histogram Processing”, Signal & Image Processing: An Inter. Jour., 2(1), 94-112 
7. Fazal Malik, Baharum Bin Baharudin (2012), “Feature Analysis of Quantized 
Histogram Color Features for Content-Based Image Retrieval Based on Laplacian Filter”, 
International Conference on System Engineering and Modeling, 34, 44-49 
8. M. A. Nascimento, E. Tousidou, V. Chitkara, Y. Manolopoulos (2002), “Image 
indexing and retrieval using signature trees”, Data & Knowledge Eng., 43(1), 57-77 
9. Rahul Mehta, Nishchol Mishra, Sanjeev Sharma (2011), “Color - Texture based 
Image Retrieval System”, International Journal of Computer Applications, 24(5), 24-29 
10 Gunja Varshney, Uma Soni (2011), “Color-Based Image Retrieval in Image 
Database System”, International Journal of Soft Computing and Engineering, 1(5), 31-35 
11. Ch. Kavitha, M. Babu Rao, B.Prabhakara Rao, A.Govardhan (2011), “Image 
Retrieval based on Local Histogram and Texture Features”, International Journal of 
Computer Science and Information Technology, 2(2), 741-746 
12. S-C Ch, C-K Y (2001), “A fast and novel technique for color quantization using 
reduction of color space dimensionality”, Pattern Recognizer Letter, 22(8), 845-956 
13. G. H. Liu, J. Y. Yang (2013), “Content-based Image Retrieval Using Color 
Difference Histogram”, Pattern Recognition, 46, 188-198 
14. X. Y. Wang, J. F. Wu, H. Y. Yang (2010), “Robust Image Retrieval Based on Color 
Histogram of Local Feature Regions”, Springer Science, Multi. Tools Appl, 49, 323-345 
15. X.-Y. Wang et al., (2013), “Robust Color Image Retrieval Using Visual Interest 
Point Feature of Significant Bit-Planes”, Digital Signal Processing, 23(4), 1136-1153 
16. Corel Corp,