Bé gi¸o dôc vµ ®µo t¹o trêng ®¹i häc b¸ch khoa hµ néi ------------------------------------------------------------- luËn v¨n th¹c sÜ khoa häc Nghiªn cøu øng dông c¸c ph¬ng ph¸p nhËn d¹ng ¶nh trong ®iÒu khiÓn Robot ngµnh : tù ®éng ho¸ xncn m· sè : nguyÔn minh s¬n Ngêi híng dÉn khoa häc : TS NguyÔn V¨n khang hµ néi - 2008 17057205234931000000 Lêi cam ®oan T«i xin cam ®oan b¶n luËn v¨n nµy ®îc thùc hiÖn bëi chÝnh b¶n th©n t«i díi sù híng dÉn cña TS NguyÔn V¨n Khang cïng víi c¸c tµi liÖu ®· ®îc trÝch dÉn trong phÇn tµi liÖu tham kh¶o ë phÇn cuèi b¶n luËn v¨n. NguyÔn Minh S¬n Môc Lôc B 0 Trang Trang phô b×a B 1 Lêi cam ®oan B 2 Môc lôc B 3 Danh môc ký hiÖu vµ ch÷ viÕt t¾t B 4 Lêi më ®Çu B 5 1 B 6 ch¬ng I - Tæng quan vÒ “ øng dông c¸c ph¬ng B 7 ph¸p nhËn d¹ng ¶nh trong ®iÒu khiÓn Robot” vµ néi dung cÇn nghiªn cøu 3 B 8 1.1 Tæng quan vÒ øng dông c¸c ph¬ng ph¸p nhËn d¹ng ¶nh B 9 trong ®iÒu khiÓn Robot 3 B 01 B 11.1 TÝnh thêi sù 3 B 21 B1.2 C¬ së khoa häc cña øng dông c¸c ph¬ng ph¸p nhËn d¹ng 31 ¶nh trong ®iÒu khiÓn Robot 4 B 41 B1.3 TÝnh øng dông 51 5 B 61 B1.4 T×nh h×nh nghiªn cøu øng dông nhËn d¹ng ¶nh trong ®iÒu 71 khiÓn Robot trªn thÕ giíi 6 B 81 B1.5 T×nh h×nh nghiªn cøu, øng dông trong níc 91 7 B 02 1.2 C¸c bíc chÝnh trong hÖ thèng nhËn d¹ng B 12 9 B 2 B1.1 Thu nhËn h×nh ¶nh 32 9 B 42 B 1.4 Ph©n tÝch h×nh ¶nh 92 10 B 03 B1.3 Néi dung nghiªn cøu B 53 11 B 63 1.4 Môc tiªu vµ néi dung cña luËn v¨n B 73 12 B 83 B1.2 Néi dung 14 12 B 24 Ch¬ng II - ph©n vïng ¶nh B 34 14 B 4 2.1 Ph©n vïng ¶nh theo ngìng biªn ®é B 54 14 B 64 B2.1 Ngìng cè ®Þnh 74 15 B 84 B2.2 Ngìng dùa trªn lîc ®å 94 15 B 05 2.1 TuËt to¸n ®¼ng liÖu B 15 16 B 25 2.2 ThuËt to¸n tam gi¸c B 35 16 B 45 2.2 ThuËt to¸n g¸n nh·n thµnh phÇn liªn th«ng B 5 17 B 65 2.3 Ph©n vïng theo miÒn ®ång nhÊt B 75 19 B 85 B2.1 Ph¬ng ph¸p t¸ch c©y tø ph©n 95 19 B 06 B2.2 Ph¬ng ph¸p côc bé 16 21 B 26 B2.3 Ph¬ng ph¸p tæng hîp 36 22 B 46 2.4 Ph©n vïng ¶nh theo kÕt cÊu bÒ mÆt B 56 23 B 6 B2.1 Ph¬ng ph¸p thèng kª 76 23 B 86 B2.2 Ph¬ng ph¸p cÊu tróc 96 27 B 07 2.3 TiÕp cËn theo tÝnh kÕt cÊu B 17 27 B 27 Ch¬ng III - C¸c ph¬ng ph¸p nhËn d¹ng ¶nh B 37 28 B 47 3.1 Kh¸i qu¸t vÒ nhËn d¹ng B 57 28 B 67 B 73.1 Kh«ng gian biÓu diÔn ®èi tîng, kh«ng gian diÔn dÞch 28 B 87 B 3.2 M« h×nh vµ b¶n chÊt cña qu¸ tr×nh nhËn d¹ng 97 29 B 08 B3.2 B¶n chÊt cña qu¸ tr×nh nhËn d¹ng 38 31 B 48 33 B 68 3.2 NhËn d¹ng dùa trªn ph©n ho¹ch kh«ng gian B 58 B 783.1 Ph©n ho¹ch kh«ng gian 33 B 8 B 983.2 Hµm ph©n líp hay hµm ra quyÕt ®Þnh 33 B 09 B 193.3 NhËn d¹ng thèng kª 35 B 29 B 393.4 Mét sè thuËt to¸n nhËn d¹ng tiªu biÓu trong tù häc 36 B 49 3.1 ThuËt to¸n dùa vµo kho¶ng c¸ch lín nhÊt B 59 36 B 69 3.2 ThuËt to¸n K trung b×nh B 79 37 B 89 3.3 ThuËt to¸n ISODATA B 9 38 B 01 3.3 NhËn d¹ng theo cÊu tróc B 10 39 B 201 B 3.1 BiÓu diÔn ®Þnh tÝnh 301 39 B 401 B 3.2 Ph¬ng ph¸p ra quyÕt ®Þnh dùa vµo cÊu tróc 501 39 B 601 3.1 Mét sè kh¸i niÖm B 701 39 B 801 3.2 Ph¬ng ph¸p nhËn d¹ng B 901 41 B 01 3.4 m¹ng n¬ ron nh©n t¹o vµ NhËn d¹ng theo m¹ng n¬ ron B 1 41 B 21 B 313.Bé n·o vµ n¬ ron sinh häc 42 B 41 B 513. M« h×nh m¹ng n¬ ron nh©n t¹o 45 B 61 3.1 M« h×nh n¬ ron nh©n t¹o B 71 46 B 81 3.3 C¸c m¹ng n¬ ron mét líp 52 B 21 3.2 M¹ng kiÓu bé nhí 2 chiÒu kÕt hîp thÝch nghi B 521 56 B 621 3.4 C¸c m¹ng n¬ ron nhiÒu líp 66 B 231 3.1 M¹ng n¬ ron nhiÒu líp lan truyÒn ngîc sai sè B 31 66 B 431 3.2 M¹ng n¬ ron nhiÒu líp ngîc híng B 531 71 B 631 74 B 831 Ch¬ng IV - B 731 øng dông nhËn d¹ng ¶nh trong ®iÒu khiÓn Robot 4.1 øng dông nhËn d¹ng ¶nh trong ®iÒu khiÓn chuyÓn ®éng B 931 cña Robot 74 B 041 4.2 X©y dùng c¸c tham sè cho bé ®iÒu khiÓn camera B 14 75 B 241 B 4.1 TÝnh to¸n tèc ®é quay theo ph¬ng ngang ϕ 341 75 B 41 B 4.2 TÝnh to¸n tèc ®é quay theo ph¬ng ®øng ψ 541 77 B 641 4.3 X©y dùng c¸c tham sè cho bé ®iÒu khiÓn robot B 741 78 B 841 B 4.1 C¸c tham sè ¶nh hëng tíi tèc ®é cña Robot 941 78 B 051 B 154.2 TÝnh to¸n c¸c tham sè trong bé ®iÒu khiÓn 79 B 251 Ch¬ng V - M« pháng B 351 83 B 451 5.1 M« pháng qu¸ tr×nh nhËn d¹ng ¶nh B 51 83 B 651 B 5.1 C¬ së lý thuyÕt thùc hiÖn qu¸ tr×nh nhËn d¹ng 751 83 B 851 B 5.2 KÕt qu¶ m« pháng 951 85 B 061 B 165.2 M« pháng bé ®iÒu khiÓn Robot, quü ®¹o ®uæi b¾t ®èi tîng B 361 88 B 461 B 5.2 KÕt qu¶ m« pháng 761 92 B 861 B 5.3 NhËn xÐt 961 94 B 071 KÕt luËn vµ kiÕn nghÞ B 17 95 B 271 Tµi liÖu tham kh¶o B 371 Phô lôc B 471 Tãm t¾t luËn v¨n B 571 Danh môc ký hiÖu vµ ch÷ viÕt t¾t θ Gi¸ trÞ ngìng cña møc x¸m Pixel §iÓm ¶nh X Lµ ®èi tîng ¶nh X Lµ kh«ng gian ®èi tîng Ω Kh«ng gian diÔn dÞch Φ TËp rçng W Ma trËn träng sè ξx, ξy Täa ®é cña ®èi tîng trong ¶nh ϕ Gãc cña camera theo ph¬ng ngang ψ Gãc cña camera theo ph¬ng ®øng v VËn tèc dµi ω VËn tèc gãc e Vector sai lÖch vÞ trÝ 1 Lêi Më ®Çu Sù ph¸t triÓn cña kü thuËt ®iÖn tö vµ c«ng nghÖ th«ng tin ®· kÐo theo sù ph¸t triÓn cña mét lo¹t c¸c ngµnh liªn quan. Mét trong nh÷ng ngµnh ®ã lµ ngµnh xö lý – nhËn d¹ng ¶nh sè.
Trªn thÕ giíi, c«ng nghÖ xö lý – nhËn d¹ng ¶nh ®· vµ ®ang ®îc ph¸t triÓn rÊt m¹nh mÏ v× nã cã rÊt nhiÒu øng dông trong hÇu hÕt c¸c lÜnh vùc cña con ngêi. Vµ hiÖn nay, nÕu s¶n phÈm nµo cã øng dông c«ng nghÖ nµy th× ®Òu ®îc coi lµ s¶n phÈm th«ng minh, cã søc c¹nh tranh lín. Mét trong nh÷ng lÜnh vùc rÊt cÇn ®îc trang bÞ c«ng nghÖ nhËn d¹ng ¶nh ®ã lµ c«ng nghiÖp chÕ t¹o Robot. ViÖc øng dông c«ng nghÖ nµy trong ®iÒu khiÓn Robot sÏ lµm t¨ng kh¶ n¨ng nhËn thøc cho Robot, lµm cho nã ngµy cµng hoµn thiÖn vµ gièng con ngêi.
ë trong níc, m«n xö lý ¶nh míi chØ ®îc gi¶ng d¹y ë mét sè trêng träng ®iÓm vÒ khoa häc kü thuËt nh §¹i häc B¸ch khoa Hµ néi, §¹i häc Quèc gia Hµ néi, §¹i häc B¸ch khoa thµnh phè Hå ChÝ Minh…. Vµ míi chØ giíi h¹n trong c¸c ngµnh nh c«ng nghÖ th«ng tin, ®iÖn tö viÔn th«ng. HiÖn, cha cã nhiÒu nghiªn cøu ®Ó ®a c«ng nghÖ nµy vµo øng dông thùc tiÔn trong c¸c ngµnh, c¸c lÜnh vùc kh¸c. HiÖn nay, c«ng nghÖ xö lý – nhËn d¹ng ¶nh sè ®ang ®îc rÊt nhiÒu b¹n trÎ quan t©m.
§Æc biÖt lµ c¸c b¹n sinh viªn ®ang hoÆc cã ý ®Þnh tham gia trß ch¬i Robocon quèc tÕ. Bëi v× hÇu hÕt c¸c Robot tù ®éng hiÖn nay chñ yÕu rß ®êng theo v¹ch kÎ s©n vµ kh«ng ph©n biÖt ®îc cÊu kiÖn cña m×nh hay cña ®éi b¹n. ViÖc trang bÞ kü thuËt nhËn d¹ng ¶nh cho Robot tù ®éng sÏ lµm gi¶m bít c¸c nhîc ®iÓm trªn, ®ång thêi lµm t¨ng kh¶ n¨ng ®iÒu khiÓn linh ho¹t cho Robot. XuÊt ph¸t tõ nhu cÇu thùc tiÔn trªn, T«i ®· chän ®Ò tµi Nghiªn cøu øng dông c¸c ph¬ng ph¸p nhËn d¹ng ¶nh trong ®iÒu khiÓn Robot.
2 QuyÓn luËn v¨n nµy sÏ nh mét tµi liÖu tham kh¶o, gióp ngêi ®äc cã h×nh dung vÒ kh¸i niÖm nhËn d¹ng ¶nh, c¸c ph¬ng ph¸p nhËn d¹ng ¶nh vµ biÕt c¸ch øng dông c«ng nghÖ nµy trong ®iÒu khiÓn Robot. Cô thÓ ë ®©y t«i x©y dùng ph¬ng ph¸p nhËn d¹ng ¶nh ®Ó ®iÒu khiÓn Robot trong viÖc t×m vµ ®uæi b¾t môc tiªu ®ang di ®éng cã ph¬ng vµ vËn tèc cha biÕt. Trong khu«n khæ cña mét ®Ò tµi víi quü thêi gian kh«ng cho phÐp vµ cã mét sè khã kh¨n trong viÖc cËp nhËp tµi liÖu còng nh do h¹n chÕ cña b¶n th©n, nªn ch¾c ch¾n quyÓn luËn v¨n nµy kh«ng tr¸nh khái nh÷ng thiÕu sãt. VËy kÝnh mong c¸c thÇy c« cïng c¸c b¹n yªu thÝch c«ng nghÖ nµy ®ãng gãp chØ b¶o, phª b×nh ®Ó ®Ò tµi nµy ngµy cµng hoµn thiÖn.
Em xin ch©n thµnh c¶m ¬n thÇy gi¸o TS. NguyÔn V¨n Khang ®· tËn t×nh híng dÉn chØ b¶o em trong thêi gian thùc hiÖn ®Ò tµi nµy! Hµ néi, 18/ 11/ 2008. T¸c gi¶ NguyÔn Minh S¬n 3 ch¬ng I Tæng quan vÒ “ øng dông c¸c ph¬ng ph¸p nhËn d¹ng ¶nh trong ®iÒu khiÓn Robot” vµ néi dung cÇn nghiªn cøu 1.1 Tæng quan vÒ øng dông c¸c ph¬ng ph¸p nhËn d¹ng ¶nh trong ®iÒu khiÓn Robot 1.1 TÝnh thêi sù Ngµy nay, tríc sù ph¸t triÓn vît bËc cña khoa häc kü thuËt, c¸c thiÕt bÞ m¸y mãc thay thÕ hoÆc hç trî cho con ngêi trong lao ®éng s¶n xuÊt, trong sinh ho¹t, ®ßi hái ngµy cµng ph¶i hoµn thiÖn h¬n. Trong nh÷ng n¨m gÇn ®©y do kü thuËt vi ®iÖn tö ph¸t triÓn rÊt m¹nh, ®· khiÕn cho tèc ®é cña c¸c bé vi xö lý ngµy cµng cao, chÊt lîng cña c¸c camera kü thuËt sè ngµy cµng hoµn thiÖn.
V× vËy, viÖc øng dông c«ng nghÖ xö lý ¶nh, nhËn d¹ng ¶nh ngµy cµng s©u réng trong tÊt c¶ c¸c lÜnh vùc nh trong c«ng nghiÖp, qu©n sù, an ninh, vò trô, y häc, giao th«ng…vv vµ c¶ trong cuéc sèng hµng ngµy. Tõ khi xuÊt hiÖn cho tíi nay, kh«ng ai cã thÓ phñ nhËn ®îc vai trß cña Robot trong s¶n xuÊt c«ng nghiÖp lÉn trong sinh ho¹t gia ®×nh. Chóng sÏ thùc hiÖn nh÷ng c«ng viÖc rÊt nhµm ch¸n hoÆc nguy hiÓm, vµ nh÷ng c«ng viÖc mµ tèc ®é vµ ®é chÝnh x¸c vît qu¸ kh¶ n¨ng cña con ngêi. Khi ngêi m¸y trë nªn tinh vi h¬n, thÞ gi¸c m¸y tÝnh sÏ ®ãng vai trß ngµy cµng quan träng.