BỘ GIÁO DỤC VÀ ĐÀO TẠO TẬP ĐOÀN BƯU CHÍNH VIỄN THÔNG VIỆT NAM
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
NGUYỄN QUỲNH ANH

PHƯƠNG PHÁP TRA CỨU ẢNH DỰA VÀO PHÂN CỤM ẢNH
VÀ ỨNG DỤNG VÀO BÀI TOÁN TRA CỨU
ẢNH PHONG CẢNH

CHUYÊN NGÀNH : KHOA HỌC MÁY TÍNH
MÃ SỐ: 60.48.01

TÓM TẮT LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH

HÀ NỘI – 2011


……………………………………………………

Phản biện 2: ……………………………………………………
……………………………………………………

Luận văn sẽ được bảo vệ trước hội đồng chấm luận văn tại
Học viện Công nghệ Bưu chính Viễn thông
Vào lúc: giờ ngày tháng năm

MỞ ĐẦU
Tra cứu ảnh dựa theo nội dung là kỹ thuật cho phép trích chọn các đặc điểm dựa vào
nội dung trực quan của ảnh như màu sắc, kết cấu, hình dạng và bố cục không gian của
ảnh để làm cơ sở cho việc tra cứu, sắp xếp, tổ chức CSDL ảnh. Tuy nhiên, khi CSDL ảnh
lớn thì phương pháp tìm kiếm ảnh tuần tự sẽ tốn rất nhiều thời gian. Để tăng tốc hệ thống
tra cứu ảnh dựa vào nội dung, cần có một số kỹ thuật tra cứu ảnh nhanh. Đề tài "Phương
pháp tra cứu ảnh dựa vào phân cụm ảnh và ứng dụng vào bài toán tra cứu ảnh phong
cảnh " trình bày ứng dụng thuật toán phân cụm có thứ bậc (Agglomerative Hierarchical
Clustering) vào bài toán tra cứu ảnh dựa vào nội dung sử dụng đặc trưng màu với mục
đích phân tập ảnh trong CSDL thành các cụm ảnh có màu sắc tương tự nhau, khi tiến
hành tra cứu hệ thống chỉ phải so sánh ảnh truy vấn với cụm ảnh tương tự nhất mà không
phải so sánh trên toàn bộ ảnh trong CSDL.
Luận văn được bố cục thành 3 chương:
Chương 1: Giới thiệu tổng quan về tra cứu ảnh dựa vào nội dung, kỹ thuật đánh chỉ số
ảnh, một số hạn chế của các phương pháp tra cứu ảnh và nội dung nghiên cứu của đề tài.
Chương 2: Trình bày kỹ thuật phân cụm có thứ bậc (Agglomerative Hierarchical
Clustering -AHC) áp dụng cho bài toán tra cứu ảnh dựa vào nội dung sử dụng đặc trưng
màu sắc.
Chương 3: Trình bày thiết kế và xây dựng hệ thống thực nghiệm tra cứu ảnh ứng dụng
kỹ thuật phân cụm có thứ bậc (AHC) vào bài toán tra cứu ảnh phong cảnh.
Cuối cùng chúng tôi đưa ra một số kết luận và đề xuất các hướng nghiên cứu.

