Phương pháp biểu diễn đường viền trên trường số phức, áp dụng cho bài toán phân loại phương tiện giao thông

Nghiªn cøu khoa häc c«ng nghÖ qu©n sù<br /> <br /> <br /> PH­¬NG PH¸P BIÓU DIÔN §­êNG VIÒN<br /> TR£N TR­êNG Sè PHøC, ¸P DôNG CHO BµI TO¸N<br /> PH¢N LO¹I PH­¬NG TIÖN GIAO TH¤NG<br /> NGUYÔN V¡N C¡N*, NGUYÔN §¡NG TIÕN*, PH¹M VIÖT TRUNG**<br /> Tãm t¾t: Môc ®Ých cña bµi viÕt nµy lµ: thø nhÊt, tr×nh bµy ph­¬ng ph¸p biÓu<br /> diÔn ®­êng viÒn cña ®èi t­îng trong ¶nh nhÞ ph©n b»ng vector sè phøc. Thø hai<br /> ph©n tÝch mét sè tÝnh chÊt cña vector sè phøc ®Ó ¸p dông cho bµi to¸n nhËn<br /> d¹ng, so s¸nh mÉu trªn c¬ së ®­êng viÒn. X©y dùng l­îc ®å chung cho viÖc nhËn<br /> d¹ng vµ ph©n lo¹i ®èi t­îng b»ng ph­¬ng ph¸p ®­êng viÒn vector. Qu¸ tr×nh thö<br /> nghiÖm nhËn d¹ng vµ ph©n lo¹i c¸c tËp ¶nh cã møc ®é phøc t¹p vÒ xe m¸y, xe «<br /> t« cho kÕt qu¶ chÝnh x¸c vµ tèc ®é tÝnh to¸n nhanh.<br /> <br /> Tõ khãa: NhËn d¹ng, Ph©n tÝch ®­êng viÒn, NhËn d¹ng « t«, Vector phøc.<br /> <br /> 1. ®Æt vÊn ®Ò<br /> Ph©n lo¹i ¶nh lµ mét bµi to¸n ®· vµ ®ang thu hót ®­îc sù quan t©m cña c¸c nhµ<br /> nghiªn cøu vµ ph¸t triÓn, ®­îc øng dông réng r·i nhiÒu øng dông h÷u Ých nh­: t×m<br /> kiÕm ¶nh, nhËn d¹ng, theo dâi vµ ph¸t hiÖn ®èi t­îng t­îng,... C¸ch tiÕp cËn phæ<br /> biÕn cña bµi to¸n ph©n lo¹i ¶nh lµ ®èi s¸nh ¶nh, tøc lµ t×m ra nh÷ng vïng gièng<br /> nhau trªn hai ¶nh. §¬n gi¶n nhÊt lµ so s¸nh c¸c ®iÓm ¶nh. C¸c ph­¬ng ph¸p ®ang<br /> ph¸t triÓn hiÖn nay lµ trÝch chän c¸c ®Æc tr­ng ®Ó biÓu diÔn ¶nh. Khi ®ã bµi to¸n ®èi<br /> s¸nh ¶nh sÏ quy vÒ bµi to¸n so s¸nh c¸c ®Æc tr­ng trÝch chän [3, 7, 8, 9, 13]. C¸c<br /> ®Æc tr­ng cho phÐp biÓu diÔn ¶nh ®· ®­îc nghiªn cøu bao gåm ®­êng biªn vïng<br /> ¶nh, ®iÓm ¶nh ®Æc tr­ng, l­îc ®å x¸m,...<br /> Cã hai vÊn ®Ò c¬ b¶n th­êng ®Æt ra trong bµi to¸n ®èi s¸nh ¶nh: i) lµm sao cã<br /> thÓ biÓu diÔn th«ng tin mét c¸ch hiÖu qu¶ nh»m thùc hiÖn viÖc ®èi s¸nh hai ¶nh<br /> nhanh nhÊt cã thÓ; ii) lµm thÕ nµo ®Ó gi¶i ph¸p ®èi s¸nh vÉn ho¹t ®éng hiÖu qu¶ khi<br /> cã sù thay ®æi cña m«i tr­êng: nhiÔu trong qu¸ tr×nh thu nhËn ¶nh, sù thay ®æi vÒ<br /> ¸nh s¸ng, sù che khuÊt,...<br /> C¸c ph­¬ng ph¸p ®èi s¸nh ¶nh dùa trªn viÖc ®èi s¸nh c¸c ®iÓm ®Æc tr­ng ®­îc<br /> ®Ò xuÊt rÊt nhiÒu vµ ®¹t ®­îc sù thµnh c«ng ®¸ng kÓ [9, 12]. Tuy nhiªn ®Ó ®¹t ®­îc<br /> mét ®é chÝnh x¸c nhÊt ®Þnh, c¸c ph­¬ng ph¸p nµy ®Òu ®ßi hái rÊt nhiÒu thêi gian<br /> tÝnh to¸n. Trong nh÷ng øng dông thêi gian thùc nh­ gi¸m s¸t giao th«ng tù ®éng,<br /> viÖc ®­a ra mét ph­¬ng ph¸p ®èi s¸nh ¶nh thùc hiÖn trong thêi gian thùc lµ mét<br /> c«ng viÖc cÇn thiÕt [2, 4, 5, 6, 10, 11, 16].<br /> Néi dung chñ yÕu cña bµi b¸o giíi thiÖu mét ph­¬ng ph¸p tiÕp cËn ph©n lo¹i<br /> m¹nh mÏ ®èi víi « t« vµ xe m¸y trong ¶nh giao th«ng: ®Ò xuÊt mét ph­¬ng ph¸p<br /> biÓu diÔn ®­êng viÒn ®èi t­îng b»ng vector ®­êng viÒn trªn tr­êng sè phøc [1],<br /> ph©n tÝch vµ ¸p dông tÝnh chÊt cña mét sè phÐp to¸n trªn tr­êng sè phøc, ¸p dông<br /> cho viÖc nhËn d¹ng vµ ph©n lo¹i ®èi t­îng; tr×nh bµy ph­¬ng ph¸p biÓu diÔn ®­êng<br /> viÒn ®èi t­îng trªn tr­êng sè phøc vµ ¸p dông cho thuËt to¸n ph©n lo¹i ®­êng viÒn;<br /> thùc nghiÖm ®¸nh gi¸ kÕt qu¶ kiÓm chøng.<br /> <br /> <br /> <br /> <br /> T¹p chÝ Nghiªn cøu KH&CN qu©n sù, Sè 33, 10 - 2014 65<br />  Kỹ thuật điện tử & Khoa học máy tính<br /> <br /> 2. Ph­¬ng PH¸P BIÓU DIÔN §­êng VIÒN B»NG Sè PHøC<br /> 2.1. BiÓu diÔn ®­êng viÒn theo vector<br /> Ph©n tÝch ®­êng viÒn (CA) cho phÐp m« t¶, l­u tr÷, so s¸nh vµ t×m ra c¸c ®èi<br /> t­îng biÓu diÔn d­íi d¹ng ®­êng viÒn. §­êng viÒn chøa th«ng tin cÇn thiÕt vÒ h×nh<br /> d¹ng ®èi t­îng. Kh«ng quan t©m nhiÒu ®Õn c¸c ®iÓm bªn trong cña ®èi t­îng. C¸c<br /> tr­êng hîp kh«ng quan t©m nhiÒu ®Õn vïng bªn trong ®èi t­îng nh­ng quan t©m<br /> nhiÒu vÒ thÓ hiÖn ®­êng viÒn bªn ngoµi th× cho phÐp chuyÓn vÒ kh«ng gian 2 chiÒu<br /> cña ¶nh tøc lµ kh«ng gian ®­êng viÒn, tõ ®ã cho phÐp gi¶m thêi gian tÝnh to¸n vµ<br /> ®é phøc t¹p tÝnh to¸n. CA cho phÐp gi¶i quyÕt hiÖu qu¶ c¸c bµi to¸n c¬ b¶n cña<br /> nhËn d¹ng mÉu – biÕn ®æi, quay vµ tû lÖ cña ¶nh ®èi t­îng.<br /> §­êng viÒn lµ ®­êng bao cña ®èi t­îng, th­êng lµ c¸c ®iÓm ¶nh, ph©n t¸ch ®èi<br /> t­îng víi nÒn. Trong c¸c hÖ thèng thÞ gi¸c m¸y tÝnh, mét vµi ®Þnh d¹ng m· hãa<br /> ®­êng viÒn ®­îc sö dông nh­ m· hãa Freeman, m· hãa 2 chiÒu, m· hãa ®a gi¸c<br /> th­êng ®­îc sö dông nhÊt. Nh­ng tÊt c¶ nh÷ng ®Þnh d¹ng nµy th­êng kh«ng sö<br /> dông trong CA.<br /> §Þnh nghÜa 1. [Vector ®­êng viÒn]<br /> VÐc t¬ ®­êng viÒn (VC) lµ ®­êng viÒn ®­îc biÓu diÔn b»ng mét d·y c¸c sè<br /> phøc. Trªn mét ®­êng viÒn, ®iÓm b¾t ®Çu cÇn ®­îc x¸c ®Þnh. TiÕp theo, ®­êng viÒn<br /> sÏ ®­îc quÐt (xoay theo chiÒu kim ®ång hå), vµ mçi vector ®­îc biÓu diÔn b»ng<br /> mét sè phøc a+ib. Víi a lµ ®iÓm trªn trôc x, b lµ ®iÓm trªn trôc y. C¸c ®iÓm ®­îc<br /> biÓu diÔn kÕ tiÕp nhau.<br /> <br /> <br /> <br /> <br /> H×nh 1. BiÓu diÔn ®­êng viÒn b»ng vector sè phøc.<br /> <br /> §Þnh nghÜa 2. [TÝch v« h­íng cña ®­êng viÒn]<br /> Hai vector sè phøc cña 2 ®­êng viÒn  vµ N, tÝch v« h­íng cña nã lµ:<br /> k 1<br />   (, N )   ( n , n ) (1)<br /> n0<br /> <br /> víi k – kÝch th­íc cña VC, n lµ vector c¬ së (EV) cña ®­êng viÒn , n lµ EV<br /> cña ®­êng viÒn N. (n, n) lµ tÝch v« h­íng cña hai sè phøc.<br /> TÝch v« h­íng cña c¸c sè phøc ®­îc tÝnh b»ng c«ng thøc:<br /> (a+ib, c+id) = (a+ib) (c-id) = ac + bd + i(bc-ad) (2)<br /> Chó ý r»ng trong mét tÝch v« h­íng CA chØ cã mét VC cña chiÒu ®ång nhÊt.<br /> Do vËy mét sè EV trong ®­êng viÒn lµ trïng nhau.<br /> <br /> <br /> <br /> 66 N. V. C¨n, N.Đ.Tiến, P.V.Trung, " Ph­¬ng ph¸p biÓu diÔn ... ph­¬ng tiÖn giao th«ng."<br /> Nghiªn cøu khoa häc c«ng nghÖ qu©n sù<br /> <br /> TÝch v« h­íng cña c¸c vector th­êng vµ tÝch v« h­íng cña c¸c sè phøc lµ kh¸c<br /> nhau: NÕu ta nh©n mét EV nh­ mét vector ®¬n, tÝch v« h­íng cña chóng sÏ lµ:<br /> ((a,b),(c,d))=ac + bd (3)<br /> So s¸nh c«ng thøc nµy víi c«ng thøc (2) chó ý r»ng:<br /> - KÕt qu¶ tÝch v« h­íng cña c¸c vector lµ mét sè thùc. Vµ kÕt qu¶ tÝch cña c¸c<br /> sè phøc lµ mét sè phøc.<br /> - PhÇn thùc cña tÝch v« h­íng cña c¸c sè phøc trïng víi tÝch v« h­íng cña c¸c<br /> vector phï hîp. TÝch sè phøc bao gåm tÝch v« h­íng vector.<br /> Theo ®¹i sè tuyÕn tÝnh, ®Ó x¸c ®Þnh ®­îc chÝnh x¸c chiÒu vËt lý vµ c¸c ®Æc tÝnh<br /> cña tÝch v« h­íng. TÝch v« h­íng b»ng víi tÝch cña ®é dµi vector cña gãc cosin ë<br /> gi÷a trong ®¹i sè tuyÕn tÝnh. Tøc lµ 2 vector vu«ng gãc sÏ lu«n cã tÝch v« h­íng<br /> b»ng 0. Ng­îc l¹i, tÝch cña vector th¼ng hµng sÏ cho gi¸ trÞ tÝch v« h­íng tèi ®a.<br /> Nh÷ng ®Æc tÝnh nµy cña tÝch ®­îc sö dông nh­ mét c¸ch ®Ó ®o l­êng ®é gÇn<br /> cña c¸c vector. NÕu tÝch cµng lín, gãc cµng nhá gi÷a c¸c vector, th× c¸c vector nµy<br /> sÏ cµng gÇn nhau. Víi nh÷ng vector vu«ng gãc, tÝch nµy b»ng 0, vµ h¬n n÷a cã thÓ<br /> nhËn gi¸ trÞ ©m cho nh÷ng vector cã h­íng kh¸c nhau theo c¸ch nµy. TÝch v«<br /> h­íng (1) còng cã c¸c ®Æc tÝnh t­¬ng tù.<br /> <br /> MÖnh ®Ò 1. [§Æc tÝnh cña vector ®­êng viÒn]<br /> 1. Tæng c¸c EV cña mét ®­êng viÒn kÝn b»ng 0. Nã lµ tÇm th­êng – ®èi víi c¸c<br /> vect¬ tù trá vµo ®iÓm khëi ®Çu, tæng cña chóng =0 t­¬ng øng víi vector 0.<br /> 2. VC kh«ng phô thuéc vµo phÐp chuyÓn vÞ song song cña ¶nh nguån. Nh­ vËy<br /> c¸c ®­êng viÒn ®­îc m· hãa t­¬ng ®èi so víi ®iÓm b¾t ®Çu, chÕ ®é nµy cña<br /> m· hãa lµ bÊt biÕn chuyÓn cña mét ®­êng viÒn ban ®Çu.<br /> 3. Quay ¶nh theo mét gãc ®é nµo ®ã t­¬ng ®­¬ng víi quay mçi EV cña ®­êng<br /> viÒn trªn cïng gãc ®é ®ã.<br /> 4. ViÖc thay ®æi ®iÓm khëi ®Çu tiÕn hµnh theo vßng trßn VC, v× c¸c EV ®­îc m·<br /> hãa liªn quan ®Õn c¸c ®iÓm tr­íc ®ã, ®iÒu nµy râ rµng lµ thay ®æi ®iÓm khëi<br /> ®Çu, tr×nh tù cña mét EV sÏ lµ nh­ nhau, nh­ng EV ®Çu tiªn sÏ lµ b¾t ®Çu tõ<br /> ®iÓm khëi ®Çu.<br /> 5. Thay ®æi tû lÖ ¶nh nguån cã thÓ ®­îc coi lµ phÐp nh©n cña mçi EV cña<br /> ®­êng viÒn víi mét hÖ sè tû lÖ.<br /> B¾t nguån tõ c¸ch biÓu diÔn ®­êng viÒn b»ng sè phøc, gi¶ sö cã 8 h­íng c¬ b¶n<br /> cña ®­êng viÒn, b¾t ®Çu tõ ®Ønh cao nhÊt, quay theo chiÒu kim ®ång hå, chóng ta cã<br /> vÐc t¬ sè phøc {1, 1-i, -i, -1-i, -1, -1+i, i, 1+i }. Râ rµng ta cã tæng vector nµy b»ng<br /> 0. B»ng trùc quan hãa h×nh häc, dÔ dµng chøng minh ®­îc ®Æc tÝnh 1, 2 vµ c¸c ®Æc<br /> tÝnh cßn l¹i.<br /> §Þnh nghÜa 3. [TÝch v« h­íng chuÈn hãa (NSP)]<br /> NSP cña hai vetor ®­êng viÒn  vµ N ®­îc x¸c ®Þnh b»ng c«ng thøc:<br /> ( , )<br /> = | || | (4)<br /> || vµ |N| - Tiªu chuÈn (chiÒu dµi) cña ®­êng viÒn ®­îc tÝnh b»ng c«ng thøc:<br /> |Γ| = (∑ | | ) (5)<br /> NSP trong kh«ng gian phøc còng lµ mét sè phøc.<br /> <br /> <br /> T¹p chÝ Nghiªn cøu KH&CN qu©n sù, Sè 33, 10 - 2014 67<br />  Kỹ thuật điện tử & Khoa học máy tính<br /> <br /> Do vËy, tÝnh ®ång nhÊt lµ gi¸ trÞ lín nhÊt cã thÓ cña chuÈn NSP (Theo bÊt ®¼ng<br /> thøc Cauchy-Bunyakovsky Schwarz): |ab|