I n d on e s i an   Jo u r n al   o f  El e c t r i c al   En gi n e e r i n g   an d   C o m p u te r   S c i e n c e   V o l .   15 ,   N o .   1 ,  J ul y   201 9 ,   pp .   5 11 ~ 5 16   IS S N :   2502 - 4752 ,   D O I :   10. 1 1591 / i j e e c s . v 1 5 .i 1 . pp 511 - 516             511       Jou r n al   h o m e pa ge :  ht t p: / / i ae s c or e . c om / j our na l s / i nde x . php/ i j e e c s   A u t o m a t i c   m o v i n g   f o r e g r o u n d   e x t r a c t i o n   u s i n g   r a n d o m   w a l k s       I d i r   B o u l fr i fi ,   K h a l i d   H o u s n i ,   A b d e l az i z   M o u l ou d i   I bn  T o f a i l   U ni v e r s i t y / F a c ul t y   o f   S c i e nc e ,   M o r o c c o       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  D e c   1 8 ,   2018   R e v i s e d  J a n   21,   201 9   A c c e pt e d  M a r   4 ,   201 9       I n   t hi s   pa pe r ,   w e   pr o po s e   a   m e t ho d  f o r   a ut o m a t i c   f o r e g r o und  e xt r a c t i o n  i n   v i de o   f r a m e s   by   a na l y z i ng   t he   s pa t i o t e m po r a l   a s pe c t .   W e   d i v i de   o ur   c o nt r i bu t i o n  t o   t r e e   s t e p s :   A u t o m a t i c   s e e d s   de t e c t i o n,   f o r m ul a t i ng   t he   e ne r gy   f unc t i o n,   a nd  u s i ng   t he   r a ndo m   w a l k  a l g o r i t hm   t o   m i ni m i z e   t h i s   f unc t i o n.   F i r s t ,   w e   de t e c t   s e e d s   by   e xt r a c t i ng   a   s pa r s e   o f   goo d  f e a t ur e s   t o   t r a c k  i n  t h e   c ur r e n t   f r a m e   a n d  c o m put e   t he   di f f e r e nc e   be t w e e n  t ho s e   p i xe l s   a nd   i t s   a dj a c e nt   i n  t he   pr e v i o us   f r a m e ,   t he   di f f e r e nc e   o f   pi xe l s   i s   t r e a t e d  i n  H S V   c o l o r   s pa c e   t o   m a ke   t he   r e s ul t   m o r e   a c c ur a t e ,   w e   t h r e s ho l d s   t hi s   d i f f e r e nc e ,   a nd  w e   c l a s s i f y   m ov i ng   a nd  s t a t i o na r y   pi xe l s .   S e c o ndl y ,   w e   f o r m ul a t e   o ur   f o r e g r o und  e xt r a c t i o n  a s   a   g r a ph  b a s e d  pr o bl e m ,   t he n  w e   d e f i ne   a n  e ne r gy   f unc t i o n  t o   e v a l ua t e   s p a t i o t e m po r a l   s m o o t hne s s .   F i n a l l y ,   w e   a ppl i e d  t he   r a ndo m   w a l k  a l g o r i t hm   w i t h  s e e d s   de t e c t e d  i n  t he   f i r s t   s t e p  t o   m i ni m i z e   t he   e ne r g y   f unc t i o n  pr o bl e m ,   t he   s o l u t i o n  l e a ds   t o   e v a l ua t e   t he   po t e nt i a l   t h a t   e v e r y   pi xe l   i n  t h e   v i de o   s e qu e nc e s   i s   m a r ke d  i n  m o t i o n  o r   a   s t a t i o n a r y   pi xe l .   W e   s ug g e s t   t h a t   o ur   u ns up e r v i s e d  m e t ho d  ha s   t h e   po t e n t i a l   t o   be   us e d  f o r   m a ny   ki nds   o f   m o t i o n  de t e c t i o n  a n d  r e a l - t i m e   v i de o .     Ke y w or ds :   A ut o m a t i c   m o t i o n   s e gm e n t a t i o n   E n e rgy   f un c t i o n   G ra p h   R a n do m   w a l k   a l go ri t hm   C opy r i gh t   ©   201 9   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 :   Idi r   B o ul f r i f i ,     F a c ul t y   of   S c i e n c e ,   Ib n   T o f a i l   U n i v e r s i t y ,     K e n i t ra ,   M o r o c c o .   E m a i l :   i b o ul f r i f i @ g m a i l . c o m       1.   I N TR O D U C TI O N   V i de o   fo r e gr o un d   e xt r a c t i o n   a i m s   t o   c l a s s i f y   pi xe l s   of   vi de o   f r a m e s   t o   pi xe l s   b e l o n gs   t o   t h e   fo r e gr o u n d  a nd  b a c kgr o und  pi xe l s ,   m o r e   ge n e r a l l y   t h e   m o s t   e xi s t e d  a pp r o a c h e s   a r e   b a s e d  o n   o pt i c a l   f l ow ,   b a c kgr o un d  s ub t r a c t i o n,   i m a ge s   di f f e r e n c e ,   g r a p h   b a s e d  a p pr o a c h ,   c l us t e ri n g  a l go ri t hm ,   a n d  de e p  l e a rni n g.   It ’s   c a n   b e   us e d  i n   s e m a nt i c   s c e n e   u n de r s t a n d i n g ,   t ra f f i c   s u r v e i l l a n c e ,   r e c o gn i t i o n,   r o bo t i c ,   v i de o   i n de xi ng,   a n d  m a n y   o t h e r   r e e l - t i m e   a pp l i c a t i o n.   A   l o t   o f   r e s e a r c h  h a s   b e e n   f o c us e d  o n   m o t i o n   de t e c t i o n.   T h e y   c a n   b e   c l a s s i f i e d  i nt o   s upe r v i s e d  [1 - 3]  a n d  u n s u pe r v i s e d  m e t h o ds   [4 - 11] .   I n   t h e   f i r s t   c a t e go r y ,   t h e   s e gm e n t a t i o n  r e qui r e s   s o m e   i ni t i a l   s e e ds   t o   be   s e l e c t e d  i n  t h e   f i r s t   f ra m e   t o   pe r f o r m   s e gm e nt a t i o n.   T h e r e fo r e   F a n   a n d  a l .   [1]   us e   a   m a s k  t ra n s f e r   a n d  i n t e r po l a t i o n  m e t h o d,   f r o m   f o r e gr o u n d  m a s k   i n  s o ur c e   f r a m e   h e   e s t i m a t e s   t h e   fo r e gr o u n d  a t   a n   o t h e r   f r a m e .   W a n g  a n d  a l .   [3]  p r o po s e   a n   a l go ri t hm   t o   s e gm e n t   v i de o   b a s e d   o n   a   l e v e l   s e t   f r a m e w o r k  a n d  a n   a ppe a r a n c e   m o de l ,   t h i s   a l go r i t hm   r e qu i r e s   o n l y   a   s i n gl e   f i n ge r  t o uc h   t h e   o b j e c t   i n   t h e   f i r s t   f r a m e .   I n  [17 ]  R o t h e r   a n d   a l .   us e   i t e ra t e d   g r a p h   c ut   t o   e xt ra c t   t h e   f o r e gr o und.   T h e   s e c o n d  c a t e go r y   d o e s n ’t   r e qui r e   a n y   us e r   i n v o l v e m e n t ,   ov e r   t h e   pa s t   de c a de   a   l o t   of   w o r ks   a r e   fo c us e d  o n   a na l y z i n g  i n f o r m a t i o n   l i ke   c o h e r e n c e ,   m o t i o n,   a n d  a ppe a ra n c e   i n   s pa c e - t i m e   b l ob   of   v i de o   [5],   [14],   [8].   W u  a n d   a l .   [15]  p r o po s e   a   m e t h o d  t ha t   us e s   l e a s t   s qua r e s   t r a c ki ng  f ra m e w o r k  a n d  l e a rn e d  a ppe a ra n c e   m o de l s   t o   s e gm e n t   a n d  t r a c k  m o t i o n.   T h e r e f o r e   K h o r e v a   a nd  a l .   [16]   a pp l y   a   m e t h o d  t o   l e a rn   t h e   gra p h   b y   e xpl o i t i n g  e dge   t o po l o g y   a n d  w e i ght s   o f   t h e   g r a p h.   F a k t o r   a n d   a l .   [ 4]  us e   r e - o c c ur r i ng  r e gi o n s   by   c o n s t r uc t i n g  a   g ra p h   o f   t h e   v o t i n g  s c h e m e   o f   r e - oc c ur ri n g  r e gi o n s   a c r o s s   t h e   v i de o   s e que n c e .   V e r t e n s   a n d  a l .   [11]  a r e   us e d  t h e   c o n v o l ut i o n a l   n e u r a l   n e t w o r k  t o   p r e di c t   t he   obj e c t   l a b e l   a n d  m o t i o n   s t a t us   o f   e a c h   pi xe l   i n  a n   i m a ge .   T hi s   c a t e go r y   t a ke s   o n   i t s   i m po rt a n c e   i n   r e a l   t i m e   a pp l i c a t i o n  r e qui ri n g  a n  i n s t a nt a n e o us   und e r s t a n d i n g  o f  t h e   s c e n e .   M o t i o n   s e gm e n t a t i o n   s t i l l   e n c o un t e r s   m a n y   c h a l l e n ge s   l i ke   o c c l us i o n ,   c a m e r a   Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a n  J   E l e c   E ng  &   Co m p  S c i ,   V o l .   15 ,   N o .   1 ,  J ul y   201 9   :     5 1 1   -   5 1 6   512   m o t i o n,   n o i s e ,   a nd  m a n y   c o m pl e x  s i t u a t i o n s ,   s pe c i f i c a l l y   t h e   a u t o m a t i c   m o t i o n   s e gm e n t a t i o n   t h a t   o u r   c o n t ri b ut i o n  w i l l   f o c u s e d.     T h e   f i r s t   s t e e p  i n   o u r   c o n t r i b ut i o n   c o n s i s t   t o   e xt ra c t   s o m e   s e e ds   r e pr e s e n t i ng  pi xe l s   b e l o n gs   t o   t h e   fo r e gr o u n d  a n d  b a c kg r o un d  pi xe l s .   t h e   e xt r a c t i o n   i s   pe r f o r m e d  by   de t e c t i ng  s o m e   goo d  fe a t ur e   t o   t ra c k  [12]   i n   t h e   p r e v i e w   f r a m e   i n   R G B   s pa c e   c o l o r   a nd  m a ke   di f f e r e n c e   b e t w e e n   t h o s e   s pa r s e   po i n t s   a nd  a dj a c e n t   po i n t s   i n   t h e   c urr e nt   f ra m e ,   t o   m a ke   t h e   r e s ul t   m o r e   a c c ura t e   w e   us e   H S V   s pa c e   c o l o r   t o   c o m put e   t h e   di f fe r e n c e .   S e c o n dl y ,   w e   fo r m ul a t e   o ur   i s s ue s   a s   g ra p h   b a s e d  pr o b l e m   t h e n   a n   e n e rgy   f un c t i o n   i s   de f i n e d  t o   e v a l ua t e   l a b e l i n g  pi xe l s ,   by   i n c o r po r a t e   s pa t i a l   a nd  t e m po ra l   i n f o r m a t i o n  i n   v i de o   s e que n c e s .   F i na l l y ,   t h e   ra n do m   w a l k  a l go r i t h m   [13 ]  i s   a pp l i e d  t o   m i n i m i z e   t h e   e n e rg y   f un c t i o n   a n d  ge t   t h e   f i na l   s e gm e nt a t i o n .   T h e   f i gur e   (1 )  e xpl a i n  a n   o v e r v i e w   of   o ur   a pp r o a c h.             F i gu r e   1 .   O v e r v i e w   of   o ur   a pp r o a c h       2.   TH E   P R O P O S ED   M ET H O D   O ur  a p p r o a c h   a i m s   t o   g r o up  pi xe l s   o f   f r a m e s   v i de o   i n t o   pi x e l s   i n   m o t i o n  a n d   s t a t i o n a r y   pi xe l s ,   T h e   o pe r a t i o n   o f  a ffe c t i n g  a   l a b e l   t o   e v e r y   pi xe l   i n   t h e   f r a m e   w e   ge t   t h e   m o t i o n   s e gm e n t a t i o n .   I n   t hi s   pa pe r ,   w e   pr o po s e   a   m e t h o d  b a s e d  o n   t h e   go o d  fe a t u r e s   t o   t r a c k  a nd  di f fe r e n c e   t o   de t e c t   i n i t i a l   s e e ds   a s   i l l us t r a t e d  i n  f i gur e   (2 ),   a nd  ra n do m   w a l ks   a l go ri t hm   t o   m i n i m i z e   t h e   f o r m ul a t e d  e n e r gy   f un c t i o n.           F i gu r e   2 .   T h e   l e f t   f ra m e   i l l us t ra t e   t h e   go o d  f e a t ur e s   t o   t r a c k ,   a n d  t h e   ri g h t   f ra m e   r e p r e s e nt   t h e   i n i t i a l   s e e ds (t h e   b l ue   a r e   i n  m o t i o n   a n d   t h e   r e d   a r e   s t a t i o na r y   Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a n  J   E l e c   E ng  &   Co m p  S c i     IS S N :   2502 - 4752       A ut om a t i c   m o v i ng  f or e gr ou nd  e x t r ac t i o n  us i ng  r a ndom   w al k s   ( Idi r   B ou l f r i f i )   513   2. 1 .       I n i t i al   S e e d s   T h e   e xt r a c t i o n   o f   i n i t i a l   s e e ds   s t i l l   a   m a j o r   c ha l l e n ge ,   due   t ha t   t h e   m o s t   e xi s t i ng  m e t h o ds   a r e   b a s e d  o n   t h e   pr o b a b i l i s t i c   m o de l   a n d  t h e y   a r e   m a n y   di f f i c ul t   s i t ua t i o n s   t h a t   m a ke   t h e   de t e c t i o n   o f  i n i t i a l   s e e ds   i n a c c ura t e .   I n   o u r   a pp r o a c h ,   t o   de t e c t   t h e   i n i t i a l   s e e ds   w e   a re   us e d  [12]  t o   e xt r a c t   a   s pa r s e   o f  goo d  fe a t u r e   t o  t r a c k  i n  R G B   c o l o r   s pa c e   i n   t h e   c u rr e n t   f r a m e   a nd  pe r f o r m i ng  a   d i f f e r e n c e   be t w e e n   t h o s e   s pa r s e   o f   pi xe l s   a n d   hi s   a dj a c e n t   i n   p r e v i e w   f r a m e , t o   i n c r e a s e   t h e   r e s ul t   a c c ur a c y   w e   h a v e   c o m put e d  t h e   di f f e r e n c e   i n   H S V   c o l o r   s pa c e .   By   p e r f o r m i n g  a   t hr e s h o l d  o n   t h i s   di f f e r e n c e   w e   g e t   t h e   c l a s s i f i c a t i o n   of   t h o s e   s pa r s e   pi xe l s ,   i f   i t ’s   b i gge r  t ha n  a   t hr e s h o l d  α1 ,   t h e   p i xe l   i s   l a b e l e d  a s   i n  m o t i o n,   e l s e   i f   i t ’s   s m a l l e r  t ha n  t h e n  a   t hr e s h o l d   α2 ,   t h e   pi xe l   i s   l a b e l e d  s t a t i o n a r y .   T h o s e   i ni t i a l   s e e ds   w i l l   b e   i n c o rpo r a t e d   i nt o   ra n do m   w a l ks   a l go ri t hm   t o   pe r f o r m   o ur   f i n a l   m o t i o n  s e gm e n t a t i o n .     2. 2 .       En e r g y  F u n c ti o n   T o   a c h i e v e   o ur   m o t i o n   s e gm e nt a t i o n,   a n   e n e r gy   f un c t i o n   i s   fo r m ul a t e d  i n c o r po r a t i n g  s p a t i a l   a n d   t e m p o ra l   i n f o r m a t i o n,   s i m i l a r  t o   [19]  w e   ge t   t h e   p r o b a b i l i t y     t h a t   a   pi xe l   i s   i n  m o t i o n   by   t h e   m i n i m i z i n g   t h e   e n e r gy   f un c t i o n  a s   f o l l ow :       Q [ x ] = Q S [ x ] + λ Q T [ x ]   (1)     W h e r e   λ   i s   a   f r e e   pa ra m e t e r  t ha t   c o n t r o l s   t h e   w e i ght i ng  b e t w e e n   t h e   t w o   e n e r g i e s ,   a n d   Q S   r e p r e s e n t   t h e   s pa t i a l   s m o o t hn e s s ,   t hi s   e n e r gy   f un c t i o n   m i ni m i z e s   t h e   e dge s   w e i gh t s   b e t w e e n   n e i g h b o r i n g   p i xe l s ,   i t ’s   de f i n e d  a s   f o l l ow :       Q S [ x ] = x T Lx = ∑ e ij ∈ E w ij ( x i − x j ) 2   (2)     T h e   Q T   de t e rm i n e   t h e   t e m po ra l   s m o o t hn e s s ,   t hi s   f un c t i o n   m i n i m i z e s   t h e   i n c o h e r e n c e   w i t h   p r e d i c t e d  c o n f i de n c e   m i   a n d   s i ,   i t ’s   de f i n e d  a s   f o l l ow :       Q T [ x ] = ∑ v i m i ( 1 − x i ) 2 + ∑ v i s i x i 2   (3)     T h e   e n e r gy   f un c t i o n  (9)   c a n  b e   fo r m ul a t e d   i n  m a t ri c i d a l   f o r m   a s   f o l l o w :       Q [ x ] = x T Lx + λ ( ( 1 − x ) T M ( 1 − x ) + x T Sx )   (4)     W h e r e   m i   r e p r e s e n t   t h e   p r o b a b i l i t y   t h a t   t h e   pi xe l   v i   b e l o n gs   t o   t he   f o r e gr o un d ,   a nd   s i   t h e   p r o b a b i l i t y   t h a t   t h e   p i xe l   v i   b e l o n gs   t o   t h e   b a c kg r o un d .   T h e   o pt i m i z a t i o n   o f   e n e r gy   l e a ds   t o   r e s o l v e   t h e   e qua t i o n     a s   f o l l ow :       ( L U + λ M U + λ S U ) X = − B T M + M U   (5)     T h e   t o w   m a t r i c e s   M   a n d   S   a r e   po s i t i v e   a nd  d i a go n a l .   T o   de t e rm i n e   t h e   c o n f i de n c e   t h a t   t h e   pi xe l   v i   b e l o n gs   t o   t h e   f o r e gr o u n d ,   w e   e v a l ua t e   t h e   g ra di e nt   t o   e v e r y   f r a m e   pi xe l s   i n   t w o   di r e c t i o n s   a n d   w e   c o m put e   t h e   di f f e r e n c e   be t w e e n   pi xe l s   i n   f r a m e   t   e n d  hi s   a dj a c e nt   pi xe l s   i n   f r a m e   t + 1 .   T h e n   w e   c a n   f o r m ul a t e   t h e   c o n f i de n c e   m i ∈ { 0 , 1 }   a s   f o l l o w   :       m i = ( 1 if   | ∇ ( g i t ) − ∇ ( g i t + 1 ) | > s1 , 0 o t h e r w i se ,   (6)     W h e r e   ∇ ( g i t )   r e p r e s e n t   t h e   g ra d i e nt   a t   pi xe l   v i   i n   f ra m e   t .   L i ke   (6)   t h e   c o n f i de n c e   s i ∈ { 0 , 1 }   t h a t   pi xe l   v i   b e l o n gs   t o   b a c kg r o un d   i s   de f i n e d  a s   f o l l o w :       s i = ( 1 if   | ∇ ( g i t ) − ∇ ( g i t + 1 ) | < s2 , 0 o t h e r w i se ,   (7)       3.   R ES EA R C H   M ET H O D   R a n do m   w a l ks   i m a ge   s e gm e nt a t i o n  h a v e   b e e n   p r o po s e d  by   G ra dy   [13].   T h e n  i m a ge   i s   r e p r e s e nt e d  a s   a   g r a p h  G ( V , E )   w h e r e   e a c h  n o de   v i ∈ V   r e pr e s e nt   a   pi xe l   o f   i m a ge   a n d  e a c h   e dge   e ij   r e p r e s e n t   c o nn e c t i o n  b e t w e e n   pi xe l   v i   a n d  n e i g h b o r   pi xe l   v j .   L e t   n = | V |   a nd  m = | E |   w h e r e   | . |   de no t e s   t h e   c a rdi na l i t y ,   e dge   Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a n  J   E l e c   E ng  &   Co m p  S c i ,   V o l .   15 ,   N o .   1 ,  J ul y   201 9   :     5 1 1   -   5 1 6   514   w e i ght   w ij   e v a l ua t e   t h e   s i m i l a r i t y   b e t w e e n   c o nn e c t e d  p i xe l s .   T h e   b a s i c   i de a   o f   r a ndo m   w a l ks   s e gm e n t a t i o n  c o n s i s t   t o   s t a r t i n g  a   r a n do m   w a l k  f r o m   e a c h   pi xe l   i n   t h e   i m a ge   a nd  c o m put e   t h e   pr o b a b i l i t i e s   of   w i t c h   s e e d s   t h e y   f i r s t   a rri v e   a t .   T h e   e dge   w e i ght   c a n  r e p r e s e n t   t h e   di f f e r e n c e   i n   i m a ge   i nt e n s i t y ,   t e xt u r e   i n f o r m a t i o n,   c o l o r   o r   o t h e r  f e a t u r e s .   I n  [1 3]  G ra dy   a ppl i e s   a   G a us s i a n   w e i ght i ng   f un c t i o n   t o   c o n s t r uc t   t h e   g ra p h.       W ij = e x p ( − β ( g i − g j ) 2 )   (8)       g i a n d g j :   i m a ge   i n t e n s i t y   a t   pi xe l   i   a nd   j .  β :   f r e e   p a r a m e t e r .   T o   de a l   w i t h  o t h e r  f e a t u r e s   i n f o r m a t i o n   w e   c a n   r e pl a c e   ( g i − g j ) 2   w i t h   | | g i − g j | | 2 .   T h e   s e gm e n t a t i o n   i s   a c h i e v e d  by   m i n i m i z i n g   t hi s     e n e r gy   f un c t i o n :      Q [ X ] = 1 2 X T LX = 1 2 ∑ e ij ∈ E w ij ( X i − X j ) 2   (9)     T h e   s o l ut i o n   o f  r a n do m   w a l k  p r o b l e m   c o n s i s t s   t o   f i n d  a   ha rm o n i c   f un c t i o n   t ha t   s a t i s f i e s   t h e   L a pl a c e   e qua t i o n  w i t h  r e s pe c t   t o   t h e   b o un da r y   c o n di t i o n s .       ∇ 2 x = 0   (10)     T h e   c o m b i n a t o ri a l   L a p l a c i a n   m a t r i x  L ,   de f i n e d  a s   f o l l ow :     L ij = ( d i i f i = j , − w ij if   v i a n d   v j a r e   a d j a c e n t   n o d e s , 0 o t h e r w i se ,   (11)     W h e r e   L ij   i s   i nde xe d  by   t h e   v e r t i c e s   v i   a n d   v j ,   a n d  = ∑ =  .   T h e   v e rt i c e s   a r e   g r o upe d  i nt o   s e e d e d  n o de s   V m   a nd   u n s e e de d  n o de s   V u ,   w i t h o ut   l o s s   of   ge n e r a l i t y   n o de s   i n  L   a n d   X   a r e   o r de r e d  s uc h  t ha t   s e e d  n o de s   a r e   f i r s t   a n d   u n s e e de d  n o de s   a r e   s e c o n d.   D e c o m po s i n g  e qu a t i o n   (9)  l e a d   t o   :       Q [ X u ] = 1 2 [ X m T X u T ] [ L m B B T L u ] [ X m X u ]   (12)     Q [ X u ] = 1 2 ( X m T L m X m + 2 x u T B T X m + X u T L u X u )   (13)     X U   a nd   X M   c o rr e s po n d   t o   po t e n t i a l s   o f   t h e   s e e de d  a n d   u n s e e de d  no de s   r e s pe c t i v e l y .   D i ff e r e n t i a t i n g   Q [ X u ]   w i t h   r e s pe c t   t o   X u   l e a d   t o   c o m put e   X u   by   s o l v i n g  t h i s   e qua t i o n  :       L u X = − B T M   (14)     T h e   f i n a l   s e gm e n t a t i o n  i s   o b t a i n e d  by   a s s i g n i ng  t o   e a c h  n o de   v i   t h e   l a b e l   s   c o r r e s po n d i n g   t o   M a x ( X i s ) .   W h e r e   t h e   p r o b a b i l i t i e s   a t   a n y   n o de   v i   w i l l   s um   t o   u ni t y   :       ∑ s X i s = 1   (15)     T h e   ra n do m   w a l k  s e gm e n t a t i o n   h a s   n i c e   pr o pe rt i e s   l i ke   r o b u s t n e s s   t o   t h e   w e a k  b o un da r y ,   n o i s e ,   a n d   a v o i da n c e   o f   t r i v i a l   s o l ut i o n s   i n  c o m pa r i s o n   w i t h   g ra p h  c ut   a nd  o t h e r  s e gm e n t a t i o n   a l go ri t hm s .   A l l   t h o s e   a dv a n t a ge s   c o n s o l i da t e   t h e   c h o s e   of   r a ndo m   w a l ks   a l go r i t h m   i n  o ur  a p p r o a c h.       4.   R ES U LTS   A N D   D I S C U S S I O N   W e   h a v e   i m p l e m e nt e d  o ur  a u t o m a t i c   f o r e gr o un d   e xt r a c t i o n   a ppr o a c h   i n   C + +   p r o gra m m i ng  l a n gu a ge   us i n g  o pe n CV ,   b o os t   ,   a n d  e i ge n  l i b r a ri e s ,   o n  a   P C  w i t h   I nt e l (R )  Co r e (T M )  i 5  CP U ,   2 . 40  G H Z ,   4  G o   i n   R A M   a n d  W i n do w s   7  o p e r a t i n g  s y s t e m .   T h e   m e t h o d  w a s   t e s t e d  on   s e v e r a l   v i de o s ,   a n d  t h e   f i gu r e   ( 3)  i l l us t ra t e   t h e   ob t a i n e d  r e s ul t   o n  w a l k  v i de o   s e que n c e   w i t h  λ = 0 . 1 ,   a n d   β = 0 . 01 ,  α1 = 60 ,  α2 = 1 ,  s1 = 20 ,  s2 = 3   gra p h  e dge s   i s   c o n s t r uc t   by   V4   n e i g h b o r s   pi xe l s   a n d   f r a m e   s i z e   i s   160 × 120 .   t h e   c o m pl e xi t y   a l go r i t hm i c   o f  o ur   a pp r o a c h  r e qui r e s   O ( n )   o pe ra t i o n s ,   w h e r e   n  i s   t h e   num b e r  o f  t h e   f ra m e   pi xe l s .   t o   e f f i c i e n t l y   r e s o l ve   t h e   l i n e a r   s y s t e m   of   e qua t i o n s   (13)  m a t r i c e s   a s   r e pr e s e nt e d  a s   a   s pa r s e   m a t ri x ,   s o   i n s t e a d  o f  s t o r i n g  t h e   e n t i r e   Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a n  J   E l e c   E ng  &   Co m p  S c i     IS S N :   2502 - 4752       A ut om a t i c   m o v i ng  f or e gr ou nd  e x t r ac t i o n  us i ng  r a ndom   w al k s   ( Idi r   B ou l f r i f i )   515   m a t r i x ,   a   v e c t o r   of   w e i gh t s   m a y   be   s t o r e d  t o   de c r e a s e   t h e   c o m put a t i o n a l   t i m e .   f i n a l l y ,   G P U - b a s e d   i m p l e m e nt a t i o n   i s   e n c o ur a ge d  f o r   r e a l - t i m e   p r o c e s s i n g  l i ke   b e h a v i o r   a n a l y s i s   a n d  r e c o gn i t i o n,   m o t i o n  a n a l y s i s ,   e ve n t   de t e c t i o n .             F i gu r e   3 .   E xpe r i m e nt a l   r e s ul t s   us i n g  o u r  a pp r o a c h   o n   t h e   w a l k  v i de o   s e que n c e s ,   t h e   f i r s t   r o w   i l l us t r a t e   t h e   go o d  f e a t ur e   t o   t r a c k ,   t h e   s e c o n d  r o w   r e p r e s e n t   t h e   i n i t i a l   s e e ds (b l ue   a r e   i n  m o t i o n   a n d   r e d  a r e   s t a t i o n a r y )  a n d   t h e   t hi r d   r o w   di s pl a y   f i n a l   s e gm e n t a t i o n       5.   C O N C LU S I O N   In  o ur   m o t i o n  de t e c t i o n   a pp r o a c h,   w e   ha v e   pr e s e n t e d  a   s pa t i o t e m po r a l   v i de o   s e gm e n t a t i o n,   by   fo r m u l a t i n g  t h e   de s i r e d  a ut o m a t i c   f o r e gr o und  e xt ra c t i o n   a s   a   gra p h   b a s e d  pr o b l e m .   In   a ddi t i o n   t o   s pa t i a l   c o h e r e n c e   us e d  i n   i m a ge   s e gm e n t a t i o n,   w e   h a v e   a ppl i e d  t h e   t e m po r a l   i n f o r m a t i o n   by   i nt r o duc i ng  a   l i ke l i h o o d   t e rm   i n   t h e   e n e rgy   f un c t i o n,   t hi s   t e rm   pe na l i z e s   t h e   s i m i l a r i t y   b e t w e e n   a dj a c e n t   pi xe l s   i n   t h e   c urr e nt   f r a m e   a n d  n e xt   f r a m e .   L i ke   m uc h   o t h e r   m o t i o n   s e gm e n t a t i o n ,   t h e   ra n do m   w a l ks   a l go r i t hm   w a s   a ppl i e d  t o   m i ni m i z e   t h e   de f i n e d  e n e r gy   f un c t i o n,   a nd  r e s o l v i n g  o u r   l a b e l i n g  p rob l e m   t o   ge t   t h e   f i n a l   p i xe l s   c l a s s i f i c a t i o n .   T h e   i n t e r e s t   o f   o ur   m e t h o d  i n   a ddi t i o n   t o   hi s   pe r f o r m a n c e   t ha t   n o t   r e qu i r e d  a n y   hum a n   i n t e ra c t i o n,   t h e y   c a n   b e   us e d  i n   r e a l   t i m e   a ppl i c a t i o n .   O u r   f ut u r e   w o r k  w i l l   i m p r o v e   t h e   e ff i c i e n c y   of  o ur   a ppr o a c h   f ur t h e r   a n d  m a ke   t h e   r e s ul t   m o r e   a c c u r a t e .       R EF ER EN C ES   [ 1]   Q i ng na n  F a n ,   a nd  a l . ,   “ J um pC u t   :   N o n - S uc c e s s i v e   M a s k  T r a ns f e r   a nd  I nt e r po l a t i o n  f o r   V i de o   C ut o ut , "   A C M   T r ans ac t i ons   on   G r aph i c s ,   201 5;   34 ( 6 ) .     [ 2]   A l i r e z a   F a t hi ,   a nd  a l . ,   “ C o m bi n i ng   S e l f   T r a i n i ng   a nd  A c t i v e   L e a r ni ng   f o r   V i de o   S e g m e nt a t i o n, "   B M V C ,    2011;   1 - 11 .   [ 3]   T i ng hua i   W a ng   a nd  B o   H a n  a nd  J o hn  C o l l o m o s s e ,   “ T o uc hC ut :   F a s t   I m a g e   a nd  V i de o   S e g m e nt a t i o n  us i ng   S i ng l e - T o uc h  I nt e r a c t i o n, "   C om pu t e r   V i s i on   an d   I m age   U n de r s t and i ng ,   20 14;   120;   14 - 30 .     [ 4]   A l o n  F a kt o r   a nd   M i c ha l   I r a n i ,   “ V i de o   S e g m e nt a t i o n   by   N o n - L oc a l   C o ns e ns u s   V o t i ng , "   B M V C ,   2 014;   1 - 12.     [ 5]   F a bi o   G a l a s s o ,   R o be r t o   C i po l l a   a n d  B e r n t   S c hi e l e ,   “ V i de o   S e g m e n t a t i o n  w i t h   S up e r p i x e l s , "   A C C V ,   20 13;   7 60 - 774 .   [ 6]   C he t a n  B ho l e   a nd  C hr i s t o phe r   P a l ,   “ F u l l y   A ut o m a t i c   P e r s o n  S e g m e nt a t i o n  i n  U nc o ns t r a i ne d  V i d e o   us i ng     S pa t i o - t e m po r a l   C o ndi t i o na l   R a ndo m   F i e l d s , "   I m age   and   V i s i on   C o m put i ng ,   2016;   51 .     [ 7]   J i a nbo   S hi   a nd  J i t e n dr a   M a l i k,   “ M o t i o n  S e g m e nt a t i o n  a nd  T r a c ki ng   U s i ng   N o r m a l i z e d  C ut s , "   I C C V ,   1 998;     1154 - 116 0.     [ 8]   M a t t h i a s   G r un dm a nn ,   e t   a l . ,   “ E f f i c i e nt   H i e r a r c hi c a l   G r a ph - B a s e d   V i de o   S e g m e nt a t i o n , "   C V P R ,   2 010;   2141 - 21 48 .     [ 9]   Q i a n  Z h a ng   a nd  K i ng   N g i   N g a n,   “ M u l t i - v i e w   V i d e o   B a s e d  M u l t i pl e   O b j e c t s   S e g m e nt a t i o n  us i ng   G r a ph  C ut   a nd   S pa t i o t e m po r a l   P r o j e c t i o ns , "   J o ur n al   o f   V i s ual   C om m u ni c at i o n  a nd   I m a ge   R e pr e s e nt at i o n ,   20 13;   2 1;   45 3 - 461.     [ 10]   A ne s t i s   P a pa z o g l o u  a nd  V i t t o r i o   F e r r a r i ,   “ F a s t   o bj e c t   s e g m e nt a t i o n  i n  u nc o ns t r a i n e d  v i d e o , "   I C C V ,   2 013;     1777 - 178 4.     Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a n  J   E l e c   E ng  &   Co m p  S c i ,   V o l .   15 ,   N o .   1 ,  J ul y   201 9   :     5 1 1   -   5 1 6   516   [ 11]   J o ha n  V e r t e ns   a nd  A bhi n a v   V a l a d a   a n d  W o l f r a m   B ur g a r d,   “ S M S ne t :   S e m a nt i c   m o t i o n  s e g m e nt a t i o n  us i ng   de e p   c o n vo l ut i o na l   n e ur a l   ne t w o r ks , "   I E E E / R SJ   I nt e r n at i on al   C on f e r e nc e   on  I nt e l l i ge nt   R o bo t s   and  Sy s t e m s   ( I R O S) ,  2017;   5 82 - 589 .     [ 12]   J i a nbo   S hi   a nd  C a r l o   T o m a s i ,   “ G o o d  F e a t u r e s   t o   T r a c k, "   I E E E   C onf e r e nc e   on  C om put e r   V i s i on  a nd  P at t e r n   R e c ogni t i on  ( C V P R ’ 94) ,   1 994;   593 - 600 .     [ 13]   L e o   G r a d y ,   “ R a ndo m   w a l ks   f o r   I m a g e   s e g m e nt a t i o n, "   I e e e   T r ans a c t i on  O n  P at t e r n  A na l y s i s   and  M a c h i ne   I nt e l l i ge nc e ,   2006;   28 ( 11 ) .     [ 14]   C he nl i a ng   X u  a nd  C a i m i ng   X i o ng J a s o n  a nd  J .   C o r s o ,   “ S t r e a m i ng   H i e r a r c hi c a l   V i de o   S e g m e nt a t i o n, "   E C C V ,   2012;   626 - 639 .     [ 15]   Z he ngy a ng   W u,   e t   a l . ,   “ R o bus t   v i d e o   s e g m e n t   p r o po s a l s   w i t h   p a i nl e s s   o c c l us i o n  ha nd l i ng , "   C V P R ,   2015 .     [ 16]   A nna   K ho r e v a ,   e t   a l . ,   “ C l a s s i f i e r   B a s e d  G r a p h  C o ns t r uc t i o n  f o r   V i d e o   S e g m e nt a t i o n, "   C V P R ,   2015 .     [ 17]   C a r s t e n   R o t he r   a nd  V l a d i m i r   K o l m o g o r o v   a nd  A ndr e w   B l a ke ,   “ " G r a bC u t " :   I nt e r a c t i v e   F o r e g r o und  E x t r a c t i o n   U s i ng   I t e r a t e d  G r a ph   C u t s , "   A C M   T r ans .   G r ap hi c s ,   2 004;   23 .     [ 18]   B r uc e   D .   L uc a s   a nd  T a ke o   K a na de ,   “ A n  i t e r a t i v e   i m a g e   r e g i s t r a t i o n  t e c hn i qu e   w i t h  a n  a ppl i c a t i o n  t o   s t e r e o   v i s i o n, "   I J C A I ’ 81   P r oc e e di ng s   of   t he   7t h  I n t e r na t i o nal   J oi nt   C on f e r e nc e   on   A r t i f i c i a l   I n t e l l i ge nc e ,   198 1;   67 4 - 679.     [ 19]   G r a dy ,   “ M ul t i l a be l   R a ndo m W a l ke r   I m a g e   S e g m e nt a t i o n  U s i ng   P r i o r   M o de l s , "   I E E E   C om put e r   So c i e t y   C on f e r e nc e   on  C om put e r   V i s i on   and   P at t e r n  R e c og ni t i on ,   2 005;   763 - 770 .     [ 20]   D .   Z ha ng   a nd  O .   J a v e d  a nd  M .   S ha h ,   “ V i de o   O bj e c t   S e g m e nt a t i o n  T hr o ug h  S pa t i a l l y   A c c ur a t e   a nd  T e m po r a l l y   D e ns e   E x t r a c t i o n  o f   P r i m a r y   O bj e c t   R e g i o ns , "   C om pu t e r   V i s i on   an d  P at t e r n   R e c og ni t i on ,   2 013;   628 - 635 .   [ 21]   J .   S h i   a nd   J .   M a l i k,   “ M o t i o n  S e g m e nt a t i o n  a nd   T r a c ki ng   U s i ng   N o r m a l i z e d   C u t s , "   I C C V ,   19 98;   1 154 - 116 0.   [ 22]   S ut i kno   a nd  H .   W i b a w a   a nd  P .   Y us uf   B ud i a r t o ,   “ C l a s s i f i c a t i o n   of   R o a d  D a m a g e   f r o m   D i g i t a l   I m a g e   U s i ng  B a c kpr o pa g a t i o n   N e u r a l   N e t w o r k , "   I A E S  I n t e r na t i ona l   J our na l   o f   A r t i f i c i a l   I nt e l l i ge nc e ,   2017;   6( 4) ;   159 - 165 .   [ 23]   C .   M i s hr a   a nd  D .   L .   G up t a , “ D e e p  M a c hi n e   L e a r n i ng   a nd  N e ur a l   N e t w o r ks :   A n  O v e r v i e w , "   I A E S  I n t e r na t i ona l   J our nal   o f   A r t i f i c i a l   I n t e l l i ge nc e ,   20 17;   6 ( 2 ) ;   66 - 73 .     [ 24]   M .   L a l a o ui   a nd  A .   E l   A f i a   a nd  R .   C hi he b , “ A   S e l f - T une d  S i m ul a t e d  A nne a l i ng   A l g o r i t hm   us i ng   H i dde n  M a r ko v   M o de l , "   I nt e r n at i on al   J o ur n al   o f   E l e c t r i c al   a nd  C om pu t e r   E n gi ne e r i ng ( I J E C E ) ,   2018;   8( 1) ,   291 - . 298 .                                                     Evaluation Warning : The document was created with Spire.PDF for Python.