Tóm tắt Luận án tiến sĩ Toán học: 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

Chia sẻ: Trần Văn Yan | Ngày: | Loại File: PDF | Số trang:33

Thêm vào BST

Báo xấu

20
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu của luận án nhằm nghiên cứu và đề xuất chuẩn hóa đặc trưng, chuẩn hóa khoảng cách để nâng cao hiệu quả so sánh độ tương tự. Phản hồi liên quan: đề xuất kỹ thuật hiệu chỉnh trong số và dịch chuyển truy vấn.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận án tiến sĩ Toán học: 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 Chuyên ngành: Cơ sở Toán cho Tin học Mã số: 62 46 01 10 TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội – 2017
Công trình được hoàn thành tại: 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 Người hướng dẫn khoa học 1: PGS. TS. Ngô Quốc Tạo Người hướng dẫn khoa học 2: PGS. TS. Nguyễn Hữu Quỳnh Phản biện 1: … Phản biện 2: … Phản biện 3: …. Luận án sẽ được bảo vệ trước Hội đồng chấm luận án tiến sĩ, họp tại 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 vào hồi … giờ ..’, ngày … tháng … năm 201…. Có thể tìm hiểu luận án tại: - Thư viện Học viện Khoa học và Công nghệ - Thư viện Quốc gia Việt Nam
M ¶u Tính cßp thi∏t cıa ∑ tài VÓ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 a ph˜Ïng tiªn lÓn. Nhi∑u hª thËng tìm ki∏m v´n b£n và £nh nh˜ Google, Yahoo 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. Bên c§nh nh˙ng ti∏n bÎ trong CBIR, 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 £nh lÓn không Áng nhßt. K∏t qu£ tìm ki∏m ch˜a §t ˜Òc nh˜ mong muËn. Nhi∑u nghiên c˘u trong lænh v¸c CBIR ∏n nay v®n ang cË g≠ng nâng cao hiªu qu£. 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 Hình 0.1. Hª thËng tra c˘u £nh d¸a vào nÎi dung. 1
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 : ∑ xußt kˇ thu™t hiªu chønh trÂng sË và d‡ch chuy∫n truy vßn. — ánh chø sË và tra c˘u : Vector ∞c tr˜ng cıa tßt c£ các £nh trong cÏ s d˙ liªu ˜Òc trích rút 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. K∏t qu£ tra c˘u là t™p £nh có kho£ng cách nh‰ nhßt ho∞c ˜Òc d¸ báo cùng lÓp so 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 ˜Òc s˚ dˆng nhi∑u trong 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. — ∑ xußt mÎt sË kˇ thu™t c£i thiªn Î chính xác trong CBIR trên mÎt sË t™p £nh. — Cài ∞t th¸c nghiªm cho các ∑ xußt, so sánh và ánh giá Î chính xác. Ph˜Ïng pháp và nÎi dung nghiên c˘u Ph˜Ïng pháp nghiên c˘u : 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 : Nghiên c˘u tÍng quan v∑ tra c˘u £nh d¸a vào nÎi dung. Nghiên c˘u cách k∏t hÒp nhi∑u ∞c tr˜ng 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. 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 ∑ xußt chu©n hoá c£i ti∏n cho phép nâng cao hiªu qu£ Ëi sánh Î t˜Ïng t¸, ∑ xußt kˇ thu™t hiªu chønh trÂng sË và d‡ch chuy∫n truy vßn trong tÍ hÒp ∞c tr˜ng [CT6]. ∑ xußt s˚ dˆng tËi ˜u Pareto xây d¸ng t™p ˘ng viên trên không gian k∏t hÒp a ∞c tr˜ng ∫ nâng cao Î chính xác tra c˘u [CT7]. 2
Hình 0.2. Hª thËng ∑ xußt 3
Ch˜Ïng 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 CBIR 1.1.1 Các ti∏p c™n ∞c tr˜ng toàn cˆc Các ti∏p c™n toàn cˆc th¸c hiªn trích rút các ∞c tr˜ng trên toàn bÎ £nh, các ∞c tr˜ng ˜Òc tính toán d¸a trên các thuÎc tính màu s≠c, k∏t cßu ho∞c hình d§ng cıa £nh. MÎt sË ∞c tr˜ng ˜Òc trích rút theo cách ti∏p c™n toàn cˆc nh˜ : l˜Òc Á màu, t˜Ïng quan màu, mô men màu, Gabor wavelet, bi∏n Íi Gabor, GIST ˜Òc s˚ dˆng trong các công trình [CT6], [CT7]. 1.1.2 Các ti∏p c™n ∞c tr˜ng cˆc bÎ Các kˇ thu™t phát hiªn các i∫m nÍi b™t ã ˜Òc ∑ xußt trong mÎt sË nghiên c˘u nh˜ SIFT (Scale-Invariant Feature Transform) và SURF (Speed Up Robust Features). Các ∞c tr˜ng này ˜Òc s˚ dˆng trong mÎt sË th¸c nghiªm cıa công trình [CT5]. 4
1.2 K∏t hÒp a ∞c tr˜ng trong CBIR Nhi∑u nghiên c˘u CBIR s˚ dˆng k∏t hÒp nhi∑u ∞c tr˜ng tr¸c quan gÁm các ki∫u màu s≠c, k∏t cßu và hình d§ng, mÈi ki∫u gÁm nhi∑u bÎ ∞c tr˜ng. ◊u i∫m nh¨m nhßn m§nh óng góp theo ki∫u. H§n ch∏ là không £m b£o tính công b¨ng gi˙a các bÎ ∞c tr˜ng trong cùng mÎt ki∫u vì các bÎ ∞c tr˜ng có nh˙ng óng góp tích c¸c khác nhau. 1.3 Chu©n hoá trong CBIR Các hª thËng tra c˘u cÏ s d˙ liªu £nh ph˘c t§p s˚ dˆng các ∞c tr˜ng th˜Ìng ˜Òc trích rút b¨ng nhi∑u thu™t toán khác nhau vÓi nhi∑u nguÁn khác nhau, nên không ph£i tßt c£ nh˙ng ∞c tr˜ng này có cùng ph§m vi. 1.3.1 Mˆc ích cıa chu©n hoá ∫ £m b£o s¸ bình Øng trên mÈi thành ph¶n ∞c tr˜ng trong cùng mÎt véc tÏ ∞c tr˜ng. ChØng h§n nh˜ trong bi∫u diπn k∏t cßu b∑ m∞t, mÎt thành ph¶n có th∫ là trung bình trong khi thành ph¶n khác có th∫ là Î lªch chu©n. Lúc này nhßt thi∏t ph£i chu©n hoá d˙ liªu tr˜Óc khi th¸c hiªn viªc tính Î t˜Ïng t¸ gi˙a các véc tÏ ∞c tr˜ng cıa £nh truy vßn vÓi các £nh. 1.3.2 Chu©n hóa min-max Chu©n hóa min-max cho phép chuy∫n d˙ liªu v∑ ph§m vi [0, 1] nh˜ sau : ˜ }, 8 k , tijk ˜ = tijk min{tijk } {tijk } 7! {tijk , (1.1) max {tijk } min{tijk } trong ó min{tijk } và max {tijk } là giá tr‡ nh‰ nhßt và lÓn nhßt cıa chuÈi  thành ph¶n k theo bÎ ∞c tr˜ng tij cıa tßt c£ các £nh trong cÏ s d˙ liªu. 5
1.3.3 Chu©n hóa Gauss {tijk } 7! {tijk ˜ = tijk µk , ˜ }, 8 k , tijk (1.2) 3 k def def trong ó µk = mean({tijk }), k = var ({tijk }). 1.4 Kho£ng trËng ng˙ nghæa Thu™t ng˙ “kho£ng trËng ng˙ nghæa ˜Òc dùng ∫ miêu t£ s¸ khác nhau gi˙a hai m˘c miêu t£ cıa mÎt £nh. ó là nÎi dung tr¸c quan m˘c thßp và khái niªm ng˙ nghæa m˘c cao ˜Òc hi∫u bi con ng˜Ìi. ∫ nâng cao hiªu qu£ tra c˘u c¶n thi∏t thu hµp kho£ng trËng ng˙ nghæa này. 1.5 Ph£n hÁi liên quan trong CBIR Ph£n hÁi liên quan trong CBIR ˜Òc hi∫u nh˜ sau : B˜Óc 1 : Máy tính ˜a ra các k∏t qu£ tra c˘u khi t§o (top k ) thông qua £nh truy vßn. B˜Óc 2 : Ng˜Ìi dùng cung cßp ánh giá trên k∏t qu£ top k , ánh giá theo ki∫u nh˜ “liên quan” ho∞c “không liên quan” vÓi nh™n th˘c cıa chính ng˜Ìi dùng ó. B˜Óc 3 : Máy hÂc và th˚ l§i. L∞p l§i b˜Óc 2. T¯ t™p k∏t qu£ top k mÎt sË ph˜Ïng pháp th˜Ìng s˚ dˆng kˇ thu™t ph£n hÁi liên quan nh˜ hiªu chønh trÂng sË và d‡ch chuy∫n truy vßn ; m rÎng truy vßn ; kˇ thu™t hÂc máy. MÈi ph˜Ïng pháp có cách hÂc khác nhau trong viªc s˚ dˆng thông tin cıa ng˜Ìi dùng. 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 Kˇ thu™t hiªu chønh trÂng sË hÂc quan tâm cıa ng˜Ìi dùng b¨ng cách i∑u chønh trÂng sË cıa mÈi ∞c tr˜ng cıa truy vßn và trÂng sË cıa mÈi chi∑u trong cùng mÎt ∞c tr˜ng, ˜Òc 6
i∑u chønh sau mÈi l¶n l∞p. Các trÂng sË lÓn ˜Òc gán cho nh˙ng ∞c tr˜ng có s¸ phân biªt tËt gi˙a các £nh liên quan và không liên quan ∫ t´ng c˜Ìng Î chính xác tra c˘u. 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 D˙ liªu bao gÁm truy vßn và các £nh, mÈi truy vßn liên quan ∏n mÎt sË các £nh. S¸ liên quan cıa các £nh Ëi vÓi truy vßn ˜Òc cho bi mÎt nhãn, k˛ hiªu mÎt lo§i ( ˜a ra trong hußn luyªn và d¸ báo trong ki∫m tra). D˙ liªu ki∫m tra gÁm mÎt truy vßn mÓi và các £nh liên quan. 1.7.2 Nhãn d˙ liªu Các truy vßn ˜Òc ˜a vào các hª thËng tìm ki∏m và các £nh x∏p h§ng cao nhßt ˜Òc tr£ v∑ (top rank). Nh˜ v™y, mÈi truy vßn liên quan vÓi nhi∑u £nh. Con ng˜Ìi ánh giá d¸a vào s¸ liên quan trên các c∞p £nh-truy vßn. S¸ ánh giá liên quan th˜Ìng theo nhi∑u m˘c Î. Con ng˜Ìi ánh giá liên quan theo quan i∫m cıa trung bình các ng˜Ìi dùng. Các nhãn bi∫u diπn s¸ liên quan sau ó ˜Òc gán cho các c∞p £nh-truy vßn. 1.7.3 Xây d¸ng mô hình hÂc Mˆc ích s˚ dˆng các kˇ thu™t hÂc máy ∫ th¸c hiªn nhiªm vˆ x∏p h§ng. D˙ liªu bao gÁm truy vßn và các £nh, trong ó mÈi truy vßn liên quan ∏n mÎt sË £nh. Thu™t toán sau ó truy c™p mÎt t™p ki∫m tra, t™p mÓi cıa các c∞p truy vßn - £nh vÓi mˆc ích d¸ báo các nhãn x∏p h§ng sau cùng có kh£ n´ng tËt nhßt. Î phù hÒp xác ‡nh thông qua mÎt hàm lÈi. 7
1.7.4 Phân lÓp £nh 1.7.4.1 Kˇ thu™t Adaboost ây là ph˜Ïng pháp cho phép c£i thiªn Î chính xác cıa bßt k˝ các thu™t toán hÂc nào, cho phép k∏t hÒp các ph˜Ïng pháp phân lÓp y∏u thành mÎt phân lÓp m§nh hÏn. 1.7.4.2 Support Vector Machine (SVM) SVM ph‰ng oán k∏t qu£ tra c˘u theo các m®u hußn luyªn. D¸a vào k∏t qu£ tra c˘u, ng˜Ìi dùng l¸a chÂn các £nh liên quan và các £nh không liên quan t§o thành t™p m®u d˜Ïng và t™p m®u âm t˜Ïng ˘ng. Sau khi hÂc t™p m®u hußn luyªn, b¨ng cách s˚ dˆng SVM, bÎ phân lÓp SVM f (x ) s≥ d¶n i∑u chønh theo mˆc ích tra c˘u cıa ng˜Ìi dùng. 1.8 MÎt sË ti∏p c™n d¸a theo ph˜Ïng pháp tËi ˜u Pareto T™p Pareto là mÎt t™p ch˘a tßt c£ các i∫m có ít nhßt mÎt mˆc tiêu tËi ˜u trong khi £m b£o không thay Íi các mˆc tiêu khác. Các i∫m nh˜ v™y ˜Òc gÂi là các i∫m tËi ˜u Pareto. Pareto front ¶u tiên bao gÁm mÎt t™p các i∫m không b‡ làm trÎi. 1.9 Các ph˜Ïng pháp ánh giá Î o hiªu n´ng Hai chø sË ˜Òc s˚ dˆng là Precision (Pr- Î chính xác) và recall (Re - Î hÁi t˜ng). Pr E là tø sË cıa sË các £nh liên quan ˜Òc tra c˘u (E) vÓi tÍng sË £nh ˜Òc tra c˘u (D) : Pr = D . Re là tø sË cıa sË các £nh liên quan ˜Òc tra c˘u (E) vÓi toàn bÎ sË £nh liên quan có trong cÏ E s d˙ liªu (A) : Re = A . 8
K∏t lu™n ch˜Ïng 1 Ch˜Ïng 1 giÓi thiªu mÎt sË ∞c tr˜ng th˜Ìng ˜Òc s˚ dˆng và s¸ k∏t hÒp các ∞c tr˜ng. Trong ch˜Ïng ã phân tích nh˙ng khó kh´n khi áp dˆng chu©n hoá Gauss và phân tích nh˙ng tÁn t§i cıa các kˇ thu™t nh¨m gi£m kho£ng trËng ng˙ nghæa trong CBIR. 9
Ch˜Ïng 2 ∑ xußt chu©n hoá ∞c tr˜ng và hiªu chønh trÂng sË trong tÍ hÒp ∞c tr˜ng ∫ có nh˙ng ∑ xußt c£i ti∏n trong hª thËng CBIR, trong ch˜Ïng ∑ xußt kˇ thu™t chu©n hoá ∞c tr˜ng, hiªu chønh trÂng sË kho£ng cách và hiªu chønh truy vßn s˚ dˆng ph£n hÁi liên quan. Hình 2.1 là mô hình ki∏n trúc hª thËng ∑ xußt trong công trình nghiên c˘u [CT6]. Hình 2.1. Mô hình hª thËng IR 3 FCM 10
2.1 Chu©n hoá ∞c tr˜ng d¸a vào phân cˆm mÌ FCM Kh£o sát trên mÎt sË t™p £nh chu©n cho thßy h¶u h∏t d˙ liªu ∞c tr˜ng gËc phân bË không theo Gauss. ∑ xußt b‰ gi£ thi∏t d˙ liªu các thành ph¶n ∞c tr˜ng theo phân bË Gauss, phân cˆm ∫ t§o ra các vùng Áng nhßt, chu©n hoá các thành ph¶n theo lu™t 3 trên mÈi cˆm. K∏t nh™p k∏t qu£ theo mÈi cˆm ∫ ˜Òc mÎt giá tr‡ chu©n hoá duy nhßt. Cho {Iit }1iN và các h¨ng sË p = p(t) > 1 (p(t) là hª sË FCM cho bÎ ∞c tr˜ng th˘ t), C = C (t) 2 N+ , Mt = dim(Iit ) là Î dài cıa ∞c tr˜ng bÎ t, 8 i, 1  i  N . Thu™t toán l∞p FCM c¸c ti∫u hóa hàm mˆc tiêu : N X X C p 2 J (V , ⌘) = min ⌘t,c,i Iit Vt,c , (2.1) V ,⌘ i=1 c=1 2 P Mt vÓi Î o kho£ng cách Euclid, kIit Vt,c k = (Iit [j ] Vt,c [j ])2 , và các ràng buÎc bi∏n nh˜ sau : j =1 (1) ⌘t,c,i 2 [0, 1], 8 1  i  N , i  c  C , t 1, PC (2) c=1 ⌘t,c,i = 1, 8 1  i  N , Pn (3) i=1 ⌘t,c,i < N , 8 1  c  C . ‡nh nghæa 2.1. [CT6] Cho t™p d˙ liªu {Iit }1iN ˜Òc phân thành C cˆm s˚ dˆng FCM vÓi tham sË p > 1. Î lªch chu©n  cˆm c (1  c  C ) ˜Òc tính nh˜ sau : v u N N u def tX p 2 X p = t t,c,j ⌘t,c,i (Ii [j ] Vt,c [j ]) / ⌘t,c,i , 8 1  j  Mt , (2.2) i=1 i=1 Mªnh ∑ 2.1. [CT6] Gi£ s˚ {Vc }C c=1 là t™p C véc tÏ tâm m chi∑u ( ¶u ra cıa thu™t toán phân cˆm s˚ dˆng FCM), 8 c = 1, .., C . Khi ó Î lªch chu©n cıa cˆm c tho£ mãn công th˘c sau : PN p 2 i=1 ⌘t,c,i (Iit [j ])2 2 t,c,j = PN p Vt,c [j ]. (2.3) ⌘ i=1 t,c,i ‡nh nghæa 2.2. [CT6] Phép chu©n hóa 3 FCM . n oMt Cho I = {I [j ]}M t , ˜ = I˜[j ] I , 8 1  j  Mt , ˜Òc ‡nh nghæa nh˜ sau j =1 j =1 n o n o I [j ] Vt,c [j ] I [j ] Vt,c [j ] min 3 t,c,j + max 3 t,c,j def 1cC 1cC I˜[j ] = (2.4) C +1 11
Mªnh ∑ 2.2. [CT6] Phép chu©n hóa 3 FCM b£o toàn th˘ t¸, nghæa là : I [j] I0 [j] ) I˜[j ] I˜0 [j ]. Chu©n hoá £m b£o k∏t qu£ tính Î t˜Ïng t¸ chính xác hÏn, c£i thiªn t™p k∏t qu£ top-k hi∫n th‡ cho ng˜Ìi dùng, t¯ ó nâng cao hiªu qu£ truy vßn. 2.2 Chu©n hoá kho£ng cách d¸a vào phân cˆm FCM Giá tr‡ kho£ng cách £nh truy vßn vÓi mÈi £nh cÏ s d˙ liªu ˜Òc chu©n hoá theo Thu™t toán 2.1. Thu™t toán 2.1 Chu©n hoá d˙ liªu kho£ng cách 3 FCM theo t¯ng bÎ [CT6] ¶u vào: {I˜it }1iN . /* T™p các véc tÏ ∞c tr˜ng ã chu©n hoá theo lu™t 3 FCM */ {Vt,c }1cCt . /* T™p các tâm theo t¯ng bÎ ∞c tr˜ng */ { t,c,j }1cCt ,1j Mt . /* Î lªch chu©n */ h¨ng sË p = p(t) > 1, C = C (t) 2 N , C 2 + (D) ¶u ra: {Vt,c }1cC (D) . /* T™p tâm */ t (D) { t,c }1cC (D) . /* Î lªch chu©n */ t 1: B˜Óc 1 : (1) Sinh ra hai t™p gÁm K giá tr‡ chø sË ng®u nhiên RD1 = {RD1,i }1iK , và RD2 = {RD2,i }1iK tho£ mãn : (1.1) RD1 \RD2 = ?, RD1,i < RD1,j , RD2,i < RD2,j , 8 1  i  j  K . (1.2) 1  RD1,i , RD2,i  N , 8 1  i  N (chÂn K = [N /10], m = K 2 . (2) Xác ‡nh t™p giá tr‡ D(I˜RD t 1,i , I˜RD t 1,i ) ˜Òc t™p giá tr‡ sË d˜Ïng {dk }1k m n oCt(D) n o (D) (D) (D) 2: B˜Óc 2 : FCM (Ct , pt ) {dk }1k m ta ˜Òc t™p tâm Vt,c và ⌘t,c,i (D) c=1 1cCt ,1im theo Công th˘cn(2.1)o (D) 3: B˜Óc 3 : Tính t,c (D) theo Công th˘c (2.3) 1cCt (B˜Óc 2 và 3, s˚ dˆng Công th˘c (2.1), (2.3), (2.4) thay th∏ d˙ liªu ∞c tr˜ng b¨ng giá tr‡ kho£ng cách ( là các (D) sË th¸c d˜Ïng vô h˜Óng.) ) n oCt n o (D) (D) 4: Return Vt,c , t,c (D) c=1 1cCt 2.3 Hiªu chønh trÂng sË, d‡ch chuy∫n truy vßn ‡nh nghæa 2.3. [CT6] Cho truy vßn Q thì Î o kho£ng cách cıa bÎ ∞c tr˜ng th˘ t và Î o kho£ng cách toàn bÎ vÓi mÎt £nh I trong cÏ s d˙ liªu t˜Ïng ˘ng ˜Òc xác ‡nh nh˜ sau : 12
(1) Î o kho£ng cách cıa mÎt bÎ ∞c tr˜ng : def DQt (I ) = wt DQt (I ), (2.5) trong ó wt là trÂng sË theo bÎ ∞c tr˜ng th˘ t. (2) Î o kho£ng cách toàn bÎ : T X def DQ (I ) = DQt (I ) (2.6) t=1 GÂi t™p k∏t qu£ NB có Î t˜Ïng t¸ nh™n th˘c cao nhßt cıa ng˜Ìi dùng. Ng˜Ìi dùng s≥ ánh giá và ph£n hÁi cho các £nh trên t™p NB thu ˜Òc NB + , NB . ‡nh nghæa 2.4. [CT6] T™p Áng thu™n (Agreement (AGR)) gi˙a Î o kho£ng cách toàn bÎ và Î o kho£ng cách theo bÎ ∞c tr˜ng ˜Òc ‡nh nghæa nh˜ sau def AGRt (DQ (I ), DQt (I ), N ) = NB \NBt , (2.7) trong ó NB , NBt t˜Ïng ˘ng là t™p N £nh có Î o kho£ng cách cao nhßt theo Î o kho£ng cách toàn bÎ DQ (I ), và theo Î o kho£ng cách DQt (I ) cıa riêng bÎ ∞c tr˜ng t. 2.3.1 Hiªu chønh trÂng sË Công th˘c tính trÂng sË cho t¯ng bÎ ∞c tr˜ng vÓi mÈi £nh truy vßn cˆ th∫ ˜Òc xác ‡nh trong ∑ xußt nh˜ sau : — Tính giá tr‡ trÂng sË ⇣ ⌘ (l+1) (l) (l) wt = max wt + wt , 0 (2.8) ✓ ◆ (l) (l),NB + (l),NB + trong ó l là k˛ hiªu l¶n l∞p, wt = f score(Iit ), t,DQt (I ) , t,kIit k 2 ( 1, +1), hàm f có th∫ chÂn chØng h§n : score(Iit ) (l),NB + (l),NB + f (score(Iit ), t,DQt (I ) , t,kIit k ) = (l),NB + 3 (l),NB + (2.9) ( t (I ) ⇥ ) t,DQ t,kIit k Thu™t toán 2.2 ∑ xußt hiªu chønh kho£ng cách toàn cˆc d¸a trên kho£ng cách cˆc bÎ. 13
Thu™t toán 2.2 Hiªu chønh trÂng sË Î o kho£ng cách toàn cˆc [CT6] ¶u vào: {Iit }1iN . /* CÏ s d˙ liªu ∞c tr˜ng ã ˜Òc chu©n hoá */ {Vt,c }1cCt . /* Tâm cıa các cˆm theo bÎ ∞c tr˜ng trong ¶u ra cıa thu™t toán phân cˆm FCM */ { t,c,j }1cCt ,1j Mt . /* Î lªch chu©n cıa các cˆm theo bÎ ∞c tr˜ng trong ¶u ra cıa thu™t n toán o chu©n hoá ∞c tr˜ng */ (D) Vt,c (D) . /* Tâm cıa các cˆm trên t™p giá tr‡ kho£ng cách bÎ theo bÎ ∞c 1tT ,1cCt tr˜ng n otrong ¶u ra cıa Thu™t toán 2.1 */ (D) t,c (D) . /* Î lªch chu©n cıa các cˆm trên t™p giá tr‡ kho£ng cách bÎ theo bÎ 1cCt ∞c tr˜ng trong ¶u ra cıa Thu™t toán 2.1 */ /* Véc tÏ ∞c tr˜ng m˘c thßp Q cıa £nh truy vßn. Lmax sË l¶n l∞p ph£n hÁi, K : sË £nh có Î o kho£ng cách toàn cˆc so vÓi Q là thßp nhßt. */ ¶u ra: T™p trÂng sË {wt }1tT 1: Khi t§o 8 t = 1, T , wt = T1 2: Chu©n hóa t¯ng bÎ t cıa Q theo 3 FCM (thu™t toán chu©n hoá ∞c tr˜ng). 3: for l = 1 to Lmax do 4: for Each Ii 2 {Ii }1iN , 8 t = 1, T do 5: Chu©n hoá Î o kho£ng cách cho bÎ t b¨ng cách : DQt (Ii ) = 3 FCM DQt (Ii ) ⇣ ⇣ D t (I )+1 ⌘ ⌘ i 6: Chuy∫n DQt (Ii ) v∑ [0, 1] : DQt (Ii ) = min max Q 2 , 0 , 1 P T 7: Tính Î o kho£ng cách : DQ (Ii ) = wt DQt (Ii ) t=1 /*Hiªu chønh trÂng sË d¸a trên AGRt */ 8: for each I 2 N B (l) , 8 t = 1, T do (l) 9: if I 2 AGRt then 10: Hiªu chønh wt theo công th˘c (2.8) và (2.9) 11: end if 12: end for P T 13: Chu©n hóa l§i trÂng sË wt , 8 t = 1, T , wt = wt / wt t=1 14: end for 15: end for 16: Return : K∏t thúc thu ˜Òc {wt }1tT 2.3.2 D‡ch chuy∫n truy vßn P r P def def 2 ∞t Q t = 1 Iit , và t = 1 ¯t Iit Q , #(AGRt ) #AGRt Iit 2AGRt Ii 2AGRt def ¯ t | 3 trong ó AGRt⇤ = Iit 2 AGRt / | Iit Q t 14
AGRt có s¸ Áng nhßt cao v∑ ∞c tr˜ng, khi #AGRt 2 và #AGRt⇤ 1 ( £m b£o có s¸ thay Íi), truy vßn mÓi ˘ng vÓi bÎ ∞c tr˜ng t ˜Òc l™p l§i nh˜ sau : def 1 X Qt,new = Iit (2.10) #AGRt⇤ Iit 2AGR ⇤ 2.4 Th˚ nghiªm và ánh giá các k∏t qu£ 2.4.1 CÏ s d˙ liªu £nh T™p d˙ liªu £nh Wang 1 là t™p con cıa t™p Corel ˜Òc s˚ dˆng trong th¸c nghiªm. 2.4.2 Trích rút bÎ ∞c tr˜ng k∏t hÒp CÏ s d˙ liªu £nh ˜Òc bi∫u diπn vÓi ba ki∫u ∞c tr˜ng màu s≠c, k∏t cßu, hình d§ng bao gÁm sáu bÎ ∞c tr˜ng m˘c thßp nh˜ trong B£ng 2.1. B£ng 2.1. Các miêu t£ £nh và hàm kho£ng cách s˚ dˆng trong th¸c nghiªm. Miêu t£ Ki∫u SË chi∑u Hàm kho£ng cách L˜Òc Á HSV Màu 32 L1 Các mô men màu Màu 6 L2 L˜Òc Á t¸ t˜Ïng quan màu Màu 64 L1 Các phép lÂc Gabor K∏t cßu 48 Canberra Các mô men Wavelet K∏t cßu 40 L2 Gist Hình d§ng 512 L2 2.4.3 Các k∏t qu£ th¸c nghiªm và lu™n gi£i 2.4.3.1 Phân bË d˙ liªu và chßt l˜Òng truy vßn Các Hình 2.2, 2.3, 2.4, 2.5, 2.6, 2.7 là so sánh k∏t qu£  thành ph¶n th˘ n´m cıa chu©n hoá ∞c tr˜ng 3 và chu©n hoá ∑ xußt 3 FCM . Qua phép chu©n hoá 3 FCM , các giá tr‡ thành ph¶n ∞c tr˜ng th˘ 5 “rÏi vào” [-1,1] nhi∑u hÏn chu©n hoá 3 . 1. http://wang.ist.psu.edu/docs/home.shtml 15
Thanh phan thu 5 dac trung luoc do mau HSV (3σ) 7000 Thanh phan thu 5 luoc do mau HSV (3σ-FCM) 7000 6000 6000 5000 5000 Tan suat 4000 Tan suat 4000 3000 3000 2000 2000 1000 1000 0 0 -2 -1 0 1 2 3 4 -0.5 0 0.5 1 1.5 2 Gia tri Gia tri (a) (b) Hình 2.2. (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] Thanh phan thu 5 dac trung tu tuong quan mau (3σ) 4500 Thanh phan thu 5 dac trung tu tuong quan mau (3σ-FCM) 6000 4000 5000 3500 3000 4000 Tan suat 2500 Tan suat 3000 2000 1500 2000 1000 1000 500 0 0 -2 -1 0 1 2 3 4 5 6 -0.2 0 0.2 0.4 0.6 0.8 1 Gia tri Gia tri (a) (b) Hình 2.3. (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] Hình 2.8(a-b) ch˘ng minh chßt l˜Òng truy vßn bi∫u diπn qua Î chính xác trên các k∏t qu£ top k khi ∞c tr˜ng ˜Òc chu©n hoá 3 FCM tËt hÏn khi ˜Òc chu©n hóa 3 . K∏t qu£ tra c˘u này không s˚ dˆng kˇ thu™t hiªu chønh nào. 2.4.3.2 Hiªu qu£ Î chính xác tra c˘u s˚ dˆng kˇ thu™t hiªu chønh trÂng sË và d‡ch chuy∫n truy vßn Ph˜Ïng pháp ∑ xußt (k˛ hiªu là IR-ThreeSigmaFCM ) ˜Òc so sánh vÓi ph˜Ïng pháp cÏ s PowerTool (PowerTool chu©n hoá ∞c tr˜ng 3 và s˚ dˆng kˇ thu™t hiªu chønh trÂng sË). Hình 2.9(a) cho bi∏t trung bình Î chính xác theo k∏t qu£ top k . Trˆc hoành bi∫u diπn tra c˘u theo các tr˜Ìng hÒp top k là 20, 40, 60, 80, 100, 120, 140, 160, 180, 200. Trˆc tung bi∫u diπn trung bình Î chính xác cıa các £nh tr£ v∑ theo top k sau 5 l¶n l∞p ph£n hÁi liên quan. 16
Thanh phan thu 5 dac trung mo men mau (3σ) 400 Thanh phan thu 5 dac trung mo men mau (3σ-FCM) 400 350 350 300 300 250 250 Tan suat Tan suat 200 200 150 150 100 100 50 50 0 0 -1.5 -1 -0.5 0 0.5 1 1.5 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 Gia tri Gia tri (a) (b) Hình 2.4. (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] Thanh phan thu 5 dac trung ket cau Gabor (3σ) 6000 Thanh phan thu 5 dac trung ket cau Gabor (3σ-FCM) 6000 5000 5000 4000 4000 Tan suat Tan suat 3000 3000 2000 2000 1000 1000 0 0 -2 0 2 4 6 8 -0.5 0 0.5 1 1.5 2 2.5 Gia tri Gia tri (a) (b) Hình 2.5. (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] Sau ba vòng ph£n hÁi liên quan, kˇ thu™t ∑ xußt §t tÓi 87%, 78%, 74%, 69%, 64% trên các top 20, top 40, top 60, top 80 và top 100 t˜Ïng ˘ng. Hình 2.9(b) so sánh trung bình Î chính xác trên top k cıa kˇ thu™t ∑ xußt và PowerTool sau ba vòng l∞p ph£n hÁi liên quan. Hình 2.10(a) so sánh Î chính xác trên top 20 cıa kˇ thu™t ∑ xußt và PowerTool. Bi∫u Á cho bi∏t trung bình mÈi vòng ph£n hÁi liên quan kˇ thu™t ∑ xußt ∑u cao hÏn. Hình 2.10(b) là bi∫u Á so sánh Î chính xác và Î hÁi t˜ng cıa kˇ thu™t ∑ xußt và PowerTool trung bình sau ba vòng ph£n hÁi liên quan. 2.5 K∏t lu™n ch˜Ïng 2 ∑ xußt trong ch˜Ïng ã nâng cao hiªu n´ng v∑ Î chính xác cıa hª thËng CBIR. NÎi dung ∑ xußt gÁm chu©n hoá ∞c tr˜ng, hiªu chønh trÂng sË Î t˜Ïng t¸ truy vßn và d‡ch chuy∫n 17
Thanh phan thu 5 dac trung mo ment Wavelet (3σ) 300 Thanh phan thu 5 dac trung mo men Wavelet (3σ-FCM) 300 250 250 200 200 Tan suat Tan suat 150 150 100 100 50 50 0 0 -1.5 -1 -0.5 0 0.5 1 1.5 -0.4 -0.3 -0.2 -0.1 0 0.1 0.2 0.3 0.4 Gia tri Gia tri (a) (b) Hình 2.6. (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] Thanh phan thu 5 dac trung GIST (3σ) 500 Thanh phan thu 5 dac trung GIST (3σ-FCM) 500 450 450 400 400 350 350 300 Tan suat 300 Tan suat 250 250 200 200 150 150 100 100 50 50 0 0 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 -0.4 -0.2 0 0.2 0.4 0.6 0.8 Gia tri Gia tri (a) (b) Hình 2.7. (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] truy vßn sau mÈi vòng ph£n hÁi liên quan. 18