Hough Transform

Hough Transform pertama kali diperkenalkan oleh Paul Hough pada tahun 1962 untuk mendeteksi garis lurus. Hough Transform adalah teknik transformasi citra yang dapat digunakan untuk mengisolasi atau dengan kata lain memperoleh fitur dari sebuah citra. Karena tujuan dari sebuah transformasi adalah mendapatkan suatu fitur yang lebih spesifik, Classical Hough Transform merupakan teknik yang paling umum digunakan untuk mendeteksi objek yang berbentuk kurva seperti garis, lingkaran, elips dan parabola. Keuntungan utama dari transformasi Hough adalah dapat mendeteksi sebuah tepian dengan celah pada batas fitur dan secara relatif tidak dipengaruhi oleh derau atau noise.

Fungsi Garis

Transformasi Hough memiliki beberapa perbedaan rumus yang diterapkan. Semuanya tergantung pada jenis objek yang dicari, misalnya untuk mencari objek garis akan digunakan fungsi garis seperti berikut ini:

Dengan x dan y merupakan titik koordinat yang menyusun objek garis tersebut, sedangkan teta adalah sudut yang dibentuk antara objek garis dengan sumbu x, dan r merupakan jarak antara garis dengan titik pusat (0,0). Untuk lebih jelasnya dapat diilustrasikan dengan menggunakan gambar berikut.

Fungsi Lingkaran

Jika objek yang dicari berupa lingkaran, maka digunakan transformasi lingkaran Hough. Prosedur yang digunakan dalam mendeteksi lingkaran adalah sama dengan transformasi Hough pada objek garis, tapi dikerjakan pada ruang dimensi yang lebih kompleks, yaitu dalam parameter ruang 3D (Xo,Yo,R). Di mana Xo dan Yo merupakan koordinat pusat lingkaran dan r adalah jari-jari lingkaran seperti persamaan berikut:

Vektor

Sedangkan untuk vektor parameternya adalah

dan jika diilustrasikan dalam koordinat (Xo,Yo,R) adalah sebagai berikut:

Dalam proses transformasi lingkaran Hough, meliputi tiga bagian dasar. Bagian yang pertama adalah deteksi tepi. Tujuan deteksi tepi adalah untuk menurunkan jumlah titik dalam pencarian ruang bagi objek. Ketika titik tepi ditemukan oleh detektor tepi, algoritma transformasi Hough dikerjakan hanya pada titik tersebut. Untuk deteksi tepi, digunakan detektor tepi Canny, Roberts Cross, atau Sobel yang tujuannya memaksimalkan sinyal pada rasio derau dan lokalisasi serta meminimalisasi kesalahan pada deteksi tepi.

Transformasi Lingkaran Hough membentuk lingkaran sepanjang tepian yang ditemukan dengan jari-jari sebesar r. Setelah penggambaran lingkaran sepanjang garis tepian selesai, maka dicari daerah yang paling banyak dilewati garis dan kemudian daerah tersebut diasumsikan sebagai titik tengah citra yang dicari, seperti pada ilustrasi gambar berikut.

Penerapan Transformasi Hough

Contoh penerapan transformasi Hough untuk mendeteksi objek lingkaran dapat dilihat pada gambar berikut.

Array Akumulator

Secara umum Transformasi Hough bekerja dengan memanfaatkan sebuah deret Array yang dinamakan akumulator. Array akumulator ini memiliki dimensi yang berbeda-beda tergantung dari jumlah parameter dari objek yang dicari. Misalnya pada Transformasi Garis Hough memerlukan 2 buah parameter yakni r dan teta, maka dibentuklah sebuah deret array akumulator yang berdimensi 2. Pencarian kemudian dilakukan terhadap sebuah area pixel  dengan mencari kemungkinan hubungan atau garis yang ada. Setiap kemungkinan hubungan garis dihitung nilai r dan -nya terhadap titik pusat. Selanjutnya menyimpan nilai r dan teta-nya dari setiap kemungkinan hubungan tersebut pada array akumulator. Nilai-nilai pada akumulator akan dipetakan ke dalam sebuah grafik  yang dinamakan grafik akumulator dengan teta sebagai absis dan r sebagai ordinat. Berikut ini adalah salah satu contoh citra input dan bentuk grafik akumulatornya: