DETEKSI TEPI OBYEK PADA CITRA DIGITAL MENGGUNAKAN gvf SNAKE

d

Ririen Kusumawati

Jurusan Teknik Informatika, Fakultas Sains dan Teknologi Universitas Islam Negeri (UIN) Malang. Email: rr_kusumawati@yahoo.com

Abstract – Edge detection of an image is one of the important elements in digital image processing system, because this edge detection process result will be needed in the next process in digital image processing system. Edge detection using snake or active contours is conducted to find out the object’s existence in a closed contour on an image. The main problem in snake applications is an initialization and convergence technique, especially for object edges that shape concave.

This thesis develops object’s edge detection software on digital image using GVF snake with Borland Delphi 5.0. Using Gradient Vector Flow Snake (GVF) technique and snaxel control technique in deformation process / snake movement obtains a snake movement visualization which comes close to the real object’s edge and convergent to the smaller iteration number. The edge detection accuracy result of this software has been tested by Maximum Radial Error (MRE) method and Root Mean Square Error (e_rms), which shows the average difference of snake edge and the real object’s edge.

A series trial obtains object’s edge detection result which is appropriate with the target object on image. Utilizing GVF snake, snaxel control technique on snake deformation, parameter setting selection, and an exact snaxel initialization influences the accuracy and the speed of snake movement to go in the direction of the target object’s edge on digital image.

Keywords            :     Edge detection, Snake, Gradient Vector Flow Snake, Snake Deformation, Maximum Radial Error, Root Mean Square Error.

Abstrak – Deteksi tepi suatu citra merupakan salah satu bagian yang penting dalam bidang sistem pengolahan citra digital, karena hasil dari proses ini nantinya diperlukan dalam proses selanjutnya dalam sistem pengolahan citra digital.  Deteksi tepi dengan snake atau kontur aktif dilakukan untuk mengetahui keberadaan obyek dalam kontur tertutup pada suatu citra.  Masalah pokok dalam pengaplikasian snake adalah teknik inisialisasi dan konvergensi, terutama untuk tepi-tepi obyek yang membentuk cekungan. 

Dalam tesis ini dikembangkan perangkat lunak deteksi tepi obyek pada citra digital menggunakan GVF snake dengan Borland Delphi 5.0.  Dengan menggunakan teknik Gradient Vector Flow Snake (GVF snake) dan teknik kontrol snaxel pada proses deformasi / pergerakan snake diperoleh tampilan visualisasi pergerakan snake yang dapat mendekati tepi obyek yang sesungguhnya dan konvergen dengan jumlah iterasi yang tidak terlalu besar.  Ketepatan hasil deteksi tepi yang dilakukan oleh perangkat lunak ini telah diuji dengan metode Maximum Radial Error (MRE) dan Root Mean Square Error (e_rms), yang mana menunjukkan rata-rata selisih tepi snake dengan tepi obyek yang sesungguhnya.

Dari serangkaian proses pengujian didapatkan hasil deteksi tepi yang sesuai dengan obyek yang diinginkan pada citra.  Penggunaan GVF snake, teknik kontrol snaxel pada deformasi snake, pemilihan setting parameter serta inisialisasi snaxel yang tepat mempengaruhi ketepatan dan kecepatan pergerakan snake menuju tepi obyek yang diinginkan pada citra digital.

Kata Kunci :  Deteksi tepi, Snake, Gradient Vector Flow  Snake, Deformasi snake, Maximum Radial Error, Root Mean Square Error.

1. pendahuluan

Deteksi tepi dengan snake atau kontur aktif (active contours) dimaksudkan untuk melakukan pengenalan obyek dengan memanfaatkan bentuk kontur yang ada.  Proses deteksi dilakukan untuk mengetahui keberadaan obyek dalam kontur tertutup pada suatu citra. Kontur aktif dibentuk dari kurva-kurva yang bergerak pada citra untuk mencari tepi suatu obyek.

