Tiến Sĩ 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Ì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 :
iLÌ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 §i
hÂc 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.
iiMˆ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 xi
M ¶u 1
1 TÍng quan v∑ Tra c˘u £nh d¸a vào nÎi dung 8
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 . 9
1.1.1 Miêu t£ toàn cˆc 9
1.1.2 Miêu t£ cˆc bÎ . 12
1.2 TÍ hÒp ∞c tr˜ng trong tra c˘u £nh d¸a vào nÎi dung 13
1.3 Chu©n hoá trong CBIR . 14
1.3.1 Mˆc ích cıa chu©n hoá 14
1.3.2 Chu©n hóa min-max 16
1.3.3 Chu©n hóa Gauss 16
1.4 Kho£ng trËng ng˙ nghæa 19
1.5 Ph£n hÁi liên quan trong CBIR 21
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 . 23
1.7 Tra c˘u £nh d¸a vào nÎi dung s˚ dˆng kˇ thu™t máy hÂc 27
1.7.1 Hußn luyªn và ki∫m tra 27
1.7.2 Nhãn d˙ liªu 28
1.7.3 Xây d¸ng mô hình hÂc . 29
1.8 MÎt sË ti∏p c™n d¸a theo ph˜Ïng pháp tËi ˜u Pareto 33
iii1.9 Ph˜Ïng pháp ánh giá hiªu n´ng trong CBIR 34
2 ∑ xußt chu©n hoá ∞c tr˜ng và hiªu chønh trÂng sË trong tÍ hÒp
∞c tr˜ng 37
2.1 Chu©n hoá ∞c tr˜ng d¸a vào phân cˆm mÌ FCM 39
2.2 Chu©n hoá kho£ng cách d¸a vào phân cˆm FCM 45
2.3 Hiªu chønh trÂng sË, d‡ch chuy∫n truy vßn 46
2.3.1 Hiªu chønh trÂng sË . 51
2.3.2 D‡ch chuy∫n truy vßn 52
2.4 Th˚ nghiªm và ánh giá các k∏t qu£ . 54
2.4.1 CÏ s d˙ liªu £nh 54
2.4.2 Trích rút bÎ ∞c tr˜ng k∏t hÒp 55
2.4.3 Các k∏t qu£ th¸c nghiªm và lu™n gi£i . 55
2.5 K∏t lu™n Ch˜Ïng 2 . 68
3 ∑ xußt kˇ thu™t Pareto front a m˘c sâu nâng cao hiªu qu£
phân lÓp £nh 69
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 73
3.2 Nâng cao hiªu qu£ phân lÓp £nh 81
3.3 Th˚ nghiªm và ánh giá các k∏t qu£ . 86
3.3.1 CÏ s d˙ liªu £nh 86
3.3.2 Các ph˜Ïng pháp cÏ s . 88
3.3.3 Ph˜Ïng pháp ánh giá . 88
3.3.4 Các k∏t qu£ th¸c nghiªm 89
3.4 K∏t lu™n Ch˜Ïng 3 . 96
K∏t lu™n và h˜Óng phát tri∫n 97
Danh mˆc công trình ã công bË 99
A MÎt sË cÏ s d˙ liªu £nh s˚ dˆng 111
A.1 Corel . 111
A.2 Wang . 112
A.3 Caltech 101 . 113
A.4 Oxford Building . 114
B Ph¶n m∑m tra c˘u theo các ∑ xußt cıa lu™n án 120
ivT¯ vi∏t t≠t
D§ng vi∏t t≠t D§ng ¶y ı Diπn gi£i
CBIR Content based image retrie-
val
Tra c˘u £nh d¸a vào nÎi dung
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
Retrieval Systems
Các hª thËng phân tích a
ph˜Ïng tiªn và tra c˘u
Pr Precision Î chính xác
Re Recall Î hÁi t˜ng
RF Relevance feedback Ph£n hÁi liên quan
RGB red, green, blue ‰, xanh lá, xanh d˜Ïng
SIFT Scale-Invariant Feature
Transform
SVM Support vector machine Máy vector hÈ trÒ
vK˛ 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, I i É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 t
i
Vector ∞c tr˜ng chu©n hoá  bÎ t cıa £nh th˘ i
Q t , I t ∞c tr˜ng bÎ t t˜Ïng ˘ng cıa £nh truy vßn Q và £nh I bßt k˝
˜
Q t
i
∞c tr˜ng chu©n hoá  bÎ t cıa £nh truy vßn
D t
Q
(I i ), D t (Q, I i ) Kho£ng cách theo bÎ ∞c tr˜ng t cıa £nh I i so vÓi £nh truy
vßn Q
D Q (I i ), D(Q, I i ) Kho£ng cách £nh I i 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
NB t 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 trong mÎt tra
c˘u
viNB⇤ T™p £nh ch˜a ˜Òc tra c˘u
V
(D)
t,c Tâm cˆm c t™p giá tr‡ kho£ng cách bÎ ∞c tr˜ng t theo FCM
V t (D) T™p tâm cˆm theo bÎ ∞c tr˜ng t
V t,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
w t 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, k It k
Î lªch chu©n theo Î dài ∞c tr˜ng bÎ ∞c tr˜ng t trong l¶n l∞p th˘
l Ëi vÓi các £nh trong t™p NB +

