KOMBINASI METODE MORPHOLOGICAL GRADIENT DAN TRANSFORMASI WATERSHED PADA PROSES SEGMENTASI CITRA DIGITAL Rudy Adipranata Universitas Kristen Petra Jl. Siwalankerto 121-131, Surabaya. Telp. (031) 8439040 Email :
[email protected] Abstrak Segmentasi gambar adalah sebuah proses untuk memisahkan sebuah obyek dari background, sehingga obyek tersebut dapat diproses untuk keperluan yang lain. Seiring dengan berkembangnya teknologi pada aplikasi yang memproses sebuah obyek seperti rekonstruksi obyek tiga dimensi, pengenalan benda, pengenalan tulisan, deteksi wajah, pengkodean obyek dan lain-lain maka proses segmentasi menjadi semakin diperlukan. Hasil dari segmentasi juga harus semakin akurat karena ketidak akuratan hasil segmentasi akan mempengaruhi pula hasil proses selanjutnya. Banyak metode yang dapat digunakan untuk proses segmentasi seperti dengan menggunakan threshold baik adaptive threshold ataupun tidak, pendeteksian tepi obyek dengan menggunakan filter Sobel, Prewitt ataupun yang lain. Secara umum proses segmentasi tersebut terbagi menjadi tiga bagian yaitu berdasar klasifikasi, berdasar tepi dan berdasar daerah. Pada makalah ini digunakan metode segmentasi yang dapat menghasilkan segmentasi obyek berdasar daerah obyek tersebut dengan menggunakan transformasi watershed. Penggunaan segmentasi watershed ini dapat menghasilkan suatu hasil yang dapat memisahkan obyek sekalipun tepi antar obyek bersambungan. Tetapi pada penggunaan transformasi watershed terdapat kelemahan yaitu terjadinya segmentasi yang berlebihan. Untuk mengatasi hal tersebut, dibutuhkan sebuah preprocessing untuk dapat mengurangi segmentasi berlebihan tersebut. Dari hasil penelitian, didapat bahwa dengan menggunakan metode Morphological gradient sebagai preprocessing, maka transformasi watershed dapat menghasilkan segmentasi gambar yang cukup akurat dan tidak terjadi segmentasi yang terlalu berlebihan. Kata kunci : pemrosesan citra digital, segmentasi berdasar daerah, Morphological gradient, watershed 1.
Pendahuluan Pada pemrosesan citra digital, terdapat sebuah proses penting yang sering digunakan sebagai pre-processing untuk proses yang lain. Proses tersebut adalah segmentasi. Proses segmentasi ialah sebuah proses untuk memisahkan antara satu obyek dengan obyek lain atau antara obyek dengan background yang terdapat dalam sebuah gambar. Dengan proses segmentasi tersebut, masing-masing obyek pada gambar dapat diambil secara individu sehingga dapat digunakan sebagai input bagi proses yang lain. Sebagai contoh, pada proses rekonstruksi obyek tiga dimensi, diperlukan proses segmentasi untuk memisahkan obyek yang akan direkonstruksi terhadap background yang ada. Pada proses pengenalan wajah manusia, proses segmentasi dibutuhkan untuk memisahkan wajah manusia terhadap background atau terhadap bagian tubuh lain sehingga didapatkan gambar wajah yang akan dikenali. Untuk proses pengenalan jenis obyek, proses segmentasi diperlukan untuk melakukan pemisahan masing-masing obyek terhadap background sehingga pada saat proses pengenalan, bagian background tidak ikut terproses. Begitu pula untuk proses pengenalan huruf pada sebuah teks, diperlukan juga proses segmentasi untuk mendapatkan huruf yang akan dikenali. Dan masih banyak lagi proses-proses yang membutuhkan segmentasi. Mengingat pentingnya proses segmentasi tersebut sebagai pre-processing, maka dibutuhkan metode segmentasi yang dapat
melakukan pemisahan obyek dengan akurat. Ketidak akuratan proses segmentasi dapat menyebabkan ketidak akuratan pada hasil proses selanjutnya.
Gambar 1. Posisi Proses Segmentasi Dalam Pemrosesan Citra Digital Secara umum, proses segmentasi terbagi menjadi tiga kelompok yaitu segmentasi berdasar klasifikasi (classification based segmentation), segmentasi berdasar tepi (edge based segmentation) dan segmentasi berdasar daerah (region based segmentation). Segmentasi berdasar klasifikasi adalah proses segmentasi yang dilakukan dengan mencari kesamaan ukuran dari nilai pada pixel. Segmentasi berdasar tepi adalah proses segmentasi untuk mendapatkan garis yang ada pada gambar dengan anggapan bahwa garis tersebut merupakan tepi dari obyek yang memisahkan obyek yang satu dengan obyek yang
lain atau antara obyek dengan background. Jenis segmentasi yang terakhir yaitu segmentasi berdasar daerah adalah proses segmentasi yang dilakukan untuk mendapatkan daerah yang diyakini merupakan sebuah obyek. Untuk mendapatkan daerah tersebut, dilakukan analisa terhadap kesamaan tekstur, warna pada pixel yang terdapat pada gambar. Pada penelitian ini, dilakukan proses segmentasi berdasar daerah dengan menggunakan metode transformasi watershed. Transformasi watershed ini merupakan metode segmentasi yang cukup akurat untuk mendapatkan daerah yang merupakan obyek yang disegmentasi. Tetapi terdapat kelemahan dari transformasi watershed ini yaitu adanya segmentasi yang berlebihan (over segmentation) sehingga obyek yang didapat lebih banyak dari obyek yang diharapkan. Untuk mengatasi hal ini, diperlukan preprocessing sebelum melakukan transformasi sehingga hasil transformasi tidak menunjukkan segmentasi yang terlalu berlebihan. Dari penelitian yang dilakukan, didapatkan bahwa metode Morphological gradient dapat digunakan sebagai preprocessing untuk mendapatkan hasil segmentasi yang tidak terlalu berlebihan. Transformasi Watershed Konsep transformasi Watershed adalah dengan menganggap sebuah gambar merupakan bentuk tiga dimensi yaitu posisi x dan y dengan tingkat warna pixel yang dimilikinya. Posisi x dan y merupakan bidang dasar dan tingkat warna pixel, yang dalam hal ini adalah gray level merupakan ketinggian dengan anggapan nilai yang makin mendekati warna putih mempunyai ketinggian yang semakin tinggi. Dengan anggapan bentuk topografi tersebut, maka didapat tiga macam titik yaitu : (a) titik yang merupakan minimum regional, (b) titik yang merupakan tempat dimana jika setetes air dijatuhkan, maka air tersebut akan jatuh hingga ke sebuah posisi minimum tertentu, dan (c) titik yang merupakan tempat dimana jika air dijatuhkan, maka air tersebut mempunyai kemungkinan untuk jatuh ke salah satu posisi minimum (tidak pasti jatuh ke sebuah titik minimum, tetapi dapat jatuh ke titik minimum tertentu atau titik minimum yang lain). Untuk sebuah minimum regional tertentu, sekumpulan titik yang memenuhi kondisi (b) disebut sebagai catchment basin, sedangkan sekumpulan titik yang memenuhi kondisi (c) disebut sebagai garis watershed. [1] Dari penjelasan diatas, segmentasi dengan metode watershed ini mempunyai tujuan untuk melakukan pencarian garis watershed. Ide dasar untuk cara kerja segmentasi ini adalah diasumsikan terdapat sebuah lubang yang dibuat pada minimum regional dan kemudian seluruh topography dialiri air yang berasal dari lubang tersebut dengan kecepatan konstan. Ketika air yang naik dari dua
catchment basin hendak bergabung, maka dibangun sebuah dam untuk mencegah penggabungan tersebut. Aliran air akan mencapai tingkat yang diinginkan dan berhenti mengalir ketika hanya bagian atas dari dam yang terlihat. Tepi dam yang terlihat inilah yang disebut dengan garis watershed. Dan garis watershed inilah yang merupakan hasil dari segmentasi, dengan anggapan bahwa garis watershed tersebut merupakan tepi dari obyek yang hendak disegmentasi. Untuk lebih jelas mengenai penggambaran dapat dilihat pada gambar di bawah ini.
(a)
2.
(b) Gambar 2. Konsep Transformasi Watershed Pada gambar 2a ditampilkan gambar dua dimensi dari konsep transformasi watershed dimana dua bagian yang berwarna gelap adalah dua buah catchment basin dan bagian di tengah kedua catchment basin merupakan daerah dimana garis watershed akan berada, sedangkan pada gambar 2b ditampilkan gambar tiga dimensi dari konsep transformasi watershed. 2.1 Pembentukan Dam Pembentukan dam atau garis watershed adalah hal yang paling penting dalam proses transformasi watershed. Pembuatan dam didasarkan pada gambar biner, yang merupakan anggota dari ruang integer dua dimensi Z2. Cara termudah untuk membuat dam adalah dengan menggunakan morphological dilation. Dasar pembentukan dam digambarkan pada gambar 3. Gambar 3a menunjukkan dua bagian catchment basin pada langkah aliran air n-1, sedangkan gambar 3b menunjukkan hasil aliran air pada langkah n. Air telah bergabung dari satu kolam (basin) ke kolam yang lain, sehingga perlu dibangun sebuah dam untuk mencegah bergabungnya air tersebut. Terdapat M1 dan M2
yang merupakan kumpulan koordinat titik pada dua regional minima. Terdapat pula sekumpulan koordinat titik pada catchment basin yang berasosiasi dengan dua regional minima tersebut pada tahap n-1 aliran air dan diberi tanda Cn-1 (M1) dan Cn-1 (M2). Bagian ini adalah warna hitam yang berada pada gambar 3a. Union dari dua kumpulan tersebut diberi tanda C[n-1]. Terdapat dua komponen terkoneksi pada gambar 3a dan hanya satu komponen terkoneksi pada gambar 3b. Berubahnya dari dua komponen menjadi satu komponen terkoneksi mengindikasikan bahwa air antara dua catchment basin telah bergabung pada langkah ke n. Komponen yang terkoneksi ini diberi simbol q. Dua komponen dari langkah n-1 dapat diambil dari q dengan menggunakan operasi AND q∩C[n-1]. Semua titik individu lain yang terdapat pada catchment basin juga membentuk sebuah komponen terkoneksi. Diasumsikan bahwa setiap komponen terkoneksi pada gambar 3a telah dilakukan dilation oleh elemen yang terdapat pada gambar 3c dengan dua kondisi : (1) Dilation harus dibatasi oleh q dan (2) dilation tidak dapat dilakukan pada titik yang dapat menyebabkan kumpulan titik yang satu dengan kumpulan titik yang lain menjadi bergabung. Maka hasilnya terdapat pada gambar 3d dimana pada dilation pertama menyebabkan tepi komponen terkoneksi menjadi berkembang dan pada dilation kedua, beberapa titik tidak dapat memenuhi kondisi (1) yang disyaratkan, sehingga menyebabkan terputusnya perimeter seperti ditunjukkan pada gambar tersebut. Dengan demikian, maka hanya titik pada q yang dapat memenuhi dua kondisi di atas dan tebal q adalah satu pixel dan merupakan dam yang dibentuk.
(a)
(c)
(d) Gambar 3. Pembuatan Dam 2.2. Algoritma Transformasi Watershed Dianggap M1,M2,M3, ... , MR adalah kumpulan koordinat titik dalam regional minima sebuah gambar g(x,y). Terdapat C(Mi) yang merupakan kumpulan koordinat pada catchment basin dan berhubungan dengan daerah minimum Mi. Notasi min dan max digunakan untuk menandai nilai minimum dan nilai maksimum dari g(x,y). Kemudian dianggap T[n] adalah kumpulan koordinat (s,t) di mana g(s,t) < n, sehingga dapat didefinisikan : T[n]={(s,t)| g(x,y)
(b)
R
C[ n ] = U C n ( M i ) i =1
(3)
dan C[max + 1] adalah gabungan dari semua catchment basin : R
C[max + 1] = U C( M i )
(4)
i =1
C[n-1] adalah subset dari C[n] dan C[n] adalah subset dari T[n] maka C[n-1] adalah subset dari T[n]. Dari sini didapatkan bahwa tiap komponen terkoneksi dari C[n-1] terdapat pada persis satu komponen terkoneksi dari T[n]. Algoritma untuk mencari garis watershed pertama kali diinisialisasi dengan C[min+1] = T[min+1]. Algoritma tersebut akan diproses secara rekursif dengan asumsi pada tahap n maka C[n-1] telah terbentuk. Prosedur untuk mendapatkan C[n] dari C[n-1] adalah sebagai berikut. Diasumsikan Q merupakan kumpulan komponen terkoneksi dalam T[n]. Maka untuk tiap komponen terkoneksi q ∈ Q[n], terdapat tiga kemungkinan : a. q ∩ C[n − 1] adalah kosong
q ∩ C[n − 1] mempunyai 1 komponen terkoneksi dari C[n-1] c. q ∩ C[n − 1] mempunyai lebih dari 1 komponen terkoneksi dari C[n-1] Jika kondisi c terjadi maka pengisian lebih lanjut akan menyebabkan air di catchment basin yang berbeda menjadi bergabung, sehingga perlu dibangun dam di dalam q untuk mecegah mengalirnya air di antara catchment basin yang berbeda. Dam dengan tebal satu pixel dapat dibangun dengan melakukan dilation q ∩ C[n-1] dengan elemen 3x3. b.
Morphological Gradient Dari pemrosesan dengan transformasi watershed, akan menghasilkan segmentasi yang berlebihan, sehingga obyek yang dikehendaki tidak dapat tersegmentasi dengan baik. Hal ini dikarenakan adanya noise dan ketidak teraturan gradient lokal. Agar transformasi watershed dapat menghasilkan hasil segmentasi yang baik, maka diperlukan preprocessing sebelum transformasi tersebut dilakukan. Dari hasil percobaan, maka didapat preprocessing morphological gradient dapat mengurangi segmentasi yang berlebihan. Untuk itu pada tahap ini dijelaskan tentang morphological gradient. Morphological gradient adalah proses yang menghasilkan output berupa gambar yang didapat dari pengurangan hasil dilation gambar asli dengan hasil erosion gambar asli, sehingga dapat didefinisikan : g = ( f ⊕ b) − ( f Ө b) (5) Dilation adalah suatu proses dimana jika terdapat A dan B yang merupakan himpunan Z2, dilation A oleh B dilambangkan dengan A ⊕ B, dan diformulasikan sebagai :
Sedangkan erosion adalah suatu proses dimana jika terdapat A dan B yang merupakan himpunan Z2, erosion A oleh B dilambangkan dengan AӨB, dan diformulasikan sebagai : (7) A Ө B = {x | ( B ) x ⊆ A} Di samping morphological gradient, terdapat preprocessing lain yang digunakan sebelum melakukan transformasi yaitu opening dan closing. Opening adalah suatu proses yang melakukan erosion dan diikuti dengan dilation seperti terlihat pada formula di bawah ini :
A o B = ( A B) ⊕ B
Closing adalah suat proses melakukan dilation dan diikuti oleh erosion.
A • B = ( A ⊕ B) B
(8) yang (9)
4.
Hasil Percobaan Secara garis besar, langkah yang dilakukan pada proses segmentasi adalah seperti terlihat pada diagram alir di bawah ini : Start
Opening
Closing
3.
A ⊕ B = {x | ( Bˆ ) x ∩ A ≠ ∅}
(6)
Morphological Gradient
Removal Minima
Transformasi Watershed
End Gambar 4. Diagram Alir Proses Segmentasi Dari hasil percobaan yang dilakukan, dapat dilihat hasil dari proses segmentasi yang dilakukan tanpa melibatkan morphological gradient dan dengan melibatkan morphological gradient.
Dari hasil percobaan di atas, terlihat bahwa dengan menggunakan morphological gradient sebagai preprocessing didapat hasil segmentasi yang jauh lebih baik daripada tanpa menggunakan morphological watershed karena dapat obyek utama dapat tersegmentasi dan segmentasi yang berlebihan dapat terkurangi. 5.
Gambar 4. Gambar Asli
Kesimpulan Dari percobaan yang telah dilakukan dapat diambil kesimpulan bahwa dengan menggunakan transformasi Watershed, didapat hasil segmentasi berupa daerah obyek yang dikehendaki. Hasil dari transformasi Watershed mempunyai kecenderungan menghasilkan segmentasi yang berlebihan, sehingga diperlukan preprocessing. Salah satu preprocessing yang dapat mengurangi hasil segmentasi yang berlebihan adalah morphological gradient. Daftar Pustaka [1] Gonzalez, Rafael C., and Woods, Richard E., “Digital Image Processing”, New Jersey : 2002. [2] Vincent, Luc. and Soille, Pierre. "Watersheds in Digital Spaces: An Efficient Algorithm Based on Immersion Simulations". IEEE. Trans. on Pattern Analysis and Machine Intelligence, 13(6):583{598, June 1991. [3] Wayne, Lin Wei Cheng, “Mathematical Morphology and Its Application on Image Segmentation”, Dissertation on Dept of Computer Science and Information Engineering, National Taiwan University, June 2000.
Gambar 5. Hasil Transformasi Watershed Tanpa Morphological Gradient
Gambar 6. Hasil Transformasi Watershed Dengan Morphological Gradient