Masalah pokok yang dihadapi dalam pengaplikasian snake adalah inisialisasi snake, dan konvergensi. Proses inisialisasi, pada umumnya dilakukan sedekat mungkin dengan batas-batas obyek yang sesungguhnya, jika hal tersebut tidak dilakukan maka akan didapatkan hasil yang salah / snake tidak berada pada tepi obyek yang dituju pada suatu citra. Masalah kedua dari aplikasi snake ini  adalah terbatasnya kemampuan gaya memusat (convergence) untuk penentuan cekungan (concave boundary region)  pada tepi obyek.

Pada kesempatan kali ini akan dibahas salah satu dari proses pengolahan citra yaitu deteksi tepi citra dengan kontur aktif menggunakan Gradient Vector Flow (GVF snake) sebagai gaya eksternal (external forces). Citra input yang dipakai merupakan citra biner, citra grayscale atau citra warna dengan obyek tunggal di dalamnya.  Dengan melakukan modifikasi model gaya external (GVF snake) dan teknik deformasi (pergerakan) snake pada teknik deteksi tepi citra ini diharapkan dapat menampilkan visualisasi pergerakan snake yang dapat mendekati tepi obyek yang sesungguhnya dan konvergen dengan jumlah iterasi yang tidak terlalu besar (waktu komputasi yang kecil).

2. Active Contours (Snake)

Kontur aktif (snake) merupakan suatu kurva yang didefinisikan dalam suatu citra asal yang dapat bergerak di bawah pengaruh gaya internal (internal force) yang datang dari dalam kurva itu sendiri dan gaya eksternal (external force) yang dihitung dari data citra.  Kontur aktif sebenarnya dinyatakan sebagai proses minimisasi energi.  fungsi energi merupakan penjumlahan dari fungsi energi internal kontur (E_int) dan energi citra (E_ext). 

Fungsi energi snake merupakan fungsi dari himpunan titik-titik yang menyusun snake, x(s), yang merupakan himpunan dari koordinat x dan y dari titik-titik pada snake, x(s) = [x(s), y(s)].  Fungsi energi adalah integral dari fungsi-fungsi snake, dengan memberi nilai s Î [0, 1] sebagai normalisasi jarak di sekitar snake.  Fungsi energi E_snake adalah :

                 (1)

Energi internal citra didefinisikan sebagai bobot penjumlahan dari turunan order pertama dan kedua di sekitar kontur

                           (2)

di mana : a dan b adalah parameter pembobot yang mengkontrol kerenggangan dan kekakuan snake secara berturut-turut.  x’(s) dan x’’(s) menunjukkan derivasi (turunan) pertama dan kedua dari x(s) berkenaan dengan s. 

Fungsi eksternal energi E_ext didapat dari citra yang memuat nilai-nilai terkecilnya pada ciri-ciri (feature) yang dimaksud, seperti batasan (boundaries).  Jika diberikan citra dengan graylevel I(x, y) yang ditunjukkan sebagai fungsi variabel-variabel posisi kontinu (x, y), secara khusus energi-energi eksternal dirancang untuk membimbing kontur aktif maju mendekati tepi-tepi (edges) pada citra dengan fungsi :

                               (3)

             (4)

di mana adalah fungsi Gaussian dua dimensi dengan standart deviasi s dan Ñ adalah operator gradien.  Jika citra berupa gambar garis (hitam pada putih) maka akan lebih tepat bila energi-energi eksternal memakai persamaan ;

                                           (5)

                         (6)

Dari definisi di atas dapat dilihat bahwa nilai s yang besar akan menyebabkan batasan menjadi kabur.  Bagaimanapun nilai s yang besar sering diperlukan dengan tujuan untuk memperluas daerah yang dapat ditangkap (capture range) oleh snake.

Snake yang telah bernilai minimum harus memenuhi persamaan Euler :

                       (7)

Ini dapat ditunjukkan dengan persamaan

                                                   (8)

di mana  dan  

