HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

Nguyễn Thị Tâm
NGHIÊN CỨU PHƯƠNG PHÁP TRA CỨU ẢNH SỬ DỤNG
THÔNG TIN PHẢN HỒI TỪ NGƯỜI DÙNG Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01.01 TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI - 2014


Luận văn được hoàn thành tại:
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

Người hướng dẫn khoa học: TS. Nguyễn Hữu Quỳnh
Phản biện 1: TS Hoàng Lê Minh.

Phản biện 2: PGS.TS Đặng Văn Chuyết. 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
Vào lúc: 14h15 ngày 15 tháng 02 năm 2014

Có thể tìm hiểu luận văn tại:
- Thư viện của Học viện Công nghệ Bưu chính Viễn thông

MỞ ĐẦU
Trong thập kỷ số, hàng triệu các ảnh đã được lưu trữ trong các cơ sở dữ liệu khổng lồ
và trên Internet, để tìm các ảnh quan tâm trong các tập ảnh này đòi hỏi một cách tiếp cận
mới. Hầu hết các ảnh này không phải do chúng ta sở hữu, do đó chúng ta không có tri thức
để có thể hỗ trợ tìm kiếm các ảnh quan tâm thuận lợi. Nếu tìm kiếm các ảnh trong các cơ sở

thông tin và tra cứu ảnh.
Chương 2 : Phương pháp tra cứu ảnh sử dụng thông tin phản hồi từ người dùng:
Chương này giới thiệu các kỹ thuật sử dụng trong tra cứu ảnh dựa vào nội dung sử dụng
phản hồi liên quan bao gồm kỹ thuật phân vùng ảnh, trích rút đặc trưng và đánh lại trọng số
vùng.
Chương 3: Chương trình thử nghiệm: Xây dựng mô hình, chạy thử với tập cơ sở
dữ liệu gồm 1000 ảnh và đánh giá hiệu quả của phương pháp tra cứu.
CHƯƠNG 1: TỔNG QUAN VỀ TRA CỨU ẢNH SỬ DỤNG PHẢN
HỒI LIÊN QUAN
1.1 Tra cứu thông tin
Tra cứu thông tin (IR – Information Retrieval) là việc thu thập các nguồn thông tin
liên quan trong một tập các nguồn tài nguyên. Truy vấn hệ thống có thể là văn bản, hình
ảnh, audio, bản đồ tư duy hoặc video.
1.2 Phản hồi liên quan trong tra cứu thông tin
Phản hồi liên quan (RF – Relevance Feedback) trong tra cứu thông tin chứa người
dùng trong quá trình tra cứu để cải thiện tập kết quả cuối cùng. Thủ tục cơ sở là:
- Người dùng tạo một truy vấn.
- Hệ thống trả lại một tập các kết quả tra cứu ban đầu.
- Người dùng đánh dấu một số tài liệu được trả về là liên quan hoặc không liên
quan.
- Hệ thống tính toán một đại diện tốt nhất của nhu cầu thông tin dựa trên phản hồi
của người dùng.
- Hệ thống hiển thị một tập các kết quả tra cứu được hiệu chỉnh.
Véc tơ truy vấn mà chúng ta muốn tìm được biểu thị bằng
q

, mà cực đại sự tương tự
với các tài liệu liên quan trong khi cực tiểu sự tương tự với các tài liệu không liên quan
được mô tả:
Véc tơ truy vấn tối ưu:

r
opt
d
C
d
C
q




11
(1.2)
Thuật toán Rocchio
nrjrj
Dd
j
nr
Dd
j
r
m
d
D
d
D
qq




