Pemisahan Objek-Objek Berbasis Region pada Citra Digital dengan Metode Normalized Cuts
Marsani Asfi Program Studi Sistem  Informasi Sekolah Tinggi Manajemen Informatika dan Komputer  CIC Cirebon Jl.Kesambi 202, Kota Cirebon, Jawa Barat.Tlp : (0231)220250. E-mail : marsani.asfi@cic.ac.id

## Abstrak
Citra atau gambar terdiri dari karakteristik visual seperti warna, bentuk dan tekstur. Salah satu cara untuk mendapatkan karakteristik citra visual adalah melalui segmentasi. Secara umum, segmentasi adalah  langkah  pertama  dalam  analisis  citra.  Segmentasi  dilakukan  untuk  membagi  gambar  aau  citra menjadi  bagian-bagian  yang  memiliki  karakteristik  serupa.  Metode  Normalized  Cuts  yang  digunakan dalam  penelitian  ini  menerapkan  teori  graf  untuk  membagi  gambar  atau  citra  ke  ukuran  yang  terbaik. Hasil penelitian menunjukkan bahwa citra tersegmentasi merupakan perwakilan dari objek yang dimiliki oleh  gambar  atau  citra.  Hasil  pemisahan  daerah-daerah  lebih  lanjut  dari  gambar  atau  citra  dapat digunakan  menjadi  referensi  untuk  penelitian  lebih  lanjut  pada  tahap-tahap  ekstraksi  fitur  citra, pelalabelan gambar atau citra dalam sistem temu kembali citra.
Kata Kunci : Citra, Segmentasi, Normlisasi Cuts, wilayah, objek, temu kembali citra.

## Abstract
Pictures or images that consist of visual characteristics of color, shape and texture. One way to obtain a visual image characteristic is through segmentation. In general, segmentation is the first step in image  analysis.  Segmentation  is  to  divide  the  image  into  parts  that  have  similar  characteristics Normalized Cuts method to apply graph theory to divide the image into the best size. The results showed that the segmented image is representative of the objects owned by the image. The result of the separation region into further regions of the images can be a reference for further research on the stages of image feature extraction, labeling the image in image retrieval systems.
Keywords : Image, Segmentation, Normalized Cuts, region, object, image retrieval.

