APLIKASI  METODE  LEVEL SET PADA SEGMENTASI GAMBAR ( APPLICATION OF   LEVEL SET METHOD  IN   IMAGE SEGMENTATION )

## RIANA
riananana@mail.ugm.ac.id
Abstrak; Pada tesis ini akan dibahas mengenai segmentasi citra yang merupakan bagian dari  pengolahan  citra  yang  digunakan  untuk  mendeteksi  garis  batas  (tepi)  suatu  obyek  pada  citra. Adapun pendekatan untuk deteksi garis batas (tepi) pada penelitian ini, yaitu dengan menggunakan model geodesic  active  contour .  Ide  utama  dari  model  ini  adalah  untuk  meminimumkan  energi fungsional  dengan  menggunakan  metode gradient  descent ( steepest  descent ),  yakni  dengan menggerakkan  kurva  sehingga  mencapai tepi  obyek  yang  akan  dideteksi.  Salah  satu  metode  yang banyak digunakan untuk menyelesaikan masalah perubahan kurva yaitu metode level set .
Kata kunci : Metode Level Set , Geodesic Active Contour (GAC), Segmentasi.
Abstract; In  this  thesis,  image  segmentation  in  the  image  processing  for  the  detection  of object  boundaries  will  be  discussed.  The  approach  of  edge  detection  by  geodesic  active  model  is one of methods for image segmentation based on the edge detection. The mean idea of this model is based  on  a  functional  of  energy  minimization  on  the  theory  of  curve  evolution,  the  functional  is minimized by a gradient descent (steepest descent) method, the level set is the most suitable method for solving problem of curve evolution.
Keywords : Level Set Method, Geodesic Active Contour (GAC), Segmentation.

## PENDAHULUAN
Beberapa tahun terkahir ini, penggunaan persamaan  diferensial  dalam  bidang  analisis citra menjadi salah satu topik penelitian yang menarik perhatian para peneliti, salah satunya yaitu segmentasi citra yang merupakan bidang terpenting  pada  bidang  pengolahan  citra. Segmentasi  merupakan  proses  membagi  citra ke dalam sejumlah region atau obyek. Adapun tujuan  utama  segmentasi  di  tesis  ini  adalah untuk  mendeteksi  keberadaan  suatu  objek pada sebuah citra. Algoritma segmentasi citra umumnya  didasarkan  pada  salah  satu  dari sifat  dasar  nilai  intensitas:  diskontinuitas  dan similaritas.
Diskontinuitas  merupakan  salah  satu algoritma  segmentasi  dengan  membagi  citra berdasarkan  perubahan  besar  pada  nilai intensitasnya  seperti  tepi  citra,  salah  satu pendekatan  diskontinuitas  yaitu  deteksi  tepi. Deteksi tepi ( edge detection ) pada suatu citra merupakan suatu proses yang bertujuan untuk menghasilkan  atau  mendeteksi  garis  batas ( boundary )  atau  tepi  dari  obyek  pada  citra. Suatu  titik ( , ) x y dikatakan  sebagai  tepi
( edge )  dari  suatu  citra  bila  titik  tersebut
mempunyai  perbedaan  intensitas  yang  tinggi dengan tetangganya artinya tepian citra adalah posisi  dimana  intensitas  piksel  dari  citra berubah  dari  nilai  intensitas  yang  rendah  ke nilai intensitas yang tinggi atau sebaliknya.
Salah  satu  metode  segmentasi  klasik yang  pertama  kali  diperkenalkan  pada  tahun 1998  yaitu Active  contour ( snake )  yang  juga sering  disebut deformable  models . Active contour menggunakan  prinsip  minimasi energi  untuk  mendeteksi  fitur  tertentu  dalam image . Pengguna harus memperkirakan kontur  awal initial  contour seperti  tampak pada Gambar  1, bentuk kontur awal dibentuk sedemikian  rupa  sehingga  bentuknya  hampir mendekati bentuk garis batas obyek. Selanjutnya, kontur akan tertarik kearah garis batas image karena  pengaruh  energi  internal yang dihasilkan oleh gambar tersebut.
Untuk mengatasi keterbatasan
segmentasi  dengan  model Active  contour di atas,  Casseles  memperkenal  model  deteksi tepi  yang  merupakan  pengembangan  dari model Active  contour ( snake )  yaitu  model Geodesic active  contour (GAC) yang menggambarkan  fungsi  energi  yang  terdiri dari  dua  komponen  yaitu  energi  internal  dan energi  eksternal.  Energi  internal  berfungsi untuk mengontrol kehalusan kurva, sedangkan  energi  eksternal  untuk  menarik kurva  ke  arah  batas  obyek.  Cara  kerja  model Geodesic active contour diadopsi dari metode analisis  pada  pergerakan surface , Geodesic active  contour meminimalkan  energi  pada model  dengan  cara  melakukan  pergerakan pada  kurva  yang  mempengaruhi  energi tersebut  sesuai  dengan  arah  vektor  normal. Vektor  kecepatan  ini  dipengaruhi  oleh besarnya  nilai  kurvatur  pada  titik  tersebut. Secara matematis, hal terebut bisa diformulasikan sebagai:
C N t     (1) dengan C adalah
kurva yang
direpresentasikan  sebagai  kontur, N adalah vektor  normal  kurva,  dan  adalah  fungsi kecepatan  ( speed  function )  pergerakan  kurva yang  bergantung  pada  kurvatur k pada sebuah titik. Untuk menjamin kekonvergenan pergerakan kurva tersebut, kecepatan pergerakan  kurva  juga  ditentukan  oleh besaran  yang  merupakan  fungsi  dari  citra, yang  biasanya  adalah  gradien.  Saat  kurva berada  di  daerah  dengan  nilai  gradien  tinggi, kecepatan  pergerakan  pada  posisi  tersebut akan  berkurang.  Oleh  karena  itu,  fungsi  ini biasa  juga  dikenal  sebagai Stopping  function
yang  biasanya  merupakan  fungsi  yang  secara smooth menurun  sesuai  dengan  besarnya gradien.
Salah satu metode penyelesaian masalah pergerakan  kurva  ( curve  evolution )  dan perubahan  topologi  pada  bidang  pengolahan citra  ( image  processing )  dilakukan  dengan menggunakan  pendekatan  numerik  yaitu metode level set . Metode level set ini, pertama kali  diusulkan  oleh  Osher  dan  Sethian  pada tahun  1988.  Konsep  dasar  dari  metode  ini adalah merepresentasikan kontur sebagai zero level set , dan untuk menyelesaikan segmentasi  dengan level  set secara  numerik dilakukan  dengan  mengggunakan  salah  satu pendekatan metode beda hingga yaitu metode upwind.

