DETEKSI GARIS PADA CITRA DIGITAL DENGANTRANSFORMASI HOUGH

Satrio Dewanto *

ABSTRAK

Transfonnasi Hough adalah salah satu metode yang sangat bennanfaat dalam pengolahan citra.Transfonnasi ini dapat digunakan untuk mendeteksi adanya garis pada citra digital. Pada algoritmakonvensional diperlukan matriks 2 dimensi utnuk menyimpan titik potong dari kurva-kurva sinusoidal.Akan dijelaskan pemakaian matriks 1 dimensi untuk memodifikasi algoritma konvensional. Algoritmaini akan memberikan pemakaian memori yang lebih kecil dibandingkan dengan algoritmakonvensioanal.

PENDAHULUAN

Penglihatan (vision) pada robot dapat memberikan kemanlpuan kepadanya untukbereaksi secara intelejen dan tleksibel. Hal ini bisa diperoleh dengan melakukan proses­proses:1. Pengindraan.2. Pengolahan awal.3. Segmentasi.4. Deskripsi.5. Pengenalan.6. Interpretasi.

Segmentasi merupakan salah satu unsur yang penting dalam robot vision karenapada tingkat ini obyek-obyek pertama kali diekstraksi dari citra untuk pengenalan dananalisis selanjutnya.

Ada beberapa metode segmentasi yang salah satu diantaranya berdasarkan padadeteksi tepi (edge detection) dari obyek dalam citra. Biasanya dari deteksi tepi ini jugadiperoleh pixel-pixel yang berada disekitar batas (boundary) suatu obyek yangdisebabkan oleh derau. Tetapi pixel-pixel ini tidak akan membentuk garis yangmerupakan batas suatu obyek. Untuk mendapatkan suatu garis ini bisa diperolehdengan menggunakan transfonnasi Hough. Kelemahan dalam penggunaan transfonnasiini adalah dalam pemakaian memori yang besar, yang akan menjadi persoalan bilapengolahan dilakukan pada komputer dengan kemampuan memori yang terbatas. Untuk

• Pusat Aplikasi Isotop clan Radiasi - BAT AN

215

mengatasi persoalan tersebut akan digunakan suatu algoritma yang membutuhkanmemori tidak terlalu besar untuk menghitung transfonnasi Hough ini.

ALGORITMA UNTUK TRANSFORMASI HOUGH

