Implementasi Metode Edge Linking Untuk Mendeteksi Garis Tepi Pada Citra Digital

Segmentasi Citra

Segmentasi citra (image segmentation) merupakan langkah awal pada proses analisa citra yang bertujuan untuk mengambil informasi yang terdapat di dalam suatu citra. Segmentasi citra membagi suatu citra ke dalam bagian-bagian atau objek-objek. Sampai sejauh mana pembagian tersebut dilakukan tergantung pada masalah yang dihadapi. Idealnya, langkah segmentasi tersebut dihentikan pada saat objek yang diinginkan sudah berhasil dipisahkan.

Pada umumnya segmentasi secara otomatis adalah salah satu pekerjaan yang sulit dalam pengolahan citra. Langkah ini akan menentukan berhasil atau tidaknya proses analisa citra. Namun dengan segmentasi yang efektif, kemungkinan besar akan didapatkan hasil yang baik.

Algoritma segmentasi untuk citra monochrome biasanya berdasarkan pada satu dari dua sifat nilai gray-level: diskontinuitas dan similaritas. Pada diskontinuitas, pendekatan yang dilakukan adalah memisahkan citra berdasarkan terjadinya perubahan nilai graylevel yang drastis. Sedangkan pada similaritas, pendekatan dilakukan berdasarkan thresholding, region growing, region splitting, dan merging.


Deteksi Diskontinuitas


Ada tiga jenis diskontinuitas pada citra digital, yaitu: point (titik), line (garis), dan edge (batas). Dalam prakteknya, cara yang paling umum digunakan untuk menemukan diskontinuitas pada citra adalah dengan menggunakan mask yang dioperasikan ke seluruh pixel yang ada di dalam citra tersebut. Dengan menggunakan mask berukuran 3 x 3 seperti pada gambar berikut, akan didapatkan hasil:


R = w1z1 + w2z2 + … + w9z9


dimana zi adalah graylevel dari pixel yang bersesuaian dengan koefisien mask wi.





Point Detection





Suatu titik dikatakan terdeteksi di lokasi pusat dari mask jika


|R| > T


dimana T adalah threshold positif, dan R adalah hasil perhitungan dari :


R = w1z1 + w2z2 + … + w9z9


dengan menggunakan mask tersebut di atas.


Pada dasarnya apa yang dilakukan di sini adalah mengukur besarnya perbedaan graylevel antara titik tengah dengan titik-titik tetangganya (neighbor). Idenya adalah bahwa suatu titik yang terisolasi akan memiliki perbedaan graylevel yang cukup besar dengan titik-titik tetangganya.



Edge Detection


Edge detection adalah pendekatan yang paling umum digunakan untuk mendeteksi diskontinuitas graylevel. Hal ini disebabkan karena titik ataupun garis yang terisolasi tidak terlalu sering dijumpai dalam aplikasi praktis.

Suatu edge adalah batas antara dua region yang memiliki graylevel yang relatif berbeda. Pada dasarnya ide yang ada di balik sebagian besar teknik edge-detection adalah menggunakan perhitungan local derivative operator.

Gradien dari suatu citra f(x,y) pada lokasi (x,y) adalah vektor


Rumus tersebut lebih mudah diimplementasikan, khususnya jika menggunakan hardware untuk pemrosesan.


Edge Linking


Secara ideal, teknik yang digunakan untuk mendeteksi diskontinuitas seharusnya hanya menghasilkan pixel-pixel yang berada pada batas region. Namun dalam prakteknya hal ini jarang terjadi karena adanya noise, batas yang terpisah karena pencahayaan yang tidak merata, dan efek lain yang mengakibatkan variasi intensitas. Untuk itu algoritma edge-detection biasanya dilanjutkan dengan prosedur edge-linking untuk merangkai pixel-pixel tersebut menjadi satu kesatuan sehingga memberikan suatu informasi yang berarti.

Salah satu teknik yang dapat digunakan untuk edge-linking adalah local processing, yaitu dengan menganalisa karakteristik pixel-pixel di dalam suatu neighborhood (3 x 3 atau 5 x 5) pada semua titik (x,y) di dalam citra yang telah mengalami edge-detection. Selanjutnya semua titik yang sejenis dihubungkan sehingga membentuk kumpulan pixel yang memiliki sifat-sifat yang sama.

Dua sifat utama yang digunakan untuk menentukan kesamaan edge pixel dalam analisa ini adalah:

1. Besarnya respon gradient operator yang digunakan

2. Arah gradient

Sifat yang pertama dinyatakan dengan nilai Ñf yang telah dibahas sebelumnya. Jadi suatu edge pixel dengan koordinat (x’,y’) dan bertetangga dengan (x,y), dikatakan memiliki magnitude sama dengan pixel di (x,y) jika:






