Makalah Pengolahan Citra
Image Thinning
Kelompok 11 Aldiantoro Nugroho
(1201000083)
Cininta
(1201000261)
Dhini Fitriani
(1201000342)
N. Rifka N. Liputo
(1201000768)
Yoga Lestyaningrum
(1201001098)
November 2003
Fakultas Ilmu Komputer Universitas Indonesia
1
ABSTRAK
Pembahasan mengenai image thinning membuka penelitian ke arah aplikasi pemrosesan image yang lain. Dengan algoritma image thinning, berbagai contoh penerapan pada proses pengolahan citra menjadi makin bervariasi dan sangat membantu proses pengenalan sebuah citra sebagaimana yang
dibahas pada
contoh aplikasi. Pada makalah ini pertama-tama akan dijelaskan beberapa istilah yang menyangkut image thinning pada pengolahan citra dijital, kemudian baru diberikan definisi dari image thinning dan algoritma untuk melakukan proses image thinning pada suatu citra dijital. Di bab berikutnya baru diberikan contohcontoh pemakaian image thinning yang ada hubungannya antara bidang ilmu komputer dengan bidang ilmu lain.
Bagaimana kaitan antara konsep morfologi yang dibahas di bab 2 dengan algoritma zhang suen yang dibahas di bab 3?? Kemudian di bab 4 kok contoh menggunakan morfologi dan bukan algoritma zhang suen?
2
DAFTAR ISI
Abstrak ..............................................................................................
2
Daftar Isi ...........................................................................................
3
Bab 1 Pendahuluan ...........................................................................
4
1.1. Latar Belakang ..........................................................................
4
1.2. Tujuan dan Manfaat Penulisan .....................................................
4
1.3. Ruang Lingkup Penulisan ............................................................
4
Bab 2 Image Thinning ........................................................................
5
2.1. Pendahuluan: Definisi Beberapa Terminologi..................................
5
2.2. Definisi, Tujuan dan Manfaat Thinning ..........................................
6
Bab 3 Algoritma Image Thinning ........................................................
8
3.3. Algoritma dan Proses Thinning.....................................................
8
3.3.1. Thinning dengan Algoritma Zhang Suen ...............................
8
Bab 4 Aplikasi Image Thinning ........................................................... 10 4.1. Ekstraksi Cacing Filaria ................................................................ 10 4.2. Pengenalan Citra Daun ................................................................ 13 Penutup .............................................................................................. 15 Referensi ............................................................................................ 16
3
BAB 1 PENDAHULUAN
1.1. Latar Belakang Sejak kemunculan pertama gambar digital tahun 1920, terutama munculnya aplikasi dalam teknologi komputer dalam memproses gambar digital tahun 1960 pemoresaan sebuah gambar dalam komputer menjadi lebih mudah. Teknologi pencitraan komputer yang berkembang dengan cepat dan mencapai hasil yang hebat dalam menggantikan, bahkan melampaui kehebatan penglihatan manusia. Teknologi pemrosesan citra oleh komputer banyak digunakan pada berbagai aplikasi, baik kedokteran, biologi, geografis, dan banyak lainnya. Salah satu teknologi pemrosesan citra yang digunakan dalam berbagai bidang tersebut adalah penipisan gambar, yang lebih dikenal dengan image thinning. Dalam sebuah aplikasi biasanya image thinning dikombinasikan dengan berbagai fungsi lain, seperti skeletoning, region filling, hit or miss, dan sebagainya.
1.2. Tujuan dan Manfaat Penulisan Makalah ini dibuat dengan tujuan mengetahui bagaimana proses image thinning, algoritma yang digunakan, dan apa saja contoh aplikasinya dalam dunia komputer. Tujuan lain dari penulisan makalah ini adalah untuk memenuhi tugas mata kuliah pengolahan citra mengenai image thinning.
1.3. Ruang Lingkup Penulisan Penulisan makalah ini terbatas pada pengertian image thinning dan beberapa terminologi yang berkaitan dengan image thinning, algoritma, dan contoh aplikasi image thinning.
4
BAB 2 IMAGE THINNING
2.1. Definisi Beberapa Terminologi Thinning merupakan salah satu algoritma perubahan citra dalam morphological operation. Oleh karena itu sebelum membahas tentang thinning pada pengolahan citra, kami akan membahas sedikit tentang konsep morphological operation yang berkaitan dengan thinning. Definisi singkat beberapa terminologi yang terlibat dengan pemahaman konsep thinning juga akan dicantumkan pada subbab ini. Berdasarkan etimologi bahasa, morphology berasal dari kosakata bahasa Jerman yaitu morphologie yang terdiri dari morph+logie/logy 1. Morph adalah suatu kata kerja yang berupa singkatan dari metamorphose yang artinya perubahan bentuk atau karakter akibat perubahan pada struktur atau komposisi (transformasi). Sesuai dengan arti dasarnya, konsep Morphological Operation pada pengolahan citra adalah operasi-operasi perubahan bentuk pada binary image atau grayscale image. Berbagai jenis Morphological Operation antara lain : Erosion, dilation, opening, closing, thinning dan thickness, namun pembahasan makalah ini hanya akan berfokus pada konsep Thinning. Pada paragraf sebelumnya telah disinggung tentang binary image dan grayscale image. Definisi binary image adalah citra yang direpresentasikan sebagai himpunan dari pixel-pixel foreground(obyek depan)2. Binary image merupakan citra yang hanya mempunyai dua informasi intensitas warna, yaitu hitam dan putih. Konvensi untuk menentukan intensitas warna pada binary image bisa berbeda-beda, namun pada umumnya digunakan konvensi yang mendeskripsikan nilai 0 sebagai warna hitam dan nilai 1 atau 255 sebagai warna putih. Warna putih biasanya juga digunakan untuk warna foreground, sedangkan warna hitam adalah warna background, namun sekali lagi ketentuan ini bukan merupakan 1
Main Entry: mor·phol·o·gy;Pronunciation: mor-'fä-l&-jE;Function: noun;Etymology: German Morphologie, from morph- + -logie –
logy;Date: 1830;1 a : a branch of biology that deals with the form and structure of animals and plants b : the form and structure of an organism or any of its parts;2 a : a study and description of word formation (as inflection, derivation, and compounding) in language b : the system of word-forming elements and processes in a language;3 a : a study of structure or form b : STRUCTURE, FORM;4 : the external structure of rocks in relation to the development of erosional forms or topographic features;- mor·pho·log·i·cal /"mor-f&-'lä-jik&l/ also mor·pho·log·ic /-'lä-jik/ adjective. Main Entry: morph;Function: verb;Etymology: short for metamorphose;Date: 1975;transitive senses : to change the form or character of : TRANSFORM;intransitive sense : to undergo transformation [Merriam-Webster]. 2
A binary image is represented by the set of foreground pixels. The universal set is the set of all pixels in the image
5
keharusan tergantung dari binary image yang dihasilkan. Binary image seringkali dihasilkan dari proses thresholding suatu grayscale image (citra yang memiliki informasi tingkat keabuan) dan color image (citra yang memiliki informasi intensitas warna yang bervariasi). Pada setiap operasi morphology selalu diperlukan adanya structuring element/SE atau yang biasa disebut dengan kernel, yaitu basis atau matriks yang menentukan detil-detil tertentu akibat pengaruh suatu operator pada citra. SE/Kernel mempunyai bermacam-macam ukuran/dimensi/orde matriks, masingmasing mempunyai satu origin yang bisa terletak dimana saja, namun pada umumnya origin terletak di entry tengah pada matriks. SE juga memiliki satu atau lebih entry kosong (empty spots) yang dianggap don’t care. Contoh structuring element/ kernel :
2.2. Definisi, Tujuan dan Manfaat Thinning Definisi image thinning adalah proses morphology image yang merubah bentuk asli
binary
image
menjadi
image
yang
menampilkan
batas-batas
obyek/foreground hanya setebal satu pixel. Algoritma thinning secara iteratif ‘menghapus’ pixel-pixel pada binary image, dimana transisi dari 0 ke 1 (atau dari 1 ke 0 pada konvensi lain) terjadi sampai dengan terpenuhi suatu keadaan dimana satu himpunan dari lebar per unit (satu pixel) terhubung menjadi suatu garis. Morphological thinning dari binary image oleh SE juga melibatkan proses hit-or-miss transform. Sepintas, image thinning mempunyai kemiripan dengan edge detection dalam hal output
dari
citra
yang
dihasilkan,
kedua
proses
tersebut
sama-sama
menampilkan batas obyek pada citra. Namun, tetap saja ada perbedaaan antara Image Thinning dengan Edge Detection dari segi prinsip kerjanya, yaitu : •
Edge detection : merubah graylevel image atau color image menjadi image yang menampilkan batas-batas/boundaries obyek berdasarkan kekontrasan warna antar pixel.
•
Image Thinning : mereduksi pixel-pixel pada obyek binary image menjadi pixel yang benilai sama dengan nilai pixel pada background. Menghasilkan
6
binary image dengan informasi berupa batas-batas obyek berdasarkan pixel dengan ketebalan satu pixel. Tujuan image thinning adalah untuk menghilangkan pixel-pixel yang berada didalam obyek depan (foreground object) pada binary images. Manfaat image thinning adalah sebagai berikut : •
biasanya diterapkan pada proses skeletonisasi.
•
berguna
untuk
merapikan/menyempurnakan
hasil
output
detection dengan cara mengurangi lebar sisi/batas/edge.
7
proses
edge
BAB 3 ALGORITMA IMAGE THINNING
3.1. Algoritma dan Proses Thinning Ada beberapa algoritma yang digunakan dalam proses thinning. Diantaranya adalah metode Stentiford dan metode Zhan-Suen. Stentiford
method
menggunakan
template-based
mark-and-delete
thinning
algorithm. Algoritma ini menggunakan template matching, dimana jika bagian dari gambar sesuai dengan template, hapus pixel yang di tengah. Zhan-Suen method menggunakan metode iterasi, yang berarti nilai yang baru didapat dari proses sebelumnya. Cara ini mudah untuk diimplementasikan.
3.3.1 Thinning dengan Algoritma Zhang Suen
gambar 1
Langkah-langkahnya: a. Beri tanda semua piksel 8-tetangga yang memenuhi kondisi (1) sampai dengan (4). b. Hapus piksel tengahnya. c. Beri tanda semua piksel 4-tetangga yang memenuhi kondisi (5) sampai dengan (8). d. Hapus piksel tengahnya. Lakukan langkah a sampai d berulang kali, sampai tidak ada perubahan. Kondisi: (1) 2 ≤ N(p1) ≤ 6 (2) S(p1) = 1 (3) p2 • p4 • p6 = 0
8
(4) p4 • p6 • p8 = 0 (5) 2 ≤ N(p1) ≤ 6 (6) S(p1) = 1 (7) p2 • p4 • p8 = 0 (8) p2 • p6 • p8 = 0 Dimana: N(p1) = jumlah dari tetangga p1 yang tidak nol S(p1) = jumlah transisi 0 – 1 dalam urutan p2, p3, ... Penamaan piksel : p9
p2
p3
p8
p1
p4
p7
p6
p5
Jika pada gambar 1 dilakukan proses thinning, maka gambar akan menjadi:
9
Bab 4 APLIKASI IMAGE THINNING
4.1. Ekstraksi Cacing Filaria Pada contoh berikut ini, image thinning digunakan untuk mengekstraksi citra cacing filaria dari suatu citra yang didapat. Berikut adalah langkah-langkahnya:
(Gambar 1) Gambar di atas adalah citra mikroskopik dari transmiter cacing filaria.
(Gambar 2: Closing by reconstruction) Berikutnya pada citra tersebut dilakukan filter morfologis untuk memisahkan bagian-bagiannya yang terlihat berlubang. Filtering ini dilakukan dengan closing by reconstruction.
(Gambar
3:
Subtraction)
Selanjutnya
dilakukan
morphological
gambar 1 dari gambar 2 yang menghasilkan gambar 3.
10
subtraction
(Gambar 4: Thresholding) Berikutnya dilakukan thresholding pada gambar, yang menghasilkan gambar 4.
(Gambar 5: Skeletonization) Sekarang tujuannya adalah untuk membedakan cacing filaria dari obyek yang lain. Hal itu dapat dilakukan dengan mengingat fakta bahwa cacing filaria lebih panjang daripada obyek lain. Sehingga kita tinggal mencari tanda untuk obyek terpanjang dari binary image. Kita aplikasikan skeleton dengan cara thinning pada gambar 4.
(Gambar 6: N-Thinning) Dilanjutkan oleh N-Thinning pada gambar 5.
11
(Gambar 7: Skeletonization) Tail dari citra di atas bisa menjadi tanda yang kita inginkan. Untuk mendapatkannya, kita bisa mengaplikasikan skeleton yang akan menghabiskan citra pada gambar 6.
(Gambar 8: Subtraction) Dan kurangkan citra gambar 7 dari citra gambar 6 yang akan menghasilkan gambar 8.
(Gambar 9: Opening by reconstruction) Untuk menyelesaikannya, kita hanya harus merekonstruksikan gambar cacing filaria dari tail. Ini dilakukan dengan opening by reconstruction yang hasilnya adalah gambar 9.
(Gambar 10: Citra kombinasi) Gambar di atas adalah gambar kombinasi antara citra cacing filaria yang terekstraksi dan citra asli.
12
4.2. Pengenalan Citra Daun Contoh kedua adalah pada aplikasi Leaves Recognition mengenai penggunaan image thinning untuk mengenali citra daun yang belum diketahui agar dapat menspesifikasikan spesies daun tersebut. Tujuan dari program ini yaitu untuk menunjukkan bahwa frame luar dari suatu daun dan Backpropagation Network sudah cukup untuk memberikan pernyataan mengenai spesies suatu daun. Sebelum melakukan thinning pada citra daun, dilakukan dulu Prewitt Edge detection agar dapat mengenali frame luar secara tepat. Prewitt Edge detection mengenali egde dengan preconfigured threshold. Lalu algoritma thinning akan memperkecil threshold-based edge ini menjadi frame satu garis. Setelah itu baru dapat dilakukan token recognition.
Pemakaian algoritma thinning di sini akan
memproses citra secara rekursif dan memperkecil garis-garis yang ditemukan menjadi garis-garis selebar satu piksel dengan cara membandingkan keadaan piksel yang sesungguhnya dengan pola tertentu lalu memperkecilnya. Ide transformasi dari bentuk citra daun menjadi bentuk jaringan syaraf yaitu karena sinus dan kosinus dari sudut daun merepresentasikan kriteria dari pengenalan pola.
13
Citra di atas menunjukkan bagian citra daun yang telah diproses dengan edge detection dan algoritma thinning. •
Garis hijau menunjukkan bentuk citra daun setelah dilakukan edge detection dan thinning.
•
Persegi-persegi merah menunjukkan titik-titik pada citra daun yang akan dihubungkan dengan garis biru.
•
Garis biru yang menghubungkan persegi-persegi merah akan digunakan untuk menghitung sinus dan kosinus dari sudut-sudut yang terbentuk. Garis biru tersebut adalah representasi dari leaf token.
Gambar yang diperbesar menunjukkan gambar segitiga siku-siku yang dapat merepresentasikan leaf token yang akan digunakan untuk menghitung jaringan syaraf.
Gambar di atas adalah representasi dari token sebuah citra daun. Sudut-sudut A dan B adalah bagian penting yang akan dicocokkan dengan lapisan jaringan syaraf. Dengan kedua sudut ini, dapat direpresentasikan arah dari hipotenusa dari titik P1 ke titik P2 yang sangat penting untuk representasi citra daun.
14
PENUTUP
Dari berbagai pembahasan yang telah dilakukan di atas, dapat dilihat bahwa image thinning seringkali berhubungan dengan proses pengolahan citra yang lain, seperti subtraction, reconstruction, skeletoning, dan sebagainya. Dan proses thinning juga sangat berguna untuk pengenalan citra tertentu, seperti yang dikemukakan pada contoh aplikasi di atas.
15
referensi Extraction of Filarial Worms [on-line]. Didapat dari http://www.dca.fee.unicamp.br/projects/khoros/mmach/tutor/application/bi ological/fila/fila.html; Internet; diakses tanggal 15 November 2003.
Leaves Recognition v1.0 [on-line]. Didapat dari http://damato.lightspeed.de/lrecog/ ; Internet; diakses tanggal 16 November 2003. Mathematical Morpohology [on-line]. Didapat dari www.imm.dtu.dk/~jmc/02501/lectures/02501_morphology.pdf; Internet; diakses tanggal 14 November 2003. Merriam-Webster Dictionary [on-line]. Didapat dari http://www.m-w.com/cgibin/dictionary; Internet; diakses tanggal 15 November 2003. Performance Evaluation of Shape Simplification Methods [on-line]. Didapat dari http://www.tcs.auckland.ac.nz/~btech/btech2002/ktom006/ index_files/Project%20Report.doc; Internet; diakses tanggal 14 November 2003. Selected Morphological Algorithm [on-line]. Didapat dari http://documents.wolfram.com/applications/digitalimage/UsersGuide/6.5.ht ml Internet; diakses tanggal 15 November 2003. Thining [on-line]. Didapat dari http://vision.cse.psu.edu/resources/hipr/html/thin.htm; Internet; diakses tanggal 14 November 2003. http://www.eng.fiu.edu/me/robotics/elib/am_st_fiu_ppr_2000.pdf; Internet; diakses tanggal 14 November 2003. lki-www.informatik.uni-hamburg.de/~neumann/BV-SS-2002/BV-L8.pdf; Internet; diakses tanggal 14 November 2003. http://www.cs.aue.auc.dk/~vok/ap/6._Morphological_Operators.ppt; Internet; diakses tanggal 14 November 2003.
16