## METODE LEVEL SET
Level  set dari  fungsi f yang  bernilai real  dengan n variabel,  merupakan himpunan yang dapat ditulis seperti berikut:
1 2 1 2
{( , ,..., ) | ( , ,..., ) }, n n
C x x x f x x x c   (2)
artinya  sebuah  himpunan  dengan  nilai fungsinya merupakan konstanta c R  . Fungsi f seperti  pada  (2)  di  atas  dinamakan  fungsi level  set ,  ketika 0 c  maka  himpunan tersebut  dinamakan zero  level  set .  Pada dimensi    dua  metode level    set menjadi representasi  dari  kurva  tertutup , C dengan menggunakan u sebagai  fungsi level  set sehingga dapat ditulis
{( , ) | ( , ) }. C x y u x y c   (3)
Ide  utama  dari  metode level  set ini adalah  menganggap  kurva  ( curve )  sebagai zero  level  set dari  fungsi u dalam  ruang dimensi  yang  lebih  tinggi.  Pada  waktu  yang sama,  perubahan  dari  obyek  juga  diperluas dalam  ruang  yang  lebih  tinggi.  Jadi,  ketika fungsi level set berubah berdasarkan ketentuan  yang  ditentukan,  maka zero  level set juga  akan  berubah.  Sehingga  pada akhirnya  dapat  diperoleh  bentuk  dari  kurva. Misalkan  sebuah  kurva  tertutup ( , ), 0 C p t t  dengan p merupakan  parameter  kurva ( , ) p x y  dan t adalah  waktu,  pergerakan kurva tersebut dapat dipandang sebagai fungsi PDE berikut
( , ) ( , ) ( , ), C p t T p t N p t t    
 
