Download - ITS Master 10281 Presentation
METODE SHAPE DESCRIPTORBERBASIS SHAPE MATRIXUNTUK ESTIMASI BENTUK
STRUCTURING ELEMENT
Sri Huning ANRP. 5108201002
DOSEN PEMBIMBINGDr. 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 obj ek 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 beberapacara (Cesar dan Costa, 2009) � shape descriptor
� Tujuan penelitian :mengusulkan suatu metode baruuntuk estimasi bentuk structuring element berdasar pada representasi bentuk objek yang diteliti� berbasis shape matrix.
� menguji kinerja � bentuk structuring element yang didapatkan diujicobakan untuk deteksi tepimenggunakan operasi morfologi gradien .
� Hasil Uji Coba (akurasi rata-rata):- 30 Citra sintetis : 99,6 %- 3 citra riil : 98,4 %
Abstrak (lanjutan)
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 sebaga i 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 elementdengan 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 ManfaatTujuan :
mengestimasi bentuk structuring elementdengan 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 informasimengenai bentuk dari suatu citra denganmengatur bentuk dan ukuran suatu elemenpenstruktur (structuring element).
� Morfologi : analisa bentuk, bukan mengubahbentuk
2.1.1. Structuring Element
Gambar 2.2. Contoh Structuring Element (a) titik “O” adalahtitik poros, (b) representasi biner dari structuring element
B
� Strel kunci penting dalam morfologi�komponen : yaitu bentuk dan ukuran.
Bentuk-bentuk Umum Strel
Gambar 2.5. Bentuk-bentuk Umum Structuring Element
a. Disk ukuran 3
b. Square 3 x 3
c. Diamond ukuran 3 d. Linear ukuran 3, rotasi 45o
e. Rectangle 3 x 5
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 berbedatetapi 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
Misalkan S adalah sebuah objek
0 SA
1. Mencari titik tengah objek, misal titik O
Algoritma Shape Matrix
2. Mencari radius terjauh objek, misal titik A
Akan diketahui panjang OA = L
L
3. Buat lingkaran mengelilingiobjek dengan r = L
4. Menentukan ukuran ordoshape matrix m x n, misalm = 6 dan n = 5
5. Bagi garis OA menjadi (n-1) bagian.Kemudian buat lingkaran denganradius masing-masing adalahL/(n-1), 2L/(n-1), …, (n-1)L/(n-1)
Akan didapatkan titik potongpada i1, i2, …, in-1. Kemudian dari setiap titik potong, dengan arah berlawanan jarum jam, Bagi setiap lingkaran menjadi m busurDengan dθ = 360/m derajat
dθ = 360/mθ
2.3. Shape Matrix
Algoritma menentukan nilai elemen shape matrix
Contoh shape matrix
A
Gambar 2.10. (a) contoh shape , (b) Shape Matriks(Goshtasby, 2005)
m = 6, n = 5, L = 10Koordinat (iL/(n-1),,j(360/m)
n = i
m = j
BAB 3.
Metode Penelitian
3.1. Desain Sistem
mulaiMenentukan Citra Uji dan citra ground
truth
Menentukan representasibentuk (shape matrix )
untuk dapat menentukan bentuk structuring
element
Melakukan operasimorfologi gradientmenggunakan strel
yang didapat
Menghitung KinerjaAlgoritmaselesai
Gambar 3.1. Desain Sistem
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 citrabinerisasi citra uji (optional)
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)
mencari koordinat piksel penyusun objek
Bagi garis OA menjadi bagian dengan jarak yang sama
Membuat lingkaran - dengan titik pusat O – dengan radius lingkaran masing-masing adalah )1/()1(...,),1/(2),1/( −−−− nLnnLnL
menentukan nilai-nilai elemen shape matrix
Membagi lingkaran menjadi busur yang sama dimana sudut masing-masing derajat.md /360=θ
2.1. Binerisasi
� mengubah tipe citra menjadi bertipe biner (hitam putih).
1. baca citra uji2. tentukan nilai threshold3. 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 koordinat-
koordinat piksel yang termasuk objek.
2.3. Mencari Titik Tengah Objek
∑∑==
==N
ii
N
ii y
Ncx
Nc
12
11
1,
1
Gambar 3.7. Hasil PencarianTitik Tengah Objek
Persamaan mencari koordinat pusat objek (c1,c2),
(3.1)
dimana adalah koordinat dari piksel dalam objek ),...,2,1)(,( Niyx ii =dan N adalah jumlah piksel dalam objek.
2.4. Mencari Radius Terjauh dari Objek
� Eucledian distance� setiap piksel pada objek dihitung jaraknya
terhadap titik pusat O(c1,c2)
� Di mana (x1,y1) adalah koordinat setiap piksel pada objek, sedangkan (c1,c2) adalah koordinat titik pusat objek.
221
211 )()( cycxD −+−=
O(c1,c2)
A (rMax,cMax)
L
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. LingkaranMengelilingi Bentuk 1
2.8. Menentukan nilai-nilai elemen shape matrix
1:),( =jiM
For i = 0 to (n – 1)For j = 0 to (m – 1)
If titik dengan koordinat polar (berada di dalam shape, then
otherwise
))/360(),1/( mjniL −
0:),( =jiM
10001
11111
11111
10111
10111
Gambar 3.14. Contoh Shape Matrixukuran 5 x 5
3. Deteksi Tepi Menggunakan Operasi
Morfologi Gradienstart
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
FNFPTNTP
FNTPAkurasi
++++=
Tabel 3.1. Perhitungan Akurasi Sistem
True Negatif (TN)False Negatif (FN)Bukan Edge
False Positif (FP)True Positif (TP)EdgeHasil Sistem
Bukan EdgeEdge
Ground Truth
BAB 4
UJI COBA DAN
ANALISIS HASIL
Data Uji Coba
1. Citra Ground Truth2. 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
Asli140 x 140
70%98 x 98
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
Breastgigi
Sel darah
Structuring Element Pembanding
� Diamond � Disk � Square
Hasil Pengujian (Citra Normal)
99,8299,82100,00100,00Kotaktumpul15
98,2898,2898,2698,29Bunga14
99,6299,6299,9299,92Flag13
99,9899,98100,00100,00Kotak12
98,5198,5199,9899,99Bintang11
99,4199,4199,9999,99Bentuk 1010
98,5798,5799,9799,97Bentuk 99
98,8898,8899,9799,97Bentuk 88
99,1599,1599,9899,98Bentuk 77
99,3499,3499,7699,76Bentuk 66
99,3199,3199,9899,97Bentuk 55
98,5198,5199,6199,61Bentuk 44
98,2098,2098,2898,28Bentuk 33
98,0098,0097,9797,98Bentuk 22
98,3398,3399,9999,99Bentuk 11
DiskDiamondSquareSM
Akurasi (%)Nama ObjekN0
99,2799,2799,9999,99Daun30
99,3099,30100,00100,00Trapesium 229
99,2299,22100,00100,00Segilima28
99,3999,3999,6999,69Tanjakan27
99,4299,42100,00100,00Trapesium26
95,4095,4095,3995,40Kepala25
98,7398,7399,9199,91Segitiga 224
99,0599,05100,00100,00Segitiga 123
99,2899,2899,9999,99Segienam22
99,9499,94100,00100,00PMI21
99,9899,98100,00100,00Persegi20
99,3799,3799,9999,99Oval19
98,8398,8399,9799,97Lingkaran 218
99,0099,0099,9999,99Lingkaran 117
97,7697,7699,2799,27Layang16
DiskDiamondSquareSM
Akurasi (%)Nama ObjekNo
Tabel 4.3. Perbandingan Rata-rata Akurasi Uji Coba Normal
98,9disk4
98,9diamond3
99,5square2
99,6shape matrix1
Rata-rata Akurasi(%)
StructuringElementNo
Hasil Disk99,98 %
Hasil Diamond99,98 %
Hasil Square100 %
Hasil Shape Matrix100 %
Citra Ground TruthCitra Asli
Ukuran Structuring Element : 3 x 3
Hasil Disk(98,28%)
Hasil Diamond(98,28%)
Hasil Square(98,26%)
Hasil Shape Matrix(98,29%)
Citra Ground TruthCitra Asli
Ukuran Structuring Element : 3 x 3
Tabel 4.6. Hasil Pengujian Pada Citra Uji dengan Perubahan Scaling dan Rotasi
98,9498,941001003 x 3persegi_rotasi_-454
98,9498,941001003 x 3persegi_rotasi_+453
99,9599,951001003 x 3persegi_kecil_702
99,9999,991001003 x 3persegi_besar_1501
DiskDiamondSquareSMStrel
Akurasi (%)UkuranNama CitraNo
Tabel 4.7. Hasil Pengujian Pada Citra Uji dengan Hole
99,5899,5899,9999,993 x 3Hole 33
99,9599,951001003 x 3Hole 22
98,3698,361001003 x 3Hole 11
DiskDiamondSquareSMStrel
Akurasi (%)UkuranNama CitraNo
Tabel 4.9. Perhitungan Akurasi Citra Riil
97,297,298,198,4Rata-rata
98,0698,0699,5199,52Sel Darah3
97,8096,8998,5398,53Gigi2
96,8196,8196,4197,02Breast1
DiskDiamond
SquareSM
Akurasi (%)Nama ObjekNo
Analisa Hasil Uji Coba
� metode shape descriptor berbasis shape matrixdapat diandalkan untuk estimasi bentuk structuringelement. � Kelebihan : bentuk structuring element menyesuaikan
dengan objek yang diteliti, sehingga bentuk structuringelement yang didapatkan benar-benar merupakanrepresentasi bentuk objek yang diteliti.
� Kelemahan : Akan tetapi pemilihan ukuran shapematrix m x n sangat mempengaruhi hasil representasibentuk objek. Perlu penelitian lebih lanjut untukmembahas tentang metode pemilihan ukuran shapematrix yang tepat.
Analisa Hasil (lanjutan)
Penelitian ini ada keterkaitan dengan penelitian-penelitian 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 dapatdigunakan untuk menentukan bentuk structuringelement dari suatu objek.
� Dapat menangani bentuk objek yang mengalamiperubahan scaling dan rotasi, bentuk objekdengan hole, dan citra dengan objek terpisah.
� Mampu mendeteksi citra riil yang bertipegrayscale
� Pada deteksi tepi, tingkat akurasi rata-rataberbasis shape matrix lebih tinggi.
Kesimpulan (Lanjutan)
� Faktor mempengaruhi tingkat akurasi: bentuk objek dan nilai threshold (untukcitra grayscale)
� Akurasi rata-rata untuk seluruh data citrasintetis adalah 99,6 %.
� Akurasi rata- rata hasil deteksi tepi untukkeseluruhan data citra riil sebesar 98,4%.
5.2. Saran
� Penelitian ini lebih fokus kepada bentukstructuring element, sedangkan ukuranstructuring element belum diperhatikan. Sebaiknya dilakukan penelitian lebih lanjutyang memperhatikan juga ukuran structuringelement untuk menentukan structuringelement yang optimal.
� Perlu dilakukan penelitian lebih lanjut tentangpenggunaan bentuk structuring elementberbasis shape matrix untuk menghilangkannoise (noise reduction).
Usulan Future Work
� Bentuk yang sesuai menggunakanstructuring 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, UniversitasIndonesia, Jakarta.
� Obara, Boguslaw, (2007), “ Identification of Transcrystalline MicrocracksObserved 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