Canny Edge Detection

Halo, menyambung tulisan pekan lalu, masih tentang Edge Detection alias deteksi tepi pada citra.. Nah, sekarang dikenalkan algoritme deteksi tepi Canny… hem… apa bedanya? Mengapa Canny spesial? let’s see..

Um, inti yang za tangkep waktu kuliah si, pada algoritme deteksi tepi Canny ini dilakukan proses penipisan, sehingga edge yang dihasilkan kurang lebih seperti:

Tepi Hasil Deteksi Canny

nah, lebih tipis kan?

gimana bisa? soalnya di deteksi tepi Canny ini setiap tepi/garis, direpresentasikan hanya oleh satu respon (piksel?).

***

sekian pengantarnya, berikut ini adalah tulisan yang di copas dari tugas.. hehe..

***
Algoritme deteksi tepi Canny dikenal sebagai algoritme yang optimal dalam melakukan pendeteksian tepi.  Untuk meningkatkan metode-metode yang telah ada dalam pendeteksian tepi, algortime deteksi tepi Canny mengikuti beberapa kriteria sebagai berikut:

• Tingkat error yang rendah.  Error terjadi bila ada tepi yang penting tetapi tidak muncul, atau bila ada yang bukan tepi tetapi muncul.
• Titik-titik pada tepi dilokasikan dengan benar.  Dengan kata lain, jarak antara piksel-piksel tepi yang ditemukan algoritme dengan tepi sesungguhnya diminimumkan.
• Hanya satu respon (lebar 1 piksel) untuk setiap sebuah tepi.

Berdasarkan kriteria di atas, algoritme deteksi tepi Canny dilakukan dengan langkah-langkah sebagai berikut:

1. Pertama-tama dilakukan penghalusan (smoothing) citra untuk menghilangkan noise.  Contohnya menggunakan filtering dengan Gaussian Filter.
2. Selanjutnya dicari gradient magnitude citra untuk melihat daerah-daerah yang memiliki turunan spasial yang tinggi.  Pencarian gradient magnitude seperti yang ditulis pada tulisan sebelumya, bisa pakai Sobel, Prewitt,, dll…
3. Ditentukan arah dari tepi dengan menggunakan invers tangen dari gradient magnitude Y (Gy) dibagi gradient magnitude X (Gx).  Arah yang diperoleh dari perhitungan ini kemudian dipetakan ke 0, 45, 90, atau 135 derajat berdasarkan kedekatannya dengan keempat derajat arah tadi.
4. Kemudian dilakukan Non Maximum Suppression. Yaitu, penghilangan  nilai-nilai yang tidak maksimum. Ditelusuri daerah yang ditemukan pada langkah 2 (dengan arah seperti yang ditemukan pada langkah 3), dan menghilangkan (suppress) setiap piksel yang tidak maksimum.
5. Selanjutnya dilakukan Hysteresis (disebut juga Hysthresis), [for me maybe simply "double thresholding"].  Hysteresis menggunakan dua threshold T1 (threshold bawah) dan T2 (threshold atas).  Bila magnitude ada di bawah T1, titik tersebut di-set nol (dijadikan non-tepi). Bila magnitude ada di atas T2, maka termasuk tepi.  Bila magnitude ada diantara T1 dan T2, di-set nol kecuali jika ada jalan (path) dari titik tersebut ke titik yang memiliki magnitude di atas T2.

***

sekian, semoga bermanfaat.

PPCD 9: Edge Detection (Deteksi Tepi)

Tujuannya..?

- memisahkan objek/foreground dari backgroundnya

- melakukan segmentasi (pemishan) setiap objek.  why we need it: untuk mengidentifikasi objek yang ada, dan nantinya kan bisa dipilih yang memang penting untuk pengolahan lebih lanjut

Deteksi Tepi

Pengertian..?

- adalah operasi untuk mendeteksi garis tepi yang membatasi 2 wilayah

 

Gimana cara ngedeteksi itu?

Idenya dasarnya : pada dua wilayah yang berbeda, umumnya terdapat perubahan warna (yang direpresentasikan sebagai nilai dari piksel).  Maka, tepian objek adalah lokasi di mana terdapat intensitas perbedaan warna yang “cukup” drastis antar 2 piksel yang berdekatan.

 