Gaya internal  menarik dan membelokkan gaya ke arah dalam pada saat gaya potensial eksternal  mendorong snake cenderung maju mendekati tepi/kontur pada citra.

Untuk memecahkan persamaan (7), snake dibuat dinamik dengan jalan memperlakukan x sebagai fungsi waktu terhadap t sama baik dengan s, x(s, t).  Kemudian turunan parsial dari x dengan tergantung pada t dibuat sama dengan sisi sebelah kiri persamaan (7), sehingga menjadi ;

         (9)

ketika x(s, t) stabil maka syarat x_t (s, t) menjadi hilang dan kita mendapatkan hasil dari persamaan (7).  Solusi numerik dari persamaan (9) dapat ditemukan dengan mendiskritkan persamaan dan menyelesaikan sistem diskrit secara iterasi.

3. Gradient vector flow Snake

Pertama kali didefinisikan edge map f(x, y) yang diturunkan dari citra I(x, y) yang berguna untuk mendekati tepi-tepi pada citra.  Karena itu, kita dapat menggunakan

                                     (10)

di mana i = 1, 2, 3, atau 4.  Field Ñf  mempunyai titik vektor ke arah tepi-tepi, tetapi memiliki jangkauan nilai tangkap yang kecil.  Selanjutnya, pada region serba sama (homogeneous region),  I(x, y) adalah konstan, Ñf  bernilai nol, dan sehingga tidak ada informasi kedekatan dan jarak dari tepi-tepi yang ada.

GVF field didefinisikan sebagai medan vektor v(x, y) = [u(x, y), v(x, y)] yang meminumumkan fungsi energi :

                                                                       (11)

Persamaan di atas adalah prinsip standart.  Dapat dilihat Ñf bernilai kecil, energi didominasi oleh jumlah kuadrat dari turunan parsial dari medan vector (vector field).  Di lain pihak, ketika  Ñf bernilai besar, bagian kedua akan mendominasi persamaan (11), dan dapat diminimumkan dengan mengatur v = Ñf.  Parameter m adalah parameter regularisasi yang dibangun sebagai penyeimbang bagian pertama dan bagian kedua.

Dengan menggunakan variasi-variasi kalkulus, GVF dapat dicari dengan menyertakan persamaan Euler :

                   (12)

                   (13)

di mana Ѳ adalah operator Laplacian.  Pada region yang serba sama, bagian kedua dari kedua persamaan (12) dan (13) adalah nol (karena gradien, f(x, y) adalah nol).  Selanjutnya, dengan region-region ini, u dan v masing-masing ditentukan oleh persamaan Laplace.

Persamaan (12) dan (13) dapat diselesaikan dengan menjadikan u dan v sebagai fungsi waktu dan hasilnya :

       (14)

    (15)

Pemecahan yang menguntungkan (t ® ¥) pada persamaan parabolik linear di atas merupakan pemecahan yang diinginkan untuk persamaan Euler (12) dan (13).  Kedua persamaan ini tidak berpasangan sehingga dapat dicari pemecahannya dengan persamaan deferensial scalar parsial secara terpisah untuk menjadikan u dan v. 

Setelah menghitung v(x, y), kita ganti gaya potensial -Ñ E_ext pada persamaan (9) dengan v(x, y), menghasilkan :

        (16)

Disebut penyelesaian kurva parametrik persamaan dinamik tersebut di atas dengan GVF snake.  Diselesaikan secara numerik dengan diskretisasi dan iterasi, sama dengan cara snake tradisional.

4. MAXIMUM RADIAL eRROR (MRE)

Pengujian akurasi dari formulasi kontur aktif dilakukan dengan menggunakan kurva harmonik sederhana.  Kurva-kurva ini dibangkitkan menurut persamaan :

                                   (59)

dengan mengatur nilai yang tepat untuk a, b, c dan variasi m.                             

Formula untuk perhitungan nilai MRE adalah

                      (60)