Figure 1: Bentuk Kontur Awal
dengan  syarat  awal 0 ( , ), C x y  merupakan kecepatan pada arah vektor singgung ( tangent rate )  dan  merupakan  kecepatan  pada  arah vektor normal (\ normal rate ).
Pada  beberapa  bagian  dari  kurva , C nilai  dari y dapat  didefinisikan  sebagai fungsi dari . x Oleh sebab itu, kurva C dapat dituliskan sebagai fungsi dari x
( ) ( , ( )).
C x x x   Vektor  singgungnya  yaitu (1, ), x x C   sehingga unit vektor singgung dan unit vektor
normal  berturut-turut  yaitu
2 (1, ) (1, ) x x T    dan 2 ( ,1) . (1, ) x x N    
Ketika  kurva C bergerak  pada  setiap titik,  maka x dan y akan  berubah berdasarkan fungsi berikut
2 2 2 1 1 ( ), 1 1 1 x x x x x dy dt  
             (6) 2 2 2 1 1 ( ). 1 1 1 x x x x x dx dt                 (7)
Oleh karena itu, diperoleh 2 2 2 2 2 2 2 2 2 1 1 ( ) ( ) 1 1 1 ( ) 1
1 ( ) (1 ) 1 1
1 , x t t x x x x x x x x x x x x x x x dy dx dt dt dy dx dt dt                          
 
          
     
 
dengan  kata  lain,  pergerakan  kurva  hanya dipengaruhi  oleh  vektor  normal .  Jadi,
pergerakan kurva (2) dapat ditulis
. C N t   
 (8)
Selanjutya berdasarkan Persamaan (8) di atas,  akan  diturunkan  persamaan  pergerakan fungsi level  set u yaitu  dengan  menganggap
( ) C t sebagai  fungsi  \emph{zero  level  set}. Oleh  karena  itu, zero  level  set u yaitu ( , , ) 0. u x y t  Jika zero  level  set u diturunkan terhadap , t maka diperoleh
0 ( ) ( ) [ , ] ( , ) , t x t y t T t t u x u y u u x t y t t t u x u y u x t y t u x u y x y u x y u t C u t N u                                               dengan N adalah  vektor  normal  dan  unit vektor  normal  didefinisikan , | | u N u     sehingga diperoleh 2 | | ( ) | | | | . t u u u u u u u          
 
Jadi,  persamaan  pergerakan  fungsi level  set u yaitu
| | . u u t      (9)
Persamaan  (9)  inilah  yang  merupakan Persamaan level  set yang  pertama  kali diperkenalkan oleh Osher dan Sethian dengan
( , ) u u u x y       dan  adalah  fungsi kecepatan speed function yang hanya dipengaruhi oleh kelengkungan kurva ( curvature ), yaitu
k N   seperti pada Proposisi
3 . k      ‖ ‖ ‖ ‖
MODEL GEODESIC ACTIVE CONTOUR PADA FUNGSI LEVEL SET UNTUK MENDETEKSI TEPI MODEL