Đặc trưng hình dạng: Các đặc trưng hình dạng có quan hệ chặt chẽ với mô tả vùng
hoặc các đối tượng được phân đoạn. Đặc trưng hình dạng được trích rút từ các đường bao
đối tượng hoặc vùng chứa đối tượng.
1.1.3 Kiến trúc của hệ thống tra cứu ảnh dựa vào nội dung.
Kiến trúc chung của hệ thống tra cứu ảnh gồm 2 phần:
Phần 1 : Tạo lập CSDL ảnh cùng với thông tin đặc trưng
Phần 2 : Tra cứu ảnh
Hình 1.2: Kiến trúc hệ thống tra cứu ảnh dựa vào nội dung
1.1.4 Giới thiệu một số hệ thống tra cứu ảnh
Dựa trên các nghiên cứu về tra cứu ảnh dựa vào nội dung ảnh, một số hệ thống tra cứu
ảnh đã được đưa vào sử dụng thương mại như: QBIC, RetrievalWare, VisualSEEk và
WebSeek, Google Image Swirl, Tiltomo, Byo Image Search…vv
1.2 KỸ THUẬT ĐÁNH CHỈ SỐ ẢNH
Mô hình được hoạt động như sau (xem hình 1.6):
Bước 1: Chuyển đổi các đối tượng trong tập ảnh thành các vector đặc trưng.
Bước 2: Đo khoảng cách hoặc đo độ tương tự giữa hai vector đặc trưng của hai ảnh bất
kỳ.
Bước 3: Đánh chỉ số cho các vector đặc trưng tạo thành lược đồ
Bước 4: Thực hiện truy vấn ảnh dựa trên lược đồ đánh chỉ số.
- Các cấu trúc đánh chỉ số dựa trên phân chia dữ liệu bao gồm các vùng bao được hình
thành dựa trên các cụm dữ liệu gồm các cấu trúc sau: R-tree,R
*
-tree, X-tree, SS-tree, SR-
tree
1.3 MỘT SỐ HẠN CHẾ CỦA CÁC PHƯƠNG PHÁP TRA CỨU ẢNH
Các hệ thống tra cứu ảnh hiện nay thường trích chọn các đặc trưng của ảnh truy vấn và
so sánh với các đặc trưng tương ứng của tất cả các ảnh được lưu trữ trong CSDL. Vì vậy
thời gian tìm kiếm tăng tuyến tính với kích thước của cơ sở dữ liệu.
Các kỹ thuật tìm kiếm nhanh khác cũng đã được nhiều nhà nghiên cứu đề xuất như: kỹ
thuật tìm kiếm nhanh được Barros và các đồng nghiệp sử dụng bất đẳng thức tam giác để
giảm thời gian tìm kiếm. Chen và các đồng nghiệp đề xuất kỹ thuật lượng hóa vector và
sử dụng bất đẳng thức tam giác.Cả hai kỹ thuật này đều yêu cầu độ đo tương tự được sử
dụng để so sánh hai ảnh phải thỏa mãn bất đẳng thức tam giác. Tuy nhiên hạn chế là
không phải tất cả độ đo tương tự đều thỏa mãn được bất đẳng thức tam giác. Các kỹ thuật
đánh chỉ số sử dụng cấu trúc cây R-Tree, R*- Tree, SR-Tree, SS-Tree, Kdb-Tree được
trình bày ở trên tuy nhiên nhược điểm của các phương pháp này là không thực hiện tốt
khi số chiều của các vector đặc trưng lớn.
Để khắc phục nhược điểm trên chúng tôi trình bày phương pháp tạo ra một lược đồ
được đánh chỉ số bằng cách nhóm các ảnh tương tự nhau theo nội dung của ảnh.
1.4 NỘI DUNG NGHIÊN CỨU CỦA ĐỀ TÀI
Nội dung nghiên cứu của đề tài là áp dụng phương pháp phân cụm có thứ bậc
Agglomerative Hierarchical clustering (AHC) cho bài toán tra cứu ảnh theo nội dung sử
dụng đặc trưng màu. Mục đích của phương pháp là nhóm các ảnh có nội dung về màu sắc
tương tự nhau thành các cụm và thực hiện tính các tâm cụm. Khi tra cứu ảnh thì chỉ cần
tìm kiếm ảnh tương tự trong một cụm ảnh và không phải tìm kiếm trong toàn bộ CSDL.
1.5 KẾT LUẬN CHƯƠNG 1
Trong chương này, chúng tôi đã trình bày tổng quan về tra cứu ảnh dựa vào nội dung,
trình bày các kỹ thuật đánh chỉ số ảnh. Nghiên cứu, tìm hiểu đưa ra một số hạn chế trong
các phương pháp, các công trình liên quan tới tra cứu ảnh nhanh qua đó trình bày nội

