Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
i ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CNTT & TT THÁI NGUYÊN
*****

Nguyễn Thị Nhung NGHIÊN CỨU PHƢƠNG PHÁP BIỂU DIỄN VÀ TRA CỨU
ẢNH HIỆU QUẢ ỨNG DỤNG TRONG TRA CỨU ẢNH
PHONG CẢNH

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

NGƢỜI HƢỚNG DẪN KHOA HỌC
TS. Nguyễn Hữu Quỳnh

Thái Nguyên - 2011

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
iii
LỜI CAM ĐOAN
Tôi xin cam đoan luận văn là kết quả nghiên cứu của riêng tôi, dƣới sự hƣớng
dẫn khoa học của TS. Nguyễn Hữu Quỳnh. Các số liệu, kết quả nêu trong luận văn
là hoàn toàn trung thực. Thái nguyên, ngày tháng 9 năm 2011
Ngƣời cam đoan
Nguyễn Thị Nhung


LỜI CẢM ƠN
MỤC LỤC
DANH MỤC CÁC CHỮ VIẾT TẮT ix
DANH MỤC CÁC HÌNH ix
DANH MỤC CÁC BẢNG x
Lời mở đầu x
Chƣơng 1. TỔNG QUAN VỀ TRA CỨU ẢNH DỰA VÀO NỘI DUNG .1
1.1 Giới thiệu 3
1.2 Trích rút đặc trƣng 6
1.2.1 Màu 6
1.2.1.1 Lƣợc đồ màu 7
1.2.1.2 Các màu trội 8
1.2.1.3 Các mômen màu 9
1.2.2 Kết cấu 10
1.2.3 Hình dạng 11
1.2.3.1 Các bất biến mômen 11
1.2.3.2 Các góc uốn 12
1.2.3.3 Các ký hiệu mô tả Fourier 13
1.2.3.4 Hình tròn, độ lệch tâm, và hƣớng trục chính 15
1.2.4 Thông tin không gian 15
1.2.5 Phân đoạn 16
1.3 Đánh chỉ số 18

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
vi
1.4 Độ tƣơng tự giữa các ảnh 18
1.4.1 Độ đo về màu sắc 18
1.4.2 Độ đo tƣơng đồng cho hình dạng 19
1.4.3 Độ đo tƣơng đồng cho kết cấu ảnh 19
1.4.4 Độ đo tƣơng đồng cho đặc trƣng phân đoạn 20

3.3 Thiết kế hệ thống 44
3.4 Mô tả chƣơng trình 45
3.4.1 Khái quát về chƣơng trình 45
3.4.2 Các chức năng của chƣơng trình 46
3.4.3 Biểu đồ Use Case 46
3.4.4 Biểu đồ trình tự và biểu đồ hoạt động 47
3.5 Thiết kế cơ sở dữ liệu 51
3.6 Giao diện chƣơng trình 52
3.7 Xây dựng chƣơng trình: 55
3.8 Đánh giá hiệu quả của các phƣơng pháp 56
3.9 Một số kết quả 57
3.10 Kết luận chƣơng 3 59
KẾT LUẬN 60
TÀI LIỆU THAM KHẢO 61 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
viii
DANH MỤC CÁC CHỮ VIẾT TẮT
Ký hiệu Diễn giải
QBE Query by Example (Truy vấn bởi ảnh mẫu)
QBF Query by Feature (Truy vấn bởi đặc trƣng)
RGB Red Green Blue (Đỏ, Xanh lục, Xanh lơ)
HSV Hue, Saturation, Value (Màu, sắc nét, cƣờng độ)
CCV Color Coherence Vectors (Véc tơ gắn kết màu)
SDF Spectral Distribution Functions (Hàm phân bố phổ)
MLE Maximum Likelihood Estimation (Ƣớc lƣợng khả năng nhất)
AR
MRSAR multi-resolution simultaneous auto-regressive model (Mô hình tự
hồi quy đồng thời đa phân giải)