di mana  : d adalah jarak antara titik-titik kurva dan snaxel pada kontur akhir, (x_s, y_s) adalah posisi snaxel pada kontur akhir, (x_m, y_m) adalah posisi titik pada kurva harmonik (setelah diinterpolasi), dan n adalah jumlah titik-titik snake (snaxel) pada kontur.

Proses inisialisasi kontur aktif dilakukan pada kurva yang sebenarnya dan dibuat bergerak di bawah gaya eksternal yang berbeda.  Setelah konvergen, hitung jarak maksimum pada arah radial antara batas yang sebenarnya dan setiap kontur aktif.  Untuk menghitung MRE,  semua kontur aktif (hasil akhir proses) diinterpolasi linear untuk mempertahankan  pemisahan titik kecil tertentu. MRE diukur dalam bentuk piksel.

5. rOOT MEAN SQUARE ERROR (e_RMS)

Pengujian akurasi hasil proses deteksi tepi pada citra alami atau citra non harmonik digunakan root-mean-square (rms) error antara citra input dan citra output.  Jika f’(x, y) menyatakan citra input dan f’(x, y) menyatakan citra output, maka error, e(x, y) adalah :

e(x, y) = f’(x, y) - f(x, y)                             (61)

total error antara dua citra adalah :

                          (62)

Selanjutnya, root-mean-square error (e_rms) antara citra input, f’(x, y) dan citra output, f’(x, y) adalah akar kuadrat dari rata-rata kuadrat error merupakan pada dimensi M ´ N. atau dapat ditulis sebagai

                   (63)

di mana M ´ N adalah ukuran citra input dan citra output. 

6. prOses deteksi tepi gvf snake

Langkah–langkah proses deteksi tepi citra dengan gvf snake di atas dapat ditunjukkan melalui gambar diagram proses berikut.

Gambar 1 Diagram Proses Deteksi Tepi   Obyek dengan GVF Snake

7. HASIL UJI COBA

Perangkat lunak dibuat menggunakan bahasa pemrograman Borland Delphi 5.0 dengan spesifikasi komputer sebagai berikut :

·         Sistem Operasi Windows 98

·         Prosesor Pentium III 600 MHz

·         Memori 320 MB.

Perangkat lunak menerima masukan berupa file citra bitmap (BMP) dan keluarannya berupa citra bersama dengan kontur aktifnya.  File citra masukan dapat berupa citra biner, citra grayscale, atau citra berwarna.  Pada perangkat lunak ini semua citra diperlakukan sama artinya jenis citra apapun yang dipanggil akan ditampilkan sesuai dengan file citra aslinya tetapi pada saat proses semua jenis citra digrayscalekan.

1.  Uji Coba Deteksi Tepi Obyek dengan GVF snake dan Tanpa GVF snake

Pengujian ini dimaksudkan untuk mengetahui sejauh mana perbedaan pengaruh GVF snake terhadap pergerakan snake menuju tepi obyek yang sesungguhnya pada suatu citra.  Pengujian terhadap enam macam kurva harmonik dengan dua perlakuan, yaitu deteksi tepi dengan GVF snake dan deteksi tepi tanpa GVF snake. Pada proses pengujian ketepatan hasil deteksi tepi ini, dibuat setting parameter yang sama.

Grafik di bawah ini menunjukkan total waktu deteksi tepu obyek pada enam kurva harmonik dengan GVF snake dan tanpa GVF snake.

Gambar 2. Grafik ujicoba Pengaruh Proses Deteksi Tepi   Obyek dengan GVF Snake      dan Tanpa GVF snake

Rata-rata waktu untuk semua kurva pada proses deteksi tepi obyek dengan GVF snake dan tanpa GVF snake dapat dihitung sebagai berikut

Dari hasil perhitungan di atas dapat dijelaskan bahwa proses deteksi tepi obyek dengan GVF snake mempunyai kemampuan mendekati tepi obyek tujuh  kali lebih cepat dibanding proses deteksi tepi obyek tanpa GVF snake. 

2. Uji Coba Pengaruh Noise

