TELKOM NIKA , Vol. 13, No. 4, Dece mb er 201 5, pp. 1337 ~1 342   ISSN: 1693-6 930,  accredited  A  by DIKTI, De cree No: 58/DIK T I/Kep/2013   DOI :  10.12928/TELKOMNIKA.v13i4.1178    1337      Re cei v ed Au gust 27, 20 15 ; Revi sed  No vem ber 1 3 , 2015; Accepte d  No vem ber  27, 2015   A Novel Image Segmentation Algorithm Based on  Graph Cut Optimization Problem      Zhang Gu an g-hua *, Xiong Zhong-y a n g , Li Kuan, Xing Chang - y u an, Xia Shu- y i n   Cho ngq in g Uni v ersit y , Ch on g q in g Cit y ,  4 0 0 0 30, Chi n a   *Corres p o ndi n g  author, e-ma i l : guan gh ua.zh ang @outl ook.c om      A b st r a ct   Imag e s e g m en tation, a  fun d a m e n tal  task  in  co mp uter v i si on, h a be en  w i dely  use d  i n  rece nt   years in  many  fields. De al in g w i th the gra ph cu t o p ti mi zation  prob le obtai ns the i m age s e g m e n tat i o n   results. In this study, a novel al gorith m  w i th  w e ighted g r aphs w a s co nstructed to solve the i m ag e   seg m e n tatio n  prob le thr o u gh mini mi z a tio n   of an   en erg y  functio n . A  b i nary v e ctor  of the s e g m e n ta tio n   lab e l w a s defi n ed to d e scrib e  both the for e g r oun d an the  backgr oun d of  an i m a ge. T o   de mo nstrate th effectiveness  o f  our prop osed  meth od, four  vario u s ty pes  of images w e r e  used to co n s truct a series  of  exper iments. E x peri m e n tal r e sults ind i cate t hat co mp ared  w i th other methods, the  prop osed  alg o rith m can   effectively pr o m ote th e qu al ity of ima ge  seg m e n ta tio n  und er three  p e rformanc e ev alu a tion  metri cs,  na me ly, misc la ssificatio n  error  rate, rate of the nu mber  of b a ckgrou nd p i xel s , and the r a tio  of the nu mber  of   w r ongly class i fi ed foregr ou nd  pixels.      Ke y w ords : Image Se g m e n tation, Graph C u t, Energy functi o n , Pixel        Copy right  ©  2015 Un ive r sita s Ah mad  Dah l an . All rig h t s r ese rved .       1. Introduc tion  Image e ngin eerin g is a ri ch  re sea r ch  area  that ha s been  explored for m any  years [1].  Re cently, re searche r s hav e cla ssifie d  image e ngine ering i n to three dom ain s , namely, imag pro c e ssi ng, i m age a nalysi s , and im age  comp re hen si on. Gen e rally , image seg m entation, which   has  bee n wi dely used in  many different appli c ati ons, i s  a  ke y issu e in th e field of im age   pro c e ssi ng. Image segme n tation refe rs to the divi sion of an image  into several  sep a rate  regi ons  to represent variou s types  of object s  [2, 3].  Image proce ssi ng spe c ifically aims to impl eme n t the pattern  recognition p r o c ess, and   image  segm entation is  a basi c   work in pattern  recognitio n  and compu t er vision. I m age   segm entation  sepa rate s a n  image into  several re gio n s an d then  provide s  d e scriptio ns to th ese   regio n s [4]. Using  ce rtain similar criteri a  of low-le vel vi sual featu r e s ,  such as  col o r, texture, an d   sha pe, imag e segm entati on is defin ed  as the  co nversi on of a d i gital image to several no n- overlap p ing region s, whi c h  result in obj e c ts in imag es  [5, 6].  Unfortu nately ,  the visual content s of t he image s are characterize d by d i versity,  compl e xity, and ra ndom ne ss; a n  in-dep th unde rsta n d ing of the i n ternal vi sion  mech ani sm  of  peopl e al so  remai n s l a cking [7]. To t he be st of  our  kn owle d ge, no m a tu re  segm enta t ion   approa ch exi s ts to sati sfy all the requi re ments for a p p lication e n viro nments.    Becau s e  of t he la ck of p r i o r info rmatio n ab out  obj e c ts i n  a n  ima ge, providing  accu rate   image  se gme n tation results is difficult  with the u s e of  existing m e thod s. The  de velopment  of an   effective and  highly accu ra te segme n tation app roa c h i s  theref ore im portant.        2. State o f  th e Art  Image se gm entation is a  high-level a pplication tha t  has bee n widely u s ed  in many  fields,  such as remote comm uni cation, military ,  remote  sensi ng, met eorol ogy, im age  processi ng, and intelligent   transportation, to nam e a few. In  thi s  section,  we discuss rel a ted  works abo ut image segm e n tation.   Wan g  et  al. pre s ente d  a  robu st an d eff i ci ent  app roa c h to  segme n t image wit h  limited   and intuitive use r  interacti on; the pro p o s ed al gor ith m  integrate d  g eode si c dista n ce info rmati on  with the flexibility of level set met hod s in energy minimi zation,  whi c h depends  on  compl e me nt a r y  st ren g t h s [ 8 ] .   Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 16 93-6 930   TELKOM NIKA  Vol. 13, No . 4, Decem b e r  2015 :  133 7 – 1342   1338 Han  et al. propo sed  a ne w mo del to d eal with th e i m age  seg m e n tation p r obl em. Thi s   model was  constructe d th roug h analy s i s  of the ch ar acteri stic  of textile/fabric i m age s. The  main   innovation  in  this  wo rk is it s in co rp oratio n of  ca rtoo n-an d-texture  de com p o s ition p r o c e s s in to  the mod e l, a s  well  a s  its bi as fiel d fun c ti on d e si gne d t o  e s timate th e deviatio n  d egre e  b e twe e n   the cart oon i m age an d the  piece w i s e co nstant ap prox imation [9].   Miao et  al. p r opo sed  a  ne w al gorith m  t o  segm e n t la rge top ograph ic ma ps ba se d on  the  ideas of fuzzy theory, randomiz ed  sam p ling, and m u ltilevel imag e fusi on. A l a rge topographic  map  wa s ran domly sampl ed first. Then , the optimal  clu s terin g   ce nters were  a c quire with fu zzy   c-m ean (F CM)  clu s teri ng . Multilevel i m age  fusi on  wa s develo ped to  fu se  the segm ent ed  image s into the final se gm entation map s  [10].   To enh an ce  the quality of image se gmentat ion,  Yu et al. propo sed a m e thod to  con s tru c t a  gene rali zed f u zzy co mple ment; the au thors al so d e velope d a  gene rali zed f u zzy   compl e me nt operator, whi c h ha s a go o d  prop erty fo r param eter o p timization in  real ap plicati ons  [10].   Aside f r om t he afo r em en tioned  wo rks, other  meth ods have  be en u s e d  for image   segm entation ,  such a s  in corpo r ating  adaptive lo cal inform atio n into fuzzy  clu s terin g  [ 12],  arbitrary  noi se mo del s vi a solution  of  minimal   surface  problem s [13],  clu s t e ring  te chniq ue  optimize d  by cu ckoo se arch [14], modified Gau ssi an  mixture mode ls inco rp orati ng local  spati a informatio n [15], conditio n a l rand om fie l d learni ng with convolutio nal neu ral n e twork featu r es  [16], dynami c  incorp oratio n of  wavelet  filter in  F C M   [17,18], proliferation  ind e x evaluatio n [ 19],  and fuzzy acti ve contou r m odel with  kernel metri c  .      3. Methodol og y  for Image Segmenta tion Base d on Graph Cut  Optimiza tion   From the ab o v e analysi s , we can see that  image se gmentation i s  a fundament al task in  comp uter vi sion. In this  se ction, we  discu ss th e i m age  se gme n tation p r obl em, and  so me  example s  of image segm e n tation are d e s cribe d  as foll ows.          Figure 1. Examples of ima ge se gmentat ion.      Suppo se th at  R  me an s the   whol e regio n s  in  an  imag e, and  then  segmentatio results  are represent ed by sepa ra ting  R  to several non-overla pping sub s et s, that is,  12 ,, , N R RR , a nd  the followin g  equatio ns  sh ould be  satisfi ed.    1 N i i R R   (1)     , ij R Rf o r i j    (2)     Let  ,, GV E W  be a g r a ph, in whi c V  refers  to a  s e t of vertices E  is a set of edge s,  and  W den otes weig hts of  graph edg es. Grap h cut  of  G  is to divid e  the g r ap h to  two  different   disjoi nt sets, that is,  GX Y . After w ards,  cost f unctio n  of  gra ph cut is d e fined a s  follows.    , mn G mX n Y C    (3)   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       A Novel Im ag e Segm entation Algorithm  Based o n  Graph Cut Optim i zation…   (Z. Guang -hu a 1339 w h er e  pa ra me te r   mn  refers t o  wei ght of e dge  mn E . Assum e  that graph  cut refers to  clo s ed  conto u r and di screte formula i s  e x ploited to cal c ulate the  co ntour len g th.   Grap h cut opt imization p r o b lem ca n be i llustrate d as f o llows.      12 1 , C i i M inc u t C C w   (4)     whe r 12 , CC C  refers to a partition and sym b o l   i w  denotes th e weig ht betwee n  the   edge s which con n e c the  set  1 C  and the  se 2 C . Furtherm o re, we  supp ose that  12 ,, , x A AA A  is a  binary ve cto r  of se gme n tation label , and  i A  den otes a la bel . Thus,  A  repre s ent s a  segm entation  sch eme an d  it can descri be both  fore g r oun d and ba ckgro und of the image to be   segm ented. Hen c e,  an en ergy  fun c tion  EA  for the imag e seg m entati on process is descri bed   as  follows .        E AR A B A    (5)     whe r e the foll owin g co nditions  sho u ld b e  satisfie d.    1)   xx xX R AR A   (6)     2)      , , , xy xy xy N B AB A A   (7)     3)   0, , 1, xy xy xy A A AA A A   (8)     w h er e s y mbol   R A  d enote s   regio nal  prop erties rep r e s entation, a n d  pa ramete  is   use d   to defin the wei ght of   R A . Afterward s , weight  bet wee n  two va rious pixel s  i s  co mpute d   as  follows .          1 ,,, 1 , 2 ij xy ij x y P i j P v F P v F    (9)     whe r  , P ij  mea n s the  edge  prob ability of the pixel  , ij , and  ij P vF  and  xy P vF   refers to the prob abilitie s whi c h are be longe d to pixel  , ij  and  , x y  respectively. Usi ng the   para m eter   ,, , ij x y , the ene rgy fun c tion can be  comp uted by the followin g  equatio n.          , ,,, ,,, ln , ij x y ij ij ij ij x y ij x y B i j x y f f Ef P v f Dv v        (10 )     w h er  is d e fined  as a  co nstant,  ,, , ij x y  d e n o te s  th e pa r a me te r   w h ic is  us ed  to  descri be th e i m porta nce of  neig hbo rho o d  pixel s   , ij  and  , x y . Then, im ag e segme n tation ta sk  is  s o lved by optimiz e this  energy func tion.      4. Experiment and Resul t s An aly s is   In ord e r to te st the effe ctivene ss  of ou prop osed  al g o rithm,  expe ri ments are de sign ed  to con d u c t p e rform a n c e v aluation. M o reove r , several im age  segmentatio approa che s   are   utilized, in clu d ing: 1 )  Parzen -wi ndo based th re sh olding  (PWT), 2) Doubl e-t h re shol d ima g e   binari z atio n (DTIB),  3 )  Lo cal gray   leve differe n c e   (LGL D), and  4) No rm aliz ed Cut (Nc u t).  In   particula r, da taset utilized  in this  experi m ent is  th same a s  p ape r, and  we  ch oose fou r  types  Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 16 93-6 930   TELKOM NIKA  Vol. 13, No . 4, Decem b e r  2015 :  133 7 – 1342   1340 infrared im ag es i n  o u r exp e rime nt, that i s , 1 )   Cro w , 2 )  Eagle,  3) Ai rplane  an d 4 )   Sailboat. On  t h e   other  hand,  mis-cla s sifica tion erro r rat e  (ME),  ra te  of numb e r of  backg rou nd  pixels  (FPR), an d   ratio of n u m ber  of wron g l y classified  foreg r o und pi xels  (F NR) a r expl oited as  p e rfo r ma n c e   evaluation cri t eria   Mis - c l ass i fic a tion error rate (ME) is  defined as  follows   1 TS T S TT B BF F ME BF     (11 )     whe r T B  and  T F  denote  ba ckgroun d a n d  foreg r ou nd  for the g r o u nd truth i m a ge,  more over,  S B  and  S F  refer to b a ckgroun d an d foreg r ou nd  in segm entati on re sults. Fu rtherm o re,  lowe r value o f  ME metric demon strate highe r quality  of segmentat ion re sults.   FPR  rep r e s e n ts the  ratio  of numb e r of  backg rou nd  p i xels that  mis-cla s sified to   the total  numbe r of  ba ckgro und  pix e ls, mo re over, FNR de not e s  the  ratio  of  numbe r of  wrongly  classifi ed   foreg r ou nd pi xels to the total numbe r of foreg r o und pix e ls.     TS T B F FPR B   (12 )     TS T FB FN R F   (13 )     Afterwa r ds,  e x perime n tal result s for th e  above th ree  perfo rma n ce  evaluation  metrics  with different  method s are provide d  as f o llows.         (a) Cro w       (b) Eagl e     (c ) Airpla ne     (d) Sailb oat     Figure 2. Experime n tal re sults for differe nt image type  0 0.1 0.2 0.3 0.4 0.5 0.6 PW T D T I B L GL D N cut O ur me t h o d ME FP R FN R 0 0. 1 0. 2 0. 3 0. 4 0. 5 0. 6 PW T D T I B L G L D N c u t O u r me t h o d ME FP R FN R 0 0. 1 0. 2 0. 3 0. 4 PW T D T I B L G L D N c u t O u r me t h o d ME FP R FN R 0 0. 1 0. 2 0. 3 0. 4 0. 5 0. 6 0. 7 0. 8 PW T D T I B L G L D N c u t O u r me t h o d ME FPR FN R Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       A Novel Im ag e Segm entation Algorithm  Based o n  Graph Cut Optim i zation…   (Z. Guang -hu a 1341 Integrating all  the above experim ental re sult s, we cal c ulate the average pe rform a nce  evaluation re sults from Fig u re 2 to Figu re 5 as follo ws.      Table 1. Overall experim en tal resu lt s for  all the four im age types   PWT  DTIB   LGLD   Ncut  Our  m e thod   ME  0.218  0.374  0.041  0.519   0.004   FPR   0.219  0.366  0.041  0.515   0.003   FNR   0 0 0  0.025   0.040       It can be se e n  from the ab ove experim e n tal  results th at our propo sed gra ph cut based  image  se gm entation  algo rithm i s  a b le  to effect ively  segm ent im a ges with  hig h  accu ra cy. T he  rea s on s li e in  that 1) th e g r aph  mod e l i s  able to  de scribe  relatio n ships  between  different im a ge  pixels an d th en co nvert s  the imag e se g m ent pr o b lem  to graph  cut  optimizatio n, and 2 )  graph  cut  optimizatio n has the a b ility to deeply mine intern al co rrel a tion s bet wee n  variou s graph n ode s.       5. Conclusio n   In this study, we presente d  a novel gra ph-cut-ba sed  image segm entation ap proach by  conve r ting th e imag seg m entation  pro b lem to  a  gr a ph-cut  optimi z ation  proble m . Inspi r ed  b y  the   facts that an image can be  sepa rated in to seve ral re gion s, and image se gme n tation re sults  are   rega rd ed as  several non -overlap ping region s, we convert the image se gme n tation task into a   grap h cut op timization p r o b lem. The m a in innovatio ns of thi s  stu d y are its  de velopment of  a   binary  vecto r  of the  seg m entation  la bel, which  can d e scribe   both the  foregro und  an d  the   backg rou nd o f  an image, a s  well a s  the  segm ent ation  of an image  via minimizati on of an ene rgy  function. Part icula r ly, the energy  functi on is  solved  by estimati on  of the importance b e twe e n   neigh bor  pixe ls. To evalu a t e the perfo rmance  of the  prop osed al gorithm, ME,  FPR, and  F NR  were u s e d  a s  the  pe rformance eval u a tion  crite r ia.  Fou r  type s of ima ges  were utili zed  to  con s tru c t a  d a ta set, na m e ly, the crow, eagle,  airpl ane, an d sail boat data  se ts. Finally, the   experim ental results sho w  that  our  prop ose d   al go rith m can effe ctively produ ce  accurate ima g e   segm entation  result s.   In the future, we will extend our work in t he followi ng asp e ct s: 1) we will att e mpt to   utilize the hierarchi c al graph cut algorithm in t he image segmentation task , 2)  we will introduce  other  optimi z ation te chnol ogie s  to  seg m ent ima g e s  (e.g., pa rticl e  swa r m o p timization ), a n d  3)  we will te st the perfo rman ce of our pr op ose d  method  by using oth e r  data sets.       Referen ces   [1]    Colom bo MG, D’Ad da D, Pirelli L H T he particip a tion of ne w  tech nol og y-b a se d firms in EU-fund e d   R&D partn ersh ips: T he role of venture cap i tal .   Research Policy . 2016; 45( 2) : 361-37 5.  [2]    Lush n ikov PM,  Vladimir o va  N. Modeli ng o f  nonl i near co mbini ng of mu ltiple l a ser b e a ms in Kerr  medi um.  Optics Express . 201 5; 23(24): 3 112 0-31 125.   [3]    Z e w e n  Li u, D o ng  D, C hun w e n LI. C h i nese   w o rd  segm ent ation  meth od  for sh ort C h in e s e te xt  base d   on co nd ition a rand om fie l ds.  Journ a of T s in ghu a U n ivers i ty (Scienc e a n d  T e chn o lo gy) . 201 5;  55( 8):   906- 910, 9 15.   [4]    Pike T W . Modelli ng e ggs hel l macul a tion.  Avi an Bio l ogy R e s earch.  20 15; 8( 4): 237-2 43.   [5]    Xu an  S, H a n   Y. Improved  e x treme  va lue   w e ig hted  sp ar se re prese n tati ona l im ag e d e noisi ng   w i t h   rand om pertur batio n.  Journ a l  of Electronic Ima g i ng.  20 15; 24(6): 06 30 04- 063 00 4.  [6]    Ni T ,  Gu X,  W ang H. F u zz y c-M eans  an d Mea n  S h ift Algorit hm for  3DPo int Cl ou d s  Den o isi n g .   T E LKOMNIKA Indon esi an Jou r nal of Electric al Eng i ne eri n g .  2014; 1 2 (7): 5 546- 555 1.   [7]    Basterrech  S,  Rubi no  G. Ra n dom  Neur al  N e t w o r k M ode l f o r Su pervis e d   Lear nin g  Pr obl ems.  Ne ural   Network World . 2015; 25( 5): 457.   [8]    Costall i  S, Ru gger i A. Indig n a tion, Ide o lo gi es , and Arme d  Mobil i zatio n : Civil W a r i n  Ital y 19 43– 45.   International Security.  201 5; 40(2): 11 9-1 5 7 .   [9]    McGlenn en M  S. "B y  M y   Hea r t": Gerald Vize nor' s  Almost Ashore a nd Be a r  Island: T he W a r at Sugar   Point.  T r ans mo tion . 201 5; 1(2) : 1.  [10]    Kumar S, T o shni w a l D. A dat a mini ng  frame w o r k to an al yz e roa d  acci den t data.  Journ a of Big Data 201 5; 2(1): 26.   Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 16 93-6 930   TELKOM NIKA  Vol. 13, No . 4, Decem b e r  2015 :  133 7 – 1342   1342 [11]    Heg de V N , R a o KN. A n  Outc ome B a sed  C u rricul u m D e si gn  in E n g i ne er ing-C a se  Stud y A ppr oach.   Journ a l of Eng i neer ing E ducat ion T r ansfor m a t ions . 201 5; 29 (2): 40-46.   [12]    Pahl avan i P, Nahr ST , Karimi  R. Build ing  det ection us in g ae rial ima ges a n d  LiDA R data  via ad aptiv e   neur o-fuzz y  s ystems.  Journal  of Geomatics Scienc e an d T e chn o lo gy . 201 5; 5(1): 109-1 2 5.  [13]    Okazaki T ,  Aibara  U, Seti ya ni L. A S i mul a ti on Stu d y  on   T he Behavi o Anal ys is of T he De gree  of  Members h ip i n  F u zz y  c-mean s Method.  IEIE T r ansactions  on Smart Processin g  & Computin g . 201 5;   4(4): 209- 21 5.  [14]    Sing h S, T u li R, Sharma V.  F u zz y   bi-criteri pro b lem  of c l usteri ng rati on  shops t o   w a r e hous e sites .   Internatio na l Journ a l of Know led ge a nd  Res earch i n  Mana ge me nt and E- Co mmerce . 2 0 15; 5(3): 1-7.   [15]   Venkates R. Improvin Data  Accurac y  Usin Pro a ctive Co rrelate Fuzz y S y stem in   Wire less  S ens o r   Net w orks.  KSII T r ansactions  on Internet a n d  Informati on Sy stems.  20 15; 9 ( 9): 3515- 35 38 [16]    Josep h  B, R a mach andr an  B, Muthukri shna P. Intelli ge nt Detec t ion a nd C l a ssificatio n  Of  Microcalc i ficati on In  C o mpre ssed M a mmog r am Imag e.  Image  An alysis   & Stereo lo gy.  201 5; 3 4 (3) :   183- 198.   [17]    Harikir an J,  Lakshmi PV, K u mar RK. Multip le F e ature  F u zz y  c-m ean s Cluster ing  A l gorit hm for   Segme n tatio n   of Microarr a y Images.  Inter n a t iona l Jour na of Electrica l  a nd C o mput er  Engi neer in g 201 5; 5(5): 104 5-10 53.   [18]    Srisae ng P, Ba xter GS, W ild   G. An ada ptive  neur o-fuzz y i n ference s y ste m  for forecasti ng Austra lia' s   domestic l o w  c o st carrier pas seng er dem an d.  Aviation . 2 0 15; 19(3): 1 50- 163.   [19]    Prabh avath y  P ,   T r ipath y  BK.  An integr ated  coveri ng-b a se d roug h fuzz y   set clusterin g  appr oach fo r   sequ enti a l data .   Internation a Journ a l of Re a s oni ng-b a se d Intelli ge nt Systems . 20 15; 7(3- 4): 296-3 04.     Evaluation Warning : The document was created with Spire.PDF for Python.