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…

Pengantar Data Mining

Bahasannya mencakup : pendahuluan, pengertian DaMing, DaMing dalam KDD, Arrsitektur DaMing, Data mining tasks, aplikasi daMing.

 

Pendahuluan

• Masalah Eksplorasi Data. Penumpukan data dalam database, data warehouse, dll.   “Kita telah tenggelam dalam data, tetapi kelaparan untuk mendapatkan pengetahuan/informasi!”
• Solusi : data warehousing dan data mining –>  ekstraksi pengetahuan yang menarik dari basis data berukuran besar
• mencari informasi ‘tersembunyi’ dari data (kita belum tahu hasilnya apa, tidak seperti meng-query)
• untuk menganalisis data (data tidak hanya dikumpulkan)

 

Pengertian Data Mining

 Ekstraksi Informasi/Pola yang menarik dalam basis data berukuran besar

istilah lain: Knowledge Discovery in Database, knowledge extraction, bussiness intelligence, dll.

berikut ini bukan termasuk data mining task :

• Pemrosesan (deduktif) Queri
• Sistem Pakar

Data mining berkaitan erat dengan machine learning, AI, statistika, dan sistem basis data.  Katanya buku, 

Secara khusus, data mining menggunakan ide-ide seperti (1) pengambilan contoh, estimasi, dan pengujian hipotesis, dari statistika dan (2) algoritme pencarian, teknik pemodelan, dan teori pembelajaran dari kecerdasan buatan, pengenalan pola, dan machine learning.

 

 

Data Mining sebagai proses dalam Knowledge Discovery in Data (KDD)

Data mining adalah elemen utama dalam proses knowledge discovery, lengkapnya sbb..

 

Data Mining dalam proses KDD

 Proses dalam KDD

1. Data cleaning. menghilangkan noise.
2. Integrasi Data.
3. Seleksi
4. Transformasi Data
5. Data Mining
6. Evaluasi Pola
7. Presentasi Pengetahuan

 

 

Arsitektur Data Mining

Arsitektur Data Mining

 

 

Data Mining Tasks– Tugas-tugas Data Mining

Tugas-tugas dalam data mining secara umum dibagi ke dalam dua ketegori utama :

• Prediktif. Memprediksi atribut target (variabel tak bebas) berdasarkan atribut-atribut lainnya (variabel bebas/explanatory)
• Deskriptif. Menemukan pola-pola yang meringkas hubungan dalam data.

 

Tugas-tugas dalam data mining :

• Asosiasi (correlation dan causality)/(hubungan dan sebab-akibat).
• Klasifikasi dan Prediksi. Menemukan model (fungsi) yang membedakan kelas untuk prediksi mendatang.
• Analisis Cluster. Label kelas tidak diketahui. Prinsip : memaksimumkan kemiripan intra(di dalam)kelas, dan meminimumkan kemiripan interkelas.

Aplikasi

Contohnya diantaranya: segmentasi pasar, direct marketing, penempatan barang di supermarket.  Contoh penempatan barang di supermarket:  dari data pembelian dapat dicari pengetahuan mengenai barang apa yang dibeli oleh pembeli saat ia membeli barang X, penempatan barang itu dapat diatur di dekat untuk kenyamanan pembeli.

 

*sumber : catatan, slide, diktat bab1.  Mohon merujuk ke sumber yang lebih terpercaya..*

: )

Ngomongin K-Nearest Neighbor

 T :  KNN, apaan tu?

J  :  KNN atau K-Nearest Neigbor secara harfiahnya berarti k-tetangga terdekat…  

T  : yah ini lagi cuman ngartiin kata-katanya doang, kalo bahasa Inggris mah little-little i can lah.. maksudnya KNN tu buat apa?

J :  sabar dikit napa c  T ni juga mo jelasin…,  jadi, KNN itu salah satu algoritma untuk klasifikasi.. tau kan klasifikasi apa, apa bedanya sama klustering?

T: hm,, iya kalo itu c inget. kalo kelasifikasi kan kelas targetnya dah ditentuin terlebih dahulu gitu ya, apa tuh istilah kerennya…

J :   supervised learning..

T :   nah, iya ntu.  Kalo klustering belum ditentuin kelas targetnya, berarti unsupervised learning, ya kan?

J :   siip..

T :   yaudah, lanjut-lanjut. hm,, jadi KNN tu buat klasifikasi, terus napa tu namanya unik banget.. k-tetangga terdekat.. tinggal di komplek apa tu dia, ampe disebut begono

J :  haha. ya enggaklah. makanya lanjut dulu pengertiannya ya.  Jadi konsep dasar c KNN tu, kita ngambil sebanyak k titik yang paling deket dengan titik queri…

T :   pit.. pit… dulu.   titik queri maksudnya apa Bos?

J :  titik queri itu titik yang mo kita cari dia masuk ke kelas mana.  

T : ooo..

J : oke, lanjut.  Kita ngambil sebanyak k titik yang paling deket dengan titik queri,  kita sebut dia sebagai k-tetangga terdekat. Terus kita liat deh tetangga-tetangga itu, mereka mayoritas masuk kelas apa.   Nah, si titik queri ini akan masuk ke kelas mayoritas itu.

T :   hm hm hm…  simpel juga kayanya,

