segmentasi citra
DESCRIPTION
Segmentasi Citra. Prof.Dr. Aniati Murni (R 1202) Dina Chahyati, SKom, (R 1226) Fakultas Ilmu Komputer Universitas Indonesia. Thinning & Skeletonizing - materi akhir. Thinning: pada citra yang sudah dilakukan proses thinning tidak bisa direkonstruksi kembali - PowerPoint PPT PresentationTRANSCRIPT
Segmentasi Citra
Prof.Dr. Aniati Murni (R 1202)Dina Chahyati, SKom, (R 1226)
Fakultas Ilmu KomputerUniversitas Indonesia
2
Thinning & Skeletonizing - materi akhirThinning & Skeletonizing - materi akhir
Thinning: pada citra yang sudah dilakukan proses thinning tidak bisa direkonstruksi kembali
Skeletonizing: dari citra yang telah diproses dengan teknik skeletonizing dapat dibangun kembali citra aslinya, yaitu citra sebelum diproses dengan teknik skeletonizing
Segmentasi Citra
4
Teknik Segmentasi Citra(Sumber: Anil K. Jain, Michigan State University)
Teknik Segmentasi Citra(Sumber: Anil K. Jain, Michigan State University)
Segmentasi citra: membagi suatu citra menjadi wilayah-wilayah yang homogen
Image Segmentation
General Purpose Knowledge Guided(bottom-up approach) (top-down
approach)
Histogram Clustering Rules of Features
5
Teknik Segmentasi Citra Segmentasi citra: membagi suatu citra menjadi
wilayah-wilayah yang homogen
Teknik Segmentasi Citra
Dividing Image Space Clustering Feature Space
Region Region Split Tiap pixel diberi indexGrowing Splitting and warna yang
menunjukkan\ Mergekeanggotaannya dalam
suatu cluster
6
Image Segmentation Based on Histogram (1)Image Segmentation Based on Histogram (1)
Two-Class Object Histogram
7
Image Segmentation Based on Histogram (2)Image Segmentation Based on Histogram (2)
Multi-Class Object Histogram
8
Segmentasi Citra dengan Clustering(Unsupervised Classification)
Segmentasi Citra dengan Clustering(Unsupervised Classification)
K-Mean Clustering
9
Rule-Based Image Segmentation (1)(Sumber: S.H. Purwadhi, LAPAN RI)
Rule-Based Image Segmentation (1)(Sumber: S.H. Purwadhi, LAPAN RI)
Features: Bentuk Pola Ukuran Sites(Tajuk berbentuk bintang) (Tidak teratur) (Tinggi > 10m) (Air
payau)
KELAPAHanya perlu persyaratan bentuk
KELAPA SAWIT
NIPAH NIPAH Perlu syarat bentuk dan pola
ENAU ENAU ENAU
SAGU SAGU SAGU SAGU
10
Knowledge-Based Image Segmentation (2)(Sumber: J. Ton, Michigan State University)
Knowledge-Based Image Segmentation (2)(Sumber: J. Ton, Michigan State University)
Features: indeks vegetasi dan intensitas keabuan
Land Cover
Non-vegetation Vegetation
Water Built-up Forest Non-Forest
Open AreaClear-Up Type-1 Type-2
Agriculture Bushes
11
Bottom-Up Approaches
12
Two-Class and Multi-Class Problem (1)Two-Class and Multi-Class Problem (1)
Two-Class Problem: Citra terdiri dari Obyek dan Latar
Belakang Segmentasi bisa dengan teknik:
Histogram dan thresholding value, atau Decision theory (akan dipelajari pada topik klasifikasi citra) Probability Density Function dan Maximum-Likelihood Decision Rules
13
Two-Class and Multi-Class Problem (2)Two-Class and Multi-Class Problem (2)
Multi-Class Problem: Citra terdiri dari wilayah-wilayah obyek
yang jumlahnya lebih dari 2 Segmentasi bisa dengan teknik:
Clustering (unsupervised classification – akan dipelajari pada topik klasifikasi citra)
Region Growing (wilayah tumbuh – bottom-up approach) Region Splitting (quadtree - top-down approach) Split and Merge (bottom-up and top-down approach) Decision Theory
14
Region Growing (lihat skripsi atau program Dipdha (2002)Region Growing (lihat skripsi atau program Dipdha (2002)
Ditentukan sejumlah seed pixels (random atau regular)
Cek homogenitas melalui 4-tetangga atau 8-tetangga
Memerlukan criteria of uniformityBila:
Criteria of uniformity: seed
1( )
P R
m f PN
max | ( ) |P R
f P m Thres
15
Top-Down Approaches
16
Region SplittingRegion Splitting
Menggunakan quadtree approach Memerlukan criteria of uniformity – bisa
menggunakan varian, bila varian tinggi (tidak uniform) suatu wilayah di-splitted
17
Split and MergeSplit and Merge
Prosedur sama dengan region splitting Pada akhir proses ditambah dengan proses
merging (menjadikan beberapa region yang dianggap sama menjadi satu). Bisa dilakukan secara semi-otomatis atau secara otomatis. Pendekatan secara otomatis bisa menggunakan merging criteria berupa suatu nilai ambang dari perbedaan mean (intensitas rata-rata) dari wilayah-wilayah yang akan digabungkan.
18
Teknik Segmentasi CitraTeknik Segmentasi Citra
Pendekatan Edge-Based Pendekatan Region-Based Pendekatan Hybrid
19
Pendekatan Edge-BasedPendekatan Edge-Based
Kekurangannya: belum tentu menghasilkan edge yang kontinue, mengakibatkan terjadinya kebocoran wilayah (wilayah-wilayah yang tidak tertutup)
Prosedur: Melakukan proses deteksi sisi dengan operator gradient.
Masukannya citra gray level dan keluarannya citra edge (biner)
Citra Masukan Deteksi Sisi Citra Edge
Selanjutnya dilakukan proses region growing dengan masukan citra asli (gray-level) dan citra edge. Proses pembentukan suatu wilayah berhenti bila menjumpai piksel edge. Keluarannya merupakan hasil segmentasi.
20
Pendekatan Region-BasedPendekatan Region-Based
Kekurangannya: belum tentu menghasilkan wilayah-wilayah yang bersambungan
Prosedur: Memerlukan criteria of uniformity Memerlukan penyebaran seeds atau dapat juga dengan
pendekatan scan line Dilakukan proses region growing
unidentified region
21
Pendekatan Hybrid Edge- & Region-Based (1)Pendekatan Hybrid Edge- & Region-Based (1)
Bertujuan untuk mendapatkan hasil segmentasi dengan wilayah-wilayah yang tertutup dan bersambungan
Prosedur: Lakukan proses deteksi sisi untuk menhasilkan citra
sisi (piksel edge dan piksel non-edge) Lakukan pemisahan wilayah dengan metode
connected region. Connected regions adalah set piksel 4-tetangga yang bukan piksel edge.
Selanjutnya dilakukan proses merging regions dengan rumusan-rumusan berikut (next slide).
22
Pendekatan Hybrid Edge- & Region-Based (2)Pendekatan Hybrid Edge- & Region-Based (2)
pi adalah adalah perimeter dan ni adalah luas wilayah Ri. Bij adalah panjang garis batas antar wilayah Ri dan Rj. Eij adalah jumlah piksel edge pada garis batas antar wilayah Ri dan Rj. (Eij biasanya < dari Bij karena edge yang tidak kontinue).
Untuk setiap pasang region Ri dan Rj dihitung tiga besaran / kriteria: boundary strength (bila tinggi – makin kuat garis batas, Ri dan Rj disatukan), similarity measure (bila besar – salah satu wilayah terlalu kecil, dapat disatukan) dan connectivity measure (bila besar – makin panjang garis batasnya, tidak disatukan).
23
Pendekatan Hybrid Edge- & Region-Based (3)Pendekatan Hybrid Edge- & Region-Based (3)
Boundary strength
Similarity measure scaling factor
Connectivity measure
1 ijij
ij
E
B
22 ( )
450i j
ij
n n
3 min( , )
4i j
ijij
p p
B
24
Pendekatan Hybrid Edge- & Region-Based (4)Pendekatan Hybrid Edge- & Region-Based (4)
Selanjutnya dapat dirumuskan bahwa region Ri dan Rj dapat dijadikan satu bila memenuhi tiga kondisi berikut: ni > nj (satu wilayah jauh lebih kecil – similarity measure) (40% piksel edge berada pada garis batas
yang sebenarnya – boundary strength) Rk telah memenuhi kedua kondisi diatas, Kondisi ketiga:
mencari pasangan wilayah Rk yang paling memenuhi kedua kondisi diatas untuk disatukan dengan Ri.
1ij st
2 3 2 3minij ij ik ij ck
t
25
Edge Image and Segmented ImageEdge Image and Segmented Image
Mandrill Edge Image Segmented Image
26
Watershed (a kind of region growing)
Region Growing problems: Not trivial to find good starting points, difficult to
automate Need good criteria for similarity Disconnected regions
Think of the grey-level image as a landscape. Let water rise from the bottom of each valley (the water from each valley is given its own label). As soon as the water from two valleys meet, build a dam, or watershed. These watersheds will then define the borders between different regions.
27
Watershed (a kind of region growing)
Region edges correspond to watersheds while low-gradient region interiors correspond to catchment basins. Edge or contour information can be used in watershed segmentation algorithm.
28
Watershed Algorithm
Watershed-based segmentation algorithm: Find for each pixel in an image, a
downstream path to a local minimum of gray level value (local minimum image surface altitude);
Find a region (catchment basin) as a set of pixels where their respective downstream paths all end up to the same altitude minimum.
29
Edge Image Contour Image
Watershed (over-segmented)
1. Require a Region Merging process to overcome the over-segmentation result;
2. Require a ground truth data for object class region labeling to obtain a thematic image.
30
Region Merging and Thematic Image
We have used the merging criteria called Mean Luminance Difference (Brox et al., 2004).wij = (ui – uj)2