Tài liệ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

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 khi 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 khi 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 khi 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 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. 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 ó 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], 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£ bi 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á,