(l),NB+
t,Dt
Q
(Ii )
Î lªch chu©n kho£ng cách bÎ ∞c tr˜ng t trong l¶n l∞p th˘ l Ëi vÓi
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
viiDanh sách hình v≥
0.1 Hª thËng tra c˘u £nh d¸a vào nÎi dung 3
0.2 Hª thËng ∑ xußt 6
1.1 Thành ph¶n th˘ nhßt cıa ∞c tr˜ng mô men màu 15
1.2 Phân bË d˙ liªu thành ph¶n 1 cıa ∞c tr˜ng mô men màu (gËc) 18
1.3 (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 Énh truy vßn “mandolin image 0001.jpg” . 19
1.5 Hª thËng tra c˘u vÓi £nh truy vßn “mandolin image 0001.jpg” 19
1.6 K∏t qu£ top 20 các £nh t˜Ïng t¸ nhßt vÓi £nh truy vßn  l¶n tra
c˘u khi t§o . 20
1.7 Hai £nh có ng˙ nghæa t˜Ïng Áng . 20
1.8 L˜Òc Á màu cıa £nh truy vßn và hai £nh trong k∏t qu£ top 20 21
1.9 Minh ho§ siêu phØng 32
2.1 Mô hình hª thËng ∑ xußt . 38
2.2 Minh ho§ chu©n hóa 3 FCM 42
2.3 Minh ho§ tính chßt b£o toàn th˘ t¸ cıa chu©n hoá 3 FCM . 43
2.4 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 . 56
2.5 (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] . 57
2.6 (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] 57
2.7 (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] . 58
viii2.8 (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] . 58
2.9 (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] 59
2.10 (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] 59
2.11 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 . 60
2.12 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 63
2.13 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£ . 64
2.14 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 66
2.15 Bi∫u Á Precision và Recall cıa kˇ thu™t ∑ xußt và PowerTool 67
3.1 Hª thËng ∑ xußt 72
3.2 Minh ho§ không gian tìm ki∏m E Q 74
3.3 MÎt miêu t£ Pareto front 76
3.4 Minh ho§ hai m˘c Î sâu là PF 1 và PF 2 cıa không gian E Q 78
3.5 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 91
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 92
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 94
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 94
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 . 95
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 95
A.1 Các £nh ví dˆ t¯ cÏ s d˙ liªu Corel . 112
ixA.2 MÎt £nh m®u t¯ mÈi lÓp cıa 10 lÓp cıa cÏ s d˙ liªu Wang 113
A.3 MÈi m®u cho mÎt chı ∑ trong sË 101 chı ∑ trong cÏ s d˙ liªu
£nh Caltech 101 . 117
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 118
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 . 119
B.1 ˜a mÎt £nh vào hª thËng tra c˘u ∑ xußt 120
B.2 K∏t qu£ tra c˘u khi t§o cıa top 20 121
B.3 K∏t qu£ tra c˘u top 20 vòng ph£n hÁi th˘ nhßt 121
B.4 K∏t qu£ tra c˘u top 20 vòng ph£n hÁi th˘ hai . 122
B.5 K∏t qu£ tra c˘u top 20 vòng ph£n hÁi th˘ ba . 122
B.6 ˜a vào hª thËng mÎt truy vßn 123
B.7 K∏t qu£ tra c˘u khi t§o top 20 . 123
B.8 K∏t qu£ tra c˘u top 20 vòng ph£n hÁi th˘ nhßt 124
B.9 K∏t qu£ tra c˘u top 20 vòng ph£n hÁi th˘ hai . 124
B.10 K∏t qu£ tra c˘u top 20 vòng ph£n hÁi th˘ ba . 124
B.11 K∏t qu£ tra c˘u top 20 vòng ph£n hÁi th˘ t˜ . 125
xDanh sách b£ng
2.1 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 48
2.2 Î 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Î 49
2.3 Î 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⇠ . 50
2.4 Các miêu t£ £nh và hàm kho£ng cách s˚ dˆng trong th¸c nghiªm 50
2.5 Tham sË phân cˆm FCM 55
2.6 Các Ëi t˜Òng cıa t™p AGR t trên sáu l¶n l∞p ph£n hÁi Ëi vÓi £nh
truy vßn Q = 710.jpg 60
2.7 ThËng kê trÂng sË kho£ng cách t¯ng bÎ ∞c tr˜ng w t theo mÈi l¶n
l∞p Ëi vÓi mÎt sË £nh truy vßn 61
2.8 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 . 63
2.9 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 64
2.10 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) 65
2.11 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) 65
3.1 Kho£ng cách gi˙a Q và o 1 , o 2 , o 3 trong các ∞c tr˜ng màu s≠c và
k∏t cßu 70
3.2 Các miêu t£ £nh và hàm kho£ng cách s˚ dˆng trong th¸c nghiªm 87
3.3 Các tham sË s˚ dˆng trong th¸c nghiªm 89
3.4 SË ˘ng viên Pareto theo top k Ëi vÓi Db1 . 90
3.5 SË ˘ng viên Pareto theo top k Ëi vÓi Db2 . 90
3.6 SË ˘ng viên Pareto theo top k Ëi vÓi Db3 . 91
3.7 Trung bình Î chính xác top k k∏t qu£ cıa ∑ xußt Pareto-
AdaBoost trên n´m vòng ph£n hÁi liên quan Ëi vÓi t™p d˙ liªu
Db1 . 91
xi3.8 Trung bình Î chính xác top k k∏t qu£ cıa ∑ xußt Pareto-
AdaBoost trên n´m vòng ph£n hÁi liên quan Ëi vÓi t™p d˙ liªu
Db2 . 92
3.9 Trung bình Î chính xác top k k∏t qu£ cıa ∑ xußt Pareto-
AdaBoost trên n´m vòng ph£n hÁi liên quan Ëi vÓi t™p d˙ liªu
Db3 . 92
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 . 93
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 . 93
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 . 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
xiiM ¶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 bi 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. https://www.flickr.com/
2. https://www.youtube.com
3. https://www.facebook.com/
4. https://twitter.com/
5. http://www.google.com
6. https://www.bing.com/
7. https://vn.yahoo.com/?p=us
12
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 ó bi 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], SIMPLI-
city [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£ bi các vector ∞c tr˜ng nhi∑u chi∑u. Các vector ∞c tr˜ng cıa các3
£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 k ng˜Ìi
dùng ánh giá m˘c Î liên quan theo nh™n th˘c. â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.