2.1.6 Độ đo tương tự giữa các lược đồ màu: Tra cứu ảnh theo nội dung tính toán độ
tương tự thị giác giữa ảnh truy vấn và các ảnh trong CSDL. Kết quả tìm kiếm không phải
là một ảnh đơn mà là một danh sách các ảnh được sắp xếp theo độ tương tự. Một số độ đo
tương tự được sử dụng phổ biến.
Khoảng cách Minkowski: Độ đo này chỉ so sánh các bin giống nhau giữa các lược đồ
màu và được xác định:
1/r
)
r
N
1i
|[i]
I
H[i]
Q
H|(I)d(Q,



(2.7)
Trong đó Q và I là hai ảnh. N là số các bin trong lược đồ màu,
][iH
Q
là giá trị của bin
i trong lược đồ màu
Q
H
, và ][iH
I
là gía trị của bin i trong lược đồ màu

biểu thị sự tương tự giữa màu i và màu j. a
ij
=1-d
ij
/ d
max
và d
ij
= | H
Q
[i] -
H
T
[j] |
Lược đồ giao (Histogram Intersection): Lược đồ giao được xác định dựa trên tổng số các
điểm ảnh phổ biến có trong cả 2 lược đồ màu:



N
1i
[i])
I
H[i],
Q
min(HI)I(Q,
(2.12)
2.2 GIỚI THIỆU MỘT SỐ KỸ THUẬT PHÂN CỤM
Kỹ thuật phân cụm được chia thành hai nhóm chính:
- Phân cụm bằng cách phân hoạch (Partitional clustering).

lại cho đến khi tất cả các đối tượng được nhóm vào 1 cụm hoặc là cho đến khi số lượng
cụm còn lại đạt đến một ngưỡng cho phép.
Các bước của thuật toán Agglomerative Approach như sau:
Cho một tập gồm N đối tượng và N*N là ma trận khoảng cách
Bước 1: Xác định các đặc trưng của đối tượng và tính ma trận khoảng cách (độ tương tự)
giữa các đối tượng.
Bước 2: Xem mỗi đối tượng là một cụm
Bước 3: Lặp lại 2 bước sau cho đến khi số cụm bằng 1 hoặc số cụm bằng một ngưỡng
cho phép R nào đó.
- Gộp 2 cụm gần nhất.
- Cập nhật ma trận khoảng cách (độ tương tự).

Hình 2.14: Sơ đồ Agglomerative Hierarchical Clustering
Trong bước 3 cần phải định nghĩa rõ việc tính khoảng cách giữa 2 cụm. Có 4 phương
thức hay được dùng để tính toán khoảng cách được liệt kê dưới đây:
- Kết nối đơn (Single Linkage)
- Kết nối toàn bộ (Complete Linkage)
- Kết nối trung bình (Average Linkage):
- Khoảng cách tâm (Centroid distance)
2.3 ÁP DỤNG THUẬT TOÁN PHÂN CỤM CÓ THỨ BẬC (AHC) VÀO HỆ
THỐNG TRA CỨU ẢNH THEO ĐẶC TRƯNG MÀU

giữa hai lược đồ được tính như sau:



m
1
i
)
i
q,
i
min(p
qp,
S
(2.14)
Độ tương tự giữa hai cụm ảnh: Độ đo tương tự S
k,l
giữa hai cụm ảnh C
k
và C
l
được định
nghĩa bằng trung bình độ tương tự giữa các cặp ảnh được biểu diễn trong các cụm này:
)(
,,
,
,
l
N
k

Áp dụng thuật toán phân cụm có thứ bậc được thực hiện qua các bước chính sau:
- Bước 1: Thực hiện phân cụm ảnh
- Bước 2: Tính tâm cụm
- Bước 3: Tối ưu tâm cụm
- Bước 4: Tra cứu ảnh
Ví dụ:

Hình 2.22: Biểu diễn một ví dụ phân cụm có thứ bậc với 8 ảnh

Thực hiện phân cụm ảnh:
Đặt n là số lượng ảnh trong CSDL. Độ tương tự giữa các cặp ảnh được tính toán trước.
Thuật toán phân cụm được thực hiện như sau:
Bước 1: Khởi tạo trong CSDL n ảnh được đặt vào n cụm phân biệt. Các cụm này được
đánh chỉ số { C
1
,C
2
, C
n
}. Với mỗi cụm thứ k tập E
k
biểu thị tập ảnh chứa trong cụm đó
và N
k
là số lượng ảnh. E
k
={ k } và N
k
= 1 với k=1,2, ,n.
Bước 2: Trong các cụm {C

l
. Cụm C
n+1
có cây con trái
RC
n+1 =
k và cây con phải LC
n+1
=l
.
Với mỗi cụm mới C
n+1
tính độ tương tự giữa cụm
C
n+1
với tất cả các cụm khác chưa được gom cụm.
Bước 3: Lặp lại quá trình trên cho đến khi đạt đến số các cụm cho trước hoặc độ tương tự
lớn nhất thấp hơn một ngưỡng cho trước.


{c
i
}; E
i


G
i
; N
i


1;
2. Repeat
2.1 Tính độ tương tự giữa các cụm Ck và Cl
For k=1 to count -1
For l=k+1 to count
)1(
2
)(
)(



 lk
lk
NN
NN
NN


2.2 Cập nhật các tham số
m←m+1; C
m
←m;
count ← count -1;

lkm
EEE 
1
;

lkm
NNN 
1
;

kRC
m

1
; lLC
m

1
;
C←C/ck; C←C/cl;
Until (count = “ số cụm yêu cầu”) or (max
kl
<T)

của cụm C
k
vào tập R
n+1
.
Bước 4: Lặp lại bước 2 và bước 3 cho đến khi số phần tử chứa trong R
n
= r.
Bước 5: Sau bước 4 tập Rn chứa r phần tử. Mỗi ảnh đại diện sẽ được chọn ra từ r phần tử
này. Nếu phần tử k

Rn và Nk =1 thì k được chọn luôn. Nếu Nk >1 thì chọn ra 1 ảnh
đơn từ tập Ek bằng cách chọn ảnh có độ tương tự trung bình lớn nhất so với Nk-1 ảnh
còn lại của tập Ek.
Bước 6: Sau khi chọn ra được r ảnh đại diện, tâm cụm được tính là trung bình của P lược
đồ tương đương của r ảnh. THUẬT TOÁN TÍNH TÂM CỤM
Input: C
m
– cụm ảnh thứ m,
r – số các ảnh đại diện
Output: O – tâm cụm ảnh
1. Khởi tạo
n ←0; R
n


{ C


R
n
\Cmax;
R
n


R
n


RCmax

LCmax

;
Until ( Rn = =r)
3. Chọn r ảnh đại diện tự r cụm
r

Rn ;
for k=1 to r
if (N
k
==1) E


E


sim
;
if (maxavesim< avesim
i
)
maxavesim

avesim
i
;
b1

i;
}
E


E

{b1} ;
}
4. Tính tâm của cụm
For i=1 to r O

O + Pi; O


r
O
;

Clustering- AHC) để phân tập ảnh trong cơ sở dữ liệu ảnh thành các cụm có độ tương tự
nhau nhằm mục đích hạn chế việc phải tìm kiếm ảnh trong toàn bộ cơ sở dữ liệu và tăng
tốc độ tra cứu.
3.2 THIẾT KẾ HỆ THỐNG TỔNG QUÁT
Kiến trúc này gồm hai module chính: module tiền xử lý được thực hiện ngoại tuyến
và module tra cứu được thực hiện trực tuyến.

