TELKOM NIKA , Vol. 11, No. 2, Februa ry 2013, pp. 761~773   ISSN: 2302-4 046           761     Re cei v ed Au gust 10, 20 12 ; Revi sed  De cem ber 2 9 , 2012; Accepte d  Jan uary 13,  2013   A Quick Image Registration Algorithm Based on  Delaunay Triangulation       Yongmei Zhang* 1,2 , Li M a 1,2 , Rui Zhang 1,2  1 School of Infor m ation En gi ne erin g, North Ch ina U n ivers i t y   of  T e chnol og y,  Beiji ng, Chi na,  1001 44   2 Colle ge of Info rmation a nd C o mmunic a tio n  Engi neer in g,  North Univ ersit y   of Chin a, T a iyu an, Chi na,  030 05 1   *Corres p o ndi n g  author, e-ma i l : zhang ym @n cut.edu.cn        A b st r a ct    T he traditi ona l imag e match i ng a l gor ith m s  adopt  more c o mpl e x strateg i es w hen de al i ng w i th  mis m atch cau s ed by a l o t of noise. In th is pap er,  a si mp le, intu itive  and effective  noise  proces si n g   alg o rith m  is pr opos ed  bas ed  on D e l a u nay tr ian gul atio n i n   c o mputati o n a l g e o m etry.  T h e  alg o rith m extra c ts  feature  po ints  usin g SIF T  method,  re sp ecti vely  establ ish e s  De lau nay  tr i ang ulati o n   in  mu lti-spectr al an d   panc hro m atic i m a ges, an d re mov e s the f eat ure po ints that  three po ints ar e coll ine a r an d  four poi nts are  on   circle by  Del a u nay tria ngu lati on, obta i ns th e  regi strati on i m ages thr o u gh t he corr espo nd ence  betw een  th e   Dela un ay trian gul ations. T h e effect of image  regist rati on is  eval uated  by  obj ective  meth od. In the i m a g e   match i n g , Del aun ay trian g u l atio n is intro duce d .  T he establ ish m e n t of Delau nay  triangu lati on  i s   ind epe nd ent of  the selecti on  of initia l val ues . In  gener al, a  uni que  Del a u n a y triang ul ation  can be  got w h e n   a featur e  poi nt set is  giv en, a nd  it  can  pr ovi de th e acc u rac y  of the  al gor ithm. T h e  alg o rit h m is s i mpl e   a n d   clear for c onve r ting a  lot of  mi smatch  no ise t o  the o per ation  of Del a u nay tr ian gul atio n. Experi m e n t resu lt s   show  the alg o r ithm c an ke e p  the go od rot a tion fe at ure a nd transl a tio n  invari anc e in  SIF T  method,  the   nu mb er of extr action f eature   poi nts  has  be e n  sig n ifica n tly  reduc ed  in th e  alg o rith m c o mpare d  w i th SIF T   meth od, r egistr a tion  spe e d  an d acc u racy  are  better th an th e reg i stratio n  a l gorit hm b a sed  on c onv entio n a l   SIF T  method.       Ke y w ords :  Image re gistratio n , Dela un ay triang ulati on, Mu lti-spectral i m ag e, Panchro m ati c  ima g e      Copy right  ©  2013 Un ive r sita s Ah mad  Dah l an . All rig h t s r ese rved .       1. Introduc tion  Image re gistration is an i m porta nt ste p  in the app lication s  of image fusi on,  target  recognitio n , chang e det ecti on, imag e  re gistratio n  i s  t he n e cessa r y preli m ina r y  work to  imp r ove   the a c cura cy  and validity of  the ab ove p r oblem s [1 -4]. Image  regi stration me an s  determi ning t he  transfo rmatio n para m eters between im a ges a c cordin g  to the similarity measure  so that the two   or m o re  ima g e s f r om  different sen s ors,  angle s , di fferent  time with the  same sce ne  tra n sfo r m to  the same  coo r dinate  syste m  and obtain  the best mat c h in pixel layer [5,6].  Image re gist ration involve s  a lot of techn o logy such as  com p le x feature extractio n ,  optimizatio n algorith m s,  i m age se gme n tation,  patte rn  recognitio n  and  matchi ng, but it la cks  of  system atic th eoreti c al gui dan ce in ma ny ways. Th erefo r e, it is the develop ment dire ctio n to   improve the  automation, registra tion a c curacy a nd speed of the  registration al gorithm s [7-9 ]. In   respon se to the above difficultie s, this paper p r e s ent s a regi stratio n  algorithm  suitable for m u lti- spe c tral a nd  pan chromati c images to im prove regi stra tion accuracy  and sp eed.       2. Fea t ure   Extrac tion o f  Multi - Spec tral an d Pa nchroma t ic  Images Thr ough Tr aditi onal  SIFT Method   Remote  se n s ing im age registration i s  the  best m a tchin g  process for two  or mo re  image s, overl appe d a r ea s  are  geom etri c di stortio n  o r  in con s i s ten c y in  spatial  coo r din a tes, i t  is  necessa ry to find the geom etric tra n sfo r ma tion pa ram e ters fo r imag e regi stratio n .  In the com m on characte ri stic info rmati on,  the poi nt is the mo st  usu a l feature. The  method  dete c ts fe ature p o ints  of an  i m age, d e scri bes the fe ature  point s a c cordi ng to  t he  neigh borhoo d  of the feature poi nts,  a nd finally cal c ulate s  the  corre s p ond en ce relation sh ip   betwe en the f eature  point s  in the o r iginal  image s.  Poin t feature h a s  lowe r  calculat ion, and  doe s  Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 23 02-4 046   TELKOM NIKA   Vol. 11, No. 2,  Februa ry 2013 :  761 – 773   762 not dam age t he imp o rtant  gray info rmat ion of a n   ima ge, therefore,  it  can  greatl y  improve th e  regi stratio n  speed a nd a c cura cy. Harri s  detectio n  met hod is  a tradit i onal featu r e  point extra c tion  method,  whi c h is very  se n s itive to  cha n ges in i m ag e  scale,  and  it  largely le ad s to limitation  o f   the appli c ati on sco pe. Harri s featu r e  points  ca n  get  accu rate   regi stratio n  results with only  rotation, tra n s lation, a nd  small-scale tra n sform of  an   image, but fo r the la rge - scale tran sfo r m  of  an ima ge, th e meth od  ca n not  gua ra ntee the  corre c t  regi stratio n  results. Later,   the re sea r ch ers  have propo se d a larg e nu mber of featu r e poi nt  dete c tion meth od s with  scale i n varian ce, aff i ne  invariance, as well as local invariance.   David Lo we  summ ari z ed t he existing i n variant  feature-ba se d tech nique s, and f o rmally  prop osed a l o cal fe ature  based o n  scale spa c e, which  ca n re m a in invari ant  whe n  tran slat ion,  rotation,  scali ng, o r  affine  tran sform a tion , and  he  prop ose d  a  de scri ptor  ba sed  o n  this featu r e  in  2004. He na med this Scal e Invariant Fe ature T r an sfo r m, that is SIFT algo rithm later [10].  SIFT method detect s  a feature in the sca l e  spa c e an d determi ne s the scale and l o catio n   of the featu r e poi nts, u s e s  the  main  d i rectio n of th e nei ghbo rh o od g r adi ent  as th e di re ction  feature of th e feature  poi nt in ord e r t o   enabl e the  operator in d epen dent of  the scale a n d   dire ction. T h e featu r e s  by  SIFT meth o d  can  be  u s e d  for reliable   matchin g   wit h  same  obj ect or   scene, th ey a r e inva ria n t to  image   scalin g an d  rotation , and  have  go od  robu stne ss in  llumin a tio n   cha nge s, noi se, and affine  transfo rmatio n. In additi on, SIFT features are the lo ca l characte ri stics  of an image, they can  corre c tly match wit h  high proba b ility.  This p ape r resp ectively e x tracts featu r e points in  multi-spe c tral  and pan ch romatic  image s u s in g  the SIFT me thod, featur e  points incl ud e po sition,  scale,   si ze and  dire ction.  Fig u re   1 gives th e feature  point s extracted  by the SI FT method in m u lti-sp ect r al a n d  pan ch rom a tic  image s.               (a) A multi-sp ectral im age   (b) A pan ch ro matic imag e  (c) Featu r e p o ints u s ing th e SIFT method                                Figure 1.  Extract Fe ature Points Using  The SIFT Method       3. Selection fea t ure poin t s throug h Delauna y  triangulation   Feature is  a stru cture  prop erty sh o w n by one  or so me  pixels relative to its   neigh borhoo d ,  it generally  better mai n tai n s inva rian ce  in tran slation  and rotation.  Point feature  is   a basi c  featu r e, but its scope is  the m o st extensive ,  and its calc ulation and d e scriptio n is  very  simple, so feature poi nts a r e sel e cte d   a s  the re gistration point s in the pap er.     3.1. The pro p ert y  of Dela una y  triangulation net w o r k   In the fiel d of   geo sci en ce s,  a la rge  num b e r  of di screte   data often  n e ed to  be  p r o c essed ,   the data di stribute uneve n , therefor e, it need s to con s ide r  ho w to rationally an d  effectively use  the valuable  data. In 1908 , G.Voronoi firstly limited  the effective scop e of each  discrete poi n t  in   mathemati cs,  that is th e  scope  of effe ctively  refle c ting regio nal i n formatio n, a nd d e fined t he  Voron o i di ag ram  on t w o - dimen s ion a l  plane  (referred to  a s   V -g raph ). In  191 1, A.H.Thie ssen  applie d V-gra ph in  the  ave r age  rainfall  of big  re gion s. In  193 4, B . Delau nay ev olved  Dela un ay  triangul ation  from  V -gra ph (referred  to as  D -t ri angul ation). Since  then,  V -gra ph an d   D - triangul ation  have be come  universally accepted a nd  widely u s ed t o  analyse discrete d a ta.   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046       A Quick Im age Regi stratio n  Algorithm  Base d on Dela una y Tria ngul ation (Yon gm ei Zhang )  763 Dela unay tri a ngulatio n i s  t he a s so ciate d  g r aph  of  V -grap h  [11]  (al s o  kn own a s   Thiesse n   diagram, Di ri chlet m ap,  Vigner-Seith z gra ph).  V -g raph  is  defi ned a s  foll o w s. Su ppo si n g   V ={ v 1 , v 2 ,..., v N },  N ≥ 3,  V  is a  set of p o ints  in. Euclide an  plane. And  th ese  point s a r e not colline a r ,  any four poi n t s are n o t co circula r .  d ( v i , v j ) i s  th e Eu cl idean  dista n ce of  v i ,  v j . Suppos e  point  x  is   on the pla ne,   V ( i )= { x ∈ E 2 ︱ d ( x , v i ) ≤ d( x, v j ),   j = 1 ,2,..., N ,  j ≠ i } is called V o ronoi Polygon ( V -Poly g o n ),  all  V -polygon s of each poi nt jointly constitute  V -graph .  V -gra ph o n  th e plan e can b e  se en a s  e a c h p o int in p o i nt set  V  a s  a  gro w th  core, expand   outwa rd in th e sam e  rate,  until they meet eac h oth e r and fo rm  the grap hs  o n  the plane. In   addition to  th e oute r mo st  point of the  formatio n  for  open  area s,  the re st p o int s  form  convex  polygon s [12] .  D -tri ang ulatio n is  V -polygo n s  with com m on ed ge s,  and i s  called  adja c ent  V -p olygon s.  Con n e c ting a ll adjace n t  V -polygon g r o w th center formed the trian g le netwo rk is calle d the  D - triangul ation netwo rk.   The oute r  bo unda ry of  D -triangul ation is  a convex poly gon,  whi c h  co nsi s ts of conv ex set  c o nn ec te d   V , often referred  to as convex  hull.  D -tria n g l e has two very important p r ope rtie s.  Empty circle  prope rty. Delaun ay trian gulat ion i s  u n ique (any four poi nts cannot be   co cir c ula r),  in   D -tri angl e formed by poi nt set  V , its ci rcumci rcl e  of e a ch  tri angl e contain s  no  othe r  points in  V , it is sh own in Figure 2.   The large s t minimum a n g l e pro perty. In the triang ul ar net work fo rmed by p o in t set  V ,  the minimum  angle in th e  triangle  of  D -tri ang ulatio n is the la rg est. In this  sense, Dela un ay  triangul ation i s  "the clo s e s t to the regula r izatio n"  trian gular n e t. Specifically refe r to the conv ex  quad rilate ral  diago nal fo rmed by  two   adja c ent tri a n g les,  wh en  e x chan ging, th e minim u m a ngle  of the six interior a ngle s  no  longer in crea se s. It is sho w n in Figu re  3.                                               Figure 2.    Empty Circ le                                  Figure 3.   The Larges t  Minimum Angle      These two p r opertie s   dete r mine   D -trian gulation ha s great appli c at ion  value. Me anwhile,  it is al so  th e uni que  an d be st two-d i mensi onal  p l ane tri ang ul ation. Mile s  proved  that  D - triangul ation  wa s "go od" triangul ation. S i bso n  foun d  " i n a finite  poi nt set, the r e i s  o n ly a p a rti a l  and i s om etri c triang ula r  n e t work, which i s   D -tri ang ulat ion". Ling as furthe r d e mon s trated  that "i n   gene ral,  D -tri angul ation i s   optimal". Tsai  thoug ht that  "in Euclid ean  plane, th ere  is n o  mo re th an  three adj acen t points in a ci rcle,  D - t r i an gu la tio n  is  un iqu e " .  These two  prop ertie s  ef fectively ensure  Delau n a y  triangulati on is the  optimal  triangul ation  clo s e s t to eq uiang ular  or  equilate ral, a nd ma ke the  control poi n t s distri bute  as  evenly as po ssible in e a ch small tria ngle .     Dela unay tria ngulatio n hel ps to avoi d n a rrow  or  too  small a c ute t r iangle in th e  ca se of  points evenly   distri buted. Trian g le s  in t r iang ulation  should  all be  a c ute tri angl es, or three e d g e s  roug hly equal  to each  othe r, the triangl e s  do n o t  cross and  overla p. Delau nay triang ulation i s   clo s e s t to e quilateral tria ngulatio n. In variou s t w o - dime nsi onal  triang ulation ,  only Del a u nay   triangul ation  can b o th mee t  the global a nd local opti m ization.     3.2. Selectio n of Fea t ure  Points   Select a p p r opriate  feat ure i s   parti cula rly impo rtant in  re g i stration. In  normal  circum stan ce s, the  best  ch oice  is i n  the   absen ce  of  d e formatio n trend, a nd  regi stration  requi res  enou gh poi nts, evenly distributed a s  p o ssible in th e whol e ima ge, in orde r to ensu r e the  accuracy of registration. In this pap er,  we ex pe rim ented a vari ety of feature point extra c tion  method s, the n  we respe c tively used th e SIFT to  extract featu r e  points fo r mu lti-spe c tral an d   pan chromati c image s, wh ich  can give  the coo r di n a tes of feat ure p o ints,  scale  size  a n d         D   C    B  A  D C B   D  C B  A Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 23 02-4 046   TELKOM NIKA   Vol. 11, No. 2,  Februa ry 2013 :  761 – 773   764 orientatio n fo r multi-sp ectral and  pan ch romati c  ima g es. In thi s  al gorithm,  rem o ve dupli c ati on  matche s  and   multy to one   matchin g  p o i n ts, then   e s ta blish  Del aun a y  triangul atio n, rem o ve thre e   collinear or four  cocircul ar feature poi nts by Delaunay  trian gulation.  Determin e the homologous  control p o int  pairs by the  Euclide an di stance, in  ord e r to  redu ce  the false mat c h rate. By u s i n g   the  hom olog ous co ntrol point  pai rs, make   affi ne transfo rmatio n  between multi-spe c tral   an d   pan chromati c image s thou gh the lea s t square met h o d , get tran sfo r mation  para m eters, cal c u l ate   the locatio n   betwe en regi stration im ag es. The va lid  basi s  of mul t i-spe c tral an d pan ch roma tic  image regi stration usi ng tri angul ation is l i sted a s  follo ws.   (1) T he n e a r est. The n e a r est thre e nei ghbo r poi nts  form a tria ngl e, and e a ch segm ent  (trian gle si de) does n o t interse c t to ea ch  other.   (2)  Uniq uene ss. Eventuall y  get consi s te nt result s no  matter wh ere  to start.   (3) Optimality .  If a co nvex  quad rilate ral  diago nal fo rm ed by  any two adj acent tri angle s  i s   interchan gea ble, the small e st inne r angl es  for two tria ngle s  do not  become big g e r.   (4) T he mo st rule. If the minimum a ngle of ea ch  triangle in t he trian gulati on is in   ascen d ing o r der, the mini mum angl e of the Delau n a y  triangulatio n is the maximum value.   (5)  Regi onal.  Increm ent, deletion, mov e ment  one v e rtex only affects the n e ig hbori ng  triangle s .     (6) Co nvex  p o lygon sh ell. T he  outermo st bo und ary  of the tri ang u l ar  netwo rk fo rms the  shell of a con v ex polygon.  Since  the fe ature  point s  use d  in  this  pape r  i s   ado pted a s  co ntrol poi nts, the  feature   points are ge nerally con c e n trated  in  th e feature  lin es ,  whi c h i s  co nsistent f eature of  Trian gulate d   Irreg u lar Net w ork  (TIN). The  bigg est advantag e  of TIN is the accurate de scriptio n of the  compl e x terra i n. We  ca n e s tablish  a tria n gular net work for the  wh ole  cont rol p o int s  in th e ima g e ,   establi s h  den se tri ang ulati on in l a rg er u ndulatin g regi ons,  and  co n s tru c t spa r se  triang ulation  in   the flat region s.   Comm on con s tru c tion tria n gulation m e th ods in clu de a ngle jud g men t  method, Thi e ssen  Polygon and  Delaun ay triangul ation. No matter  where to build  Delaun ay triangul ation n e t,  Dela unay tria ngulatio n is u n ique a s  lon g  as  the feature points d o  n o t chan ge.   In this  pap er, sele ct  Dela unay tria ngul ati on in  the  experim ents.  In the  pro c ess of   establi s hm en t netwo rk, e a ch  co ntrol  point pa rtic ip ated in the  netwo rk stru cture, th ere i s  n o   cross, cracks and other i rregularities.  Construc t procedure of Delaunay  tri angul ation is as   follows .  (1) T r av e r s e  all   s c attered   points, find t he incl usive  ca se of  the p o int set, get the initial   triangle s  a s  the point set convex hull, and pl a c e it into the linke d list of the trian g le.   (2) Ins e rt the s c attered points  for the  point  set in  orde r, find o u t the trian g le wh ose  circum circle contai ns  the inse rtion  p o ints in linked li st of the triangle ,  delete t he publi c   sid e s  affect the tria ngle, co nne ct  the inse rtion  points  with  all vertice s  in fluenci ng the  triangle, thu s   compl e te a p o int inse rtion  in the linke d list for Del aun ay.  (3) A c cording  to optimizati on criteri on, optimize th e l o cally an d ne wly forme d  tri angle s ,  put the forme d  triangle into  the linked li st for Delau nay  triangle.   (4) Pe rform  step (2 ) and (3), until all scattered p o int insertion is ove r .   In this pape r, respe c tively construct  De la unay tri angul ation for multi-spe c tral and   pan chromati c image s  usi ng the  del a unay fun c tio n  in  Matlab.  Del aun ay triang ulation   for   multispe ctral and pa nchro m atic imag es ar e co nst r u c ted as  sho w n i n  Figure 4.  In Figure 4  (c) i s  to respe c tively extract featu r e point s in  multi-sp ect r al and  pan chromati c images u s i ng tradition a l  SIFT al gorithm, feature  points in clu de dupli c ation   matche s, m u l t y to one  mat c hin g  p o ints,  three  colli nea r o r  fou r   co circula r  featu r e   points, th e tot a l  numbe r is 11 2. The numb e r of matchin g  points after removeme nt duplicatio n matche s, mul t y to   one mat c hing  points is 9 7 . The numb e r of matching  points afte r removeme nt three  collin ea r or  four  coci rcula r  feature poi n t s by  Del aun ay triangul ation is  91. The  intersectio n  o f  straight lin e s  in   Figure 4 (d ) shows the mismatch by  u s ing tradition al SIFT algorith m .   It can be see n  in Figure 4,  Delaun ay triangul at ion ca n automatical ly adjust the grid si ze   according  to the g r ou nd flu c tuation  and  compl e xity  in the overl appi ng a r ea s. Sel e ct fewer  poi nts  in flat region s, form larg er triangl es.  In ground fluctuatio n an d  complex i ty, form s m all e r  triangles thro ugh further  matching interpolat io n, all triangles are acute triangles.   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046       A Quick Im age Regi stratio n  Algorithm  Base d on Dela una y Tria ngul ation (Yon gm ei Zhang )  765                        (d) Mi smat ch  usin g Tra d itio nal SIFT Algorithm     (e)  Red Fe ature poi nts wit h in the Re cta ngle s   for Fepe ated  Matchin g , Mu lty to one      (f) Image s for Removem e n t  Repeate d , Many- to-one M a tchi ng     (g)  Red Fe ature Point s  for Removem e n t  three  Collinear or  four Coci rcular Poin ts using  Dela unay Tri angul ation                                                            Figure 4. Con s tru c t Dela un ay Triang ulati on Thr oug h Feature Poi n ts Extracted by SIFT Method       4. A Ne w   Re gistra tion Al gorithm Ba s e d on Delau n a y  Triangulation    Matchin g  me thod ba se d  on SIFT de scripto r  h a s succe ssfully a pplied i n  ma ny fields,   su ch  as targ et identification,  pa norami c  ima ge  mo saicin g. Howe ver, the SIFT  algo rithm i s   still  less appli ed i n  remote  se nsin g image  regi stratio n . The main  re aso n s a r e th at the traditio nal  SIFT algo rith m ado pts  Lo we' s  the  ne a r est  neig hbo r and  next n e are s t nei ghb or di stan ce  ratio   method, thre shol d is al ways ch osen  empiri cally , accuracy of  remote  sen s i ng imag es f o r  (a) A multi- sp ectral  Image   (b) A Pan c hromatic  Image   (c) Extract Fe ature u s ing T r adition al SIFT  Algorithm   Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 23 02-4 046   TELKOM NIKA   Vol. 11, No. 2,  Februa ry 2013 :  761 – 773   766 compl e x matching feature  points i s  lower. The accu racy of matching points will directly affect the  sub s e que nt image regi stra tion accuracy .  In image regi stration o n  the basi s  of feature  point s, feature poi nt extraction n eed s to be   con s id ere d  fi rstly. When   extracting  fe ature  poi nt s,  feature p o in ts ne ed to  b e  si gnificant  and   evenly dist rib u ted, and  the  numb e r i s  n o t too fewe r.  Feature extra c tion i s  mo re  compl e x, and  it  need s to find a sTabl e, effective and sim p le feature ex traction o p e r a t or.  SIFT features have many f i ne f eatures,  but there  are still so m e  shortcomings li sted as   following:  (1) Be cau s e  feature dete c tion need s to search fo r  multi-scal e space, which requi re s a lot of  convol ution  operation, a nd in  or der  to pro d u c e f eature  poi nt de scripto r s,  req u ire  mul t iple  weig hted hi st ogra m  op erat ions. All the s e ope ration s  inclu de a l a rge nu mbe r  o f  floating poi nt  operation s , th erefo r e, relati ve to the  nu mber of  its  fe ature point s, the  computati onal com p lex i ty  of algorithm i s  high er, and  the comp utation is large r , speed i s  lower.  (2) SIFT feat ure s   are  firstly applie d to t a rget  re co gnit i on, which n e eds to d e tect   feature  point s as  many as possible. However, large num ber of f eatures will increase feature mat c hing time.  (3) SIFT feat ure set is not  very significant, ther e are  still some inst ability points in the set. Many  feature  point s det ected  b y  SIFT algori t hm ca nnot  d e scrib e   conto u r featu r e s , they are neith er  edge p o ints n o r co rn er poi nts.  For  remote  sensi ng ima g e  regi stratio n   with differe nt sea s o n s, resolution s, and  sen s o r s,   the feature p o int matchi ng  is more co mplex  than g eneral imag e s . Tra d itional  SIFT algorit hm  can not get ri d of som e  e rro r mat c h p o int pairs for remote  sen s ing im age s.  Mean while,  the  traditional  SIFT metho d  d oes not ta ke  into a c count  repe ated  mat c hin g , multy to on e mat c hi ng   points a nd so  on, and it is with larg er  sp ace to optimi z e mat c hing  accuracy.    Whe n  cal c ul ating the dire ction s  of SIFT  key point s, the same  key point may have a  prima r y dire ction, one or  more a u xiliary direction.  In the prop osed algo rithm,  we sh all cla ssify  them into different featu r e  points.  Th ese  feature p o int s  may po ssib ly all or in pa rt gene rate th e  corre c t match  points, but they are a c tu ally the  same  points, it will gene rate rep eated mismat ch.  SIFT feature  match  with   exhau st ive search  may a l so  pro d u c e  one to  many , many to o n e   matchin g . Th ese fal s e mat c he s ne eds t o  be eliminat ed one by on e, otherwi se i t  will affect th e   sub s e que nt image  regi stration a c curacy. Lei Xiaoqu n and  etc.  an alysed th e m a in e rro r  sou r ce s  in SIFT feature point m a tch i ng, po ssi ble  error  pai rs  were  eliminate d  gradually, a nd p r eci s e  pa irs  were  extract ed a s   many  as  po ssi ble.  Then  u s e th ese  mat c he d  point s a s  re gistratio n   con t rol   points, affine  transfo rmatio n and tiny fa cet pri m it ive rectifying were tested  on d i fferent time  and  resolution  im age s. Experi m ental  re sult s  sho w e d   thi s  al go rithm  could  get hi g her a c cura cy  in   regis t ration.  While the fea t ure point s are descri bed  by t he SIFT  algorith m , the descri p tor i s  a 128 - dimen s ion a l  vector,  whi c h cau s ed  ex ce ssive  com putation i n  t he  cou r se  of de scripto r  a nd  sub s e que nt regi stratio n . Many schola r s h a ve pro posed vario u s  improved  SIFT metho d s,  prin cipal  com pone nt analy s is  (PCA ) ca n red u ce th e  descri p tor di mensi onality, thus, it red u c e s   the computati onal  com p lex i ty. Re and  Suktha nkar   etc. use d  PCA  method to  re duce de scri ptor  dimension in  the norm a lized gradi ent field, the st ability was higher,  but t he preci s ion  was lower.  Speede d Up  Rob u st F eat ure s  (S URF) method  re d u ce d  the co mputational complexity,  which   wa s suitable   for large r  ch ange s in  ima ge resolution , but und er t he affine t r a n sformation  and  illumination  chang es, th e  effect was u n sati sfac to ry. Mikeolaj czy k p r o posed   expan sion  SIFT  descri p tor G r adient  Lo cati on-O r ie ntatio n Hi stog ra m  (GL O H),  it strength ene d  d i stinctive qua lity  for the  c h arac teris t ic   des c riptor, but the effec t   on the  fast imag e  matchin g  wa s not  satisfa c tory.  Wan g  Ti anji a  redu ce d  dimen s ion a lity of hig h -di m ensi onal  d e scripto r  fo r SIFT al gori t hm,  simultan eou sl y stren g thene d the nei ghb o r hoo d pixel  in formation  of the key point s, and a c hieve d   a fas t  matc h  effec t.  In the traditi onal alg o rith m for the fe ature  p o ints  extracted f r o m  two ima g e s, firstly  cal c ulate  the  nearest  neig h bor  matching  of ea ch  f eat ure  point fo r t he first ima g e  to the  seco nd   image,  which  is the  key p o int de scripto r  vecto r  of mi nimum Eu clid ean di stan ce.  The tradition al  SIFT algo rith m u s ed  Lo we 's  nea re st n e i ghbo r  and  su b-ne arest  nei ghbo r  distan ce ratio to  mat c h.  Whe n  the  rat i o is le ss tha n  a threshold  co rre sp ondi ng to the p o i n t, it is as th e co rrect m a tch,  otherwise it woul d be a b ando ned, ratio usually  uses L o we 's  re comm end ed  value of 0.8. For  remote  sen s i ng image  re gistratio n  wit h  different re solutio n s o r  sen s o r s, the  matchin g  fea t ure  points a r e m o re complex than the gen e r al image s. Although the traditional SIFT algorithm u s e s   a smalle r  rati o value  to o b t ain bette r m a tch  re sult s  with hi ghe r a c cura cy, te sting  re sults for a  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046       A Quick Im age Regi stratio n  Algorithm  Base d on Dela una y Tria ngul ation (Yon gm ei Zhang )  767 large  number of remote  sensing im ages show that ev en with a  sm a ller ratio val ue, it still cannot  get rid of som e  errors in re mote sen s in g  images.    This pa per p r ese n ts an im proved regi strati on algo rith m base d  on Dela unay tria ngulatio n   to achieve   multi-spe c tral  and  p anchromatic im ag e regi stration , whi c h  is o n  the  groun d of   con s trai ned  Dela unay tria ngulatio n feature poi nt regi stration. Th e spe c ific  step s are as follo ws.  (1)  Re spe c tively extract feature poi nts i n  multi-spe c tral and pa nchromatic ima g e s .  (2)  Even with   a small ratio  value,  it  still cannot   com p le tely get rid  of  the erro r p o in ts, and  the numb e r  of feature p o i nts extra c ted  is very li ttle at this time, whi c h is  unf avorabl e in t he  followin g  ima ge regi stratio n . In ord e r t o  extr a c t ma ny matchi ng  points, thi s  p aper u s e s  th e  prop osed ratio of 0.8 by Lo we, ado pting  the nea re st n e ighb or a nd sub-n e a r e s t neighb or meth od   for the initial match.    (3) Ba sed on  the initial match point s, the erro rs a r e eli m inated on e by one. Aiming at the   traditional  SIFT metho d  d oes not ta ke  into a c count  repe ated  mat c hin g , multy to on e mat c hi ng   points a nd so  on, the pape r com p a r e s  the pixel  co ordinate s  for m a tch poi nts a nd traverse s  the  corre s p ondin g  points to remove dupli c ation mat c h e s an d multy to one matching poi nts in  traditional SI FT method, a nd en sures th e matchin g  p o ints uni que  and on e-to -o ne.  (4)In thi s  pap er , re spe c tive ly construct  De la unay tria ngulatio n of the multi-spe c tral and  pan chromati c images. Re mote sen s in g image s ca n be divided  into some grid area s by  Dela unay tria ngulatio n in orde r to guara n tee that  feature poi nts are examined i n  each g r id.  The  improve d  re gi stration  algo ri thm based o n  SIFT  can  m a ke the  extract i on feature p o ints u n iformly  distrib u ted, range feature  point s in each small triangle, and it can ef fectively improve the  regi stratio n  preci s ion.   (5)  Revise the feature poi nts by the Delaun ay  trian gulation, re m o ve three col linear o r   four co ci rcula r  feature p o in ts obtaine d b y  SI FT descri p tor usi ng the  Delau nay triangul ation.   (6) T o  redu ce the false m a tch rate, Eu clide an di sta n ce i s  introd uce d  to dete r mine the   homolo gou s  control poi nt pairs   in this  pape r. Cal c ul ate the Eucli dean di stan ce betwe en t w o  feature  poi nts de scripto r , t hat is to fin d   out  the   ne are s t  an d su b-n eare s t neig h b o r  fe ature   p o i n t  descri p tors   and   with th e feature  poi nts  de scripto r    by Euclid ean di stan ce . Then  cal c ulate  the  ratio of E u cli d ean  dista n ce  of  de scripto r s   an d  ,   and   . If the ratio   r  is   less than  the  spe c ified th re shol d (Usuall y   , here  ), th en con s ide r   succe ssful  match, poi nt pairs ( , ) are  a pair of mat c hi n g  point s  of image seq uen ce, othe rwise, the   matc h fails .    (7)  Using th e  homolo gou s cont rol poi nt pairs, obtain  the affine tra n sformation  b e twee n  multi-spe c tral  and  pa nch r omati c  im a ges by a d o p ting the  le ast  squ a re  method,  obt ain   transfo rmatio n param eters, cal c ulate  the loca tion  of the regist ration imag e s , and get the  regi st rat i o n  re sult s.    SIFT algo rith m can d e tect   a lot of fe ature poi nt s, the   numbe r  of m a tchin g  i s  mo re, thi s  i s   one featu r e  of SIFT algo rithm. At first, SIFT featur es  was  used  in target re cog n ition, target  recognitio n  n eed s to match smalle r targets fr om a l a rge n u mbe r  of image databa se, theref ore   the small e r t a rget s al so n eed ri ch er fe ature info rma t ion. This is  also ve ry important to im age  regi stratio n  with small e r  proportio n  of  o v erlap, b e cau s e i n  this case we ne ed to  en sure that t i ny  image overl a p still has en ough featu r e  points. Of course, image  r egist ration i s  different from  obje c t re co gn ition, the re gi stration  for t w o im age s d oes  not n eed  too many m a tch p o ints,  and   this is the imp r oveme n t in the pap er.       Table 1.   The Test Results    ' i q " i q i p i p ' i q i p T h e  i m a g e  p a rt  w i t h  re l a t i o n s h i p  I D   rI d2 0  w a s  no t  f o und i n  t h e  f i l e . T h e im ag e p a r t  w i t h  r e lat i o n s h ip  I D  r I d 2 1  w a s  n o t  f o u n d  in  t h e f ile. T h e im ag e p a r t  w i t h  r e lat i o n s h ip  I D  r I d 2 2  w a s  n o t  f o u n d  in  t h e f i le. T h e im ag e p a r t  w i t h  r e lat i o n s h ip  I D  r I d 2 3   w a s  no t  f o und i n  t h e  f i l e . T h e im ag e p a r t  w i t h  r e lat i o n s h ip  I D   rI d2 4  w a s  no t  f o und i n  t h e  f i l e . Performance  Traditional  SIFT  algorithm  The algorithm ba sed on Delauna y  triangulation  The numbe r of fe ature points   296  251  Correct rate   64%   72%   Registration time( s ) 1.5058   1.3852   RM SE   0.9665  0.6254   Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 23 02-4 046   TELKOM NIKA   Vol. 11, No. 2,  Februa ry 2013 :  761 – 773   768 In this paper ,  a lot of multi-sp ect r al and  panch r om atic image s hav e been re spe c tively  tested by the  traditional SI FT  algo rithm  and the p r op ose d  algo rith m in the pape r ,  the test re sults   are sh own in  T abl e 1. Expe riment re sults show  the pro posed algo rithm has sig n ificantly redu ced   the numb e r  of extraction  feature  poi nts, im prove d  the mat c h i ng spee d a nd re du ced  the  mismat ch rat e , and improved the regi stration accu ra cy .    As an examp l e, a regist rat i on re sult for t he propo se d algorith m  is sh own in Figure 5.   The ru nnin g  time is rel a tively slower th an onl y usi n g  SIFT control  points in im age regist rati on  without  Dela u nay trian gulat ion. For multi - sp ect r al a nd  pan chromati c image s illu st rated i n  Figu re   4, the registration run n ing  time after Delaun ay correction is 0.2 0 98 s , the regi stration  RMS E  is   0.6524,  whil e the  re gistration time  b y  dire ctly u s ing SIFT  co ntrol p o ints  is 0.2 1 5 s , t he  regi stratio n   RMSE  is 0.680 8                                      (d) Mi smat ch  usin g Tra d itio nal SIFT Algorithm     (e)  Regi strati on Image s using SIFT Algorithm     (f) Re d point s for repe ated,  multy to one  matchin g  extracted by tradi tional SIFT  algorith m   (g) Ima ges fo r remove men t  repeated m any- to-one m a tchi ng   (a) A multi- sp ectral  Image   (b) A pan ch ro matic  Image   (c) Extract Fe ature Point s  usin g  Traditio nal SIFT Algorithm   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046       A Quick Im age Regi stratio n  Algorithm  Base d on Dela una y Tria ngul ation (Yon gm ei Zhang )  769 (h) Red featur e  points for rem o veme nt three  colli ne ar or fou r  cocircular fe a t ure poi nts usin g  Dela un a y  tri a n gul ation     (i) Registrati on  imag es   Figure 5.  Re gistratio n  Re sults      5.  Registr a ti on Effe ct an d Ev aluation   There are two regi stratio n  accuracy a nalysi s  meth ods, on e is  statistical an alysis of  control point s, Root Mean  Square Erro r  (RMSE). It  is assume d that the matching  control p o int s   can  re pr ese n t  t he simil a r  cha r a c t e ri st ic s,  an d dete r mine the  tra n sformation  relation b e twe e n   image s. The  other i s  direct compa r ison  betwee n  the  gray of ima ges. Hi stog ra m matchin g   of  regi stratio n  image s is re q u ired. Thi s  p aper u s e s   RMSE  as the quantitative  evaluation of image  regi st rat i o n  re sult s.     The  RMSE  b e twee n refe rence image  S ( x , y ) an d re gistratio n  ima g e  T 1 ( x , y ) i s   denote d   as  E 1 ,  RMSE  is defined a s  follows.     N M y x T y x S E M x N y   11 2 1 1 ) , ( ) , (            whe r e  E 1  reflects the differen c e b e tween  S ( x , y ) a nd  T 1 ( x , y ), the small e r  E 1  is, the smaller  differen c e i s . The algo rith m still has  b e tter regi stration effects  when the ima g e  exists rotation  and  tran slati on.  The expe rim ent image s with 0 0 ~3 60 0  rotation   can  accurately re gister. Fig u re  6 sho w s  the regi strati on  re sults in  the case of  rotation 3 6 0  for the  multi-sp ectral  ima ge.   The regi stration   time is  0.149 8 s , a nd  RMSE  is  re spe c ti vely 0.6524  and 0.7 452  b e fore  and  after  rotation. A fter  rotation, the  registration ti me is 0.16 96 s ,  RMSE   i s  separately  0.6 808 and 0.87 33  in Figu re 6  by  the tradition al  SIFT algorith m , the re sult  sho w s  the p r opo sed  regi st ration al go rith m has  strong er   adapta b ility to rotation.              (a) A pan ch ro matic  image     (b) Rotation  3 6 0  for a  multi-spectral  image    (c)  Mismat ch  by using ditio nal SIFT  algorith m   Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 23 02-4 046   TELKOM NIKA   Vol. 11, No. 2,  Februa ry 2013 :  761 – 773   770   (d)  Regi strati on image s by  using tra d itio nal  SIFT algorith m   e) Extract fea t ure point s using tradition al   SIFT algorith m   (f) Re d feature points  for re peated  mat c h i ng,  multy to one   (g) Ima ges fo r remove men t  repeated m any to  one matvhing   (h)  Red featu r e point s for removeme nt three  collinear or four coci rc ular f eature points  usin g Del aun ay triangulati o n   (i) R egi stratio n  image s   Figure 6.  Re gistratio n  Re sults      In Figure 6 (e), the total numbe r of points is  69 respectively extracted in multi - sp ect r al   and p a n c h r o m atic ima g e s  usin g tra d itio nal SIFT alg o r ithm, the fea t ure p o ints i n clud e du plication   matche s, m u l t y to one  mat c hin g  p o ints,  three  colli nea r o r  fou r   co circula r  featu r e   points, th e tot a l  matchin g  nu mber  of point s is  60. Th e   red  poi nts within  the re ctan gles sh ow re peated  m a tch i ng,   multy to one f eature  point  matchin g  in F i gure  6 (f).  T h e red  point s  within the  re ctangle s  in Fig u re  6 (h) are removement three collinear or four  cocircul ar feature point s using Delaunay  triangul ation,  the total num ber of m a tchi ng poi nts i s   60 after   rem o vement rep eated mat c hi ng,  Evaluation Warning : The document was created with Spire.PDF for Python.