dimana T adalah threshold positif.

Sedangkan arah vektor gradient dinyatakan dengan a(x,y) yang juga telah dibahas sebelumnya. Suatu edge pixel dengan koordinat (x’,y’) dan bertetangga dengan (x,y), dikatakan memiliki sudut yang sama dengan pixel di (x,y) jika:






dimana A adalah threshold sudut.

Suatu titik yang menjadi tetangga dari (x,y) dihubungkan dengan titik (x,y) jika memenuhi kedua kriteria di atas, baik magnitude maupun sudutnya. Proses linking ini diulang untuk seluruh lokasi titik yang ada di dalam citra.




CARA PENELITIAN


Untuk mengimplementasikan proses contrast stretching pada komputer, penulis membuat program yang memiliki kemampuan untuk:

· membuka file yang berisi citra digital

· menampilkan citra digital tersebut di layar

· melakukan pemrosesan edge linking

· menampilkan citra digital hasil proses

Adapun batasan dari program ini adalah:

· file citra yang digunakan harus berformat BMP, berukuran 256x256 pixel, dengan 256 gray-level


File citra digital dengan format BMP


File citra dengan format BMP adalah salah satu format standar yang digunakan dalam sistem operasi Windows. File ini biasanya disimpan dengan ekstensi .BMP. Struktur dari file BMP adalah sebagai berikut:


BITMAPFILEHEADER

BITMAPINFOHEADER

Array RGBQUAD

Array warna



Struktur BITMAPFILEHEADER menunjukkan jenis file dan ukuran file. Struktur BITMAPINFOHEADER menunjukkan ukuran (lebar dan tinggi) dari citra, format warna citra, dan banyaknya warna yang digunakan di dalam citra. Struktur RGBQUAD berisi nilai intensitas warna yang dibagi menjadi komponen R, G, dan B (red, green, dan blue). Sedangkan array warna berisi informasi mengenai isi citra itu sendiri, yaitu pixel-pixel yang membentuk citra tersebut.

Untuk mempercepat proses pengolahan citra digital, maka pixel-pixel yang ada di dalam file BMP dicopykan ke dalam variabel array. Dengan demikian pada proses selanjutnya tidak perlu dilakukan pembacaan file secara berulang-ulang. Deklarasi array untuk menyimpan citra tersebut adalah:


arCitra1 : array[1..256, 1..256] of byte;

arCitra2 : array[1..256, 1..256] of byte;


Secara lengkap, proses peng-copy-an pixel ini dapat dilihat pada procedure BukaFileCitra di listing program terlampir. Untuk menampilkan citra ke layar, digunakan component TImage dari Delphi.




Proses Edge Linking


Setelah semua pixel tersimpan di dalam variabel array, dilakukan perhitungan komponen Gx dan komponen Gy dari gradien. Proses ini terdapat di dalam procedure HitungKomponenGX dan HitungKomponenGY di dalam program. Data hasil perhitungan ini kemudian disimpan ke dalam array tersendiri dan dapat ditampilkan ke layar. Untuk menghasilkan komponen Gx dan Gy ini digunakan operator Sobel.

Berikut ini kutipan perintah di dalam program untuk menghitung komponen Gx dan Gy dengan menggunakan operator Sobel:


GX :=

(-1 * arCitra1[ix-1,iy-1]) +

(-2 * arCitra1[ix,iy-1]) +

(-1 * arCitra1[ix+1,iy-1]) +

(1 * arCitra1[ix-1,iy+1]) +

(2 * arCitra1[ix,iy+1]) +

(1 * arCitra1[ix+1,iy+1]);


GY :=

(-1 * arCitra1[ix-1,iy-1]) +

(1 * arCitra1[ix+1,iy-1]) +

(-2 * arCitra1[ix-1,iy]) +

(2 * arCitra1[ix+1,iy]) +

(-1 * arCitra1[ix-1,iy+1]) +

(1 * arCitra1[ix+1,iy+1]);


Implementasi selengkapnya dapat dilihat pada listing program terlampir.


Setelah perhitungan komponen gradien selesai, dilanjutkan dengan proses perhitungan magnitude dari gradien dan besar sudut gradien dari masing-masing pixel. Magnitude dari gradien dapat diperoleh dengan rumus pendekatan


Setelah diperoleh kedua informasi di atas, dilakukan proses edge linking dengan cara memandingkan setiap pixel dengan pixel tetangganya. Jika perbedaan dari magnitude maupun perbedaan dari sudut gradien antara suatu pixel dengan pixel tetangganya memenuhi kriteria yang ditentukan, maka kedua pixel tersebut dianggap terhubung.

Penentuan nilai untuk kedua kriteria ini dapat dilakukan dengan memasukkan nilai tersebut pada kotak dialog yang tersedia pada program.