“Cukup” drastis? seperti apa yang “cukup” drastis itu?..

Untuk menghitung “tingkat kedrastisan” perubahan warna itu, kita menggunakan suatu ukuran yang disebut Magnitude.  Semakin besar magnitude, semakin drastis perubahan warna yang terjadi.  Untuk menentukan apakah suatu piksel itu tepian atau bukan, kita menetapkan suatu batasan nilai (threshold) dari nilai magnitude-nya.  Setiap piksel yang magnitude-nya lebih besar (atau sama dengan? [please cek lagi]) threshold, berarti dia tepian, yang kurang dari threshold, berarti bukan tepian.

 

Langkah pendeteksian…

1. Um, pakai  filtering gitu,, jadi ada matriks konvolusi yang diterapkan ke citra. Matriks konvolusinya ini berbeda2 sesuai dengan algoritmenya.  nilai yang dihitung adalah nilai X dan Y (citra 2D), Mx adalah matriks konvolusi untuk X, sedangkan My matriks konvolusi untuk Y.

2. Hitung magnitude nya.  Magnitude adalah akar dari penjumlahan hasil penerapan matriks Mx kuadrat dan hasil penerapan matriks My kuadrat.

Ada beberapa algoritme dalam edge detection ini (yang matriks nya juga beda2).  Yang dijelaskan di kelas antara lain: Robert, Prewitt, dan Sobel.

1. Robert : matriks berukuran 2×2

Mx =  [1 0 ;  0 -1]      My = [0 -1; 1  0]   (titik koma berarti ganti baris)

2. Prewitt : matriks berukuran 3×3, elemen diagonal dengan elemen veritkal/horizontal diberi bobot yang sama (1 atau -1)

Mx = [-1 0 1; -1 0 1; -1 0 1]    My =[-1 -1 -1; 0 0 0 ; 1 1 1]

3. Sobel :   matriks berukuran 3×3, tapi elemen yang horizontal/vertikal, diberi bobot lebih besar (2 atau -2) dibandingkan dengan elemen diagonal (1 atau -1).

Mx = [-1 0 1; -2 0 2; -1 0 1]   My=[-1 -2 -1; 0 0 0; 1 2 1]

Di kuliah disebutkan kalau algoritme Sobel ini memberikan hasil yang lebih baik, mengapa bisa demikian? alasannya ternyata karena perbedaan pembobotan itu tadi.  Elemen horizontal/vertikal dari suatu piksel itu “lebih dekat” daripada elemen diagonalnya, karena itu dia dikasi bobot lebih besar daripada elemen diagonal.  ”Lebih dekat”, maksudnya? secara sederhana, seperti persegi gitu,, diagonalnya pasti lebih panjang daripada sisi-sisinya, seperti itulah..

Secara lebih kompleksnya, kalau tetangga horizontal dari piksel kan yang membedakan hanya nilai x-nya, sedangkan y-nya sama.  Gitu juga dengan tetangga vertikal dari piksel, nilai y-nya aja yang beda, tapi x-nya sama.  Sedangkan tetangga diagonal nilai x ataupun y nya beda. Oh iya, tetangga yang dimaksud, jaraknya hanya 1 piksel (di sekeliling) piksel itu.

 

Ada pertanyaan nih..

Misalnya ada sebuah citra, akan dideteksi tepiannya.  Diterapkan algoritme yang sama beberapa kali. Misalnya saja Prewitt. Nah, ternyata hasil yang diperoleh di berbeda, walaupun algoritmenya sama. Mengapa bisa demikian..?

 

 

Ya, benar..

jawabannya adalah karena kita menentukan threshold magnitude nya berbeda-beda sehingga piksel mana-mana aja yang termasuk edge akan berubah sesuai dengan thresholdnya.  So, penentuan threshold ini jadi hal yang penting.. Kalo terlalu besar thresholdnya,, nanti edge yang didapat terlalu sedikit, dan kalau threshold nya kekecilan,, nanti edge yang didapet terlalu banyak… Nah, threshold yang tepat segimana dong? Ini katanya dibahas pekan depan…

 

otreh, sekian.  Silakan merujuk ke sumber lainnya.. semangaat…