（计算机软件与理论专业论文）block+matching+using+lower+bound+comparison+algorithm.pdf

a b s t r a c t b l o c k m a t c h i n gu s i n g l o w e rb o u n d c o m p a r i s o na l g o r i t h m w e i w u b l o c km a t c h i n gi s f r e q u e n t l yu s e d i ns t e r e o v i s i o n ，v i s u a lt r a c k i n g ，a n dv i d e o c o m p r e s s i o n i n t h i s t e c h n i q u e t h e c u r r e n t i m a g e f l a m ei s p a r t i t i o n e d i n t o l i o n o v e r l a p p i n g f i x e d - s i z e r e c t a n g u l a r b l o c k s t h e g o a lh e r e i st oe s t i m a t et h e i n t e r - f l a m em o t i o nv e c t o rf o re a c hb l o c ki nt h ec u r r e n tf r a m eb yf i n d i n gt h eb e s t m a t c h i n gb l o c k ( a c c o r d i n gt oam a t c h i n gc r i t e r i o n ) i nt h er e f e r e n c ef r a m e ，u s u a l l yt h e p r e v i o u sf r a m i nac o m p u t a t i o n a l l ye f f i c i e n tm a n n e r i nt h i sr e p o r t w ef i r s tg i v ea i l o v e r v i e wo fs o m eo ft h ef a s b l o c k m a t c h i n ga l g o r i t h m st h a th a v e b e e n p r o p o s e di nt h e p a s t ，t h e ni n t r o d u c e an e wf a s tb l o c km a t c h i n ga l g o r i t h m u n l i k em a n yb l o c km a t c h i n ga l g o r i t h m sp r o p o s e di nt h ep a s tt h a tc a no n l ya s s u r ea l o c a lm i n i m u mo f m a t c h i n ge r r o rf o rt h ew h o l eb l o c k ，t h i sa l g o r i t h m ，w h i c hi sc a l l e d “l o w e rb o u n d c o m p a r i s o na l g o r i t h m i nt h i sr e p o r t ，i sa na l g o r i t h mt h a ts i g n i f i c a n t l y s p e e d su p t h ec o m p u t a t i o no f t h eb l o c km a t c h i n gw h i l eg u a r a n t e e i n gt h eg l o b a lo p t i m a l m a t c hi nt h es e a r c hr a n g e t oa c h i e v et h i s t h en e wa l g o r i t h mu s e sl o w e rb o u n d c o m p a r i s o ns t r a t e g yw h i c h u t i l i z e sa na s c e n d i n gl o w e rb o u n dl i s to f t h e m a t c h i n g e r r o r t od e t e r m i n et h et e m p o r a r yb e s tm a t c h p o s i t i o n w h a t t h es t r a t e g yd o e si st oa v o i dt h e c o s t l yc o m p u t a t i o n o f c o m p l e t em a t c h i n ge r r o ra te v e r ys e a r c hp o s i t i o nw h e n al o w e r b o u n d l a r g e rt h a nt h eg l o b a lm i n i m u mm a t c h i n g e r r o rc a nb eu s e d as e to fc o m m o nt e s ti m a g es e q u e n c e sa r eu s e dt ot e s tt h ep e r f o r m a n c eo ft h i sn e w a l g o r i t h m i n t h i sr e p o r t ，i t sp e r f o r m a n c ei sc o m p a r e dw i t ht h a to fs e v e r a lo t h e rb l o c k m a t c h i n ga l g o r i t h m sb y t h es a m eb e n c h m a r k s ，r e s u l t sa r ed i s c u s s e di nt h er e p o r t i n d e xl e r m s b l o c km a t c h i n g ，m o t i o ne s t i m a t i o n ，l o w e rb o u n dc o m p a r i s o ns t r a t e g y 2 l i s to ft a b l e s t a b l e i ：c o m p u t a t i o n a lc o m p l e x i t y o fs o m es e a r c ha l g o r i t h m si nc a t e g o r y l t a b l e i i ：r e s u l t f o r s a l e s m a ns e q u e n c e t a b l e i i i ：r e s u l t f o r t r e v o rs e q u e n c e ， t a b l e i v ：r e s u l t f o r a l e x s e q u e n c e t a b l ev ：r e s u l tf o rc l a i r es e q u e n c e t a b l e v i ：r e s u l t f o r f o r e m a n s e q u e n c e ， 4 1 4 2 7 2 7 2 8 2 8 2 9 t a b l eo f f i g u r e s f i g u r el ：t h e1 k e es t e ps e a r c h ( t s s ) l o f i g u r e2 ：t h ep r o g r e s s i n go f t d ls e a r c hf o rp = 8 1 2 f i g u r e3 ：c r o s ss e a r c ha l g o r i t h m 1 3 f i g u r e4 ：p i x e ld e c i m a t i o n ，1 7 f i g u r e5 ：a l t e r n a t i n gs c h e d u l eo f t h ef o u rp i x e ls u b s a m p l i n gp a t t e r n so v e rt h es e a r c h a r e a ，18 f i g u r e6 ：s u b s a m p l i n gp a t t e r nu s e df o rt h em o t i o nf i e l d 1 8 f i g u r e7 ：t e s ti m a g es e q u e n c e s ( a ) s a l e s m a n ，( b ) t r e v o r ，( c ) a l e x ，( d ) c l a i r e 2 6 f i g u r e8 ：o r i g i n a l r e c o n s t r u c t e df o r e m a ni m a g e sb vl b m i a n dl b t s s 3 1 f i g u r e9 ：e x a m p l e so f o r i g i n a l r e c o n s t r u c t e di m a g e sf o ro t h e rs e q u e n c e sb yl b t s s & l b m i 4 8 1 i n t r o d u c t i o n m o t i o nv e c t o re s t i m a t i o ni sa t e c h n i q u eu s e db ym o t i o nc o m p e n s a t i o ni no r d e rt o r e d u c et h et e m p o r a lr e d u n d a n c yt h a te x i s t si nav i d e os e q u e n c e t h et e r m “m o t i o n v e c t o r ”( m v ) r e f e r s t ot h ed i s p l a c e m e n tb e t w e e nt w o c o r r e s p o n d i n gp i x e l so f t h es a m e o b j e c ti nd i f f e r e n t 仔a m e so f t h e v i d e os e q u e n c e o n eo f t h ea p p r o a c h e si nm o t i o nv e c t o re s t i m a t i o ni sb l o c k m a t c h i n g 1 】i nb l o c k m a t c h i n g ，e a c hi m a g ei s d i v i d e di n t on o n - o v e r l a p p i n gf i x e d - s i z er e c t a n g u l a rb l o c k s t h em o t i o nv e c t o r sf o ra l lt h ep i x e l si no n eb l o c ka r et r e a t e da so n e s i n g l ev e c t o r t h e m o t i o nv e c t o ri so b t a i n e dw h e nam e a s u r eo fm a t c h i n ge r r o r ，t h es o - c a l l e d “c o s t f i m c t i o n ”，i sa t m i n i m u m m o s tf r e q u e n t l yu s e dc o s tf u n c t i o n sa r em e a n s q u a r e d d i f f e r e n c e ( m s d ) a n dm e a na b s o l u t ed i f f e r e n c e ( m a d ) t h ec o s tf u n c t i o nu s e di nt h i s r e p o r t ，u n l e s so t h e r w i s en o t e d ，i s m a d t h em a t c h i n ge r r o rb e t w e e nt h eb l o c k sa t p o s i t i o n 阮i n t h ec u r r e n ti m a g e ，i t ，a n dt h ec a n d i d a t eb l o c ka tp o s i t i o nb + “，_ y 十一i n t h er e f e r e n c ei m a g e ，i t - 1 ，i st h e nd e f i n e da s 1 8 一ib - l m a d ( 。) 0 ，v ) ；专i ，( x + f ，y + ) 一。( x + “+ f ，y + v + 川( 1 1 ) 上j ，= 0j = 0 w h e r et h eb l o c ks i z ei sb b t h em a d ，w h i c hu s e st h es u m m a t i o no v e rt h e “c o m p l e t e ”b l o c ko rt h e “c o m p l e t e ”s u m m a t i o ns e t i s r e f e r r e dt oa st h ec o m p l e t e m a t c h i n ge f i nt h i st e c h n i q u e ，t h eb e s te s t i m a t eo f t h em o t i o n v e c t o r ，( “a ，v a ) ，i st h e 似w w h i c hm i n i m i z e sm a d ( ) ( “，v ) ，i e ， ( “，v ) - a r g r a m i n 。m m d ( 。) ( 则) ， ( 1 2 ) w h e r e sesd e f i n e st h es e a r c hs e t ，s = ( u ，v ) i p u ，v pa n d ( x + u ，y + v ) i sa v a l i dp o s i t i o ni nso f l 一) ，a n dpi sa ni n t e g e rw h i c hd e f i n e st h er a n g eo fs t h e s i m p l e s t m e t h o dt oe v a l u a t et h em o t i o nv e c t o r ( “v1i s b yu s i n g t h e 力l l s e a r c h ( f s ) a l g o r i t h m o r t h es oc a l l e de x h a u s t i v es e a r c h a l g o r i t h m ，w h i c h 6 c a l c u l a t e sa n dc o m p a r e st h ef u l lv a l u e so f m a d s ( i e ，t h ec o m p l e t em a t c h i n ge r r o r s ) f o ra l lt h es e a r c hp o s i t i o n s ， 0 + my + v ) ) ，i nt h es e a r c hs e ts ( i e s = s ) i nt h e r e f e r e n c e i m a g e 丘，u n f o r t u n a t e l y ，f r o m ( 1 1 ) a n d ( 1 2 ) ，w ec a i ls e e t h a t t h e f u l l s e a r c h a l g o r i t h mr e a l l yi n v o l v e se x t r e m e l yl a r g ea m o u n t o f c o m p u t a t i o n st of i n dt h eo p t i m a l m a t c h ，a n dt h u si st h em o s ti n e f f i c i e n tw a y t of i n dt h em i n i m u m m a t c h i n g e r r o r s i n c e t h es p e e do fm a t c h i n gp r o c e s sd i r e c t l ya f f e c t st h ee f f i c i e n c yo ft h eo v e r a l lv i d e o p r o c e s s i n g ，m a n y f a s tb l o c k m a t c h i n ga l g o r i t h m sh a v eb e e n p r o p o s e d t h i sr e p o r ti sa r te f f o r tt oc l a s s i f y ，d i s c u s st h eb a s i ci d e aa n dm e c h a n i s m o f o p e r a t i o n ， a n d c o m p a r e t h ea d v a n t a g e sa n d d i s a d v a n t a g e so fd i f f e r e n tb l o c km a t c h i n ga l g o r i t h m s ， w h i c hh a v eb e e np r o p o s e di nt h ep a s t ，t h e ni n t r o d u c e san e wf a s tb l o c km a t c h i n g a l g o r i t h m l o w e r b o u n d c o m p a r i s o na l g o r i t h m w h i c ha c h i e v e sm o r e c o m p u t i n g e f f i c i e n c yi nf i n d i n go u tt h eo p t i m a lm a t c h i n gp o s i t i o nb ya d o p t i n gas t r a t e g yt h a t c o m p u t e so n l yp a r t i a la m o u n to fm a d ，i n s t e a do ff u l lm a d ，f o rm o s to f t h es e a r c h p o s i t i o n s t h er e p o r t 矗o r g a n i z e da sf o l l o w s f i r s t i ns e c t i o n2 t h em o t i o ne s t i m a t i o n a l g o r i t h m sa r ec l a s s i f i e di n t ot h r e em a j o rc a t e g o r i e s ，a n dt h er e p r e s e n t a t i v ea l g o r i t h m s i ne a c h c a t e g o r y a r ef u r t h e rs u b d i v i d e di n t o s u b c a t e g o r i e sa c c o r d i n g t ot h e i r c h a r a c t e r i s t i c sa n dp r e s e n t e di nd e t a i l t h ea d v a n t a g e so f c o m b i n i n g o ft h ea l g o r i t h m s f r o mv a r i o u ss u b c a t e g o r i e sa r ea l s op r e s e n t e da n de x p l o r e d i ns e c t i o n3 ，w ei n t r o d u c e t h ec o n c e p to f t h el o w e rb o u n d c o m p a r i s o ns t r a t e g ya n dt h ep r o p o s e da l g o r i t h m t h e n ， t h ec o m b i n a t i o no f t h e p r o p o s e da l g o r i t h ma n d t h et s s a l g o r i t h mi sp r e s e n t e d s e c t i o n 4 p r e s e n t s t h e e x p e r i m e n t a l r e s u l t so ft h e p r o p o s e da l g o r i t h m a sw e l la ss o m e p r e v i o u s l yd e v e l o p e da l g o r i t h m s a n dc o m p a r e st h e i r p e r f o r m a n c e f i n a l l y ，s o m e d i s c u s s i o n sa n dc o n c l u s i o n sa r es t a t e di ns e c t i o n s5 2 b a e k g r o u n d a n dl i t e r a t u r er e v i e w f r o m t h e e q u a t i o n s ( 1 1 ) a n d ( 1 2 ) a b o v e ，w ec a n s e e t h a t i tr e a l l y i n v o l v e se x t r e m e l y l a r g ea m o u n to fc o m p u t a t i o n st of i n dt h eo p t i m a lm a t c h ，p a r t i c u l a r l yf o rf u l l - s e a r c h a l g o r i t h m ，w h i c hc o m p u t e st h ec o m p l e t em a t c h i n g e r r o rf o re v e r b l o c k a st h es p e e d o f m a t c h i n gp r o c e s sd i r e c t l ya f f e c t st h ee f f i c i e n c yo f o v e r a l li m a g ep r o c e s s i n g ，m a n y f a s tb l o c km a t c h i n ga l g o r i t h m sh a 、，eb e e np r o p o s e d u pt o d a t e b l o c km a t c h i n g 7 a l g o r i t h m s t e c h n i q u e s c a nb ec l a s s i f i e di n t ot h r e ec a t e g o r i e s 2 1c a t e g o r yl ：p a r t i a l - s e a r c h - s e tt e c h n i q u e s t e c h n i q u e s o f t h i sc a t e g o r y 【2 卜【1 0 s a v e t h ec o m p u t a t i o n s b y r e d u c i n g t h e n u m b e r o f p o s i t i o n ss e a r c h e d m o r es p e c i f i c a l l y ，m a t c h i n ge r r o r sa r ec a l c u l a t e da n dc o m p a r e d w i t h i nas u b s e to ft h ec o m p l e t es e a r c hs e t ，s ，d e f i n e db y ( 1 2 ) c o n s e q u e n t l y ，t h e m i n i m u mo fm a t c h i n ge r r o rf o u n di su s u a l l yal o c a l o n e t h ee f f i c i e n c yo ft h e s e t e c h n i q u e sd e p e n d so n t h en u m b e ro ft h es e l e c t e ds e a r c hp o s i t i o n s ，w h i l et h er e s u l t i n g m i n i m u mm a t c h i n ge r r o rd e p e n d so nh o w t h es e a r c hp o s i t i o n sa r es e l e c t e d t h ed e s i g n i s s u eo ft h e s et e c h n i q u e si sh o w t of i n dt h em o t i o nv e c t o rw i t has m a l lm i n i m u m m a t c h i n ge r r o rb ye x a m i n i n g a ss m a l ln u m b e ro fs e a r c hp o s i t i o n sa sp o s s i b l e a l m o s t a l la l g o r i t h m si nt h i sc a t e g o r ya r eb a s e d o i lu n i m o d a le r r o rs u r f a c ea s s u m p t i o n ，i e ，t h e m a t c h i n g e r r o ri n c r e a s e sm o n o t o n i c a l l ya st h es e a r c hm o v e sa w a y f r o mt h ep o s i t i o no f t h eg l o b a lm i n i m u me r t o r h o w e v e r ，t h i sa s s u m p t i o ni sg e n e r a l l yn o tt r u eu n l e s st h e s e a r c hs t a r t sf r o mp o s i t i o n sw h i c h a r ec l o s ee n o u g ht ot h eg l o b a lm i r f i m u a lp o s i t i o n ， a n dt h u st h ea s s u m p t i o nc a n h a v et h ea l g o r i t h mt r a p p e da tal o c a lm i n i m u m 2 1 1g r a d i e n t d e s c e n t t e c h n i q u e s u s i n g p i x e l - b y p i x e l s e a r c h w i t h s t e p s i z eo f o n e a t y p i c a le x a m p l e o f a l g o r i t h m si nt h i ss u b c a t e g o r y i st h ec o n j u g a t ed i r e c t i o ns e a r c h a l g o r i t h m ( c d s ) 2 a s d e s c r i b e db e l o w s t e p ：t h ec o s tf u n c t i o n i sf i r s tc a l c u l a t e da t ( o ，o ) ，( 1 ，o ) a n d ( _ 1 ，o ) i nt h exd i r e c t i o n i f ( 1 ，o ) i st h em i n i m u m ，( 2 ，o ) i sc o m p u t e d a n de v a l u a t e d t h ep r o c e s si sc o n t i n u o u s u n t i lam i n i m u m i sf o u n dt ob es a n d w i c h e db e t w e e n2h i g h e rv a l u e s s t e p 2 ：t h es e a r c hn o wc o n t i n u e si nt h eyd i r e c t i o ns t a r t i n gf r o mt h em i n i m u m p o s i t i o n ， t w op o s i t i o n si m m e d i a t e l ya b o v ea n d b e l o wi t ，a n dp r o c e e d si nt h es a m em a n n e r a si n s t e p1 u n t i las a n d w i c h e dm i n i m u m o fc o s tf i m c t i o ni sf o u n da g a i n s t e p3 ：s e a r c hi nt h ed i r e c t i o nc o n n e c t i n gt h es t a r t i n gp o i n t ( 0 , 0 ) a n dt h em i n i m u m o b t a i n e di ns t e p2 ，f o re x a m p l e ，( 2 ，2 ) t h e f o l l o w i n g s e a r c hl o c a t i o n sa r ee v a l u a t e dn e x t ： ( 1 ，1 ) ，( 3 ，3 ) ，a n ds oo n ，u n t i las a n d w i c h e dm i n i m u mi nt h i sd i r e c t i o ni sf o u n da g a i n w h i c hi st h ef i n a lm a t c h i f xa n d yv e c t o r so b t a i n e di ns t e p s1a n d2 ，d on o tc o n s t i t u t ea s q u a r e ，t h ec l o s e s td i r e c t i o nw h i c hf o r m sa na n g l eo f4 5d e g r e e sw i t hb o t hxa n dy d i r e c t i o n si sc h o s e nf o rt h es e a r c ht oc o n t i n u e c d su s u a l l yc a nb et r a p p e da tal o c a lm i n i m u m ，a n dt h en u m b e ro ft h es e a r c h p o s i t i o n se x a m i n e dd e p e n d so nt h ed i s t a n c e b e t w e e nt h ei n i t i a l p o s i t i o na n dt h e v a l l e y ”p o s i t i o n a s i m p l ev a r i a t i o n t oc d si so n e a t - a - t i m es e a r c h ( o t s ) 【2 ， 3 t h i si se s s e n t i a l l y s t o p p i n gt h ec a l c u l a t i o n a f t e r s t e p s1a n d 2i nt h ec d s a l g o r i t h m i tm e a n s t h a tw el o o k f o ram i n i m u mi nt h exd i r e c t i o nf i r s ta n d p r o c e e d f r o mt h e r ei nt h eyd i r e c t i o nt of i n d t h eb e s tm a t c h p o s i t i o n 2 1 2g r a d i e n td e s c e n t t e c h n i q u e su s i n gc o a r s e t o f i n es e a r c h t h ea l g o r i t h m si nt h i ss u b c a t e g o r yi n v o l v es e v e r a ls e a r c hs t e p s s t a r t i n gf r o mt h e o r i g i np o s i t i o n ，t h em a t c h i n ge r r o r so fs e v e r a lc o a r s e l y - s p a c e ds e a r c hp o s i t i o n sa r e c a l c u l a t e da n dt h eo n ew i t ht h em i n i m u mi ss e l e c t e da s 也en e w s t a r t i n gp o s i t i o no f t h e n e x t s t e p t h i sp r o c e d u r e i sr e p e a t e ds e v e r a lt i m e sw i t has m a l l e ra n d s m a l l e r ( i e ，f i n e r ) s p a c i n gb e t w e e nt h e s e a r c hp o s i t i o n su n t i lt h e s p a c i n go fo n ep i x e l i sr e a c h e d e x a m p l e s o ft h i s s u b c a t e g o r y i n c l u d e t h r e e s t e p s e a r c h a l g o r i t h m 4 1 ，a n d i t s i m p r o v e m e n t s 【5 _ 【7 ，t h et w o d i m e n s i o n a ll o g a r i t h m i cs e a r c ha l g o r i t h m 【8 】，a n d t h e c r o s s s e a r c ha l g o r i t h m 【9 a t h r e e - s t e ps e a r c h ( t s s ) a l g o r i t h m i nt h i sa l g o r i t h m 【4 ，i n i t i a l l yt h eb l o c ka tt h ec e n t r eo f t h es e a r c ha r e ai ss e tt ob et h e b e s t m a t c h i n gb l o c ka n di t sm a t c h i n ge r r o r i s c o m p u t e d a s s u m et h a t t h es e a r c h p a r a m e t e ri sp ，a n dt h es t e ps i z esi s s e tt ob ep 2 m a t c h i n ge r r o r so ft h e8p o s i t i o n s s u r r o u n d i n gt h ec u r r e n tb e s tm a t c hp o s i t i o n a r ec a l c u l a t e d t h e s e8 p o s i t i o n s a r e l o c a t e d a t - s 。一s 1 。 - s 0 】。 - s + s j 。l o 。一s 】。l o ，七s j 。( + s - s 】，l s ，o j ? l + s ， s j a m o n g t h e 9 t o t a lo f9 p o s i t i o n s ，t h eo n ew i t ht h em i n i m l u t lm a t c h i n ge r r o ri ss e l e c t e da st h en e x t b e s tm a t c h a f t e rt h es t e ps i z ei sr e d u c e d ，u s u a l l yb yd e c r e m e n t i n go rh a l v i n g ，t h e8 p o s i t i o n sd e f i n e di nt h es a m e m a n n e ra sa b o v ea r o u n dt h i sn e wb e s tm a t c hb l o c k ，a r e e x a m i n e db y c a l c u l a t i n gt h e i rm a t c h i n ge r r o r s a g a i na m o n g t h e s e9p o s i t i o n s ，t h eo n e h a v i n gt h em i n i m u mm a t c h i n g e r r o ri ss e l e c t e da st h en e x tb e s tm a t c h t h i sp r o c e s si s r e p e a t e d a f t e rt h es t e ps i z eo fo n e p i x e li sr e a c h e d l i k eo t h e ra l g o r i t h m si nc a t e g o r y1 ，t h ec h o i c eo ft h es t a r t i n gp o s i t i o ni si m p o r t a n t i no r d e rt oa v o i dt s sb e i n gt r a p p e da tal o c a lm i n i m u me r r o ra n dt oi m p r o v et h e m a t c h i n ga c c u r a c y o n es o