## 1. Pendahuluan
Perkembangan  internet  dan  banyaknya  aplikasi  multimedia  saat  ini,  menyebabkan  pengguna sulit  untuk  mendapatkan  citra  yang  tersimpan  dalam  komputer.  Citra  memiliki  subjek  dan  objek  citra. Subjek  citra  merupakan  persepsi  umum  pengguna  terhadap  objek-objek  yang  dimiliki  citra.  Pada  citra digital  yang  didalamnya  terdapat  objek  gunung,  air,  pepohonan,  dan  burung  merupakan  suatu  bentuk kemampuan manusia untuk mengenali objek-objek pada gambar. Kemampuan tersebut tidak terlepas dari pengalamannya  melihat  berbagai  jenis  gambar  sehingga  mampu  membedakan  objek  yang  satu  dengan yang  lain.  Hubungan  satu  objek  dengan  objek  lainnya  akan  menjelaskan  tema  gambar  atau  melakukan penafsiran  ( interpretation )  gambar.  Gambar  atau  citra  memiliki  karakteristik  visual  yang  terdiri  dari warna, bentuk dan tekstur. Pengenalan pada tahap karakteristik visual disebut dengan persepsi. Persepsi adalah  tanggapan  (penerimaan)  langsung  terhadap  sebuah  objek  berupa  karakteristik  visual  tanpa melakukan  interpretasi.  Salah  satu  cara  untuk  memperoleh  karakteristik  visual  citra  adalah  melalui segmentasi (Sebe and Lew, 2000).
Secara umum, segmentasi merupakan langkah awal dalam analisis citra. Segmentasi dilakukan untuk membagi  citra  ke  dalam  bagian-bagian  yang  memiliki  kemiripan  karakteristik  (Gonzales  and  Woods, 2002).  Dalam  tulisan  ini  akan  dipaparkan  salah  satu  metode  segmentasi  berbasis region yang  akan dipergunakan untuk mengidentifikasi objek-objek.
Hasil penelitian dengan menggunakan metode Normalized Cuts telah dilaksanakan dalam sistem
124
temu kembali citra menggunakan Fuzzy C-Means yang menunjukkan hasil 86.68% (Asfi Marsani, 2008). Sedangkan untuk ruang lingkup pemabahasan dalam tulisan ini mencakup : 1. Objek citra yang digunakan adalah citra berwarna.
2. Segmentasi citra berbasis region.
3. Subjek citra terdiri dari subjek pemandangan.
4. Pembagian region sebanyak 6 region
2. Tinjauan Pustaka
2.1 Segmentasi Citra
Secara umum, segmentasi merupakan langkah awal dalam analisis citra. Segmentasi dilakukan untuk membagi citra ke dalam bagian-bagian yang memiliki kemiripan karakteristik (Gonzales & Woods, 2002). Besarnya tingkat pembagian tergantung pada masalah yang dihadapi. Proses segmentasi harus berhenti pada saat suatu objek dalam suatu aplikasi telah dianggap terpisahkan.
2.2 Normalized Cuts.
Metode Normalized Cuts menerapkan teori graf untuk membagi citra ke dalam ukuran terbaik. Dalam Gambar 1 citra dalam Normalized Cuts dipandang sebagai suatu graf yang saling berhubungan secara penuh ( Fully-connected graph) . Setiap piksel merupakan node untuk graf. Hubungan menyatakan keterkaitan dalam graf antara pasangan piksel yang dinotasikan dengan p dan q. Masing-masing edge memiliki biaya pq C (Shi and Malik, 2000).
Gambar 1. Citra sebagai suatu graf dalam Normalized Cuts.
Proses segmentasi citra berdasarkan graf adalah proses memecah graf-graf menjadi suatu segmen (Gambar 2). Proses tersebut dilakukan dengan menghapus semua edge yang memotong di antara segmen citra atau edge-edge yang memiliki biaya terkecil. Semua piksel yang memiliki kemiripan akan digabungkan dalam segmen yang sama (Shi and Malik, 2000).
125
Gambar 2. Graf Citra setelah di Segmentasi.
Proses pemotongan edge dilakukan untuk membuat graf-graf tersebut menjadi tidak terhubung (Gambar 3). Nilai biaya pemotongan edge dinyatakan dengan persamaan (1) (Shi and Malik, 2000) :
    B q A p q p C B A Cut , , ) , ( (1)
Gambar 3. Ilustrasi Pemotongan dalam Normalized Cuts
Proses pemotongan graf dilakukan untuk menghasilkan segmen terbesar. Dalam Normalized Cuts (Ncut) proses pemotongan ini diperbaiki dengan menormalkan ukuran dari segmen dengan cara menggunaakan persamaan (2) (Shi and Malik, 2000) :
) ( ) , ( ) ( ) , ( ) , ( B volume B A Cut A volume B A Cut B A Ncut  
(2)
dengan volume(A) dan volume(B) adalah jumlah biaya untuk semua edge yang ada dalam segmen A dan segmen B.

## 3. Citra Sumber
Citra sumber penelitian diperoleh dari web ALIPR (http://www.alipr.com) yang berisi informasi citra-citra  yang  sesuai  dengan  subjek  serta  objek  yang  terkandung  dalam  kamus  kata  (tabel  1) . Citra sumber  digunakan  sebagai  data  pelatihan  dan  data  pengujian.  Citra  pelatihan  digunakan  untuk pembentukan basis data ciri. Basis data ciri ini menjadi rujukan awal proses penemuan kembali citra saat diujikan. Citra sumber terdiri atas topik-topik atau subjek citra yang berhubungan dengan pemandangan, bangunan, alam, hewan.
Citra  sumber  di- segmentasi menggunakan  metode Normalized  Cuts (J.  Shi  &  J.  Malik,2000). Metode Normalized Cuts merupakan segmentasi berbasis region yang menghasilkan sub citra – sub citra. Sub  citra  tersebut  dinamakan  dengan region .  Dalam  penelitian  ini  digunakan  enam region untuk  setiap citra  sumber.  Beberapa  citra  sumber  kemudian  di segmentasi sehingga  diperoleh region-region yang bersesuaian. Pembentukan region-region ini dimaksudkan untuk  mendapatkan objek  yang terdapat pada citra.
Masing-masing region pada  citra  sumber,  kemudian  dilakukan  pemisahan region dari  citra utama.  Pemisahan  ini  dilakukan  untuk  mempermudah  mendapatkan  ciri  masing-masing region yang diasumsikan sebagai  ciri objek. Pemisahan setiap region dari citra sumber dilakukan  melalui pemberian tanda tertentu untuk area tertentu . Tanda yang dimaksud adalah dengan pemberian warna putih untuk area diluar target area yang dimaksud. Ukuran citra yang dihasilkan tetap sesuai dengan citra hasil praproses awal yaitu 50 x 50, tapi untuk area yang dihasilkan dalam pembentukan region ini tidak memiliki format ukuran yang standar.
4. Tahapan Identifikasi Objek
Pada  diagram  1  diatas  citra  sumber  disegmentasi  menggunakan  metode Normalized  Cuts (Shi  and Malik,  2000).  Metode Normalized  Cuts merupakan  segmentasi  berbasis region yang  menghasilkan  sub citra.  Sub  citra  tersebut  dinamakan  dengan region .  Dalam  penelitian  ini  digunakan  enam region untuk setiap citra sumber.
126
SEGMENTASI REGION DENGAN
NORMALIZED CUTS CITRA DENGAN REGION PEMISAHAN REGION REGION-REGION TERPISAH CITRA SUMBER IDENTIFIKASI OBJEK DENGAN NORMALIZED CUTS
Diagram 1.  Alur Metodologi Identifikasi Objek Citra
Beberapa  citra  sumber  kemudian  di  segmentasi sehingga  diperoleh region-region yang bersesuaian.  Pembentukan region-region ini  dimaksudkan  untuk  mendapatkan  objek  citra.  Dalam implementasinya proses segmentasi ini berisi 2(dua) modul utama, yaitu : modul segmentasi dan modul pemberian identitas region.
Masing-masing region pada  citra  sumber,  kemudian  dilakukan  pemisahan region dari  citra utama.  Pemisahan  ini  dilakukan  untuk  mempermudah  mendapatkan  ciri  masing-masing region sebagai ciri objek. Pemisahan setiap region dari citra sumber dilakukan  melalui pemberian tanda tertentu untuk area tertentu . Tanda  yang dimaksud adalah  dengan pemberian warna putih untuk area diluar target  area yang dimaksud.  Ukuran citra  yang dihasilkan tetap sesuai dengan citra  hasil praproses awal  yaitu  50 x 50,  tapi  untuk  area  yang  dihasilkan  dalam  pembentukan region ini  tidak  memiliki  format  ukuran  yang standar.
Untuk proses berikutnya dilakukan pembentukan modul. Modul-modul ini kemudian dapat digunakan mendukung tahapan penelitian dalam bagian sebelumnya. Beberapa modul identifikasi Objek Citra, diantaranya :

## A.  Modul Segmentasi.
Citra sumber disegmentasi menggunakan metode Normalized Cuts (Shi & Malik, 2000). Metode Normalized Cuts merupakan segmentasi berbasis region yang menghasilkan sub citra. Sub citra tersebut dinamakan  dengan region .  Dalam  penelitian  ini  digunakan  enam region untuk  setiap  citra  sumber. Beberapa  citra  sumber  kemudian  di  segmentasi  sehingga  diperoleh region-region yang  bersesuaian. Pembentukan region-region ini dimaksudkan untuk mendapatkan objek citra.
Modul  ini  bekerja  dengan  memanfaatkan  algoritma Normalized  Cuts untuk  segmentasi.  Hasil akhirnya akan terbentuk region-region pada citra sumber. Secara umum algoritma segmentasi Normalized Cuts seperti berikut (Shi and Malik, 2000) : Tahapan-tahapan Normalized Cuts, diantaranya :
1. Mendefinisikan sekumpulan matrik dari citra yang akan di segmentasi
2. Menentukan  bobot  graph  G=(V,E),  dimana  masing-masing  pixel  diperlakukan  sebagai  suatu  node dan  keterhubungan  masing-masing  pixel  sebagai  suatu  edge.  Bobot  pada  edge  menyatakan kemungkinan antara dua pixel termasuk dalam suatu objek. Bobot edge graph yang menghubungkan dua node i dan j dapat dinyatakan dengan persamaan 3:
 
          lainnya r X X jika e F F e w j i X X I j i ij X j i 0 2 ) ( ) ( 2 2 2 ) ( ) ( 2 2 2 ) ( ) (  
(3) 3. Menghitung untuk nilai eigen vektor dengan nilai eigen terkecil dengan persamaan 3: Dy y W D    ) ( (3)
127
4. Mempartisi graph menjadi 2 bagian berdasarkan nilai eigen vektor terkecil kedua.
5. Setelah  dua  graph  terbagi  jadi  2  bagian,  jalankan  kembali    algoritma  untuk  kedua  bagian  yang terpartisi secara rekursif.
6. Jika  NCuts  untuk  setiap  segmen  >  nilai  maksimum  dari  Ncuts  yang  didefinisikan  maka  proses dihentikan.

## B. Modul Pemberian Identitas Region
Modul  ini  dilakukan  untuk  memberikan  identitas  pada  setiap  region  yang  terbentuk.  Region-region hasil segmentasi diberikan identitas berupa nomor urut dari 1 sampai dengan 6, sesuai dengan banyaknya region yang diinginkan.
Algoritma pemberian identitas region adalah :
1. Membaca setiap piksel region yang terbentuk
2. Melakukan perulangan sebanyak region yang diinginkan.
3. membaca Identitas region
4. Kemudian, memetakan hasil pembacaan region tersebut ke setia region yang terbentuk.

## 3. Hasil dan Pembahasan
Citra sumber pada gambar 4 diambil dari beberapa sumber diinternet. Tema citra sumber secara umum  berasal  dari  tema  pemandangan.  Dalam  implementasinya  metode  ini  dapat  diterapkan  untuk beberapa tema citra. Citra sumber ini mengandung objek-objek yang terkait  dengan Citra pemandangan seperti awan, air, rumput, hewan, matahari dan tumbuhan.
Gambar 4. Citra Sumber
Citra sumber pada gambar 4, kemudian di  segmentasi dan  hasil  segmentasi  berbasis regionnya terlihat seperti pada gambar 5.
128
Gambar 5. Citra hasil segmentasi
Gambar 6. Citra Sumber dengan hasil Pemisahan berdasarkan region
Hasil citra tersegmentasi kemudian dilakukan pemberian identitas region. Pemberian identitas ini terlihat pada salah satu citra segmentasi seperti pada gambar 7.
Gambar 7. Citra teridentifikasi dengan id region
Citra-citra  teridentifikasi  kemudian  dilakukan  pemisahan  region.  Pemisahan  region  dilakukan untuk  menggambarkan objek-objek  yang dimiliki  citra. Sebagai contoh citra pada gambar 6, pemisahan region yang dilakukan adalah seperti gambar 8.
129
Gambar 8. Citra-citra region hasil  pemisahan region
Citra-citra  sumber  yang  telah  dilakukan  pemisahan  berdasarkan  region  kemudian  dapat dikelompokkan kedalam objek-objek tertentu. Seperti terlihat pada Tabel 1.
Tabel 1. Pengelompokan Region Citra SUBJEK CITRA REGION CITRA Pemandangan
Rumput Awan langit
Citra-citra  region  kemudian  disimpan  menjadi  file-file  citra  region.  Citra  region  ini  dapat digunakan untuk penelitian selanjutnya.

## 4. Usulan Penelitian Lanjutan
Segmentasi  citra  merupakan  tahapan  awal  dalam  sistem  temu  kembali  citra.  Pemisahan  region yang  telah  dilakukan  pada  bahasan  selanjutnya  dapat  digunakan  untuk  beberapa  penelitian  selanjutnya yang berkaitan dengan sistem temu kembali citra. Penelitian lanjutan dapat berupa : 1. Pembentukan  ontology  citra  yang  berkaitan dengan  subjek citra  berdasarkan objek-objek citra  hasil segementasi, usulan skema dapat dilihat seperti gambar 9.
2. Penentuan  persepsi  pengguna  terhadap  citra  yang  terkandung  dalam  objek-objek  citra  hasil segmentasi.
3. Pelabelan  otomatis  terhadap  objek-objek  yang  telah  dilakukan  pemisahan  menjadi  sub  region  –  sub region.  Dengan  pelabelan  otomatis  pada  citra  maka  pencarian  terhadap  citra  dapat  lebih  mendekati persepsi dari pengguna. Usulan skema seperti gambar 10.
130
Gambar 9. Skema usulan Ontology Citra
Gambar 10. Usulan Hasil untuk Pelabelan Otomatis Citra

## 5. Kesimpulan
Penelitian ini mencoba memaparkan salah satu metode untuk segmentasi berbasis region. Hasil penelitian menunjukkan bahwa citra yang tersegmentasi dapat digunakan untuk mewakili objek citra. Penelitian  lanjutan  yang  berkaitan  dengan  Temu  kembali  citra  dapat  menggunakan  hasil  dari identifikasi  objek  yang  dilakukan.  Hasil  identifikasi  objek  menunjukkan  bahwa  hasil  pemisahan objek perlu diidentifikasi dan diperbaiki kembali sehingga diperoleh bentuk objek yang bersesuaian.

## 6. Saran
Beberapa saran untuk pengembangan lebih lanjut diantaranya : sampai saat ini belum ada teknik segmentasi citra yang dapat melakukan segmentasi dengan baik. Oleh karena itu, disarankan untuk dapat memperbaiki  hasil  segmentasi  sehingga  ketidaksesuaian  dengan  objek  yang  diinginkan  dapat diminimalisasi.  Penelitian  selanjutnya  dapat  dikembangkan  untuk  penelitian  sistem  temu  kembali  citra berdasarkan ciri warna, bentuk, dan tekstur untuk melengkapi hasil temu kembali.

## Daftar Pustaka
[1] Asfi  Marsani,  2008.  Pelabelan  Otomatis  Citra  menggunakan  Fuzzy  C-Means  Untuk  Sistem  Temu Kembali  Citra[Tesis].  Bogor:Fakultas  Matematika  dan  Ilmu  Pengetahuan  Alam,  Institut  Pertanian Bogor.
[2] Asfi  Marsani,  2010.  Pelabelan  Otomatis  Citra  menggunakan  Fuzzy  C-Means  Untuk  Sistem  Temu Kembali Citra. Jurnal  SISKOMTEL, Volume 1 No. 1,hal 18-27. ISSN:2087-2445. STMIK CIC.
131
[3] Benjamins  V.R,  P´erez.  A.  G.  2004.  Knowledge  System  Technology:  Ontologies  and  Problem- Solving Methods. Website. www.swi.psy.uva.nl/usr/richard/ pdf/kais.pdf [15 Januari 2008].
[4] Brodatz.  1966.  Textures:  A  Photographic  Album  for  Artists  and  Designers.  http://www- dbv.informatik.uni-bonn.de/image/segmentation.html. [15 Oktober 2007].
[5] Gonzales RC, Woods RE, 2002. Digital Image Processing. Edisi ke-2. New Jersey: Prentice Hall, Inc.
[6] Sebe N, Lew NS, 2000. Robust Computer Vision : Theory and Application. Leiden : Leiden Institue of Advance Computer Science.
[7] Shi  J,  Malik  J.  2000. Normalized  Cuts and  image  segmentation. IEEE  Transactions  on  Pattern Analysis and Machine Intelligence . 22:8:888-905.
[8] Schober,  Jean-Pierre.  Thorsten  Hermes,  Otthein  Herzog.2004.  Content-based  Image  Retrieval  by Ontology-based Object Recognition . TZI Center for Computing  Technology Universitätsallee . 21-23 28359. Bremen, Germany.