Pengujian ini dilakukan terhadap bangkitan kurva harmonik yang diberi noise, pada penelitian ini dicoba bangkitan noise Multiplicative Gaussian dengan range nilai tertentu antara 0 sampai dengan 1.  Proses pengujian  dimulai dengan pengaturan setting parameter yang sesuai supaya tepi obyek citra dapat didekati oleh snake.

Hasil bangkitan kurva harmonik dengan posisi inisial snake setelah diberikan range noise Multiplicative Gaussian sebesar  0.2 dapat dilihat pada gambar berikut :

    

m = 0           m = 2             m = 4

    

m = 6           m = 8             m = 10

Gambar 3.  Kurva harmonik dengan Multiplicative Gaussian Noise                         (range noise : 0.2)

Grafik antara nilai m dengan maksimum error untuk pengujian ketepatan deteksi tepi dengan pemberian noise dapat ditunjukkan seperti pada gambar berikut

Gambar 4. Grafik MRE untuk test dengan pembangkitan Multiplicative Gaussian        Noise (range : 0.2)

Dengan melihat grafik pada gambar 5 dapat dijelaskan sebagai berikut : dengan penambahan noise sampai 0.2 menunjukkan bahwa snake masih mampu mengenali tepi obyek dengan tepat , ini dapat dilihat dari maksimum error yang menunjukkan nilai di bawah satu piksel untuk masing-masing bentuk kurva.

3. Uji Coba Pengaruh Setting Parameter

Uji coba dilakukan pada enam macam kurva harmonik dengan menggunakan dua setting parameter berbeda. Hasil dari ujicoba ini menunjukan bahwa pemilihan setting parameter yang sesuai sangat mempengaruhi kecepatan dan ketepatan snake mendekati tepi obyek ynag sesungguhnya pada citra.

Grafik berikut menunjukkan total iterasi dari percobaan dengan dua setting parameter pada obyek citra yang sama.

Gambar 5. Grafik ujicoba pengaruh setting parameter proses deteksi tepi obyek

dengan GVF snake

4. Uji Coba pada Citra Alami

Proses pengujian ketepatan hasil deteksi tepi dengan menggunakan citra alami dimulai dengan penentuan setting parameter sesuai.  Hasil proses pengujian ini dengan setting parameter sesuai dapat ditabelkan menjadi :

Tabel 1. Hasil Uji Ketepatan Hasil Dekteksi Tepi pada Citra Alami

Nama Citra	Inisialisasi	Times (second)	erms
Bentuk ”U”	Otomatis	0.309	0.2842
Bentuk ”U”	Manual	0.248	0.2851
Kuda	Otomatis	5.327	0.1980
Wajah	Manual	8.532	0.1881
Cangkir	Otomatis	5.627	0.2212
Mobil	Manual	6.763	0.2716

Dari tabel di atas dapat dijelaskan bahwa root-mean-square error (e_rms) yang dipakai untuk pengujian ketepatan hasil deteksi tepi obyek pada citra alami menunjukkan nilai yang kecil (rata-rata sebesar 0.2405) artinya selisih tepi snake (akhir proses deteksi tepi) dibandingkan dengan tepi obyek yang sesungguhnya  rata–rata sebesar 0.2405.  Analisa secara kualitatif dapat dilihat pada tabel 2 yang dibuat di akhir paper ini.  Secara visualisasi ditunjukkan hasil proses deteksi tepi obyek dengan GVF snake, mulai dari citra input, inisialisasi snake, sampai dengan citra output yang berupa tampilan citra input dan snake serta posisi snake pada GVF field.  Dengan melihat hasil akhir proses deteksi tepi dapat dijelaskan bahwa snake dapat mendekati tepi obyek yang sesungguhnya dengan baik. Hal ini bisa ditunjukkan secara kuantitatif dari nilai root-mean-square error (e_rms) yang kecil (rata-rata selisih tepi snake dengan tepi obyek sesungguhnya kecil/tidak jauh dari tepi obyek yang sesungguhnya).

8. SIMPULAN DAN sARAN

