1
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Vũ Thị Quế

NGHIÊN CỨU PHƯƠNG PHÁP BIỂU DIỄN ẢNH VÀ ĐỘ ĐO TƯƠNG TỰ
HIỆU QUẢ ỨNG DỤNG TRONG TRA CỨU ẢNH QUA MẠNG Chuyên ngành:Truyền dữ liệu và mạng máy tính
TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI – NĂM 2012 2
Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện
Công nghệ Bưu chính Viễn thông

3
MỞ ĐẦU
Ngày nay, sự phát triển mạnh mẽ công nghệ thông tin và đặc biệt là sự phát
triển mạng Internet làm cho một số lượng khổng lồ các ảnh số được đưa lên mạng.
Một thực tế khác là hiện nay số lượng ảnh ngày càng lớn. Khi một người sử
dụng muốn tìm kiếm một bức tranh tương tự với một ảnh đã có là một việc khó.
Từ những thực tế đó đặt ra vấn đề phải có những phương pháp tổ chức cơ sở
dữ liệu ảnh và xây dựng những kỹ thuật tra cứu, so sánh, tìm kiếm ảnh số hiệu quả.
Một trong những phương pháp được nhiều người quan tâm nghiên cứu hiện nay là
kỹ thuật "Tra cứu ảnh dựa theo nội dung" (Content Based Image Retrieval). Kỹ
thuật này 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 cơ sở dữ liệu ảnh. Một số hệ thống tra cứu ảnh nổi tiếng như
QBIC (IBM), Virage (Virage Inc.) Photobook (MIT) Visual SEEK (Columbia
University) đã áp dụng thành công kỹ thuật này.
Để giảm chi phí về không gian lưu trữ, thời gian so sánh các véc tơ đặc
trưng và thời gian tra cứu, cần có kỹ thuật biểu diễn, trích rút và độ đo tương tự hiệu
quả. Đề tài này nghiên cứu cơ sở lý thuyết và các ứng dụng chính của kỹ thuật tra
cứu ảnh theo nội dung và kỹ thuật biểu diễn và độ đo tương tự hiệu quả, trên cơ sở
đó thử nghiệm phương pháp cụ thể để xây dựng một phần mềm đọc vào một ảnh
mẫu và qua mạng tìm kiếm những ảnh tương tự với ảnh mẫu trong một tập hợp các
ảnh cho trước.
Nội dung luận văn gồm 3 chương:
Chương 1: Tổng quan về tra cứu ảnh dựa vào nội dung.
Chương 2: Kỹ thuật biểu diễn và độ đo tương tự hiệu quả.

mẫu màu là duy nhất so với phần còn lại của tập dữ liệu. Lược đồ màu là dễ dàng để
tính toán và hiệu quả trong mô tả cả phân bố màu toàn cục và cục bộ trong ảnh. Hơn
nữa, nó mạnh với quay và dịch chuyển về trục quan sát và thay đổi chậm với tỷ lệ
và góc quan sát.
Các màu trội
Ký hiệu mô tả đặc trưng lược đồ màu trội F được định nghĩa là một tập các cặp
sau:

