TELKOM NIKA , Vol. 11, No. 10, Octobe r 2013, pp. 5 600 ~ 5 608   ISSN: 2302-4 046           5600      Re cei v ed Ma rch 2 5 , 2013;  Re vised June  24, 2013; Accepte d  Jul y  1 1 , 2013   Ultrasound Image Segmentation based on the Mean- shift and Graph Cuts Theory      Yun Ting* 1 , Gao Mingxin g 1 , Wang  y a nming 1   1 Departme n t of Information & Scienc e, Nanj i ng F o restr y   Un iversit y ,   Jian gsu Provi n ce, Nanj ing  21 002 7, Chi na.   *Corres p o ndi n g  author, e-ma i l : nj yunti ng@ q q .com* 1 , d806 4 916 39@ qq.co m 2 , 718515 02 8 @ qq.com 3       A b st ra ct   T h is p aper  ad d r essed  the  issu e of v a scul a r u l tr asoun d i m ag e se g m entati o n a nd  pro pose d  a  nov e l   ultraso n ic vasc ular l o catio n  a nd detecti on  method.  W e  con t ributed i n  sev e ral as pects: F i rstly usin g me an- sh i ft se gm en tati o n  al g o r i t hm  to  o b t ai n  the  i n i t i a l  segm en ta tio n  re su l t s o f  va scu la r im ag es; Se co n d l y  new  data ite m  a nd  smo o th ite m  of  t he grap h cut  energy fu nctio n  w a s constru c ted bas ed o n  the MRF  mo d e ,  then w e  p u t forw ard sw ap  and  ex p an si on a  i d e a s  to o p t im i z e segm en ta ti on  re su l t s, co n s e q uen tly  accurate ly loc a ted the vess el  w a ll an d lu men  in vascu lar i m ages. F i n a lly c o mparis on w i th  experts  ma nu all y   taggi ng r e su lts, and  ap ply i ng  ed ge c o rrel a t i on  coeffi ci ent s an d var i anc e to v e rify th e va lid ity of o u r   alg o rith m, exp e ri ment al res u l t s show  that o u r al gorit h m  c a n efficie n tly co mb in es the  ad vantag es of  mean- shift and gra p h - cut algor ith m  and ac hi eve be tter segmentati on resu lts.     Ke y w ords :  Ult rasound im age; Mean-shift; Graph-c u t algorithm ;  Gauss  m i x t ure model.    Copy right  ©  2013 Un ive r sita s Ah mad  Dah l an . All rig h t s r ese rved .       1. Introduc tion  Medical ultra s ou nd imag e s  is an impo rtant type of medical image s and is widely  used in  medical di ag nosi s ,  Comp ared  with  oth e r m edical im aging  metho d s , ultra s o und   imaging  ha s t h e   advantag es  of non-tra u m a tic to huma n  body, real-t ime displ a y, low co st, ease to use. As an  ideal n on-i n vasive di agno sis metho d  it h a s b r illiant d e v elopment a n d  bro ad p r o s pect s . Ho wev e r,  becau se of  the imagin g  mech ani sm  lead to be  insufficie n t grayscal e  displ a y ran g e  or   unreasonable gray distri bution, so the ultras ound images auxiliary diagnosi s  effect  is   con s trai ned,  esp e ci ally in some l o cal d e tails, if t he g r ay scale diff eren ce i s  not  obviou s , that will  bring  a l o t of difficult to di agno si s. In o r de r to im pro v e ultra s ou nd  image s  quali t y and en han ce   the reada bility of ultra s o u nd ima g e s  l o cal  detail s ,  ma ke im ag es  suita b le f o r  huma n  e y es  observation  or ma chine  analysi s , the r efore in  re cent years  automat ic se gmentation  f o r   patholo g ical  area in ult r a s ound ima g e s  become the rese arch focu s.  Some  schola r s dealt  with  the ultrasoun d  image   segm entation i n  th e fre quen cy  domain,   su ch a s  litera t ure [1] used  wavelet de co mpositio n to  achi eve wave let coeffici ent s then  com b i ned   with neu ral n e twork meth o d  to pro c e ss  segm ent ation  probl em. Sheng Y etc [2]  con s tru c ted  an   accurate ultraso und im ag e seg m entati on algo rith m  in the wavele t domain with  the Cha n -Ve s e   model, Ali Kerma n i etc [3 ] combin ed the local histo g ram a nd  wa velet transfo rm to locate t he  positio n of  breast l e si on s.  J.Xie [4] p r op ose d   a  ne w  method  whi c h combin ed  texture  and  shap e   as th e p r ior i n formatio n, then  ene rgy f unctio n   wa s  con s tru c ted  a nd texture  of  patholo g ical   area  wa s cla s sifie d  by the shape p a ram e ter an d ga bor filter  co efficients. Ot her  re sea r ch ers  pro c e s sed  ultrasoun d ima g e  in th e time  domain,  Literature [5]  prop ose d   segm en tation alg o rith m  for vascula r  i m age b a sed  on gray pro b ability density   function  and  fast matching  idea s, Literat u re  [6] con s tru c t ed an i m ag e se gmentati on meth od  based o n  g r aph the o ry,  whi c h h a s t h e   advantag es  of robu st to  noise, se nsiti v e to the  blu rre d ed ge, lo w re sid ual e r ror  rate a nd  fast  cal c ulatio n speed. After  remove  spe ckle noi se,  literature [7,  8] a dopted  active  cont our mo del  combi n ing wi th  prio r  info rmation such as sha pe  tex t ure colo r  to   com p lete  p a thology  regi on   division. Ch ri stodo u [9] used ten differe nt texture  feature incl ude fi rst-ord e r  statistics, gray le vel  co-occu r ren c e-matrix, gra y   differ ential  statistics,  n e i ghbo rho od gray  differe nce  matrix, statist i cal  feature mat r ix, texture energy spe c trum,  cha r a c teri stic of fractal dim ensi on, po we r sp ectrum an d  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046     TELKOM NIKA  Vol. 11, No . 10, Octobe r 2013 : ISSN: 2302 -40 4 6   5601 sha pe p a ra m e ters etc to  extract  carotid atheros cle r otic pla que s,  then extra c t i ng sepa ratio n   results was treated by the K-neig hbo rin g  method [10,  11].  Becau s e  the  imagi ng m e cha n ism  of  u l traso und  im age s i s   com p lex, ch aract e risti c s of  patholo g ical   area  are di sturbe d by noi se a nd u n - p a t hologi cal reg i on, so th e visual fe ature s  of  critical re gion s are not di stin ct, the swap thoug ht o f  graph  cut  algorith m  ca n only get lo cal  optimum  sol u tion, so for the excessive inte rfere n ce  ultra s o u nd ima ge  can not  achi eve   satisfactory result s, if increas e the iteration steps t hat will  s pend more time, thus vascul ar  ultrasoun d im age segme n tation method  base d  on m ean-shift and  graph  cut theory is p r op o s ed   in this arti cl e, firstly mean-shift method is  a dop ted for initia l vascul a r ul traso und im age   segm entation ,  in image  small adja c e n t are a s  with  similar g r ay at tribute a r e  cl assified into  one   cla ss,  se cond ly a new d a ta  and smooth i t em of  the en ergy fun c tion  is define d  an d the graph  cut  method i s  u s ed to obtain  the global  op timal solu tio n ,  thereby opt imization  and  corre c tion o f   segm entation  re sult s a r e   reali z ed  an d  the vessel  wall ed ge  and  vessel  lume n is a c curate ly  locate d. Final ly compa r ing  with the man ual taggin g  re sults the valid ity of our algorithm is p r ove d .      2. Mean-shift Ultras ound Image Segmenta tion Me thod   Mean -shift co mputational  model is a n  e ffective  tool for analy s is in  f eature sp ace, it was  widely  used I n  many  co m puter vi sion   appli c ation s .  Mean -shift is a p r ob ability den sity grad ient  function  with  no pa ram e ters e s timation  algorith m , It along the  gra d i ent risi ng di re ction to find t he  peak of the  probability di st ribution. In  the kernel  density esti mati on, kernel fu nction generally  meets the  condition s:  () 2 , kd K pc p æö ÷ ç = ÷ ç ÷ ç èø ,where   ( ) ( ) 0 Kp p ³  calle d  ke rnel  fun c tion an d  p   rep r e s ent s  a sin g le pi xel in the  image  doma i n The  normalizatio n p o sitive con s tant   ψψ δ σ m es r s r sr L 3 Ts i n 2L L = is to  en su re  that ( ) Kp  integ r al  is 1. In  me an-shift meth od g a u ssi an   kernel   fun c tio n   an d uniform  kern el fun c tion is two  kind of com m only use d  kernel fun c tio n , le t  ( ) ( ) g pK p =- , k e rnel func tion  ( ) Gp  define  () 2 , gd Gp c g p æö ÷ ç = ÷ ç ÷ ç èø , and me an  shift vector i s  d e fined   as  follows ,  i p  is the sample p o int of the current pa rzen windo w.    () () () 2 1 , 2 1 n ii i hk n i i pg p h p h mp x gp ph = = æö ÷ ç - ÷ ç ÷ ç èø =- æö ÷ ç - ÷ ç ÷ ç èø å å  (1)      Mean -shift so lving step s in clud e two pa rts:      1) Cal c ul ation  of mean shift  vector  () , hk mp ;  2) According  to the  () , hk mp  value to transfo rm n u cle a r lo ca tion, this  proc ess  ens u res  to  conve r ge to  the poi nts tha t  neighb orh o ods  gra d ient  are  ze ro. Let   {} 1 , 2 , . .., j y jn =  is location  seq uen ce d u ring mean -shif t  proce s s, by the formula (1) ca n be got:      () () 2 1 ,1 2 1 ,1 , 2 , . . . n ii i ij n i i pg p p h yj gp p h = + = æö ÷ ç - ÷ ç ÷ ç èø == æö ÷ ç - ÷ ç ÷ ç èø å å  (2)      formula  (2 )  calcul ate  weig ht mean  valu e with  kern el  functio n  G  i n   , ij y  positio n,  whe r e   , ij y  is the initial position of kernel.   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   e-ISSN:  2087 -278X     Ultra s ou nd Im age Segm entation ba sed  on the Mean -shift and  Gra ph Cut s  Theo ry   (Y un Ting )  5602 Ultra s ou nd i m age  se gm entation m e thod b a sed  on me an-shi ft algorithm  can  be   descri bed  as: Firstly, the ultrasoni c im age can b e  rep r e s ente d  as a two-di m ensi onal g r id  in  three - dime nsi onal spa c e,  grid  spa c e i s  called  sp atial domai n, gray value sp ace al so  call ed  rang e dom ai n. Throu gh  searchin g for t he next sh ift point in the i m age  spa c e,  and set the stop   conditions, until the di splacement is l e ss than  a give n value, the n  tran slation i s  stopp ed. L e t  i x   and  i z  (i ＝ 1, 2,  …, n) are  re spectively the input  vector a nd the filter output re sults.    For the all d a ta points i x i ＝ 1 ,  2, …, n, mean-shift vector  ( ) , hk mx  of each  point are   cal c ulate d , accordi ng to the  () , hk mx  value tha t  moving win dow  cente r  to the next point. This  pro c e ss i s  repeate d  until  conve r gen ce to t he de nsity pea k o f  the data space, whe n  the   estimated  de nsity gra d ient  is ze ro, then  no need to  move, and a s sign the  pixel value  x P  to  i Z ,  that is  ix Z P = . i Z  is the filtered pi xel. The output im age consi s ts of m u ltiple indep ende nt  regio n s.  B a si c st ep s a r e a s  f o llow s :   1) Initialize  1 j =  and  1 ii y x =   2) A c cordi ng  to equ ation  (2), calculate ,1 ij y +  until converg ence, an d re cord  conve r g ence  value is  , ic y .  3)   As s i gn  () , , r ii s i c zx y = .  Thro ugh the  above three steps we get final re su lts  of mean -shift filter, wh ere  sup e rscript   s  and sub s cri p t  r  respe c tively rep r e s ent  spatial d o m a in and val u e ran ge. Usi ng mea n -shift  filtering meth od, need to set band width  vector  ( ) , hh s h r = .Band width can be  rega rded a s  the   resolution of  segm entation ,  bandwi d th is larger,  mo re details of t he image  will  be igno red,  how  to choo se the  appro p ri ate band width, is the key of  su ccessfully usi ng ke rnel d e n s ity function. In   this pap er rad i al gau ss  kernel functio n   is adopted for  ultrasoun d im age segme n tation.      3. Ultras oun d Image Segmenta tion O p timi zation  Bas e d On th e Graph  Cut  Theor y   Grap h cut al gorithm   is  a  global   optimi z ation   alg o rit h m, by u s in g  the  cla s s la bel a n d   con s tru c t ene rgy function, i t  convert ima ge se gmentat ion pro b lem i n to the probl e m  of minimizi ng   the ene rgy functio n . Un d e r the g u ida n ce  of  the  grap h cut theory, network is i ngeni o u sly  con s tru c ted,  and en ergy i s  linked to the netwo rk  ca pacity, lastly netwo rk flo w   prin ciple a b o u t  grap h the o ry  is ad opted  to  find the g r ap h minimu m cut, the cut i s   optimal  soluti on of the  ene rgy  function  mini mization  p r o b lem, be sid e s  the   imag e  se gmentatio n is complet ed. Graph  cut  algorith m  are  two thoug hts,  includ e swap  and  ex p an si on a .    A. Ultra s oun d Image Segmenta tion M odel Bas e d  On MRF   Image se gm entation app roach based  on the MRF  model can b e  seen a s  op timization   probl em s of acq u isitio n the label field   f  which ma ke energy function  ( ) Ef  minimization.  Energy fun c tion expre s sed  as follows:     () () () () {} () , , ,, s mo o t h d a t a p q p q p p i pP pq N Ef E f E f V f f D f w Î Î =+ = + åå  (3)      Whe r e  ( ) sm oo t h Ef  calle d smo o th en ergy, it is th e puni shm e n t  to the un-smoothne ss  cha r a c t e ri st ic s;   ( ) da t a Ef  kno w n  as the  data  item ene rg y, it is the  puni shm ent  to the  disa gre e ment  betwee n  cu rrent cla ss la b e l  f  and ob se rvation data   i w  class. For a gi ven image,  p  represent ea ch pixel,  P  is the set of all p i xels, all neig hbori ng pixel  pair  { } , p q  that c o ns titute   the set N . Where  () , , p qp q Vf f   use s  fou r  neigh bo rh ood Potts model  [10]:  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046     TELKOM NIKA  Vol. 11, No . 10, Octobe r 2013 : ISSN: 2302 -40 4 6   5603 () () ( ) , , s mo o t h p q p q p q Ef V f f f f ld == ¹ ,  l  is the  fact or to  bal an ce  the  data ite m  an d  smo o thing   item, each pi xel data item energy  () p p Df  in typ e  (3)  can b e  got by type (4):     () ( ) 2 11 ˆ ,e x p 2 2 i pi pp i w p i Df w f y dm ps æö æö ÷ ç - ÷ ÷ ç ç ÷ ÷ ç ç == - ÷ ÷ ç ç ÷ ÷ ç ç ÷ ÷ ÷ ç ç èø ÷ ÷ ç èø h  (4)      Whe r e  p d  repre s ent attrib ute  value of pixel  p  (su c h a s   gray value ) .  () ˆ i wp fd  r e pr es e n t   the probabilit y of pixel  p  bel ong s to the  category  i w . We  use th e mea n -shift metho d  to obtain  the initial ultraso und i m ag e se gme n tation, and  get  mean val u e s  and va rian ces of  w  cla s se s:   ( ) 12 1 2 ,, , , , ww qm m m s s s =L L , with ga uss  RBF  kernel f unctio n  (4)  g e t likelih ood   estimation  of  the   pixel  p  to the correspon ding  w  cla s s e s.   Wh ere  h  cont rol th e smo o thne ss ra nge  of fun c tion (4),  whe n  the va lue of  h is la rge, function  curve i s  mo re smo o th, b u t may lose  more d e tail  informatio n; The value of   h  is smaller,  function curve will  be m o re  sharper, that will over- relian c e  on t he ob se rvatio n data, then  the algo rith m  perfo rma n ce  will de gra d e .  In literature[ 5]  the meth od t o  e s timation   h   is given, su ch as  () ex p fr q n a md g æö ÷ ç ÷ =- ç ÷ ç ÷ ç èø h ,where   ( ) frq d  is the   occurre n ce freque ncy of  y  in the training  sampl e  set.     B.   Gra ph-Cu t Algorithm : S w a p  Algorithm Ideas   Thoug ht of th e swap  algo ri thm is  rep eat edly cal c ul ation two  differe nt categ o ri es  , ww ab ,  and g r ap h gri d  is  con s tru c t ed to a s soci a t e with en erg y  equation ( 3 )  in ord e r to  o b tain the o p timal  solutio n  of e q uation. Let  P  b e  the  set of a ll pixels,  whil e  P ab  is a pixel   points  set  wh ich  cla ss  belon g to  , ww ab ,   grid  con s truction as  sh o w n in fig u re   1, figure el ements  are: vertex set     {} ,, VS S P ab =- - , edge  set  {} {} {} , , ,, pp pq pP pq N tt e ab e Î Î ìü ïï ïï = íý ïï ïï î þ UU , where  , SS ab --  is two graph   ver t ex,  { 1 , 2 , 3 , ... , 1 2 } pp R= = , , p X a  in figure  1 represe n t pixel  p  label  to the  cla ss  w a  throug h  mean -shift method. Pixel  p  (satisfy   p fa =  or  p fb = ) in  ab R  respe c tively conne ct with two   ver t ic es   , SS ab --  th at co nstitute  t-lin k e dge s, de noted   by  , p p tt ab , and  th e ele m ents  among ab R  con s ti tute n-link ed ges, den oted  by  {} , p q e , the weight of t-link and n-lin k assi gnment   approa ch respectively se e equatio n(5 )  a nd equ ation(6 ) .    () () (, ) (, , ,) q qN p p q q qN p p q pp pp tV f p t Df w w Df w w Vf p a a ab ab b ab a a b b b Î ÏR Î ÏR =+ Î R =+ Î R å å  (5)     {, } (, ) { , } , p pq q eV p q fp q f ab =Î N Î R  (6)     Whe r e  p N  is a d j ace n t area o f  pixel  p , litera t ure[11] p r ov e the  capa cit y  of cut set i s :  CE K =-  (7 ). Where  E  is the  en ergy  value of  equa tion(3 ) ,  , ww ab  is a  con s tant, the   optimal   solutio n  of e nergy fu nctio n (3 ) is the  minima l cut set  of  g r ap h(1a). swap  al gorithm ra nd omly  sele ct  t w o  cla s s , ww ab  from  w  cla ss, an d  throug h th e ene rgy fu nction to  so lve th e   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   e-ISSN:  2087 -278X     Ultra s ou nd Im age Segm entation ba sed  on the Mean -shift and  Gra ph Cut s  Theo ry   (Y un Ting )  5604 corre s p ondin g  cut  set, the n  dete r mine t he pixel b e lo ngs to  which   cla ss  set, thu s  compl e te the   segm entation  optimization,  spe c if ically shown in Figu re 1a.    C.   Gra ph-Cu t Algorithm :  ex p an si on a  Algorithm Ideas  The swap  al gorithm ca n only  exch ang e  w a   w b  cla s s to  cal c ulate  of the minimu m   energy. If we limit  w b  and make  w a  exchan ge with all other cl asse s, then will get a broa de r  transfo rmatio n app ro ach, it is  ex p an si on a  algorith m . Literatu re[ 14] proved  when fo rmatio ns  of  smooth item  satisfy ‘metri cs’  con s train,  then  ex p an si on a  algo rithm idea s ca n be ad opte d  to   achi eve more broa der t r an sform a tion , as sh o w n  in figure 1b, a set of vertices  V,  {} {} , , ,s i n , , pq pq pq N ff Vs o u r c e k P Z aa Î ¹ ìü ïï ïï ïï =- - íý ïï ïï ïï î þ U  is the  com positio n ele m ents  of the graph,  wh ere   s ou r c e a - , sin k a -  re spe c tively the  highe st  and l o west v e rtice s .  p  is th e any  one  pix e l in  P ,  q  is adjacent pixels of  , pq ÎN . When the two pixel class la bel  p f and  q f  are unequal, the n   auxiliary nodes  {} , p q Z  a r e  adde d, Let  {} , ,, p q ab c Z Î are  th e auxilia ry n ode, a ddin g  t he a u xiliary  node  () 1, 3 2 , 1 , X aX  betwee n   1, 3 X  and  2, 1 X , as sh own in fig 1b,  similarly, there are a u xiliary nodes  () 4, 3 5 , 1 , X bX  and  () 7, 3 8 , 1 , X cX . Where  edge  set i s   {} {} {} () ( ) {} {} () ( ) ,, ,, ,, , pp pq pq pP pq N p q N di s p p d i s p q di s p p d i s p q tt e aa ex Î ÎÎ =¹ ìü ïï ïï ïï ïï ïï = íý ïï ïï ïï ïï ïï îþ UU U ,  {} , p q x are  the ed ges th at between  a u xiliary no de  {} , p q Z  with n ode s p , q , a . For exampl e  figure  1b  sh ows   that total thre e ed ge s of  c,   the ed ge   {} 73 , X c e  betwee n   c  and   73 X , the e dge   {} 81 , cX e  bet wee n   c  and  8, 1 X ; the edge  c t a  betwee n   c  and  a , similarly, auxiliary node  a  and  b  constru c t edge s with   their adja c e n t node s. the pixels of  P  resp ectively con n e cted  with  a  and  a  to c o ns truc t t-link   edge s, the pixels amon g P conne ct wi th each othe r to constitute  n-link ed ge s, edge weig h t s   assignm ent method is ex pre s sed by formul a (8 )  a nd (9 ), if existing auxiliary node  c, then  the   edge  weight  betwe en c a n d  adja c ent po ints ca n refe r to the followin g  formula (10 ) .    () () , , , pp i p p pp i p Df w w tp w Df w tp p tp a a a a a aa =¥ Î R =Ï Î =Î R  (8)        {, } () ,{ , } , pq pp q eV p f wf f q a =Î N =  (9)     {, } {, } () { , } , () { , } , (, ) { , } , , , pc cq p c p q qp q pq p q fw f f wf eV p q ef f ff f f Vp q tV p q a a a =Î N ¹ =Î N ¹ =Î N ¹  (10 )     Whe r e th e d e finition of d a ta item D  see form ula  (4), sm ooth it em  V  as sho w n in  formula (3). Literature [14] proved that the c u t-s e t capac i ty is      CE =   (11 )      whe r e E is obtaine d fro m  equation (3), then usi n g the metho d  of  ex p an si on a  to  optimally solv e the equatio n (11). The  steps of  ex p an si on a  algori t hm is: con s truct the netwo rk  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046     TELKOM NIKA  Vol. 11, No . 10, Octobe r 2013 : ISSN: 2302 -40 4 6   5605 sho w n in Fig u re 1b, pixel  set  R , Label is  the same d e finition as swa p  algorithm, f o r the  R  cla ss,   if the pixel  la bels a r e  a  a nd  a , then  set t-li nk  and  n - lin k edg es to fin d  the  minimu m graph   cut  set C, eq uiva lent to see k  t he minimu m energy  E ¢  whi c h co rre sp ondi ng to the cl ass label  L ¢ , if   condition  EE ¢ < is satisfied, then  modify the cl ass la b e l by the same mo de of swap  al gorithm,   and up date the cla s s set  of every pixel to  L ¢ .if  EE ¢ > ,then excha nge  a  to other cl ass  and   cal c ulate the  energy.        a    swa p   k si n s ou r c e t X 7 t X 4 t X 1 t X 3 t X 6 t X 9 t X 5 t X 8 t c t b t a t X 2   b  ex p an sion     Figure 1. Gra ph cut alg o rit h m prin cipl e diagram       4. Experimental Re sults    The expe rime nt of three ultrasoun d imag es is  sho w n i n  Figure 2     Then   varia n ce  an d co rrel ation coeffici ents ar e u s e d  for comp arison  of te st  results,   varian ce rep r esents  devi a tion deg ree  of the two bound ary p o ints, whil e the co rrel a tion   coeffici ents i ndicate simil a rity of two boun dar y sh ape. Firstly starting p o sit i ons in the t w o   boun dari e s  a r e cho s e, the n  two L  su b-seque nce ( 1 R an d 2 R ) with fixed l ength in t w o  curve s  a r e   taken,  The  si milarity of  1 R  an d  2 R  notes for  () 12 , L s im il R R , it depi cts  by  12 RR -  varianc e  , that   is  ( ) ( ) 12 1 2 , LL s im i l R R S E R R =- , whe r e variance  () ( ) 2 12 1 2 1 L Li i i SE R R R R m e a n L = éù -= - - êú ëû å ,  () 12 1 L ii i me a n R R L = =- å , L SE  is  smaller, t he  1 R  and  2 R  ar e mo re   s i mila r, w h er e   1 i R   rep r e s ent s the di stan ce  betwe en  sampling  poin t s on a  cu rve to the o r igin. Correla t ion   coeffici ents  L r  are ado pted for  ed ge co mpari s o n .  ( ) 12 12 , L Co v R R r dd = ,  ( ) 12 , Co v R R  rep r e s ent s  covari an ce  b e twee n  cu rve  1 R  and  curv e  2 R ,  1 d  and   2 d  re spe c tively de note the   sta ndard   deviation of  1 R  and  2 R ,     () () () 12 1 1 2 2 1 1 , n ii i Co v R R R R R R n = =- - å  (12 )     () 2 11 1 1 1 n i i RR n d = =- å ,  () 2 22 2 1 1 n i i RR n d = =- å  ,  1 R   2 R  rep r e s e n t the m ean   distan ce  of  all points o n  curves to the o r igin.   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   e-ISSN:  2087 -278X     Ultra s ou nd Im age Segm entation ba sed  on the Mean -shift and  Gra ph Cut s  Theo ry   (Y un Ting )  5606   a    b    c    d      a  b  c  d       a    b    c    d      Image 1 re sul t     Image 2 re sul t     Image 3 re sul t     Figure 2. Segmentation of ultras oun d im age s, First co lumns  (a): the  original ult r a s ou nd imag e s ;  S e con d  col u mns ( b ):  t h re e sna p s hot  f o r only   mean -shift segmenta t ion results; T h ird colum n s  (c): only the graph  cut algo rithm used to  get t he segm entation re sul t s. Fourth col u mns  (d):  Segmentatio n of our algo ri thm, using g r aph cut  re-se g mentation af ter mean -shift segme n tatio n   results, wh ere label 1 re prese n ts the ve ssel  wall a nd  label 2 re presents lume n of blood vessel.   The last row i n  Figure 2 is  comp ari s o n  chart  abo ut ab ove three ultraso und ima g e  segm entati on  results, blue li nes rep r e s ent s the medi cal  experts ha nd -label ed resul t s of vessel  cell and lume n   edge, the re d  line is the lab e ling re sult s of our algo rith m.      Next, true po sitive ratio (T rue po sitive ra tio, TP ), fals e-pos i tive ratio  (Fal se po siti ve ratio,  FP) an d total  simila rity de gree  (Simila ri ty, SI)  are a d opted, the s e  three i ndi cato rs  evaluate  the  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046     TELKOM NIKA  Vol. 11, No . 10, Octobe r 2013 : ISSN: 2302 -40 4 6   5607 tumor regio n   differen c e s  b e twee n the e x pert man ual  labeled  re sul t s and  our  al gorithm  calib rate   segm entation  result s [15]:    M S M A A TP A Ç = ， MS M M A AA FP A È- = ， M S M S A A SI A A Ç = È  (13 )     whe r e  S A  rep r e s ent s tumo r region  of ou r  algorith m  seg m entation,  M A  r e p r es en ts  the  docto rs man ually label tu mor a r e a ,  TP  is hig her, th a t  our  segm e n tation result s cover th e  highe r deg re e of expert  manual  calib ration area; F P  index is lo wer, the n  the  covered wro n g   area  is less;  SI index is  hi gher, th at ou r se gment atio n re sult i s   clo s er to the  ma nual la bel  are a .  In this pape r we defin e:    ( ) 2 wa l l l u m e n TP TP T P =+ ,  ( ) 2 w a ll lu m e n FP FP F P =+ ,  ( ) 2 w a ll lu m e n SI SI SI =+     Table 1 sho w s the sp ecifi c  experim ental para m eters a nd experi m en tal result s, includi ng   the  sel e ctio n threshold, an d  the comp arison  between  our  algo rith m and  man u a l se gme n tation  results, by calcul ating the  correlation  coeffici ent s an d varian ce of  the curve s  to comp are t h e   simila rity betwee n  them.  From th e ex perim ental   re sults  ca n b e   see n , ou r de sign ed al gorit hm  can  com p lete ly extract vascula r  lume n and a c curat e ly locate the  positio n of the vessel wall , it  has ex celle nt perfo rman ce i n  vascular ult r asoun d imag e segm entati on.      Table 1. Sele cted   coeffici e n ts and Expe rimental resul t s    The  h  of  equal(1)   The  of  equal(4)   vessel w a ll segmentation   comparison w i th  hand- labeling  vessel lumen  segmentation comparison  w i th ha nd-labelin g  TP  (% )  FP  (% )   SI  (%)   va r i a n c e   correlati on  coef ficien t   va r i a n c e   correlati on  coef ficien t   w a ll+  lumen   w a ll+  lumen   w a ll+  lumen   ultras oun d  image1   h =17   60 25.7  0.7789   13.2  0.8524   92.1  22.07   77.92   ultras oun d  image2   h =13  90  12.6  0.9121   8.4  0.9456   95.3  8.90  86.80   ultras oun d  image3   h =13  90  21.2  0.7833   11.8  0.9219   89.6  17.21   80.31       5. Conclusio n  and Futu r e  Work   This p ape r p r esents  a no vel vascular  ultrasoun d i m age  seg m e n tation meth od which   combi n ing m ean-shift an d  grap h cut al gorithm, fi rstly mean-shift algorith m  is  adopte d  for the   initial segm entation, then initial classification  re su lt s whi c h in clud e sp ecif i c  ch ara c t e ris t ic   para m eters o f  each cl ass  are obtai ned  according to   the histog ra m classification, sub s e que ntly  prob abili stic  model is u s e d  to const r u c t  data and smooth items  of energy fu nction, and t h e n   usin g g r aph   cut meth od t o  get the  opti m al solution  of the en ergy  function, th e r eby lo cating   th e   positio n of ve ssel wall an d  vessel lum e n, com pari s o n   with expert manual   segm entation re sul t s,  our al gorith m  achi eves va scular l o catio n  functi o n . O u r future work mainly in cl ude two aspe cts,  firstly how t o  accu rately  and effe ctively locate th e ultra s ou nd  vascular im age e dge  when  acq u isitio n effect of ultra s o und imag e are not we ll, se con d ly whe n  the amount o f  medical ima g e   data is too la rge, how to im prove  calcula t ion  spe ed of maximum flo w  metho d s a nd enh an ce the  grap h-cut rea l -time pe rformance for be tter adapt fo r  the division o f  ultraso und i m age s, these  will  be the focu s  of our future  work.           Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   e-ISSN:  2087 -278X     Ultra s ou nd Im age Segm entation ba sed  on the Mean -shift and  Gra ph Cut s  Theo ry   (Y un Ting )  5608 Referen ces   [1]  İş can Z ,  Kurn az MN. Ultra soun d Imag e  Segme n tatio n  b y  Us in g  W a velet T r ansform and  Se lf   Organiz i ng Ne ural  N e t w ork.  Neur al Infor m a t ion Proc essin g -Letters a nd  Review s . 20 06 , 10(8): 18 3- 190.   [2]  Yan S, Y uan  J P , Hou  CH. Se gmentati on  of  medic a l u l traso und  ima ges  ba sed o n  l e ve l se t method  w i t h   edg e repr ese n ting m a sk.  3 rd International Conference on Adv anc ed Com puter  T heor y  and  Engi neer in g (ICACT E). Chengdu,  Ch in a. 20 10; 2: 85-8 8 .  [3]  Kerman i  A, A y atoll ahi A. Med i cal Ultras o u n d   Image Segm e n tation  b y  M odi fied Loc al H i stogram R ang e   Image Metho d .   Biomed ical Sc ienc e an d Engi neer ing , 2 010,  3: 1078- 10 84.   [4]  Xi e J, Jian g Y,  T s ui H T . Se gmentati on of  Ki dn e y  F r om  Ultraso und Im ages Bas ed o n  T e xture an d   Shap e Priors.  IEEE Transaction on Medic a l Im aging . 20 05, 24(1): 53 9-5 5 1 .   [5]  Hélè ne  Ma, C a rdi nal  R, Me uni er J, et  al.  In travascul a r  Ultraso und  Image  Segm enta t ion: A T h ree - Dimens io nal  F a st-Marchi ng  Method  Bas e d  on  Gra y   Lev el  Distrib ution s .  IEEE Trans  On Medic a l  Im aging . 200 6, 25(5): 590- 60 2.  [6]  Grad y  L, F u n k a-le a G. Multi-lab e l ima ge  segm e n tatio n  for medica l ap plicati ons b a s ed on gr aph- theoretic  el ectrical  pote n tia l s.  Confer ence  o n  Comp uter V i si on  and  Math e m atical M e tho d s i n  Me dica l   and Bi ome d ica l  Image Ana l ysi s .  Pr ague, America. 20 04; 23 0-24 5.  [7]  Cremers  D, R ousso n M, D e riche  R. A R e vi e w  of  Statistic a l Ap pro a ches  to Lev el S e t  Segme n tatio n :   Integratin g Co l o r,  T e xt ure, Mo tion an d Sha p e .   Int.  J. Com put e Vision.  200 7; 72(2): 195- 21 5.  [8]  D y de nko I, Ja mal F ,  Bernard  O, D' hooge J.  A Leve l  Set F r ame w ork W i th  a Sha pe a nd M o tion Pr ior fo r   Segme n tatio n  and R e g i on T r ackin g  in Ech o c ardi ogra p h y .  Medic a l Imag e  Analysis . 2 0 0 5 ; 10(2): 16 2- 177.   [9]  Christodoulou CI,  Pattichis CS . T e xture Bas ed C l ass i ficatio n  of Ath e roscl e r otic Car o tid  Pl aqu es.  IEEE   T r ansaci on on  Medic a l Imagi n g . 2003; 2 2 (7): 902- 912.   [10]  Li Zhe ngz hou,  Liu M e i, Wan g   Huig ai, Ya ng  Y ang,  C h e n  Ji n, Jin Gan g . Gra yscale E d g e  De tection a n d   Image S egmentation Algorith m Based on M ean Shift.  T E L K OMNIKA Ind ones ian  Jo urn a l  of Electric a l   Engi neer in g . 2013; 11( 3): 141 4-14 12.   [11]  Jun Sun, Ya n W ang, Xiao ho ng W u , Xi aod ong Z h a ng, H ong ya n Gao.  A Ne w  Im age  Segme n tatio n   Algorit hm an d  It’s Applic ation  in lettuc e  o b j e ct segme n tati on.  T E LKOMN I KA Indon esia n Jour nal  of   Electrical E ngi neer ing . 2 012;  10(3): 55 7-5 6 3 .   [12]  Fjortoft R, Delignon Y, Piec z y nsk i  W. Unsupervis ed Class i fica tion of Radar Images Using Hidden  Markov Ch ai ns  and H i d den  Markov Ra nd o m  F i elds.  IEEE Transactio n  on Geosc i enc e  and R e mot e   Sensi n g . 20 03;  41(3): 675- 68 6.   [13]  Szeliski R, Z a b i n R, Scharst ei n D. A Compa r ative Stud y   of Energ y  M i nim i zation Meth od s for Markov  Ran dom F i e l d s   w i t h  Smoot h ness-Bas ed Pr iors.  IEEE Transactio n  on P a ttern Ana l ysis  and M a chi n e   Intelli genc e . 20 08; 30(5): 1 068 -108 0.      [14]  Bo y k ov Y, Ve ksler O, Z abi h R. F a st ap pro x imat e en e r g y  m i nim i zati on vi a gra p h  cuts.  IEEE   T r ansactio n s o n  Pattern Ana l ysis and Mac h i ne Intell ig ence .  2001; 3 3 (3): 1 81-2 00.   [15]  Mada bhus hi A ,  Metaxas  DN . Combin in g L o w - , Hig h-lev e l an d Empiric a l Dom a i n  Kn o w le dg e F o r   Automated Se gmentati on of  Ultraso nic Bre a st Lesi ons.  IE EE T r ansactio n s on M edic a l  Imag in g . 20 03;   22(2): 15 5-1 6 9 .     Evaluation Warning : The document was created with Spire.PDF for Python.