Hình 3.10.Giao diện thêm một ảnh vào cơ sở dữ liệu. 54
Hình 3.11.Giao diện thêm một tập ảnh vào cơ sở dữ liệu. 54
Hình 3.12.Giao diện xoá một ảnh khỏi cơ sở dữ liệu. 55
Hình 3.13.Ảnh truy vấn. 57
Hình 3.14. Kết quả tìm kiếm đƣợc với phƣơng pháp GCH. 57
Hình 3.15 Kết quả tìm kiếm đƣợc với phƣơng pháp LCH. 58
Hình 3.16.Kết quả tìm kiếm đƣợc với phƣơng pháp HG. 59

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
x
DANH MỤC CÁC BẢNG

Bảng 3.1 Bảng imgBin 51
Bảng 3.2. Bảng imgOri: 51
Bảng 3.3. Bảng imgTemp: 51
Bảng 3.4. Bảng color: 52

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
1
LỜI MỞ ĐẦU

Những năm gần đây việc xử lý ảnh số ngày càng đƣợc nhiều ngƣời quan tâm,
một phần là do dung lƣợng của các thiết bị lƣu trữ và thiết bị số hoá tăng nhanh và
có giá thành giảm. Thêm nữa là 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 dẫn đến 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à khi số lƣợng ảnh trong một bộ sƣu tập còn ít,
chúng ta có thể dùng mắt thƣờng để nhận dạng một bức ảnh, tuy nhiên với một số
lƣợng ảnh lớn thì việc làm thủ công này sẽ không khả thi. Khi số lƣợng ảnh phong
cảnh ngày càng lớn, ngƣời sử dụng muốn tìm kiếm một bức ảnh phong cảnh tƣơng
tự với một ảnh phong cảnh đã có là một việc rất khó khăn.

Chƣơng 1: Giới thiệu tổng quan về tra cứu ảnh dựa vào nội dung
Chƣơng 2: Trình bày kỹ thuật biểu diễn và tra cứu ảnh hiệu quả
Chƣơng 3: Giới thiệu một hệ thống thực nghiệm tra cứu ảnh phong cảnh.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
3
Chƣơng 1. TỔNG QUAN VỀ TRA CỨU ẢNH DỰA VÀO NỘI DUNG
1.1 Giới thiệu
Ngày nay, cùng với nhu cầu tìm kiếm văn bản, nhu cầu tìm kiếm ảnh cũng
nhận đƣợc nhiều quan tâm của ngƣời sử dụng. Tuy nhiên, với một số lƣợng ảnh
quá lớn trên Internet công việc tìm kiếm trở nên vô cùng khó khăn. Để giải quyết
vấn đề này, các hệ thống tìm kiếm ảnh đã ra đời nhƣ: Yahoo, MSN, Google
Image Search, Bing,…. Các hệ thống này cho phép ngƣời sử dụng truy vấn các
ảnh cần quan tâm. Thông qua việc phân tích các văn bản đi kèm ảnh, hệ thống
gửi trả các ảnh tƣơng ứng với truy vấn của ngƣời dùng. Tuy nhiên, các phƣơng
pháp dựa trên văn bản mô tả ảnh dựa trên các phƣơng pháp tra cứu thông tin văn
bản truyền thống và hệ quản trị cơ sở dữ liệu cũng nhƣ sự can thiệp của con ngƣời
để trích rút siêu dữ liệu về một đối tƣợng trực quan và kết hợp nó cùng với đối
tƣợng trực quan nhƣ một chú thích văn bản. Tuy nhiên, gán các thuộc tính văn bản
một cách thủ công cần nhiều thời gian và chi phí. Hơn nữa, các chú thích thủ công
thƣờng phụ thuộc rất nhiều vào nhận thức chủ quan của con ngƣời. Nhận thức chủ
quan và chú thích thiếu chính xác là nguyên nhân tra cứu không chính xác trong các
quá trình tra cứu sau.
Các vấn đề đối với việc truy cập các ảnh và video dựa vào văn bản đã thúc đẩy
nhanh chóng sự quan tâm phát triển các giải pháp dựa vào nội dung. Với giải pháp

