tesis deteksi kepala janin pada gambar usg … · •antarmuka sub aplikasi preproses. antarmuka...
TRANSCRIPT
TESIS
DETEKSI KEPALA JANIN PADA GAMBAR USG
MENGGUNAKAN FUZZY C-MEANS (FCM) DENGAN MENGGUNAKAN FUZZY C-MEANS (FCM) DENGAN
INFORMASI SPASIAL & ITERATIVE RANDOMIZED
HOUGH TRANSFORM (IRHT)
Oleh : Dwi puspitasari - 5109201026
Dosen Pembimbing :
Prof. Ir. Handayani Tjandrasa, M.Sc, Ph.D
Latar Belakang
• Analisis kepala janin pada pencitraan USG sangat dibutuhkan oleh tenaga medis
• Diameter biparietal (BPD) dan lingkar kepala (HC) adalah dua pengukuran penting untuk :
– mengevaluasi pertumbuhan janin
– memperkirakan usia kehamilan
– memprediksi berat dan kematangan janin,
– mendiagnosa berbagai masalah obstetri.
• Perlu pengukuran BPD dan HC secara otomatis �eteksi bentuk elips yang diasumsikan sebagai kepala janin
Latar Belakang
• Penelitian deteksi kepala janin – Sebelumnya: Menggunakan metode IRHT dengan
praproses berupa klasterisasi piksel berdasarkan nilai keabuan menggunakan K-Means [1]. • Hasil : Metode tersebut mampu mendeteksi elips dengan baik.
Akan tetapi pada beberapa gambar dengan banyak noise, hasil Akan tetapi pada beberapa gambar dengan banyak noise, hasil segmentasi kurang baik sehingga menghasilkan kesalahan deteksi
– Penelitian ini : menggunakan metode IRHT [1] dengan praproses berupa klasterisasi menggunakan Fuzzy C-Means (FCM) dengan informasi spasial [3], serta penghalusan dengan metode thinning. • Hipotesa : Dengan klasterisasi menggunakan FCM dengan
informasi spasial, diharapkan dapat meningkatkan kualitas hasil segmentasi sehingga dapat meningkatkan akurasi deteksi kepala janin
Perumusan Masalah
• Bagaimana meningkatkan hasil segmentasi
sehingga mampu meningkatkan akurasi
deteksi kepala janin pada gambar USG.
• Bagaimana membangun sistem yang dapat • Bagaimana membangun sistem yang dapat
mendeteksi kepala janin serta menghasilkan
ukuran BPD dan HC secara otomatis
Batasan Masalah
• Data yang digunakan dalam uji coba penelitian
merupakan data gambar USG kepala janin
yang berumur antara 18-34 minggu.
• Implementasi menggunakan perangkat lunak • Implementasi menggunakan perangkat lunak
Matlab 7.1.
Tujuan & Manfaat
• Tujuan
Membangun sistem deteksi kepala janin pada gambar USG menggunakan Fuzzy C-Means (FCM) dengan informasi spasial dan IterativeRandomized Hough Transform (IRHT)Randomized Hough Transform (IRHT)
• Manfaat
Menghasilkan suatu sistem deteksi kepala janin pada gambar USG dengan pengukuran BPD dan HC secara otomatis sebagai alat bantu tenaga ahli dibidang kedokteran.
K-means VS FCM
• Persamaan : metode klastering partitioning dengan
penentuan awal jumlah klaster
• Perbedaan :
– K-means � data terklaster secara tegas– K-means � data terklaster secara tegas
– FCM � data terklaster pada semua klaster
dengan derajat keanggotaan berbeda
(a) Keanggotaan pada
metode K-means
(a) Keanggotaan pada
metode FCM
Algortima K-means
1. Inisialisasi K titik sebagai titik2 pusat (centroids) awal dari grup
2. Masukkan tiap objek dalam grup yang mempunyai titik pusat terdekat
3. Setelah selesai untuk semua objek, hitung kembali posisi K titik2 pusat yang
baru
• Pada penelitian ini klasifikasi menggunakan metode K-means
dibangun menggunakan fungsi ‘kmeans’ yang disediakan oleh
perangkat lunak Matlab
4. Ulangi langkah 2 dan 3 sampai titik2 pusat tidak berubah
Algoritma FCM
1. Inisialisasi matriks U=[uij] , U(0)
2. Pada langkah ke-k, hitung vektor pusat C(k)=[cj] dengan U(k)
3. Update U(k) , U(k+1)
4. Bila || U(k+1) - U(k)||< berhenti, kalau tidak kembali ke langkah 2.
Informasi Spasial
• Merupakan korelasi ketetanggaan yang digunakan untuk meningkatkan hasil segmentasi
• Klasterisasi piksel bukan hanya berdasarkan nilai • Klasterisasi piksel bukan hanya berdasarkan nilai keabuan, tetapi juga nilai keabuan dan jarak piksel ketetanggaan � local image feature
• Penentuan keanggotaan klaster bukan hanya berdasarkan nilai keanggotaan piksel tetapi juga nilai keanggotaan piksel ketetanggaan
Iterative Randomized Hough
Transform (IRHT)
Y Y Y
Hough Transform (HT)
Rosenfeld, 1962 [4]
Randomized Hough Transform (RHT)
Xu Oja, 1989 [5]
Iterative Randomized Hough
Transform (IRHT)
Wei Lu, 2008 [1]
Y
b
k
Yy=kx+b
(x,y)
x
Yy=kx+b
(x,y)
x
b
(k,b)
k
b
(k,b)
k
Yy=kx+b
(x,y)
x
b
(k,b)
k
Yy=kx+b
(x,y)
x
Elips
• Persamaan elips
• Fungsi elips [1]:
ac - b2 > 0
Diagram Sistem
Menghitung local image feature berdasarkan
jarak dan nilai keabuan ketetanggaan
Pembobotan piksel
Klasterisasi menggunakan K-meansKlasterisasi menggunakan FCM dengan
PenskalaanCitra USG kepala janin dengan
skala yang sama
Citra USG kepala
janin
Klasterisasi menggunakan K-meansKlasterisasi menggunakan FCM dengan
informasi spasial
Pembentukan citra obyek
Thinning
IRHT
Kaliberai piksel ke mili meter
Citra obyek
Citra hasil thinning
BPD dan HC
Parameter elips
Elips hasil deteksi
Segmentasi
Penghalusan
Deteksi
Penskalaan
• Dilakukan untuk :
– Menyamakan skala citra USG
– Mendapatkan perbandingan piksel dalam mili
metermeter
Skala :
10 mili meter : 16 piksel
Perhitungan Local Image Feature
• Local image feture (Fij) dihitung berdasarkan pada :
– jarak ketetanggaan ( ) dan
– keabuan ketetanggaan (FijG)
Gambar asli
ketetanggaan dengan
ukuran window (3x3)
j
i
λS = faktor skala,λG =faktor global
i
i
j
i
Gambar asli
Pembobotan Piksel
• Mengganti nilai piksel gambar asli dengan nilai yang
dipengaruhi ketetanggaan � wi
F1,
1
Fi,j
i=1 4 7 10
2 5 8 11
3 6 9 12
Gambar asli
j=1 4 7
2 5 8
3 6 9
Window 3x3
w1 w2 w12
Wi’
Klasterisasi FCM
1. Inisialisasi segmentasi dengan FCM basic
2. Mendapatkan inisialisasi keanggotaan piksel (μk) dan pusat
klaster (vk)
3. Menghitung keanggotaan (μ’k) dan pusat klaster
baru (vk)baru (vk)
Sudah
konvergen ?
4. Mendapatkan keanggotaan piksel dan pusat
klaster
Pembentukan citra obyek
• Proses untuk memilih piksel-piksel hasil
klasterisasi yang menjadi obyek
• Yaitu piksel yang menjadi anggota klaster dengan
pusat klaster tertinggi. Dikarenakan obyek berupa pusat klaster tertinggi. Dikarenakan obyek berupa
kepala janin pada citra USG memiliki nilai
keabuan tertinggi (warna cerah) [1]
• Selanjutnya dibentuk citra monokrom dengan
piksel pembentuk obyek bernilai 1 dan piksel lai
bernilai 0.
Thinning
• Digunakan untuk mencari bentuk dasar/ rangka/ skeleton dari gambar obyek hasil klasterisasi
• Pada penelitian ini digunakan fungsi thinning yang disediakan oleh software Matlab yaitu menggunakan fungsi bwmorph
Gambar Asli Gambar hasil klasterisasi Gambar hasil thinning
Tidak
Ya Tidak
1.Inisialisasi ROI sebesar ukuran gambar, maxEpoch dan maxIterasi
2.Mengambil semua piksel obyek dalam ROI dan menyimpannya di daftar
piksel. Membersihkan accumulator, dan bestellipse. Inkremen epoch
3.Memilih secara acak 4 piksel dalam daftar piksel. Inkremen I.
4.Menemukan parameter elips dengan persamaan (1),
(2), (3), (4), (5), (6)
Apakah merupakan
elips ?
IRHT
Ya Tidak
Tidak
Ya
Tidak
Ya
5.Tambahkan ke accumulator
Apakah iterasi =
maxIterasi ?
6.Mendeteksi bestellipse berdasarkan parameter di accumulator yang memiliki
skor terbanyak. Update ROI selanjutnya berdasarkan bestellpse
Apakah epoch =
maxEpoch ?
7.Verifikasi elips yang ditemukan
Antarmuka preproses
• Antarmuka sub aplikasi preproses
Antarmuka deteksi
• Antarmuka sub aplikasi deteksi elip
Uji Coba
• Lingkungan uji coba :
Perangkat Spesifikasi
Perangkat
Keras
Prosesor : Intel (R) Core (TM) 2 Duo CPU T5750 @2.00GHz
Memori : 2,00 GB
• Skenario uji coba :
1. mengetahui pengaruh parameter ukuran window pada metode FCM
dengan informasi spasial
2. membandingkan hasil output segmentasi citra USG kepala janin antara
metode K-means dengan metode FCM berdasarkan informasi spasial
3. membandingkan akurasi deteksi elips dari hasil segmentasi menggunakan
metode K-means dan IRHT dengan metode FCM dan IRHT
Perangkat
Lunak
Sistem Operasi : Windows Vista Home Basic 32-bit
Perangkat Pengembang : Matlab 7.1, Photoshop CS 2
Data uji coba
1. BPD51mm.jpg
2. BPD63mmjpg
3. BPD69mm.jpg
4. BPD72mm.jpg
5. BPD77mm.jpg
6. BPD82.jpg
7. BPD90,2mm.jpg
8. BPD90mm.jpg
Hasil Uji Coba Skenario 1
�o. Citra Inputan Ukuran
Window
Jumlah
Partisi
Waktu Eksekusi
(detik)
1. BPD51mm.jpg 3 x 3 11 193.422
5 x 5 7 478.111
2. BPD63mm.jpg 3 x 3 12 100.011
5 x 5 8 271.394
3. BPD69mm.jpg 3 x 3 9 43.2743. BPD69mm.jpg 3 x 3 9 43.274
5 x 5 4 200.295
4. BPD 72.mm.jpg 3 x 3 15 111.814
5 x 5 8 741.472
5. BPD77mm.jpg 3 x 3 11 104.808
5 x 5 4 419.099
6. BPD82mm.jpg 3 x 3 6 93.084
5 x 5 5 410.260
7. BPD90,2mm.jpg 3 x 3 10 202.141
5 x 5 6 786.619
8. BPD90mm.jpg 3 x 3 11 122.761
5 x 5 7 590.067
Hasil Uji Coba Skenario 2
�o. Citra Inputan Metode Jumlah
Partisi
Waktu
Eksekusi
(detik)
1. BPD51mm.jpg K-means 50 2.474
FCM dengan informasi spasial 7 478.111
2. BPD63mm.jpg K-means 57 0.553
FCM dengan informasi spasial 8 271.394
3. BPD69mm.jpg K-means 65 0.2283. BPD69mm.jpg K-means 65 0.228
FCM dengan informasi spasial 4 200.295
4. BPD 72.mm.jpg K-means 63 3.197
FCM dengan informasi spasial 8 741.472
5. BPD77mm.jpg K-means 58 1.179
FCM dengan informasi spasial 4 419.099
6. BPD82mm.jpg K-means 84 1.336
FCM dengan informasi spasial 5 410.260
7. BPD90,2mm.jpg K-means 51 1.376
FCM dengan informasi spasial 6 786.619
8. BPD90mm.jpg K-means 58 0.833
FCM dengan informasi spasial 7 590.067
Hasil uji coba skenario 3
Citra UjiBPD
(mm)
BPD Sistem Pada Uji Coba ke- (mm) Rata-Rata BPD
Sistem (mm)Akurasi (%)
1 2 3 4 5 6 7 8 9 10
Kmeans_BPD51mm.jpg 51 118,75 77,50 55,00 125,00 107,50 100,00 57,50 52,50 97,50 37,50 82,88 20
Kmeans_BPD63mm.jpg 63 73,75 7,50 10,00 11,25 17,50 107,50 90,00 86,25 22,50 76,25 50,25 0
Kmeans_BPD69mm.jpg 69 68,75 67,50 70,00 71,25 71,25 13,75 63,75 32,50 6,25 13,75 47,88 60
Kmeans_BPD72mm.jpg 72 76,25 68,75 72,50 76,25 75,00 80,00 73,75 83,75 77,50 87,50 77,13 60
Kmeans_BPD77mm.jpg 77 57,50 82,00 101,25 53,75 86,25 75,00 41,25 106,25 98,75 66,25 76,83 20
Kmeans_BPD82mm.jpg 82 25,00 8,75 11,25 105,00 38,75 13,75 90,00 36,25 80,00 16,25 42,50 10
Kmeans_BPD90,2mm.jpg 90,2 73,75 81,25 58,75 77,50 88,75 47,50 107,50 97,50 100,00 97,50 83,00 10
Kmeans_BPD90mm.jpg 90 50,00 27,50 81,25 40,00 38,75 108,75 40,00 56,25 17,50 22,50 48,25 0
FCM_BPD51mm.jpg 51 51,25 51,25 51,25 52,50 51,25 51,25 48,75 53,75 47,50 46,25 50,50 100
FCM_BPD63mm.jpg 63 66,25 62,50 63,75 62,50 63,75 66,25 68,75 63,75 63,75 62,50 64,38 90
FCM_BPD69mm.jpg 69 68,75 71,25 68,75 77,50 70,00 72,50 71,25 70,00 70,00 68,75 70,88 90
FCM_BPD72mm.jpg 72 81,25 77,50 76,25 77,50 76,25 77,50 83,75 73,75 75,00 78,75 77,75 70
FCM_BPD77mm.jpg 77 86,25 85,00 80,00 93,75 90,00 82,50 90,00 75,00 92,50 73,00 91,13 30
FCM_BPD82mm.jpg 82 20,00 30,00 18,75 27,50 80,00 78,00 25,00 37,50 30,00 81,25 42,80 30
FCM_BPD90,2mm.jpg 90,2 93,75 100,00 98,75 105,00 102,50 92,50 90,00 101,25 106,25 113.75 89,00 30
FCM_BPD90mm.jpg 90 18,75 94,00 100,00 101,25 17,50 113,75 111,25 86,00 88,00 110,00 84,05 30
Hasil Uji Coba Skenario 3
�o. Citra Inputan Kebenaran Deteksi
(%)
Rata-Rata Waktu
Eksekusi (detik)
1. Kmeans_BPD51mm.jpg 20 8.501
2. Kmeans_BPD63mm.jpg 0 10.557
3. Kmeans_BPD69mm.jpg 60 4.893
4. Kmeans_BPD 72.mm.jpg 60 9.827
5. Kmeans_BPD77mm.jpg 20 4.2435. Kmeans_BPD77mm.jpg 20 4.243
6. Kmeans_BPD82mm.jpg 10 4.596
7. Kmeans_BPD90,2mm.jpg 10 4.519
8. Kmeans_BPD90mm.jpg 0 4.483
9. FCM_BPD51mm.jpg 100 9.966
10. FCM_BPD63mm.jpg 90 4.837
11. FCM_BPD69mm.jpg 90 11.787
12. FCM_BPD 72.mm.jpg 70 9.193
13. FCM_BPD77mm.jpg 30 10.974
14. FCM_BPD82mm.jpg 30 6.260
15. FCM_BPD90,2mm.jpg 30 12.094
16. FCM_BPD90mm.jpg 30 6.546
Kesimpulan
• Hasil segmentasi pada gambar USG kepala janin menggunakan metode FCM dengan informasi spasial lebih baik dibandingkan dengan menggunakan metode K-means.
• Dengan menggunakan metode FCM berdasarkan informasi spasial dan IRHT, mampu meningkatkan keberhasilan deteksi kepala janin dibandingkan dengan menggunakan deteksi kepala janin dibandingkan dengan menggunakan metode K-means dan IRHT. Dengan kata lain meningkatnya hasil segmentasi dapat meningkatkan akurasi deteksi.
• Dengan deteksi elips yang diasumsikan sebagai kepala janin menggunakan metode FCM berdasarkan informasi spasial dan IRHT, dapat menghasilkan BPD dan HC kepala janin secara otomatis
Saran
• Pada penelitian ini waktu eksekusi proses
segmentasi relatif lama, dengan demikian
permasalahan untuk mempercepat waktu
eksekusi dapat digunakan sebahai bahan eksekusi dapat digunakan sebahai bahan
penelitian lebih lanjut
Daftar Pustaka
1. Lu, W., Jinglu Tan, (2008), “Detection of incomplete ellipse in images with strong noise by
Iterative Randomized Hough transform (IRHT)”, Journal of Pattern Recognition 41 pp
1268 – 1279 Elsivier Science Ltd
2. Xu, L., Oja, E., (1990), “A new curve detection method : Randomized Hough Transform
(RHT)”, Journal of Pattern Recognition Letter 11 331-338 North-Holland Elsivier Science
Ltd
3. Wang, X-Y., J.Bu., (2010), “A fast and robust image segmentation using FCM with 3. Wang, X-Y., J.Bu., (2010), “A fast and robust image segmentation using FCM with
spatial information”, Journal of Digital Signal Processing 1173–1182 Elsivier Science Ltd
4. Xu, L., Oja, E., (2009), “Randomized Hough Transform”, Encyclopedia of Artificial
Intelligence, IGI Global publishing company
5. J. C. Bezdek, (1981), "Pattern Recognition with Fuzzy Objective Function Algoritms",
Plenum Press, New York
6. J. B. MacQueen, (1967), "Some Methods for classification and Analysis of Multivariate
Observations”, Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and
Probability, Berkeley, University of California Press, 1:281-297
7. Gonzalez. R.C, (2007), “Digital Image Processing Chapter 10 Image Representation and
Description”, Prentice Hall
8. Leavers, V.F., (1992), “The Dynamic Generalized Hough Transform: Its Relationship to
the Probabilistic Hough Transforms and an Application to the Concurrent Detection
of Circles and Ellipses”, CVGIP:Image Understanding
Citra hasil uji coba skenario 1
Gambar
asli
FCM dg
window 3x3
FCM dg
window 5x5
Citra hasil uji coba skenario 2
Gambar
asli
K-means
FCM dg
window 5x5