BỘ GIÁO DỤC VÀ ĐÀO TẠO
VIỆN HÀN LÂM KHOA HỌC
VÀ CÔNG NGHỆ VIỆT NAM
HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ
-----------------------------
VŨ VĂN HIỆU
NGHIÊN CỨU MỘT SỐ KỸ THUẬT PHÂN HẠNG TRONG
TRA CỨU ẢNH DỰA VÀO NỘI DUNG
LUẬN ÁN TIẾN SỸ TOÁN HỌC
HÀ NỘI – 2017
BỘ GIÁO DỤC VÀ ĐÀO TẠO
VIỆN HÀN LÂM KHOA HỌC
VÀ CÔNG NGHỆ VIỆT NAM
HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ
-----------------------------
VŨ VĂN HIỆU
NGHIÊN CỨU MỘT SỐ KỸ THUẬT PHÂN HẠNG
TRONG TRA CỨU ẢNH DỰA VÀO NỘI DUNG
LUẬN ÁN TIẾN SỸ TOÁN HỌC
Chuyên ngành: Cơ sở Toán học cho Tin học
Mã số: 62 46 01 10
Người hướng dẫn khoa học:
1. PGS. TS. Ngô Quốc Tạo
2. PGS.TS. Nguyễn Hữu Quỳnh
Hà Nội – 2017
LÌi cam oan
Tôi xin cam oan lu™n án “Nghiên c˘u mÎt sË kˇ thu™t phân h§ng trong
tra c˘u £nh d¸a vào nÎi dung” là công trình nghiên c˘u cıa riêng tôi. Các sË
liªu, k∏t qu£ ˜Òc trình bày trong lu™n án là hoàn toàn trung th¸c và ch˜a t¯ng
˜Òc công bË trong bßt k˝ mÎt công trình nào khác.
⌅
Tôi ã trích d®n ¶y ı các tài liªu tham kh£o, công trình nghiên c˘u liên
quan trong n˜Óc và quËc t∏. Ngo§i tr¯ các tài liªu tham kh£o này, lu™n
án hoàn toàn là công viªc cıa riêng tôi.
⌅
Trong các công trình khoa hÂc ˜Òc công bË trong lu™n án, tôi ã th∫ hiªn
rõ ràng và chính xác óng góp cıa các Áng tác gi£ và nh˙ng gì do tôi ã
óng góp.
⌅
Lu™n án ˜Òc hoàn thành trong thÌi gian tôi làm Nghiên c˘u sinh t§i Phòng
Nh™n d§ng và Công nghª tri th˘c, Viªn Công nghª thông tin, Viªn Hàn
lâm Khoa hÂc và Công nghª Viªt Nam.
Tác gi£ :
Hà NÎi :
i
LÌi c£m Ïn
Lu™n án ˜Òc th¸c hiªn d˜Ói s¸ h˜Óng d®n khoa hÂc cıa PGS.TS Ngô QuËc T§o
và PGS.TS Nguyπn H˙u Qu˝nh. Nghiên c˘u sinh xin bày t‰ lòng bi∏t Ïn sâu s≠c
∏n hai Th¶y v∑ ‡nh h˜Óng khoa hÂc, nh˙ng bài hÂc, nh˙ng góp ˛ qu˛ báu trong
nghiên c˘u. Các Th¶y ã t§o i∑u kiªn vô cùng thu™n lÒi trong suËt quá trình
nghiên c˘u cıa Nghiên c˘u sinh.
Tôi xin ˜Òc c£m Ïn các nhà khoa hÂc, tác gi£ cıa các công trình công bË ã ˜Òc
trích d®n trong lu™n án, ây là nh˙ng t˜ liªu qu˛, ki∏n th˘c liên quan quan trÂng
giúp Nghiên c˘u sinh hoàn thành lu™n án. Xin c£m Ïn ∏n các nhà khoa hÂc ã
ph£n biªn các công trình nghiên c˘u cıa Nghiên c˘u sinh.
Tôi trân trÂng c£m Ïn Phòng Nh™n d§ng và Công nghª tri th˘c, Phòng qu£n l˛
ào t§o, Viªn Công nghª thông tin, HÂc viªn Khoa hÂc và Công nghª, Viªn Hàn
lâm Khoa hÂc và Công nghª Viªt Nam ã t§o i∑u kiªn thu™n lÒi cho tôi trong
suËt quá trình nghiên c˘u th¸c hiªn lu™n án. Tôi cÙng xin c£m Ïn sâu s≠c ∏n HÎi
Áng Khoa hÂc Viªn Công nghª thông tin, các Th¶y trong HÎi Áng b£o vª cßp
cÏ s ã góp ˛ giúp Nghiên c˘u sinh hoàn thiªn công trình lu™n án này.
Tôi cÙng bày t‰ s¸ c£m Ïn sâu s≠c ∏n Khoa Công nghª thông tin, Tr˜Ìng
hÂc
§i
iªn L¸c, Hà NÎi ã t§o i∑u kiªn cho tôi ˜Òc hÂc t™p, trao Íi và nghiên
c˘u. Tôi xin c£m Ïn Tr˜Ìng
§i hÂc H£i Phòng ã t§o i∑u kiªn v∑ thÌi gian và
tài chính cho tôi th¸c hiªn lu™n án này.
MÎt ph¶n cıa nghiên c˘u này ˜Òc th¸c hiªn trong khuôn khÍ ∑ tài nghiên c˘u
mã sË CS’15.03 cıa Viªn Công nghª Thông tin, Viªn Hàn lâm Khoa hÂc và Công
nghª Viªt Nam và ∑ tài nghiên mã sË VAST01.07/15-16 cıa Viªn Hàn lâm Khoa
hÂc và Công nghª Viªt Nam. Xin c£m Ïn các trao Íi và trÒ giúp cıa các thành
viên ∑ tài.
CuËi cùng, tôi xin bày t‰ lòng bi∏t Ïn vô h§n Ëi vÓi cha mµ, vÒ con và toàn th∫
anh em trong gia ình ã luôn ıng hÎ, giúp Ô tôi.
ii
Mˆc lˆc
LÌi cam oan
i
LÌi c£m Ïn
ii
T¯ vi∏t t≠t
v
K˛ hiªu toán hÂc
vi
Danh mˆc các hình v≥
vii
Danh mˆc các b£ng bi∫u
M
xi
¶u
1
1 TÍng quan v∑ Tra c˘u £nh d¸a vào nÎi dung
1.1 MÎt sË ∞c tr˜ng £nh th˜Ìng s˚ dˆng trong tra c˘u £nh d¸a vào
nÎi dung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.1 Miêu t£ toàn cˆc . . . . . . . . . . . . . . . . . . . . . . .
1.1.2 Miêu t£ cˆc bÎ . . . . . . . . . . . . . . . . . . . . . . . .
1.2 TÍ hÒp ∞c tr˜ng trong tra c˘u £nh d¸a vào nÎi dung . . . . . . .
1.3 Chu©n hoá trong CBIR . . . . . . . . . . . . . . . . . . . . . . . .
1.3.1 Mˆc ích cıa chu©n hoá . . . . . . . . . . . . . . . . . . .
1.3.2 Chu©n hóa min-max . . . . . . . . . . . . . . . . . . . . .
1.3.3 Chu©n hóa Gauss . . . . . . . . . . . . . . . . . . . . . . .
1.4 Kho£ng trËng ng˙ nghæa . . . . . . . . . . . . . . . . . . . . . . .
1.5 Ph£n hÁi liên quan trong CBIR . . . . . . . . . . . . . . . . . . .
1.6 Hiªu chønh trÂng sË và d‡ch chuy∫n truy vßn trong CBIR s˚ dˆng
ph£n hÁi liên quan . . . . . . . . . . . . . . . . . . . . . . . . . .
1.7 Tra c˘u £nh d¸a vào nÎi dung s˚ dˆng kˇ thu™t máy hÂc . . . . .
1.7.1 Hußn luyªn và ki∫m tra . . . . . . . . . . . . . . . . . . .
1.7.2 Nhãn d˙ liªu . . . . . . . . . . . . . . . . . . . . . . . . .
1.7.3 Xây d¸ng mô hình hÂc . . . . . . . . . . . . . . . . . . . .
1.8 MÎt sË ti∏p c™n d¸a theo ph˜Ïng pháp tËi ˜u Pareto . . . . . . .
iii
8
.
.
.
.
.
.
.
.
.
.
9
9
12
13
14
14
16
16
19
21
.
.
.
.
.
.
23
27
27
28
29
33
1.9
2
3
Ph˜Ïng pháp ánh giá hiªu n´ng trong CBIR . . . . . . . . . . . . 34
∑ xußt chu©n hoá ∞c tr˜ng và hiªu chønh trÂng sË
∞c tr˜ng
2.1 Chu©n hoá ∞c tr˜ng d¸a vào phân cˆm mÌ FCM . .
2.2 Chu©n hoá kho£ng cách d¸a vào phân cˆm FCM . .
2.3 Hiªu chønh trÂng sË, d‡ch chuy∫n truy vßn . . . . . .
2.3.1 Hiªu chønh trÂng sË . . . . . . . . . . . . . . .
2.3.2 D‡ch chuy∫n truy vßn . . . . . . . . . . . . . .
2.4 Th˚ nghiªm và ánh giá các k∏t qu£ . . . . . . . . .
2.4.1 CÏ s d˙ liªu £nh . . . . . . . . . . . . . . . .
2.4.2 Trích rút bÎ ∞c tr˜ng k∏t hÒp . . . . . . . .
2.4.3 Các k∏t qu£ th¸c nghiªm và lu™n gi£i . . . . .
2.5 K∏t lu™n Ch˜Ïng 2 . . . . . . . . . . . . . . . . . . .
trong tÍ hÒp
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
37
39
45
46
51
52
54
54
55
55
68
.
.
.
.
.
.
.
.
.
.
∑ xußt kˇ thu™t Pareto front a m˘c sâu nâng cao hiªu qu£
phân lÓp £nh
3.1 MÎt sË tính chßt hình th˘c d¸a trên kˇ thu™t Pareto front a m˘c
sâu trong không gian tÍ hÒp ∞c tr˜ng . . . . . . . . . . . . . . . .
3.2 Nâng cao hiªu qu£ phân lÓp £nh . . . . . . . . . . . . . . . . . . . .
3.3 Th˚ nghiªm và ánh giá các k∏t qu£ . . . . . . . . . . . . . . . . .
3.3.1 CÏ s d˙ liªu £nh . . . . . . . . . . . . . . . . . . . . . . . .
3.3.2 Các ph˜Ïng pháp cÏ s . . . . . . . . . . . . . . . . . . . . .
3.3.3 Ph˜Ïng pháp ánh giá . . . . . . . . . . . . . . . . . . . . .
3.3.4 Các k∏t qu£ th¸c nghiªm . . . . . . . . . . . . . . . . . . . .
3.4 K∏t lu™n Ch˜Ïng 3 . . . . . . . . . . . . . . . . . . . . . . . . . . .
69
73
81
86
86
88
88
89
96
K∏t lu™n và h˜Óng phát tri∫n
97
Danh mˆc công trình
99
A MÎt sË cÏ s d˙ liªu
A.1 Corel . . . . . . .
A.2 Wang . . . . . . .
A.3 Caltech 101 . . .
A.4 Oxford Building .
ã công bË
£nh
. . .
. . .
. . .
. . .
s˚ dˆng
. . . . . .
. . . . . .
. . . . . .
. . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
B Ph¶n m∑m tra c˘u theo các ∑ xußt cıa lu™n án
iv
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
111
. 111
. 112
. 113
. 114
120
T¯ vi∏t t≠t
D§ng vi∏t t≠t D§ng ¶y
CBIR
ı
Diπn gi£i
Content based image retrie-
Tra c˘u £nh d¸a vào nÎi dung
val
FCM
Fuzzy c-means
Phân cˆm mÌ c-means
HI
Histogram Interrsection
L˜Òc Á giao
HSV
hue, saturation, value
màu s≠c, Î bão hoà màu, Î sáng
L2R
Learning to Rank
HÂc x∏p h§ng
MARS
Multimedia Analysis and Các hª thËng phân tích
Retrieval Systems
ph˜Ïng tiªn và tra c˘u
Pr
Precision
Î chính xác
Re
Recall
Î hÁi t˜ng
RF
Relevance feedback
RGB
red, green, blue
SIFT
Scale-Invariant
Ph£n hÁi liên quan
‰, xanh lá, xanh d˜Ïng
Feature
Transform
SVM
Support vector machine
v
Máy vector hÈ trÒ
a
K˛ hiªu toán hÂc
M
Î dài cıa mÎt vector ∞c tr˜ng
N Kích th˜Óc cıa cÏ s d˙ liªu £nh
T SË bÎ ∞c tr˜ng
t Chø sË bÎ ∞c tr˜ng
Q, Ii Énh truy vßn và £nh th˘ i trong cÏ s d˙ liªu
I˜i Vector ∞c tr˜ng chu©n hoá cıa £nh th˘ i
I˜it Vector ∞c tr˜ng chu©n hoá bÎ t cıa £nh th˘ i
Qt, I t
Q̃it
∞c tr˜ng bÎ t t˜Ïng ˘ng cıa £nh truy vßn Q và £nh I bßt k˝
∞c tr˜ng chu©n hoá bÎ t cıa £nh truy vßn
DQt (Ii ), D t (Q, Ii ) Kho£ng cách theo bÎ ∞c tr˜ng t cıa £nh Ii so vÓi £nh truy
vßn Q
DQ (Ii ), D(Q, Ii ) Kho£ng cách £nh Ii so vÓi £nh truy vßn Q trên bÎ ∞c tr˜ng
k∏t hÒp
top
k T™p gÁm k £nh có th˘ h§ng t˜Ïng t¸ cao nhßt Ëi vÓi £nh truy vßn
NB T™p £nh có Î t˜Ïng t¸ cao nhßt theo ∞c tr˜ng toàn cˆc trong mÎt tra
c˘u
NB
T™p £nh ˜Òc xác nh™n không liên quan ph£n hÁi cıa ng˜Ìi dùng
NB + T™p £nh ˜Òc xác nh™n liên quan ph£n hÁi cıa ng˜Ìi dùng
NBt T™p £nh có Î t˜Ïng t¸ cao nhßt theo ∞c tr˜ng bÎ t trong mÎt tra c˘u
NB ⇠ T™p £nh có th˘ h§ng Î t˜Ïng t¸ cao và thuÎc t™p NB
c˘u
vi
trong mÎt tra
NB ⇤ T™p £nh ch˜a ˜Òc tra c˘u
(D)
Vt,c
Tâm cˆm c t™p giá tr‡ kho£ng cách bÎ ∞c tr˜ng t theo FCM
Vt (D) T™p tâm cˆm theo bÎ ∞c tr˜ng t
Vt,c,j Tâm cˆm c cıa thành ph¶n ∞c tr˜ng j bÎ ∞c tr˜ng t theo phân cˆm
mÌ FCM
wt TrÂng sË kho£ng cách cıa bÎ ∞c tr˜ng t
p
⌘t,c,i
Giá tr‡ Î thuÎc cıa ph¶n t˚ th˘ i bÎ ∞c tr˜ng t so vÓi cˆm c, p là
hª sË FCM
(l),NB +
t,kIt k
Î lªch chu©n theo Î dài ∞c tr˜ng bÎ ∞c tr˜ng t trong l¶n l∞p th˘
(l),NB +
t (I )
t,DQ
i
Î lªch chu©n kho£ng cách bÎ ∞c tr˜ng t trong l¶n l∞p th˘ l Ëi vÓi
l Ëi vÓi các £nh trong t™p NB +
các £nh trong t™p NB +
t,c,i
Î lªch chu©n thành ph¶n j cıa bÎ ∞c tr˜ng t theo cˆm c
(D)
t,c
Î lªch chu©n kho£ng cách bÎ ∞c tr˜ng t theo cˆm c
vii
Danh sách hình v≥
0.1
0.2
Hª thËng tra c˘u £nh d¸a vào nÎi dung. . . . . . . . . . . . . . . .
Hª thËng ∑ xußt . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1
1.2
1.3
Thành ph¶n th˘ nhßt cıa ∞c tr˜ng mô men màu. . . . . . . . . . 15
Phân bË d˙ liªu thành ph¶n 1 cıa ∞c tr˜ng mô men màu (gËc) . . 18
(a) Phân bË d˙ liªu thành ph¶n 5 l˜Òc Á ∞c tr˜ng l˜Òc Á HSV
(gËc). (b) L˜Òc Á ∞c tr˜ng l˜Òc Á HSV chu©n hoá theo lu™t 3
thành ph¶n th˘ 5, 97.4555% d˙ liªu “rÏi vào” [-1,1] . . . . . . . . . 18
1.4
1.5
1.6
Énh truy vßn “mandolin image 0001.jpg”. . . . . . . . . . . . . .
Hª thËng tra c˘u vÓi £nh truy vßn “mandolin image 0001.jpg”. . .
K∏t qu£ top 20 các £nh t˜Ïng t¸ nhßt vÓi £nh truy vßn l¶n tra
c˘u khi t§o. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Hai £nh có ng˙ nghæa t˜Ïng Áng . . . . . . . . . . . . . . . . . .
L˜Òc Á màu cıa £nh truy vßn và hai £nh trong k∏t qu£ top 20.
Minh ho§ siêu phØng . . . . . . . . . . . . . . . . . . . . . . . . .
1.7
1.8
1.9
2.1
2.2
2.3
2.4
2.5
2.6
2.7
Mô hình hª thËng ∑ xußt . . . . . . . . . . . . . . . . . . . . . .
Minh ho§ chu©n hóa 3
FCM . . . . . . . . . . . . . . . . . . .
Minh ho§ tính chßt b£o toàn th˘ t¸ cıa chu©n hoá 3
FCM . .
Phân bË d˙ liªu gËc thành ph¶n th˘ n´m cıa các ∞c tr˜ng (a)
L˜Òc Á màu HSV, (b) l˜Òc Á t¸ t˜Ïng quan màu, (c) mô men
màu, (d) k∏t cßu Gabor, (e) mô men Wavelet, (f) GIST . . . . . .
(a) Phân bË d˙ liªu ∞c tr˜ng l˜Òc Á HSV (chu©n hoá 3 ) thành
ph¶n 5 gÁm 97.45% thuÎc [-1,1]. (b) Phân bË d˙ liªu ∞c tr˜ng l˜Òc
Á HSV (chu©n hoá 3
FCM ) thành ph¶n 5 gÁm 99.81% thuÎc
[-1,1] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
(a) Phân bË d˙ liªu ∞c tr˜ng autoCorrelogram (chu©n hoá 3 )
thành ph¶n 5 gÁm 98.02% thuÎc [-1,1]. (b) Phân bË d˙ liªu ∞c
tr˜ng autoCorrelogram (chu©n hoá 3
FCM ) thành ph¶n 5 gÁm
99.9955% thuÎc [-1,1] . . . . . . . . . . . . . . . . . . . . . . . . .
(a) Phân bË d˙ liªu ∞c tr˜ng mô men màu (chu©n hoá 3 ) thành
ph¶n 5 gÁm 99.68% thuÎc [-1,1]. (b) Phân bË d˙ liªu ∞c tr˜ng mô
men màu (chu©n hoá 3
FCM ) thành ph¶n 5 gÁm 100% thuÎc
[-1,1] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
viii
3
6
. 19
. 19
.
.
.
.
20
20
21
32
. 38
. 42
. 43
. 56
. 57
. 57
. 58
2.8
2.9
2.10
2.11
2.12
2.13
2.14
2.15
(a) Phân bË d˙ liªu ∞c tr˜ng k∏t cßu Gabor(chu©n hoá 3 ) thành
ph¶n 5 gÁm 98.1% thuÎc [-1,1]. (b) Phân bË d˙ liªu ∞c tr˜ng k∏t
cßu Gabor (chu©n hoá 3
FCM ) thành ph¶n 5 gÁm 99.95% thuÎc
[-1,1] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
(a) Phân bË d˙ liªu ∞c tr˜ng bßt bi∏n Wavelet(chu©n hoá 3 )
thành ph¶n 5 gÁm 99.5% thuÎc [-1,1]. (b) Phân bË d˙ liªu ∞c
tr˜ng bßt bi∏n Wavelet (chu©n hoá 3
FCM ) thành ph¶n 5 gÁm
100% thuÎc [-1,1] . . . . . . . . . . . . . . . . . . . . . . . . . . .
(a) Phân bË d˙ liªu ∞c tr˜ng hình d§ng GIST (chu©n hoá 3 )
thành ph¶n 5 gÁm 98.8% thuÎc [-1,1]. (b) Phân bË d˙ liªu ∞c
tr˜ng hình d§ng GIST (chu©n hoá 3
FCM ) thành ph¶n 5 gÁm
99.9985% thuÎc [-1,1] . . . . . . . . . . . . . . . . . . . . . . . . .
So sánh chßt l˜Òng truy vßn. (a) Hiªu n´ng Precision/Recall. (b)
Hiªu n´ng Î chính xác. . . . . . . . . . . . . . . . . . . . . . . .
Trung bình Î chính xác cıa kˇ thu™t ∑ xußt trên top k k∏t qu£
theo n´m vòng cıa ph£n hÁi liên quan . . . . . . . . . . . . . . .
So sánh trung bình Î chính xác cıa kˇ thu™t ∑ xußt và PowerTool
trên các top k k∏t qu£. . . . . . . . . . . . . . . . . . . . . . . .
So sánh trung bình Î chính xác cıa kˇ thu™t ∑ xußt và PowerTool
trên top 20 k∏t qu£ theo m˜Ìi vòng cıa ph£n hÁi liên quan . . .
Bi∫u Á Precision và Recall cıa kˇ thu™t ∑ xußt và PowerTool .
3.1
3.2
3.3
3.4
3.5
Hª thËng ∑ xußt . . . . . . . . . . . . . . . . . . . . . . . . . . .
Minh ho§ không gian tìm ki∏m EQ . . . . . . . . . . . . . . . . .
MÎt miêu t£ Pareto front . . . . . . . . . . . . . . . . . . . . . . .
Minh ho§ hai m˘c Î sâu là PF 1 và PF 2 cıa không gian EQ . . .
Trung bình Î chính xác (Precision) trên k∏t qu£ top k cıa ∑
xußt Pareto-AdaBoost trên ba t™p d˙ liªu theo n´m vòng ph£n hÁi
liên quan. (a) Db1. (b) Db2. (c) Db3. . . . . . . . . . . . . . . . .
3.6 Trung bình Î chính xác (Precision) trên k∏t qu£ top k cıa ∑
xußt Pareto-SVM trên ba t™p d˙ liªu theo n´m vòng ph£n hÁi liên
quan. (a) Db1. (b) Db2. (c) Db3. . . . . . . . . . . . . . . . . . .
3.7 So sánh Î chính xác trên các k∏t qu£ top k cıa kˇ thu™t ∑ xußt
Pareto-AdaBoost vÓi các kˇ thu™t cÏ s trên ba t™p d˙ liªu. (a) T™p
d˙ liªu Db1. (b) T™p d˙ liªu Db2. (c) T™p d˙ liªu Db3. . . . . . .
3.8 So sánh Î chính xác trên các k∏t qu£ top k cıa kˇ thu™t ∑ xußt
Pareto-SVM vÓi các kˇ thu™t cÏ s trên ba t™p d˙ liªu. (a) T™p d˙
liªu Db1. (b) T™p d˙ liªu Db2. (c) T™p d˙ liªu Db3. . . . . . . . .
3.9
Á th‡ Î chính xác (Precision) và hÁi t˜ng (Recall) cıa các ph˜Ïng
pháp Pareto-AdaBoost, SVM, AdaBoost và MARS trên t™p d˙ liªu.
(a) T™p d˙ liªu Db1. (b) T™p d˙ liªu Db2. (c) T™p d˙ liªu Db3. .
3.10 Á th‡ Î chính xác (Precision) và hÁi t˜ng (Recall) cıa các ph˜Ïng
pháp Pareto-SVM, SVM, AdaBoost và MARS trên t™p d˙ liªu Db1,
Db2 và Db3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. 58
. 59
. 59
. 60
. 63
. 64
. 66
. 67
.
.
.
.
72
74
76
78
. 91
. 92
. 94
. 94
. 95
. 95
A.1 Các £nh ví dˆ t¯ cÏ s d˙ liªu Corel . . . . . . . . . . . . . . . . . 112
ix
A.2 MÎt £nh m®u t¯ mÈi lÓp cıa 10 lÓp cıa cÏ s d˙ liªu Wang . . .
A.3 MÈi m®u cho mÎt chı ∑ trong sË 101 chı ∑ trong cÏ s d˙ liªu
£nh Caltech 101 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.4 Các m®u cıa cÏ s d˙ liªu Wang, các chı ∑ ng˙ nghæa : bi∫n, Châu
Phi, hoa hÁng, khıng long, ng¸a, núi, th˘c ´n, di tích, voi, xe bu˛t.
MÈi dòng mÎt chı ∑, ví dˆ mÈi chı ∑ 5 £nh t˜Ïng ˘ng t¯ trên
xuËng d˜Ói. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.5 Toàn bÎ 55 £nh truy vßn ˜Òc s˚ dˆng trong ánh giá ground truth.
MÈi dòng cho bi∏t các truy vßn khác nhau cho cùng c£nh ‡a danh.
L˜u ˛ s¸ thay Íi lÓn v∑ ph§m vi cıa các vùng truy vßn và thay
Íi v‡ trí, ánh sáng, v.v cıa chính các £nh. . . . . . . . . . . . . .
B.1
B.2
B.3
B.4
B.5
B.6
B.7
B.8
B.9
B.10
B.11
˜a mÎt £nh vào hª thËng tra c˘u ∑ xußt. . . .
K∏t qu£ tra c˘u khi t§o cıa top 20 . . . . . .
K∏t qu£ tra c˘u top 20 vòng ph£n hÁi th˘ nhßt
K∏t qu£ tra c˘u top 20 vòng ph£n hÁi th˘ hai .
K∏t qu£ tra c˘u top 20 vòng ph£n hÁi th˘ ba .
˜a vào hª thËng mÎt truy vßn . . . . . . . . . .
K∏t qu£ tra c˘u khi t§o top 20. . . . . . . . .
K∏t qu£ tra c˘u top 20 vòng ph£n hÁi th˘ nhßt
K∏t qu£ tra c˘u top 20 vòng ph£n hÁi th˘ hai .
K∏t qu£ tra c˘u top 20 vòng ph£n hÁi th˘ ba .
K∏t qu£ tra c˘u top 20 vòng ph£n hÁi th˘ t˜ .
x
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. 113
. 117
. 118
. 119
.
.
.
.
.
.
.
.
.
.
.
120
121
121
122
122
123
123
124
124
124
125
Danh sách b£ng
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
2.9
2.10
2.11
3.1
3.2
3.3
3.4
3.5
3.6
3.7
B£ng mÎt sË £nh theo nh™n ‡nh chı quan cıa ng˜Ìi dùng so sánh
v∑ t˜Ïng t¸ ng˙ nghæa vÓi truy vßn Q = 710.jpg. Các £nh n¨m trong
t™p Wang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Î o kho£ng cách cıa £nh truy vßn 710.jpg Ëi vÓi các £nh t™p
NB + , NB và NB ⇠ . K˛ hiªu các cÎt (d1), (d2), (d3), (d4), (d5),
(d6) là kho£ng cách t˜Ïng ˘ng cıa các bÎ ∞c tr˜ng l˜Òc Á màu
HSV, t¸ t˜Ïng quan màu, mô men màu, k∏t cßu Gabor, mô men
Wavelet và GIST theo các hàm kho£ng cách ; D là kho£ng cách
toàn bÎ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Î o kho£ng cách L2 cıa £nh truy vßn 710.jpg Ëi vÓi các £nh
trong t™p NB + , NB và NB ⇠ . . . . . . . . . . . . . . . . . . . . .
Các miêu t£ £nh và hàm kho£ng cách s˚ dˆng trong th¸c nghiªm. .
Tham sË phân cˆm FCM . . . . . . . . . . . . . . . . . . . . . . . .
Các Ëi t˜Òng cıa t™p AGRt trên sáu l¶n l∞p ph£n hÁi Ëi vÓi £nh
truy vßn Q = 710.jpg . . . . . . . . . . . . . . . . . . . . . . . . . .
ThËng kê trÂng sË kho£ng cách t¯ng bÎ ∞c tr˜ng wt theo mÈi l¶n
l∞p Ëi vÓi mÎt sË £nh truy vßn . . . . . . . . . . . . . . . . . . . .
Trung bình Î chính xác (Precision) top k k∏t qu£ trên 10 vòng
ph£n hÁi liên quan Ëi vÓi t™p d˙ liªu Wang cıa kˇ thu™t ∑ xußt .
Trung bình Î hÁi t˜ng (Recall) top k k∏t qu£ trên 10 vòng ph£n
hÁi liên quan Ëi vÓi t™p d˙ liªu Wang cıa kˇ thu™t ∑ xußt . . . .
Trung bình Î chính xác (Precision) top k k∏t qu£ trên 10 vòng
ph£n hÁi liên quan Ëi vÓi t™p d˙ liªu Wang cıa PowerTool (MARS)
Trung bình Î hÁi t˜ng (Recall) top k k∏t qu£ trên 10 vòng ph£n
hÁi liên quan Ëi vÓi t™p d˙ liªu Wang cıa PowerTool (MARS) . .
Kho£ng cách gi˙a Q và o1 , o2 , o3 trong các ∞c tr˜ng màu s≠c và
k∏t cßu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Các miêu t£ £nh và hàm kho£ng cách s˚ dˆng trong th¸c nghiªm.
Các tham sË s˚ dˆng trong th¸c nghiªm. . . . . . . . . . . . . . .
SË ˘ng viên Pareto theo top k Ëi vÓi Db1 . . . . . . . . . . . .
SË ˘ng viên Pareto theo top k Ëi vÓi Db2 . . . . . . . . . . . .
SË ˘ng viên Pareto theo top k Ëi vÓi Db3 . . . . . . . . . . . .
Trung bình Î chính xác top
k k∏t qu£ cıa ∑ xußt ParetoAdaBoost trên n´m vòng ph£n hÁi liên quan Ëi vÓi t™p d˙ liªu
Db1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
xi
.
.
.
.
.
.
48
49
50
50
55
60
61
63
64
65
65
70
87
89
90
90
91
. 91
3.8
Trung bình Î chính xác top
k k∏t qu£ cıa ∑ xußt ParetoAdaBoost trên n´m vòng ph£n hÁi liên quan Ëi vÓi t™p d˙ liªu
Db2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.9 Trung bình Î chính xác top
k k∏t qu£ cıa ∑ xußt ParetoAdaBoost trên n´m vòng ph£n hÁi liên quan Ëi vÓi t™p d˙ liªu
Db3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.10 Trung bình Î chính xác top k k∏t qu£ cıa ∑ xußt Pareto-SVM
trên n´m vòng ph£n hÁi liên quan Ëi vÓi t™p d˙ liªu Db1 . . . .
3.11 Trung bình Î chính xác top k k∏t qu£ cıa ∑ xußt Pareto-SVM
trên n´m vòng ph£n hÁi liên quan Ëi vÓi t™p d˙ liªu Db2 . . . .
3.12 Trung bình Î chính xác top k k∏t qu£ cıa ∑ xußt Pareto-SVM
trên n´m vòng ph£n hÁi liên quan Ëi vÓi t™p d˙ liªu Db3 . . . .
. 92
. 92
. 93
. 93
. 93
A.1 Danh sách 10 chı ∑ cıa cÏ s d˙ liªu Wang . . . . . . . . . . . . . 114
A.2 Danh sách 101 chı ∑ cıa cÏ s d˙ liªu Caltech 101 . . . . . . . . . 115
A.3 Danh sách 17 chı ∑ cıa cÏ s d˙ liªu Oxford Buildings . . . . . . . 116
xii
M
¶u
Tính cßp thi∏t cıa
∑ tài
S¸ phát tri∫n m§nh m≥ cıa Internet cho phép dπ dàng xây d¸ng, l˜u tr˙ các
cÏ s d˙ liªu lÓn. MÎt trong sË ó là Flickr 1 , YouTube 2 , Facebook 3 , Twitter 4 và
toàn bÎ m§ng Internet. Yêu c¶u khai thác mÎt cách hiªu qu£ d˙ liªu a ph˜Ïng
tiªn trên thúc ©y s¸ quan tâm cıa cÎng Áng nghiên c˘u [21]. Nhi∑u hª thËng
tìm ki∏m thông tin v´n b£n và £nh nh˜ Google 5 , Bing 6 , Yahoo 7 ã ˜Òc phát
tri∫n m§nh m≥ trong nh˙ng n´m g¶n ây nh˜ng v®n ch˜a áp ˘ng ˜Òc nhu c¶u
ng˜Ìi dùng. S¸ phát tri∫n m§nh m≥ cıa d˙ liªu a ph˜Ïng tiªn ngày càng tr
thành mÎt thách th˘c lÓn. Khi kích th˜Óc cıa kho £nh rßt lÓn cách ti∏p c™n tra
c˘u b¨ng t¯ khóa tr nên không kh£ thi d®n tÓi các nghiên c˘u khai thác tra c˘u
d¸a trên nÎi dung d˙ liªu £nh.
Tra c˘u £nh d¸a vào nÎi dung (Content-based image retrieval) hay gÂi t≠t là
CBIR ˜Òc giÓi thiªu bi các nghiên c˘u t¯ nh˙ng n´m 1980. CBIR ã ˜Òc ã
˜Òc nghiên c˘u rÎng rãi, nhi∑u ph˜Ïng pháp và hª thËng ã ˜Òc phát tri∫n ∫
trích rút nÎi dung cıa £nh b¨ng cách s˚ dˆng các ∞c tr˜ng m˘c thßp . D˙ liªu
trong CBIR ˜Òc lßy trên cÏ s các nÎi dung mà nó trích rút b¨ng cách s˚ dˆng
1.
2.
3.
4.
5.
6.
7.
https://www.flickr.com/
https://www.youtube.com
https://www.facebook.com/
https://twitter.com/
http://www.google.com
https://www.bing.com/
https://vn.yahoo.com/?p=us
1
2
các kˇ thu™t trích rút ∞c tr˜ng m˘c thßp bên trong cıa mÈi £nh (màu s≠c, hình
d§ng, k∏t cßu, vv).
Tuy CBIR có nhi∑u ti∏n bÎ song ng˜Ìi dùng v®n g∞p khó kh´n trong viªc
tìm ki∏m thông tin liên quan t¯ t™p d˙ liªu £nh lÓn không Áng nhßt v∑ m∞t nÎi
dung và ng˙ nghæa.
i∑u này d®n ∏n k∏t qu£ tìm ki∏m ch˜a §t ˜Òc nh˜ mong
muËn. Thông tin mà máy tính hi∫u nÎi dung £nh th˜Ìng là các giá tr‡ i∫m £nh,
vector ∞c tr˜ng ˜Òc trích rút theo các thı tˆc,... còn con ng˜Ìi hi∫u v∑ nÎi dung
cıa £nh th˜Ìng là các khái niªm ng˙ nghæa. Do không có s¸ t˜Ïng quan mÎt cách
chính xác gi˙a nÎi dung mà máy tính có ˜Òc thông qua ∞c tr˜ng tr¸c quan m˘c
thßp vÓi nÎi dung mà con ng˜Ìi hi∫u thông qua các khái niªm ng˙ nghæa m˘c
cao d®n ∏n kho£ng trËng ng˙ nghæa. Kho£ng trËng ng˙ nghæa ‡nh nghæa theo
Smeulders và cÎng s¸ [94] nh˜ sau :
“Kho£ng trËng ng˙ nghæa là s¸ không t˜Ïng Áng gi˙a thông tin £nh, ˜Òc
trích rút t¯ d˙ liªu tr¸c quan so vÓi diπn gi£i v∑ d˙ liªu £nh ó bi ng˜Ìi dùng
trong tình huËng cˆ th∫ ”.
Kho£ng trËng ng˙ nghæa n¨m gi˙a các ∞c tr˜ng tr¸c quan m˘c thßp cıa các
£nh và các ng˙ nghæa m˘c cao mong muËn d¸ ‡nh suy ra t¯ các ∞c tr˜ng tr¸c
quan m˘c thßp. Nhi∑u nghiên c˘u trong lænh v¸c CBIR ∏n nay v®n ang cË g≠ng
thu hµp kho£ng trËng ng˙ nghæa này. Cˆ th∫, hÏn ba th™p kø qua nhi∑u hª thËng
CBIR ã ˜Òc phát tri∫n, bao gÁm QBIC [28], Photobook [80], MARS [79], [83],
[90], PicHunter [17], VisualSEEK [96], Blobworld [11], MindReader [46], SIMPLIcity [110], FIRE [23], và các nghiên c˘u khác [12], [41], [60], [115], [124].
Mˆc tiêu, ph§m vi nghiên c˘u cıa lu™n án
Thông th˜Ìng mÎt hª thËng tra c˘u £nh d¸a vào nÎi dung ˜Òc miêu t£ nh˜
Hình 0.1 [62]. Các nÎi dung tr¸c quan cıa các £nh trong cÏ s d˙ liªu ˜Òc trích
rút và miêu t£ bi các vector ∞c tr˜ng nhi∑u chi∑u. Các vector ∞c tr˜ng cıa các
3
£nh trong cÏ s d˙ liªu t§o nên mÎt cÏ s d˙ liªu ∞c tr˜ng.
∫ tra c˘u các £nh,
thông tin truy vßn cıa ng˜Ìi dùng ˜a vào hª thËng tra c˘u có th∫ là các £nh
m®u ho∞c v≥ phác th£o. Hª thËng sau ó s≥ bi∏n Íi nh˙ng m®u này t˜Ïng ˘ng
vÓi bi∫u diπn cıa các vector ∞c tr˜ng. Các Î t˜Ïng t¸ ho∞c các kho£ng cách gi˙a
các vector ∞c tr˜ng cıa £nh truy vßn vÓi các £nh trong cÏ s d˙ liªu ˜Òc tính
và tra c˘u ˜Òc th¸c hiªn d¸a trên mÎt l˜Òc Á chø sË. L˜Òc Á chø sË ˜a ra mÎt
cách hiªu qu£ ∫ tìm ki∏m các £nh trong cÏ s d˙ liªu. Qua kh£o sát nhi∑u nhiên
Hình 0.1. Hª thËng tra c˘u £nh d¸a vào nÎi dung.
c˘u CBIR, s¸ k∏t hÒp a ∞c tr˜ng ch˜a ˜Òc xem xét mÎt cách ¶y ı d®n ∏n
viªc so sánh Î t˜Ïng t¸ §t hiªu qu£ ch˜a cao. Trong hª thËng này ánh chø sË
và tra c˘u s˚ dˆng k∏t hÒp a ∞c tr˜ng cÙng c¶n ˜Òc nghiên c˘u ∫ nâng cao
hiªu qu£ tra c˘u.
∫ nâng cao k∏t qu£ tra c˘u chính xác ¶u ra, lu™n án ˜a ra
các mˆc tiêu và giÓi h§n ph§m vi nghiên c˘u nh˜ sau.
Mˆc tiêu cıa lu™n án
So sánh Î t˜Ïng t¸ : Nghiên c˘u và ∑ xußt chu©n hoá ∞c tr˜ng, chu©n hoá
kho£ng cách ∫ nâng cao hiªu qu£ so sánh Î t˜Ïng t¸.
Ph£n hÁi liên quan : Nghiên c˘u và ∑ xußt kˇ thu™t hiªu chønh trÂng sË và
d‡ch chuy∫n truy vßn.
4
ánh chø sË và tra c˘u : Tßt c£ các £nh trong cÏ s d˙ liªu vector ∞c tr˜ng
˜Òc tính toán tr˜Óc và l˜u tr˙ trong hª qu£n tr‡ cÏ s d˙ liªu. Rút gÂn không
gian tìm ki∏m s˚ dˆng ti∏p c™n tËi ˜u Pareto ∫ l¸a chÂn t™p ˘ng viên tËt nhßt
t¯ cÏ s d˙ liªu. Tra c˘u ˜a ra “top” k∏t qu£ các £nh có kho£ng cách cıa vector
∞c tr˜ng nh‰ nhßt ho∞c ˜Òc d¸ báo x∏p h§ng cao nhßt vÓi £nh truy vßn.
Ph§m vi nghiên c˘u cıa lu™n án
S˚ dˆng mÎt sË t™p £nh chu©n ˜Òc s˚ dˆng nhi∑u trong các nghiên c˘u v∑
CBIR. Xây d¸ng cÏ s d˙ liªu ∞c tr˜ng d¸a trên mÎt sË ph˜Ïng pháp trích rút
∞c tr˜ng tËt ã có. Cài ∞t th¸c nghiªm cho các ∑ xußt. So sánh và ánh giá
hiªu n´ng v∑ m∞t Î chính xác thông qua t™p k∏t qu£ tra c˘u.
Ph˜Ïng pháp và nÎi dung nghiên c˘u
Ph˜Ïng pháp nghiên c˘u là k∏t hÒp gi˙a nghiên c˘u l˛ thuy∏t và th¸c nghiªm.
CÏ s d˙ liªu và thông tin khoa hÂc ˜Òc thu th™p, tÍng hÒp t¯ các t§p chí khoa
hÂc chuyên ngành trong và ngoài n˜Óc, qua Xêmina ho∞c tham gia báo cáo t§i các
hÎi th£o khoa hÂc, qua trao Íi vÓi th¶y h˜Óng d®n và các Áng nghiªp cùng lænh
v¸c nghiên c˘u,...
Lu™n án tÍng hÒp các thông tin liên quan trong lænh v¸c CBIR, l¸a chÂn các
cách ti∏p c™n ã ˜Òc áp dˆng thành công, ti∏n hành th˚ nghiªm vÓi các t™p d˙
liªu £nh chu©n trong các bài báo khoa hÂc và ánh giá k∏t qu£.
NÎi dung nghiên c˘u trong lu™n án gÁm :
(1) Nghiên c˘u tÍng quan v∑ tra c˘u £nh d¸a vào nÎi dung.
(2) Nghiên c˘u cách k∏t hÒp nhi∑u ∞c tr˜ng trong hª thËng CBIR t¯ ó phát
hiªn các quy lu™t, ràng buÎc cÏ b£n cıa k∏t hÒp nhi∑u ∞c tr˜ng.
5
(3) Nghiên c˘u mÎt sË kˇ thu™t gi£m kho£ng trËng ng˙ nghæa trong CBIR.
K∏t qu£ §t ˜Òc cıa lu™n án
Lu™n án ã có nh˙ng óng góp chính nh˜ sau :
∑ xußt chu©n hoá c£i ti∏n phù hÒp vÓi d˙ liªu th¸c t∏ trong tra c˘u £nh d¸a
vào nÎi dung, cho phép nâng cao hiªu qu£ Ëi sánh Î t˜Ïng t¸ d¸a vào ∞c tr˜ng
m˘c thßp cıa các £nh trong hª thËng tra c˘u trong công trình [CT6].
∑ xußt kˇ thu™t hiªu chønh trÂng sË Î t˜Ïng t¸ và d‡ch chuy∫n truy vßn
d¸a vào thông tin ph£n hÁi cıa ng˜Ìi dùng trong công trình [CT6].
∑ xußt s˚ dˆng tËi ˜u Pareto xây d¸ng t™p ˘ng viên ∫ nâng cao Î chính
xác cıa hª thËng CBIR trên không gian k∏t hÒp a ∞c tr˜ng trong công trình
[CT7].
Mô hình tÍng quát cho các ∑ xußt cıa lu™n án trong Hình 0.2 ˜Òc mô t£
nh˜ sau :
(1)
∞c tr˜ng £nh cıa truy vßn và các ∞c tr˜ng £nh cıa các £nh cÏ s d˙
liªu ˜Òc chu©n hoá theo ∑ xußt chu©n hoá ∞c tr˜ng.
(2)
Î t˜Ïng t¸ cıa các £nh trong cÏ s d˙ liªu vÓi £nh truy vßn ˜Òc tính
toán d¸a vào các vector ∞c tr˜ng ã ˜Òc chu©n hoá. Các £nh ˜Òc x∏p h§ng
theo Î t˜Ïng t¸ gi£m d¶n. T™p £nh k∏t qu£ hi∫n th‡ top
k (t™p gÁm k £nh có
th˘ h§ng t˜Ïng t¸ cao nhßt Ëi vÓi £nh truy vßn). Trên k∏t qu£ top
dùng ánh giá m˘c Î liên quan theo nh™n th˘c.
k ng˜Ìi
ây là ¶u vào cıa ∑ xußt hiªu
chønh trÂng sË và d‡ch chuy∫n truy vßn, k∏t qu£ ¶u ra là t™p các trÂng sË cho
mÈi bÎ ∞c tr˜ng.
(3)
Î t˜Ïng t¸ các £nh trong cÏ s d˙ liªu so vÓi £nh truy vßn ˜Òc tính l§i
d¸a vào hàm kho£ng cách k∏t hÒp bÎ trÂng sË v¯a thu ˜Òc.
6
Hình 0.2. Hª thËng ∑ xußt
(4) Xây d¸ng t™p ˘ng viên Pareto ∫ gi£m không gian tìm ki∏m.
(5) T™p hußn luyªn là các £nh ˜Òc ánh giá trong t™p k∏t qu£ top
k . T™p
ki∫m tra là t™p ˘ng viên Pareto.
(6) Tìm hàm phân lÓp d¸a vào thông tin ¶u vào là t™p hußn luyªn và t™p
ki∫m tra b¨ng mÎt máy phân lÓp.
(7) S≠p x∏p các £nh trong t™p ki∫m tra theo giá tr‡ d¸ báo phân lÓp. T™p k∏t
qu£ hi∫n th‡ gÁm top
k £nh có th˘ h§ng giá tr‡ d¸ báo phân lÓp cao nhßt.
(8) Ph£n hÁi liên quan : S˚ dˆng thông tin ánh giá cıa ng˜Ìi dùng liên quan
ho∞c không liên quan trên t™p k∏t qu£ top
k . D¸a trên các £nh ˜Òc ánh giá,
- Xem thêm -