5


)11( 1},,{  NipcF
ii

Ở đây
N
là tổng số các cụm màu trong ảnh, c
i
là một véc tơ màu ba chiều, p
i
là
phần trăm của nó, và


i
i
1p
. Lưu ý rằng
N
có thể thay đổi từ ảnh này sang ảnh

+
và R
*
.
1.4 Độ tương tự giữa các ảnh
1.4.1 Độ đo về màu sắc
Một số độ đo tương đồng được sử dụng như: Độ đo khoảng cách Ơclit, độ
đo
Jensen-Shannon divergence
(JSD).


Khoảng cách
Ơclit:
Intersection (h(I),h(M)) =
2
1
( ( ) ( ))
k
j
h I h M



2
1
( ( ) ( ))
k
j
h I hM

sánh,
H
m
là dải thứ m của biểu
đồ H.
1.4.2 Độ đo tương đồng cho hình dạng
Độ đo về hình dạng rất nhiều trong phạm vi lý thuyết của bộ môn xử lý
ảnh.
Chúng trải rộng từ những độ đo toàn cục dạng thô với sự trợ giúp của việc
nhận
dạng đối tượng, cho tới những độ đo chi tiết tự động tìm kiếm những hình
dạng
đặc
biệt
1.4.3 Độ đo tương đồng cho kết cấu ảnh
Kết cấu được trích xuất từ các bức ảnh sẽ được biểu diễn thành các véc tơ
nhiều
chiều và khoảng cách Ơclit được dùng để đo độ tương đồng giữa các đặc trưng
của
ảnh truy vấn với đặc trưng của ảnh trong cơ sở dữ
liệu

1.4.4 Độ đo tương đồng cho đặc trưng phân đoạn


Độ đo Cosin:
d
(x,y) =
.
.

i i
i
x y



2
1
m
i i
i
x y




1.5 Các hệ thống CBIR
1.5.1 QBIC của IBM
QBIC hỗ trợ chính các truy vấn dựa vào các ảnh mẫu, các phác thảo và các bản vẽ
được người sử dụng xây dựng, và các mẫu kết cấu và màu được lựa chọn.
1.5.2 Virage
Virage hỗ trợ các truy vấn trực quan dựa trên màu, thành phần cấu tạo (bố cục
màu), kết cấu và cấu trúc (thông tin đường bao đối tượng)
1.5.3 RetrievalWare
RetrievalWare là ứng dụng của các mạng neural để tra cứu ảnh sử dụng màu,
hình, kết cấu, độ sáng, bố cục màu, và hướng tỷ lệ của ảnh, như các đặc trưng truy
vấn.
1.5.4 VisualSeek và WebSeek
VisualSEEk là một máy tìm kiếm đặc trưng trực quan và WebSEEk là một máy
tìm kiếm văn bản/ảnh trên web. Các đặc trưng trực quan được sử dụng trong các hệ

Trong chương này, chúng tôi đã giới thiệu một số khái niệm và kỹ thuật cơ bản về
tra cứu ảnh dựa vào nội dung, bao gồm: trích rút đặc trưng, đánh chỉ số, độ tương tự
giữa các ảnh, các hệ thống tra cứu ảnh, đánh giá hiệu năng tra cứu và trình bày một
số hệ thống CBIR.
9
Chương 2:KỸ THUẬT BIỂU DIỄN VÀ ĐỘ ĐO TƯƠNG TỰ
HIỆU QUẢ
2.1 Giới thiệu
Động cơ chính của việc nghiên cứu phương pháp biểu diễn ảnh hiệu quả là: tra
cứu độ tương tự trong cơ sở dữ liệu ảnh lớn sử dụng màu sắc. Màu sắc trong một
vùng sẽ được chia thành nhiều cụm nhỏ các màu. Mô tả đặc trưng bao gồm biểu
diễn màu và tỉ lệ của chúng trong vùng. Phương pháp đo độ tương tự được sử dụng
trong đồ án sử dụng độ đo khoảng cách lược đồ màu chính phương, nghĩa là màu
sắc biểu diễn có thể được đánh chỉ số trong tọa độ không gian màu ba chiều (3D),
điều này có thể giúp chương trình tránh được các vấn đề có thể sảy ra như đối với
việc sử dụng lược đồ màu truyền thống. Để tra cứu độ tương tự, mỗi màu biểu diễn
trong ảnh truy vấn được kết hợp để đưa ra kết quả cuối cùng. Hiệu quả đánh chỉ số
sẽ được đưa ra nhằm tăng tốc độ tra cứu. Thực nghiệm cho thấy rằng phương pháp
miêu tả kết hợp này sẽ cho hiệu quả tra cứu cao hơn so với phương pháp lược đồ
màu truyền thống.
2.2 Một số kỹ thuật tra cứu ảnh dựa vào đặc trưng màu
2.2.1 Các không gian màu
Một không gian màu chỉ rõ các màu như các bộ số, theo các đặc tả nào đó. Các
không gian màu có thể dùng để sinh ra các biểu diễn màu, đặc biệt trong các biểu
diễn số, như in số hoặc hiển thị điện tử số. Mục đích của không gian màu là để phục
vụ đặc tả các màu theo một số cách chuẩn, được chấp nhận chung
Một số không gian màu phổ biến là : Không gian màu RGB, HSx, YUV và YIQ,

i
= 1.
Lưu ý: N có thể thay đổi qua mỗi vùng.
2.3.1 Phân cụm màu
Trong thuật toán phân cụm giá trị màu của điểm ảnh là vector lượng hóa sử dụng
thuật toán Loyd tổng quát (GLA). Màu được biểu diễn trong không gian màu đồng
dạng CIE LUV. Sự thay đổi D trong mỗi cụm có thể được tính theo công thức:
D
i
=
||
2
)(||)(


n
i
c
nxnv
,


i
Cnx

(2.2)
Với c
i
là trọng tâm của cụm, x(n) là vector màu tại điểm ảnh n, v(n) là trọng số
cảm quan của điểm ảnh n Để tính toán ra độ cảm nhận màu sắc ta dùng công thức:

có dạng các mô tả
màu được đưa ra bởi (2.1). Ta có hai mô tả đặc trưng màu như sau:
F
1
= {{c
i
, p
i
}, i = 1,…, N
1
}
Và F
2
= {{b
j
, q
j
}, j = 1,…, N
2
}
Khoảng cách giữa F
1
và F
2
được tính theo công thức:
 
ji
N
i
N








dji
djiji
ji
Td
Tddd
a
,
,max,
,
,0
,1
(2.5)
Với d
i,j
là khoảng cách Euclide giữa màu c
i
và b
j

d
i,j
= ||c
i

là các vector lược đồ màu truyền thống, và các hệ số của ma trận
A là a
i,j
. Mặt khác, nếu số bin của màu trong vector lược đồ N
h
là đủ lớn sao cho tất
cả các màu đại diện là các bin màu của phương pháp lược đồ màu. Khoảng cách
bình phương được viết lại như sau:
 
 
    

2 2 1 21 1
1 1 1 1
,,
1 1
,21
2
2,
N
j
N
l
N
i
N
j
jijiljlj
N
i

lj
lj
a
lj
,0
,1
,
(2.9)
Ta có thể dễ dàng nhận ra: D
h
(H
1
,H
2
) = D(F
1
,F
2
). 12
2.4 Độ tương tự
2.4.1 Cấu trúc mạng D
*
3

Có hai tham số quan trọng trong việc thiết kế mạng: p bán kính tối thiểu của
một hình cầu có thể bao gồm các tế bào Voronoi, và p’ là bán kính tối đa có thể của
các tế bào Voronoi. Hình 2.4 minh họa các thông số đối với trường hợp 2-D.







 (2-11)
và 2.
2
0
LL
L
Lc
roundb 







 (2.12)
Ở đây L = 2s, và L là kích thước dọc theo trục tọa độ. Ví dụ L = 2 đối với các
mạng cơ bản. Chú ý rằng b
e
là điểm mạng chẵn gần nhất và b
0
là điểm lưới lẻ gần
nhất đối với điểm c cho trước. Cho b={b
e

biệt giữa phần trăm truy vấn p
i
và tỷ lệ thu hồi q
j
. Một khu vực bị loại nếu không
đạt điều kiện sau:
| p
i
– q
j
| < T
p
(2.14)
Bước 2: Các truy vấn màu sẽ được lấy nếu kết quả phù hợp và loại bỏ tất cả
các kết quả sai. Khu vực mà phù hợp hai điều kiện sau đây được coi như đã thu
được các điều kiện cuối cùng:

t
i
i
Tp 

và
t
j
j
Tq 

(2.15)
và ở đây i và j là chỉ số màu phù hợp. Giá trị của T

Từ những thực tế trên đặt ra một bài toán tra cứu ảnh phong cảnh như sau: tìm
trong một cơ sở dữ liệu ảnh phong cảnh những ảnh có nội dung (màu sắc, hình
dạng, kết cấu) giống với một ảnh phong cảnh mẫu nhất, sau đó phân hạng theo thứ
tự giảm dần của độ tương tự.
Với hệ thống tra cứu ảnh qua mạng bạn chỉ cần đường kết nối Internet và một
chiếc máy tính. Bạn không cần phải lo lắng về việc cài đặt phần mềm. Ngoài ra bạn
có thể tra cứu bất kỳ lúc nào và bất kỳ nơi đâu.
3.2 Phân tích bài toán
Nhiệm vụ của bài toán là xây dựng hệ thống tra cứu ảnh phong cảnh có một số các
chức năng sau:
o Khi người sử dụng cung cấp một ảnh phong cảnh mẫu cần tra cứu. Hệ thống
có nhiệm vụ tìm kiếm trong một cơ sở dữ liệu ảnh đã có và cho ra một danh
sách tất cả các ảnh tương tự như ảnh mẫu theo thứ tự ảnh nào tương tự với ảnh
mẫu hơn thì được phân hạng ở phía trên.
o Người sử dụng có thể qui định số lượng ảnh kết quả trả lại.
3.3 Thiết kế hệ thống
Hệ thống được mô tả tổng quát như sau:
Từ một cơ sở dữ liệu ảnh cho trước, ta tiến hành trích rút các đặc trưng của các
ảnh và lưu trữ trong cơ sở dữ liệu đặc trưng.
Người sử dụng đưa vào một ảnh truy vấn, các đặc trưng của ảnh truy vấn này
được tập hợp thành các véc tơ đặc trưng. Sau đó, hệ thống tiến hành so sánh các véc
tơ đặc trưng này với các đặc trưng trong cơ sở dữ liệu đặc trưng để từ đó tìm ra độ

16
tương tự. Tra cứu nào cho độ tương tự cao nhất thì chúng ta được kết quả tốt nhất.
Tức là kết quả tìm được là giống nhất với ảnh truy vấn ban đầu.
Tác nhân tra cứu
 Chọn ảnh truy vấn.
 Chọn tra cứu ảnh.
Hệ thống thực hiện trích rút đặc trưng màu của ảnh truy vấn, so sánh với các đặc

sưu tầm trên Internet với nhiều chủ đề như bầu trời, hoa, ngựa, Chúng ta sẽ xem
kết quả của hệ thống khi tra cứu với một số ảnh thuộc các chủ đề khác nhau để thấy
được sự hiệu quả của hệ thống.
3.5.2 Kết quả thử nghiệm
Từ hệ thống tra cứu ảnh qua mạng, chúng tôi tiến hành thử nghiệm với 5 truy
vấn, trong đó 3 truy vấn được lấy trong tập ảnh cơ sở dữ liệu và 2 truy vấn được lấy
ở ngoài tập ảnh cơ sở dữ liệu.
 Truy vấn lấy trong tập ảnh cơ sở dữ liệu:
Thử nghiệm 1:

Ảnh truy vấn 1
Với ảnh truy vấn 1, hệ thống tra cứu trả ra 20 ảnh kết quả, trong đó có 16 ảnh kết
quả tương tự với ảnh truy vấn 1 và 4 ảnh kết quả có độ tương tự kém hơn so với ảnh
truy vấn 1.
- Các ảnh phù hợp với ảnh truy vấn:
21- Các ảnh không phù hợp với ảnh truy vấn:

Hình 3.6. Kết quả tra cứu với mặt trời
 Truy vấn lấy ngoài tập ảnh cơ sở dữ liệu:
Thử nghiệm 1:

Truy vấn 1:
Với ảnh truy vấn 1, hệ thống tra cứu trả ra 20 ảnh kết quả, trong đó có 18 ảnh kết
quả tương tự với ảnh truy vấn 1 và 2 ảnh kết quả có độ tương tự kém hơn so với ảnh

■ Ứng dụng kỹ thuật phân cụm vào quá trình phân đoạn ảnh.
■ Xây dựng một phần mềm thực nghiệm qua mạng đọc vào một ảnh mẫu và
tìm kiếm những ả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 cơ sở dữ liệu gồm 1000 ảnh, kết quả
thực nghiệm cho thấy khá hiệu quả.

KIẾN NGHỊ VÀ HƯỚNG NGHIÊN CỨU TIẾP THEO
- Thử nghiệm trên tập ảnh có kích cỡ lớn và đa dạng chủ đề hơn.
- Kết hợp thêm các đặc trưng khác vào quá trình tra cứu.
- Từng bước đưa vào ứng dụng thực tế.