I n te r n ati o n al   Jo u r n al   o El e c tr i c a l   an d   C o m p u te r   En gi n e e r i n g   (I JEC E )   V o l .   7 ,   N o .   1 F e b r ua r y   201 7 ,   pp .   2 16 ~ 2 24   IS S N :   2088 - 8708 D O I :   10. 1 1591 / i j e c e . v7 i 1 . pp216 - 22 4             216       Jou r n al   h o m e pa ge ht t p: / / i ae s j o ur nal . c om / on l i n e / i nde x . php/ IJ E C E   A   S u r v e y   o n   B l o c k   M a t c h i n g   A l g o r i t h m s f o r   V i d e o   C o d i n g       A d ap V e n k ata   P ar am k u s am V u yy u r u   A r u n   D e pa r t m e n t   o f   E l e c t r o ni c s   a nd   C o m m uni c a t i o n   E ng i ne e r i ng ,   M L R   I ns t i t u t e   o f   T e c hno l o gy ,   H y de r a ba d,   I ndi a       A r ti c l e   I n fo     A B S TR A C T   Ar t i c l e   h i s t or y :   R e c e i v e O c t   7 ,   201 6   R e v i s e D e c   3 0 ,   201 6   A c c e pt e J a n   1 5 ,   201 7       B l o c m a t c hi ng   a l g o r i t hm   ( B M A )   f o r   m o t i o e s t i m a t i o ( M E )   i s   t h e   he a r t   t m a ny   m o t i o n - c o m pe ns a t e v i de o - c o di ng   t e c hni qu e s / s t a n da r ds ,   s u c a s   I S O   M P E G - 1/ 2 / a n I T U - T   H . 261/ 26 2/ 2 63 / 264 / 26 5,   t o   r e d uc e   t he   t e m po r a l   r e du nda nc y   be t w e e di f f e r e n t   f r a m e s .   D ur i ng   t he   l a s t   t h r e e   de c a de s ,   hund r e d s   o f   f a s t   b l o c m a t c hi ng   a l g o r i t hm s   ha v e   b e e pr o po s e d .   T he   s ha p e   a nd  s i z e   o f   s e a r c pa t t e r ns   i m o t i o e s t i m a t i o w i l l   i nf l ue nc e   m o r e   o t he   s e a r c hi ng   s p e e a nd  qua l i t y   of   pe r f o r m a nc e .   T h i s   a r t i c l e   pr o v i de s   a n   o v e r v i e w   of   t he   f a m o us   bl o c m a t c hi ng   a l g o r i t hm s   a n c o m p a r e s   t h e i r   c om put a t i o na l   c o m pl e x i t y   a nd   m o t i o p r e d i c t i o n   qua l i t y .   Ke y w or d:   B l oc m a t c hi n g   a l go r i t hm   M o t i o n   e s t i m a t i o n   M o t i o n   v e c t o r   S e a r c h   p a t t e rn   C opy r i gh t   ©   201 7   I n s t i t ut e   o f   A dv anc e E ng i ne e r i ng   and   S c i e nc e   A l l   r i gh t s   r e s e r v e d .   Cor r e s pon di n g   Au t h or :   A da pa   V e nka t a   P a ra m k us a m ,   D e pa rt m e n t   o f   E l e c t r o n i c s   a n Co m m u ni c a t i o E n g i n e e ri n g ,   M L R   In s t i t ut e   o f   T e c hn o l o g y ,   H y de r a b a d,   I n di a .   E m a i l :   a d a pa 74@ gm a i l . c o m       1.   I N TR O D U C TI O N   T h e   m a i n   o b j e c t i ve   o b l o c m a t c hi n a l go ri t hm s   i s   t o   de t e r m i n e   t h e   di r e c t i o n   a n m a g ni t ude   of  m o t i o n   ( m o t i o v e c t o r f o r   a   m a c r o b l o c k   i n   t h e   c u rr e n t   f r a m e   r e l a t i v e   t o   t h e   b e s t   m a t c h e c a n di da t e   b l o c i n   t h e   r e f e r e n c e   f r a m e .   T h e   s e a r c h   f o r   t h e   b e s t   m a t c h i ng  c a n di da t e   b l o c m a y   b e   c a rri e o ut   by   c o m pa ri n t h e   m a c r o b l oc i n   t h e   c urr e n t   f r a m e   w i t h   s o m e   o r   a l l   t h e   po s s i b l e   c a n d i da t e   b l oc ks   i n   a   s e a r c h   w i n do w F ul l - S e a r c h   (F S i s   a n   e x h a us t i v e   s e a r c h   a l go r i t h m   a nd  i t   i s   t h e   s i m pl e s t   m e t h o t o   f i n t h e   o pt i m a l   m o t i o n   v e c t o r s   fo r   e a c m a c r o b l o c k.   It   de t e rm i n e s   t h e   b e s t   m a t c h e c a n d i da t e   b l o c t hr o ug h   c a l c ul a t i n t h e   S um   of  A b s o l ut e   D i ff e r e n c e   (S A D fo r   a l l   c a n di d a t e   b l o c ks   i n   t h e   s e a r c h   w i n do w .   A l t h o ugh   F u l l - S e a r c h   c a n   o b t a i n   t h e   gl o b a l   o pt i m a l   r e s ul t ,   i t   h a s   v e r y   i n t e n s i v e   c o m put a t i o n s .   T o   r e duc e   t h e   c o m pl e xi t y   of   F ul l - S e a r c h,   s e v e r a l   f a s t   s e a rc h   m o t i o n   e s t i m a t i o a l go r i t hm s   h a v e   b e e n   pr o po s e a t   t h e   p r i c e   of   s l i gh t l y   i m pa i r e P e a S i gna l - to - N o i s e   R a t i o   (P S N R )   pe r fo r m a n c e .   A   po s s i b l e   c l a s s i f i c a t i o n   o f   t h e s e   f a s t   s e a r c h   m o t i o n   e s t i m a t i o n   a l go ri t hm s   i nt o   t h e   f o l l ow i n c a t e go r i e s :   r e d uc t i o n   i s e a r c h   po s i t i o n s   [1 - 9],   p r e di c t i v e   s e a r c [10 - 14 ],   s e a r c pa t t e rn   s w i t c hi n g   [15] ,   [ 1 6] ,   m u l t i - r e s o l ut i o   s e a r c h   [17 - 20]  a n F r a c t i o na l - P i xe l   I n t e r po l a t i o n   [2 1 - 22] .   E xi s t i ng  f a s t   s e a r c h   m o t i o n   e s t i m a t i o n   a l go r i t hm s   us e   o n e   o r   a   c o m b i n a t i o n   o f   t h e s e   c a t e go r i e s .   A   po pul a r   e xa m pl e   i s   t h e   t hr e e - s t e s e a r c h   (T S S a l go r i t h m   [1].   H ow e ve r ,   i t s   u ni f o r m l y   s pa c e s e a r c h   pa t t e rn   i s   n o t   w e l l   m a t c h e t o   m o s t   r e a l - w o r l v i de o   s e que n c e s   i n   w h i c h   t h e   m o t i o n   v e c t o r   di s t ri b ut i o n   i s   n o n - u ni f o r m l y   b i a s e t ow a r t h e   z e r o   ve c t o r .   S uc h   a n   o b s e r v a t i o n   i n s pi r e t h e   n e w   t hr e e - s t e s e a r c h   (N T S S w hi c h a s   a   c e n t r e - b i a s e s e a r c p a t t e rn  a nd  s uppo r t s   a   ha l f w a y - s t o t e c h n i q ue   [2].   T h e   c e n t r e - b i a s e N T S S   a l go r i t h m   i s   a n   i m p r o v e d   ve r s i o n   o T S S ,   t e n ds   t o   a c h i e v e   m uc h   s upe r i o pe r f o r m a n c e   w i t h   f e w e r   n u m b e r   o f   s e a r c h   po i nt s   o n   a v e ra ge .   T h e   s e a r c pa t t e rn  h a s   a n   i m po r t a n t   i n f l ue n c e   o s pe e a n d   di s t o r t i o pe r f o r m a n c e   i b l o c m o t i o n   e s t i m a t i o n.   In   T S S   a n N T S S   a l go r i t hm s   s qua r e - s ha pe s e a r c h   p a t t e rns   of   di ffe r e n t   s i z e s   a r e   e m pl oy e d.   T h e   D i a m o n s e a r c h   (D S a l go r i t hm   a do pt s   a   di a m o nd - s h a pe s e a r c h   pa t t e rn   [3] ,   w h i c h   i s   m o r e   e f f i c i e n t   t ha n   Evaluation Warning : The document was created with Spire.PDF for Python.
IJ E CE     IS S N :   2088 - 8708       A   Sur v e y   on  B l o c k   M at c hi ng   A l gor i t hm s   f or   V i de o   Cod i ng   ( A dapa  V e n k a t P ar am k us am )   217   s qua r e - s ha pe s e a r c h   pa t t e rn s   T S S   a n d   N T S S .   T h e   s e a r c pa t t e rn s   i n   D S   a l go r i t h m   a r e   de r i v e f r o m   t h e   c h e c ki ng  po i n t s   w i t hi n   c i r c l e   o f   r a di u m   o f   pe l s .   T h e   h e xa g o n   b a s e s e a r c h   a l go r i t hm   [4]  w a s   de v e l o p e b y   i n v e s t i g a t i ng  w h y   t h e   D S   pa t t e rn  c a n   y i e l s pe e i m pr o v e m e n t   o v e r   s o m e   s qua r e - s h a pe s e a r c h   p a t t e rn s   a n w h a t   t h e   m e c ha n i s m   b e h i nd  i s .   H e xa go n - b a s e s e a r c h   (H S a l go ri t hm   c a a c hi e v e   s u b s t a nt i a l   s pe e i m p r o v e m e n t   o v e r   t h e   D S   a l go ri t hm   w i t h   s i m i l a r   d i s t o rt i o n   pe r f o r m a n c e .   T h e   e nh a n c e v e r s i o n s   o f   h e xa go n a l   s e a r c h   a l go r i t hm   [6 - 8]  ha v e   b e e n   p r o po s e fo r   f ur t h e r   r e duc t i o n   o f   t h e   s e a r c h   p o i n t s   o v e r   H e xa go n a l   S e a r c h   a l go r i t hm .   T h e s e   a l go ri t hm s   m a i n l y   c o n c e n t ra t e   o t h e   f a s t   i nn e r   s e a r c h   t e c hn i que   t o   i m p r o v e   t h e   i nn e s e a r c s pe e d.   T h e   m a i purpo s e   of   t h i s   pa pe r   i s   t o   m a ke   a   c o m pr e h e n s i v e   s t ud y of   b l o c m a t c h i ng  a l go r i t h m s .   Co m pa ri s o n s   i n   m a n y   di r e c t i o n s   a r e   m a de   f o r   s y s t e m   de s i gn e r s   t o   de t e r m i n e   t h e   b e s t   t ra de o ff .   T h e   r e s t   o t h i s   pa pe r   i s   o r g a n i z e a s   fo l l ow s .   In   s e c t i o n   II ,   T h e   w e l l   kn o w n   b l o c m a t c hi n a l go ri t hm s   s uc h   a s   t hr e e   s t e s e a r c h ,   N e w   t hr e e   s t e s e a r c h ,   D i a m o n s e a r c h ,   H e xa go n   b a s e s e a r c h   a n e nh a n c e ve r s i o n s   o f   h e xa go na l   s e a r c h   a l go ri t hm   ha v e   b e e n   di s c us s e d.   S e c t i o n   I II  i s   de v o t e t o   t h e   d i s c us s i o n s   o t h e   e xpe ri m e n t a l   r e s ul t s   f o r   v a r i o us   s e que n c e s .   F i na l l y ,   s e c t i o n   IV   c o n c l ude s   t h i s   pa pe r.       2.   O V ER V I EW   2. 1 .   Th r e e   S t e p   S e ar c h   (TS S )   B l o c k   M at c h i n g   A l go r i th m   T hr e e   S t e S e a r c h   (T S S i s   o n e   o t h e   f i r s t   n o n   f ul l   s e a r c h   a l go r i t hm s   a n w a s   i nt r o duc e by   K o ga   e t   a l   [1]  i n   1981 .   It   s e a r c h e s   fo r   t h e   b e s t   m o t i o n   ve c t o r s   i n   t hr e e   s t e ps .   T h e   s e a r c h   pa t t e rn   o f   T S S   i s   s h o w n   i n   F i gu r e   1.   I n   t h e   f i r s t   s t e b l oc ks ,   a t   a   d i s t a n c e   o s t e s i z e   e qua l   t o   o r   s l i g ht l y   l a r ge r   t ha n   ha l f   of   t h e   m a x i m u m   s e a r c h   r a nge ,   f r o m   t h e   c e n t r e   po i n t   c o rr e s po n d i n t o   z e r o   m o t i o n   v e c t o r   a r e   s e l e c t e fo r   c o m pa ri s o n .   I n   t h e   s e c o n s t e t h e   s t e s i z e   i s   h a l v e d,   t he   c e n t r e   po i n t   i s   m o v e t o   t h e   po i n t   w i t h   t h e   m i ni m u m   di s t o r t i o n .   S t e p - a n s t e p - a r e   r e pe a t e t i l l   t h e   s t e s i z e   be c o m e s   s m a l l e r   t h a n   o n e .   It   i s   m a i n l y   us e fo r   r e a l   t i m e   v i de o   c o m pr e s s i o n   w i t l o w   b i t   ra t e   v i de o   a ppl i c a t i o s uc a s   v i de o   c o n f e r e n c i n g   a n d   v i de o ph o n e .   T h e   T S S   i s   o n e   o f   t h e   m o s t   po pul a r   B M A s   a n d   i s   a l s o   r e c om m e n de by   R M of   H . 261  a n d   S M o M P E G   o w i n t o   i t s   s i m p l i c i t y   a n e f fe c t i ve n e s s .   F o r   a   m a xi m u m   d i s pl a c e m e n t   w i n do w   of   i . e .   d = 7,   t h e   n u m b e r   o f   c h e c ki ng  po i nt s   r e qui r e i s   (9 + 8+ 8)  = 25 .   F o r   a   m a xi m um   di s pl a c e m e nt   w i n do w   o f „d‟,   t h e   n u m b e r   of   c h e c ki ng  po i n t s   r e qui r e d   e qua l s   t o   [1 + 8{ l o g2(d + 1)} ] .                 F i g u r e   1 .   E xa m p l e   o f   T hr e e   S t e p   S e a r c P a t h   t o   Lo c a t e   a   M o t i o V e c t o r   a t   ( - 3 ,   2)       2. 2 .   N e w   Th r e e   S t e p   S e a r c h   (N TS S )   B l o c k   M at c h i n g   A l go r i th m   T h i s   a l go r i t hm   w a s   p r o po s e by   R e n xi a n g   L i ,   B i n g   Z e n a n M i ng  L . L i o [2] .   I t   i s   a   m o di f i e v e r s i o n   o f   t h e   t hr e e   s t e s e a r c h   a l go r i t h m   f o r   s e a r c hi n s m a l l   m o t i o v i de o   s e que n c e s .   F o r   t h e s e   v i de s e que n c e s ,   t h e   m o t i o n   v e c t o r   di s t ri b ut i o i s   hi g h l y   c e n t r e   b i a s e d.   T h e r e f o r e ,   i n   a ddi t i o n   t o   t h e   o ri gi na l   c h e c ki ng  po i n t s   us e i n   T S S ,   e xt ra   n e i g h b o ur i ng  c h e c ki n g   po i nt s   o f   s e a r c h   w i n do w   c e n t r e   a r e   s e a r c h e i n   t h e   f i r s t   s t e o f   N T S S   (t o t a l   17)  a s   s h o w n   F i g u r e   2.   T h e r e   a r e   t hr e e   c a s e s   w h e r e   t h e   m i ni m u m   B D M   po i n t   o c c ur s .   a.   F o r   s t a t i o n a r y   b l oc t h e   m i ni m um   B D M   po i nt   o c c ur s   a t   t h e   s e a r c h   w i n do w   c e n t r e   t h e n   s e a r c h i n g   w i l l   s t o p   (T h i s   i s   c a l l e d   f i r s t   s t e p   s t o p).   b.   F o r   qua s i   s t a t i o n a r y   b l oc (s m a l l   m o t i o n   v i de o   s e que n c e t he   m i n i m u m   B D M   p o i nt   o c c ur s   a t   a n y   o n e   of  t h e   e i g h t   n e i g h b o ur s   o f   t h e   s e a r c h   w i n do w   c e n t r e ,   t h e   s e a r c h   i n   t h e   s e c o n s t e w i l l   b e   pe r f o r m e o n l y   fo r   e i ght   n e i g h b o ur i ng  po i n t s   o f   t h e   m i n i m um   B D M   po i n t   a nd  t h e n   s t o t h e   s e a r c h   ( T hi s   i s   c a l l e s e c o n s t e s t o p).   D e pe n di n o n   po s i t i o n   o t h i s   m i ni m u m   B D M   po i n t ,   o n l y   f i v e   o r   t hr e e   n e w   c h e c ki n po i nt s   a r e   Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2088 - 8708   IJ E CE     V o l .   7 ,   N o .   1 F e b r ua r y   2017   :     2 16     2 24   218   r e qui r e d   t o   b e   t e s t e d.   T h e   n u m b e r   o f   c h e c ki n po i nt s   r e qu i r e i s   t h e n   e i t h e r   (1 7+ 3)   = 20  o r   ( 17+ 5 = 22 .     c.   If   t h e   m i ni m um   B D M   po i nt   o c c ur s   a t   a n y   o n e   of   t h e   r e m a i ni n g   e i g h t   c h e c ki ng  po i n t s   t h e n   c o m pl e t e   t hr e e   s t e s e a r c h   w i l l   b e   e xe c ut e d.   In   t h e   w o r s t   c a s e   (i . e .   t h e r e   i s   n o   s i n gl e   s t a t i o na r y   b l oc k)  t h e   N T S S   r e qu i r e s   33  b l oc m a t c h e s   a s   c o m pa r e t o   25  m a t c h e s   i n   T S S .   E i g h t   b l oc m a t c h e s   w i l l   b e   s a ve o n c e   a   f i r s t   s t e p - s t o o c c ur s .   D e pe n d i n o n   t h e   po s i t i o n   o f   t h e   m i n i m um   B D M   po i n t   (i n   t h e   f i r s t   s t e p)  o n   t h e   n e i g h b o ur s   of   t h e   w i n dow   c e n t r e ,   f i v e   o r   t hr e e   b l o c m a t c h e s   w i l l   be   s a v e d   o n c e   a   s e c o n s t e p - s t o oc c ur s : (1)  i f   t h e   m i ni m u m   i s   o n e   o f   t h e   fo ur   n e i g h b o ur i ng  po s i t i o n s   a l o n t he   h o ri z o nt a l   o r   v e rt i c a l   di r e c t i o n s ,   f i v e   b l o c k   m a t c h e s   w i l l   b e   s a v e d; (2)  i f   t h e   m i ni m um   i s   o n e   o f   t h e   fo ur   n e i g h b o ur i ng  po s i t i o n s   a l o n t h e   t w di a go n a l   d i r e c t i o n s ,   t hr e e   b l o c m a t c h e s   w i l l   b e   s a v e d.   T h e   n u m b e r   of   b l oc m a t c h e s   n e e de i n   N T S S   fo r   e s t i m a t i n g   a   b l o c m o t i o n   v e c t o r   c a n   b e   e s t i m a t e by   17P +   20P 2   +   22P 2'   +   33  (   1 - P1 - P2 -   P 2' ) ,   w he r e   P i s   t h e   p r o b a b i l i t y   of   o c c urr i ng  a   f i r s t   s t e p - s t o w h i l e   P a n P 2'     a r e   r e s pe c t i v e l y   pr o b a b i l i t i e s   of   o c c urr i n a   s e c o n s t e p - s t o i n   t h e   t w o   c a s e s   m e nt i o n e a b ov e .   T h e s e   pr o b a b i l i t i e s   a r e   de pe n de n t   o n   h o w   m a n y   s t a t i o n a r y   o r   qu a s i - s t a t i o n a r y   b l oc ks   a   v i de o   f r a m e   c o nt a i n s .           F i g u r e   2.    Ci r c l e s   a r e   t h e   c h e c ki n g   po i n t s   i t h e   f i r s t   s t e p   o f   T S S ,   t r i a n g l e s   a r e   t h e   8   e xt r a   po i n t s   a d de i t h e   f i r s t   s t e o f   N T S S ,   a n d   s qua r e s   a r e   t h e   n e w   c h e c ki n g   po i n t s   ( o 5)   i t h e   s e c o n s t e de pe n d i n g   o m i ni m u m   B D M   po i nt ,   i t h e   f i r s t   s t e p ,   o n   t h e   8   n e i g h b o r s   o f   t h e   w i n do w   c e n t r e       2. 3 .   D i am o n d   S e ar c h   (D S )   B l o c k   M at c h i n g   A l go r i th m     T h e   di a m o n s e a r c h   a l go r i t hm   (D S i s   p r o po s e by   S .   Z h a n K .   K .   M a   [3] . It   i s   b a s e o n   M V   di s t r i b ut i o n   o f   r e a l   w o r l v i de o   s e que n c e s .   It   i s   a n   o ut s t a n di n a l go r i t hm   a do pt e by   M P E G - v e r i f i c a t i o n   m o de l   (V M due   t o   i t s   s upe r i o r i t y   t o   o t h e r   m e t h o ds   i n   t h e   c l a s s   of   f i xe s e a r c h   pa t t e rn   a l go ri t hm s .   I t   e m pl o y s   t w s e a r c h   p a t t e rn s   a s   s h o w n   i n   F i g u r e   3,   w hi c h   a r e   de r i v e f r o m   t h e   c h e c ki n po i nt s   w i t hi n   c i r c l e   of   r a di um   of   2   pe l s .   T h e   f i r s t   pa t t e rn,   c a l l e l a r ge   d i a m o n s e a r c h   p a t t e rn   (L D S P c o m pr i s e s   n i n e   c h e c ki ng  po i n t s   a nd  fo r m   a   di a m o n s ha pe .   T h e   s e c o n pa t t e rn   c o n s i s t i n o f   f i ve   c h e c ki n po i n t s   f o r m s   a   s m a l l e r   d i a m o n d   s h a pe ,   c a l l e S m a l l   di a m o nd  s e a r c h   pa t t e rn   (S D S P ). T h e   s e a r c h   s t a rt s   w i t h   t h e   L D S P   w h i c h   i s   c e nt e r e a t   t h e   o ri g i n   of   t h e   s e a r c h   w i n do w ,   a n t h e   c h e c ki ng  po i n t s   o f   L D S P   a re   t e s t e d.   If   t h e   m i ni m u m   b l o c di s t o r t i o n   (M B D )   c a l c ul a t e d   i s   n o t   l o c a t e a t   t h e   c e nt r e   po s i t i o n,   n e w   L D S P   i s   f o r m e w hi c i s   c e nt e r e a t   t h e   M B D   po i n t   fo un i nt h e   s e a r c h .   T h e   s e a r c h   p r o c e dur e   i s   r e pe a t e u nt i l   M B D   o c c ur s   a t   t h e   c e n t r e   po i n t .   A t   a n y   s t a ge   i M B D   o c c ur s   a t   c e n t r e   o f   L D S P ,   t h e   s e a r c h   pa t t e rn   i s   s w i t c he t o   S D S P   a s   r e a c h i ng  t o   t h e   f i na l   s e a r c h   s t a ge .   A m o n t h e   f i v e   c h e c ki n po i n t s   i n   S D S P ,   t h e   po s i t i o n   y i e l di n t h e   M B D   pr o v i de s   t h e   m o t i o n   v e c t o r   of   t h e   b e s t   m a t c h i n g   b l o c k.           (a )                                                     (b )     Evaluation Warning : The document was created with Spire.PDF for Python.
IJ E CE     IS S N :   2088 - 8708       A   Sur v e y   on  B l o c k   M at c hi ng   A l gor i t hm s   f or   V i de o   Cod i ng   ( A dapa  V e n k a t P ar am k us am )   219   F i g u r e   3 .   S e a r c h   P a t t e rn s   o f   D S   (a L D S P   w i t S e a r c P o i nt s   (b S D S P   w i t h   5   S e a r c h   P o i n t s   T h e   c h e c ki ng  po i nt s   a r e   pa r t i a l l y   ov e r l a ppe b e t w e e n   a dj a c e n t   s t e ps ;   e s pe c i a l l y ,   w h e n   L D S P   i s   r e pe a t e dl y   us e d.   F o r   i l l us t ra t i o n ,   t hr e e   c a s e s   of   c h e c ki ng - po i n t   o v e r l a pp i n a r e   p r e s e n t e i n   F i g u r e   4.   W h e t h e   pr e v i o us   M B D   p o i n t   i s   l o c a t e a t   o n e   o f   t h e   c o rn e r s   o r   e dge   po i nt s   o f   L D S P ,   o n l y   f i v e   o r   t hr e e   n e w   c h e c ki ng  po i nt s   a r e   r e qui r e t o   be   t e s t e a s   s h ow n   i n   F i g u r e   4(a a n (b ),   r e s pe c t i v e l y .   I f   t h e   c e n t r e   po i nt   of  L D S P   pr o duc e s   t h e   M B D ,   t h e   s e a r c h   pa t t e rn   i s   c ha n g e f r o m   L D S P   t S D S P   i n   t h e   f i n a l   s e a r c h .   I n   t h i s   c a s e ,   o n l y   fo ur   n e w   po i n t s   a r e   r e qu i r e t o   b e   t e s t e d,   a s   s h o w n   i n   F i g ur e   4(c ).     2. 4 .   H e x ago n   Bas e d   S e ar c h   ( H S )   B l o c k   M at c h i n g   A l go r i th m   B a s e o n   a n   i n - de pt h   e x a m i n a t i o n   o f   t h e   i n f l ue n c e   of   s e a r c pa t t e rn   o n   s pe e pe r f o r m a n c e   i n   b l o c k   m o t i o n   e s t i m a t i o n ,   Ce   Z hu,   X i a o   L i n,   a nd  L a p - P u i   C ha u   [ 4] .   P r o po s e   a n   a l go r i t h m   us i n g   a   h e xa go n - b a s e d   s e a r c h   pa t t e rn   t o   a c h i e v e   s u b s t a nt i a l   s pe e i m p r o v e m e n t   ov e r   t h e   D S   a l go ri t hm   w i t h   s i m i l a r   d i s t o rt i o pe r f o r m a n c e .   T h e   di a m o n s ha p e pa t t e rn   i s   m o r e   e ff i c i e nt   t ha n   s qua r e   s h a pe s e a r c h   p a t t e rn s ,   b ut   t h e   di a m o n s h a pe   i s   n o t   a p p r o xi m a t e   e n o ugh   t o   a   c i r c l e ,   w h i c h   i s   j us t   90  r o t a t i o n   o f   a   s qua r e .   T h e   c h e c ki ng  po i n t s   ha v e   di f fe r e n t   di s t a n c e s   f r o m   t h e   c e n t r e ,   s o   t h a t   e a c h   s e a r c po i nt   c a nn o t   b e   e qua l l y   ut i l i z e w i t h   m a x i m u m   e ff i c i e n c y   i D S   a l go r i t hm .   A   h e xa go n - b a s e s e a r c h   p a t t e rn  i s   de pi c t e i F i g u r e   5(a ),   w h i c c o n s i s t s   o f   s e v e n   c h e c ki n g   po i n t s   w i t h   t h e   c e n t r e   s u rr o u n de by   s i e n dpo i nt s   o f   t h e   h e xa go w i t h   t h e   t w o   e dge   p o i nt s   (up  a n do w n b e i n g   e xc l ude d.   O f   t h e   s i e n dpo i n t s   i n   t h e   h e xa go n,   t w o   h o r i z o n t a l   po i n t s   a r e   a w a y   f r o m   t h e   c e n t r e   w i t di s t a n c e   a n t h e   r e m a i n i ng  f o ur   po i nt s   ha v e   a   di s t a n c e   o       f r o m   t h e   c e n t r e   po i n t ,   r e s pe c t i v e l y .   F r o m   t h e   F i g u r e   5( a ),   w e   c a n   s e e   t h e   s i e n dpo i n t s   a r e   a pp r o xi m a t e l y   un i f o r m l y   di s t r i b ut e a r o u n t h e   c e n t r e ,   w h i c h   i s   hi g h l y   de s i ra b l e .   T h i s   a l go r i t hm   us e s   t w o   s e a r c h   pa t t e rn s   l a r ge   H S   a n s m a l l   H S   a s   s h ow n   i n   F ig u r e   5(a a n 5(b ).   I t h e   f i r s t   s t e of  s e a r c h ,   t h e   l a r ge   h e xa go n a l   pa t t e rn   w i t h   s e ve n   c h e c ki ng  po i n t s   i s   us e fo r   s e a r c h.   I n   t h e   s e c o n s t e i t h e   M B D   i s   f o un a t   t h e   c e n t r e ,   s w i t c h   t o   us e   t h e   s m a l l   h e xa go n a l   pa t t e rn,   i n c l u di n f o ur   c h e c ki ng  po i n t s   f o r   t h e   f oc us e i nn e r   s e a r c h .   O t h e r w i s e ,   t h e   s e a r c h   c o n t i n ue s   a r o u n t h e   po i n t   w i t m i n i m u m   b l oc di s t o r t i o n   (M B D us i ng  t h e   s a m e   l a r ge   h e xa go n a l   p a t t e rn .   N o t e   t ha t   w h i l e   t h e   l a r ge   h e xa go n a l   pa t t e rn  m o ve s   a l o n t h e   di r e c t i o n   o f   d e c r e a s i ng  di s t o rt i o n ,   o n l y   t hre e   n e w   n o n   ov e r l a ppe c h e c ki n po i nt s   w i l l   be   e v a l ua t e a s   c a n d i da t e s   e a c t i m e .   T h e   t o t a l   num b e o f   s e a r c po i n t s   pe b l o c w i l l   b e     N H S   (m x,   m y =   7   X   (3   X   n +   4.   (1)     W h e r e   ( m x,   m y i s   t h e   f i na l   m o t i o n   v e c t o r   f o un d,   a nd  n   i s   t h e   n u m b e r   o f   e x e c ut i o n s   of   S t e p   2.   In  E qua t i o n   1   t h e   d i gi t   i ndi c a t e s   n u m b e r   o f   c h e c ki n po i n t s   us e i n   s t e 1,   t h e   di g i t   i n d i c a t e s   num b e r   o c h e c ki ng  po i nt s   us e i n   e a c h   e xe c ut i o n   of s t e a n t h e   di gi t   i n d i c a t e s   n u m b e r   of   c h e c ki n po i nt s   us e w i t s m a l l   H S   a s   a   f i na l   s t a ge .             (a                                                                                               (b )     F i g u r e   5 S e a r c h   pa t t e rn s   o fH S   (a L a r ge   H S   (b S m a l l   H S       2. 5 .   En h an c e d   V e r s i o n s   o H e x ago n al   S e a r c h   A l go r i th m   A n   E nha n c e H e xa go n a l   S e a r c h   ( E H S a l go r i t hm   [6]  i s   p r o po s e fo r   f ur t h e r   r e duc t i o n   o f   t h e   s e a r c po i n t s   o v e r   H e xa go n a l   S e a r c h   a l go r i t hm .   T hi s   E H S   us e s   t h e   6 - s i de - b a s e f a s t   i nn e r   s e a r c h   t e c hn i q ue   t i m p r o v e   t h e   i nn e r   s e a r c h   s pe e a ga i n s t   t h e   H e xa go n a l   S e a r c h.   I n   H e xa go n a l   S e a r c h   a l go ri t hm ,   a l l   t h e   s e a r c po i n t s   i n s i de   t h e   l a rge   h e xa go n   n e e t o   b e   e v a l ua t e d ,   t h i s   i s   c o m put a t i o na l l y   i n e f fe c t i ve .     Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2088 - 8708   IJ E CE     V o l .   7 ,   N o .   1 F e b r ua r y   2017   :     2 16     2 24   220   T h e   E H S   a l go r i t hm   o n l y   c h e c ks   t h e   m o s t   p r o m i s i ng  i nn e r   s e a r c h   po i nt s   by   e xpl o i t i n t h e   g r o up - s u m   di s t o rt i o i n f o r m a t i o n   o f   t h e   s i x   c h e c ke e n d po i nt s   o f   t h e   l a r ge   h e xa go n .   A t   f i r s t   E H S   s t a rt s   c o a r s e   s e a r c h   w i t h   t h e   l a rge   h e xa go n a l   pa t t e rn   (F i g u r e   5 (b ))  t o   t r a c e   a   s m a l l   a r e a   o f   o pt i m a l   m o t i o n   v e c t o r .   A f t e r   l o c a t i n a   s m a l l   a r e a   i n   t h e   c o a r s e   s e a r c h,   E H S   gr o ups   t h e   s i c h e c ke e n dpo i nt s   o f   t h e   l a r ge   h e xa go n   a s   s h o w n   i n   F i g u r e   6 (a ).   A t   e a c h   g r o up,   t h e   g r o up - s um   di s t o r t i o n   i s   c a l c ul a t e a n t h e n   f oc us e d   i nn e r   c h e c ki n po i n t s   n e a r e s t   t o   t h e   s m a l l e s t   d i s t o rt i o g r o up  w i l l   b e   e v a l ua t e t o   ob t a i n   t h e   m i ni m u m   di s t o r t i o n   po i nt .   T hr e e   i nn e s e a r c h i n po i nt s   n e a r by   t h e   s m a l l e s t   di s t o rt i o n   g r o up  w i l l   b e   c a l c ul a t e i n   t h e   f oc us e i n n e r   s e a r c h   i f   t h e   s m a l l e s t   di s t o r t i o g r o up  i s   3   o 6.   O t h e r w i s e ,   t w o   i nn e r   s e a r c hi n po i nt s   n e a r e s t   t o   t h e   s m a l l e s t   di s t o r t i o gr o up  w i l l   b e   us e i t h e   f oc us e i nn e s e a r c h.     A n   E nha n c e H e xa go n a l - b a s e S e a r c h   us i ng  P o i n t - O ri e nt e Inn e r   S e a r c h   ( E H S - P O IS i s   p r e s e n t e d   i n   [7]   t o   r e duc e   t h e   s e a r c h   po i n t s   f u r t h e r .   T h e   E H S - P O IS   us e s   a n   e f f i c i e n t   g r o upi n g   m e t h o f o r   t h e   l a r ge   h e xa go n   w hi c h   i s   b a s e o n   m i ni m i z i n M e a I n t e rna l   D i s t a n c e   (M ID f o r   e a c h   i nn e po i nt ,   a s   s h o w n   i F i g u r e   6 (b ).   T h e   e i ght   i nn e r   po i n t s   e n c l o s e by   l a r ge   h e xa g o n   a r e   di v i de i n t o   t w s e t s   by   t h e   M ID   v a l ue .   F i r s t   s e t   c o n t a i n s   a ,   c ,   e ,   f ,   g   a n h   po i nt s   a n d   s e c o n s e t   i n c l ude s   b   a n d′   po i n t s .   T h e s e   po i nt s   a r e   s urr o u n de by   t w o   o r   t hr e e   n e a r e s t   c h e c ke l a r ge   h e x a go p o i n t s .     T h e   N o r m a l i z e G r o up  D i s t o r t i o n s   (N G D s o f   t h e   h e xa go n   a r e   c a l c ul a t e a n t h e   m i ni m u m   N G D s   i n   e a c h   s e t   a r e   f o un d.   T h e   t w o   i nn e po i n t s   r e l a t e t o   m i ni m u m   N G D s   i t w o   s e t s   a r e   f i n a l l y   e v a l ua t e t o   f i nd  t h e   f i na l   m o t i o n   v e c t o r .   T h e   f i n e   s e a r c o f   E H S   r e qui r e s   2   o r   s e a r c h   po i n t s   de pe n di ng  o n   t h e   po r t i o n   o i nn e po i n t s   w i t s m a l l e s t   g r o up  di s t o r t i o n   w h e r e a s   t h e   f i n e   s e a r c h   o f   E H S - P O IS   r e qui r e s   o n l y   s e a r c po i n t s   c o n s t a nt l y .                                (a )     (b                                                       (c )     F i g u r e   6 .   S t ra t e g i e s   us e t o   p r e di c t   po rt i o o f   i nn e s e a r c h e s   i n   E H S ,   E H S - P O IS   a n d   E H S - D O IS ,   ( a )   G r o up  o r i e nt e p r e di c t i o o f   E H S ,   (b P o i n t - o r i e n t e p r e di c t i o o f   E H S - P O IS ,   (c D i r e c t i o n - o r i e n t e d   p r e di c t i o n   o f   E H S - D O IS       A E nha n c e H e xa go n a l - b a s e S e a r c h   us i n g   D i r e c t i o n - O ri e nt e I nn e r   S e a r c (E H S - D O IS [8]  ha s   s h o w n   t h e   c o n s i de r a b l e   i m p r o v e m e n t   o v e r   E H S - P O IS   by   i n c r e a s i ng  t h e   i nn e r   s e a r c h   s pe e do ub l e .   T h e   E H S - D O IS   fo r m s   ps e udo - po i n t s   p r e di c t i o pa t t e rn   { A ,   B ,   C′ ,   D ,   E ,   F ,   G ,   H }   a s   s h o w n   i n   F i g u r e   6 (c ).   T h e   gr o up  di s t o r t i o n s   o t h e s e   e i gh t   ps e udo - po i n t s   a r e   c a l c ul a t e t hr o ug h   s i c h e c ke po i n t s   of   l a r ge   h e xa go n.   S e l e c t   o n e   po i n t   i n   { a ,   b ,   c ,   d′ ,   e ,   f ,   g′ ,   h }   t ha t   w o ul b e   o n   t h e   a rr o w   f r o m   t h e   c e n t e r   o f   l a r ge   h e xa go n   t t h e   ps e udo - p o i n t   w i t h   m i ni m um   di s t o r t i o n   a m o n e i g ht ps e udo - p o i nt s .   T h e   S A D   a t   t h i s   s e l e c t e p o i n t   i s   f i n a l l y   e v a l ua t e t o   f i n t h e   f i n a l   m o t i o v e c t o r .       3.   C O M P A R I S I O N   A   c o m pr e h e n s i v e   s e t   of   e xpe r i m e nt s   h a v e   be e n   c o n duc t e us i n t h e   l u m i na n c e   c o m po n e n t s   o f   t h e   f i r s t   100  f r a m e s   o f   s i v i de o   s e que n c e s   t o   a s s e s s   t h e   pe r f o r m a n c e   a nd  c o m put a t i o n a l   c o m pl e xi t y   o f   s t a t e - of - t h e - a r t   f a s t   s e a r c h   m o t i o n   e s t i m a t i o n   a l go ri t hm s .   T h e s e   v i de o   s e qu e n c e s   c o n s i s t   o f   di ff e r e n t   t y pe s   of   m o t i o n   c h a ra c t e ri s t i c s   a nd  h a v e   v a r i o us   f o r m a t s   i n c l udi ng  Q CIF ,   C IF ,   a n H D .     T h e   s e a r c h   r a nge   i s   s e t   t o   ±63  f o r   H D   v i de s e qu e n c e s   (K i r s t e n - S a ra   a n R oc ke t   l a un c h   s e que n c e s a n ±1 fo r   t h e   r e m a i n i ng  (Q CIF   a n CIF v i de o   s e que n c e s .   T h e   e xpe r i m e nt a l   r e s ul t s   a r e   s h o w n   i n   t e rm s   o f   t w t e s t i ng  c r i t e ri a :   s pe e a n m o t i o n   p r e d i c t i o qua l i t y .   T h e   s pe e pe r f o r m a n c e   i s   s h o w n   i n   t h e   A v e r a ge   N um b e r   o t o t a l   O pe r a t i o n s   pe r   B l o c (A N O B ).   F o r   Evaluation Warning : The document was created with Spire.PDF for Python.
IJ E CE     IS S N :   2088 - 8708       A   Sur v e y   on  B l o c k   M at c hi ng   A l gor i t hm s   f or   V i de o   Cod i ng   ( A dapa  V e n k a t P ar am k us am )   221   t h e   l a t t e r,   t h e   a v e r a ge   P e a S i gn a l   t o   N o i s e   R a t i o   (P S N R )   pe r   f r a m e   i s   c a l c ul a t e d.   T h e   s i z e   of  a   m a c r o b l oc i s   s e t   t o   16  ×   16  pi xe l s   i a l l   t h e   f a s t   b l o c m a t c h i ng  a l go r i t h m s .      O n e   p r o b l e m   t h a t   o c c ur s   w i t h   t h e   T S S   i s   t ha t   i t   us e s   a   u ni f o r m l y   a l l o c a t e c h e c ki n po i nt   p a t t e rn   i t h e   f i r s t   s t e p,   w h i c h   i s   n o t   v e r y   e f f i c i e n t   t o   s e a r c h   s m a l l   m o t i o n s   a ppe a ri n i n   s t a t i o na r y   o r   qua s i - s t a t i o na r y   b l oc ks .   T o   r e m e d y   t h i s   p r o b l e m   t h e   N T S S   e m pl oy s   a   c e n t r e - b i a s e c h e c ki n po i nt   pa t t e rn   i n   t h e   f i r s t   s t e a n ha l f w a y - s t o t e c h n i que .   A s   c o m pa r e t o   T S S ,   N T S S   i s   m uc h   m o r e   r o b us t ,   p r o duc e s   s m a l l e r   m o t i o n   c o m pe n s a t i o n   e rr o r s ,   a n d   h a s   a   v e r y   c o m pa t i b l e   c o m put a t i o na l   c o m pl e xi t y .   A l t h o ug h   N T S S   us e s   m o r e   c h e c ki n po i n t s   i n   i t s   f i r s t   s t e a s   c o m pa r e t o   T S S ,   t h e   f i r s t   s t e p - s t o a n s e c o n s t e p - s t o c a n   r e duc e   c o m put a t i o n   e f fe c t i ve l y .   E i ght   b l o c m a t c h e s   w i l l   b e   s a v e o n c e   a   f i r s t   s t e p - s t o oc c ur s   a nd  f i v e   o r   t hr e e   b l o c m a t c h e s   w i l l   b e   s a ve o n c e   a   s e c o n s t e p - s t o o c c ur s .   F r o m   t h e   e xpe r i m e nt a l   r e s ul t s   c o n duc t e o S a l e s m a a nd  M i s s   A m e ri c a   t e s t   s e que n c e s ,   T S S   a n d   N T S S   a r e   c o m pa r e i n   t e r m s   o f   s pe e d - up  r a t i o s   w i t h   r e s pe c t   t o   F ul l   s e a r c h,   P r o b a b i l i t i e s   o f   c a t c h i ng  t r ue   m o t i o n s ,   a n A v e ra ge   di s t a n c e s ,   a s   s h o w n   i n   T a b l e   I.   F o a   s e a r c h   w i n do w   of   s i z e   15x15,   w = 7.   F ul l   s e a r c h   w i l l   c h e c (2w + 1)2= 225 ,   w h i l e   T S S   c h e c (1+ 8   l o g2(w + 1))  =   25 ,   t hu s   l e a di n g   t o   a   s pe e d - up  ra t i o   of   9.   T h e   s pe e d - up  ra t i o s   o f   N T S S   w i t r e s pe c t   t o   f ul l   s e a r c h   a r e   gi v e i T a b l e   1.   Co m pa ri n g   w i t h   t h e   r e s ul t s   o f   T S S   t h e   N T S S   b a s i c a l l y   p o s s e s s   r a t h e r   c o m pa ra b l e   c o m put a t i o n a l   c o m pl e xi t y .   T h e   p r o b a b i l i t y   t h a t   t h e   t rue   m o t i o n   v e c t o r   i s   fo un by   N T S S   a n T S S   a r e   a l s o   pr e s e nt e i n   T a b l e   1,   f ro m   w h i c h   i t   i s   s e e n   t h a t   N T S S   p r o v i de s   hi g h e r   pr o b a b i l i t i e s   t h a n   t h o s e   of   T S S .   T h e   a v e r a ge   di s t a n c e s   c a l c ul a t e i n   N T S S   a r e   s m a l l   a s   c o m pa r e w i t h   T S S ,   t h i s   i s   b e c a us e   of   c e n t r e - b i a s e pa t t e rn   i s   us e i n   N T S S   w h e re   a s   T S S   e m pl o y s   un i f o r m l y   di s t ri b ut e pa t t e rn .   In   T S S   a nd  N T S S   a l go ri t hm s ,   s qu a r e - s ha pe s e a r c h   pa t t e rn s   a r e   e m pl oy e d,   w h e r e a s   t h e   D S   a l go ri t hm   a do pt s   a   d i a m o n d - s ha pe s e a r c h   p a t t e rn,   w h i c h   ha s   f a s t e r   p r o c e s s i n w i t h   s i m i l a r   d i s t o rt i o n   i n   c o m pa ri s o n   w i t h   T S S   a n N T S S .   Co m pa r e w i t h   T S S ,   t h e   D S   pa t t e rn   c a n   f i n l a r ge   m o t i o n   b l o c ks   w i t f e w e r   s e a r c po i n t s   a n d   a l s o   r e duc e   i t s   s us c e pt i b i l i t y   t o   ge t t i n g   s t uc i n   l o c a l   o pt i m a   due   t o   i t s   r e l a t i v e l y   l a r ge   s t e s i z e   i n   h o r i z o nt a l   a n d   v e r t i c a l   d i r e c t i o n s .       T a b l e   1 .   Co m p a r i s o b e t w e e n   T S S   a n d   N T S S   (I t e r m s   o f   s pe e d - up - r a t i o s   w . r. t . F ul l   s e a r c h,   P r o b a b i l i t i e s   o f   c a t c hi n T r ue   m o t i o n s ,   A v e ra ge   di s t a n c e s )                 T h e   c o m pa c t   s h a pe   of   t h e   D S   pa t t e rn   a r o und  t h e   c e n t r e   a l s o   y i e l ds   f e w e r   s e a r c h   po i n t s   t ha n   N T S S   fo r   f i n di ng  s t a t i o na r y   o r   s m a l l   m o t i o n   v e c t o r s .   T h e   di a m o nd  pa t t e rn   (l a r ge   o n e i s   s o   c o m pa c t   i n   t e rm s   of  di s t a n c e   b e t w e e n   n e i g h b o r i ng  po i nt s   t h a t   t h e r e   m a y   e xi s t   s o m e   r e dun d a n c y   a m o n t h e   s e a r c h   po i nt s ,   e s pe c i a l l y   i n   t h e   b e gi nn i ng  o f   l ow e r   r e s o l ut i o n   s e a r c h.   Co n s e que n t l y ,   s uc h   di s t ri b ut i o n   o f   s e a r c h   po i nt s   i n   D S   pa t t e rn   i s   i n e f f i c i e n t   i n   f i n d i n po s s i b l e   c a n di d a t e s   i n   t h e   n e xt   s t e p.   T h e   r e a s o n   f o r   t hi s   di s a dv a nt a ge   i s   t h a t   t h e   di a m o n d   s h a pe   i s   n o t   a pp r o xi m a t e   e n o ug h   t o   a   c i r c l e ,   w hi c h   i s   j us t   90  r o t a t i o n   o f   a   s qua r e .   T h e   H e xa go n   b a s e s e a r c h   pa t t e rn   i s   m o r e   a pp r o xi m a t e t o   a   c i r c l e   w i t h   a   u ni f o r m   d i s t r i b ut i o n   o f   a   m i n i m u m   num b e r   o s e a r c h   po i n t s   a nd  e a c h   s e a r c h   po i n t   i s   e qua l l y   ut i l i z e w i t h   m a xi m u m   e ff i c i e n c y ,   w h e r e   t h e   r e du nda n c y   a m o ng  s e a r c po i nt s   i s   r e m o v e m a xi m a l l y .   T h i s   H S   a l go ri t hm   c a n   f i n a   s a m e   m o t i o v e c t o r   w i t h   f e w e r   s e a r c h   po i n t s   t ha n   t h e   D S   a l go r i t hm .   G e n e ra l l y   s pe a ki ng,   t h e   l a r ge r   t h e   m o t i o n   v e c t o r ,   t h e   m o r e   s e a r c h   po i n t s   t h e   H S   a l go ri t hm   c a s a v e .   T h e   a v e ra ge   n u m b e r   o f   s e a r c h   po i nt s   pe r   b l o c w i t r e s p e c t   t o   di f f e r e n t   a l go ri t hm s   a n d   di f f e r e n t   v i de o   s e que n c e s   a r e   s h o w n   i n   T a b l e   2 .       T a b l e   2 .   T h e   a v e ra ge   n u m b e r   o f   s e a r c h   po i nt s   pe b l o c w i t r e s pe c t   t o   b l o c m a t c h i n g   d i f fe r e nt   a l go r i t hm s   a n di f f e r e n t   v i de o   s e que n c e                                                                                             S p e e d - u p   ra t i o s   P ro b a b i l i t i e s   A v e ra g e   d i s t a n c e s   S a l e s m a n   M i s s   A m e ri c a   S a l e s m a n   M i s s   A m e ri c a   S a l e s m a n   M i s s   A m e ri c a   T S S   9 . 0   9 . 0   0 . 9 5 1   0 . 5 3 5   0 . 3 6 9   1 . 1 9 3   N T S S   1 0 . 9 4   7 . 9 4   0 . 9 9 0   0 . 7 2 2   0 . 0 4 4   0 . 6 8 7     S a l e s m a n   M i s s   A m e ri c a   T e n n i s   M o b i l e   K i r s t e n - S a ra   Ro c k e t   l a u n c h   N T S S   1 8 . 0   2 1 . 3   2 2 . 7   2 8 . 4   2 3 . 8   2 4 . 9   DS   1 3 . 0   1 6 . 3   1 6 . 9   2 2 . 7   1 9 . 0   1 9 . 8   HS   1 0 . 7   1 2 . 8   1 3 . 0   1 6 . 3   1 3 . 9   1 4 . 8   E H S   1 0 . 3   1 2 . 2   1 2 . 8   1 5 . 8   1 3 . 3   1 4 . 1   E H S - P O IS   1 0 . 1   1 2 . 0   1 2 . 3   1 5 . 3   1 3 . 0   1 2 . 8   E H S - D O I S   0 9 . 5   1 1 . 2   1 1 . 6   1 1 . 6   1 2 . 6   1 2 . 1   Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2088 - 8708   IJ E CE     V o l .   7 ,   N o .   1 F e b r ua r y   2017   :     2 16     2 24   222   T h e   s e a r c h   po i n t   num b e r   pe r   b l o c fo r   t h e   F S   a nd  T S S   a r e   f i xe a s   255  a n 2 r e s pe c t i v e l y   fo r   a l l   v i de o   s e que n c e s .   Co m pa r e w i t h   T S S ,   N T S S   a n D S   s e a rc h   pa t t e rn s   t h e H S   t a ke s   l e s s   n u m b e r   o f   s e a r c po i n t s   i n   a n   a v e r a ge   pe r   b l o c k.   T h e   E H S - D O IS   i s   t h e   f a s t e s t   a m o n t h e   c o m pa r e a l go ri t hm s ,   a n d i t s   pe r f o r m a n c e   i s   i n   t h e   m o s t   c a s e s   c o m pa r a b l e   w i t h   D S a nd  H S . T h e   a v e r a ge   P S N R   v a l ue s   pe r   f r a m e   i n   a l l   t h e   f a s t   b l oc m a t c h i ng  a l go ri t hm s   a r e   f urn i s h e i n   T a b l e   3 .   It   c a b e   ob s e r v e f r o m   T a b l e   3   t ha t   t h e   a v e ra ge   P S N R s   ob t a i n e by   D S   a r e   b e t t e r   t h a n   t h o s e   of   HS a n e nha n c e ve r s i o n s   o f   HS i . e . ,   E H S ,   E H S - P O IS   a n d   E H S - D O IS   a l go r i t hm s   i n   a l l   t h e   c a s e s .   T h e   t o t a l   a v e r a ge   P S N R   of   t h e   D S   i s   be t t e r   by   1. 11dB   w h e n   c o m pa r e d   t o   t h a t   o f   E H S - D O IS   a l go ri t hm .       T a b l e   3 .   T h e   a v e ra ge   P S N R s   i n   dB   f o r   a l l   t h e   f a s t a l go ri t hm s                     T o   c o m pr e h e n t h e   e ff i c i e n c y   of   a l l   t h e   f a s t   b l o c k   m a t c h i n g   a l go ri t hm s   m o r e   v i v i dl y ,   s pe e a n m o t i o n   p r e d i c t i o n   qua l i t y   of   a l l   t h e   f a s t   b l o c m a t c h i ng  a l g o r i t hm s   us i ng  M o b i l e   a n d   R o c k e t   l a u n c h   v i de s e q ue n c e s   h a v e   b e e n   pl o t t e i n   F i g u r e   a nd  F i g u r e   r e s pe c t i v e l y .   F i g ur e   7 (a a n F i g u r e   8 (a pl o t   a   f ra m e - by - f r a m e   c o m pa ri s o n   o f   t h e   a v e r a ge   n u m b e r   o f   s e a r c h   p o i n t s   pe r   b l o c f o r   a l l   t h e   f a s t   b l oc m a t c h i ng  a l go ri t hm s   a p pl i e t o   t h e   M o b i l e   a n R o c ke t   l a un c h   v i de o   s e qu e n c e s   r e s pe c t i ve l y .   F i g ur e   7 (b a n d     F i g u r e   8 (b pl o t   a   f r a m e - by - f r a m e   c o m pa r i s o n   o a ve r a ge   P S N R   fo r   a l l   t h e   f a s t   b l oc m a t c hi n a l go r i t hm s   a ppl i e t o   t h e   M ob i l e   a n R oc ke t   l a un c h   v i de s e qu e n c e s   r e s pe c t i v e l y .   F i g ur e   7 (a a n F i g u r e   8 (a c l e a r l y   m a ni f e s t   t h e   s upe ri o r i t y   of   t h e   E H S - D O IS   a ga i n s t   o t h e r   a l go r i t hm s   i n   t e rm s   o f   a ve r a ge   n um b e r   o f   s e a r c h   po i n t s ,   w h i l e   F i g u r e   7(b a n d   8 (b s h o w   t h a t   t h e   P S N pe r f o r m a n c e   of   t h e   D S   a r e   b e t t e r   t ha n   t ha t   o   E H S - D O IS .           (a )         (b )     F i g u r e   7 .   P e r f o r m a n c e   c o m pa r i s o n   o f   t h e   f a s t   b l o c m a t c hi ng   a l go ri t hm s   f o r   M o b i l e   s e que n c e   i t e r m s   o f :   (a t h e a v e r a ge   n um b e o f   s e a r c po i n t s   pe b l o c a n d   (b a v e ra ge   P S N R   pe f r a m e     S a l e s m an   M i s s   A m e ri c a   T e n n i s   M o b i l e   K i r s t e n - S a ra   Ro c k e t   l a u n c h   N T S S   2 6 . 5 2   3 2 . 3 2   2 4 . 2 2   2 3 . 3 2   4 4 . 1 3   3 7 . 4 3   DS   2 7 . 4 5   3 3 . 8 5   2 4 . 8 2   2 3 . 8 5   4 4 . 2 1   3 7 . 6 9   HS   2 6 . 8 3   3 2 . 6 9   2 4 . 4 5   2 3 . 6 3   4 4 . 0 4   3 7 . 1 2   E H S   2 6 . 6 4   3 2 . 5 5   2 4 . 5 6   2 3 . 5 4   4 3 . 6 8   3 6 . 8 6   E H S - P O IS   2 6 . 3 1   3 2 . 2 3   2 4 . 3 3   2 3 . 2 1   4 3 . 3 4   3 6 . 5 4   E H S - D O I S   2 6 . 9 1   3 2 . 9 1   2 3 . 8 1   2 2 . 7 1   4 2 . 4 5   3 6 . 2 0   Evaluation Warning : The document was created with Spire.PDF for Python.
IJ E CE     IS S N :   2088 - 8708       A   Sur v e y   on  B l o c k   M at c hi ng   A l gor i t hm s   f or   V i de o   Cod i ng   ( A dapa  V e n k a t P ar am k us am )   223       (a )         (b )     F i g u r e   8 .   P e r f o r m a n c e   c o m pa r i s o n   o f   t h e   f a s t   b l o c m a t c hi ng   a l go ri t hm s   f o r   R o c k e t   l a u n c h   s e que n c e   i n   t e rm s   o f :   (a )   t h e a v e ra ge   n u m b e r   o f   s e a r c h   po i nt s   pe r   b l o c a n d   (b a v e ra ge   P S N R   pe f ra m e       4.   C O N C LU S I O N   M o t i o n   e s t i m a t i o n   ge n e ra l l y   c o n s um e s   t h e   m o s t   c o m put a t i o n   i n   a   v i de o   c o di n g.   I t hi s   pa pe r ,   m a n y   f a s t   B M A   a l go r i t hm s b e l o n gi n g   t o   di f fe r e n t   s e a r c h   pa t t e rn s   a n s e a r c h   s t ra t e gi e s   a r e   a na l y z e d.   P e r f o r m a n c e   a n c o m put a t i o na l   c o m pl e xi t y   of   s e l e c t e a l go r i t h m s   i s   c o m pa r e t o   f a c i l i t a t e   t h e   c h o i c e   o f   a n   a pp r o p r i a t e   a l go ri t hm   t o   a   s pe c i f i c   a ppl i c a t i o n .       R EF ER EN C ES   [ 1]   T .   K o g a ,   e t   a l . M o t i o c o m pe ns a t e d   i n t e r f r a m e   c o di ng   f o r   v i de o   c o nf e r e nc i ng ,   i P r oc .   N a t .   T e l e c om m un .   C o nf . pp.   C 9 . 6 . 1 C 9 . 6 . 5 1981 .   [ 2]   R .   L i ,   e t   a l . ,   A   N e w   T hr e e - s t e S e a r c A l g o r i t hm   f o r   B l o c M o t i o E s t i m a t i o n,   I E E E   T r ans .   C i r c ui t s   Sy s t .   V i de T e c hnol . ,   v o l / i s s u e :   4 ( 4 ) ,   pp .   438 442 ,   199 4.   [ 3]   S .   Z hu  a nd  K .   K .   M a ,   A   N e w   D i a m o nd  S e a r c A l go r i t hm   f o r   F a s t   B l o c k - m a t c hi ng   M o t i o E s t i m a t i o n,   I E E E   T r ans .   I m a ge   P r oc e s s i ng ,   v o l / i s s ue :   9 ( 2 ) ,   pp .   287 290 ,   20 00.   [ 4]   C .   Z h u,   e t   a l . ,   H e x a g o n - ba s e S e a r c P a t t e r n   f o r   F a s t   B l o c M o t i o E s t i m a t i o n , ”  I E E E   T r an s .   on   C i r c u i t s   a nd   Sy s t e m s   f or   V i de T e c hn ol o gy v ol / i s s ue :   12 ( 5 ) ,   p p.   34 9 - 355 ,   2002 .     [ 5]   C H .   C he u ng   a nd  L M .   P o ,   N o v e l   C r o s s - D i a m o nd - H e xa g o na l   S e a r c A l go r i t hm s   f o r   F a s t   B l o c M o t i o E s t i m a t i o n,   I E E E   T r a ns . on   M ul t i m e di a ,   v o l / i s s ue :   7 ( 1 ) ,   pp .   16 22 ,   200 5.   [ 6]   C .   Z hu ,   e t   a l . ,   E nha nc e H e xa g o na l   S e a r c f o r   f a s t   b l o c m o t i on  e s t i m a t i o n,   I E E E   T r ans .   C i r c u i t s   S y s t .   V i de o   T e c hnol . ,   v o l / i s s u e :   14 ( 10 ) ,   pp.   1 210 1214 ,   200 4.   [ 7]   L .   M .   P o ,   e t   al . ,   N o v e l   po i n t   o r i e n t e i nne r   s e a r c he s   f o r   f a s t   bl o c m o t i o e s t i m a t i o n ,   I E E E   T r a ns . on  M ul t i m e di a vol / i s s u e :   9 ( 1 ) ,   pp .   9 15 ,   200 7.   [ 8]   B J .   Z o u,   e t   a l . ,   E nha nc e H e x a g o na l - B a s e d   S e a r c U s i ng   D i r e c t i o n - O r i e nt e I nne r   S e a r c f o r   M o t i o n   E s t i m a t i o n,   I E E E   T r a ns .   C i r c ui t s   S y s t .   V i de T e c hn ol . ,   v o l / i s s ue :   20 ( 1 ) ,   pp .   156 160 ,   201 0.     [ 9]   O N di l i   a n T O g unf unm i ,   A l g o r i t hm   a nd  A r c hi t e c t u r e   C o - D e s i g o f   H a r dw a r e - O r i e n t e d ,   M o di f i e D i a m o nd   S e a r c f o r   F a s t   M o t i o E s t i m a t i o i H . 264 / A V C ,   I E E E   T r an s .   C i r c u i t s   Sy s t .   V i de T e c hn ol . ,   v o l / i s s ue :   21 ( 9 ) ,   pp .   1214 1227 ,   201 1.   [ 10]   Z .   S hi ,   e t   al .,  A   m o t i o e s t i m a t i o a l g o r i t hm   ba s e o P r e d i c t i v e   I nt e ns i v e   D i r e c t i o S e a r c f o r   H . 264/ A V C ,   M u l t i m e di a   an E x po   ( I C M E ) ,   2010   I E E E   I n t e r na t i ona l   C o nf e r e nc e   on ,   pp .   667 ,   672 ,   19 - 23   J u l y   2010.   Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2088 - 8708   IJ E CE     V o l .   7 ,   N o .   1 F e b r ua r y   2017   :     2 16     2 24   224   [ 11]   Y .   H .   Ko ,   e t   al . A da p t i v e   s e a r c r a ng e   m o t i o n   e s t i m a t i o u s i ng   n e i g hbo r i ng   m o t i o v e c t o r   d i f f e r e nc e s ,   C ons um e r   E l e c t r on i c s ,   I E E E   T r an s ac t i on s   o n ,   vol / i s s u e :   57 ( 2 ) ,   pp .   726,   7 30,   2 011 .   [ 12]   L .   H s i e h ,   e t   a l . ,   M o t i o e s t i m a t i o us i ng   t w o - s t a g e   pr e di c t i v e   s e a r c a l g o r i t hm s   ba s e o j o i n t   s pa t i o - t e m po r a l   c o r r e l a t i o i nf o r m a t i o n,   E x pe r t   Sy s t e m s   w i t A pp l i c at i o ns v ol / i s s u e :   38 ( 9 ) pp .   1160 8 - 11623 ,   201 1.   [ 13]   H N i s a r ,   e t   a l . ,   C o nt e nt   a d a p t i v e   f a s t   m o t i o e s t i m a t i o ba s e d   o s pa t i o - t e m po r a l   ho m og e ne i t y   a na l y s i s   a n d   m o t i o c l a s s i f i c a t i o n,   P at t e r R e c o gn i t i on   L e t t e r s v ol / i s s u e :   33 ( 1 ) pp.   52 - 61,   20 12.   [ 14]   Y H .   Ko ,   e t   al . F a s t   m o t i o e s t i m a t i o a l g o r i t hm   c o m bi ni ng   s e a r c po i nt   s a m pl i ng   t e c hn i qu e   w i t a d a p t i v e   s e a r c r a ng e   a l g o r i t hm ,   C i r c ui t s   an Sy s t e m s   ( M W SC A S) ,   2012  I E E E   55t I nt e r n at i ona l   M i dw e s t   Sy m po s i um   on pp.   98 8,   99 1,   5 - A ug   2012 .   [ 15]   K H .   Ng ,   e t   al . A   S e a r c P a t t e r ns   S w i t c hi ng   A l go r i t hm   f o r   B l o c M o t i o E s t i m a t i o n,   C i r c u i t s   and  Sy s t e m s   f or   V i de T e c h nol ogy ,   I E E E   T r ans ac t i o ns   on ,   v o l / i s s ue :   19 ( 5 ) ,   pp .   7 53 ,   759 ,   200 9.   [ 16]   J J .   T s a i   a n d   H M .   H a ng ,   O n   t he   D e s i g o f   P a t t e r n - B a s e B l o c M o t i o E s t i m a t i o A l g o r i t hm s ,   C i r c u i t s   a nd   Sy s t e m s   f or   V i de T e c hn ol o gy ,   I E E E   T r ans a c t i on s   on ,   v o l / i s s ue :   2 0( 1 ) ,   pp .   136 ,   143 ,   2010 .   [ 17]   F .   V a r r a y   a nd  H .   L i e bg o t t ,   M ul t i - r e s o l u t i o t r a ns v e r s e   o s c i l l a t i o n   i u l t r a s o und   im a g i ng   f o r   m o t i o e s t i m a t i o n,   U l t r as o ni c s ,   F e r r oe l e c t r i c s ,   a nd  F r e que nc y   C on t r o l ,   I E E E   T r ans a c t i ons   o n ,   v o l / i s s u e :   60 ( 7 ) ,   pp .   133 3,   13 42 ,   2 013 .   [ 18]   J .   S t uc kl e r   a nd  S .   B e h nke ,   M ul t i - r e s o l u t i o s u r f e l   m a p s   f o r   e f f i c i e nt   de n s e   3D   m o de l i ng   a nd  t r a c ki ng ,”   J our na l   of   V i s u al   C om m un i c at i on   an I m age   R e pr e s e nt at i on ,   v o l / i s s ue :   25( 1) ,   pp.   13 7 - 147 ,   2 014 .   [ 19]   M .   N i e uw e nhu i s e a nd  S .   B e hnk e ,   H i e r a r c h i c a l   pl a nn i ng   w i t 3d  l o c a l   m ul t i r e s o l u t i o o bs t a c l e   a v o i d a nc e   f o r   m i c r o   a e r i a l   v e hi c l e s ,”   P r oc e e di ngs   o f   t he   J o i nt   I n t .   S y m pos i um   on   R obot i c s   ( I SR )   and  t he   G e r m an  C onf e r e nc e   on   R obot i c s   ( R O B O T I K ) ,   2014 .   [ 20]   D .   D r o e s c he l ,   e t   al . ,   L o c a l   m ul t i - r e s o l u t i o r e p r e s e n t a t i o f o r   6D   m o t i o e s t i m a t i o a nd  m a ppi ng   w i t a   c o nt i nuo us l y   r o t a t i ng   3D   l a s e r   s c a nne r . I n:   R o b o t i c s   a nd  A ut o m a t i o ( I C R A ) ,   I E E E   I nt e r na t i ona l   C on f e r e nc e   on ,   2014 .   [ 21]   Y .   L i a nd  Y .   C .   W a ng ,   I m pr ov e pa r a bo l i c   pr e d i c t i o n - ba s e f r a c t i o na l   s e a r c f o r   H . 264/ A V C   v i de o   c o di ng ,   I m age   P r oc e s s .   I E T ,   v o l / i s s ue :   3 ( 5 ) ,   p p.   26 1 27 1,   20 09 .   [ 22]   S .   D i kba s ,   e t   al . ,   F a s t   m o t i o e s t i m a t i o w i t i n t e r po l a t i o n - f r e e   s u b - s a m pl e   a c c ur a c y ,   I E E E   T r a ns .   C i r c u i t s   S y s t .   V i de T e c h nol . ,   v o l / i s s ue :   20 ( 7 ) ,   p p.   10 47 1 051 ,   2010 .   Evaluation Warning : The document was created with Spire.PDF for Python.