TELKOM NIKA Indonesia n  Journal of  Electrical En gineering   Vol.12, No.7, July 201 4, pp . 5645 ~ 56 5 4   DOI: 10.115 9 1 /telkomni ka. v 12i7.585 5          5645     Re cei v ed Fe brua ry 24, 20 13; Re vised  Ma rch 25, 20 14; Accepted  April 12, 201 4  Digital Image Stabilization Based on Improved Scale  Invarian t  Feature Transform      Xiaoran Guo * , Shaohui Cui, Dan Fang   Ordnanc e Eng i neer ing C o ll eg e, Shiji azhu an g 050 00 3, Chin a  *Corres p o ndi n g  author, e-ma i l : vip85 05 22@ 163.com       A b st r a ct   A nove l  di gital  imag e stabi li z a tion a ppro a ch  usin g Harris  a nd Sca l e Invar i ant F eature T r ansfor m   (SIF T )  w a s pre s ented i n  this article. Usin g SIF T  in di gital i m a ge stab ili z a t i on, t oo many feature p o ints a n d   match e s  w e re  extracted,  b u t some of  the m  w e re  not  s o  st abl e. Usi ng t h ese fe ature  po ints a nd  match e s   can n o t only i n creas e the c o mputati o n a l e ffort, but  also enh anc e the  w r ong matchi n g  prob ab ility. W e   prop osed to us e SIF T   to detect featur e point s and inc o rpor ate the Harris  crit erion to se l e ct the most stabl e   feature p o ints  in the vi deo s equ enc e w here imag e motio n  w a s happ en ed du e to veh i cle or p l atfo r m   vibrati on. W i th these feat ur e p o ints, w e  use  gen eral fe ature  descriptor  and  match i ng  alg o r ithm to ac hi ev e   the i m age  stab i l i z a t io n. Exp e ri me nt al  resu lts  show  that th e p r opos ed  al gorit hm ca n n o t o n l y  brin g  dow n th e   prob abi lity of  w r ong  matchi n g  an d g e t  mor e  accur a te   ma tches, but a l so  reduc e the  co mp utatio n b u rd e n   than SIF T  effe ctively.     Ke y w ords : dig i tal i m a ge stabi li z a tio n , SIF T ,   Harris         Copy right  ©  2014 In stitu t e o f  Ad van ced  En g i n eerin g and  Scien ce. All  rig h t s reser ve d .       1. Introduc tion  Video stabili zation tech niq ues h a ve bee n studi e d  for decade s to improve visua l  qualities  of image se q uen ce s captu r ed by digital  video came ras which a r e  hand held o r  mounte d  on  unsta ble pl atform  or ve hicl e, the captu r ed video  ge n e rally lo oks  shaky b e cau s e of un de sire d   came ra motio n s. Un wante d  video vibrations w ould le ad to degrad ed view expe rien ce an d also   greatly affe ct the pe rform ances  of ap plicatio ns li ke video  co di ng, video  su rveillan c e, o b j ect  detectio n , target tra cki ng,  image  naviga t ion and  guid ance. Video  stabili zation i s  be co ming  an   indispen sabl e  techniq ue in  indu strial, m ili tary and co nsumer a ppli c at ions field s .   The video  st abilization sy stem s can b e  cla s si fied i n to three  ma jor types: el ectro n ic  image  stabili zation  (EIS), o p tional im age  stabili zati o n  (OIS),  a nd di gital  imag e st abilization (DI S )   [1]. The EIS stabili ze s the  image  se qu ence by em p l oying motion  sen s o r s, su ch as gyro sco pe  and accel e ro meter, to detect the came ra move me nt for compe n sation. The OIS adopts a prism   assembly whi c h move s op posite the  sh akin g of ca m e ra for  stabili zation [2]. Th e appli c ation s  of  EIS and OIS are rest ricte d  to device, be cau s e  b o th are hardware  d epen dent. DI S is the pro c ess  of removing t he und esi r ed  motion affect s to gene rate  a stable ima ge se que nce by using di gital   image processing   tech nique s with out  any  m e ch ani cal d e vice s  su ch  as gyro scope,  accele rom e te r, or a fluid  pri s m.  DIS system  e s sentially co nsi s ts  of two  u n its: the m o tion   estimation u n i t and the motion com pen sation units.   The motion e s timation unit  estimates th e global moti on paramete r s between ev ery two  con s e c utive f r ame s   of the  input vid eo  seq uen ce s.  With the s e  gl obal m o tion  para m eters, t he  motion  comp ensation u n it then g ene rates th e co mpen sating   motion p a ra meters n eed ed to   comp en sate f o r the  jitter of  a fram e a n d  create s  a  m o re vi sual  sta b le ima ge  se quen ce.  Unli ke  most motio n   estimation te chni que s, in  DIS the  ro bu stne ss  of the  motion e s timation is  critical  asso ciated  with the fact t hat an i m proper e s ti mat e  will yiel d  an a b ru pt jitter in  the vid eo  seq uen ce.   Variou s alg o rithms have b een devel op ed to es timat e  the local  motion vecto r s. Block  matchin g  [3] is the co nvent ional way to detect  the glob al motion vector betwe en two con s e c uti v e   frame s . In this method, e a ch ima ge is divided in to  squa re s, re ctangl es o r  circul ars [1] of a   certai n dime n s ion, an d the n  motion sea r ch i s  exe c ut ed to find the  motion vecto r  for ea ch bl o c k   in cu rrent fra m e. With the s e lo cal  moti on vecto r s, cl usteri ng m e th od [3] is  used  to find the m a in  motion ve cto r  which i s  reco gni zed  a s  the  glob al  motion ve ct or. Be cau s e  of the tedi ous  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 7, July 201 4:  5645 – 56 54   5646 comp utationa l cost of blo ck m a tchi ng  with full  pixel information,  some  sche mes h a ve b een   prop osed to   spe ed  up the  pro c e s s  with only  partial  pixel info rm ation, such a s  rep r e s entat ive  point mat c hin g  sch e me [4],  sel e cte d  a r e a s m a tchi ng  scheme  [5], b i t-plane  matching  schem e  [6]  and gray-cod ed bit-pla ne matchin g  sch e me [7].  These sch e me s can redu ce t he com putati on  compl e xity, but also lo we r the motion e s timati on accu racy. Besi de s block matchi ng method  wi th   full or  partial  pixel info rm ation, opti c al  flow [8] b a sed meth od  h a s  been  p r o posed fo r im age  stabili zation.  In optical flo w  alg o rithm t he con s tr aint  is the first-o r de r ap proxi m ation of Ta ylor  seri es, which  means that the motion s can not be ve ry large. Othe rwi s e, the hig her orde r terms   of Taylor  se ri es  whi c h a r e  igno red,  can  lead to   sig n i f icant in co rre ct estim a tion.  Some featu r e   matchin g  ba sed algo rithm s , such  as p h a se  co rrel a tio n  schem e [9], and edge  p a ttern matchi n g   scheme  [10]  have al so  be en p r o p o s ed   in DIS. T h e s e  sch e me s a r e lack of ad aptation to affine   and pe rspe ctive motions.    The m o re ef fective meth ods for affin e  an d  persp ective m o tio n  e s timation  are lo cal   feature s  ba se d one s. Ha rri s [11]  co rne r   feature s  are extracted  and  tracked in o r der to e s tima te   global motio n  [12]. Scale  invariant fe ature tra n sf o r m (SIFT) [1 3] feature s , con s id ere d  to be   invariant to  i m age  rotatio n  an d  scaling ,  are  bein g   widely u s ed  in  the late st me thods  fo r gl o bal  motion e s tim a tion [14], image mat c hin g  [15] and ima ge re gist ratio n  [16]. Also  many wo rks  are  prop osed to  improve the  distinctivene ss of SI FT descri p tor, such a s  pri n cipal com pon ent  analysi s  (PCA)-SIFT [17] whi c h wa s le ss di stin ctive than the SIFT  descripto r proved by [18],  and   spe ede d up  robu st feature s  (S URF)  [19]  whi c h  is fast  in matching  a nd  suf f i cie n t l y  dist in ct iv e,  b u t  wea k e r  than  SIFT in the invariant of scalin g and ro tation. Such above-mentio ned app ro aches  mainly focu s on the development of d e scripto r s,  but in this paper, we  care  more abo ut the   extraction of  the most stable  feature points,  which  can not only   bring down t he probability of  wro ng m a tchi ng an d get m o re  accu rate  matche s,  b u t also  effectively redu ce  th e co mputatio nal   effort. By carefully reviewi ng the su rve y  on feat ure point detecto rs [20], we n o te that Harris  corne r  could  provide  sta b le dete c tion  perfo rman ce with hig h   repe atability and lo cali zati on  accuracy un der vario u s  distortio n s a nd geom et ri c tran sform.  Therefo r e, we propo se  to  inco rpo r ate t he  Harri s  cri t erion i n  SIF T  to se le ct the mo st  sta b le featu r e  p o ints fo r im a g e   stabili zation.  With these most sta b le  featur e p o int s , we u s e g eneral feature descriptor  and  matchin g  al g o rithm to  ge nerate  match e s, an d  u s e  those  mat c hes to  calcul ate geo metri c al  transfo rm p a rameters. Fin a lly, we tran sfor m  one im age u s ing th e geom etri ca l transfo rmati o n   matrix to align with the oth e r imag e, and  accompli sh i m age comp e n satio n .      2. Robus t Lo cal Feature  Points Extr a c tion   Local feature s , su ch as  co rne r s, blob s,  and re gion s, have been  wi dely used fo r object  detectio n , re cog n ition, an d retrieval pu rpo s e s  in  co mputer visio n .  The intrinsi c advantag es of  these lo cal fe ature s  are their invaria n ce  under g eom etric tra n sfo r ms. A comp rehen sive revi ew of  the state - of-t he-a r t lo cal f eature s   ca n  be fou nd  in  [18]. Among   variou s lo cal   feature  dete c tors  and de script ors,   SIFT wa s sho w n   to be relative ly  optimal  con s i derin g the  trade-off bet ween  robu stne ss, distin ctivene ss,  an d efficie n cy,  an d  Ha rris corn er co uld p r ovide   stable d e tecti o n   perfo rman ce  with high  re peatability an d locali zatio n  accuracy u nder va riou s distortio n s  and   geomet ric tra n sform.  The ori g inal  SIFT algorith m  con s ist s  of the followin g  four maj o r ste p s:   (1) S c ale - spa c e extrem e d e tection   (2) A c curate f eature p o ints  locali zation   (3) O r ientatio n assignm ent   (4) F eature p o ints de script or  Whe r e  ste p s  1 an d  2 a r e  the featu r e  de tection  and   steps  3  and  4  are the  de scription  and ge neratio n of the feature point s.  Our  m e thod u s e s   the step 1,  step  3 and step  4 of  the  origin al SIFT  algorith m , but  in step  2, when the  potential feature poi nts ha ve all  found, and the point s of the edg e and the lo wer  contrast  point s  were elimi n ated. Yet there are  st ill too many feature points,  and some  of them   are  not so  stable, if ad opti ng all th e feat ure  point s to  execute th e f eature  matchi ng, not o n ly the   computational effort  will be tr emendous,  but al so t he wrong matchi ng  probab ility  will be high. To  further i dentif y the most  st able f eatu r e  points,  we in corpo r ate the  Ha rri s  criteri on to  sele ct the   most sta b le  SIFT feature  points.  Th e u nderlyin g re a s on i s  that such a  crite r io n help s  keep  the   most stable  l o cal pattern s  with  hig her gradi ents di st ribution  but reject s the fe ature p o ints  with   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Digital Im age Stabilization  Based o n  Impro v ed S c al e  Invari ant Feat ure T r an sform  (Xiaoran G uo)  5647 lowe r g r adi e n t distri butio n. Also, the  Ha rri s-ba se d criterio n i s  self-ada ptive and  can  yield   relatively stab le detectio n  p e rform a n c e.   The ste p s of the pro p o s ed  algorith m  are:   (1) S c ale - spa c e extrem e d e tection   The first sta g e  of comput ation sea r che s   over all  scale s  an d ima ge l o catio n s to  find lo cal   extrema. It is  impleme n ted  efficiently by usin g  a seri e s  of differe nce-of-Gau ssia n (DOG ) ima ges  in the scale  spa c e   to identify poten tial feature p o ints  that are invariant to scale an d  orientatio n.  The im age  scale  spa c e  is  expre s sed  as a fu nction   ) , , ( y x L , that is ge ne rat ed from th e  convol ution o f  a serie s  of  Gau ssi an kernel functio n s  ) , , ( y x G  with con s e c utively incre m ental  scale s , with a n  input image   ) , ( y x I :    ) , ( ) , , ( ) , , ( y x I y x G y x L                                                                                 (1)    Whe r e   denote the convol u t ion operator,  and the Gau ssi an fun c tion   ) , , ( y x G :    2 2 2 2 / ) ( 2 2 1 ) , , (  y x e y x G                                                                                   (2)    The scal e sp ace  ) , , ( y x D  is set u p  from the di fference of two ne arby  scale s  by a  constant mult iplicative fact or  k .    ) , ( )) , , ( ) , , ( ( ) , , ( ) , , ( ) , , ( y x I y x G k y x G y x L k y x L y x D                                                            (3)    2) Accu rate feature p o ints  loca li zation with  Harris crit erion  Whe n  the po tential feature points h a ve all  found, to further id e n tify the more stable   feature poi nts, we will eli m inate the unstabl e poi nt s, such as the point s of the edge and the  lowe r contrast points. Only  the  stabl e fe ature p o ints  remain. Acco rding to Taylo r  expan sio n , let  the derivative  of  ) ( x D  equal zero after an off s et  x ˆ  set can  be found. T h i s   x ˆ  can take a  pixe l  locatio n  with   true lo cal  extreme valu e, then sub s titute  x ˆ  into the T a ylor exp a n s ion.  If a value of  | ) x ˆ D( |  is less than  03 . 0 ,  we will  say the point  has low cont rast. The  ) ( x D  is co mput ed belo w .     x x D x x x D D x D 2 2 2 1 ) ( T T                                                                      (4)    x D x D x 2 1 2 ˆ                                                                                              (5)    | ˆ 2 1 | ) ˆ ( x x D D x D T                                                                                        (6)    After eliminat ing the point s  with low cont rast, we  will cancel the point s of t he edge  perh a p s . Here we use a  2 2  He ssi an  mat r ix   E  which ena bles u s  to co mpute the scale an d   locatio n  of the feature poi n t. The matrix is given by:    yy xy xy xx D D D D E                                                                                              (7)    Whe r e  xx D  is the second de riv a tive of t he image in the  x-dire ction, a nd  xy D  is the first  derivative of the image in the x-dire ction and y-di rectio n re sp e c tively,  yy D  is the se co nd  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 7, July 201 4:  5645 – 56 54   5648 derivative of t he ima ge i n  t he y-di re ction .  Then,  E  is do ne in  the  de compo s ition  of eige nvalue s  to get the two eigenvalue s:    and  .  We u s e the ratio of the eigenvalue s a s  follows:      2 2 ) 1 ( ) ( ) ( ) ( E E Det Tr                                                                             (8)                                                                                                         (9)    The followi ng  inequality must be satisfi ed, if not, we say that this point is pro b ably on   the edge, an d  it can be eli m inated like this:     2 ) 1 ( ) ( ) ( E E Det Tr                                                                                    (10)    So far,  we  ge t the a  set of  SIFT point s  ) , , ( n n n y x P , w h er e  n x  is the   hori z ontal  o r d i nate,  n y  is the ve rtical ordinate,  and  n  is the   scale p a ram e ters of the  SIFT feature  point  n .  Suppo se tha t  there are t o tal  N  feature  points, so  N n ,... 3 , 2 , 1 . Then, we a dd the Ha rri s  crit e r ion  t o  s e lect  t h e mo st  st a b le S I F T  f eat ur e p o i n ts. The  Harris  criterio n i s  b a sed o n  t he  autocorrelatio n  matrix, whi c h rep r e s ent s the g r adi e n t distrib u tion  within a l o cal regi on of t he  sele cted  poin t. We a dopt t he  n x ,  n y ,  n  to cal c ulate the  Ha rris respon se   ) , ( n n y x R n , where  n   is the  stand a r d deviatio n   of the Gau ssian kern el fu nction  as th e  weig hted  windo w u s ed to   comp ute the  Harri s  auto c o rrel a tion mat r i x   M , which  re prese n ts the  gradi ent di strib u tion withi n  a   local  regi on  of the sele ct ed point. Th e Gau s sian  kernel  wind o w  in this  pa per i s   3 3 . The   autocorrelatio n  matrix  M  of at feature point  ) , , ( n n n y x P  is  r e pr es e n t ed  a s :    ) , ( ) , ( 2 2 ) , ( n n y x W y x y y x y x x I I I I I I y x M                                                                      (11)    ) , ( n n y x W  is th e G a u s sian  kern el  windo w  with th e  ) , ( n n y x  as th e  ce nter to  dete r mine   the accum u la ted regi on, a nd  ) , ( y x  is the Ga ussian  ke rnel  function of t he wei ghted  wind ow,  x I  and   y I  are  the  image  g r adi ents i n  x-dire ction  and  y-d i rectio n. So  2 x I  is  th e pr o d u c t o f  the  image  gradie n ts in  x-di rection. We  u s e  the G a u ssi a n  kern el fun c tion  ) , ( y x  as th e  weig hted  wind ow to m a ke the  matrix  isotro pi c. If b o th eige nvalu e s of m a trix  M ,  1  and  2  are  suffi ciently  large  po sitive  value s , this  point i s  a  co rne r  p o int. Harri s  pro p o s e d  a fo rmula  to evaluate  th e  corne r  point s instea d of co mputing the two eig envalu e s a s :    ) ( ) det( ) ( 2 2 1 2 1 M trace M R                                                         (12)    Whe r e   is a coeffici ent wit h  value 0.04-0.06. We  set 0.06 as its d e fault value in this  pape r.  ) det( M  is th e dete r mina n t  of matrix  M , and  ) ( M trace  is th e trace  of matrix   M . We  cal c ulate th e   ) , ( n n y x R n  of ea ch fea t ure p o int  ) , , ( n n n y x P , and calculate  the mea n  val ue of  them. Finally, we set the m ean value a s   the thre shold  to sele ct robu st SIFT feature points:     N n n n y x R N Threhold n 1 ) , ( 1                                                                         (13)    If the  ) , ( n n y x R n  of feature poi nt is greate r  than  Threhold , we keep this  feature poi nt  and ta ke  it a s  a mo st  stabl e feature p o i n t, otherwise  reje ct this fea t ure p o int.  With this th re sh old,  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Digital Im age Stabilization  Based o n  Impro v ed S c al e  Invari ant Feat ure T r an sform  (Xiaoran G uo)  5649 we ca n re serve  the  m o st stable   f eatu r e  point s  with  h i gher g r adi en ts di strib u tion , and  rej e ct t he  feature  point s with  lower g r adient  dist rib u tion, an d  th en we co uld  extract stabl e   feature  p o int   in   image s  unde r g eomet ric transfo rm s eve n  un de r the   a ttack of  blurring.  Du e to t h is th re sh old  is  based on  Harri s alg o rith m, it is self-ada ptiv e an d can yield  relatively stable dete c tion  perfo rman ce.   3) Ori entation  Assign ment   One o r  mo re  orientatio ns  are a s sign ed  to each fe ature p o int location ba sed  on local   image g r a d ie nt dire ction s . All future o peratio ns  are  perfo rmed  o n  image  dat a that ha s b een  transfo rme d  relative to the assig ned o r i entati on, scal e, and locati on fo r each feature, there b y  providin g invarian ce to the s e tran sfo r ma tions.   After finding  the featu r e  points, th e  fo llowin g   step will  defin e the ma gni tude an d  orientatio n fo r ea ch featu r e point in  order to  u s e i m age m a tchi ng. The o r ie ntation of ea ch   feature  point  is d e termi n e d  by the  pea k of th e o r ie ntation hi stog ram fo rme d   by the g r adi ent  orientatio ns  within it s nei ghbo rho od.  After fi nding  the majo r o r i entation fo r  an ima ge fe ature   point, whe n  doing the im age mat c hin g  again, we can  rotate to  the same o r ientation in t w o   image s, and thus a c hieve rotation-inva ri ance. Here  we are u s ing the distri butio n of the gradi ent  dire ction  fo r  feature point s taken as a  co nsi s tent  o r ien t ation to ea ch  feature  point . Therefo r e,  we  will compute   the gradient  magnitud e  a nd t he o r ie ntation for  ea ch imag e sam p le  ) , ( y x L . The   comp utation  of the gradie n t  magnitude a nd the  orie nta t ion in pixels  are given a s   belo w .    2 2 )) 1 , ( ) 1 , ( ( )) , 1 ( ) , 1 ( ( ) , ( y x L y x L y x L y x L y x m                                       (14)    ))) , 1 ( ) , 1 ( /( )) 1 , ( ) 1 , ( (( tan ) , ( 1 y x L y x L y x L y x L y x                                     (15)    After the g r a d ient di re ctio ns  of all  pixe ls  within a re gion aro und  the  featu r e p o int  a r e   comp uted, we cal c ul ate th e dire ction  of the most  p o i n ts supp ortin g  the pri m ary  dire ction. Th e  weig ht of each poi nt adja c ent to the central pixe l s   is de cide d u s ing the p r o d u ct of Gau ssian   distrib u tion s and gradie n t magnitude o f  the point,  whe r e Ga ussian distri butio n is a setting  at  5 . 0 .  4) Featu r e Po ints De scripto r   The local ima ge gra d ient s are mea s u r e d  at  the selected scale in the regi on aro und ea ch  feature p o int. These are transfo rme d  in to a rep r e s e n tation that a llows for si gn ificant levels  of  local  shap e  distortio n  a n d  chan ge i n  illuminat io n. He re  we a dopte  an  ap proa ch  which is  basi c ally ba sed on the ori entat ion histo g ram. The  computati on a nd de scriptio n of the image  gradi ent is d one by usi n g  the feature  poi nts a nd a d jacent pixel s , we em plo y  a  16 16  local  neigh borhoo d  blo ck  around  the featu r e  p o ints, the n  di vide it up i n to   4 4  su b-blo c ks  again, a nd  define the ei ght dire ction s ,  therefo r e, we treat the   128 8 4 4  dimensio na l vector as t he  feature point s  descriptor.  The feature  vector  i s  then normali zed to decrease the illuminat ion  alteration effec t s .       3. Featur e M a tching a nd  Image Comp ensa te   Once the  mo st sta b le fe ature  point s h a v e bee n d e te cted i n  the  im age s, the  nex t step i s   to matc h them. In this  paper, f eatu r e p o ints a r e m a tche d by con s tructing  KD-t ree with  be st-bin- first se arch,  the advantag e of KD-tre e  is red u ci ng  the numb e r  of feature th at need s to be   sea r ched. Th e feature d e scripto r s of the refere n c e f r ame a r e  clu s tere d by bui lding KD-tre e .  A  feature i s  th en rand omly sel e cte d  to  be the  pa rtition n ode. Ea ch fe ature  e x tracted f r om  the   curre n t fram e traverse s t he built KD-t ree to fi nd it s corre s po nd ing point  with be st-bin -first  sea r ch. The  pair of matchi ng feature s  in  two di fferent  image s is call ed a co rresp onde nce. Wh e n   all co rresp o n den ce s have  been fou n d ,  the tr ansfo rmation m a trix can be  computed  usi n g   rand om  sa m p le a nd  co nsensus (RANSAC). In t h is  study, th e f o cu s  will  be   on  stabili zati on of  aerial i m age s whe r e the  di stan ce of the  came ra to t he sce ne i s   much l a rger t han  cha nge s in   scene  depth,  or if depth  va riation i s  la rg e, the ca mera  motion is sm all eno ugh  so  that the fram es  being  re gist ered  have   negligibl e  lo cal  geom etri c diffe ren c e.  We  will   use  proje c tive   transfo rmatio n to registe r   the image fra m es. As sum e  that the number of mismatche s  can  be   redu ce d by u s ing  our im proved ap pro a c h a nd KD-tr ee with b e st -bin-first search, small a m o unt  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 7, July 201 4:  5645 – 56 54   5650 of mism atch e s   still o c cur,  and thi s  m a y  lead to  un reli able  pre d ictio n  of m o tion e s timation. T h us,  a furthe r  ch e c k of mat c hin g  erro rs is a  signifi c ant p a r t of the  algo rithm. We  use  the  well  kno w n  RANSAC al g o rithm for th e purp o se of both elimina t ion the mismatche s  an d  estimation o f  th e   para m eters  o f  the proje c tive tran sform   model . Ba se d on th e  corresp ond en ce s, RANSAC can   iteratively co mpute the  p a ram e ters of  the motio n   model  by det ecting  the inl i ers an d o u tliers  among  the s e  matching  pa irs. T r a d ition a lly, t he ge o m etric tra n sf ormatio n  b e twee n two im age s  can b e  de scri bed by a hom ogra phy whi c h is a 3D mo del.   The procedu re to calculate  the homog ra phy can b e  e x presse d as f o llows:   (1)  We b egin  with a sim p l e  liner al gorit hm for dete r mining h o mo grap hy  H  by giving a  set of fo ur  point  corre s pond en ce s,  i i P P , whi c h are not three  points collinear. T h e  transfo rmatio n is given by equatio n  i i HP P .  (2)  Com pute  a simila rity transfo rmati on  T  for the  points in th e  refere nce i m age,  con s i s ting of a transl a tion  and scali ng, that take s poi nts  i P  to a new  set of points  i P ~ , the points  are tran slate d  and  scale d   so t hat the  ce ntroid of th e  points  i P ~  is at t he coordinate  origin  T ) 0 , 0 ( ,  and thei r average di stan ce  from the ori g i n  is equ al to  2 . So coo r dinat es  i P  in refere n c e ima ge  are repla c ed  by  i i TP P ~ . Compu t e a similar tran sform a tion   T  for the points in the cu rre nt  image, tra n sf ormin g  poi nts  i P  to  i P ~ , that is  coo r din a tes  i P  in cu rrent im age a r e  re pla c ed  b y   i i P T P ~ .  T  and  T  are  3 3  matrixes. Su bstituting in the equ ation  i i HP P , we de riv e  t h e   equatio n  i i P HT T P ~ ~ 1 . This rel a tion im plies that  1 ~ HT T H  is  the tran sform a tion matrix f o r  the poi nt correspon den ce s  i i P P ~ ~ . Note th at the e quation   i i P H P ~ ~ ~  involves ho mogen eo u s   v e ct or s,  t h u s  t he 3-v e ct o r s  i P ~  and  i P H ~ ~  are  n o t equal, th e y  have the  same di re ction  but ma y  differ in m a g n itude by  a n onzero  scal e  factor.  T he e quation  may  be exp r e s sed  in term s  of the  vector cro s s prod uct a s   0 ~ ~ ~ i i P H P . This form  will  enable a si mple linea r solution for  H ~  to  be  derived. If the j-th row of th e matrix  H ~  is denoted by  T ~ j H , th en we may write:    i i i i P H P H P H P H ~ ~ ~ ~ ~ ~ ~ ~ T 3 T 2 T 1                                                                                             (16)    Writing  T ) ~ , ~ , ~ ( ~ i i i i y x P , the cross p r od uct  may then be given explicitl y  as:    i i i i i i i i i i i i i i y x x y P H P H P H P H P H P H P H P ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ T 1 T 2 T 3 T 1 T 2 T 3                                                                           (17)    Since  j i i j H P P H ~ ~ ~ ~ T T , for 3 , 2 , 1 j , this give s a  set  of three e q u a tions i n  the  entrie s  of  H ~ ,  whic h may be written in the form:    0 H H H 0 P P P 0 P P P 0 3 2 1 T ' T ' T ' T ' T ' T ' ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ T i i i i i i T i i i i i i T x y x y                                                          (18)    That is,   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Digital Im age Stabilization  Based o n  Impro v ed S c al e  Invari ant Feat ure T r an sform  (Xiaoran G uo)  5651 0 8 7 6 5 4 3 2 1 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 0 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 0 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 0 0 h h h h h h h h h x y x x x y y y x y x y x x x y x y y y x y y x i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i      (19 )     These equ ations have the  form  0 h A ~ i , where  i A  is a  9 3  matrix, and  h ~  is a 9- vector ma de  up of the entri es of the matrix  H ~ , with  i h ~  the i-th element of  h ~ .     T 3 2 1 ~ ~ ~ ~ H H H h , 8 7 6 5 4 3 2 1 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ h h h h h h h h h H                                                        (20)    Although the r e are th ree  e quation s  in (18),  only two  of them are  linearly in dep ende nt  (sin ce the third row is o b tai ned,  up to scale, from the sum of  i x ~  times the first row and  i y ~  times   the second ).  Each  poi nt correspon den ce give s  ri se t o  two  ind epe ndent  equ atio ns i n  th e e n tries  of  H ~ . Given a set of four  su ch p o int co rres p ond en ce s, we obtain  a  set of equ ations  0 h A ~ ,  whe r e  A  is the  matrix of eq uation  coeffi cients b u ilt fro m  the matrix  rows  i A  cont rib u ted from   each co rresp onde nce, an d  h ~  is the vector of un kn own e n trie s of  H ~ . Executing the SVD   (Singul ar Val ue  De comp o s ition) of  A , the unit  sing ul ar ve ctor correspon ding  to the  small e st  sing ular valu e is the sol u tion  h ~ , and the matrix  H ~  is determin ed  from  h ~ . Then  we ca n  cal c ulate h o m ography  H  by  1 ~ HT T H .  (3)  We  cal c ulate the e r ror of a  corresp ond en ce  from hom og raphy  H  using  the   s y mmetric  trans f er  erro r, that is  2 2 1 - 2 ) ( ) ( i i i i transfer d d d HP P P H P ， ， . If the  2 transfer d  is less than  the given th reshold  valu e, then  confi r ming th e  correspon den ce inlie rs, oth e rwi s e  outlie rs.  Rep eat fo r a   numbe r  of sa mples,  and  reco rd  t he l a rgest  num ber  of inliers. Fi n a lly, re-estim ate   R H  from  all  co rrespon den ce s  cla ssifie d   as i n lie rs,  an d u s ing  the   final ho mog r aphy  R H  to  impleme n t image compe n sate.      4. Results a nd Analy s is  To test the  stabilization abi lity of the pro posed alg o rit h m and  com pare it  with traditional   SIFT algorith m , some ima ge pairs with  different ch an ges a r e u s ed.        (a) T he refe re nce ima g e     (b) T he curre n t image     Figure 1. Input Images (a) Refere nce Image an d (b ) Current Imag e  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 7, July 201 4:  5645 – 56 54   5652 Figure 1 i s  the inp u t ima ges,  with sca ling an d rotat i onal vari atio ns. Figu re  1(a) is th e  referen c e im age, an d Fig u re  1(b )  i s  th e cu rrent im a ge. As  we  ca n se e, Figu re  1(b )  takes  great  scaling a nd rotational cha nge compa r e d  to Figure 1 ( a).                            Figure 2 sho w s the mat c h i ng points fro m  SI FT algori t hm and our  algorith m . As we can   see, SIFT ge nerate s  too many  feature  points and  matche s. At  the same tim e , our algo rithm  gene rate s le ss featu r e  p o ints  and  m a tche s  but  with hi gh  co rre ctne ss, which  ma ke s  the   sub s e que nt calcul ation of t r an sform  very promi s ing.  This allows us  to  gain better  accuracy  t han  SIFT.       (a) SIFT   ap proa ch     (b) Propo se d approa ch     Figure 2. Matchin g  Re sult s from (a) SIF T  and (b ) the  Propo se d Approa ch       Figure 3 ( a )   shows th e  co mpen sated  i m age  usi ng  SIFT, and  Fi gure  3 ( b)  sh ows the  comp en sated  image usi ng  our alg o rithm.         (a) SIFT   ap proa ch     (b) Propo se d approa ch     Figure 3. Stabilizatio n Images fro m  (a ) SIFT and (b ) the Propo se d  Approa ch       We al so test  the stabilization ability  of  the two  algorithm s usi ng the im ages  with  illumination  chang es, viewpoint ch ang e s , and blu r .   Nume ri cal ev aluation  of the qu ality of the  imag e  stabili zation i s  fulfilled u s i ng pe ak  sign al-to - noi se ratio  (PS N R) as  e rro r  measure. PSNR bet wee n  frame   t  and  frame   1 t  is  defined a s :   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Digital Im age Stabilization  Based o n  Impro v ed S c al e  Invari ant Feat ure T r an sform  (Xiaoran G uo)  5653   M y N x t t y x I y x I MN t MSE 11 2 1 )] , ( ) , ( [ 1 ) (                                                           (21)    ) ( log 10 ) ( 2 10 t MSE I t PSNR MAX                                                                          (22)    W h er e  ) ( t MSE  is t he m ean -sq uare  e rro r  b e twee n fra m es,  MAX I  is the  maximum   intensity valu e of a pixel,  and  M  and  N  are th e fram e dimen s io ns.  PSNR  measure s   the   simila rity betwee n  two  im age s, hen ce,  it is u s eful  to  evaluate h o w much a im ag e is  stabili ze d  by  the algorith m  by simply evaluating t he si milarity of the two image s.   In order to prove the stabilization effe ct of the algorithm, we  calcul ated the  PSNR   betwe en ea ch frame of th e su ccessive  50 frame s  u n stabl e video  sequ en ce s, the expe rime ntal  results  are  sh own i n  Fig u re  4. The  cu rve  at the botto m rep r e s e n t the  PSNR  of the ori g inal n on- comp en sated  video sequ e n ce s, the mid d le one is the   PSNR  of compen sated video se quen ce s  usin g SIFT  method,  and   the ab ove o n e  is the  PSNR   of compen sate d video seq uen ce s  u s in g  the prop osed  approa ch.         Figure 4. Experime n tal Re sults of PSNR      At the same ti me, we u s e t he execution  time to  evalu a te the efficie n cy of the alg o rithm s .  In Table  1,  executio n time comp ari s ons amo ng  variou s vari a t ions  betwe e n  SIFT an d  our  approa ch a r e  sho w n. As  can be  see n  from Figu re 4  and Ta ble 1,  the  PSNR  of our a p proa ch i s   a little bigge r  than SIFT un der th e vari o u s va riation s ,  and th e exe c ution time of  our  app roa c h  is  much le ss than SIFT, so o u r app ro ach outperfo rm s the SIFT approach.      Table 1. Execution Time Compa r ison s  variation  execution time of  SIFT   execution time of  our app roach   rotations and scale   6203.7ms   3394.9ms   illumination  2385.6ms   171 1.0ms   view point  4153.5ms   2895.6ms   blur 3716.0ms   2868.1ms       5. Conclusio n   In con c lu sion , we pro p o s e a novel ro bust lo cal fe ature p o int e x traction a p p r oa ch in  image sta b ili zation. First, we use SIFT algorithm  de tect the feature poi nt of the image, then  adopt Harris  crite r ion to select the mo st rob u st fea t ure point s. The Harris  Threhold  is self - adaptive  and  ca n yield  rel a tively stable  dete c tion p e r forma n ce. E x perime n tal result s  sho w  t he  prop osed scheme yield s  better perfo rman ce s tha n  SIFT, it h a s a little better stabili zation  accuracy, an d save s a lot of computatio n burd en.     0 5 10 15 20 25 30 35 40 45 50 11 12 13 14 15 16 17 18 19 F r am es PS N R ( d B) Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 7, July 201 4:  5645 – 56 54   5654 Referen ces   [1]    Xu  LD, Li n  XG. Digital im ag e  stabiliz atio n Based o n  Circ u l a r Block Matc hin g .  IEEE Transactions on  Cons u m er Ele c tronics . 200 6; 52: 566- 57 4.  [2]    Sato K. Contr o l tech niq ues  for optica l  ima ge stab iliz in g  s y stem.  IEEE  Transactions on Consum er   Electron ics.  19 93; 39: 46 1-46 6.  [3]    Vell a F ,  Castor ina A, M ancus o M. Dig ital  im age sta b i lizati o n  b y  ada ptive block  m o tion  v e ctors filteri ng.   IEEE Transactions on Cons um er Electronic . 2002; 4 8 : 796- 800.   [4]    Uomori K. Aut o matic ima ge  stabiliz in g s y stem b y  full- dig i tal sig n a l  proc e ssing.  IEEE Transactions o n   Cons u m er Ele c tronics . 199 0; 36: 510- 51 9.   [5]    Enge lsber g A, Schmidt G. A compar ative rev i e w  of  di gita l i m age stab ilis in g alg o rithms fo r mobil e  vide o   communications.  IEEE  Transactions on Cons umer Electronics.  1999; 45: 5 92-5 97.   [6]    Ko SJ, L ee S H , Le e KH. D i g ital  ima ge st abil i zi ng  alg o ri thms bas ed  o n  bit-p l a ne m a tching.  IEEE   T r ansactio n s o n  Cons u m er El ectronics.  19 98 ; 44: 617-6 22.   [7]    Ko SJ, Lee SH , Jeon SW . Fa st digital im ag e  stabiliz er bas e d  on gra y -c od e d  bit-pl an e matchin g .  IEEE  T r ansactio n s o n  Cons u m er El ectronics.  19 99 ; 45: 598-6 03.   [8]    Cha ng J Y , Hu   W F , Cheng  M H . Di gital  ima g e  trans lati on  a nd r o tatio n  mot i on  stabi liz atio n us ing  o p tica l   fl o w  te ch ni qu e .  IEEE Transactions on Consum er Electronic s.  2002; 48: 10 8-11 5.  [9]    Erturk S. Digita l  imag e stab iliz ation  w i th su b-i m age  phas e c o rrelati on  bas e d  gl oba l moti o n  estimati on,   IEEE Transactions on Cons um er Electronic s.  2003; 49: 13 20-1 325.    [10]    Paik JK, Park   YC, Kim DW .  An a daptiv e m o tion  dec isio n  s y stem for  di gi tal ima ge st abi l i zer b a se d o n   edg e pattern m a tchin g .  IEEE  Transactions on Cons um er Electronics . 19 92 ; 38: 607-6 16.   [11]    Harris C, Step hens M.  A co mb in ed corn er  and e dge  det ection.  Proc. 4 t h Alve y  V i sio n  Confer enc e.  198 8; 189- 192.   [12]    Z hu JJ, Guo BL. Electronic  image sta b ili zation s y stem  based  on gl oba l feature tr ackin g .  IEEE   T r ansactio n s o n  Cons u m er El ectronics . 20 08 ; 19: 228-2 33.   [13]    Lo w e  DG. Di stinctive Imag e F eat ures fr om Scal e-Inva riant Ke y P o i n ts.  Internatio nal J ourn a l  of   Co mp uter Visi on.  200 4; 60: 9 1 -11 0 .  [14]    Yang J L , Scho nfeld D, Mo ha m ed M. Rob u s t  Video Stab iliz ation B a sed  o n  Particle Filt e r   T r acking of  Projecte d C a m e ra Moti on . IE EE T r ansacti o n s o n  Circ u its  and  Syste m s for Vid eo T e ch nol ogy . 20 09 ;  19: 945- 95 4.  [15]    Can Su n, Jin-g e  W ang, Z a ix in  Liu, Junmin L i . W e ighted Mult i-Scale Imag e Matchin g  Base d on Harris- SIFT  Descriptor.  T E LKOMNIKA Indon esia n  Journa l of Electrical En gin e e rin g . 201 3; 11(10): 59 65- 597 2.  [16]    Quan Su n, Jia n xun Z h an g.  Parall el  Rese arc h  an d Impl eme n tation  of SAR  Image R egistr a tion B a se d   on Optimiz ed  SIFT .  T E LKOMNIKA Indo ne sian J our nal  of  Electrica l  En g i ne erin g . 20 14;  12(2):  112 5- 113 1.  [17]    Yan K, Sukth ankar  R.  Pca-sift: A m o re  distinctive repres entation for local image descriptors . In  Proceedings of  the IEEE Com puter  Soc i et y   Confer ence on Computer  Vision and P a tte rn Recognition.   200 4; 506- 513.   [18]    Mikola jcz y k K.  A p e rforma nc e ev alu a tio n   o f  loca l  descri p tors . Journ a l   of the  Ch ines e Institute  of  Engi neers . 2 0 0 5 ; 27: 161 5-16 30.   [19]   Ba y   H.  Surf: Spee de d up robust features.  Computer Vis i on a nd Image  Understa ndi n g . 2008; 11 0:   161 5-16 30.   [20]    T u y t el aars T .   Loca l  invar i ant  feature detec tors: A surve y .  F oundatio ns  and T r ends i n  Co mp uter   Graphics a nd  Visio n .  200 8; 3: 177-20 8.    Evaluation Warning : The document was created with Spire.PDF for Python.