đánh chỉ số hiện đại có thể đƣợc sử dụng để tổ chức lại không gian đặc trƣng để
tăng tốc quá trình đối sánh.
4. Thực hiện các điều chỉnh cần thiết trong hệ thống (thƣờng bằng điều chỉnh
các tham số trong máy đối sánh) dựa trên phản hồi từ ngƣời sử dụng và/hoặc các
ảnh đƣợc tra cứu.
Có nhiều cách gửi một truy vấn trực quan. Một phƣơng pháp truy vấn tốt là
một phƣơng pháp tự nhiên đối với ngƣời sử dụng cũng nhƣ thu đƣợc đủ thông tin từ

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
5
ngƣời sử dụng để trích rút các kết quả có ý nghĩa. Các phƣơng pháp truy vấn dƣới
đây đƣợc sử dụng phổ biến trong nghiên cứu tra cứu ảnh dựa vào nội dung:
Truy vấn bởi ảnh mẫu (QBE): Trong loại truy vấn này, ngƣời sử dụng hệ
thống chỉ rõ một ảnh truy vấn đích, dựa trên ảnh truy vấn đó hệ thống sẽ tìm kiếm
trong cơ sở dữ liệu ảnh các ảnh tƣơng tự nhất. Ảnh truy vấn có thể là một ảnh thông
thƣờng, một bản quét của một ảnh có độ phân giải thấp, hoặc một phác thảo của
ngƣời sử dụng sử dụng các công cụ mô tả giao diện đồ hoạ. Một ƣu điểm chính của
loại hệ thống này đó là nó là một cách tự nhiên cho những ngƣời sử dụng chung và
chuyên gia để tìm kiếm một cơ sở dữ liệu ảnh.
Truy vấn bởi đặc trưng (QBF): Trong hệ thống QBF tiêu biểu, những ngƣời
sử dụng chỉ rõ các truy vấn bằng việc chỉ rõ các đặc trƣng họ quan tâm cho tìm
kiếm. Thí dụ, một ngƣời sử dụng có thể truy vấn một cơ sở dữ liệu ảnh bằng việc
đƣa ra một lệnh để tra cứu tất cả các ảnh có góc phần tƣ trái chứa 25% pixel màu
vàng. Truy vấn này đƣợc chỉ rõ bằng việc sử dụng các công cụ giao diện đồ hoạ
chuyên dụng. Những ngƣời sử dụng hệ thống tra cứu ảnh chuyên biệt có thể thấy
loại truy vấn này là bình thƣờng, nhƣng những ngƣời sử dụng chung thì không thể.
QBIC [5] là một ví dụ về một hệ thống tra cứu ảnh dựa vào nội dung sử dụng loại
phƣơng pháp truy vấn này.
Các truy vấn dựa vào thuộc tính: Các truy vấn dựa vào thuộc tính sử dụng
các chú thích văn bản, trích rút trƣớc bởi nỗ lực của con ngƣời, nhƣ một khoá tra