Pada transfonnasi Hough setiap titik (Xi,yJ pada citra digital dibidang (x,y) akanditransfonnasikan menjadi kurva sinusoidal ke bidang (p,8) menu rut persamaan :

p = Xi cos 8 + Yisin 8 (1)

Sitat dari transfonnasi ini adalah setiap titik yang terletak pada sebuah garis biladitransfonnasikan ke bidang (p,8) akan menjadi kurva-kurva sinusoidal yang salingberpotongan pada sebuah titik (Gambar I).

Gambar I. Transfonnasi Hough dari bidang x,y ke bidang p,8

Dengan menentukan koordinat dari titik potong ini, persamaan garis padabi fang (x,y) bisa diperoleh menurut persamaan:

pc = x cos 8c + y sin 8c (2)

Untuk menyimpan banyaknya titik potong antara 2 kurva sinusoidal diperlukanmatriks 2-dimensi yang ukurannya tergantung pada besamya pembagian sumbu p dansumbu 8. Bila sumbu p dan sumbu 8 dibagi menjadi K dan L maka diperlukan matriksl.erukuran (K x L). Diagram alir untuk mendapatkan persamaan garis pada bidang(x:y) ditunjukkan pada Gambar 2.

216

Max A(p,9) .> pc,9c

y = (pc-x cos 9c)/.in 9c

Gambar 2. Diagram alir algoritma matriks 2-dimensi

Untuk mengurangi pemakaian memori yang cukup besar ini digunakanmatriks I-dimensi yang besamya tergantung,pada pembagian sumbu e (Gambar 3).

217

p

(J

....... ::~i

.....,.•·..··:····:IU/·HU'·

:iliiiiiP=:iUI:jH::1::

:::: :':"U'! .:•• rr ......... . ......::::s::.!:s:iJ.i!.: iil!!

.t I" ,: •••• • t •........::1:: • t •••••••••••...... ::..:~:::::::1 :::::!::S::::::::':or ,.:.; .s, ••s••••......

..... • t ••••••••••••••

memori komputer

Gambar 3. Matriks l-dimensi untuk menyimpan titik potong

Prinsip algoritma ini berdasarkan sifat bahwa 2 buah titik pada bidang (x,y)hanya berpotongan satu kali di bidang (p,e) sehingga persamaan (1) dapat dinyatakansebagai:

atau

(Xi - Xj) cos e + (Yi- yj) sin e = 0

B

(3)

(4)

Dengan demikian titik ke i akan berpotongan dengan (N-I) titik Iainnya dirnanaN adalah jumlah data dan j = 1,2, N (i:t:j) pada persamaan (4). Titik-titik potongdengan sudut kemiringan e yang sama akan menempati lokasi memori yang sama padamatiks I-dimensi. Isi dari matriks ini disortir untuk mencari harga maksimumnya.Proses ini dilakukan untuk i= 1,2, (N-1) dan pada setiap i dicari dan dibandingkanharga maksimumnya. Diagram alir dari algoritma ini ditunjukkan pada Gambar 4.

218

ej = atan(Xi - Xj)

(Yi - Yj)

no

no I-----7> e = e (i-I)

k=i-I

(x-xk) cos e + (y-yk) sin e = 0 I

Gambar 4. Diagram alir algoritma matriks I-dimensi

219

x( a )

Gambar 5. a. Data citra yang akan dideteksi.b. Kurva sinusoidal dari data.

c. Garis yang terdeteksi.

PEMBAHASAN

Pemakaian dari algoritma diatas dilakukan dengan simulasi yang hasilnya bisadilihat pada Gambar 5. Dilihat dari pemakaian memori jelas algoritma yang keduamenggunakan memori yang jauh lebih kecil jika dibandingkan algoritma yang keduayaitu K dan K x L. Sedangkan untuk perhitungannya algortima pertama melakukan1 J x K kali kalkulasi dan algoritma kedua melakukan 1/2 (N x (N-I) kali kalkulasi.

220

KESIMPULAN

Telah dilakukan perubahan algoritma yang biasanya digunakan padatransfonnasi Hough dengan matriks 2-dimensi dan diperIihatkan keefisienan dalampemakaian memori dan juga waktu yang lebih singkat. .

Algoritma pertama dan kedua digunakan untuk mendeteksi adanya sebuah garissedangkan pada citra bisa terdapat lebih dari satu garis sehingga perIu ditambahkanalgoritma untuk mendetekasi adanya garis-garis yang lain.

DAFTAR PUSTAKA

1. R.O. DUDAAND P.E. HART, "Use of the Hough transfonn to detect lines andcurves in pictures", Comm.Ass.Comput. March IS, II-IS (1975)

2. D.H. BALLARD, "Generalizing the Hough transfonn to detect arbitrary shapes",Pattern Recognition vol 12, (2) (1981) II 1-122

3. K.S. FU, R.c. GONZALES and C.S.G. LEE, ROBOTICS : "Control, Sensing,Vision and Intelligence", McGraw Hill Int. Edition (1987)

221

DISKUSI

M. BUNJAMIN :

Apakah keperluan memori yang besar dapat diganti oleh memori dalam hard disk?

SATRIO DEWANTO:

Pada prinsipnya dapat diganti hanya masalah waktu yang lebih lama.

ELFRIDA SARAGI :

I. Bagaimana cara yang paling cepat untuk menentukan titik maksimum pada titikpotong kedua garis transformasi tersebut ?

2. Apa pemanfaatan deteksi garis pada citra digital tersebut ?

SATRIO DEWANTO :

1. Cara yang saya gunakan adalah penyortiran biasa. Sete1ah semua titik potong adadalam memori, lalu saling dibandingkan isinya.

2. Diantaranya untuk menentukan titik lenyap pada robot yang beIjalan dalam lorongdimana titik lenyap ini sebagai arah gerak robot yang dilengkapi kamera supayatidak menabrak dinding.- Untuk mendeteksi benda yang akan diambil oleh jari robot, posisinya dimana.- Dalam pengembangannya dapat digunakan untuk deteksi obyek dengan bentuk

sembarang, bukan hanya garis. Jadi dapat digunakan untuk misalnya deteksikerangka dari pam-pam pada citra hasil Rontgen.

222