## GEODESIC ACTIVE CONTOUR
Model Geodesic Active  Contour (GAC) (Sapiro,  2009)  berawal  dari  model  Active contour ( snake ) yang pertama kali diperkenalkan oleh Kass yaitu   1 1 1 2 2 0 0 0 [ ] | ( ) | | ( ) | | ( ( ) | , E C p C p dp C p dp I C p dp             (12)
Selanjutnya,  jika 0   ,  dan  mengganti
I   dengan   2 g I  maka  Persamaan
(12) diatas menjadi 1 1 2 2 0 0 [ ( )] | ( ) | (| ( ( )) |) E C p C p dp g I C p dp             1 1 int ext 0 0 [ ( )] .
E C p E C p dp E C p dp             (13)
Model geodesic active contour akan diperoleh  melalui  Persamaan  (13),  dengan kata  lain  solusi  dari  Persamaan  (13)  yaitu merupakan  kurva  geodesic  (kurva  geodesik merupakan  salah  satu  istilah  pada  ruang Riemannian yang menujukkan jarak terpendek antara dua titik). Untuk menunjukkan hal ini, yaitu dengan menggunakan prinsip maupertuis (Dubrovin, 1992) diperoleh Persamaan (13) menjadi
        1 0 min 2 , m g I C q C q dq     (14)
karena 2 m  adalah  sebuah  konstanta, maka  tanpa  mengurangi  keumuman  dengan memilih 2 1 m   ,  maka  Persamaan  (14) menjadi
        1 0 min . g I C q C q dq   
(15)
Penulisan lain dari Persamaan (15) yaitu
        1
0
, R L g I C q C q dq    
(16) Untuk  meminimumkan  Persamaan  (16), akan  dicari  dengan  menggunakan  metode steepest  descent ( gradient  descent ).  Metode
gradient  descent ,  merupakan  salah  satu pendekatan  secara  iterasi  untuk  memperoleh pengekstrim  (peminimum  atau  pemaksimum) lokal suatu fungsi tujuan yang arah pencarian berdasarkan  pada  gradien  dari  fungsi  tujuan (Chong,  2001)  pada  masalah  ini  merupakan fungsional  pada  Persamaan  (14).  Adapun Gradien dari fungsional pada Persamaan (14) merupakan  Persamaan  Euler-Lagrange  yang merupakan  variasi  (turunan)  pertama  dari Persamaan  (16)  yang  diperoleh  berdasarkan kalkulus  variasi.  Berdasarkan  Lemma  dasar kalkulus variasi, maka
[( ( ) ) ( ) ] 0. g C N N g C kN    (17)
Persamaan (17) inilah merupakan
Persamaan  Euler  Lagrange  dari  (16), dengan k adalah Euclidean curvature dan N normal  vektor  kurva.  Jadi,  berdasarkan metode steepest descent untuk menggerakkan  kurva  awal 0 C kearah minimum lokal dari R L (16) maka haruslah pergerakan kurva berdasarkan persamaan
[ ( ) ( ( ) ) ]. t C g C kN g C N N   
(18)
Artinya,  kurva  bergerak  dengan  arah pergerakan  ( ( ) ) . g C N N   Persamaan (18) ini  menunjukkan  bagaimana  setiap  titik pada active  contour C harus  bergerak sehingga R L minimum.  Lebih  lanjut,  objek yang  terdeteksi  ketika  Persamaan  (6) mencapai  solusi steady  state yakni 0. t C  Selanjutnya  dengan  menambah  “energi konvergensi” pada Persamaan (18), sehingga Persamaan Geodesic active contour menjadi ( ) ( ) ( . ) , C t g c k N g N N t       (19)
dengan  menambahkan cgN ,  maka  kurva ( ) C t tidak  hanya  akan  bergerak  lebih  cepat ke  arah  tepi  objek  tetapi  juga  akan  tetap bergerka sekalipun 0. k 
MODEL

## GEODESIC
ACTIVE

## CONTOUR PADA FUNGSI LEVEL SET UNTUK MENDETEKSI TEPI
Untuk  mengimplentasikan  pendekatan deteksi  tepi  dengan  model Geodesic  active contour , maka Persamaan (19) akan direpresentasikan dengan menggunakan pendekatan  fungsi  level  set  (8).  Oleh  sebab itu,  jika  kurva , C bergerak  berdasarkan Persamaan  (2),  maka  model  Geodesic  Active Contour  pada  Persamaan  (19)  yang  akan digunakan untuk proses segmentasi menjadi,
( ) | | ( ) ( ) | | ( ) | | u u g I u div cg I u g I u t u           (20)
dengan c adalah  konstanta  positif  dan
( ), | | u k div u    sedangkan ( ) g I adalah fungsi
stopping  function yang  digunakan  untuk menghentikan  pergerakan  kurva  pada  saat mencapai  garis  batas  ( boundary )  objek  yang didefinisikan
1 . ˆ 1 | | g I    (21)
Artinya,  kurva C yang  bergerak  untuk mendeteksi  garis  batas  (tepi)  obyek  yang dimplementasikan  sebagai  fungsi u akan berhenti  ketika  sudah  mencapai  garis  batas (tepi) objek yaitu ketika 0 t u  .

## IMPLEMENTASI  NUMERIK  MODEL GEODESIC  ACTIVE  CONTOUR  PADA LEVEL  SET  UNTUK  SEGMENTASI GAMBAR
Untuk mendeteksi garis batas ( boundary )  objek  pada  suatu  gambar  ,  maka fungsi u pada  Persamaan  (20)  akan didiskritisasi  dengan  menggunakan  metode beda  hingga  (Aubert,  2002).  Oleh  karena  itu, diperoleh  diskritisasi  model geodesic  active contour pada Persamaan (20), yaitu
1 , n i j u   2 2 , , , , , ( ) ( ) n n n n i j i j i j x i j y i j u tg k u u      , , , [max( , 0) min( , 0) ] n i j i j i j tc g g u       (22) , , [max(( ) , 0) n n x i j x i j t g u    , , min(( ) , 0) ] n n x i j x i j g u   
, , [max(( ) , 0) n n y i j y i j t g u    , , min(( ) , 0) ] n n y i j y i j g u    dengan
2 2 2 2 , , , , , [ ( ,0) ( ,0) ( ,0) ,0) ], ( n n n n n i j x i j x i j y i j x i j u max u min u max u min u              
dan
2 2 , 2 2 3 2 ( ) . | | ( ) xx y xy y x yy x n i j x y u u u u u u u u
k div u u u       
Adapun  nilai  awal 0 ( , ) u x y ( zero  level set ) yaitu berupa lingkaran yang didefinisikan dalam  domain  gambar  dan  di  luar  obyek, yang  diperoleh  dengan  menghitung  jarak antara  setiap  titik  (piksel)  dengan  kurva 0 . C Karena 0 C adalah kurva tertutup, oleh karena itu  jika 0 C adalah  sebuah  lingkaran  dengan radius R dan titik pusat 0 0 ( , ) x y maka
2 2 0 0 0
( , ) ( ) ( ) . u x y x x y y R      (23)
Model geodesic active contour yang digunakan untuk mendeteksi keberadaan garis batas  ( boundary )  gambar  yaitu  Persamaan (20)  yang didiskritisasi dengan menggunakan metode  beda  hingga  sehingga  diperoleh Persamaan  (22).  Selanjutnya,  solusi  iteratif untuk  mendeteksi  tepi  dapat  diperoleh dengan  menggunakan software matlab  2010a dengan langkah-langkah sebagai berikut:
1. Menginput  gambar  yang  akan  akan disegmentasi  dengan  format  .jpg  atau .png.
2. Mengubah  gambar  menjadi gray  scale (hitam putih) jika gambar yang dimasukkan berwana (RGB).
3. Menentukan parameter , c k dan time step
( t  ).
4. Mendefinisikan  kurva  awal  ( 0 ( , ) u x y ) yang  diletakkan  di  luar  obYek  yang  akan di deteksi
5. Melakukan  evolusi  pada  fungsi level  set (22)
6. Menggambar Fungsi Level set
7. Menggambar Zero Level set
Untuk  mendapatkan  hasil  segmentasi yang  baik,  ada  lima  parameter  yang  harus ditentukan  dengan  tepat  dan  hati-hati  yaitu
, _ , _
, c delt t re init iterations dan . k Untuk simulasi  yang  pertama  pada  objek  yang tunggal dipilih 3, 0.01, 2000, _ 50 t c delta iteration re init    
dan 5. k  Sehingga  dengan  menggunakan software Matlab seri 2010a diperoleh sebagai berikut
Untuk  simulasi  yang  kedua  yaitu  pada objek ganda dipilih 5, 0.01, 1540, _ 20 t c delta iteration re init     dan 5. k  Sehingga  dengan  menggunakan software Matlab seri 2010a diperoleh sebagai berikut

## REFERENSI
Aubert, G., Kornprobst, P., 2002, Mathematical Problems in Image Processing: Partial Differential Equations and the Calculus of Variations , Springer-Vcrlag New York. Chong, K.P.E., Zak, H.S, 2001, An
Introduction  To  Optimization  Second Edition , Wiley Canada.
Dong,  Y.,  Xin  Xu,  Zhao,  Q.,  2012,
Application  Of  Level  Set  Method  In Image Segmentation , Elsevier, 6 Oktober 2012.
Dubrovin,  B.A,  Fomenko,  A.T.,  Novikop, S.P.,  1992, Modern  Geometry  Method and Application Part. I The Geometry Of
Surface,  Transformation  Groups,  and Fields Second Edition , Springer. Sapiro, G., 2009, Geometri Partial Differential Equation An Image Analysis , Cambridge University Press.
Figure 2: Proses Segmentasi Gambar
Figure 3: Proses Evolusi Level Set dan Zero Level Set