METODE SHAPE DESCRIPTOR BERBASIS SHAPE MATRIX UNTUK ESTIMASI BENTUK
STRUCTURING ELEMENT Sri Huning A NRP. 5108201002 DOSEN PEMBIMBING Dr. Agus Zainal Arifin, S. Kom, M.Kom Anny Yuniarti, S.Kom, M.Comp.Sc
Abstrak
Operasi morfologi analisa bentuk Konsep morfologi : mem-passing sebuah structuring element (strel) pada sebuah citra strel sebagai mask Pemilihan Strel memegang peranan penting berpengaruh terhadap hasil pengolahan citra. Sebuah structuring element yang sesuai digunakan pada sebuah objek, belum tentu sesuai digunakan pada objek lain Belum ada pedoman umum pemilihan strel kemiripan bentuk dengan objek yang diteliti yang ditentukan secara manual. (Gang Li, dkk, 2009). Bentuk (shape) dapat direpresentasikan ke dalam beberapa cara (Cesar dan Costa, 2009) shape descriptor
Abstrak (lanjutan)
Tujuan penelitian :mengusulkan suatu metode baru untuk estimasi bentuk structuring element berdasar pada representasi bentuk objek yang diteliti berbasis shape matrix. menguji kinerja bentuk structuring element yang didapatkan diujicobakan untuk deteksi tepi menggunakan operasi morfologi gradien. Hasil Uji Coba (akurasi rata-rata): - 30 Citra sintetis : 99,6 % - 3 citra riil : 98,4 %
Latar Belakang
Bentuk Umum : rectangle, square, disk, linear, dan diamond kelebihan dan kekurangan masing-masing. Bentuk structuring element yang sesuai untuk satu objek belum tentu sesuai untuk objek lain belum ada pedoman baku kemiripan bentuk objek yang diteliti - Gang Li, dkk (2009) : deteksi sel tumor gastric rectangle - Obara (2007) : deteksi retakan kecil (microcrack) pada batu dolomit linear - Ruberto, dkk (2000) : deteksi sel darah pada penyakit malaria disk. Oleh karena itu bentuk objek dapat digunakan sebagai dasar untuk estimasi bentuk stucturing element.
Latar Belakang (Lanjutan)
Sebuah representasi yang baik 1. akan dapat menggambarkan karakteristik intrinsik dari sebuah shape secara eksplisit. 2. Representasi sebuah shape juga harus invarian terhadap rotasi, scaling dan transformasi (Loncaric, 1999). Beberapa penelitian mengemukakan bahwa shape matrix dapat menggambarkan bentuk objek serta invarian terhadap scaling, rotasi, dan translasi (Goshtasby, 1985, C. Sheng, 2005). Representasi bentuk objek ini dapat digunakan untuk estimasi bentuk structuring element yang mendekati bentuk objek yang diteliti.
Square
Disk/?????
Kontribusi
mengusulkan metode baru untuk mengestimasi bentuk structuring element dengan menganalisa representasi shape/bentuk berbasis shape matrix.
Rumusan Masalah
Bagaimana cara merepresentasikan objek dalam bentuk shape matrix ? Bagaimana cara menentukan bentuk structuring element berdasar representasi objek berbasis shape matrix ?
Tujuan dan Manfaat Tujuan :
mengestimasi bentuk structuring element dengan menggunakan algoritma berbasis shape matrix Manfaat : mendapatkan metode lain untuk mencari bentuk structuring element untuk dapat diterapkan pada operasi-operasi pengolahan citra yang menggunakan pendekatan morfologi seperti deteksi tepi, segmentasi, noise reduction, dan beberapa operasi pengolahan citra lain
Batasan Masalah
Objek citra yang digunakan adalah citra sintetis dan citra asli. Citra uji yang digunakan tidak mengandung noise (noiseless). Penelitian ini hanya membahas operasi deteksi tepi meggunakan morfologi gradien pada morfologi Citra dan structuring element yang dibahas bertipe binary. Menggunakan bahasa pemrograman Matlab 7.0.1
BAB 2 DASAR TEORI
2.1. Morfologi
Tujuannya : memperoleh informasi mengenai bentuk dari suatu citra dengan mengatur bentuk dan ukuran suatu elemen penstruktur (structuring element). Morfologi : analisa bentuk, bukan mengubah bentuk
2.1.1. Structuring Element B
Gambar 2.2. Contoh Structuring Element (a) titik “O” adalah titik poros, (b) representasi biner dari structuring element
Strel kunci penting dalam morfologi komponen : yaitu bentuk dan ukuran.
Bentuk-bentuk Umum Strel
b. Square 3 x 3 a. Disk ukuran 3
c. Diamond ukuran 3
d. Linear ukuran 3, rotasi 45o
e. Rectangle 3 x 5 Gambar 2.5. Bentuk-bentuk Umum Structuring Element
Pengaruh Strel
(a)
(b)
(c)
Gambar 2.3 Citra Hasil MDMF Filter menggunakan strel dengan bentuk sama tetapi ukuran berbeda (a) strel 2x2 ; (b) strel 3 x 3 ; (c) strel 4 x 4
(a)
(b)
Gambar 2.4. Citra Hasil MDMF Filter menggunakan strel dengan bentuk berbeda tetapi ukuran sama (a) strel rectangle 3 x 3 ; (b) strel diamond 3 x 3
2.1.2. Operasi-operasi Morfologi
Translasi Dilasi Erosi Opening Closing Morfologi gradien
2.2 Representasi Shape
Taksonomi Teknik Representasi Shape Menggunakan Region-Based
2.3. Shape Matrix
0
LS
Misalkan adalahMatrix sebuah objek AlgoritmaSShape 1. Mencari didapatkan titik tengah titik objek, potong misal titiktitik O A 2. Akan radius terjauh objek, misal 4. Menentukan 3. Buat lingkaran ukuran mengelilingi ordo 5. Bagi garis OA (n-1) bagian. padaobjek i1matrix , i2,dengan …,mmenjadi in-1. shape x n, r = misal L Akan diketahui panjang =L Kemudian buat setiap lingkaran dengan Kemudian titikOA potong, m = 6 dan ndari =5 radius adalah denganmasing-masing arah berlawanan jarum jam, L/(n-1), 2L/(n-1), …, (n-1)L/(n-1) Bagi setiap lingkaran menjadi m busur Dengan dθ = 360/m derajat A
θ dθ = 360/m
Algoritma menentukan nilai elemen shape matrix
Contoh shape matrix m = 6, n = 5, L = 10 Koordinat (iL/(n-1),,j(360/m)
n=i
A
m=j
Gambar 2.10. (a) contoh shape , (b) Shape Matriks (Goshtasby, 2005)
BAB 3. Metode Penelitian
3.1. Desain Sistem mulai
selesai
Menentukan Citra Uji dan citra ground truth
Menghitung Kinerja Algoritma
Gambar 3.1. Desain Sistem
Menentukan representasi bentuk (shape matrix ) untuk dapat menentukan bentuk structuring element
Melakukan operasi morfologi gradient menggunakan strel yang didapat
1. Penentuan Citra Uji dan Citra Ground Truth A. CITRA UJI Citra Uji : citra sintetis (40 buah) dan citra asli (riil) (3 buah). Ukuran citra sintetis : 140 x 140 piksel. Sedangkan ukuran citra riil tidak ditentukan. citra grayscale dan citra biner. asumsi yang digunakan adalah nilai ‘1’ : objek, nilai ‘0’ : background dari objek Binerisasi citra uji juga tidak mengandung noise Menguji Rotasi dan Scaling, Hole, dan Objek terpisah
B. CITRA GROUND TRUTH : manual menggunakan aplikasi Paint. Ukuran disesuaikan dengan ukuran citra yang diuji. citra biner
2. Menentukan shape matrix dari citra binerisasi citra uji (optional)
mencari koordinat piksel penyusun objek Mencari titik tengah dari objek (titik O) Mencari radius terjauh dari objek (titik A) Membuat lingkaran yang mengelilingi objek dengan r = L Menentukan ukuran shape matrix (m x n) Bagi garis OA menjadi bagian dengan jarak yang sama Membuat lingkaran - dengan titik pusat O – dengan radius lingkaran masingmasing adalah L /(n − 1), 2 L /(n − 1), ..., (n − 1) L /(n − 1) Membagi lingkaran menjadi busur yang sama dimana sudut masing-masing derajat.
d θ = 360 / m
menentukan nilai-nilai elemen shape matrix
2.1. Binerisasi
mengubah tipe citra menjadi bertipe biner (hitam putih). 1. baca citra uji 2. tentukan nilai threshold 3. ubah citra uji menjadi citra biner berdasar pada nilai threshold Gambar 3.5 Algoritma Proses Binerisasi Citra
Citra Asli
Citra Biner, threshold = 0.725 (185)
2.2. Mencari Koordinat Piksel Penyusun Objek
Piksel-piksel penyusun objek berwarna putih (bernilai ’1’), sehingga harus dicari terlebih dahulu piksel-piksel yang bernilai ”1’. Fungsi yang digunakan adalah fungsi find. Dari tahapan ini akan didapatkan koordinatkoordinat piksel yang termasuk objek.
2.3. Mencari Titik Tengah Objek Persamaan mencari koordinat pusat objek (c1,c2),
1 c1 = N
N
1 xi , c 2 = ∑ N i =1
N
∑y i =1
i
(3.1)
dimana ( x i , y i )(i = 1,2,..., N ) adalah koordinat dari piksel dalam objek dan N adalah jumlah piksel dalam objek.
Gambar 3.7. Hasil Pencarian Titik Tengah Objek
2.4. Mencari Radius Terjauh dari Objek
Eucledian distance setiap piksel pada objek dihitung jaraknya terhadap titik pusat O(c1,c2)
D = ( x1 − c1 ) + ( y1 − c 2 ) 2
2
Di mana (x1,y1) adalah koordinat setiap piksel pada objek, sedangkan (c1,c2) adalah koordinat titik pusat objek.
A (rMax,cMax) L O(c1,c2)
Gambar 3.9. Ilustrasi Titik Pusat dan Radius Terjauh
Gambar 3.10. Radius terjauh Bentuk 1
2.5. Membuat lingkaran yang mengelilingi objek dengan besar jari-jari sama dengan radius terjauh
Gambar 3.12. Lingkaran Mengelilingi Bentuk 1
2.8. Menentukan nilai-nilai elemen shape
matrix For i = 0 to (n – 1) For j = 0 to (m – 1) If titik dengan koordinat polar ( iL /( n − 1), j (360 / m)) berada di dalam shape, then otherwise M (i, j ) : = 0 M (i, j ) : = 1 1
1
1
0
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
1
Gambar 3.14. Contoh Shape Matrix ukuran 5 x 5
3. Deteksi Tepi Menggunakan Operasi
Morfologi Gradien start Citra Uji, structuring element (SE) Melakukan operasi dilasi pada citra uji menggunakan structuring element (SE) Melakukan operasi erosi pada citra uji menggunakan structuring element (SE) Melakukan pengurangan terhadap citra hasil dilasi dikurangi citra hasil erosi Citra Hasil Deteksi tepi
selesai Gambar 3.15. Proses Deteksi tepi
Citra Asli
Citra Hasil Operasi Dilasi
Citra Hasil Operasi Erosi
Citra Hasil Deteksi Tepi
4. Menghitung Kinerja Algoritma TP + FN Akurasi = TP + TN + FP + FN Tabel 3.1. Perhitungan Akurasi Sistem
Ground Truth Edge Hasil Sistem
Bukan Edge
Edge
True Positif (TP)
False Positif (FP)
Bukan Edge
False Negatif (FN)
True Negatif (TN)
BAB 4 UJI COBA DAN ANALISIS HASIL
Data Uji Coba 1. Citra Ground Truth 2. Citra Sintetis
Citra Uji Normal Citra Uji dengan Variasi Scaling dan Rotasi Citra Uji dengan Hole Citra Uji dengan Objek Terpisah
3. Citra Riil
CITRA GROUND TRUTH (normal) 5/30
Citra Uji Normal (5/30)
Citra Uji dengan Variasi Scaling dan Rotasi
70% 98 x 98 Asli 140 x 140 150% 210 x 210
45o 201 x 201
Citra Uji dengan Hole
Hole 1
Hole 2
Hole 3
Citra Uji dengan Objek Terpisah
Pisah 1
Pisah 2
Pisah 3
Citra Riil
Breast
gigi
Sel darah
Structuring Element Pembanding
Diamond Disk Square
Hasil Pengujian (Citra Normal) N0
Nama Objek
Akurasi (%) SM
Square
Diamond
Disk
1 Bentuk 1
99,99
99,99
98,33
98,33
2 Bentuk 2
97,98
97,97
98,00
98,00
3 Bentuk 3
98,28
98,28
98,20
98,20
4 Bentuk 4
99,61
99,61
98,51
98,51
5 Bentuk 5
99,97
99,98
99,31
99,31
6 Bentuk 6
99,76
99,76
99,34
99,34
7 Bentuk 7
99,98
99,98
99,15
99,15
8 Bentuk 8
99,97
99,97
98,88
98,88
9 Bentuk 9
99,97
99,97
98,57
98,57
10 Bentuk 10
99,99
99,99
99,41
99,41
11 Bintang
99,99
99,98
98,51
98,51
12 Kotak
100,00
100,00
99,98
99,98
13 Flag
99,92
99,92
99,62
99,62
14 Bunga
98,29
98,26
98,28
98,28
15 Kotaktumpul
100,00
100,00
99,82
99,82
No
Nama Objek
Akurasi (%) SM
Square
Diamond
Disk
16 Layang
99,27
99,27
97,76
97,76
17 Lingkaran 1
99,99
99,99
99,00
99,00
18 Lingkaran 2
99,97
99,97
98,83
98,83
19 Oval
99,99
99,99
99,37
99,37
20 Persegi
100,00
100,00
99,98
99,98
21 PMI
100,00
100,00
99,94
99,94
22 Segienam
99,99
99,99
99,28
99,28
23 Segitiga 1
100,00
100,00
99,05
99,05
24 Segitiga 2
99,91
99,91
98,73
98,73
25 Kepala
95,40
95,39
95,40
95,40
26 Trapesium
100,00
100,00
99,42
99,42
27 Tanjakan
99,69
99,69
99,39
99,39
28 Segilima
100,00
100,00
99,22
99,22
29 Trapesium 2
100,00
100,00
99,30
99,30
30 Daun
99,99
99,99
99,27
99,27
Tabel 4.3. Perbandingan Rata-rata Akurasi Uji Coba Normal
Structuring No Element 1 shape matrix 2 square 3 diamond 4 disk
Rata-rata Akurasi (%) 99,6 99,5 98,9 98,9
Ukuran Structuring Element : 3 x 3
Citra Asli
Citra Ground Truth
Hasil Shape Matrix 100 %
Hasil Square
Hasil Diamond
Hasil Disk
100 %
99,98 %
99,98 %
Ukuran Structuring Element : 3 x 3
Citra Asli
Citra Ground Truth
Hasil Shape Matrix (98,29%)
Hasil Square (98,26%)
Hasil Diamond (98,28%)
Hasil Disk (98,28%)
Tabel 4.6. Hasil Pengujian Pada Citra Uji dengan Perubahan Scaling dan Rotasi No
Nama Citra
Ukuran
Akurasi (%)
Strel
SM
Square
Diamond
Disk
1
persegi_besar_150
3x3
100
100
99,99
99,99
2
persegi_kecil_70
3x3
100
100
99,95
99,95
3
persegi_rotasi_+45 3 x 3
100
100
98,94
98,94
4
persegi_rotasi_-45
100
100
98,94
98,94
3x3
Tabel 4.7. Hasil Pengujian Pada Citra Uji dengan Hole No Nama Citra Ukuran
Akurasi (%)
Strel
SM
Square
Diamond
Disk
1
Hole 1
3x3
100
100
98,36
98,36
2
Hole 2
3x3
100
100
99,95
99,95
3
Hole 3
3x3
99,99
99,99
99,58
99,58
Tabel 4.9. Perhitungan Akurasi Citra Riil Nama Objek No
Akurasi (%) SM
1
Breast
97,02
2
Gigi
98,53
3
Sel Darah Rata-rata
Square Diamo nd 96,41
Disk
96,81
96,81
98,53
96,89
97,80
99,52
99,51
98,06
98,06
98,4
98,1
97,2
97,2
Analisa Hasil Uji Coba
metode shape descriptor berbasis shape matrix dapat diandalkan untuk estimasi bentuk structuring element.
Kelebihan : bentuk structuring element menyesuaikan dengan objek yang diteliti, sehingga bentuk structuring element yang didapatkan benar-benar merupakan representasi bentuk objek yang diteliti. Kelemahan : Akan tetapi pemilihan ukuran shape matrix m x n sangat mempengaruhi hasil representasi bentuk objek. Perlu penelitian lebih lanjut untuk membahas tentang metode pemilihan ukuran shape matrix yang tepat.
Analisa Hasil (lanjutan) Penelitian ini ada keterkaitan dengan penelitianpenelitian sebelumnya. 1. Menurut Gang Li, dkk (2009), umumnya pemilihan bentuk structuring element hanya didasarkan pada kemiripan dengan bentuk objek yang diteliti. 2. Menurut Loncaric (1999), sebuah bentuk objek dapat direpresentasikan, salah satunya adalah shape matrix. 3. Shape matrix memiliki keunggulan yaitu sudah teruji invarian terhadap translasi, rotasi, dan scaling (Goshtasby, 2005). Representasi objek berbasis shape matrix ini dapat digunakan untuk estimasi bentuk structuring element.
BAB 5 KESIMPULAN DAN SARAN
5.1. Kesimpulan
Algoritma berbasis shape matrix dapat digunakan untuk menentukan bentuk structuring element dari suatu objek. Dapat menangani bentuk objek yang mengalami perubahan scaling dan rotasi, bentuk objek dengan hole, dan citra dengan objek terpisah. Mampu mendeteksi citra riil yang bertipe grayscale Pada deteksi tepi, tingkat akurasi rata-rata berbasis shape matrix lebih tinggi.
Kesimpulan (Lanjutan)
Faktor mempengaruhi tingkat akurasi: bentuk objek dan nilai threshold (untuk citra grayscale) Akurasi rata-rata untuk seluruh data citra sintetis adalah 99,6 %. Akurasi rata- rata hasil deteksi tepi untuk keseluruhan data citra riil sebesar 98,4%.
5.2. Saran
Penelitian ini lebih fokus kepada bentuk structuring element, sedangkan ukuran structuring element belum diperhatikan. Sebaiknya dilakukan penelitian lebih lanjut yang memperhatikan juga ukuran structuring element untuk menentukan structuring element yang optimal. Perlu dilakukan penelitian lebih lanjut tentang penggunaan bentuk structuring element berbasis shape matrix untuk menghilangkan noise (noise reduction).
Usulan Future Work
Bentuk yang sesuai menggunakan structuring element berbasis shape matrix
DAFTAR PUSTAKA
Cecilia Di Ruberto, Andrew Dempster, Shahid Khan, Bill Jarra. (2000), ” Segmentation of Blood Images Using Morphological Operators”, Proceedings of the International Conference on Pattern Recognition (ICPR'00), London, hal. 1051 - 4651 Costa, Luciano da Fontoura dan Cesar, Roberto Marconed, Jr, (2009), Shape Representation and Analysis: Theory and Practice , 2nd Edition, CRC Press, London. Cun Jin, Xue , Fen-Zhen, Su, dan Jun-qi, Zhou. (2006) , “An Adaptive Algorithm to Define Optimal Size of Structuring Element”, Journal of Image and Graphics, Vol. 11, No. 2. F.G. Huang, G. Yang , dkk., (2000), “The Application of Soft Morphology in Image Edge Detection, Journal of Image and Graphics of China, Nomor 5, hal. 284–288. Goshtasby, Ardeshir, (1985), “Description and Discrimination of Planar Shapes Using Shape Matrices”, IEEE Transaction On Pattern Analysis and Machine Intelligence, Vol. PAMI-7, No. 6, hal 738 – 743. Goshtasby, Ardeshir, (2005), Intersience 2-D and 2-D and 3-D Image Registration for Medical, Remote Sensing, and Industrial Applications, John Wiley & Sons, Inc., New York. Haralick. S, S. Sternberg, and X. Zhuang. (1987), ”Image analysis using mathematical morphology”, IEEE Transactions on PAMI-9, hal 532-550.
Daftar Pustaka (lanjutan)
Loncaric, Sven, (1999), A Survey of Shape Analysis Techniques, Tesis Ph.D., University of Zagreb, Croasia. Murni, Aniati. (2004). Diktat Kuliah : Pengolahan Citra Digital, Universitas Indonesia, Jakarta. Obara, Boguslaw, (2007), “ Identification of Transcrystalline Microcracks Observed in Microscope Images of a Dolomite Structure using Image Analysis Methods Based on Linear Structuring Element Processing”, Journal Computers & Geosciences , Nomor. 33 (2007), hal. 151–158. Serra, J, (1982), Image Analysis and Mathematical Morphology, Academic Press, Inc., London. Soille P., (1999). Morphological Image Analysis: : Principles and Applications, Springer Verlag, Germany. Syamsa, Ardisasmita, (2000), “Matematika Morfologi untuk Segmentasi dan Analisis Citra “, Procedings Komputer dan Sistem Intelijen, Universitas Gunadarma, Jakarta, hal. D152 – D. 163 Tian-Gang Li, Su-pinWang, NanZhao, (2009), “Gray-scale Edge Detection for Gastric Tumor Pathologic Cell Images by Morphological Analysis, Biology and Medicine Journal, Nomor. 39, hal. 947 – 952.
Terima Kasih