Berdasarkan hasil uji coba dapat disimpulkan sebagai berikut :

Penggunaan GVF snake sangat membantu kecepatan pergerakan snake menuju tepi obyek yang sesungguhnya.

Penentuan inisialisasi dan setting parameter yang tepat serta pemakaian teknik control point snaxel pada proses deformasi snake akan menyebabkan pergerakan snake  lebih cepat dan tepat menuju tepi obyek citra yang sesungguhnya.

Hasil pengujian ketepatan hasil akhir deteksi tepi obyek citra dengan GVF snake dengan metode Maximum Radial Error (MRE) didapat rata selisih kontur aktif /snake dengan obyek sesungguhnya (kurva harmonik) tidak lebih dari satu piksel artinya perangkat lunak ini mempunyai tingkat akurasi yang tinggi untuk melakukan proses deteksi tepi obyek, sedang pada pengujian ketepatan hasil akhir deteksi tepi obyek pada citra alami dengan root-mean-square error (e_rms) menunjukkan selisih tepi snake pada akhir proses deteksi tepi  dengan tepi obyek yang sesungguhnya pada citra alami sangat kecil (tepi snake tepat / mendekati obyek yang sesungguhnya).

Kemungkinan pengembangan yang mungkin dilakukan  adalah :

Pembuatan perangkat lunak lanjutan dengan memanfaatkan hasil deteksi tepi untuk proses yang lebih lanjut misalnya proses identifikasi obyek.

Otomatisasi penentuan inisialisasi snake dan setting parameter untuk segala macam bentuk obyek citra yang akan dideteksi serta berlaku untuk obyek citra yang lebih dari satu.

9. daftar pustaka

[1].      Denzler J. and H. Niemann. (1995). “A New Energy Term Combining Kalman-Filter and Active Contour Models for Object Tracking”. European Transactions on Telecommunications.

[2].      Efford, Nick. (2000). “Digital Image Processing : A Practical Introduction Using Java”. Addison-Wesley Publishing Company.

[3].      Gonzales, R.C. and Woods, R.E. (2002). “Digital Image Processing”. Second Edition. Prentice Hall. Upper Saddle River, New Jersey.

[4].      Nixon, Mark. and Alberto Aguado. (2002). “Feature Extraction & Image Processing”. Addison-Wesley Publishing Company.

[5].      Tabrizi, J. H. and W. Robert J. Funnell. (2002). “Comparison of Gradient, Gradient Vector Flow and Pressure Force forImage Segmentation Using Active Contours”. Department of BioMedical Engineering and Department of Otolaryngology McGill University, Montreal, QC, Canada.

[6].      Xu, Chenyang and Jerry L. Prince. (1997). “Gradient Vector Flow : A New External Force Model for Snakes”. Department Electrical and Computer Engineering. The Johns Hopkins University. Baltimore. IEEE Proc. Conf. On CVPR’97. Pages 66-71.

[7].      Xu, Chenyang and Jerry L. Prince. (1998). “Generalized Gradient Vector Flow External Forces for Active Contours”. Department Electrical and Computer Engineering. The Johns Hopkins University. Baltimore. Pages 131-139.

[8].      Xu, Chenyang and Jerry L. Prince. (1998). “Snakes, Shapes, and Gradient Vector Flow”. IEEE Transactions on image processing. Vol. 7, No. 3. Pages 359-369.

[9].      Xu, Chenyang and Jerry L. Prince. (2000). “Gradient Vector Flow Deformable Models”. Department Electrical and Computer Engineering. The Johns Hopkins University. Baltimore. Pages 1-20.

[10].    Young, David. (1995). “Active Contour Models (Snakes)”. School of Cognitive and Computing Sciences. University of Sussex. Falmer. Brighton. Pages 1-20.

Tabel 2 Gambar Citra Alami Hasil Proses Dekteksi Tepi dengan GVF snake

Nama Citra	Citra Inisial	Citra akhir proses	GVF + snake

Share: