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 30 ~ 2 37   IS S N :   2088 - 8708 D O I :   10. 1 1591 / i j e c e . v7 i 1 . pp230 - 23 7             230       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   T h r e e - P o i n t   D i r e c t i o n a l   S e a r c h   B l o c k   M a t c h i n g   A l g o r i t h m       A.   V .   P ar am k u s am D .   Lax m R e d d y   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 ,   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   14 ,   201 7       T hi s   p a pe r   p r o po s e s   c o m pa c t   di r e c t i o na l   a s y m m e t r i c   s e a r c pa t t e r ns ,   w h i c w e   ha v e   n a m e a s   t h r e e - po i n t   d i r e c t i o na l   s e a r c ( T D S ) .   I m o s t   f a s t   s e a r c h   m o t i o e s t i m a t i o a l g o r i t hm s ,   a   s y m m e t r i c   s e a r c pa t t e r i s   us u a l l y   s e t   a t   t he   m i ni m um   b l o c di s t o r t i o po i n t   a t   e a c s t e o f   t he   s e a r c h.   T h e   de s i g o f   t he   s y m m e t r i c a l   pa t t e r i t h e s e   a l g o r i t hm s   r e l i e s   p r i m a r i l y   o t he   a s s um p t i o t ha t   t he   d i r e c t i o n   o f   c o nv e r g e nc e   i s   e qua l l y   a l i ke   i n   e a c d i r e c t i o w i t h   r e s pe c t   t o   t h e   s e a r c c e n t e r .   T h e r e f o r e ,   t he   m o no t o ni c   pr o pe r t y   o f   r e a l - w o r l d   v i de o   s e que nc e s   i s   no t   pr o pe r l y   us e b y   t he s e   a l g o r i t hm s .   T he   s t r a t e g y   of   T D S   i s   t o   k e e s e a r c hi ng   f o r   t he   m i n i m um   b l o c d i s t o r t i o po i nt   i t h e   m o s t   pr o ba bl e   di r e c t i o ns ,   un l i k e   t he   p r e v i o us   f a s t   s e a r c m o t i o e s t i m a t i o a l g o r i t hm s   w he r e   a l l   t he   d i r e c t i o ns   a r e   c he c ke d.   T he r e f o r e ,   t he   pr o po s e m e t ho s i g n i f i c a nt l y   r e duc e s   t he   num be r   o f   s e a r c po i nt s   f o r   l o c a t i ng   a   m o t i o v e c t o r .   C o m pa r e t o   c o n v e nt i o na l   f a s t   a l g o r i t hm s ,   t he   pr o po s e m e t ho ha s   t he   f a s t e s t   s e a r c s pe e a nd  m o s t   s a t i s f a c t o r y   P S N R   v a l ue s   f o r   a l l   t e s t   s e que nc e s .   Ke y w or d:   B l oc m a t c hi n g   a l go r i t hm   F a s t   s e a r c h   a l go r i t h m   M o t i o n   e s t i m a t i o n   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.   V .   P a r a m kus 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 ,   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   M o t i o n   e s t i m a t i o n   (M E i n   v i de o   s e que n c e s ,   ha s   b e e n   de e pl y   a na l y z e by   t h e   r e s e a r c h   c o m m u ni t y ,   due   i t s   i m po r t a n c e   i n   t h e   v i s ua l   e xpe r i e n c e   fo r   a   h uge   v a r i e t y   of   v i s ua l   t a s ks .   M o t i o n   e s t i m a t i o n   i s   a n   e s s e n t i a l   pa rt   i v i de o   c o di n p r o c e s s   a n g r e a t l y   a c h i e v e s   s i gni f i c a n t   c o m p r e s s i o n   by   r e m ov i n t h e   t e m po ra l   r e du n d a n c y   e xi s t i ng  i n   a   v i de o   s e qu e n c e .   H ow e ve r ,   t h e   i nt e n s i v e   c o m put a t i o n   o M E   i s   t h e   m a j o r   p r o b l e m   fo r   r e a l - t i m e   e n c o de r s .   I b l o c b a s e m o t i o n   e s t i m a t i o n ,   t he   c urr e n t   f r a m e   i s   d i v i de i nt o   n o n - o v e r l a pp i n g   m a c r o   b l oc ks   of   16  16  p i xe l s .   T h e   M E   p a r t   o f   v i de c o de c   c a l c ul a t e s   t h e   m o t i o n   v e c t o r   f o r   e a c h       m a c r o b l oc by   s e a r c hi n g   b e s t   m a t c h i n g   c a n d i da t e   b l o c f r om   t h e   p r e v i o us l y   e n c o de r e f e r e n c e   f r a m e .     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 ri t hm   a n 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 h   m a c r o b l o c k.   In   i t ,   t h e   S um   o f   a b s o l ut e   di f fe r e n c e   ( SA D i s   c a l c ul a t e a t   e a c h   s e a r c h   po i n t   i t h e   s e a r c h   a r e a .   T h e   S A D   b e t w e e n   a   m a c r o b l oc of   s i z e   × N   a t   po s i t i o n   ( p ,   q )   i t h e   c u rr e n t   f r a m e   f t   a n c a ndi d a t e   b l o c a t   po s i t i o n   ( +   x ,   q   +   y )   i t h e   r e f e r e n c e   f r a m e   f t - 1   i s   de f i n e i t h e   e q   (1) .     1 0 1 0 1 ) 1 ( ) , ( ) , ( ) , ( N i N j t t j y q i x p f j q i p f y x S A D   (1)        W i t h   s e a r c h   ra n ge   o f   t h e r e   w i l l   b e   (2 W + 1) 2   c a n d i da t e   b l o c ks   o r   s e a r c h   po i n t s .   S o ,   f o r   e a c m o t i o n   v e c t o r   t h e   S A D   f un c t i o n   ha s   t o   b e   e v a l ua t e (2 W + 1) 2   t i m e s .   A t   e a c s e a r c po i n t   N 2   c o m put a t i o n s   a r e   r e qui r e d   t o   c a l c ul a t e   t h e   S A D   a n d   o n e   c o m put a t i o c o n s i s t s   of   o n e   s ub t r a c t i o n ,   o n e   a ddi t i o a nd  o n e   a b s o l ut e   v a l ue   o pe r a t i o n s .   T h us   t h e   t o t a l   c o m put a t i o n   pe r   o n e   m o t i o n   v e c t o r   i s   (2 W + 1) 2   ×  N 2   ×   o pe r a t i o n s .   L e t   a   Evaluation Warning : The document was created with Spire.PDF for Python.
IJ E CE     IS S N :   2088 - 8708       A   T hr e e   P oi nt   D i r e c t i ona l   Se ar c B l o c k   Ma t c hi ng   A l gor i t hm   ( A .   V .   P ar am k us am )   231   f a m e   s i z e   i s   K   L   a n f r a m e   ra t e   i s   T   f ps ,   t h e   a m o unt   o f   c o m put a t i o n   i s   3 T KL   (2 W + 1) 2   pe r   s e c o n d.   T hi s   m a ke s   f ul l   s e a r c h   b l o c m a t c hi n a l go r i t h m   a s   a   v e r y   c om put a t i o na l l y   i n t e n s i v e   m e t h o d.   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 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   ha v e   b e e n   pr o po s e a t   t h e   pri c e   o s l i g h t l y   i m pa i r e P e a S i g n a l - to - N o i s e   R a t i o   (P S N R pe r f o 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   fo l l ow i n 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 ],   pr e di c t i v e   s e a r c h   [10 - 14] ,   s e a r c h   p a t t e rn   s w i t c hi n [15] ,   [ 16] ,   m ul t i - r e s o l ut i o n   s e a r c h   [17 - 20]  a n F ra c t i o na l - P i xe l   Int e r po l a t i o n   [21] ,   [ 22] .   E x i s t i n 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   us e   o n e   o r   a   c o m b i n a t i o n   of  t h e s e   c a t e go r i e s .       T h e   m a i n   a s s u m pt i o n   o f   m o s 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   i s   t ha t   t h e   b l o c di s t o r t i o m e a s u r e   fo r   e xa m p l e   S A D   i s   m o n o t o n i c   o v e r   t h e   s e a r c h   r a nge ,   i m pl y i n t h a t   t h e   S A D   i n c r e a s e s   m o n o t o n i c a l l y   a s   t h e   s e a r c h   po s i t i o n   m o ve s   a w a y   f r o m   t he   m i ni m um   d i s t o rt i o n   po i nt .   S o ,   t h e   b e s t   m a t c po i n t   m a y   be   fo un by   fo l l ow i n t h e   di s t o r t i o n   t r e n w i t h o ut   c h e c ki n a l l   s e a r c h   po i n t s   i n   t h e   s e a r c h   w i n do w .   A c c o r di ngl y ,   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 a l go ri t hm s   e m p l oy   v a r i o us   s e a r c h   p a t t e rn s   t o   r e duc e   t h e   n um b e r   o f   s e a r c h   po i n t s ,   t h e r e by   s pe e di n up  t h e   s e a r c h.   T h e   m a i n   d ra w b a c of   t h e s e   a l go r i t hm s   i s   t h a t   t h e   s e a r c h   p a t t e rn  o f   t h e s e   a l go r i t hm s   i s   us u a l l y   s y m m e t r i c ,   a nd  t h e   m a g ni t u de   o f   b l oc m a t c h i n e rr o r   i s   n o t   e f fe c t i ve l y   us e d.   F o r   m o s t   f a s t   s e a r c h   m o t i o e s t i m a t i o a l go ri t hm s ,   t h e   i n i t i a l   po i nt   o f   s e a r c h   i s   us ua l l y   s e t   a t   t h e   c e n t e r   o t h e   s e a r c h   w i n do w   a n t h e   s e a r c h   o c c ur s   a c c o r di n t o   a   s y m m e t ri c   pa t t e rn .   A f t e r   c o m pa ri s o n ,   t h e   n e w   c e n t e r   po i n t   i s   s e t   a t   t h e   po i n t   w i t h   t h e   l e a s t   a m o u n t   o f   S A D ,   a n t h e n   ge n e r a t e s   a   n e w   s y m m e t ri c   s e a r c h   pa t t e rn   f o r   t h e   n e xt   s e a r c h .   T hi s   p r o c e dure   c o n t i n ue s   u n t i l   t h e   c o n di t i o n s   of   c o n v e r ge n c e   a r e   s a t i s f i e d.   In   b l o c m a t c h i ng  a l go r i t h m ,   t h e   m o s t   i m p o r t a nt   a s s um p t i o n   i s   t ha t   t h e   e rr o r   s ur f a c e   i s   m o n o t o n i c .   B ut ,   t h e   s t r uc t u r e   o t h e   s y m m e t ri c a l   pa t t e rn   a s s um e s   t ha t   t h e   di r e c t i o n   o f   c o n v e r ge n c e   i s   e qua l l y   a l i ke   i n   e a c h   di r e c t i o n   w i t h   r e s pe c t   t o   t h e   s e a r c h   c e nt e r.   A s   a   r e s ul t ,   t h e   m o n o t o n i c   pr o pe rt y   i s   n o t   pr o pe r l y   us e d.   If   t h e   s e a r c di r e c t i o c a b e   c o r r e c t l y   de t e r m i n e d ,   t h e   s e a r c h   s pe e w i l l   b e   f ur t h e r   e nha n c e d.   In  t hi s   pa pe r,   a   n o v e l   t hr e e - po i n t   di r e c t i o na l   s e a r c (T D S )   a l go ri t hm   i s   de v e l o pe d.   T hi s   a l go ri t hm   c o n s i s t s   o f   po s s i b l e   s e a r c h   p a t t e rn s   o f   w h i c h   e i g h t   a r e   di r e c t i o n a l   p a t t e rn s   a n d   t h e   r e m a i ni n o n e   i s   a   c o m pa c t   s y m m e t ri c   s e a r c h   p a t t e rn   w hi c c o n s i s t s   o f   n i n e   s e a r c h   po i n t s .   T h e   r e m a i n de r   o f   t h i s   pa pe r   i s   o r ga ni z e a s   f o l l ow s .   In   S e c t i o n   2 ,   w e   b r i e f l y   de s c r i b e   t h e   s o m e   c o n v e n t i o na l   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 a l go ri t hm s .   T h e   de t a i l s   o f   t h e   p r o po s e T D S   a r e   g i v e n   i S e c t i o n   3 .   S e c t i o c o m p r i s e s   a   di s c us s i o n   o f   t h e   e xpe r i m e nt a l   r e s ul t s .   F i n a l l y ,   c o n c l us i o n s   a r e   p r o v i de i S e c t i o n   5 .       2.   F A S S EA R C H   M O TI O N   ES TI M A TI O N   A L G O R I T H M S   T h e   di a m o n s e a r c h   a l go r i t h m   (D S i s   p r o po s e by   S .   Z h u   a n d   K .   K .   M a   [3] .   I t   e m p l oy s   t w o   s e a r c pa t t e rn s   a s   s h o w n   i F i g u r e   1( a a n d   (b ).   T h e   f i r s t   o n e   i s   a   c o a r s e   s e a r c h   w i t a   l a rge   di a m o n s e a r c h   p a t t e rn  (L D S P t o   f i n 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 nd  s e c o n o n e   i s   a   f i n e   s e a r c h   us i n a   s m a l l   di a m o n s e a r c h   p a t t e rn   (S D S P t o   f i n t h e   b e s t   m o t i o n   v e c t o r   i n   t he   l o c a t e s m a l l   a r e a .   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 n t e r e a t   t h e   o r i g i n   o f   t h e   s e a r c h   w i ndo w ,   a n t h e   c h e c ki ng  po i n t s   o f   L D S P   a r e   t e s t e d.   If  t h e   m i n i m u m   s um   of   a bs o l ut e   di f fe r e n c e   (S A D m i n c a l c ul a t e i s   n o t   l o c a t e a t   t h e   c e n t r e   po s i t i o n ,   n e w   L D S i s   fo r m e w h i c h   i s   c e n t e r e a t   t h e   S A D mi n   po i n t   f o un i n   t he   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 unt i l   SAD mi n   o c c ur s   a t   t h e   c e n t r e   po i nt .   A t   a n y   s t a ge   i f   S A D mi n   o c c ur s   a t   c e n t r e   o L D S P ,   t h e   s e a r c h   p a t t e rn   i s   s w i t c h e 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 s t a ge .   A m o n g   t h e   f i v e   c h e c ki ng  po i n t s   i S D S P ,   t h e   po s i t i o n   y i e l di n g   t h e   S A D m i n   pr o v i de s   t h e   m o t i o n   v e c t o r   o f   t h e   b e s t   m a t c h i n g   b l o c k.     G e n e ra l l y ,   a   c i r c l e - s ha pe s e a r c h   p a t t e rn   w i t h   a   u n i f o r m   di s t r i b ut i o n   o f   a   m i n i m um   num b e r   o s e a r c h   po i nt s   i s   d e s i r a b l e   t o   a c h i e v e   t h e   f a s t e s t   s e a r c h   s pe e uni f o r m l y .   T h e   di a m o n s ha pe pa t t e rn   i s   n o t   c l o s 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 0   r o t a t i o o f   a   s qua r e .   Ce   Z h u,   X i a o   L i n ,   a n L a p - P ui   C h a [4]  pr o po s e   a   h e xa go na l   s e a r c h   pa t t e rn   (H S 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   o v e r   t h e   D S   a l go r i t h m   w i t h   s i m i l a r   di s t o r t i o n   pe r f o r m a n c e .   T h e   H S   a l go r i t hm   us e s   t w o   s e a r c h   p a t t e rn s ,   a   l a r ge   h e xa go na l   pa t t e rn   w h i c h   i s   c l o s e   e n o ugh   t o   a   c i r c l e   a nd  a   s m a l l   h e x a go na l   p a t t e rn   a s   s h o w n   i n   F i g u r e   1 (c a n ( d).   I n   t h e   f i r s s t e of   s e a r c h,   t h e   l a r ge   h e xa go n a l   p a t t e rn   w i t s e v e n   c h e c ki n g   po i n t s   i s   us e f o r   c o a r s e   s e a r c h .   I n   t h e   s e c o n s t e i f   t h e   S A D m i n   i s   fo 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   p a t t e rn,   i n c l udi ng  f o ur   c h e c ki n g   po i n t s   f o r   t h e   f o c u s e i nn e r   f i n e   s e a r c h.   O t h e r w i s e ,   t h e   s e a rc h   c o n t i nue s   a r o un t h e   po i nt   w i t h   S A D m i n   us i n g   t h e   s a m e   l a r ge   h e xa go n a l   pa t t e rn.   T h e   h e xa go na l   s e a r c h   a l go ri t hm   r e duc e s   t h e   s e a r c h   po i nt s   by   i m pr o v i n t h e   c o a r s e   s e a r c h   s pe e a ga i n s t   t h e   D S   a l go ri t hm .     A n   e nha n c e h e x a go na l   s e a r c h   ( E H S a l go r i t h m   [6]  i s   pr o p o s e t o   r e duc e   t h e   s e a r c h   po i nt s   f ur t h e r.   T h i 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 t e c hni qu e   t o   i m p r o v e   t h e   i nn e r   s e a r c s pe e a ga i n s t   t h e     H S   [4].   I n   H S ,   t h e   e nt i r e   i nn e r   s e a r c po i n t s   i n s i de   t h e   l a r ge   h e xa go n   ha v e   t o   be   e v a l ua t e d,   w h i c h   i s   c o m put a t i o n a l l y   i n e f f e c t i v e .   T h e   E H S   a l go ri 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 po i n t s   by   e xpl o i t i n t h e   g r o up - s um   d i 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 c h e c ke e n dpo i n t 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 x a go na l   p a t t e rn  t o   t ra 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 .   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 30     2 37   232   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   of   t h e   l a rge   h e xa go n   a s   s h o w n   i n   F i g u r e   2 (a ) .   A t   e a c h   g r o up ,   t h e   gr o up - s u m   di s t o rt i o n   i s   c a l c u l a t e a nd  t h e n   f oc us e i n n e c h e c ki ng  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   di s t o r t i o n   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 n i m u m   di s t o r t i o po i n t .   T hr e e   i nn e r   s e a r c hi n po i n t s   n e a r by   t h e   s m a l l e s t   di s t o r t i o n   g r o up  w i l l   be   c a l c ul a t e i n   t h e   f oc us e d   in n e s e a r c 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 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   d i s t o rt i o g r o up  w i l l   b e   us e i t h e   f o c us e i nn e r   s e a r c h.     A n   e nh a n c e h e xa go na l - b a s e s e a r c h   us i ng  po i n t - o ri e n t e i nn e r   s e a r c h   (E H S - P O IS )   i s   p r e s e n t e   i n   [7]  f o r   f urt h e r   r e duc t i o n   o f   t h e   s e a r c h   po i nt s   o v e r   E H S .   T h e   E H S - P O IS   us e s   a e ff i c i e n t   g r o upi ng  m e t h o fo r   t h e   l a r ge   h e xa go n   w h i c h   i s   b a s e o n   m i ni m i z i n m e a n   i n t e rn a l   di s t a n c e   (M ID f o r   e a c h   i nn e r   po i n t ,   a s   s h o w n   i n   F i g u r e   2 (b ).   T h e   e i g ht   i nn e r   po i n t s   e n c l o s e by   l a rge   h e xa go n   a r e   di v i de i nt 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 ,   a n po i n t s   a n s e c on s e t   i n c l ude s   b   a n po i nt s .   T h e s e   po i n t 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 xa go n   p o i n t s .   T h e   n o rm a l i z e g r o up  di s t o r t i o n s   (N G D s of   t h e   h e xa go n   a r e   c a l c ul a t e d   a nd  t h e   m i n i m u m   N G D s   i n   e a c h   s e t   a r e   fo un d .   T h e   t w o   i nn e r   po i n t s   r e l a t e 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 t o   f i n 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 E H S   r e qui r e s   2   o r   3   s e a r c h   po i nt s   de pe ndi n g   o n   t h e   po rt i o o f   i nne r   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 o f   E H S - P O IS   r e qui r e s   o n l y   s e a r c h   po i nt s   c o n s t a n t l y .     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 n di r e c t i o n - o ri e nt e i nn e r   s e a r c h   (E H S - D O IS [8]  h a s   s h o w n   t h e   c o n s i de ra 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 ,   E H S - P O IS ,   a n E H S - D O IS   a l go r i t h m s   us e   s a m e   l a r ge   h e x a go na l   s e a r c h   pa t t e rn   f o r   c o a r s e   s e a r c h   a n f i n s m a l l   h e xa go n a l   a r e a   us i n s a m e   pr o c e dura l   s t e ps .   B ut ,   t h e s e   a l go r i t h m s   ha v e   di ff e r e n t   p r e d i c t i o n   s t ra t e gi e s   t o   f i n t h e   po r t i o n   o f   i n n e r   c h e c ki n po i nt s   f o r   f i n e   s e a r c h.   A f t e r   f i n i s h i ng  c o a r s e   s e a r c h ,   E H S - D O IS   fo r m s   ps e udo - p o 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   2 (c ).   T h e   g r o up  d i s t o rt i o n s   of  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   o f   l a r ge   h e x a go n.   S e l e c t   o n e   po i n t   i   { a,   b,   c ,   d ,   e ,   f ,   g ,   h }   t ha t   w o ul be   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 - po i n t   w i t h   m i ni m u m   di s t o r t i o n   a m o n e i g ht   ps e udo - po i n t s .   T h e   S A D   a t   t hi s   s e l e c t e p o i n t   i s   f i na l l y   e v a l ua t e t o   f i n d   t h e   f i na l   m o t i o n   v e c t o r .           (a                                   (b                                     (c                                    (d)     F i g u r e   1 .   S e a r c h   pa t t e rn s   o f   D S   a n d   H S   a l go ri t hm s   (a )   L D S P   w i t h   9   s e a r c po i n t s   (b S D S P   w i t h   5   s e a r c h   po i n t s   (c L a r ge   h e xa go na l   p a t t e rn  (d)   S m a l l   h e x a go na l   pa t t e rn                       (a )               (b )       (c )     F i g u r e   2 .   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   Evaluation Warning : The document was created with Spire.PDF for Python.
IJ E CE     IS S N :   2088 - 8708       A   T hr e e   P oi nt   D i r e c t i ona l   Se ar c B l o c k   Ma t c hi ng   A l gor i t hm   ( A .   V .   P ar am k us am )   233   3.   TH R EE - P O I N T   D I R EC TI O N A L   S EA R C H   (TD S )   A LG O R I TH M   T h e   T D S   ha s   b e e n   pr o po s e t o   f i n o ut   t h e   m o t i o n   v e c t o r s   w i t h   f e w e r   n um b e r   o f   s e a r c po i n t s .     T h e   s t ra t e gy   of   T D S   i s   t o   ke e s e a r c h i n f o r   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 po i nt   i n   t h e   m o s t   p r o b a b l e   di r e c t i o n s ,   u n l i ke   t h e   p r e v i o us   f a s t   s e a r c m o t i o n   e s t i m a t i o a l go r i t hm s   w h e r e   a l l   t h e   di r e c t i o n s   a r e   c h e c ke d.   A s   s h o w n   i F i gu r e   3 ,   t h e   p r o po s e T D S   c o n s i s t s   o f   po s s i b l e   s e a r c h   pa t t e rn s   o f   w h i c h   e i g ht   a r e   di r e c t i o n a l   pa t t e rn s   a n d   t h e   r e m a i ni n o n e   i s   i ni t i a l   s e a r c h   p a t t e rn.   T he   i ni t i a l   s e a r c pa t t e rn   i s   a   c o m pa c t   di r e c t i o n a l   s y m m e t ri c   s e a r c h   pa t t e rn   ( F i g u r e   4 )   w h i c h   c o n s i s t s   o f   ni n e   s e a r c h   po i n t s .   I t h e   f i r s t   s t e o f   t h e   s e a r c h,   w e   fo l l ow   t h e   i n i t i a l   s e a r c h   p a t t e rn   w h e r e   w e   c h e c e i gh t   a dj a c e n t   po i n t s   o f   t h e   s e a r c h   c e n t r e   i n   e i g ht   di r e c t i o n s   i n c l udi ng  t h e   s e a r c c e n t r e   i n   o r de r   t o   f i n o ut   t h e   m o s t   p r o ba b l e   s e a r c h   di r e c t i o n   i n   w h o s e   v i c i n i t y   t h e   M B D   i s   pr e s e nt .   T h e r e a f t e r,   w e   c o n t i nue   t h e   s e a r c h   us i ng  a   pa rt i c ul a r   s e a r c h   pa t t e rn   f r o m   a m o n t h e   e i g h t   s m a l l   t hr e e - po i n t   d i r e c t i o n a l   s e a r c h   p a t t e rn s   a t   e a c h   s t e o f   t h e   s e a r c h .   A t   a n y   gi ve n   s e a r c h   s t e p,   s e l e c t i o n   o a   s e a r c h   pa t t e rn   de pe n ds   o n   t h e   s e a r c h   di r e c t i o n   of   t h e   pr e v i ous   s e a r c h   s t e p.   S e a r c h   di r e c t i o n   i s   de f i n e a s   t h e   di r e c t i o n   f r o m   t h e   s e a r c c e n t r e   t o   l o c a t i o n   o f   t h e   M B D   po i n t .   T h e   s e a r c h   c e nt r e   a nd  t h e   M B D   po i nt   a r e   uni que   a t   e a c h   s t e o f   t h e   s e a r c h.   W h i l e   t h e   s e a r c h   c o n t i n ue s ,   i f   t h e   M B D   i s   fo un i n   t h e   c e n t r e   a t   a n y   s e a r c s t e p,   t h e   s e a r c h   c e a s e s   a n t ha t   s e a r c h   c e n t r e   i s   t h e   r e qui r e m o t i o n   v e c t o r .   T h e r e   a r e   e i ght   di r e c t i o na l   s e a r c h   pa t t e rn s   c o rr e s po n di ng  t o   t h e   e i g h t   po s s i b l e   di r e c t i o n s .   O n c e   t h e   s e a r c h   d i r e c t i o n   i s   o b t a i n e d ,   t hr e e   a ddi t i o na l   s e a r c h   po i n t s   a c c o r di n t o   t h e   s e a r c h   di r e c t i o (t h e   r e d i a m o n ds   i n   e a c h   di r e c t i o na l   s e a r c h   pa t t e rn  a s   s h o w n   i n   F i gu r e   3   a r e   s e l e c t e f o r   t h e   n e xt   s t e a s   f o l l o w s :   L e t   t h e   s e a r c h   c e n t r e   a n t h e   M B D   po i n t   i n   a   gi v e n   s e a r c h   s t e b e   de n o t e by   S ‟  a n M ‟  r e s pe c t i v e l y .   T h e   s t ra i g h t   l i n e   f r o m   S ‟  t o w a r M ‟  i n d i c a t e s   t h e   s e a r c h   di r e c t i o n .   E xt e n t h e   l i n e   SM   i n   t h e   s e a r c h   d i r e c t i o n   a n d   s e l e c t   t h e   s e a r c po i nt   w hi c i s   c l o s e s t   t o   t h e   M B D   po i n t   o n   t h e   e xt e n de l i n e .   L e t   t h i s   s e a r c h   po i nt   b e   de n o t e by   A ‟  a s   s h o w n   i n   F i g u r e   3.   T h e   re m a i ni n t w o   po i n t s   B ‟  a n C ‟  (F i g u r e   3)  a r e   s e l e c t e i n   s uc h   a   w a y   t h a t   t h e   l i n e s   MB   a n MC   a r e   a t   a n gl e s   π/ a nd  -   π/ 4   w i t r e s pe c t   t o   MA .   T h e   s e a r c pr o c e dur e   w i t T D S   i s   s u m m a r i z e a s   f o l l ow s .   S t e 1)  T h e   i ni t i a l   c o m pa c t   di r e c t i o na l   s y m m e t r i c   s e a r c h   pa t t e rn  (F i g u r e   4 )   i s   c e n t e r e a t   t h e   o r i gi of   t h e   s e a r c w i n do w .   S t e 2)  T h e   b l o c di s t o r t i o n s   a r e   c a l c ul a t e a t   ni n e   s e a r c h   po i n t s   o f   t h e   c o m pa c t   di r e c t i o n a l   s y m m e t ri c   s e a r c h   pa t t e rn.   If   t h e   l o c a t i o n   o f   t h e   M B D   o c c ur s   a t   t h e   c e nt e r,   t h e   s e a r c h   c o m e s   t o   a n   e n a n t h e   s e a r c h   c e nt r e   i s   c o n s i de r e a s   t h e   m o t i o v e c t o r .   O t h e r w i s e ,   pr o c e e t o   s t e 3.   S t e 3)  S e t   t h e   l o c a t i o o f   t h e   M B D   a s   t h e   n e w   c e n t e r ,   f i n d   t h e   s e a r c h   d i r e c t i o n,   a n s e l e c t   t h e   pr o pe s e a r c p a t t e rn  f o r   t h e   n e xt   s t e a c c o r di n t o   t h e   s e a r c di r e c t i o n .   S t e 4)  T hr e e   a ddi t i o na l   s e a r c h   po i n t s   (t h e   r e di a m o n ds   i n   F i g u r e   3)  a r e   c h e c ke b a s i n o n   t h e   s e l e c t e pa t t e rn.   If   t h e   l o c a t i o o f   t h e   M B D   r e m a i n s   u n c ha n ge d,   t h e   s e a r c h   d i s c o n t i n ue s ,   a nd  t h e   m o t i o v e c t o r   i s   s e t   a t   t h e   l o c a t i o n   o f   t h e   M B D .   If  n o t ,   r e t u rn   t o   s t e 3.   A n   e xa m pl e   o a   s e a r c h   p r o c e dur e   by   t h e   T D S   t o   l o c a t e   t h e   m o t i o n   v e c t o r   (3 ,   - 2)  i s   s h o w n   i F i g u r e   5 .                  (a )                                                                                 (b                                                                                 (c )                                                                                   (d)                 (e                                                                                 (f                                                                              (g)                                                                                 ( h )     F i g u r e   3 .   S e a r c h   pa t t e rn s   o f   T D S .   (a )   R i g h t   pa t t e rn  (b U p - r i ght   pa t t e rn   (c )   U pa t t e rn  ( d)  U p - l e f t   pa t t e rn   (e L e f t   pa t t e rn  (f D o w n - l e f t   pa t t e rn   (g)  D o w n   p a t t e rn  ( h )   D o w -   ri g ht   pa t t e rn   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 30     2 37   234       F i g u r e   4 .   T h e   i n i t i a l   s e a r c pa t t e rn   o f   t h e   T D S           F i g u r e   5 .   A e xa m pl e   o f   a   s e a r c h   p r o c e dur e   by   t h e   T D S   t o   l o c a t e   t h e   m o t i o v e c t o r   (3,   - 2) .   E a c c a n di da t e   i s   m a r ke d   w i t h   i t s   s t e n u m b e r ,   w i t h i w h i c o n l y   o n e   i s   t h e   m i ni m u m   B D M   po i nt   (f i l l e by   r e c o l o r ).       4.   EX P ER I M EN TA R ES U L TS   T o   e v a l ua t e   t h e   pe r f o r m a n c e   o t h e   pr o po s e m e t h o d,   e l e v e n   v i de o   s e que n c e s   w h i c h   c o n s i s t   of  di f fe r e nt   t y pe s   of   m o t i o n   c o n t e n t   a n v a r i o us   fo r m a t s   i n c l ud i n Q CIF ,   CIF ,   a n H D   a r e   us e d.   T h e   l um 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 ra m e s   o f   t h e s e   v i de o   s e que n c e s   a r e   c o n s i de r e i n   t h e   s i m ul a t i o n .   T h e   b l o c s i z e   i s   s e t   t o   16   ×   16  a n d   t h e   s e a r c h   ra n ge   t o   ±63  f o r   hi g h   de f i n i t i o n   v i de o   s e que n c e s   (K i r s t e n - S a ra ,   R o c k e t   l a u n c a n F o o t b a l l   s e que n c e s a nd  ±15  f o r   t h e   r e m a i n i n g   v i de o   s e que n c e s .   T h e   S A D   i s   us e a s   t h e   e rr o m e a s u r e m e nt   f o f i n d i n g   t h e   m o t i o v e c t o r .     T h e   F ul l - S e a r c h   a l go ri t hm   a c h i e v e s   t h e   h i g h e s t   P S N R   a s   i t   s e a r c h e s   a l l   po s s i b l e   s e a r c h   po i n t s   i n   t h e   s e a r c h   w i n do w   a n t hus   i s   gua ra n t e e t o   f i n gl o b a l   m i ni m u m   po i nt .   S o ,   t h e   P S N R   a c h i e v e by   F ul l - S e a r c h   a l go ri t hm   i s   us e a s   r e f e r e n c e   t o   c o m pa r e   o r   e v a l ua t e   o t h e f a s t   b l oc m a t c h i ng  a l go r i t hm s .   I f a c t ,   i t   i s   n o t   po s s i b l e   t gr o un t h e   qua l i t y   o t h e   r e s ul t s   by   e xc l udi n F u l l - S e a r c h   a l go r i t hm .   T h e   s i m u l a t i o n   r e s ul t s   w i t h   pr o po s e T D S   a l go r i t h m   a r e   c o nt r a s t e w i t h   t h o s e   o f   o t h e a l go r i t hm s   i t w o   a s pe c t s ,   w h i c h   a r e :   1)   T h e   a v e r a ge   s e a r c h   po i nt s   pe r   b l o c a n d   2)   T h e   a v e r a ge   pe a k   s i g na l - to - n o i s e   r a t i o   (P S N R pe f ra m e .   T h e   r e s ul t s   pe rt a i n i ng  t o   t h e   s pe e pe r fo r m a n c e   (i . e . ,   t h e   a v e r a ge   s e a r c h   po i n t s   pe r   b l o c k)  of   a l l   t h e   f a s t   b l o c m a t c hi n a l go ri t hm s   i n c l ud i n t h e   pr o po s e T D S   a l go ri t hm   a r e   s um m a ri z e i n   T a b l e   1 .   F r o m   T a b l e   1 ,   i t   i s   c l e a r   t ha t   t h e   n u m b e r   o f   s e a r c h   po i n t s   c a n   b e   r e duc e m o r e   by   a ppl y i n T D S   a l go r i t hm   t ha n   a n y   o t h e s t a t e - of - t h e - a r t   f a s t   b l o c m a t c h i ng  a l go r i t hm s .   I o t h e w o r ds ,   t h e   T D S   m a y   f i n a n y   m o t i o v e c t o r   i m o t i o f i e l w i t h   f e w e r   s e a r c h   po i nt s   t ha a n y   o t h e r   s t a t e - of - t h e - a r t   f a s t   b l o c m a t c h i n g   a l go ri t hm s .     T h e   r e s ul t s   pe rt a i n i n g   t o   t h e   m o t i o p r e di c t i o n   qua l i t y   (i . e . ,   t h e   a v e r a ge   P S N R   pe r   f ra m e o f   a l l   t h e   f a s t   b l oc m a t c h i n g   a l go r i t hm s   i n c l ud i n t h e   p r o po s e T D S   a l go ri t hm   a r e   s h o w n   i n   T a b l e   2 .   It   c a n   b e   ob s e r ve f r o m   T a b l e   2   t h a t   t h e   a v e r a ge   P S N R s   ob t a i n e by   T D S   a r e   b e t t e r   t ha n   t h o s e   of   D S ,   H S ,   E H S ,   E H S - P O IS ,   E H S - D O IS   a n d   D G D S   a l go ri t hm s   i n   m a n y   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   T D S   i s   b e t t e r   by   0. 24dB ,   0 . 52 dB ,   0. 6 4dB ,   0. 51dB ,   1 . 29dB   a n d   0. 15dB   w h e n   c o m pa r e t o   t h e   t o t a l   a v e r a ge   P S N R s   of   t h e   a l go ri t hm s   o f   D S ,   H S ,   E H S ,   E H S - P O IS ,   E H S - D O IS   a nd  D G D S   r e s pe c t i v e l y .     T h e   pr o po s e T D S   i s   be t t e r   t ha n   DS   a l go r i t hm   w i t h   r e s pe c t   t o   t h e   a v e ra ge   P S N R   pe r   f r a m e   w i t l e a s t   c o m put a t i o n a l   c o s t .   T h e   P SN R   pe r f o r m a n c e   o f   T D S   i s   e i t h e a p p r o xi m a t e l y   e qua l   t o   t ha t   o f   D GD S   o r   b e t t e r .   I n   a   f e w   c a s e s ,   t h e   P SNR   pe r f o r m a n c e   i s   l e s s   w h i c h   i s   i n s i g n i f i c a n t .   H ow e ve r ,   t h e   n um b e r   o f   a ve r a ge   s e a r c h   po i nt s   pe r   b l o c h a s   g r e a t l y   r e duc e i n   t h e   T D S   w h e c o m pa r e t o   t h i s   a l go r i t hm .   Co m i n t o   t h e   H S   a l go r i t hm ,   t h e   p r o po s e T D S   s h ow s   b e t t e r   P SNR   pe r f o r m a n c e   a s   w e l l   a s   s pe e d   pe r f o r m a n c e .   W h e n   c o m pa r e t o   t h e   e nha n c e v e r s i o n s   of   H S   i . e . ,   E H S ,   E H S - P O IS   a n E H S - D O IS   a l go ri t hm s ,   t h e   T D S   s h o w s   n o t i c e a b l e   s pe e d   i m p r o v e m e n t   a ga i n s t   t h e s e   a l go ri t hm s .   H ow e v e r ,   t h e   a v e r a ge   P S N R   pe r   f ra m e   ha s   g r e a t l y   r e duc e i t h e   T D S   w h e c o m pa r e t o   t h e s e   a l go ri t hm s .   Evaluation Warning : The document was created with Spire.PDF for Python.
IJ E CE     IS S N :   2088 - 8708       A   T hr e e   P oi nt   D i r e c t i ona l   Se ar c B l o c k   Ma t c hi ng   A l gor i t hm   ( A .   V .   P ar am k us am )   235   T a b l e   1 A v e r a ge   S e a r c P o i nt s   pe B l o c k   V i d e o   T D S   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 g o ri t h m s   DS   HS   E H S   E H S - P O IS   E H S - D O I S   DGDS   F u l l - s e a rc h   F o r e m a n   1 0 . 5 7   1 7 . 7 1   1 3 . 0 4   1 0 . 8 9   1 0 . 9 2   1 0 . 6 1   1 8 . 6 4   7 8 2 . 2 1   M o b i l e   9 . 7 5   1 3 . 2 6   1 0 . 7 1   8 . 7 1   8 . 6 3   7 . 7 1   1 1 . 6 0   8 6 9 . 3 3   Rh i n o s   1 3 . 2 8   2 8 . 7 4   1 9 . 9 0   1 7 . 9 2   1 7 . 8 5   1 6 . 5 9   3 4 . 2 7   8 5 5 . 5 0   Ro b o t   b o a t   1 3 . 7 7   2 7 . 0 0   1 8 . 6 8   1 6 . 8 5   1 6 . 6 4   1 5 . 8 7   3 2 . 6 7   8 5 5 . 5 0   S u z i e   9 . 0 7   1 2 . 9 6   1 0 . 4 4   8 . 4 0   8 . 3 1   7 . 4 8   1 1 . 1 6   7 8 2 . 2 1   A k i y o   7 . 8 7   1 1 . 4 3   9 . 6 4   7 . 5 6   7 . 5   6 . 6 8   7 . 8 7   7 8 2 . 2 1   Cri c k e t   1 0 . 3 7   1 8 . 1 3   1 3 . 7 3   1 1 . 6 3   1 1 . 6 5   1 0 . 7 1   1 6 . 4 8   8 5 5 . 5 0   F l o w e r   9 . 4 9   1 5 . 1 1   1 1 . 8 9   9 . 9 1   9 . 8 1   8 . 9 1   1 3 . 6 5   8 5 5 . 5 0   K i r s t e n - S a ra   8 . 5 0   1 3 . 5 0   1 1 . 1 8   9 . 4 3   9 . 1 6   8 . 1 9   9 . 5 8   1 3 9 7 7 . 2 1   Ro c k e t   l a u n c h   9 . 0 4   1 8 . 5 3   1 3 . 8 7   1 1 . 9 7   1 1 . 8 5   1 0 . 8 7   1 5 . 5 0   1 3 9 7 7 . 2 1   F o o t b a l l   1 0 . 5 0   2 8 . 1 5   1 9 . 5 7   1 7 . 7 2   1 7 . 5 6   1 6 . 5 7   2 7 . 6 2   1 3 9 7 7 . 2 1   T o t a l   A v e ra g e   1 0 . 2 0   1 8 . 5 9   1 3 . 8 7   1 1 . 9 0   1 1 . 8 0   1 0 . 9 2   1 8 . 0 9   4 4 1 5 . 4       T a b l e   2 .   A v e r a ge   P S N R   pe r   F ra m e   V i d e o   T D S   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 g o ri t h m s   DS   HS   E H S   E H S - P O IS   E H S - D O I S   DGDS   F u l l - s e a rc h   F o r e m a n   2 8 . 5 1   2 8 . 1 6   2 7 . 7 7   2 7 . 4 0   2 7 . 6 0   2 6 . 7 0   2 8 . 2 8   2 8 . 8 9   M o b i l e   2 3 . 8 8   2 3 . 8 3   2 3 . 6 6   2 2 . 9 6   2 3 . 4 7   2 2 . 7 1   2 3 . 8 7   2 3 . 9 5   Rh i n o s   2 7 . 9 2   2 7 . 0 6   2 6 . 8 4   2 6 . 8 6   2 6 . 8 9   2 6 . 7 5   2 7 . 4 5   2 9 . 1 6   Ro b o t   b o a t   2 7 . 7 8   2 7 . 3 5   2 7 . 2 0   2 7 . 2 0   2 7 . 2 1   2 7 . 0 5   2 7 . 7 1   2 8 . 7 1   S u z i e   3 5 . 4 5   3 5 . 2 1   3 4 . 8 2   3 4 . 6 3   3 4 . 9 2   3 3 . 8 7   3 5 . 2 5   3 5 . 3 0   A k i y o   4 4 . 4 4   4 4 . 1 6   4 4 . 1 3   4 4 . 0 3   4 4 . 1 5   4 3 . 2 5   4 4 . 1 6   4 4 . 1 6   Cri c k e t   3 3 . 8 1   3 3 . 8 0   3 3 . 6 1   3 3 . 5 9   3 3 . 6 0   3 2 . 9 1   3 3 . 9 0   3 5 . 5 7   F l o w e r   3 2 . 5 7   3 2 . 3 2   3 1 . 7 8   3 1 . 9 7   3 2 . 0 3   3 0 . 4 1   3 2 . 4 0   3 2 . 6 2   K i r s t e n - S a ra   4 5 . 6 9   4 5 . 7 4   4 5 . 1 7   4 5 . 1 6   4 5 . 2 5   4 4 . 0 5   4 5 . 5 4   4 5 . 9 7   Ro c k e t   l a u n c h   3 9 . 9 5   4 0 . 1 5   3 9 . 8 1   3 9 . 7 2   3 9 . 7 5   3 8 . 9 1   4 0 . 2 2   4 1 . 3 1   F o o t b a l l   2 7 . 9 9   2 7 . 5 8   2 7 . 4 9   2 7 . 4 9   2 7 . 5 1   2 7 . 2 1   2 7 . 6 2   3 3 . 6 6   T o t a l   A v e ra g e   3 3 . 4 5   3 3 . 2 1   3 2 . 9 3   3 2 . 8 1   3 2 . 9 4   3 2 . 1 6   3 3 . 3 0   3 4 . 4 8       T o   f i gur e   o ut   t h e   e f f i c i e n c y   of   pr o po s e T D S   a l go ri t hm     m o re   ga r i s h l y ,   t h e   a v e ra ge   P S N R   pe r   f ra m e   a n t h e   a v e r a ge   s e a r c h   po i n t s   pe r   b l o c of   a l l   t h e   f a s t   b l o c m a t c hi n a l go r i t hm s   i n c l ud i n t h e   p r o po s e T D S   a l go ri t hm   us i ng  F o r e m a a n F o o t b a l l   v i de o   s e que n c e s   ha v e   be e n   pl o t t e i n   F i g u r e   6   a n F i g u r e   r e s pe c t i v e l y .   F i g ur e   6 (a )   a n d   F i g u r e   7 (a )   pl o t   a   f r a m e - by - f r a m e   c o m pa r i s o o f   t h e   a v e ra ge   s e a r c po i n t s   pe r   b l oc fo r   t h e   p r o po s e T D S   a l go r i t hm   a n f a s t   b l o c m a t c hi n a l go ri t hm s   a p pl i e t o   t h e   F o r e m a n   a nd  F oo t b a l l   v i de o   s e que n c e s   r e s pe c t i v e l y .   F i g ur e   6 (b a n F i g ur e   7 (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 v e r a ge   P SNR   f o r   t h e   p r o po s e T D S   a nd  f a s t   b l o c m a t c h i n a l go r i t h m s   a pp l i e t o   t h e   F o r e m a a n d   F o o t b a l l   v i de o   s e que n c e s   r e s pe c t i v e l y .   F i g ur e   6 (a a nd  F i g u r e   7 (a c l e a rl y   s h o w   t h e   s upr e m a c y   of   t h e   p r o po s e T D S   a ga i n s t   D S ,   H S ,   E H S ,   E H S - P O IS ,   E H S - D O I S   a n D G D S   a l go r i t hm s   i n   t e r m s   o f   t h e   a v e r a ge   s e a r c h   po i nt s   pe r   b l o c k,   w h i l e   F i g u r e   6 (b a n 7 (b m a ni f e s t   t ha t   t h e   P SN R   pe r f o r m a n c e   o f   t h e   p r o po s e T D S   i s   c l o s e r   t t h a t   o f   F ul l - S e a r c h   l i ke   D S   a n D G D S   a l go r i t h m s   a n b e t t e r   t ha n   t ha t   o f   t h e   e nh a n c e v e r s i o n s   o f   H S   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 h m s .               (a )       (b )     F i g u r e   6 .   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   F o r e m a n”   s e que n c e   i t e r m s   of :   (a )   t h e   a v e r a ge   num b e o f   s e a r c po i n t s   pe b l o c a n (b a v e r a ge   P S N R   pe f ra m 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 30     2 37   236         (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   F o o t b a l l   s e que n c e   i t e rm s   o f :   (a t h e   a v e r a ge   n u m b e r   o f   s e a r c po i nt s   pe b l o c k   a nd  (b a v e r a ge   P S N R   pe r   f ra m e       5.   C O N C LU S I O N     In  t hi s   pa pe r,   w e   h a v e   p r o po s e a   n o v e l   t hr e e - po i nt   d i r e c t i o na l   s e a r c h   ( T D S f o r   m o t i o n   e s t i m a t i o n   i n   v i de o   c o di n g .   W e   e xpl o r e t h e   r e l a t i o n s hi b e t w e e n   s e a r c h   di r e c t i o n   a n s e a r c h   p a t t e rn s .   W i t h   a   k n o w n   s e a r c h   di r e c t i o n ,   a s y m m e t ri c   s e a r c h   p a t t e rn s   a r e   de v e l o pe d,   a nd  t h e   s e a r c h   po i n t s   o n   t h e   o ut s i de   o f   t h e   di r e c t i o n   w e r e   di s r e ga r de d.   S i n c e   t h e   u nn e c e s s a r y   s e a r c h   p o i n t s   a r e   e l i m i n a t e d,   t h e   s e a r c h   s pe e i s   g r e a t l y   i m p r o v e d.   T h e   e xpe r i m e n t a l   r e s ul t s   ha v e   de m o n s t ra t e t h e   s upe r i o r i t y   o f   o ur   p r o po s e m e t h o d.       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 ck - 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   b a 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.   [ 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 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 ,   v o l / 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 :   20 ( 1) ,   pp .   136 ,   143 ,   2010 .   Evaluation Warning : The document was created with Spire.PDF for Python.
IJ E CE     IS S N :   2088 - 8708       A   T hr e e   P oi nt   D i r e c t i ona l   Se ar c B l o c k   Ma t c hi ng   A l gor i t hm   ( A .   V .   P ar am k us am )   237   [ 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   i m 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 da 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 .       B I O G R A P H I ES   O F   A U T H O R S         A d ap a   V e n k at a   P a r am k u s am   i s   a   P r o f e s s o r   o f   E l e c t r o ni c s   a nd  c o m m uni c a t i o E ng i ne e r i ng   a t   t he   M L R   I ns t i t u t e o f   T e c hno l ogy ,   A ut o n o m o us ,   H y de r a ba d.   H e   i s   a   s e l f - di r e c t e d ,   a c t i o n - o r i e n t e d   pr o f e s s i o na l   w i t o v e r   16  y e a r s   t e a c hi ng   e x pe r i e nc e   a t   v a r i o us   r e pu t e E ng i ne e r i ng   C o l l e g e s .   H e   qu a l i f i e i G A T E - 2000  a nd  2001w i t pe r c e n t i l e s   93. 48  a nd  94  r e s pe c t i v e l y .   H e   i s   a   m e m be r   o f   I S T E .   H e   r e c e i v e hi s   B . E   a nd  M . E ,   de g r e e s   i nE l e c t r o ni c s   a nd  c om m uni c a t i o f r o m   A ndhr a   U ni v e r s i t y ,   V i s a k ha p a t n a m ,   I ndi a ,   i 1996  a nd  2004 ,   r e s pe c t i v e l y ,   he   c o m pl e t e d P h . D   i t he   a r e a   o f   v i de o   c o di ng   a t   t he   J N T U H ,   H y de r a ba d .   H e   h a s   o u t s t a nd i ng c o nt r i b ut i o w i t 18  P ub l i c a t i o ns   i t h e   N a t i o na l ,   I E E E   I nt e r na t i o na l   C o nf e r e nc e s   a nd  I nt e r n a t i o na l   J o ur na l s .   H i s r e s e a r c i n t e r e s t s   i nc l ud e   I m a g e   pr o c e s s i ng ,   v i d e o   c o di ng   a nd   v i de o   w a t e r   m a r k i ng .       D .   L axm R e d d y    i s   A s s i s t a n t   P r o f e s s o r   o f   E l e c t r o ni c s   a nd  c o m m uni c a t i o E ng i ne e r i ng   a t   t h e   M L R   I ns t i t u t e   o f   T e c hno l o gy ,   A ut o n o m o us ,   H y de r a ba d . H e   ha s   y e a r s   o f   t e a c hi ng   e x pe r i e nc e   i n   v a r i o us   r e put e E ng ne e r i ng   C o l l e g e s . H e   i s   a   l i f e   t i m e   m e m be r   o f   I S T E .   H e   r e c e i v e B . T e c i n   E l e c t r o n i c s   a nd  c o m m uni c a t i o a nd  M . T e c i C o m put e r s   a n C o m m unc i a t i o ns   f r o m   J N T U   H y de r a ba i 200 a nd  20 11  r e s pe c t i v e l y . H e   ha s   pub l i c a t i o ns   i N a t i o na l   a nd  I nt e r na t i o na l   j o ur na l s .   H i s   r e s e a r c i nt e r e s t s   i nc l ude   V i de o   C o di ng , E m be d de S y s t e m s , C o m m u ni c a t i o n   S y s t e m s .       Evaluation Warning : The document was created with Spire.PDF for Python.