trong lĩnh vực.
Một ảnh màu tiêu biểu đƣợc thu từ một camera số, hoặc đƣợc tải xuống từ
Internet thƣờng có ba kênh màu (các ảnh xám chỉ có một kênh, các ảnh đa phổ có
thể có nhiều hơn ba kênh). Tuy nhiên, các giá trị của dữ liệu ba chiều từ ảnh màu
không cho chúng ta một mô tả chính xác của màu trong ảnh, nhƣng cho vị trí của
các pixel này trong không gian màu. Các pixel có các giá trị
)1,1,1(
sẽ xuất hiện
khác nhau về màu trong các không gian màu khác nhau. Vì thế mô tả đầy đủ của
một ảnh màu tiêu biểu sẽ bao gồm thông tin không gian hai chiều cho biết nơi của

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
7
pixel màu là trong miền không gian, chúng ta đang nói đến không gian màu, và dữ
liệu màu ba chiều cho biết nơi của pixel màu là trong không gian màu này.
Ở đây không gian màu đƣợc giả thiết là cố định, thông tin không gian trong
ảnh bị bỏ qua, và thông tin màu trong một ảnh tiêu biểu có thể đƣợc xem nhƣ tín
hiệu ba chiều đơn.
Các tín hiệu màu một hoặc hai chiều cũng đƣợc sử dụng rộng rãi trong CBIR
đặc biệt trong các ứng dụng mà các điều kiện thu ảnh tƣơng phản mạnh là quan
trọng. Thông tin màu ở dạng các toạ độ xy hoặc ab của các hệ thống CIE XYZ và
CIE LAB có thể đƣợc sử dụng trong các ứng dụng độc lập cƣờng độ. Thông tin màu
(Hue) đƣợc sử dụng trong các ứng dụng nơi chỉ sự khác biệt giữa chất liệu của các
đối tƣợng trong cảnh là quan trọng. Trong [8, 7] đã chỉ ra rằng màu là bất biến dƣới
ánh sáng, bóng, và thay đổi hình học của ngƣời quan sát và các góc chiếu sáng.
Nếu coi thông tin màu của một ảnh nhƣ một tín hiệu một, hai, hoặc ba chiều,
phân tích tín hiệu bằng việc sử dụng ƣớc lƣợng mật độ xác suất là cách đơn giản
nhất để mô tả thông tin màu của ảnh. Lƣợc đồ là công cụ đơn giản nhất. Các cách
mô tả thông tin màu khác trong CBIR gồm sử dụng véc tơ gắn kết màu, tƣơng quan
màu, các màu trội, hoặc các dấu hiệu màu, và các mômen màu.

Khi một cơ sở dữ liệu ảnh chứa một số lƣợng lớn các ảnh, so sánh theo lƣợc
đồ sẽ bão hòa sự phân biệt. Để giải quyết vấn đề này, kỹ thuật lƣợc đồ liên kết đƣợc
giới thiệu. Ngoài ra, lƣợc đồ màu không đƣa thông tin không gian của các pixel vào
xem xét, vì thế các ảnh rất khác nhau có thể có các phân bố màu tƣơng tự. Vấn đề
này trở nên đặc biệt sâu sắc với các cơ sở dữ liệu lớn. Để tăng khả năng phân biệt,
một số cải tiến đã đƣợc đề xuất để liên kết thông tin không gian. Một cách đơn giản
là chia một ảnh thành các vùng con và tính lƣợc đồ cho mỗi vùng con này. Nhƣ đã
đƣợc giới thiệu ở trên, cách chia đơn giản là phân hoạch hình chữ nhật, hoặc phức
tạp nhƣ phân đoạn vùng hoặc thậm chí phân hoạch đối tƣợng. Tăng số các vùng con
sẽ tăng thông tin về vị trí, nhƣng cũng tăng về chi phí bộ nhớ và thời gian tính toán.
1.2.1.2 Các màu trội
Dựa trên quan sát rằng các lƣợc đồ màu thì rất thƣa và thông thƣờng một số
nhỏ các màu là đủ để miêu tả thông tin màu trong một ảnh màu, các màu trội đƣợc

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
9
sử dụng để mô tả nội dung màu của một ảnh. Một phân cụm màu đƣợc thực hiện để
thu các màu trội đại diện của nó và phần trăm tƣơng ứng của nó. Mỗi màu đại diện
và phần trăm tƣơng ứng của nó tạo ra một cặp các thuộc tính mô tả các đặc trƣng
màu trong một vùng ảnh.
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:
 
)11( 1},,{  NipcF
ii

Ở đây
N
là tổng số các cụm màu trong ảnh, c
i

N


)31())(
1
(
2
1
2


iiji
f
N


)41())(
1
(
3
1
1
3



N
j
iiji
f

Kết cấu là một đặc tính quan trọng khác của ảnh. Các biểu diễn kết cấu đa
dạng đã đƣợc nghiên cứu trong nhận dạng mẫu và thị giác máy tính. Về cơ bản, các
phƣơng pháp biểu diễn kết cấu có thể đƣợc phân ra thành hai loại: cấu trúc và thống
kê.
Các phƣơng pháp cấu trúc, gồm toán tử hình thái và đồ thị kề, mô tả kết cấu
bởi nhận dạng cấu trúc gốc và các luật sắp đặt của chúng. Chúng có chiều hƣớng
hiệu quả nhất khi đƣợc áp dụng với các kết cấu đều.
Các phƣơng pháp thống kê, gồm các kỹ thuật phổ năng lƣợng Fourier, các ma
trận đồng khả năng, phân tích thành phần chính bất biến - trƣợt, đặc trƣng Tamura,
phân rã Wold, trƣờng ngẫu nhiên Markov (Markov random field), mô hình fractal,
và lọc đa phân giải nhƣ biến đổi Gabor và sóng, mô tả kết cấu bằng phân bố thống
kê của cƣờng độ ảnh.
Một số biểu diễn kết cấu [15], đƣợc sử dụng thƣờng xuyên và đã đƣợc chứng
minh là hiệu quả trong tra cứu ảnh dựa vào nội dung.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
11
1.2.3 Hình dạng
Các đặc trƣng hình dạng của các đối tƣợng hoặc các vùng đã đƣợc sử dụng
trong nhiều hệ thống tra cứu ảnh dựa vào nội dung. So với các đặc trƣng màu và kết
cấu, các đặc trƣng hình dạng thƣờng đƣợc mô tả sau khi các ảnh đƣợc phân đoạn
thành các vùng hoặc các đối tƣợng. Do phân đoạn ảnh mạnh và chính xác là khó đạt
đƣợc, sử dụng các đặc trƣng hình dạng cho tra cứu ảnh bị giới hạn đối với các ứng
dụng chuyên biệt, ở đó các đối tƣợng hoặc các vùng đã sẵn có. Các phƣơng pháp
state-of-art cho mô tả hình có thể đƣợc phân thành hoặc là các phƣơng pháp dựa
vào đƣờng bao hoặc các phƣơng pháp dựa vào vùng. Một biểu diễn đặc trƣng hình
tốt cho một đối tƣợng phải bất biến với dịch chuyển, quay và tỷ lệ. Chúng ta sẽ mô
tả ngắn gọn một số đặc trƣng hình đƣợc sử dụng phổ biến trong các ứng dụng tra
cứu ảnh với một giới thiệu tổng quan ngắn gọn về các kỹ thuật đối sánh hình.
1.2.3.1 Các bất biến mômen

,
0,0
,
,



qp
qp
qp






Dựa trên các mômen này, một tập các bất biến mômen đối với dịch chuyển,
quay và tỷ lệ có thể tìm thấy trong:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
12
 
 
 
 
2
1,23,0
2
2,10,32,10,33,01,27
1,23,02,10,31,1

)3()3(
4)(

















1.2.3.2 Các góc uốn
Chu tuyến (contour) của một đối tƣợng hai chiều có thể đƣợc biểu diễn bằng
một dãy đóng đƣờng bao các pixel liên tiếp
)y,x(
ss
, ở đây
1Ns0 
là tổng số
các pixel trên đƣờng biên đóng. Hàm xoay hoặc góc xoay
)s(




'
)81('
'
'
tan)(
1


Một vấn đề chính đối với biểu diễn này là nó biến đổi đối với quay của đối
tƣợng và chọn điểm tham chiếu. Nếu chúng ta trƣợt điểm tham chiếu dọc theo
đƣờng bao của đối tƣợng bởi một lƣợng
t
, thì hàm xoay mới trở thành
)ts( 

.
Nếu chúng ta quay đối tƣợng một góc

thì hàm mới trở thành

)s(
.
Do đó, để so sánh sự tƣơng tự hình giữa các đối tƣợng
A
và
B
với các hàm
xoay của nó, khoảng cách tối thiểu cần đƣợc tính toán trên tất cả các trƣợt



Ở đây chúng ta giả thiết rằng mỗi đối tƣợng đã tỷ lệ lại sao cho tổng độ dài
chu vi là 1. Độ đo này là bất biến với dịch chuyển, quay, và thay đổi tỷ lệ.
1.2.3.3 Các ký hiệu mô tả Fourier
Các ký hiệu mô tả Fourier mô tả hình của một đối tƣợng với biến đổi Fourier
của đƣờng bao của nó. Xét đƣờng biên đóng của một đối tƣợng hai chiều bằng một
dãy đóng các pixel bao liên tiếp
)y,x(
ss
, ở đây
1Ns0 
và
N
là tổng số các
pixel trên đƣờng bao. Sau đó ba loại biểu diễn đƣờng biên đóng, tức là, độ cong,
khoảng cách trọng tâm, và hàm toạ độ phức hợp, có thể đƣợc định nghĩa.
Độ cong
)s(K
tại một điểm
s
dọc theo đƣờng biên đóng đƣợc định nghĩa nhƣ
tỷ lệ thay đổi theo hƣớng tiếp tuyến của đƣờng biên đóng, tức là,
)s()s(K
ds
d


(1-10)
Ở đây

DC
hoặc hệ số khác không đầu tiên. Bất
biến dịch chuyển thu đƣợc trực tiếp từ biểu diễn đƣờng biên đóng.
Các ký hiệu mô tả Fourier của đƣờng cong là:
 
)141(, ,,
2/21

MK
FFFf

Ký hiệu mô tả Fourier của khoảng cách trọng tâm là:
)151(, ,,
0
2/
0
2
0
1










F

1
)12/(












F
F
F
F
F
F
F
F
f
M
M
Z

Ở đây
1
F

2

P
S



Ở đây
S
là cỡ và
P
là chu vi của một đối tƣợng. Giá trị này có phạm vi giữa 0
và 1.
Hƣớng trục chính có thể đƣợc định nghĩa nhƣ hƣớng của véc tơ riêng lớn nhất
của ma trận hiệp biến bậc hai của một vùng hoặc một đối tƣợng. Độ lệch tâm có thể
đƣợc định nghĩa nhƣ tỷ lệ của trị riêng nhỏ nhất với trị riêng lớn nhất.
1.2.4 Thông tin không gian
Các vùng hoặc đối tƣợng với các đặc tính màu và kết cấu tƣơng tự có thể đƣợc
phân biệt dễ dàng bằng việc tận dụng các ràng buộc không gian. Thí dụ, các vùng
bầu trời màu xanh và biển xanh có thể có các lƣợc đồ màu tƣơng tự, nhƣng các vị trí
không gian của chúng trong các ảnh là khác nhau. Do đó, vị trí không gian của các
vùng (hoặc các đối tƣợng) hoặc quan hệ không gian giữa nhiều vùng (hoặc đối
tƣợng) trong một ảnh thì rất hữu ích cho tìm kiếm các ảnh.
Thu thông tin không gian của các đối tƣợng trong một ảnh là một quá trình
quan trọng đối với các hệ thống GIS. Quá trình này bao gồm việc biểu diễn vị trí
không gian tuyệt đối và cũng bao gồm vị trí không gian tƣơng đối của các đối
tƣợng. Các thao tác nhƣ giao và chồng đƣợc sử dụng. Bố cục màu kết hợp thông tin
không gian với thông tin màu xuất hiện trong ảnh và tạo ra một đặc trƣng rất quan
trọng trong quá trình tra cứu, gọi là đặc trƣng màu – không gian.
Biểu diễn quan hệ không gian đƣợc sử dụng rộng rãi nhất là các xâu