TESIS DETEKSI KEPALA JANIN PADA GAMBAR USG 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 segmentasi kurang baik sehingga menghasilkan kesalahan deteksi
– Penelitian ini : menggunakan metode IRHT [1] dengan praproses berupa klasterisasi menggunakan Fuzzy CMeans (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 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 Matlab 7.1.
Tujuan & Manfaat • Tujuan Membangun sistem deteksi kepala janin pada gambar USG menggunakan Fuzzy C-Means (FCM) dengan informasi spasial dan Iterative 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 – 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
4.
Ulangi langkah 2 dan 3 sampai titik2 pusat tidak berubah
• Pada penelitian ini klasifikasi menggunakan metode K-means dibangun menggunakan fungsi ‘kmeans’ yang disediakan oleh perangkat lunak Matlab
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 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) Hough Transform (HT)
Randomized Hough Transform (RHT)
Rosenfeld, 1962 [4]
Xu Oja, 1989 [5]
Wei Lu, 2008 [1]
Y
Y
Iterative Randomized Hough Transform (IRHT)
Y
Y
y=kx+b
y=kx+b
y=kx+b
(x,y)
(x,y)
(x,y)
b
x b
(k,b)
k
(x,y)
x
x b
y=kx+b
b
(k,b)
k
x
(k,b)
k
k
Elips • Persamaan elips • Fungsi elips [1]:
ac - b2 > 0
Diagram Sistem Citra USG kepala janin
Citra USG kepala janin dengan skala yang sama
Penskalaan
Menghitung local image feature berdasarkan jarak dan nilai keabuan ketetanggaan
Pembobotan piksel
Klasterisasi menggunakan FCM dengan informasi spasial
Klasterisasi menggunakan K-means
Pembentukan citra obyek
Segmentasi
Citra obyek Thinning Citra hasil thinning
Penghalusan Elips hasil deteksi
Deteksi
IRHT
Kaliberai piksel ke mili meter
Parameter elips BPD dan HC
Penskalaan • Dilakukan untuk : – Menyamakan skala citra USG – Mendapatkan perbandingan piksel dalam mili meter
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
i j i
i
j i
ketetanggaan dengan ukuran window (3x3)
λS = faktor skala,λG =faktor global
Pembobotan Piksel • Mengganti nilai piksel gambar asli dengan nilai yang dipengaruhi ketetanggaan wi Fi,j F1, 1
Window 3x3
Gambar asli i=1
4
7
10
j=1
4
7
2
5
8
11
2
5
8
3
6
9
12
3
6
9
Wi’ w1
w2
w12
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)
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 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
Gambar Asli
Gambar hasil klasterisasi Gambar hasil thinning
• Pada penelitian ini digunakan fungsi thinning yang disediakan oleh software Matlab yaitu menggunakan fungsi bwmorph
1.Inisialisasi ROI sebesar ukuran gambar, maxEpoch dan maxIterasi
IRHT
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)
Tidak
Apakah merupakan elips ?
Ya 5.Tambahkan ke accumulator
Tidak
Tidak
Apakah iterasi = maxIterasi ?
Ya 6.Mendeteksi bestellipse berdasarkan parameter di accumulator yang memiliki skor terbanyak. Update ROI selanjutnya berdasarkan bestellpse
Tidak
Apakah epoch = maxEpoch ?
Ya
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
Prosesor : Intel (R) Core (TM) 2 Duo CPU T5750 @2.00GHz
Keras
Memori : 2,00 GB
Perangkat
Sistem Operasi : Windows Vista Home Basic
Lunak
Perangkat Pengembang : Matlab 7.1, Photoshop CS 2
32-bit
• Skenario uji coba : 1. 2. 3.
mengetahui pengaruh parameter ukuran window pada metode FCM dengan informasi spasial membandingkan hasil output segmentasi citra USG kepala janin antara metode K-means dengan metode FCM berdasarkan informasi spasial membandingkan akurasi deteksi elips dari hasil segmentasi menggunakan metode K-means dan IRHT dengan metode FCM dan IRHT
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.
1.
2.
3.
4.
5.
6.
7.
8.
Citra Inputan
BPD51mm.jpg
BPD63mm.jpg
BPD69mm.jpg
BPD 72.mm.jpg
BPD77mm.jpg
BPD82mm.jpg
BPD90,2mm.jpg
BPD90mm.jpg
Ukuran
Jumlah
Waktu Eksekusi
Window
Partisi
(detik)
3x3
11
193.422
5x5
7
478.111
3x3
12
100.011
5x5
8
271.394
3x3
9
43.274
5x5
4
200.295
3x3
15
111.814
5x5
8
741.472
3x3
11
104.808
5x5
4
419.099
3x3
6
93.084
5x5
5
410.260
3x3
10
202.141
5x5
6
786.619
3x3
11
122.761
5x5
7
590.067
Hasil Uji Coba Skenario 2 o.
Citra Inputan
Metode
Jumlah
Waktu
Partisi
Eksekusi (detik)
1.
BPD51mm.jpg
K-means FCM dengan informasi spasial
2.
BPD63mm.jpg
K-means FCM dengan informasi spasial
3.
BPD69mm.jpg
K-means
FCM dengan informasi spasial 4.
BPD 72.mm.jpg
K-means FCM dengan informasi spasial
5.
BPD77mm.jpg
K-means FCM dengan informasi spasial
6.
BPD82mm.jpg
K-means FCM dengan informasi spasial
7.
BPD90,2mm.jpg
K-means FCM dengan informasi spasial
8.
BPD90mm.jpg
K-means FCM dengan informasi spasial
50
2.474
7
478.111
57
0.553
8
271.394
65
0.228
4
200.295
63
3.197
8
741.472
58
1.179
4
419.099
84
1.336
5
410.260
51
1.376
6
786.619
58
0.833
7
590.067
Hasil uji coba skenario 3 Citra Uji
BPD Sistem Pada Uji Coba ke- (mm)
BPD (mm)
1
4
5
6
7
Rata-Rata BPD 8
9
10
Akurasi (%)
Sistem (mm)
2
3
55,00 125,00 107,50 100,00
57,50
52,50
97,50
37,50
82,88
20
Kmeans_BPD51mm.jpg
51
118,75
77,50
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
80,00
16,25
42,50
10
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
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
90
18,75
94,00
110,00
84,05
30
Kmeans_BPD90,2mm.jpg
FCM_BPD90,2mm.jpg FCM_BPD90mm.jpg
100,00 101,25
17,50 113,75 111,25
36,25
86,00
88,00
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.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 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 penelitian lebih lanjut
Daftar Pustaka 1.
2.
3.
4. 5. 6.
7. 8.
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 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 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 Xu, L., Oja, E., (2009), “Randomized Hough Transform”, Encyclopedia of Artificial Intelligence, IGI Global publishing company J. C. Bezdek, (1981), "Pattern Recognition with Fuzzy Objective Function Algoritms", Plenum Press, New York 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 Gonzalez. R.C, (2007), “Digital Image Processing Chapter 10 Image Representation and Description”, Prentice Hall 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
