DETEKSI
GARIS PADA CITRA DIGITAL TRANSFORMASI HOUGH
DENGAN
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 algoritma konvensional diperlukan matriks 2 dimensi utnuk menyimpan titik potong dari kurva-kurva sinusoidal. Akan dijelaskan pemakaian matriks 1 dimensi untuk memodifikasi algoritma konvensional. Algoritma ini akan memberikan pemakaian memori yang lebih kecil dibandingkan dengan algoritma konvensioanal.
PENDAHULUAN Penglihatan (vision) pada robot dapat memberikan kemanlpuan kepadanya untuk bereaksi secara intelejen dan tleksibel. Hal ini bisa diperoleh dengan melakukan prosesproses: 1. Pengindraan. 2. Pengolahan awal. 3. Segmentasi. 4. Deskripsi. 5. Pengenalan. 6. Interpretasi. Segmentasi merupakan salah satu unsur yang penting dalam robot vision karena pada tingkat ini obyek-obyek pertama kali diekstraksi dari citra untuk pengenalan dan analisis selanjutnya. Ada beberapa metode segmentasi yang salah satu diantaranya berdasarkan pada deteksi tepi (edge detection) dari obyek dalam citra. Biasanya dari deteksi tepi ini juga diperoleh pixel-pixel yang berada disekitar batas (boundary) suatu obyek yang disebabkan oleh derau. Tetapi pixel-pixel ini tidak akan membentuk garis yang merupakan batas suatu obyek. Untuk mendapatkan suatu garis ini bisa diperoleh dengan menggunakan transfonnasi Hough. Kelemahan dalam penggunaan transfonnasi ini adalah dalam pemakaian memori yang besar, yang akan menjadi persoalan bila pengolahan 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 membutuhkan memori 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) akan ditransfonnasikan menjadi kurva sinusoidal ke bidang (p,8) menu rut persamaan : p = Xi cos 8 + Yi sin 8
(1)
Sitat dari transfonnasi ini adalah setiap titik yang terletak pada sebuah garis bila ditransfonnasikan ke bidang (p,8) akan menjadi kurva-kurva berpotongan pada sebuah titik (Gambar I).
sinusoidal yang saling
Gambar I. Transfonnasi Hough dari bidang x,y ke bidang p,8
Dengan menentukan koordinat dari titik potong ini, persamaan bi fang (x,y) bisa diperoleh menurut persamaan: pc = x cos 8c
+ y sin 8c
garis pada
(2)
Untuk menyimpan banyaknya titik potong antara 2 kurva sinusoidal diperlukan matriks 2-dimensi yang ukurannya tergantung pada besamya pembagian sumbu p dan sumbu 8. Bila sumbu p dan sumbu 8 dibagi menjadi K dan L maka diperlukan matriks l.erukuran (K x L). Diagram alir untuk mendapatkan persamaan garis pada bidang (x:y) ditunjukkan pada Gambar 2.
216
Max A(p,9)
y = (pc-x
.>
cos 9c)/.in
pc,9c
9c
Gambar 2. Diagram alir algoritma matriks 2-dimensi
Untuk mengurangi pemakaian memori yang cukup besar ini digunakan matriks I-dimensi yang besamya tergantung,pada pembagian sumbu e (Gambar 3).
217
p
...... ::1:: ......
......
. :~ ::~i
(J
.. :::: ..... .. .....: :::::!::S:::::::: • t •••••••••••••• ••••••••••• ::.. ::::s::.!:s:iJ.i!.: ::1:: iil!! : ::::::1 ':or I",.:.; ,: .s, ••s•••• ':"U'! .:•• ··:····:IU/·HU'· ,.•·.. •••• • t • .t :iliiiiiP=:iUI:jH
......
rr .
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 dinyatakan sebagai: (Xi - Xj) cos
e + (Yi- yj) sin e = 0
(3)
atau
B
(4)
Dengan demikian titik ke i akan berpotongan dengan (N-I) titik Iainnya dirnana N adalah jumlah data dan j = 1,2, N (i:t:j) pada persamaan (4). Titik-titik potong dengan sudut kemiringan e yang sama akan menempati lokasi memori yang sama pada matiks 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 dibandingkan harga maksimumnya. Diagram alir dari algoritma ini ditunjukkan pada Gambar 4.
218
ej = atan
(Xi - Xj) (Yi - Yj)
no
no
-----7>
I
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 bisa dilihat pada Gambar 5. Dilihat dari pemakaian memori jelas algoritma yang kedua menggunakan memori yang jauh lebih kecil jika dibandingkan algoritma yang kedua yaitu K dan K x L. Sedangkan untuk perhitungannya algortima pertama melakukan 1 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 pada transfonnasi Hough dengan matriks 2-dimensi dan diperIihatkan keefisienan dalam pemakaian memori dan juga waktu yang lebih singkat. . Algoritma pertama dan kedua digunakan untuk mendeteksi adanya sebuah garis sedangkan pada citra bisa terdapat lebih dari satu garis sehingga perIu ditambahkan algoritma untuk mendetekasi adanya garis-garis yang lain.
DAFTAR PUSTAKA 1. R.O. DUDAAND P.E. HART, "Use of the Hough transfonn to detect lines and curves 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 titik potong 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 ada dalam memori, lalu saling dibandingkan isinya. 2. Diantaranya untuk menentukan titik lenyap pada robot yang beIjalan dalam lorong dimana titik lenyap ini sebagai arah gerak robot yang dilengkapi kamera supaya tidak 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 deteksi kerangka dari pam-pam pada citra hasil Rontgen.
222