p
ii
JfIfJID
/1
))()((),(

Trong đó D(I,J) là khoảng cách đo giữa ảnh truy vấn I và ảnh J trong cơ sở dữ
liệu; f
i
(I) là số pixel trong bin i của ảnh I.
1.3.5 Một số hệ thống CBIR tiêu biểu
1.3.5.1 Hệ thống Blobwold
Hệ thống Blobwold của khoa Khoa học máy tính, Đại học California, Berkeley. Các
đặc tính được sử dụng cho truy vấn là màu sắc, kết cấu, vị trí và hình dạng của vùng và nền
1.3.5.2 Hệ thống Query By Image Content (QBIC)
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.3.5.3 Hệ thống VisualSeek
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ệ
thống của họ là các tập màu và các đặc trưng kết cấu dựa vào biến đổi sóng
1.4 Tra cứu ảnh sử dụng phản hồi liên quan
Phản hồi liên quan được giới thiệu trong CBIR nhằm giải quyết một số hạn chế của
CBIR: Khoảng trống giữa các đặc trưng mức thấp và các khái niệm mức cao (khoảng cách
ngữ nghĩa); Sự nhận thức chủ quan của con người mà thực tế chủ yếu góp phần làm cho
phản hồi liên quan là chủ đề nghiên cứu tích cực nhất trong CBIR là do độ chính xác của
các máy tìm kiếm CBIR nói chung rất thấp.
Phản hồi liên quan được giới thiệu trong CBIR trong đó người và máy tính tương tác
nhiều lần với nhau để cải tiến các truy vấn mức cao đối với các biểu diễn dựa trên các đặc
trưng ảnh mức thấp.

Trong chương này, chúng tôi đã giới thiệu một số khái niệm cơ bản của phản hồi liên
quan trong tra cứu thông tin, tra cứu ảnh dựa vào nội dung, một số hệ thống tra cứu ảnh dựa
vào nội dung, phản hồi liên quan trong tra cứu ảnh đánh giá hiệu năng tra cứu. Đặc biệt tôi
muốn nhấn mạnh vào phản hồi liên quan trong tra cứu thông tin và tra cứu ảnh.
CHƯƠNG 2: PHƯƠNG PHÁP TRA CỨU ẢNH SỬ DỤNG THÔNG
TIN PHẢN HỒI TỪ NGƯỜI DÙNG
2.1 Giới thiệu
Tra cứu ảnh dựa vào nội dung sử dụng đặc trưng mức thấp như màu sắc, kết cấu, hình
dạng…là một lĩnh vực nghiên cứu tích cực trong một vài năm qua. Tuy nhiên, các hệ thống
này thường cho các kết quả không gần với nhận thức của con người. Phần này chúng tôi xin
trình bày phương pháp tra cứu ảnh dựa vào nội dung sử dụng thông tin mà người dùng quan
tâm để nâng cao hiệu năng của hệ thống tra cứu. Để thực hiện điều này, thuật toán đánh lại
trọng số vùng dựa trên thông tin quan tâm của người dùng được đề xuất. Các trọng số vùng
trùng với nhận thức của người dùng sẽ cải tiến độ chính xác. Các trọng số vùng được ghi
nhớ lại để dùng cho các truy vấn sau.
2.2 Phân vùng ảnh
2.2.1 Phân cụm dựa vào màu sắc (CBC – Color based Clustering)
Ý tưởng chính của kỹ thuật phân cụm dựa vào màu sắc là: mỗi ảnh được chia thành
các vùng, mỗi vùng có một véc tơ đặc trưng riêng và có kích thước lớn hơn hoặc bằng
ngưỡng cỡ s
0
, tất cả các pixel của vùng đã được xác định trước độ tương tự màu theo
ngưỡng khoảng cách màu d
0
. Ngưỡng d
0
, s
0
của vùng CBC(d
0

6. E

SortIncreasingOrder(E);
7. For mỗi (u,v) E do
7.1 If (d(Find-Region(u), Find-Region(v)<d
0
)
7.1.1 If (Find-Region(u) Find-Region(v))
Merge(u,v)
7.1.2 else break;
8. For mỗi vùng R
i
R
8.1 If (Size(R
i
)<T)
8.1.1 R
j

GetNeighborRegion(R
i
)
8.1.2 Merge(R
i
, R
j
)
9. Return R
Thủ tục ConvertGraph() chuyển ảnh cần phân đoạn I thành đồ thị G, hàm
GetVertexSet() trả về tập đỉnh của đồ thị G, hàm GetEdgeSet(G) trả lại tập cạnh của đồ thị

j
là vùng chứa ảnh A, B tương ứng, L
2
(.,.) là hàm trả về khoảng cách
L
2
giữa các đối số của nó.
Thuật toán tính khoảng cách giữa hai ảnh A và B. Hàm trả về khoảng cách giữa các
vùng tương ứng của ảnh A và B.
Hàm tính khoảng cách d(A,B,α)
1. for mỗi cặp vùng A
i
A và B
j
B
2.
0.statusA
i

3.
0.statusB
j

4.
),,(
jiBA
BARdD
ji

5. sắp xếp khoảng cách

1.statusA
i

13. else
14.
sizeBw
j
.

15.
sizeBsizeAsizeA
jii16.
1.statusB
j

17. if
0.sizeA
i
then
1.statusA
i

18.
ji
BA
Dw


(2.2)
Ở đây, X(R
i
) và Y(R
j
) là các tọa độ x và y của các tâm của các vùng.
Khoảng cách giữa hai vùng về mặt nội dung (màu và cỡ) được tính toán theo công
thức:
n
k
n
k
jkik
n
k
jkik
RHRH
RHRH
RRDR
0 0
0
)()(
)()(
),(
(2.3)
Ở đây H(R
i
) và H(R
j
) là các lược đồ màu gồm n bin của các vùng R

, R
2
,…, R
n
} là:
n
i
k
RRsARs
1
),(),(
(2.5)
Định nghĩa 3: Sự tương tự giữa một vùng R và một tập ảnh IS gồm các ảnh {A
1
,
A
2
,…,A
n
} là:
n
k
k
ARsISRs
1
),(),(
(2.6)
Trọng số vùng được xác định như sau:
Định nghĩa 4: Trọng số của vùng R
i

sau m lần cập nhật là:
m
RWmCRW
mCRW
ii
i
)1(
)(
(2.9)
Thuật toán WIR (Weight of Image Region), tính trọng số của các vùng cho lần truy
vấn thứ m với bước lặp k.
Thuật toán WIR
Đầu vào: QI - ảnh truy vấn đã được phân vùng
k- bước lấy thông tin phản hồi
CRW
i
(m-1) – trọng số tích lũy
IS
+
(k) – tập ảnh tích cực ở bước k đã được phân vùng
IS
-
(k) – tập ảnh tiêu cực ở bước k được phân vùng
Đầu ra: RW(k) – danh sách trọng số các vùng của các ảnh ứng
với ảnh I tại bước k
1. Khởi tạo
1.1 sp
-



j
, IS
-
(k))
sp
+


sp
+
+ RP
j
.s(R
j
, IS
+
(k))
2.2.1.1.2 RP
i


1-
sp
kISRs
i
))(,(

2.2.1.1.3 RW
i
(k)

(0)

CRW
i
(0);
1.4 RW
i


RW
i
(0);
2. For mỗi ảnh QI QIS do
2.1 m

m+1;
2.2 Repeat
2.2.1
m
RWmCRW
mCRW
ii
i
)1(
)(

2.2.2 RW

WIR (QI, k, CRW
i

, RA
2
,…,
RA
n
} và {RB
1
, RB
2
,…, RB
m
} tương ứng và trọng số của đối sánh tương ứng để so sánh hai
ảnh.
Thuật toán CI (Comparing Two Images) so sánh độ tương tự giữa hai ảnh:
Thuật toán CI
Đầu vào: A- Ảnh thứ nhất được biểu diễn bởi {RA
1
, RA
2
,…,RA
n
}
B - Ảnh thứ hai được biểu diễn bởi {RB
1
, RB
2
,…, RB
m
}
RWA

←0;
2.1.1.3 D
denominator1
←0;
2.1.1.4 D
denominator2
←0;
2.1.1.5 for k

0 to e do
D
numerator


D
numerator
+ abs(H
k
(RA
i
) – H
k
(RB
j
))
D
denominator1


D

RBRADRRBRADRs

2.1.1.8 if (s
i,j
>ε)
W
i,j


(1-|RWA
i
- RWB
j
|)
2.1.1.9 else
W
i,j

0
3. Tính độ tương tự của hai ảnh
3.1 for I

1 to n do
3.1.1 for j

1 to m do
3.1.1.1 SI

SI + s
i,j

ảnh cơ sở dữ liệu. Tiếp theo, tập các ảnh kết quả được trả về. Trên tập các ảnh kết quả này,
người dùng đánh giá và gán nhãn cho các ảnh là tích cực hay tiêu cực ở khối gán nhãn. Khối
học, các nhãn vừa được người dùng gán sẽ được sử dụng để cập nhật trọng số của các vùng.
Sử dụng trọng số các vùng vừa được cập nhật, hệ thống hiệu chỉnh tập các ảnh kết quả trả
về. Quá trình này dừng lại khi người dùng thỏa mãn yêu cầu.

Hình 3.1 Sơ đồ hệ thống tra cứu ảnh sử dụng phản hồi liên quan
3.2.2 Xây dựng chương trình
3.2.2.1 Biểu đồ Use case
3.2.2.2 Biểu đồ trình tự và biểu đồ hoạt động
Tác nhân tra cứu ảnh:
Mô tả công việc:
o Người sử dụng chọn ảnh truy vấn và ấn nút tra cứu ảnh.
o Hệ thống sẽ tiến hành tìm kiếm và hiển thị kết quả ra màn hình.
Tác nhân phản hồi ảnh:
Mô tả công việc:
o Người sử dụng cung cấp ảnh tích cực và ảnh tiêu cực từ kết quả hiển thị ở bước
tra cứu ảnh và ấn nút phản hồi.
o Hệ thống sẽ tiến hành tính toán và cập nhật lại các trọng số (bất lợi vùng và đặc
trưng ảnh truy vấn).
o Người sử dụng ấn nút tra cứu để đưa ra kết quả sau lần phản hồi.
Tác nhân upload ảnh:
Mô tả công việc:
o Người sử dụng chọn một file ảnh để upload:
 Hệ thống tiến hành lấy thông tin và trích rút đặc trưng của các vùng ảnh.
 Nếu không có lỗi thì cập nhật vào cơ sở dữ liệu (CSDL), ngược lại thông báo
lỗi.
o Người sử dụng chọn nhiều file ảnh để upload:
 Chọn một thư mục chứa ảnh cần đưa vào CSDL.
 Duyệt từng file ảnh trong thư mục và tiến hành ghi từng file ảnh vào CSDL

của LU
1
Ngựa
71
56%
2
Cảnh hoàng hôn
85
52%
3
Vườn hoa
121
63%
4
Rừng
130
60%
5
Bầu trời, phong cảnh
356
78%
6
Nhà cửa
115
50%
7
Các loại khác
122
55%