J : yap, intinya c algortima ini ada dua langkah.  Pertama, cari k- tetangga terdekat.  Tentu sebelumnya kita dah nentuian nilai k-nya, artinya kita dah tentuin dulu berapa tetagga terdekat nih yang diambil…

T : lah terus cara nyarinya gimana. Gimana kita tau kalo mereka adalah our nearest neighbor, halah..

J :  Ah elu.  Masa gitu aja nanya c..  ya pake jarak dong. 

T :  xixixi.. oh iye ye. 

J :  Hitung jarak antara titik queri dengan titik-titik training…

T :  titik training tu berarti titik yang udah kita tau kelasnya apa kan? kayak data training gitu.

J : yap, encer juga tu otak kadang2..

T :   eerrggh..

J : he… sori, ngocol dikit. yawdah lanjut. hitung jarak antara titik queri dengan titik-titik training..   Caranya ngitung jarak,  bisa pake fungsi2 yang uda pernah dibahas di kulian metkuan, inget? ada jarak Euclidean,  jarak Mahlanobis, dll…

T :  oo.. yayaya, kayaknya pernah denger tu.

J :  itu kan ada di kuliah metkuan

T : ah, elu suka pura-pura gak tau, gw kan suka sambil tidur kalo belajar di kelas.

J : hahaha.. emang bisa ya.  yawdah lanjut..  Udah dapet ni perhitungan jaraknya, abis itu kita ambilin yang paling kecil, ambil k titik yang nilainya paling kecil.  caranya? urutin dari kecil ke gede, ambil k baris pertama. Itulah our k-nearest neighbor.

T : hm…

J : sip, langkah pertama beres.  Sekarang kita dah punya k-tetangga terdekat..

T : lanjut..

J : langkah kedua;    dari k-tetangga terdekat tadi, kita liat mayoritas pada masuk kelas apa, misal masuk kelas x. yaudah, berarti titik queri kita juga masuk kelas x. beres deh klasifikasi kita.. !  

T :  hooo… bingung. 

J :   lha?  hm, emang lebih jelas langsung pake contoh c. yawda, coba unduh (maaf untuk saat ini belum ada link nya) hand-outnya aja kalo gitu.

T:  ok ok..

J :  Sebenernya… katanya c, algoritma ini juga bisa dipake buat interpolasi ma ekstrapolasi. 

T:  apalagi tu? kalo interpolasi c gw tau dikit. yang kayak di anum kan? nge-fit titik-titik gitu pake polinom or fungsi2 lain..

J : yap.. interpolasi tu untuk smoothing, kalo ekstrapolasi buat cari nilai di luar rentang nilai data yang diketahui… istiahnya… prediction. 

T : hm,, 

J : bedanya dengan klasifikasi yang tadi, kalo klasifikasi yang tadi kan nilai targetnya berupa data kategorik (dia masuk ke kelas 1 kelas 2 dst…), kalo smoothing ma prediction itu  nilai targetnya kuantitatif.. bingung?

T :  he em uy..

J  :  sama.. hehehe… nti kalo sempet kita bahas lagi… yawdah. otak gw dah ngebul ni. udahan dulu ye..

T :  ok makasi. kapan-kapan kita nge-gosip lagi ya…!!

 

* mohon rujuk kembali ke sumber yang lebih terpercaya… he.. *

Sekilas Geometri Fraktal

Representasi objek menggunakan metode geometri-Euclidian dijelaskan melalui persamaan-persamaan.   Metode ini cukup untuk menjelaskan objek-objek dengan permukaan halus dan bentuk yang reguler.  Tetapi bagaimana untuk objek-objek natural seperti gunung dan awan serta objek-objek dengan sisi yang tak beraturan? objek-objek seperti ini sulit dimodelkan dengan geometri Euclidian.

Lalu bagaimana memodelkannya?  Objek natural dapat secara realistis dimodelkan menggunakan metode geometri-Fraktal.  Dalam memodelkan objek, metode ini lebih menggunakan prosedur ketimbang persamaan.  Geometri fraktal adalah cabang matematika yang mempelajari sifat-sifat dan perilaku fraktal.

katanya om Wiki,

Fraktal adalah benda geometris yang kasar pada segala skala, dan terlihat dapat “dibagi-bagi” dengan cara yang radikal. Beberapa fraktal bisa dipecah menjadi beberapa bagian yang semuanya mirip dengan fraktal aslinya.

lucu deh, melihat animasi gimana sebuah gambar boundary segitiga dipecah-pecah jadi segitiga baru, terus diulang ampe kecil banget.  Jadilah sebuah bentuk dengan boundary yang bagus, mau lihat? di uncle Wiki.

Basis dari fraktal pun adalah persamaan, hanya saja persamaan ini dijalankan dalam suatu iterasi atau suatu rekursi.  Fractal sendiri berasal dari kata latin fractus yang artinya rusak, atau patah.  Oiya, yang unik juga, sebelum dinamakan fraktal, bentuk-bentuk kurva seperti ini dinamakan sebagai kurva monster loh… 

———

beberapa Istilah :

Complex plane, atau bidang kompleks adalah representasi geometri dari bilangan kompleks.  Ditentukan dengan sumbu real dan sumbu imajiner yang (saling) tegak lurus.  Dapat dikatakan sebagai modifikasi dari bidang Cartesian, dimana yang bertindak sebagai sumbu real adalah sumbu-x, dan yang bertindak sebagai sumbu imajiner adalah sumbu-y.