Phát triển một số kỹ thuật phát hiện dị thường trên ảnh viễn thám quang học phục vụ công tác tìm kiếm cứu nạn

Nội dung tài liệu: Phát triển một số kỹ thuật phát hiện dị thường trên ảnh viễn thám quang học phục vụ công tác tìm kiếm cứu nạn

1. BË QUÈC PHÁNG HÅC VIỆN KỸ THUẬT QUÂN SỰ NGUYỄN VĂN PHƯƠNG PHÁT TRIỂN MËT SÈ KỸ THUẬT PHÁT HIỆN DỊ THƯỜNG TRÊN ẢNH VIỄN THÁM QUANG HÅC PHỤC VỤ CÆNG TÁC TÌM KIẾM CỨU NẠN Chuy¶n nghành: CƠ SÐ TOÁN HÅC CHO TIN HÅC M¢ sè: 9 46 01 10 TÂM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT Hà Nëi - 2023
2. CÆNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI DANH MỤC CÁC CÆNG TRÌNH SỬ DỤNG TRONG HÅC VIỆN KỸ THUẬT QUÂN SỰ - BË QUÈC PHÁNG LUẬN ÁN CT1 Nguy¹n V«n Phương, Đào Kh¡nh Hoài, Tèng Minh Đức, Cao Thị Vinh (2020), "Phương ph¡p ph¡t hi»n dị thường tr¶n £nh vi¹n th¡m quang học ùng Người hướng d¨n khoa học: dụng trong công t¡c t¼m ki¸m cùu n¤n", T¤p ch½ Khoa học Trường Đại học 1. TS Đào Kh¡nh Hoài C¦n Thơ, Tªp 56, sè 1A, tr. 21–36, ISSN: 1859-2333. DOI: 10.22144/ctu.jvn. 2. TS Tèng Minh Đức 2020.003. CT2 Nguy¹n V«n Phương, Đào Kh¡nh Hoài (2018), "Mët sè kỹ thuªt ph¡t hi»n dị thường tr¶n £nh UAV ùng dụng trong công t¡c t¼m ki¸m cùu n¤n", Chuy¶n san C¡c công tr¼nh nghi¶n cùu ph¡t triºn Công ngh» thông tin và Ph£n bi»n 1: PGS.TS Đặng V«n Đức - Vi»n CNTT/Vi»n HLKH&CNVN Truy·n thông - Bë Thông tin và Truy·n thông, Tªp V-1, Sè 39, tr. 1–8, ISSN: 1859-3534, DOI: 10.32913/rd-ict.vol1.no39.581. Ph£n bi»n 2: TS L¶ Đại Ngọc - Cục B£n đồ/Bộ Têng Tham mưu CT3 Nguy¹n V«n Phương, Đào Kh¡nh Hoài, Tèng Minh Đức (2020), "T«ng hi»u qu£ ph¡t hi»n dị thường tr¶n £nh UAV ùng dụng trong công t¡c t¼m Ph£n bi»n 3: PGS.TS Tr¦n Nguy¶n Ngọc - Học vi»n Kỹ thuªt Qu¥n sự ki¸m cùu n¤n", T¤p ch½ Khoa học và Công ngh» - Đại học Th¡i Nguy¶n, Tªp 225, Sè 06, tr. 58 – 65, ISSN: 1859-2171. CT4 Nguy¹n V«n Phương, Đào Kh¡nh Hoài, Tèng Minh Đức (2019), "T«ng tèc độ ph¡t hi»n dị thường tr¶n £nh đa phê và si¶u phê ùng dụng trong công t¡c t¼m ki¸m cùu n¤n", Chuy¶n san C¡c công tr¼nh nghi¶n cùu ph¡t Luªn ¡n s³ được b£o v» trước Hëi đồng đánh gi¡ luªn ¡n c§p Học vi»n theo Quy¸t định sè 950/QĐ-HV ngày 09 th¡ng 3 n«m 2023 cõa Gi¡m đốc Học vi»n triºn Công ngh» thông tin và Truy·n thông - Bë Thông tin và Truy·n thông, Kỹ thuªt Qu¥n sự, họp t¤i Học vi»n Kỹ thuªt Qu¥n sự vào hồi giờ ngày Tªp 2019, Sè 2, tr. 70-82, ISSN: 1859-3534, DOI: 10.32913/micict-research- th¡ng n«m 2023 vn.v2019.n2.866. CT5 Nguyen Van Phuong, Dao Khanh Hoai, Tong Minh Duc (2020), "The Anomaly Detection Efficiency of Kernel Density Estimation Functions on Có thº t¼m hiºu luªn ¡n t¤i: UAV Images", Section on Information and Communication Technology (ICT), - Thư vi»n Quèc gia Vi»t Nam - Thư vi»n Học vi»n Kỹ thuªt Qu¥n sự. No. 15, pp. 7-22, ISSN: 1859 – 0209.
3. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN CỦA LUẬN ÁN MÐ ĐẦU Mët sè k¸t qu£ đạt được cõa luªn ¡n 1. T½nh c§p thi¸t cõa Luªn ¡n: 1. Đề xu§t kỹ thuªt gi£m tỷ l» dương t½nh gi£ (làm t«ng độ ch½nh x¡c ph¡t Theo sè li»u cõa Ủy ban Quèc gia Ứng phó sự cè thi¶n tai và t¼m ki¸m cùu hi»n) cõa thuªt to¡n ph¡t hi»n dị thường dựa tr¶n ước lượng mªt độ h¤t nh¥n n¤n [3], tø n«m 2004 đến n«m 2021, t¤i Vi»t Nam đã có 54.964 vụ thi¶n tai, [120, 121] b¬ng c¡ch khû bớt nhi¹u tr¶n £nh gèc và x¡c định c¡c khu vực giới sự cè, hªu qu£ làm ch¸t 14.937 người, m§t t½ch 2.616 người, bị thương 15.502 h¤n t½nh to¡n cõa thuªt to¡n KDE. K¸t qu£ thû nghi»m cho th§y, thuªt to¡n người, làm hư hỏng hàng chục ngàn trang thi¸t bị. Hi»n nay, do bi¸n đổi kh½ IKDE t«ng 0,58% v· độ ch½nh x¡c ph¡t hi»n dị thường so với thuªt to¡n KDE. hªu toàn c¦u và nhúng ho¤t động thi¸u ý thùc cõa con người, nh§t là trong 2. Đề xu§t kỹ thuªt t«ng tèc độ t½nh to¡n cõa thuªt to¡n IKDE, b¬ng c¡ch b£o v» môi trường sèng n¶n dự b¡o trong nhúng n«m tới, t¼nh h¼nh thi¶n tai, nhóm c¡c điểm £nh có gi¡ trị gièng nhau, x­p s¸p nhóm c¡c điểm £nh, ¡p dụng sự cè di¹n bi¸n phùc t¤p, b§t thường, theo chi·u hướng cực đoan, c£ v· t½nh c¥y kd-Tree để t¼m ki¸m nhanh c¡c điểm £nh, nhóm điºm £nh thỏa m¢n hàm ch§t, quy mô, cường độ và mùc độ tàn ph¡. Theo đó, công t¡c t¼m ki¸m cùu nh¥n; t½nh to¡n PDF đa luồng tr¶n CPU hoặc song song tr¶n GPU. Tø k¸t qu£ n¤n cũng ph£i được đầu tư đúng mùc để theo kịp t¼nh h¼nh thực t¸. thû nghi»m cho th§y kỹ thuªt đề xu§t mang l¤i hi»u qu£ cao v· thời gian t½nh Mët công cụ đang ngày càng được chùng minh có hi»u qu£ cao không ch¿ to¡n, đặc bi»t tr¶n £nh màu RGB, thời gian t½nh to¡n đã gi£m tới hơn 99% trong công t¡c t¼m ki¸m cùu n¤n mà cán trong nhi·u ùng dụng kh¡c như trong so với c¡c thuªt to¡n như KDE, Intel TBB, GPU CUDA. Tr¶n £nh đa phê 8 nông nghi»p và l¥m nghi»p [5], tài nguy¶n nước [34], rà ph¡ bom m¼n [8, 55], k¶nh phê và £nh si¶u phê 224 k¶nh phê, thuªt to¡n GP-PC đã gi£m được ½t công nghi»p thực ph©m [35], đó là sû dụng £nh vi¹n th¡m quang học. Bởi nh§t 82,21% so với thuªt to¡n GPU CUDA. Độ ch½nh x¡c ph¡t hi»n c¡c điểm công ngh» Vi¹n th¡m có nhi·u t½nh n«ng ưu vi»t so với phương ph¡p truy·n £nh dị thường v¨n được giú nguy¶n so với thuªt to¡n IKDE. thèng như độ phõ trùm rëng, thời gian cªp nhªt ng­n, d£i phê rëng, có thº thu Hướng ph¡t triºn cõa luªn ¡n nhªn £nh ở nhúng khu vực r§t khó ti¸p cªn như vùng núi cao, røng rªm, h£i 1. Gi£i quy¸t được v§n đề m§t c¥n b¬ng cõa dú li»u đầu vào có thº làm đảo, khu vực ngoài l¢nh thê, Đặc bi»t, trong nhúng n«m g¦n đây, c¡c thi¸t t«ng độ ch½nh x¡c ph¡t hi»n c¡c điểm £nh £nh dị thường cõa c¡c thuªt to¡n, bị bay không người l¡i (UAV) đã và đang ph¡t triºn r§t m¤nh m³, đưñc ùng b¬ng c¡ch: thu thªp th¶m dú li»u; l§y l¤i m¨u trong tªp dú li»u; Ngoài ra, dụng rëng r¢i c£ trong d¥n sự và qu¥n sự. Nó thực sự là mët nguồn lực r§t có thº sû dụng phương ph¡p ph¤t mô h¼nh (Penalized Models). lớn cho sù m»nh t¼m ki¸m, cùu n¤n bởi thi¸t bị này có thº mang c¡c bë c£m 2. Nghi¶n cùu, ph¥n t½ch mèi quan h» ràng buëc dú li»u, mèi tương quan bi¸n để thu thªp h¼nh £nh có độ ph¥n gi£i cao với ph¤m vi ho¤t động rëng lớn, v· mặt không gian cõa c¡c điểm £nh có thº làm t«ng độ ch½nh x¡c ph¡t hi»n địa h¼nh đa d¤ng mà không c¦n qu¡ nhi·u nh¥n lực và chi ph½ cho qu¡ tr¼nh dị thường cõa c¡c thuªt to¡n. t¼m ki¸m. 3. Có thº sû dụng gi¡ trị hàm DoG để t¼m k½ch thước cûa sê W th½ch nghi Ho¤t động t¼m ki¸m và cùu n¤n bao gồm vi»c t¼m ki¸m và gi£i cùu người, cho PUT, tr¡nh l¢ng ph½ thời gian t½nh to¡n. phương ti»n bị m­c kẹt trong c¡c t¼nh huèng khó kh«n hoặc được b¡o n¤n. 4. Ph¡t hi»n cụm điểm £nh dị thường c¦n k¸t hñp c¡c đặc trưng h¼nh d¤ng, C¡ch ti¸p cªn sû dụng £nh vi¹n th¡m quang học là sû dụng £nh đa phê [102], k½ch thước tr¶n cùng mët kỹ thuªt ph¡t hi»n c¡c điểm £nh dị thường. si¶u phê [15, 36] có độ ph¥n gi£i cao được c¡c c£m bi¸n g­n tr¶n m¡y bay, 5. X¥y dựng bë dú li»u đặc trưng đầy đủ, phong phú s³ c£i thi»n đáng kº khinh kh½ c¦u hoặc v» tinh thu nhªn hoàn toàn kh£ thi và mang l¤i hi»u qu£ vi»c nghi¶n cùu trong lĩnh vực này, cho ph²p so s¡nh tèt hơn giúa c¡c phương cao. Tuy nhi¶n, c¡c £nh hưởng b§t lñi g¥y ra bởi đặc trưng cõa địa h¼nh, điều ph¡p theo c¡c kịch b£n kh¡c nhau. ki»n thời ti¸t kh­c nghi»t làm cho vị tr½ b¡o n¤n có dung sai lớn. C¡c đối tượng 24 1
4. c¦n t¼m ki¸m đôi khi bị che khu§t bởi địa h¼nh, mªt độ dày đặc cõa l¡ c¥y B£ng 3.1: Thời gian thực thi cõa c¡c thuªt to¡n (t½nh b¬ng gi¥y). hoặc bị ch¼m mët ph¦n dưới nước. Trực ti¸p t¼m ra người đang gặp n¤n s³ là lý tưởng, nhưng trong mët sè trường hñp, c¡c đồ vªt đi k±m như qu¦n ¡o, ch«n m·n, va ly, túi x¡ch, l·u b¤t nơi c­m tr¤i, c¡c m£nh vỡ phương ti»n, (gọi t­t Thuªt to¡n 6010_1_2 6010_1_2_M Salinas là nhúng đối tượng nh¥n t¤o) có thº cung c§p mët sè thông tin húu ½ch [12, KDE 1.819.712 11.038 557 80, 95]. Ngoài ra, c¡c thi¸t bị c£m bi¸n thu dú li»u ph£i qu²t tr¶n mët di»n Intel TBB [86] 1.404.590 9.052 458 rëng và dung lượng dú li»u lớn là mët rào c£n đối với vi»c t¼m ki¸m thõ công GPU CUDA [87] 21.609 253 14 b¬ng m­t thường. C¡c kỹ thuªt tự động ph¡t hi»n mục ti¶u là gi£i ph¡p phù GP-KDT 21 3.744 40 hñp giúp người quan s¡t n¥ng cao hi»u qu£ và tèc độ t¼m ki¸m. V¼ vªy, đề tài GP-MC 15 548 8 "Ph¡t triºn mët sè kỹ thuªt ph¡t hi»n dị thường tr¶n £nh vi¹n th¡m quang học phục vụ GP-PC 5 45 2 công t¡c t¼m ki¸m cùu n¤n" mang t½nh c§p thi¸t. Đề tài tªp trung vào hai hướng nghi¶n cùu ch½nh đó là đề xu§t thuªt to¡n nh¬m n¥ng cao độ ch½nh x¡c ph¡t hi»n c¡c điểm £nh dị thường và t«ng tèc độ t½nh to¡n. Nhúng k¸t qu£ đạt được cõa Luªn ¡n s³ góp ph¦n x¥y dựng cơ sở lý cao nh§t là 99,999% (tr¶n £nh 6010_1_2). Trong ch¸ song song tr¶n GPU, tr¶n thuy¸t ùng dụng £nh vi¹n th¡m quang học trong công t¡c t¼m ki¸m cùu n¤n. B£ng 3.1 thº hi»n thuªt to¡n GP-PC đã nhanh hơn thuªt to¡n GPU CUDA 2. C¡c đóng góp cõa luªn ¡n: ½t nh§t 82.21% (tr¶n £nh 6010_1_2_M) và cao nh§t là 99,999% (tr¶n £nh 1. Đề xu§t thuªt to¡n t«ng đë ch½nh x¡c ph¡t hi»n c¡c điểm £nh dị thường 6010_1_2). cõa thuªt to¡n ph¡t hi»n dựa tr¶n ước lượng mªt độ h¤t nh¥n (KDE - 3.7 K¸t luªn Kernal Density Estimation) [120, 121] b¬ng c¡ch gi£m tỷ l» dương t½nh Mët sè v§n đề đã được tr¼nh bày trong chương này gồm: gi£ (gọi t­t là IKDE). ˆ Thù nh§t, đã tr¼nh bày chi ti¸t bèn bước để t«ng tèc độ t½nh to¡n cõa 2. Đề xu§t thuªt to¡n t«ng tèc độ t½nh to¡n cõa thuªt to¡n IKDE b¬ng thuªt to¡n IKDE. c¡ch sû dụng kỹ thuªt nhóm điểm £nh, s­p x¸p điểm £nh, ¡p dụng c¥y kd-tree và t½nh to¡n hàm mªt độ x¡c su§t đa luồng tr¶n CPU hoặc song ˆ Thù hai, k¸t qu£ cho th§y: kỹ thuªt đề xu§t mang l¤i hi»u qu£ cao v· thời song tr¶n GPU. gian t½nh to¡n. Đặc bi»t tr¶n £nh màu RGB, thời gian t½nh to¡n đã gi£m Luªn ¡n sû dụng phương ph¡p thực nghi»m để chùng minh t½nh đúng đắn tới hơn 99% so với c¡c thuªt to¡n như thuªt to¡n t½nh to¡n trực ti¸p cõa c¡c phương ph¡p đề xu§t. Sû dụng c¡c ngôn ngú lªp C++ và C# để cài (Thuªt to¡n 2.1). Điểm đặc bi»t trong đề xu§t này, độ ch½nh x¡c ph¡t đặt c¡c thuªt to¡n. Sû dụng bë dú li»u m¨u do Pháng th½ nghi»m khoa học và hi»n c¡c điểm £nh dị thường cõa thuªt to¡n không thay đổi so với thuªt công ngh» quèc pháng (DSTL)- Vương quèc Anh cung c§p [23] và dú li»u do to¡n t½nh to¡n trực ti¸p, đây là điều h¸t sùc quan trọng khi ¡p dụng hé NCS thu thu thªp làm dú li»u nguồn để đánh gi¡ c¡c thuªt to¡n đã đề xu§t. trñ công t¡c t¼m ki¸m cùu n¤n. 3. Bè cục luªn ¡n: Luªn ¡n được tê chùc như sau: mở đầu; 3 chương nëi dung; k¸t luªn và hướng nghi¶n cùu ti¸p theo; danh mục c¡c công tr¼nh công bè và tài li»u tham kh£o. 2 23
5. Thuªt to¡n 3.5: Ph¡t hi»n c¡c điểm £nh dị thường sû dụng kỹ thuªt nhóm c¡c điểm £nh cùng gi¡ trị và t½nh to¡n song song (gọi Chương 1 t­t là GP-PC). input: X: ma trªn c¡c điểm £nh, G: danh s¡ch nhóm c¡c điểm Têng quan v· ph¡t hi»n dị thường £nh, L: sè k¶nh phê, h: b«ng thông, ϵ: h¬ng sè để tr¶n £nh vi¹n th¡m quang học K(u) 6= 0, η: ngưỡng ph¡t hi»n dị thường. 1.1 Ảnh vi¹n th¡m quang học output: anomaly_value: gi¡ trị dị thường cõa c¡c điểm £nh. Vi¹n th¡m (Remote sensing) là khoa học thu nhªn thông tin v· mët vªt thº, 1 X0 ma trªn c¡c điểm £nh sau khi làm trơn; mët vùng, hoặc mët hi»n tượng qua ph¥n t½ch dú li»u thu được bởi phương ti»n 2 S tªp c¡c điểm £nh đặc trưng; không ti¸p xúc với vªt, vùng hoặc hi»n tượng khi kh£o s¡t [67]. Hiºu đơn gi£n, 3 B tªp hñp c¡c điểm £nh n¬m trong c¡c cûa sê l§y c¡c điºm vi¹n th¡m là th«m dá tø xa v· mët đối tượng hoặc mët hi»n tưñng mà không trong S làm t¥m; có sự ti¸p xúc trực ti¸p với đối tượng hoặc hi»n tượng đó. Điều này thực hi»n 4 r h × ϵ; được do c¡c vªt thº kh¡c nhau h§p thụ và ph¡t ra bùc x¤ điện tø (photon) theo 5 id blockDim:x ∗ blockIdx:x + threadIdx:x; c¡ch đặc trưng cõa thành ph¦n hóa học c§u t¤o n¶n nó. N¸u đo n«ng lượng 6 for i 1 to jG[id]j do cõa bùc x¤ này b¬ng mët thi¸t bị theo bước sóng, k¸t qu£ thu được là t½n hi»u 7 if X'[G[id][i]] 2 B then quang phê và như vªy, quang phê có thº được sû dụng để mô t£ đặc trưng cho 8 P SearchGroupPixels(G, X'[G[id][i]],r); b§t kỳ vªt li»u nào. Sự k¸t hñp giúa quang phê, công ngh» h¼nh £nh và phương ph¡p để thu thªp thông tin quang phê tr¶n c¡c khu vực rëng lớn được gọi là 9 sum_ker 0; quang phê h¼nh £nh. 10 for j 1 to jP j do 11 for l 1 to jP [j]j do 1.1.1 Phê cõa £nh vi¹n th¡m quang học 12 mul 1; Sensor giú nhi»m vụ thu nhªn c¡c n«ng lượng bùc x¤ do vªt thº ph£n x¤, 13 for d 1 to L do t¿ sè giúa n«ng lượng ph£n x¤ và n«ng lượng tới là mët hàm cõa bước sóng. Gi¡ trị ph£n x¤ s³ thay đổi theo gi¡ trị bước sóng đối với h¦u h¸t c¡c vªt li»u 14 mul X0[G[id][i]][d] − X0[P [j][l]][d] do n«ng lượng ở méi bước sóng nh§t định s³ t¡n x¤ hoặc h§p thụ ở c¡c mùc mul × K ; h độ kh¡c nhau. Đường vãng xuèng cõa c¡c đường cong quang phê đánh d§u d£i bước sóng dao động mà vªt li»u h§p thụ n«ng lượng tới. C¡c đặc điểm này 15 sum_ker sum_ker + mul; thường được gọi là d£i h§p thụ. H¼nh d¤ng têng thº, vị tr½, kh£ n«ng h§p thụ 16 if sum_ker=N ≤ η then cõa đường cong quang phê trong nhi·u trường hñp có thº được sû dụng để x¡c định và ph¥n bi»t c¡c vªt li»u kh¡c nhau. 17 atomicAdd(&anomaly_valalue[G[id][i]],1); 1.1.2 C¡c lo¤i £nh vi¹n th¡m quang học 18 else Có ba lo¤i £nh vi¹n th¡m quang học, đó là: £nh toàn s­c (£nh ch¿ có mët 19 atomicAdd(&anomaly_valalue[G[id][i]],0); k¶nh phê); £nh đa phê [102] và £nh si¶u phê [15, 36]. 20 else 1.1.3 C§u trúc dú li»u cõa £nh vi¹n th¡m quang học 21 atomicAdd(&anomaly_valalue[G[id][i]],0); Ảnh đa phê, si¶u phê được lưu trú dưới d¤ng mët file thèng nh§t bao gồm c¡c điểm £nh được tê chùc thành mët ma trªn, méi mët điểm £nh là mët vector 22 3
6. có k½ch thước b¬ng với sè k¶nh phê để lưu trú phê ph£n x¤ cõa tøng k¶nh phê Thuªt to¡n 3.4: Ph¡t hi»n c¡c điểm £nh dị thường sû dụng kỹ hoặc méi mët k¶nh phê được lưu như là mët £nh đen tr­ng. Tùy thuëc vào thuªt nhóm c¡c điểm £nh cùng gi¡ trị và t½nh to¡n đa luồng (gọi định d¤ng cõa tøng kiºu file £nh s³ có nhúng c¡ch để lưu trú kh¡c nhau. t­t là GP-MC). 1.2 Bài to¡n ph¡t hi»n dị thường tr¶n £nh vi¹n th¡m quang input: X, G, startindex, endindex, L, h, ϵ, η. học phục vụ công t¡c t¼m ki¸m cùu n¤n output: C1, C2. 1.2.1 Kh¡i ni»m dị thường 1 G CreateGroupPixels(X,N,L); C¡c điểm £nh dị thường tr¶n £nh đa phê, si¶u phê được x¡c định là nhúng 2 X0 ma trªn c¡c điểm £nh sau khi làm trơn điểm £nh có phê (hoặc màu s­c) nêi bªt hoặc kh¡c bi»t nhi·u so với nhúng 3 S tªp c¡c điểm £nh đặc trưng điểm £nh l¥n cªn, nhúng điểm £nh này thưa thớt và hi¸m khi đại di»n cho £nh. 4 B tªp hñp c¡c điểm £nh n¬m trong c¡c cûa sê l§y c¡c điºm Nh¼n chung, c¡c d§u hi»u dị thường là r§t nhỏ v· mặt không gian và tồn t¤i trong S làm t¥m; với x¡c su§t th§p trong mët c£nh £nh. 5 C1 ;; C2 ;; r h × ϵ; 1.2.2 Công t¡c t¼m ki¸m cùu n¤n 6 for i startindex to endindex do T¼m ki¸m cùu n¤n là toàn bë c¡c ho¤t động cõa lực lượng cùu n¤n, cùu hë, 7 for j 1 to jG[i]j do được ti¸n hành khi có mët sự cè, tai n¤n x£y ra nh¬m t¼m ki¸m và gi£i cùu 8 if X'[G[i][j]] 2 B then mët người nào đó đang gặp n¤n, bị m§t t½ch, bị thương, ở mët khu vực xa xôi 9 P SearchGroupPixels(G, X'[G[i][j]],r); //theo hoặc khó ti¸p cªn, ch¯ng h¤n như ở røng, núi, sa m¤c hoặc tr¶n biºn. Tr¶n th¸ Thuªt to¡n 3.2 giới, đặc bi»t là c¡c nước sở húu công ngh» v» tinh, vi»c ùng dụng công ngh» 10 sum_ker 0; vi¹n th¡m phục vụ công t¡c t¼m ki¸m cùu n¤n đã được ¡p dụng và mang l¤i 11 for l 1 to jP j do hi»u qu£ to lớn. Mët sè nước ph¡t triºn như Mỹ, Nhªt, Nga đ·u có c¡c trung 12 for f 1 to jP [l]j do t¥m quèc gia hoặc Bë c¡c t¼nh huèng kh©n c§p ph£n ùng nhanh với c¡c t¼nh 13 mul 1; huèng th£m họa, thi¶n tai trong đó công ngh» thông tin v» tinh, thông tin địa lý và thông tin vi¹n th¡m là c¡c hñp ph¦n không thº thi¸u. Đi k±m với nó là c¡c 14 for d 1 to L do ph¥n h» ph¦n m·m xû lý thông tin địa lý, £nh vi¹n th¡m k¸t xu§t c¡c thông 15 mul X0[G[i][j]][d] − X0[P [l][f]][d] tin húu ½ch góp ph¦n đẩy nhanh qu¡ tr¼nh ph£n ùng với th£m họa, t¼m ki¸m mul × K ; cùu n¤n và gi£m nhẹ thi»t h¤i. Theo Wallacea và c¡c cëng sự [123], h» thèng h Sarsat k¸t hñp với đối t¡c Cospas cõa Nga và NASA đã đạt được thành công 16 sum_ker sum_ker + mul; lớn khi đã gi£i cùu thành công hơn 8.000 người tr¶n th¸ giới trong 16 n«m ho¤t động. C¡c cuëc t¼m ki¸m hi»n đang được thực hi»n với sự hé trñ cõa thông tin 17 if sum_ker=N ≤ η then vô tuy¸n, c£m bi¸n quang học và radar trong c¡c n·n t£ng tr¶n không. 18 C2 C2 [ fX[G[i][j]]g; 1.2.3 Ph¡t biºu bài to¡n 19 else Bài to¡n ph¡t hi»n dị thường tr¶n £nh vi¹n th¡m quang học được ph¡t biºu 20 C1 C1 [ fX[G[i][j]]g; như sau: N L×N 21 else - Cho mët £nh đa phê, si¶u phê có N điểm £nh và L k¶nh phê: X = fxigi=1 2 R . L 22 C1 C1 [ fX[G[i][j]]g; - X²t mët điểm £nh xi 2 R ; i = 1; 2; :::; N, h¢y ph¥n đúng xi vào mët trong hai lớp là lớp "dị thường" hoặc lớp "b¼nh thường". 4 21
7. Thuªt to¡n 3.3: Ph¡t hi»n c¡c điểm £nh dị thường sû dụng kỹ 1.3 Mët sè ti¸p cªn v· ph¡t hi»n dị thường thuªt nhóm c¡c điểm £nh cùng gi¡ trị và c¥y kd-tree (gọi t­t là Dựa tr¶n c¡c phương ph¡p ph¡t hi»n c¡c điểm £nh dị thường tr¶n £nh đa GP-KDT). phê, si¶u phê kh¡c nhau, n«m nhóm phương ph¡p được ph¥n chia như sau: 1. Phương ph¡p dựa tr¶n mô h¼nh x¡c su§t thèng k¶: tr¶n quan điểm lý input: X, N, L, h, ϵ, K(u), η. thuy¸t, v§n đề ph¡t hi»n c¡c điểm £nh dị thường có thº được xem như là v§n output: C , C . 1 2 đề ph¥n lớp nhị ph¥n [79], có nghĩa r¬ng mục đích cõa nhi»m vụ này là ph¥n lo¤i 1 G CreateGroupPixels(X,N,L); c¡c điểm £nh vào mët trong hai lớp "dị thường" hoặc "b¼nh thường". Trong 2 X0 ma trªn c¡c điểm £nh sau khi làm trơn phương ph¡p ph¡t hi»n c¡c điểm £nh dị thường dựa tr¶n mô h¼nh x¡c su§t 3 S tªp c¡c điểm £nh đặc trưng thèng k¶ có c¡c thuªt to¡n như: thuªt to¡n ph¡t hi»n dị thường Reed-Xiaoli 4 B tªp hñp c¡c điểm £nh n¬m trong c¡c cûa sê l§y c¡c điºm [96] và c¡c bi¸n thº cõa nó [16, 18, 25, 39, 42, 51, 58, 69, 88, 98, 125]; m¡y dá trong S làm t¥m; dị thường theo phương ph¡p thèng k¶ bªc cao [17, 38, 97]; ước lưng mªt độ 5 C1 ;; C2 ;; r h × ϵ; x¡c su§t phi tham sè n·n [12, 83, 120, 121, 135]. 6 for i 1 to jGj do 2. Phương ph¡p dựa tr¶n ph¥n cụm và ph¥n đoạn: c¡ch ti¸p cªn này là ph¥n 0 7 query X [G[i][1]]; cụm c¡c điểm £nh hoặc là ph¥n đoạn không gian để thu được b£n đồ chõ đề 8 K SearchGroupPixels(G, query,r); theo phương ph¡p lượng tû hóa biºu đồ cõa c¡c thành ph¦n ch½nh h¼nh £nh. 9 T CreateKDTree(L,|K|,L); Trong méi cụm hoặc đoạn không gian, dú li»u được cho là có ph¥n phèi theo 10 for j 1 to jG[i]j do mô h¼nh hén hñp Gaussian. Sau đó, có thº sû dụng phương ph¡p đo kho£ng 11 if X'[G[i][j]] 2 B then c¡ch Mahalanobis để kiºm tra kho£ng c¡ch tø PUT đến t¥m cõa méi cụm. 12 P T.SearchKdTree(X'[G[i][j]],r); Điểm £nh vượt qu¡ ngưỡng được coi là dị thường. Phương ph¡p dựa tr¶n ph¥n 13 for l 1 to jP j do cụm có c¡c thuªt to¡n như: thuªt to¡n ph¥n cụm trựa tr¶n b£n đồ tự tê chùc 14 mul_ker 1; [27, 93], thuªt to¡n h¼nh thành c¡c cụm ban đầu theo bước đệm đầu ti¶n, sau 15 for d 1 to L do đó b¬ng c¡ch cªp nhªt đệ quy c¡c tham sè c¡c cụm trong qu¡ tr¼nh thu nhªn 16 mul_ker h¼nh £nh [110], phương ph¡p Bayesian để ti¸p cªn dùng cho ph¥n lớp không X0[G[i][j]][d] − P [l][d] gi¡m s¡t [7, 43]. Phương ph¡p dựa tr¶n ph¥n đoạn có c¡c thuªt to¡n: ph¥n mul_ker × K( ); h vùng module dựa tr¶n khèi b¬ng c¡ch sû dụng ph¥n t½ch thành ph¦n ch½nh 17 sum_ker sum_ker + mul_ker; [64], kỹ thuªt ph¡t hi»n dựa tr¶n ph¥n kỳ thưa thớt cục bë [131]. sum_ker 3. Phương ph¡p dựa tr¶n bi¸n đổi phi tuy¸n: v§n đề ch½nh với c¡c kỹ thuªt 18 if ≤ η then ph¡t hi»n dị thường dựa tr¶n thèng k¶ là gi£ định v· t½nh tuy¸n t½nh cõa n·n. N 19 C2 C2 [ fX[G[i][j]]g; Trong thực t¸, sự ph¥n bè cõa hàm mªt độ x¡c su§t cõa h¼nh £nh đa phê, si¶u phê là r§t xa so với ph¥n phèi chu©n. Do đó, c¡c kỹ thuªt ph¡t hi»n dị thường 20 else phi tuy¸n được đ· xu§t sû dụng c¡c chi¸n lược h¤t nh¥n. Kỹ thuªt cơ b£n cõa 21 C C [ fX[G[i][j]]g; 1 1 phương ph¡p này ch½nh là sû dụng dụng mët hàm ¡nh x¤ phi tuy¸n để ¡nh x¤ 22 else dú li»u tø không gian có sè chi·u th§p sang không gian có sè chi·u r§t cao. Điều này cho ph²p lớp n·n và lớp mục ti¶u được rời r¤c, t¡ch xa nhau d¨n đến 23 C1 C1 [ fX[G[i][j]]g; vi»c ph¡t hi»n c¡c điểm £nh dị thường hi»u qu£ hơn. Sau khi dú li»u đã được 20 5
8. ¡nh x¤ sang không gian N chi·u; có thº sû dụng RX để ph¡t hi»n dị thường, Thuªt to¡n 3.2: T¼m ki¸m nhúng nhóm điểm £nh n¬m trong do đó thuªt to¡n Kernel – RX [59] được đề xu§t. Mët hướng ti¸p cªn kh¡c là b¡n k½nh r, t¥m là PUT (SearchGroupPixels) sû dụng ước lượng vùng hé trñ n·n, có nghĩa r¬ng s³ t¼m mët si¶u c¦u k½n tèi input: A: m£ng chùa nhóm điểm £nh, query: PUT, r: b¡n k½nh. thiºu chùa c¡c điểm £nh b¼nh thường, nhúng điểm £nh nào n¬m ngoài si¶u c¦u k½n này là nhúng điểm £nh dị thường [9]. output: L: danh s¡ch nhóm c¡c điểm £nh c¦n t¼m ki¸m. 4. Phương ph¡p dựa tr¶n bi¸n đổi tuy¸n t½nh: ngược với với phương ph¡p 1 L ;; dựa tr¶n bi¸n đổi phi tuy¸n, phương ph¡p dựa tr¶n bi¸n đổi tuy¸n t½nh sû dụng 2 index: ch¿ sè cõa nhóm chùa query, t½nh theo công thùc (3.1); ph¥n t½ch thành ph¦n độc lªp ti¸p cªn theo c¡ch ngược l¤i là chi¸u dú li»u si¶u 3 L L [ fA[index]g phê có chi·u cao vào không gian dú li»u chi·u th§p, trong khi v¨n giú l¤i nhúng 4 for i index − 1 to 1 do thông tin quan trọng [18, 26, 50]. Ngoài ra, sû dụng phương ph¡p biºu di¹n 5 if kho£ng c¡ch tø query đến A[i] tr¶n chi·u dú li»u thù nh§t h¤ng th§p và biºu di¹n thưa, c¡c phương ph¡p này gi£ định r¬ng t½n hi»u phê v¨n nhỏ hơn hoặc b¬ng r then có thº được biºu di¹n b¬ng c¡ch sû dụng tø điển. Với c¡c ràng buëc kh¡c nhau 6 L L [ fA[i]g; v· c¡c h» sè biºu di¹n có thº thu được c¡c phương ph¡p ph¡t hi»n dị thường 7 else kh¡c nhau [63, 68, 119, 127,137]. 8 break; 5. Phương ph¡p dựa tr¶n học m¡y: trong thời gian g¦n đây, phương ph¡p học s¥u đã thu hút sự chú ý cõa c¡c nhà khoa học và ¡p dụng nó ngày càng 9 for i index + 1 to jAj do nhi·u trong ph¥n t½ch £nh si¶u phê. Li và c¡c cëng sự [65] đã đề xu§t sû dụng 10 if kho£ng c¡ch tø query đến A[i] tr¶n chi·u dú li»u thù nh§t m¤ng nơ-ron t½ch chªp để ph¡t hi»n c¡c điểm £nh dị thường vào n«m 2017. v¨n nhỏ hơn hoặc b¬ng r then Yan và c¡c cëng sự [128] đề xu§t phương ph¡p 2SHyperNet (two-stage deep 11 L L [ fA[i]g; learning – base hyperspectral neural network) b¬ng c¡ch sû dụng mët m¤ng 12 else học s¥u hai giai đoạn tr¶n £nh si¶u phê để ph¡t hi»n người tr¶n biºn. 13 break; 1.4 Ti¶u ch½ đánh gi¡ độ ch½nh x¡c cõa c¡c thuªt to¡n ph¡t hi»n dị thường Để đánh gi¡ đë ch½nh x¡c cõa mët thuªt to¡n ph¡t hi»n dị thường xem nó tèt hay x§u là mët v§n đề khó, bởi v¼ nhúng điểm £nh dị thường là nhúng GPU CUDA cũng do Michailidis và c¡c cëng sự đề xu§t t¤i [87]. Cuèi cùng, điểm £nh hi¸m. H¦u h¸t c¡c thuªt to¡n đưa ra gi¡ trị dị thường và ngưỡng tương ùng với méi £nh, thực thi c¡c thuªt to¡n do luªn ¡n đề xu§t, bao gồm: để k¸t luªn c¡c điểm £nh có là dị thường hay không. Vi»c chọn ngưỡng s³ GP-KTD, GP-MC và GP-PC. Sû dụng hàm h¤t nh¥n Hypercube với b«ng £nh hưởng đến vi»c bỏ sót (dương t½nh gi£) hoặc nh¦m l¨n với c¡c điểm £nh thông cè định h = 10 để kiºm nghi»m c¡c thuªt to¡n tr¶n 3 £nh này. Thời gian không ph£i là dị thường (¥m t½nh gi£). Trong công bó "Facing Imbalanced Data thực thi cõa c¡c thuªt to¡n được thº hi»n tr¶n B£ng 3.1. Recommendations for the Use of Performance Metrics" [53], Jeni và c¡c cëng So s¡nh thời gian t½nh to¡n giúa c¡c ch¸ độ đơn luồng tr¶n CPU, đa luồng sự đã sû dụng mët sè độ đo như Accuracy, F-score, AUC, Precision-Recall để tr¶n CPU và song song tr¶n GPU chúng ta th§y r¬ng: ở ch¸ độ đơn luồng, tr¶n đánh gi¡ độ ch½nh x¡c cõa c¡c thuªt to¡n nhªn bi¸t c¡c đơn vị hành đëng tr¶n B£ng 3.1 thº hi»n thuªt to¡n GP-KDT đã nhanh hơn Thuªt to¡n 2.1 ½t nh§t khuôn mặt cõa c¡c tªp dú li»u m§t c¥n b¬ng; k¸t qu£ cho th§y r¬ng, ch¿ có 66,10% (tr¶n £nh 6010_1_2_M) và cao nh§t là 99,999% (tr¶n £nh 6010_1_2). AUC ph£n ¡nh ch½nh x¡c độ ch½nh x¡c cõa c¡c thuªt to¡n, c¡c độ đo cán l¤i Trong ch¸ độ đa luồng tr¶n CPU, tr¶n B£ng 3.1 thº hi»n thuªt to¡n GP-MC đã đều bị suy gi£m do dú li»u m§t c¥n b¬ng, đặc bi»t là trong c¡c trường hñp nhanh hơn thuªt to¡n Intel TBB ½t nh§t 93,55% (tr¶n £nh 6010_1_2_M) và 6 19
9. 3.4 T½nh to¡n PDF và ph¥n lo¤i c¡c điểm £nh m§t c¥n b¬ng nghi¶m trọng. V¼ vªy, độ đo AUC được dùng để kiºm nghi»m độ T½nh to¡n PDF cho PUT là chùc n«ng ch½nh và quan trọng nh§t cõa thuªt ch½nh x¡c ph¡t hi»n c¡c điểm £nh dị thường cõa c¡c thuªt to¡n. to¡n ph¡t hi»n c¡c điểm £nh dị thường tr¶n £nh đa phê, si¶u phê. Ch½nh v¼ 1.5 Th¡ch thùc và hướng ph¡t triºn vªy, thời gian để ước lượng hàm mªt độ x¡c su§t theo phương ph¡p phi tham Th¡ch thùc đầu ti¶n li¶n quan đến vi»c t«ng tỷ l» ph¡t hi»n trong khi gi£m sè cho PUT cũng chi¸m ph¦n lớn thời gian xû lý cõa thuªt to¡n. Điểm m§u tỷ l» b¡o động gi£. Th¡ch thùc thù hai li¶n quan đến vi»c ph¡t hi»n dị thường chèt ti¶u tèn nhi·u thời gian trong phương ph¡p ước lượng mªt độ x¡c su§t phi với c¡c h¼nh d¤ng và k½ch cỡ kh¡c nhau. Trong thực t¸, k½ch thước cõa dị thường tham sè là t¼m ki¸m nhúng điểm dú li»u thỏa m¢n điều ki»n K(u) 6= 0. Thuªt có thº dao động tø mët ph¦n điểm £nh đến vài điểm £nh và vi»c ph¡t hi»n c¡c to¡n để t¼m nhúng nhóm điểm £nh là ùng vi¶n tham gia t½nh to¡n PDF cho dị thường với k½ch thước kh¡c nhau cùng mët kỹ thuªt ph¡t hi»n dị thường là PUT được thº hi»n trong Thuªt to¡n 3.2. mët th¡ch thùc lớn. Th¡ch thùc thù ba, đó là tèc độ t½nh to¡n, c¡c kỹ thuªt Để t½nh to¡n PDF và ph¥n lo¤i c¡c điểm £nh, luªn ¡n đã x¥y dựng c¡c thuªt ph¡t hi»n dị thường có thời gian t½nh to¡n g¦n với thời gian thực s³ r§t húu to¡n: ph¡t hi»n c¡c điểm £nh dị thường sû dụng kỹ thuªt nhóm c¡c điểm £nh ½ch trong c¡c ùng dụng thực t¸, đặc bi»t là trong công t¡c t¼m ki¸m cùu n¤n. cùng gi¡ trị và c¥y kd-tree (Thuªt to¡n 3.3, gọi t­t là GKDT); ph¡t hi»n c¡c Cuèi cùng, dù có nhi·u bë dú li»u có s®n cho cëng đồng khoa học với mục đích điểm £nh dị thường sû dụng kỹ thuªt nhóm c¡c điểm £nh cùng gi¡ trị và t½nh ph¥n lớp, v¨n cán thi¸u bë dú li»u cho mục đích ph¡t hi»n dị thường. T½nh to¡n đa luồng tr¶n CPU (Thuªt to¡n 3.4, gọi t­t là GMCPU); ph¡t hi»n c¡c kh£ dụng cõa c¡c bë dú li»u được chia s´ s³ c£i thi»n đáng kº vi»c nghi¶n cùu điểm £nh dị thường sû dụng kỹ thuªt nhóm c¡c điểm £nh cùng gi¡ trị và t½nh trong lĩnh vực này, cho ph²p so s¡nh tèt hơn giúa c¡c phương ph¡p theo c¡c to¡n song song tr¶n GPU (Thuªt to¡n 3.5, gọi t­t là GPGPU); kịch b£n kh¡c nhau. 3.5 Đánh gi¡ độ phùc t¤p cõa c¡c thuªt to¡n 1.6 K¸t luªn - Thuªt to¡n ph¡t hi»n c¡c điểm £nh dị thường sû dụng kỹ thuªt nhóm c¡c Mët sè v§n đề đã được tr¼nh bày trong chương này gồm: điểm £nh và c¥y kd-tree là O(N 2), M là sè nhóm c¡c điểm £nh. ˆ Thù nh§t, tr¼nh bày mët sè ki¸n thùc têng quan v· £nh vi¹n th¡m quang học và ùng dụng £nh vi¹n th¡m quang học phục vụ công t¡c t¼m ki¸m - Thuªt to¡n ph¡t hi»n c¡c điểm £nh dị thường sû dụng kỹ thuªt nhóm c¡c cùu n¤n. điểm £nh và t½nh to¡n đa luồng tr¶n CPU hoặc song song tr¶n GPU là O(N 2). ˆ Thù hai, ph¡t biºu v· bài to¡n ph¡t hi»n dị thường (ngo¤i lai) tr¶n £nh 3.6 Thû nghi»m và đánh gi¡ k¸t qu£ đề xu§t vi¹n th¡m quang học, là cơ sở để nghi¶n cùu t¼m c¡c gi£i ph¡p để gi£i 3.6.1 Dú li»u thû nghi»m quy¸t bài to¡n này. ˆ Thù ba, nghi¶n cùu c¡c c¡ch ti¸p cªn tr¶n th¸ giới v· bài to¡n ph¡t hi»n Dú li»u thû nghi»m gồm ba lo¤i £nh kh¡c nhau, lo¤i £nh đầu ti¶n là £nh dị thường tr¶n £nh vi¹n th¡m quang học. Tr¶n cơ sở đó, luªn ¡n đã ch¿ màu 3 k¶nh phê có t¶n là 6010_1_2 [24], lo¤i £nh thù 2 là £nh đa phê 8 k¶nh ra nhúng k¸t qu£ đạt được và n¶u l¶n ba th¡ch thùc c¦n được gi£i quy¸t. phê có t¶n là 6010_1_2_M [24], và lo¤i £nh thù 3 là £nh si¶u phê 224 k¶nh phê có t¶n là Salinas [47]. 3.6.2 Phương ph¡p thû nghi»m Tương ùng với méi mët £nh đã tr¼nh bày ở tr¶n, ch¤y c¡c thuªt to¡n: Thuªt to¡n t½nh to¡n trực ti¸p cho c¡c điểm £nh (KDE) theo Thuªt to¡n 2.1; thuªt to¡n t½nh to¡n đa luồng tr¶n CPU sû dụng ngôn ngú lªp tr¼nh Intel TBB do Michailidis và c¡c cëng sự đề xu§t t¤i [86]; thuªt to¡n t½nh to¡n song song tr¶n 18 7
10. thỏa m¢n điều ki»n K(u) 6= 0; t½nh to¡n đa luồng tr¶n CPU gièng như đề xu§t Chương 2 cõa Michailidis và c¡c cëng sự trong [86] hoặc t½nh to¡n song song tr¶n GPU CUDA như trong đề xu§t cõa Michailidis và c¡c cëng sự [87]. Kỹ thuªt n¥ng cao độ ch½nh x¡c ph¡t hi»n 3.3 Thuªt to¡n nhóm c¡c điểm £nh và s­p x¸p dị thường tr¶n £nh vi¹n th¡m quang học Do gi¡ trị cõa c¡c điểm £nh thông thường được lưu trú ở d¤ng sè nguy¶n và gi¡ trị nhỏ hơn hoặc b¬ng 10bit n¶n để gi£m độ phùc t¤p t½nh to¡n, s³ x¥y 2.1 Giới thi»u chung dựng mët m£ng hai chi·u, gọi là m£ng A. Để x¡c định vị tr½ cõa c¡c điểm £nh Thuªt to¡n ph¡t hi»n c¡c điểm £nh dị thường dựa tr¶n KDE [120, 121] là trong m£ng A, thực hi»n t½nh to¡n gi¡ trị tê hñp 3 k¶nh phê theo công thùc: mët trong nhúng phương ph¡p ph¡t hi»n c¡c điểm £nh dị thường dựa tr¶n mô 3 X 3−d h¼nh x¡c su§t thèng k¶, thuªt to¡n này đã được x¥y dựng và kiºm chùng trong indexi = (m + 1) × xid; i = 1; 2; :::; N (3.1) nhúng n«m g¦n đây, trong c¡c nghi¶n cùu [12, 83, 135] đã cho th§y được độ d=1 ch½nh x¡c trong vi»c ph¡t hi»n c¡c điểm £nh dị thường tr¶n £nh đa phê, si¶u trong đó, phê và độ ch½nh x¡c ph¡t hi»n dị thường cõa nó đã vượt RXD. Ch½nh v¼ lý do m = max xid; d = 1; 2; 3; i = 1; 2; :::; N (3.2) đó, thuªt to¡n ph¡t hi»n c¡c điểm £nh dị thường dựa tr¶n KDE được lựa chọn là gi¡ trị lớn nh§t cõa ba k¶nh phê đầu ti¶n cõa t§t c£ c¡c điểm £nh (thông để nghi¶n cùu và c£i ti¸n nh¬m t«ng độ ch½nh x¡c ph¡t hi»n c¡c điểm £nh dị thường, đối với £nh lưu trú 8bit/1 k¶nh m = 256, 10bit/k¶nh m = 1024, ). indexi thường tr¶n £nh đa phê, si¶u phê ùng dụng cho công t¡c t¼m ki¸m cùu n¤n. tương ùng với ch¿ sè tr¶n chi·u thù nh§t cõa m£ng A. Thuªt to¡n nhóm được 2.2 Thuªt to¡n ph¡t hi»n dị thường dựa tr¶n KDE tr¼nh bày cụ thº t¤i Thuªt to¡n 3.1. Ph¡t hi»n c¡c điểm £nh dị thường tr¶n £nh đa phê, si¶u phê có thº được coi là nhi»m vụ ph¥n c¡c điểm £nh vào mët trong hai lớp "b¼nh thường" (lớp Thuªt to¡n 3.1: Nhóm c¡c điểm £nh (CreateGroupPixels) C1) hoặc "dị thường" (lớp C2). X²t mët £nh có L k¶nh phê, £nh này được t¤o input: X: ma trªn cõa c¡c điểm £nh, N: sè điểm £nh. thành tø tªp hñp gồm N điểm £nh X = (x1; x2; :::; xN ). Quan s¡t thù i tr¶n X là output: A: m£ng chùa c¡c nhóm điểm £nh. x = (x ; x ; :::; x )T ; i = 1; 2; :::; N, để ph¥n x vào lớp C hoặc C theo phương i i1 i2 iL i 1 2 1 m gi¡ trị lớn nh§t cõa ba k¶nh phê đầu ti¶n cõa t§t c£ c¡c ph¡p thèng k¶ là gi£i quy¸t v§n đề kiºm nghi»m gi£ thuy¸t nhị ph¥n b¬ng c¡ch điểm £nh (t¼m M theo công thùc (3.2)); sû dụng quy t­c Neyman-Pearson dựa tr¶n tỷ l» kh£ n«ng (LR) cõa hàm mªt 2 A sizeof((M + 1)3); //Khởi t¤o m£ng A độ s¡c xu§t có điều ki»n theo hai gi£ thuy¸t: 3 for i 1 to N do ( H0 : xi 2 C1; 4 index 0; H(xi) = i = 1; 2; :::; N (2.1) H1 : xi 2 C2: 5 for d 1 to 3 do 3−d Theo quy t­c Neyman-Pearson, ta có: 6 index index + (M + 1) × X[i][d]; 7 H1 A[index] A[index] [ fig; ^ fXjH1 (xi) ≥ ^NP (xi) = η; i = 1; 2; :::; N (2.2) f^ (x ) < XjH0 i Do sû dụng phương ph¡p tê hñp 3 k¶nh phê theo công thùc (3.1) để t¤o ch¿ H 0 sè cõa nhóm n¶n hiºn nhi¶n c¡c nhóm cõa c¡c điển £nh đã được s­p x¸p t«ng Trong đó f^(·) là hàm mªt độ x¡c su§t có điều ki»n, η là ngưỡng th½ch hñp để d¦n theo chi·u thù nh§t cõa dú li»u. Và như vªy, chúng ta không ph£i ti¶u tèn ph¥n xi vào lớp C1 hoặc C2. Tuy nhi¶n, trong thực t¸, c¡c tham sè để t½nh to¡n th¶m thời gian để s­p x¸p l¤i danh s¡ch nhóm c¡c điºm £nh. 8 17
11. c¡c hàm mªt độ x¡c su§t có điều ki»n trong công thùc (2.2) thường không Chương 3 có s®n bởi v¼ chúng ta thi¸u ki¸n thùc lớp "dị thường", hoàn toàn chưa có c¡c nghi¶n cùu thèng k¶ v· nó, hơn núa c¡c điểm £nh dị thường có gi¡ trị phê b§t Kỹ thuªt t«ng tèc độ ph¡t hi»n dị thường kỳ, ch¿ phụ thuëc vào c£nh cõa £nh, chúng là nhúng điểm độc lªp hoặc cụm điểm £nh nhưng có k½ch thước r§t nhỏ so với £nh và có mªt độ thưa thớt. V¼ tr¶n £nh vi¹n th¡m quang học ^ vªy, chúng ta có thº gi£ định r¬ng fXjH1 (xi) là mët h¬ng sè, khi đó công thùc 3.1 Giới thi»u chung (2.2) được rút ng­n thành: Công t¡c t¼m ki¸m cùu n¤n là công vi»c khó kh«n và phùc t¤p, đòi hỏi sự H1 kh­t khe v· thời gian t¼m ki¸m. Thuªt to¡n IKDE cho th§y sự hi»u qu£, d¹ ^ ≥ ^(xi) = −logffXjH (xi)g η; i = 1; 2; :::; N (2.3) dàng cài đặt, độ ch½nh x¡c ph¡t hi»n c¡c điểm £nh dị thường tèt. Tuy nhi¶n, 0 < độ phùc t¤p t½nh to¡n cõa thuªt to¡n này là O(LMN), d¨n đến vi»c ùng dụng H0 thuªt to¡n này vào trong công t¡c t¼m ki¸m cùu n¤n là không kh£ thi. Để ¡p ^ dụng thuªt to¡n IKDE nh¬m ph¡t hi»n c¡c điểm £nh dị thường phục vụ trong Do mªt độ x¡c su§t cõa dú li»u n·n fXjH0 (xi) chưa được bi¸t n¶n nó ph£i được công t¡c t¼m ki¸m cùu n¤n, luªn ¡n đề xu§t gi£i ph¡p có thº gi£m thời gian ước t½nh tø dú li»u có s®n. Với gi£ thuy¸t r¬ng, c¡c điểm £nh dị thường r§t ½t, t½nh to¡n tới hơn 99% so với thuªt to¡n KDE và có thº ùng dụng ngoài thực t¸. mªt độ thưa n¶n t§t c£ c¡c điểm £nh xi 2 X; i = 1; 2; :::; N có thº được sû dụng 3.2 T«ng tèc độ t½nh to¡n cõa thuªt to¡n IKDE cho ước t½nh này. Qua qu¡ t¼nh nghi¶n cùu cho th§y r¬ng, khi t½nh hàm mªt độ x¡c su§t Trong c¡c nghi¶n cùu [83, 120, 121, 135], c¡c t¡c gi£ đã sû phương ph¡p ước theo công thùc (2.4), vi»c t¼m nhúng điểm £nh trong ph¤m vi b«ng thông để t½nh mªt độ x¡c su§t phi tham sè để ước lượng mªt độ x¡c su§t cho điểm £nh x . Công thùc ước t½nh mªt độ h¤t nh¥n cõa dú li»u đa bi¸n được định nghĩa K(u) 6= 0 ti¶u tèn r§t nhi·u thời gian, nhúng điểm £nh n¬m ngoài b«ng thông s³ i trong [122] là: làm cho K(u) = 0 và như vªy s³ không làm thay đổi gi¡ trị cõa f^(·) trong công N ( L  ) 1 X Y 1 xid − xjd thùc (2.4) n¶n chúng ta s³ bỏ qua nhúng điểm £nh này. V¼ vªy, phương ph¡p f^(xi) = K (2.4) N hd hd đầu ti¶n nghĩ đến là làm th¸ nào để gi£m dú li»u tham gia t½nh to¡n mà không j=1 d=1 làm thay đổi độ ch½nh x¡c ph¡t hi»n c¡c điểm £nh dị thường cõa thuªt to¡n Trong đó, f^(·) gọi là hàm mªt độ x¡c su§t (PDF - Probability Density Function), IKDE. Lñi dụng sự gièng nhau tr¶n mi·n gi¡ trị cõa nhi·u điểm £nh tr¶n cùng R 1 K(u) được gọi là hàm nh¥n thỏa m¢n điều ki»n −∞ K(u)d(u) = 1 và hd là b«ng mët £nh, đặc bi»t là tr¶n £nh màu RGB, s³ nhóm nhúng điểm £nh này thành thông, N là sè điểm £nh, L là sè k¶nh phê. K(u) có thº là c¡c hàm nh¥n điển mët nhóm. Bước ti¸p theo, c¡c nhóm điểm £nh s³ được s­p x¸p, với mục đích h¼nh do Hardle tr¼nh bày trong [122]. Thuªt to¡n 2.1 được x¥y dựng để ph¥n để chọn nhanh c¡c nhóm điểm £nh có thº chùa c¡c điểm £nh thỏa m¢n điều c¡c điểm £nh vào mët trong hai lớp C1 và C2. ki»n K(u) 6= 0. Như vªy, bước ph¥n nhóm cơ b£n làm gi£m đáng kº sè lượng 2.3 Gi£i ph¡p t«ng độ ch½nh x¡c cõa thuªt to¡n ph¡t hi»n dú li»u c¦n t½nh to¡n, bước s­p x¸p c¡c nhóm điểm £nh s³ chọn nhanh được c¡c điểm £nh dị thường dựa tr¶n KDE nhúng nhóm điểm £nh trong đó có c¡c điểm £nh có thº làm thỏa m¢n điều Thuªt to¡n KDE ho¤t động theo nguy¶n t­c dựa tr¶n gi¡ trị cõa hàm mªt ki»n K(u) 6= 0. Nhúng nhóm điểm £nh không được lựa chọn để tham gia t½nh độ x¡c su§t để ph¥n lớp. N¸u điểm £nh đang x²t có mªt độ x¡c su§t th§p (nhỏ to¡n chúng ta không c¦n quan t¥m đến nó n¶n đã gi£m được khèi lượng dú hơn ngưỡng η), nó s³ được ph¥n v· lớp C và ngược l¤i. Trong khi đó, c¡c điểm li»u c¦n t½nh to¡n, gi£m được thời gian t½nh to¡n. Sau khi nhúng nhóm điểm 2 £nh là nhi¹u thường chi¸m mët ph¦n nhỏ trong £nh n¶n nó s³ được ph¥n vào £nh được lựa chọn để tham gia ước lượng PDF cho PUT, chúng ta có thº dùng lớp dị thường làm t«ng tỷ l» dương t½nh gi£, d¨n đến gi£m độ ch½nh x¡c ph¡t mët trong ba phương ph¡p: sû dụng c¥y kd-tree để t¼m nhanh nhúng điểm £nh hi»n dị thường cõa thuªt to¡n. 16 9
12. Thuªt to¡n 2.1: Ph¡t hi»n c¡c điểm £nh dị thường dựa tr¶n B£ng 2.1: Độ đo AUC cõa thuªt to¡n KDE và thuªt to¡n IKDE tr¶n 36 KDE (gọi t­t là Thuªt to¡n KDE) [118, 119] £nh gèc input: X: Ma trªn c¡c điểm £nh, N: sè điểm £nh, L: sè k¶nh phê, T¶n file £nh KDE IKDE T¶n file £nh KDE IKDE h: b«ng thông, η: ngưỡng ph¡t hi»n dị thường. Ảnh (a) 0,9981 0,9982 6110_3_1 0,9130 0,9220 output: C1, C2. Ảnh (b) 0,9969 0,9976 6110_3_1_A 0,7064 0,7074 1 C ;; C ;; 1 2 Ảnh (c) 0,9719 0,9883 6110_3_1_M 0,8673 0,8753 2 for i 1 to N do Ảnh (d) 0,9591 0,9600 6110_4_0 0,9263 0,9313 3 sum_ker 0; 4 for j 1 to N do Ảnh (e) 0,9887 0,9947 6110_4_0_A 0,8503 0,8533 5 mul_ker 1; Ảnh (f) 0,9996 0,9999 6110_4_0_M 0,9509 0,9529 6 for d 1 to L do 6010_1_2 0,9034 0,9114 6120_2_0 0,9082 0,9152 X[i][d] − X[j][d] 6010_1_2_A 0,7192 0,7262 6120_2_0_A 0,7758 0,7858 7 mul_ker mul_ker × K ; h 6010_1_2_M 0,8656 0,8726 6120_2_0_M 0,9278 0,9308 8 sum_ker sum_ker + mul_ker; 6090_2_0 0,8106 0,8196 6140_1_2 0,9177 0,9217 sum_ker 6090_2_0_A 0,9564 0,9664 6140_1_2_A 0,8350 0,8420 9 if ≤ η then N 6090_2_0_M 0,9693 0,9773 6140_1_2_M 0,9240 0,9302 10 C2 C2 [ fX[i]g; 6100_2_2 0,8466 0,8556 6170_0_4 0,8121 0,8181 11 else 6100_2_2_A 0,8519 0,8549 6170_0_4_A 0,9882 0,9912 6100_2_2_M 0,8726 0,8826 6170_0_4_M 0,9759 0,9819 12 C1 C1 [ fX[i]g; 6110_1_2 0,9272 0,9332 6170_2_4 0,8524 0,8574 6110_1_2_A 0,9480 0,9552 6170_2_4_A 0,9999 0,9999 6110_1_2_M 0,8940 0,9052 6170_2_4_M 0,9783 0,9803 Trong nghi¶n cùu v· t«ng độ ch½nh x¡c ph¡t hi»n dị thường tr¶n £nh UAV ùng dụng trong công t¡c t¼m ki¸m cùu n¤n [CT3], NCS và tªp thº c¡n bë hướng mªt độ h¤t nh¥n. d¨n đã đề xu§t phương ph¡p gi£m tỷ l» dương t½nh gi£ cõa thuªt to¡n ph¡t ˆ Thù hai, tr¼nh bày thuªt to¡n t«ng độ ch½nh x¡c ph¡t hi»n dị thường dựa hi»n c¡c điểm £nh dị thường dựa tr¶n KDE b¬ng c¡ch thực hi»n theo ba bước, tr¶n ước lượng mªt độ h¤t nh¥n. Cài đặt c¡c thuªt to¡n dựa tr¶n ý tưởng gồm: tr½ch chọn c¡c điểm £nh đặc trưng và làm mịn £nh; t½nh to¡n thuªt to¡n đã đề xu§t. ph¡t hi»n c¡c điểm £nh dị thường dựa tr¶n KDE cho nhúng điểm £nh xung ˆ Thù ba, kiºm nghi»m đề xu§t, sû dụng 36 £nh để kiºm tra độ ch½nh x¡c quanh c¡c điểm £nh đặc trưng; ph¥n lo¤i c¡c điểm £nh đã được t½nh to¡n. ph¡t hi»n c¡c điểm £nh dị thường cõa thuªt to¡n KDE và thuªt to¡n đề Bước đầu ti¶n, tr½ch chọn c¡c điểm £nh đặc trưng và làm mịn £nh. Để gi£m xu§t (thuªt to¡n IKDE). Cụ thº: thuªt to¡n IKDE có độ ch½nh x¡c cao mët ph¦n nhi¹u tr¶n £nh, luªn ¡n sû dụng dụng phương ph¡p làm mịn £nh hơn thuªt to¡n KDE trung b¼nh là 0,58%. b¬ng c¡ch t½ch chªp £nh gèc với to¡n tû Gaussian Blur: 1 2 2 2 G(x; y; σ) = e−(x +y )=2σ ; (2.5) 2πσ 10 15
13. têng sè điểm £nh dị thường trong mët £nh không vượt qu¡ 0.05% têng sè điểm Trong đó, σ là h» sè làm mịn, σ càng cao th¼ £nh càng mịn. Tuy nhi¶n, σ càng £nh trong mët £nh. C¡c £nh đều được chụp vào ban ngày, trời n­ng nhẹ. Thù cao th¼ độ s­c n²t (chi ti¸t) cõa c¡c đối tượng càng gi£m, có thº làm m§t t½nh ba, sû dụng 30 £nh gồm: 10 £nh 3 k¶nh phê; 10 £nh 8 k¶nh hồng ngo¤i g¦n và đặc trưng cõa c¡c điểm £nh dị thường d¨n đến độ ch½nh x¡c ph¡t hi»n c¡c điểm 10 £nh 8 k¶nh phê hồng ngo¤i ng­ng do Pháng th½ nghi»m khoa học và công £nh dị thường cõa thuªt to¡n gi£m so với £nh chưa qua làm mịn. ngh» quèc pháng (DSTL)- Vương quèc Anh cung c§p [24]. Dựa vào t½nh ch§t cõa c¡c điểm £nh dị thường là có màu s­c nêi bªt hoặc có sự kh¡c bi»t lớn so với c¡c điểm £nh xung quanh và chúng r§t thưa thớt, 2.6.2 Phương ph¡p thû nghi»m hi¸m khi đại di»n cho £nh, luªn ¡n s³ sû dụng mët công cụ để định vị c¡c điểm Như vªy, chúng ta có 36 £nh để thû nghi»m, sû dụng thuªt to¡n KDE và £nh này. Tªp nhúng điểm £nh được định vị này có thº không chùa t§t c£ c¡c thuªt to¡n IKDE để đánh gi¡. Độ ch½nh x¡c ph¡t hi»n dị thường cõa c¡c thuªt điểm £nh dị thường và có thº có th¶m c¡c điểm £nh b¼nh thường nhưng chúng to¡n được t½nh b¬ng độ đo AUC. là nhúng điểm £nh có màu s­c nêi bªt (có thº có gi¡ trị lớn nh§t hoặc nhỏ nh§t) trong mët vùng cục bë, nhúng điểm £nh này gọi là tªp nhúng điểm đặc 2.6.3 K¸t qu£ thû nghi»m trưng. Tø c¡c điểm £nh đặc trưng, sû dụng Thuªt to¡n KDE để t½nh to¡n c¡c Quan s¡t B£ng 2.1 chúng ta th§y, độ ch½nh x¡c ph¡t hi»n c¡c điểm £nh dị điểm xung quanh trong mët ph¤m vi giới h¤n để t¼m c¡c điểm £nh dị thường thường cõa c¡c thuªt to¡n tr¶n 3 £nh được c§y m¨u dị thường (£nh: a, b và thực sự, c¡c điểm £nh cán l¤i s³ được bỏ qua và coi nó là nhúng điểm £nh b¼nh c), tr¶n 3 £nh r¢i c¡c m¨u ở thực địa (£nh: d, e và f) và tr¶n 10 £nh 3 k¶nh thường. Như vªy, thay v¼ ph£i t½nh to¡n Thuªt to¡n 2.1 cho toàn bë c¡c điểm phê cõa DSTL cao hơn nhúng £nh cán l¤i. Ảnh 8 k¶nh phê hồng ngo¤i ng­n là £nh, chúng ta ch¿ đi t½nh to¡n cho mët tªp hñp nhỏ c¡c điểm £nh xung quanh nhúng £nh cho độ ch½nh x¡c ph¡t hi»n cõa c¡c thuªt to¡n th§p nh§t, ph¦n lớn c¡c điểm đặc trưng, tø đó gi£m được nhi¹u bị g¡n vào tªp gi¡ trị dị thường độ ch½nh x¡c ph¡t hi»n c¡c điểm £nh dị thường cõa c¡c thuªt to¡n tr¶n lo¤i làm gi£m tỷ l» dương t½nh gi£. £nh này nhỏ hơn 85%, nhi·u £nh độ ch½nh x¡c ph¡t hi»n ch¿ ở mùc hơn 70%. Qua nghi¶n cùu phương ph¡p tr½ch rút c¡c điểm £nh đặc trưng b§t bi¸n cục Quan s¡t tªp dú li»u đầu vào cho th§y: tø £nh (a) đến (f) và 10 £nh 3 k¶nh bë SIFT [71] cho th§y, trong mët cụm c¡c điểm £nh dị thường n¬m c¤nh nhau phê cõa DSTL có độ ph¥n gi£i cao (độ ph¥n gi£i ≤ 1; 24m=pixel), nhúng £nh s³ có ½t nh§t mët điểm £nh được chọn là điểm đặc trưng. Điều này hoàn toàn cán l¤i có độ ph¥n gi£i tương đối th§p (7; 5m=pixel). Như vªy, ch§t lượng h¼nh phù hñp bởi c¡c điểm £nh dị thường có màu s­c nêi bªt hoặc kh¡c bi»t so với £nh s³ £nh hưởng đến độ ch½nh x¡c ph¡t hi»n c¡c điểm £nh dị thường cõa c¡c nhúng điểm £nh xung quanh, trong khi đó SIFT t¼m nhúng điểm £nh có gi¡ thuªt to¡n. trị lớn nh§t hoặc nhỏ nh§t trong mët vùng cục bë làm điểm £nh đặc trưng. Tr¶n B£ng 2.1 cho ta th§y, phương ¡n đề xu§t (thuªt to¡n IKDE) có độ Bước thù hai, thuªt to¡n ph¡t hi»n c¡c điểm £nh dị thường dựa tr¶n KDE ch½nh x¡c ph¡t hi»n c¡c điểm £nh dị thường tèt hơn thuªt to¡n gèc (thuªt to¡n cho nhúng điểm £nh xung quanh c¡c điểm £nh đặc trưng. Sau khi t¼m được tªp KDE). Cụ thº, thuªt to¡n IKDE cho độ ch½nh x¡c ph¡t hi»n c¡c điểm £nh dị hñp nhúng điểm đặc trưng, t¤i méi mët điểm đặc trưng, ch¿ t½nh to¡n thuªt thường trung b¼nh tèt hơn thuªt to¡n KDE trung b¼nh 0.58%. Như vªy, đề to¡n ph¡t hi»n c¡c điểm £nh dị thường dựa tr¶n KDE cho mët sè điểm £nh xu§t cõa luªn ¡n để lo¤i bỏ mët ph¦n nhi¹u được ph¥n vào lớp "dị thường" xung quanh điểm đặc trưng thông qua mët cûa sê giới h¤n gọi là cûa sê W, cõa c¡c thuªt to¡n hoàn toàn ch½nh x¡c; do nhi¹u trong méi £nh không ph£i là nhúng điểm £nh n¬m ngoài cûa sê W s³ được g¡n luôn cho lớp b¼nh thường nhi·u n¶n không có ch¶nh l»ch lớn v· độ ch½nh x¡c ph¡t hi»n giúa thuªt to¡n mà không ph£i t½nh to¡n. W có t¥m là điểm £nh đặc trưng đang x²t, W ph£i KDE và thuªt to¡n IKDE. bao h¸t toàn bë c¡c điểm £nh dị thường (n¸u có) xung quanh điểm đặc trưng. 2.7 K¸t luªn Nhưng W cũng không được qu¡ lớn, n¸u lớn qu¡ s³ tương đương với vi»c t½nh Mët sè v§n đề đã được tr¼nh bày trong chương này gồm: to¡n Thuªt to¡n KDE cho toàn bë c¡c điểm £nh. Bước thù ba, ph¥n lo¤i c¡c điểm £nh đã được t½nh to¡n. Nhúng điểm £nh ˆ Thù nh§t, tr¼nh bày thuªt to¡n ph¡t hi»n dị thường dựa tr¶n ước lượng 14 11
14. được t½nh to¡n gi¡ trị dị thường trong bước thù hai s³ được ph¥n lo¤i khi so 2.4 T½nh đúng đắn cõa thuªt to¡n IKDE s¡nh với mët ngưỡng ph¡t hi»n dị thường η. Nhúng điểm £nh không được t½nh Để ph¥n mët điểm £nh vào lớp "b¼nh thường" C1 hay lớp "dị thường" C2 to¡n trong bước thù hai s³ được x¡c định là nhúng điểm £nh b¼nh thường. (tø hàng 8 đến hàng 18) ph£i c«n cù tr¶n hàm mªt độ x¡c su§t cõa điểm £nh Thuªt to¡n 2.2 được x¥y dựng theo ý tưởng đã được tr¼nh bày ở tr¶n. đang x²t và được thực hi»n như thuªt to¡n gèc (thuªt to¡n KDE). V¼ vªy, c¦n ph£i chùng minh t§t c£ c¡c điểm dị thường đều được x²t, hay Thuªt to¡n 2.2: C£i ti¸n thuªt to¡n ph¡t hi»n c¡c điểm £nh dị nói c¡ch kh¡c, c¡c điểm dị thường ph£i n¬m trong c¡c cûa sê W l§y c¡c điểm thường dựa tr¶n KDE (gọi t­t là thuªt to¡n IKDE) đặc trưng làm t¥m. Thªt vªy: input: X: ma trªn c¡c điểm £nh, N: sè điểm £nh, L: sè k¶nh phê, - Trong mët cụm điểm £nh dị thường, có ½t nh§t 1 điểm £nh được chọn làm h: b«ng thông, η: ngưỡng ph¡t hi»n dị thường, W: cûa sê. điểm £nh đặc trưng theo Thuªt to¡n SIFT như đã tr¼nh bày t¤i Mục 2.3. output: C1, C2. - Thuªt to¡n c£i ti¸n IKDE đã x²t t§t c£ c¡c điºm đặc trưng (hàng 4), t¤i 1 P tªp c¡c điºm £nh đặc trưng (sû dụng thuªt to¡n SIFT); méi mët điểm đặc trưng, x²t toàn bë c¡c điểm £nh n¬m trong mët cûa sê W 2 X0 GaussianBlur(X,σ);//làm mờ £nh theo công thùc (2.5) l§y điểm £nh đặc trưng đó làm t¥m (hàng 6), k½ch thước cûa sê W dài và rëng 3 C fX0g, i=1,2, ,N; C ;; C ;; 0 i 1 2 g§p 2 l¦n cụm điểm £nh dị thường (do c¡c điểm £nh đặc trưng thường n¬m 4 foreach p 2 P do tr¶n bi¶n cõa cụm £nh dị thường) n¶n t§t c£ c¡c điểm £nh dị thường đều được 5 w tªp hñp c¡c điểm £nh n¬m trong W l§y p là t¥m; x²t. Do đó, t§t c£ c¡c điểm £nh dị thường được ph¥n vào lớp C n¶n thuªt to¡n 0 2 6 foreach Xi 2 w do IKDE có t½nh đúng đắn. 0 7 if Xi 2 C0 then 2.5 Đánh gi¡ độ phùc t¤p cõa thuªt to¡n KDE và IKDE 8 sum_ker 0; - Độ phùc t¤p t½nh to¡n cõa thuªt to¡n KDE là O(N 2). 9 for j 1 to N do - Độ phùc t¤p t½nh to¡n cõa thuªt to¡n IKDE là O(L:M:N) = O(N 2) (v¼ 10 mul 1; M ≤ N, L là h¬ng sè). 11 for d 1 to L do * T½nh hi»u qu£ cõa thuªt to¡n: V· lý thuy¸t, độ phùc t¤p t½nh to¡n cõa X0[i][d] − X0[j][d] 12 mul mul × K ; Thuªt to¡n KDE b¬ng với độ phùc t¤p t½nh to¡n cõa thuªt to¡n IKDE. X²t h trường hñp tồi nh§t th¼ M=N. Tuy nhi¶n, thực t¸ th¼ M ≪ N do đó, thời gian 13 sum_ker sum_ker + mul; t½nh to¡n cõa Thuªt to¡n IKDE đã gi£m đáng kº so với Thuªt to¡n KDE. sum_ker 2.6 Thû nghi»m và đánh gi¡ k¸t qu£ đề xu§t 14 if ≤ η then N 2.6.1 Dú li»u thû nghi»m 15 C2 C2 [ fXig; 16 else Để kiºm nghi»m k¸t qu£ nghi¶n cùu, luªn ¡n ti¸p cªn theo ba c¡ch: thù 17 C1 C1 [ fXig; nh§t, c§y mët sè m¨u dị thường vào 3 £nh (Ảnh: a, b, c) chụp tø thi¸t bị UAV tr¶n ba lo¤i địa h¼nh kh¡c nhau (địa h¼nh đồng b¬ng, địa h¼nh røng thưa và 18 C0 C0 − fXig; địa h¼nh vùng biºn). Thù hai, để t¤o t¼nh huèng g¦n s¡t với thực t¸, bè tr½ mët 19 C1 C1 [ C0; sè m¨u dị thường tr¶n không gian quan s¡t, sû dụng thi¸t bị UAV thu chụp (3 £nh: d, e, f). Nhúng m¨u được c§y đã được ch¿nh sûa k½ch thước sao cho tương đồng với độ ph¥n gi£i mặt đất cõa c¡c £nh, có k½ch thước r§t nhỏ so với £nh, 12 13