Hình 3.1: Kiến trúc của hệ thống tra cứu ảnh

Hình 3.2: Mô hình chi tiết của hệ thống tra cứu ảnh
3.3 BIỂU ĐỒ USE CASE CỦA HỆ THỐNG
( Xem tài liệu chi tiết)
3.4 BIỂU ĐỒ TRÌNH TỰ VÀ SƠ ĐỒ HÀNH ĐỘNG CỦA HỆ THỐNG ( Xem tài
liệu chi tiết)
3.5 MỘT SỐ GIAO DIỆN CHÍNH CỦA CHƯƠNG TRÌNH
3.5.1 . Giao diện chính của chương trình

Hình 3.8: Giao diện chính của chương trình.
3.5.2 Biểu diễn lược đồ màu trong không gian màu RGB

Hình 3.10: Giao diện lược đồ màu cục bộ của ảnh.
3.5.3 . Tính độ tương tự giữa hai ảnh

Hình 3.11: Giao diện tính độ tương tự giữa hai ảnh. 3.5.4 Giao diện phân cụm ảnh

Hình 3.12: Giao diện phân cụm ảnh.


nhằm tăng tốc độ tìm kiếm của hệ thống là một chủ đề đang được rất nhiều quan tâm của
các nhà nghiên cứu trong lĩnh vực tra cứu ảnh.
Sau đây là các kết quả đã được trong luận văn:
 Nghiên cứu lý thuyết tổng quan về tra cứu ảnh theo nội dung.
 Nghiên cứu các kỹ thuật đánh chỉ số ảnh và một số các thuật toán phân cụm.
 Ứng dụng kỹ thuật phân cụm có thứ bậc (Agglomerative Hierarchical Clustering -
AHC) vào bài toán tra cứu ảnh sử dụng đặc trưng màu.
 Xây dựng một phần mềm thực nghiệm đọc vào một ảnh phong cảnh mẫu và tìm kiếm
những ảnh phong cảnh tương tự với ảnh mẫu trong một tập hợp các ảnh cho trước.
 Chúng tôi đã tiến hành thực nghiệm với CSDL gồm 2000 ảnh phong cảnh. Kết quả
cho thấy thuật toán phân cụm đạt độ chính xác 95% chỉ với 300 phép so sánh thay vì
2000 phép so sánh vét cạn với toàn bộ ảnh trong CSDL.
KIẾN NGHỊ CÁC HƯỚNG NGHIÊN CỨU TIẾP THEO
Trong quá trình nghiên cứu và thực hiện luận văn đã giúp cho tác giả có nhiều gợi mở
về các định hướng nghiên cứu trong tương lai:
Kết hợp nhiều đặc trưng như: kết cấu, không gian, hình dạng để so sánh độ tương tự
giữa hai ảnh.
Kết hợp nhiều thuật toán để phân cụm ảnh hiệu quả hơn. Thực nghiệm trên CSDL ảnh
có kích thước lớn hơn và đa dạng hơn