I n te r n ati o n al   Jo u r n al   o f  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 a  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 d  O c t   7 ,   201 6   R e v i s e d  D e c   3 0 ,   201 6   A c c e pt e d  J a n   1 5 ,   201 7       B l o c k  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 n  e s t i m a t i o n  ( M E )   i s   t h e   he a r t   t o  m a ny   m o t i o n - c o m pe ns a t e d  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 h  a s   I S O   M P E G - 1/ 2 / 4  a n d  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 n  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 k  m a t c hi ng   a l g o r i t hm s   ha v e   b e e n  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 h  pa t t e r ns   i n  m o t i o n  e s t i m a t i o n  w i l l   i nf l ue nc e   m o r e   o n  t he   s e a r c hi ng   s p e e d  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 k  m a t c hi ng   a l g o r i t hm s   a n d  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 n  p r e d i c t i o n   qua l i t y .   Ke y w or d:   B l oc k  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 d  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 d  Co m m u ni c a t i o n  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 f  b l o c k  m a t c hi n g  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 d  m a g ni t ude   of  m o t i o n   ( m o t i o n  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 d  c a n di da t e   b l o c k  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 k  m a y   b e   c a rri e d  o ut   by   c o m pa ri n g  t h e   m a c r o b l oc k  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 d  t o   f i n d  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 h  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 d  c a n d i da t e   b l o c k  t hr o ug h   c a l c ul a t i n g  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 n  a l go r i t hm s   h a v e   b e e n   pr o po s e d  a t   t h e   p r i c e   of   s l i gh t l y   i m pa i r e d  P e a k  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 g  c a t e go r i e s :   r e d uc t i o n   i n  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 h  [10 - 14 ],   s e a r c h  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 n    s e a r c h   [17 - 20]  a n d  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 p  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 d  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 d  t o   m o s t   r e a l - w o r l d  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 d  t ow a r d  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 d  t h e   n e w   t hr e e - s t e p  s e a r c h   (N T S S )  w hi c h  h a s   a   c e n t r e - b i a s e d  s e a r c h  p a t t e rn  a nd  s uppo r t s   a   ha l f w a y - s t o p  t e c h n i q ue   [2].   T h e   c e n t r e - b i a s e d  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 f  T S S ,   t e n ds   t o   a c h i e v e   m uc h   s upe r i o r  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 h  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 n  s pe e d  a n d   di s t o r t i o n  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.   In   T S S   a n d  N T S S   a l go r i t hm s   s qua r e - s ha pe d  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 d  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 d  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 a  P ar am k us am )   217   s qua r e - s ha pe d  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 h  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 d  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   2  pe l s .   T h e   h e xa g o n   b a s e d  s e a r c h   a l go r i t hm   [4]  w a s   de v e l o p e d  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 d  s pe e d  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 d  s e a r c h   p a t t e rn s   a n d  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 d  s e a r c h   (H S )  a l go ri t hm   c a n  a c hi e v e   s u b s t a nt i a l   s pe e d  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 d  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 d  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 n  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 r  s e a r c h  s pe e d.   T h e   m a i n  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 k  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 f  t h i s   pa pe r   i s   o r g a n i z e d  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 k  m a t c hi n g  a l go ri t hm s   s uc h   a s   t hr e e   s t e p  s e a r c h ,   N e w   t hr e e   s t e p  s e a r c h ,   D i a m o n d  s e a r c h ,   H e xa go n   b a s e d  s e a r c h   a n d  e nh a n c e d  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 d  t o   t h e   d i s c us s i o n s   o f  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 p  S e a r c h   (T S S )  i s   o n e   o f  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 d  w a s   i nt r o duc e d  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 p  8  b l oc ks ,   a t   a   d i s t a n c e   o f  s t e p  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 g  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 d  fo r   c o m pa ri s o n .   I n   t h e   s e c o n d  s t e p  t h e   s t e p  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 d  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 - 1  a n d  s t e p - 2  a r e   r e pe a t e d  t i l l   t h e   s t e p  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 d  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 h  l o w   b i t   ra t e   v i de o   a ppl i c a t i o n  s uc h  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 d  by   R M 8  of   H . 261  a n d   S M 3  o f  M P E G   o w i n g  t o   i t s   s i m p l i c i t y   a n d  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   7  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 d  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 h  P a t h   t o   Lo c a t e   a   M o t i o n  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 d  by   R e n xi a n g   L i ,   B i n g   Z e n g  a n d  M i ng  L . L i o u  [2] .   I t   i s   a   m o di f i e d  v e r s i o n   o f   t h e   t hr e e   s t e p  s e a r c h   a l go r i t h m   f o r   s e a r c hi n g  s m a l l   m o t i o n  v i de o   s e que n c e s .   F o r   t h e s e   v i de o  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 n  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 d  i n   T S S ,   8  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 d  i n   t h e   f i r s t   s t e p  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 k  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 k  (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 d  s t e p  w i l l   b e   pe r f o r m e d  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 p  t h e   s e a r c h   ( T hi s   i s   c a l l e d  s e c o n d  s t e p  s t o p).   D e pe n di n g  o n   po s i t i o n   o f  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 g  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 g  po i nt s   r e qu i r e d  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 p  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 k  m a t c h e s   a s   c o m pa r e d  t o   25  m a t c h e s   i n   T S S .   E i g h t   b l oc k  m a t c h e s   w i l l   b e   s a ve d  o n c e   a   f i r s t   s t e p - s t o p  o c c ur s .   D e pe n d i n g  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   8  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 k  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 d  s t e p - s t o p  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 g  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 g  t h e   t w o  di a go n a l   d i r e c t i o n s ,   t hr e e   b l o c k  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 k  m a t c h e s   n e e de d  i n   N T S S   fo r   e s t i m a t i n g   a   b l o c k  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 d  by   17P 1  +   20P 2   +   22P 2'   +   33  (   1 - P1 - P2 -   P 2' ) ,   w he r e   P 1  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 p  w h i l e   P 2  a n d  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 g  a   s e c o n d  s t e p - s t o p  i n   t h e   t w o   c a s e s   m e nt i o n e d  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 n  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 d  i n  t h e   f i r s t   s t e p  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   ( 3  o r  5)   i n  t h e   s e c o n d  s t e p  de pe n d i n g   o n  m i ni m u m   B D M   po i nt ,   i n  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 d  s e a r c h   a l go r i t hm   (D S )  i s   p r o po s e d  by   S .   Z h u  a n d  K .   K .   M a   [3] . It   i s   b a s e d  o n   M V   di s t r i b ut i o n   o f   r e a l   w o r l d  v i de o   s e que n c e s .   It   i s   a n   o ut s t a n di n g  a l go r i t hm   a do pt e d  by   M P E G - 4  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 d  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 o  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 d  f r o m   t h e   c h e c ki n g  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 d  l a r ge   d i a m o n d  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 d  s ha pe .   T h e   s e c o n d  pa t t e rn   c o n s i s t i n g  o f   f i ve   c h e c ki n g  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 d  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 d  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 d  t h e   9  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 k  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 d  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 d  w hi c h  i s   c e nt e r e d  a t   t h e   M B D   po i n t   fo un d  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 d  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 f  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 d  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 g  t h e   f i v e   c h e c ki n g  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 g  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 a  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 h  9  S e a r c h  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 d  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 g  a r e   p r e s e n t e d  i n   F i g u r e   4.   W h e n  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 d  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 d  t o   be   t e s t e d  a s   s h ow n   i n   F i g u r e   4(a )  a n d  (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 d  f r o m   L D S P   t o  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 d  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 d  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 h  pa t t e rn   o n   s pe e d  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 d  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 n  pe r f o r m a n c e .   T h e   di a m o n d  s ha p e d  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 d  s e a r c h   p a t t e rn s ,   b ut   t h e   di a m o n d  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   8  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 h  po i nt   c a nn o t   b e   e qua l l y   ut i l i z e d  w i t h   m a x i m u m   e ff i c i e n c y   i n  D S   a l go r i t hm .   A   h e xa go n - b a s e d  s e a r c h   p a t t e rn  i s   de pi c t e d  i n  F i g u r e   5(a ),   w h i c h  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 d  by   s i x  e n dpo i nt s   o f   t h e   h e xa go n  w i t h   t h e   t w o   e dge   p o i nt s   (up  a n d  do w n )  b e i n g   e xc l ude d.   O f   t h e   s i x  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 h  di s t a n c e   2  a n d  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        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 x  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 d  a r o u n d  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 d  s m a l l   H S   a s   s h ow n   i n   F ig u r e   5(a )  a n d  5(b ).   I n  t h e   f i r s t   s t e p  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 d  fo r   s e a r c h.   I n   t h e   s e c o n d  s t e p  i f  t h e   M B D   i s   f o un d  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 g  f o ur   c h e c ki ng  po i n t s   f o r   t h e   f oc us e d  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 d  t h e   po i n t   w i t h  m i n i m u m   b l oc k  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 g  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 d  c h e c ki n g  po i nt s   w i l l   be   e v a l ua t e d  a s   c a n d i da t e s   e a c h  t i m e .   T h e   t o t a l   num b e r  o f   s e a r c h  po i n t s   pe r  b l o c k  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   7  i ndi c a t e s   n u m b e r   o f   c h e c ki n g  po i n t s   us e d  i n   s t e p  1,   t h e   di g i t   3  i n d i c a t e s   num b e r   o f  c h e c ki ng  po i nt s   us e d  i n   e a c h   e xe c ut i o n   of s t e p  2  a n d  t h e   di gi t   4  i n d i c a t e s   n u m b e r   of   c h e c ki n g  po i nt s   us e d  w i t h  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 f  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 d  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 d  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  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 d  f a s t   i nn e r   s e a r c h   t e c hn i q ue   t o  i m p r o v e   t h e   i nn e r   s e a r c h   s pe e d  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 h  po i n t s   i n s i de   t h e   l a rge   h e xa go n   n e e d  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 g  t h e   g r o up - s u m   di s t o rt i o n  i n f o r m a t i o n   o f   t h e   s i x   c h e c ke d  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 g  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 x  c h e c ke d  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 d  a n d  t h e n   f oc us e d   i nn e r   c h e c ki n g  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 n  g r o up  w i l l   b e   e v a l ua t e d  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 r  s e a r c h i n g  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 d  i n   t h e   f oc us e d  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 n  g r o up  i s   3   o r  6.   O t h e r w i s e ,   t w o   i nn e r   s e a r c hi n g  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 n  gr o up  w i l l   b e   us e d  i n  t h e   f oc us e d  i nn e r  s e a r c h.     A n   E nha n c e d  H e xa go n a l - b a s e d  S e a r c h   us i ng  P o i n t - O ri e nt e d  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 d  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 d  o n   m i ni m i z i n g  M e a n  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 r  po i nt ,   a s   s h o w n   i n  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 d  by   l a r ge   h e xa g o n   a r e   di v i de d  i n t o   t w o  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 d  h ′   po i nt s   a n d   s e c o n d  s e t   i n c l ude s   b ′   a n d  d′   po i n t s .   T h e s e   po i nt s   a r e   s urr o u n de d  by   t w o   o r   t hr e e   n e a r e s t   c h e c ke d  l a r ge   h e x a go n  p o i n t s .     T h e   N o r m a l i z e d  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 d  a n d  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 r  po i n t s   r e l a t e d  t o   m i ni m u m   N G D s   i n  t w o   s e t s   a r e   f i n a l l y   e v a l ua t e d  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 h  o f   E H S   r e qui r e s   2   o r   3  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 f  i nn e r  po i n t s   w i t h  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   2  s e a r c h  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 d  t o   p r e di c t   po rt i o n  o f   i nn e r  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 d  p r e di c t i o n  o f   E H S ,   (b )  P o i n t - o r i e n t e d  p r e di c t i o n  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 n  E nha n c e d  H e xa go n a l - b a s e d  S e a r c h   us i n g   D i r e c t i o n - O ri e nt e d  I nn e r   S e a r c h  (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 d  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 n  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 f  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 d  t hr o ug h   s i x  c h e c ke d  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 d  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 o  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 g  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 d  p o i n t   i s   f i n a l l y   e v a l ua t e d  t o   f i n d  t h e   f i n a l   m o t i o n  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 d  us i n g  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 x  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 d  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 o  s e qu e n c e s   (K i r s t e n - S a ra   a n d  R oc ke t   l a un c h   s e que n c e s )  a n d  ±1 5  fo r   t h e   r e m a i n i ng  (Q CIF   a n d  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 o  t e s t i ng  c r i t e ri a :   s pe e d  a n d  m o t i o n   p r e d i c t i o n  qua l i t y .   T h e   s pe e d  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 f  t o t a l   O pe r a t i o n s   pe r   B l o c k  (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 a  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 k  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 k  i s   s e t   t o   16  ×   16  pi xe l s   i n  a l l   t h e   f a s t   b l o c k  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 d  c h e c ki n g  po i nt   p a t t e rn   i n  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 g  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 d  c h e c ki n g  po i nt   pa t t e rn   i n   t h e   f i r s t   s t e p  a n d  ha l f w a y - s t o p  t e c h n i que .   A s   c o m pa r e d  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 g  po i n t s   i n   i t s   f i r s t   s t e p  a s   c o m pa r e d  t o   T S S ,   t h e   f i r s t   s t e p - s t o p  a n d  s e c o n d  s t e p - s t o p  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 k  m a t c h e s   w i l l   b e   s a v e d  o n c e   a   f i r s t   s t e p - s t o p  oc c ur s   a nd  f i v e   o r   t hr e e   b l o c k  m a t c h e s   w i l l   b e   s a ve d  o n c e   a   s e c o n d  s t e p - s t o p  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 d  o n  S a l e s m a n  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 d  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 d  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 r  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 k  (2w + 1)2= 225 ,   w h i l e   T S S   c h e c k  (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 h  r e s pe c t   t o   f ul l   s e a r c h   a r e   gi v e n  i n  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 d  by   N T S S   a n d  T S S   a r e   a l s o   pr e s e nt e d  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 d  i n   N T S S   a r e   s m a l l   a s   c o m pa r e d  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 d  pa t t e rn   i s   us e d  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 d  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 d  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 d  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 g  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 d  N T S S .   Co m pa r e d  w i t h   T S S ,   t h e   D S   pa t t e rn   c a n   f i n d  l a r ge   m o t i o n   b l o c ks   w i t h  f e w e r   s e a r c h  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 k  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 p  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 n  b e t w e e n   T S S   a n d   N T S S   (I n  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 g  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 g  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 g  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 d  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 d  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 f  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 d  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 h  po i nt s   i s   r e m o v e d  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 d  a   s a m e   m o t i o n  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 n  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 k  w i t h  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 r  b l o c k  w i t h  r e s pe c t   t o   b l o c k  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 d  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 k  fo r   t h e   F S   a nd  T S S   a r e   f i xe d  a s   255  a n d  2 5  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 d  w i t h   T S S ,   N T S S   a n d  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 h  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 g  t h e   c o m pa r e d  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 k  m a t c h i ng  a l go ri t hm s   a r e   f urn i s h e d  i n   T a b l e   3 .   It   c a n  b e   ob s e r v e d  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 d  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 d  e nha n c e d  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 d  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 d  a n d  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 k  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 o  s e q ue n c e s   h a v e   b e e n   pl o t t e d  i n   F i g u r e   7  a nd  F i g u r e   8  r e s pe c t i v e l y .   F i g ur e   7 (a )  a n d  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 k  f o r   a l l   t h e   f a s t   b l oc k  m a t c h i ng  a l go ri t hm s   a p pl i e d  t o   t h e   M o b i l e   a n d  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 f  a ve r a ge   P S N R   fo r   a l l   t h e   f a s t   b l oc k  m a t c hi n g  a l go r i t hm s   a ppl i e d  t o   t h e   M ob i l e   a n d  R oc 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 v e l y .   F i g ur e   7 (a )  a n d  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 R  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 f    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 k  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 n  t e r m s   o f :   (a )  t h e a v e r a ge   n um b e r  o f   s e a r c h  po i n t s   pe r  b l o c k  a n d   (b )  a v e ra ge   P S N R   pe r  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 a  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 k  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 k  a n d   (b )  a v e ra ge   P S N R   pe r  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 n  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 d  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 d  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 d  a l go r i t h m s   i s   c o m pa r e d  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 n  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 n  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 p  S e a r c h  A l g o r i t hm   f o r   B l o c k  M o t i o n  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 o  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 h  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 n  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 d  S e a r c h  P a t t e r n   f o r   F a s t   B l o c k  M o t i o n  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 o  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 h  A l go r i t hm s   f o r   F a s t   B l o c k  M o t i o n  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 d  H e xa g o na l   S e a r c h  f o r   f a s t   b l o c k  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 d  i nne r   s e a r c he s   f o r   f a s t   bl o c k  m o t i o n  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 d  H e x a g o na l - B a s e d   S e a r c h  U s i ng   D i r e c t i o n - O r i e nt e d  I nne r   S e a r c h  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 o  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 d  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 n  o f   H a r dw a r e - O r i e n t e d ,   M o di f i e d  D i a m o nd   S e a r c h  f o r   F a s t   M o t i o n  E s t i m a t i o n  i n  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 o  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 n  e s t i m a t i o n  a l g o r i t hm   ba s e d  o n  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 n  S e a r c h  f o r   H . 264/ A V C , ”   M u l t i m e di a   an d  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 h  r a ng e   m o t i o n   e s t i m a t i o n  u s i ng   n e i g hbo r i ng   m o t i o n  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 n  e s t i m a t i o n  us i ng   t w o - s t a g e   pr e di c t i v e   s e a r c h  a l g o r i t hm s   ba s e d  o n  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 n  i nf o r m a t i o n, ”   E x pe r t   Sy s t e m s   w i t h  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 n  e s t i m a t i o n  ba s e d   o n  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 n  c l a s s i f i c a t i o n, ”   P at t e r n  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 n  e s t i m a t i o n  a l g o r i t hm   c o m bi ni ng   s e a r c h  po i nt   s a m pl i ng   t e c hn i qu e   w i t h  a d a p t i v e   s e a r c h  r a ng e   a l g o r i t hm , ”   C i r c ui t s   an d  Sy s t e m s   ( M W SC A S) ,   2012  I E E E   55t h  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 - 8  A ug   2012 .   [ 15]   K .  H .   Ng ,   e t   al . ,  “ A   S e a r c h  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 k  M o t i o n  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 o  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 n  o f   P a t t e r n - B a s e d  B l o c k  M o t i o n  E s t i m a t i o n  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 o  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 n  t r a ns v e r s e   o s c i l l a t i o n   i n  u l t r a s o und   im a g i ng   f o r   m o t i o n  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 n  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 d  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 n  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 h  3d  l o c a l   m ul t i r e s o l u t i o n  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 n  r e p r e s e n t a t i o n  f o r   6D   m o t i o n  e s t i m a t i o n  a nd  m a ppi ng   w i t h  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 n  ( 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 n  a nd  Y .   C .   W a ng ,   “ I m pr ov e d  pa r a bo l i c   pr e d i c t i o n - ba s e d  f r a c t i o na l   s e a r c h  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 n  e s t i m a t i o n  w i t h  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 o  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.