Pengolahan Citra Digital

“Segmentasi Citra”

Oleh :Lukki Arjuna10951005568

Fakultas Sains dan TeknologiJurusan Teknik InformatikaUniversitas Islam Negeri Sultan Syarif Kasim Riau

1. Gambaran Umum

Segmentasi citra digital adalah pembagian daerah citra digital menjadi bagian-bagian

daerah yang lebih kecil berdasarkan letak pixel dan intensitasnya yang masih berdekatan.

Pendekatan yang digunakan antara lain berdasarkan jumlah daerah pembagian yang

diinginkan, dan ada juga berdasarkan kriteria untuk suatu tujuan tertentu.

Algoritma segmentasi citra umumnya didasarkan pada salah satu dari diskontinuitas

atau similaritas. Pada diskontinuitas, citra dipartisi berdasarkan perbedaan intensitas yang

mencolok, misalnya edge (tepian) dari citra. Sedangkan pada similaritas, citra dibagi menjadi

beberapa region berdasarkan kesamaan yang dimiliki dalam hal kriteria-kriteria yang telah

ditentukan sebelumnya.

Segmentasi banyak digunakan dalam bidang komputer vision untuk memisahkan

objek dari latar belakangnya dan memisahkan objek yang satu dengan objek yang lain. Satu

daerah dipandang sebagai satu objek atau bagian dari suatu objek. Jika tujuan yang

diinginkan adalah pengenalan objek, maka objek-objek yang terpisah tersebut akan lebih

mudah dikenali oleh komputer. Tetapi jika tujuan yang diinginkan adalah menentukan

koordinat dimensi tiga pixel-pixel, maka koordinat dari pixel-pixel yang satu daerah tersebut

dipandang sebagai titik-titik yang berdekatan atau sebagai suatu permukaan objek yang

kontinu.

Ketunggalan dan keglobalan segmentasi merupakan hal yang sangat penting dalam

komputer vision. Ketunggalan adalah segmentasi citra digital tidak akan berubah walaupun

nilai awal proses segmentasi berubah. Sedangkan keglobalan adalah proses segmentasi

dilakukan dengan melibatkan semua pixel-pixel citra digital. Mean Shift merupakan metode

yang sekaligus memenuhi sifat ketunggalan dan keglobalan.

2. Metode Segmentasi Citra

2.1. Deteksi Diskontinuitas

Ada tiga macam diskontinuitas tingkat keabuan pada citra digital; yaitu : point (titik),

line (garis), edge (tepi).Cara yang paling banyak digunakan untuk mendeteksi diskontinuitas

pada citra digital adalah dengan menjalankan mask (filter) melewati seluruh citra Mask

umumnya berupa matriks m x n, terdiri dari koefisien-koefisien yang jika dijumlahkan akan

bernilai nol, yang menyatakan bahwa response mask akan bernilai nol di area yang tingkat

keabuannya konstan.

Response dari mask pada sembarang titik pada citra :

 

 

 

dimana zi adalah tingkat keabuan dari piksel citra, dan diasosiasikan dengan koefisien mask

wi. Response mask didefinisikan pada lokasi titik pusat mask.

Deteksi Titik (Point detection)

Suatu titik terdeteksi berada di pusat mask jika |R| ≥ T, dimana T adalah threshold

nonnegative. Idenya adalah bahwa titik yang terisolasi (suatu titik dengan tingkat keabuan

yang sangat berbeda dari latar belakangnya dan berada di area yang homogen atau hampir

homogen) akan sangat berbeda dengan latar belakangnya

Deteksi Garis (Line Detection)

Jika mask sebelah kiri dipindahkan pada seluruh citra, maka responnya akan lebih

kuat pada garis dengan ketebalan satu piksel dan berorientasi horisontal. Koefisien mask jika

dijumlahkan adalah nol. Hal ini menunjukkan bahwa respon mask adalah nol pada area

dengan tingkat keabuan konstan.

Misalkan R1, R2, R3, dan R4, menyatakan respons dari mask. Anggaplah bahwa

setiap mask dijalankan sendiri-sendiri pada suatu citra. Jika, pada satu titik citra, |Ri|>|Rj|,

untuk semua j¹i, titik tersebut dikatakan lebih berasosiasi dengan garis dengan arah mask i.

Jika kita ingin mendeteksi garis dengan arah yang sudah ditentukan, kita bisa menggunakan

mask yang sesuai dengan arah tersebut dan melakukan thresholding terhadap outputnya.

2.2. Deteksi Tepi (Edge Detection)

Tepi (edge) adalah himpunan piksel terhubung yang terletak pada boundary di antara

dua region. Tepi ideal seperti diilustrasikan pada gambar 10.5.a adalah himpunan piksel

terhubung (dalam arah vertikal), masing-masing terletak pada transisi step orthogonal dari

tingkat keabuan.

Pada prakteknya, ketidaksempurnaan optik, sampling, dan proses pengambilan data

citra, akan menghasilkan tepi-tepi yang kabur, dengan derajat kekaburan ditentukan oleh

faktor-faktor seperti kualitas peralatan yang digunakan untuk mengambil data citra, rata-rata

sampling, dan kondisi pencahayaan. Akibatnya, tepi lebih banyak dimodelkan seperti “ramp”

(lihat gambar fig 10.5.b). Ketebalan tepi ditentukan oleh panjang ramp. Panjang ramp

ditentukan oleh kemiringan (slope), dan slope ditentukan oleh derajat kekaburan. Tepian

yang kabur cenderung lebih tebal, dan tepian yang tajam cenderung lebih tipis.

Magnitude dari turunan pertama bisa digunakan untuk mendeteksi keberadaan edge

pada suatu titik dalam citra (misalnya, menentukan apakah suatu titik berada pada ramp atau

tidak). Tanda dari turunan kedua bisa digunakan untuk menentukan apakah suatu piksel edge

terletak pada sisi gelap atau sisi terang dari edge. Property zero-crossing (garis lurus imajiner

yang menghubungkan nilai ekstrim positif dan negatif dari turunan kedua akan melintasi nol

di pertengahan edge) cukup berguna untuk menentukan pusat dari edge yang tebal.

Agar dapat diklasifikasikan sebagai titik tepi, transisi tingkat keabuan pada titik tersebut

harus cukup kuat dibandingkan background di sekitarnya. Untuk menentukan apakah suatu

nilai “cukup signifikan” atau tidak, bisa digunakan threshold.

Jadi, suatu titik di dalam citra merupakan bagian dari edge, jika turunan pertama 2-D

nya lebih besar dari threshold. Himpunan titik-titik yang terhubung menurut kriteria

keterhubungan tertentu didefinisikan sebagai edge. Istilah segmen edge digunakan jika

ukuran edge relatif pendek dibanding ukuran citra. Permasalahan dalam segmentasi adalah

bagaimana cara merangkai segmen-segmen edge ini menjadi edge yang lebih panjang. Edge

juga bisa ditentukan menggunakan property zero crossings dari turunan kedua.

Operator Gradien

Gradien dari citra f(x,y) pada lokasi (x,y) didefinisikan sebagai vektor :

Magnitude vektor adalah :

Arah gradien pada (x,y) adalah :

dimana α(x,y) menyatakan sudut vector Ñf di (x, y) terhadap

sumbu x-axis.

Pendekatan lain untuk memperkirakan magnitude vektor adalah :

Laplacian

Laplacian dari fungsi 2-D f(x, y) adalah turunan kedua yang didefinisikan sebagai :

Laplacian umumnya tidak digunakan dalam bentuk aslinya untuk deteksi tepi, karena:

sangat sensitive terhadap noise

magnitude dari Laplacian menghasilkan menghasilkan tepi ganda

tidak dapat mendeteksi arah tepian.

Peranan Laplacian untuk segmentasi adalah :

mendeteksi lokasi edge(tepi) menggunakan properti zero crossing.

Untuk menentukan apakah suatu oiksel berada di daerah gelap atau daerah terang dari

edge (tepi)

Untuk menemukan edge dengan zero-crossing, Laplacian dikombinasikan dengan

fungsi Gaussian berikut:

 dimana r2 = x2 + y2, dan s adalah standard deviasinya.

Sehingga Laplacian dari h adalah:

 

yang disebut sebagai Laplacian of Gaussian(LoG). Tujuan dari fungsi Gaussian pada

LoG adalah untuk memperhalus citra, dan tujuan dari operator Laplacian tersebut

adalah untuk memberikan suatu citra dengan zero-crossing yang digunakan untuk

menentukan lokasi dari edge (tepi). Zero crossing berada di antara nilai positif dan

negative dari Laplacian, sehingga satu cara untuk memperkirakan zero crossing

adalah men-threshold citra LoG dengan menetapkan semua nilai positif menjadi,

misal, putih, dan semua nilai negative menjadi hitam. Kelebihan zero crossing adalah

kemampuannya untuk mereduksi noise dan potensinya untuk citra yang tidak rata.

Edge Linking and Boundary Detection

Local Processing

Dua hal terpenting yang digunakan untuk menentukan persamaan edge pixel pada

analisis ini adalah: kekuatan dari respon gradient operator yang digunakan untuk

memproduksi edge pixel (diperoleh dari nilai ); dan arah dari vektor gradien.

Suatu edge pixel dengan koordinat (x0,y0) dalam predefined neighborhood (x,y),

sama dalam hal magnitude pixel pada (x,y) jika  dimana E

merupakan nonnegative threshold. Suatu edge pixel pada (x0,y0) dalam predefined

neighborhood dari (x,y) mempunyai kesamaan angle dengan pixel pada (x,y) jika

dimana A merupakan nonnegative angle threshold. Satu titik

pada predefined neighborhood dari (x,y) dihubungkan dengan pixel pada (x,y) jika

kriteria magnitude dan arah terpenuhi. Proses ini diulang pada setiap lokasi dalam

gambar.

Global Processing via the Hough Transform

Dalam hal ini, titik-titik dihubungkan oleh ketetapan awal apakah titik-titik itu berada

pada kurva dari bentuk yang ditetapkan. Selain itu juga memperhatikan relasi global

antara pixel. Hough Transform merupakan pendekatan alternatif untuk menemukan

himpunan dari beberapa titik dalam suatu image yang terletak pada garis lurus. Satu

jalan yang dapat digunakan untuk masalah representasi suatu garis menggunakan

persamaan y = ax + b adalah dengan menggunakan representasi normal dari suatu

garis: x cosθ + y sinθ = ρ. Hough Transform dapat diaplikasikan kepada fungsi dari

bentuk g(v,c) = 0, dimana v merupakan koordinat vektor dan c adalah koefisien

vektor.

Pendekatan Hough Transform:

1. Hitung gradien dari suatu image dan lakukan pembatasan untuk mendapatkan

binary image.

2. Spesifikasikan subdivisi dalam ρθ-plane.

3. Periksa jumlah accumulator cells untuk pixel dengan konsentrasi tinggi.

4. Periksa relasi antara pixel-pixel dalam cell yang terpilih.

Global Processing via Graph-Theoretic Techniques

Merupakan pendekatan yag paling rumit dan butuh waktu pemrosesan yang lebih

lama dibandingkan metode-metode sebelumnya. Graph G = (N,U)àdimana U

merupakan pasangan elemen yang tidak berurutan dari N. Arc merupakan setiap

pasang (ni,nj) dari U. Jika suatu arc diarahkan dari node ni ke node nj, maka nj

disebut successor dari node parent ni. Expansi dari suatu node adalah proses

mengidentifikasi successor dari suatu node. Start atau root node yaitu level yang

terdiri dari single node, sedangkan goal node adalah node pada level paling akhir.

Suatu cost c(ni,nj) dapat dihubungkan dengan setiap arc(ni,nj). Urutan dari node n1,

n2,...,nk, dengan setiap node ni menjadi successor dari node ni-1, disebut path dari n1

ke nk. Cost dari path keseluruhan adalah:

Setiap elemen edge yang didefinisikan oleh pixel p dan q mempunyai cost sebagai

berikut: , dimana H = nilai gray-level tertinggi dalam

suatu image, f(p) = nilai gray-level dari p, f(q) = nilai gray-level dari q. Dengan

kesepakatan bahwa titik p berada pada sisi right-hand dari arah perjalanan elemen-

elemen edge. Jika r(n) merupakan perkiraan biaya dari minimum-cost path dari node

awal s ke node akhir, dimana path dibatasi melalui n, maka r(n) = g(n) + h(n)

dimana g(n) à lowest-cost path dari s ke n, dan h(n) didapatkan dengan menggunakan

informasi heuristic yang tersedia.

Langkah-langkah algoritma yang menggunakan r(n) sebagai dasar dari pencarian

grafik:

1. Tandai node awal “open” dan tetapkan g(s) = 0

2. Jika tidak ada node yang bertanda OPEN keluar dengan kegagalan; jika tidak

lanjutkan

3. Tandai dengan ”closed” n node ”open” yang hasil penghitungan r(n)dari

persamaan r(n) = g(n) + h(n) bernilai paling kecil

4. Jika n adalah node akhir, keluar dengan solusi path yang didapatkan dengan

tracing back melalui pointer; jika tidak lanjutkan

5. Tambahkan node n, menghasilkan semua successor (jika tidak ada successor,

kembali ke langkah kedua)

6. Jika successor ni tidak ditandai, maka r(ni) = g(n) + c(n,ni),  tandai dengan

”open” dan kembalikan pointer ke n.

7. Jika successor ni ditandai ”closed” atau ”open”, update nilainya dengan

. Tandai ”open”successor bertanda

”closed” tersebut yang memilki nilai g’ lebih rendah dan arahkan pointer ke n

dari semua node yang memiliki nilai g’ lebih rendah. Lanjutkan ke langkah

kedua.

2.3. Thresholding

Merupakan posisi pusat pada aplikasi segmentasi image karena karakterisitik yang intuitif

dan kesederhanaan implementasi.

Foundation

Menjelaskan dua tipe thresholding: single threshold dan multiple threshold. Pada

single threshold, pixel object dan background mempunyai gray level yang

dikelompokan menjadi dua mode yang dominan. Satu cara untuk memisahkan object

dari background adalah dengan memilih background batas T. Maka, titik (x,y) dimana

 disebut object point; selain itu berarti titik tersebut merupakan

background point. Di lain pihak, pada multiple threshold, pixel object dan background

mempunyai gray level yang dikelompokkan menjadi tiga mode yang dominan,

menggolongkan satu titik (x,y) sebagai object class jika , lalu ke

object class yang lain jika , dan merupakan background jika .

Fungsi T pada thresholding: , dimana adalah gray

level titik (x,y) dan p(x,y) menunjukkan beberapa local property pada titik ini.

Batasan image g(x,y):

 

pixel yang diberi label 1 mengacu pada object sedangkan yang berlabel 0 merupakan

background.

Tiga tipe threshold:

1. Global, jika T tergantung hanya pada f(x,y).

2. Local, jika T tergantung pada f(x,y) maupun p(x,y).

3. Dynamic atau adaptive, jika T tergantung pada koordinat spasial x dan y.

The Role of Illumination

Pada chapter 2 diperkenalkan sebuah model sederhana dari sebuah image f(x,y) yang

dibentuk sebagai hasil dari sebuah komponen yang direfleksikan oleh r(x,y) dan

sebuah komponen cahaya i(x,y). Tujuan dari bab ini adalah menggunakan model ini

untuk mendiskusikan secara jelas efek dari cahaya pada thresholding, terutama pada

global thresholding.

Fungsi computer generated reflectance ditunjukkan pada gambar 10.27(a). Histogram

pada fungsi ini ditunjukkan pada gambar 10.27(b), bimodal dan dapat dipartisi dengan

mudah dengan menempatkan single global threshold T pada lembah histogram.

Perkalian fungsi reflectance pada gambar 10.27(a) oleh fungsi illumination

ditunjukkan pada gambar 10.27(c) yang menghasilkan image yang ditunjukkan pada

gambar 10.27(d). Gambar 10.27(e) menunjukkan histogram dari image ini.

Alasan mengapa histogram pada gambar 10.27(e) diubah, dapat dijelaskan sebagai

berikut :

Dari persamaan (4.5-1) F(x,y) = i(x,y)r(x,y) (10.3-3) Mengambil logaritma natural

dari persamaan ini menghasilkan sebuah penjumlahan :

Z(x,y)   = ln f(x,y) = ln i(x,y) + ln r(x,y) = i’(x,y) + r’(x,y)

Dari teori probabilitas, jika i’(x,y) dan r’(x,y) adalah variable yang independent,

histogram dari z(x,y) diberikan oleh convolution dari histogram i’(x,y) dan r’(x,y)/

Jika i(x,y) konstan, I’(x,y) juga akan konstan, dan histogramnya akan menjadi simple

spike (seperti sebuah impulse).

Ketika mengakses sumber illumnitaion yang tersedia, sebuah solusi yang digunakan

untuk mengkompensasi ketidakseragaman adalah memproyeksikan pola illumination

ke dalam sebuah konstanta, permukaan putih yang memantulkan cahaya.

Ini menghasilkan sebuah image g(x,y) = ki(x,y) dimana k adalah sebuah konstanta

yang tergantung pada permukaan dan i(x,y) adalah pola illumination.

f(x,y) = i(x,y)r(x,y) mendapatkan fungsi illumination yan sama, f(x,y) dibagi g(x,y)

menghasilkan fungsi normal h(x,y) = f(x,y)/g(x,y) = r(x,y)/k.

Jika r(x,y) dapat disegmen menggunakan single threshold T, kemudian h(x,y) dapat

disegmen menggunakan single threshold dari nilai T/k.

Basic Global Thresholding

Teknik yang paing sederhana dari semua thresholding adalah mempartisi image

histogram menggunakan single global threshold T.

Segmentasi diselesaikan dengan men-scan image pixel per pixel dan melabelkan tiap

pixel sebagai obyek atau background, tergantung pada gray level dari pixel tersebut

lebih besar / kecil daripada nilai T.

Misal obyek lebih gelap dari background, maka pixel dengan gray level <= T

dilabelkan hitam(0), dan pixel dengan gray level > T dilabelkan putih(255).

Algoritma berikut dapat digunakan untuk mendapatkan T secara otomatis :

1. Pilih sebuah perkiraan inisial untuk T

2. Segmen image menggunakan T. Ini akan menghasilkan 2 grup pixel :

G1 yang terdiri dari semua pixel dengan nilai gray level > T dan G2 terdiri dari pixel

dengan nilai <=T

3. Hitung nilai gray level rata – rata dan untuk piksel – piksel pada area G1

dan G2.

4. Hitung nilai threshold baru :

5. Ulangi langkah 2 – 4 sampai perbedaan T pada iterasi yang berturut – turut

lebih kecil daripada parameter yang ditetapkan sebelumnya

Basic Adaptive Thresholding

Semua subimage yang tidak mengandung batasan antara obyek dan background

mempunyai varian yang lebih kecil dari 75. Semua image mengandung batasan yang

mempunyai varian yang lebih dari 100. Tiap subimage dengan varian yang lebih besar

dari 100 disegmen dengan sebuah threshold yang dihitung untuk subimage tersebut

menggunakan algoritma yang didiskusikan pada bab sebelumnya.

Optimal Global and Adaptive Thresholding

Seandainya sebuah image hanya mengandung dua area gray-level yang utama.  Nilai

z menunjukkan nilai gray-level. Nilai – nilai ini adalah kuantitas random, dan

histogramnya kemungkinan adalah perkiraan dari probability density function (PDF),

p(z). Fungsi density secara keseluruhan adalah penjumlahan atau pencampuran dari

dua density, satu untuk terang, dan yang lain untuk area gelap pada gambar.

Gambar 10.32 menunjukkan dua PDF. Diasumsikan bahwa dua PDF yang lebih besar

terhubung dengan background level, sedangkan yang lebih kecil menjelaskan gray

level obyek dalam image. Campuran PDF yang menggambarkan variasi gray level

secara keseluruhan pada image adalah :

p(z) = P1p1(z) + P2p2(z)                                              

P1 dan P2 adalah probabilitas dari dua kelas piksel. P1 adalah probabilitas piksel

random dengan nilai z. P2 adalah probabilitas yang mana piksel adalah background

piksel. Asumsikan bahwa piksel yang diberikan termasuk onyek atau background,

sehingga P1 + P2 = 1 Sebuah image disegmentasikan oleh klasifikasi sebagai

background semua piksel dengan gray – level yang lebih besar dari threshold T.

Semua piksel yang lain disebut piksel obyek.

Probabilitas dari sebuah variable random yang mempunyai nilai pada interval [a,b]

adalah integral dari PDF dari a ke b, yang mana area kurva PDF di antara dua batasan

ini.

Probabilitas klasifikasi sebuah titik background sebagai titik obyek

adalah                     

                                           

Ini adalah area di bawah kurva dari p2(z) ke sebelah kiri dari threshold. Probabilitas

dari klasifikasi sebuah titik obyek sebagai background adalah

                                           

Yang mana area di bawah kurva dari p1(z) ke kanan T. Kemudian probabilitas

keseluruhan error adalah

E(T) = P2E1(T) + P1E2(T)                                         

Untuk mencari nilai threshold untuk error ini minimal membutuhkan perbedaan E(T)

dengan respect T (menggunakan Leibniz’s rule) dan hasilnya sama dengan 0.

Hasilnya :

P1p1(T) = P2p2(T)                                                

Satu dari density utama yang digunakan pada cara ini adalah Gaussian density, yang

mana digolongkan oleh dua parameter: mean dan varian. Dalam kasus ini,

                        

dimana dan adalah mean dan varian dari Gaussian density dari satu kelas dari

piksel – piksel dan dan adalah mean dan varians dari kelas lain.

Menggunakan persamaan pada solusi umum dari persamaan (10.3-10) menghasilkan

solusi berikut untuk threshold T :

AT2 + BT + C = 0                                                    

dimana

Karena persamaan kuadrat mempunyai dua solusi yang memungkinkan, nilai dua

threshold dibutuhkan untuk mendapatkan solusi optimal.

Jika varian – varian sama, , cukup untuk sebuah single threshold :

                        

Use of Boundary Characteristic for Histogram Improvement and Local

Thresholding

Puncak histogram yang tinggi, sempit, simetrik, dan terpisah oleh lembah yang dalam,

menambah kemungkinan untuk mendapatkan threshold yang bagus.

Sebuah pendekatan untuk menambah bentuk histogram dengan hanya

mempertimbangkan pixel yang berada atau dekat pada batasan antara objek dan

background. Perbaikan yang sangat jelas yaitu ketergantungan histogram terhadap

ukuran objek dan background lebih sedikit. Contohnya histogram dari sebuah gambar

yang terdiri dari objek-onjek yang kecil pada sebuah background yang besar akan

didominasi oleh puncak yang besar karena konsentrasi yang tinggi dari sebuah tipe

pixel.

Probabilitas dari letak pixel pada sebuah objek akan mendekati probabilitas letak

pixel tersebut pada background, jadi memperbaiki simetri pada lembah histogram.

Penggunaan pixel yang dapat memenuhi ukuran yang berdasarkan gradient and

Laplacian operators memiliki kecenderungan ke lembah yang lebih dalam diantara

puncak histogram.

Penggunaan Laplacian dapat memberi informasi mengenai letak pixel mana yang

berada pada sisi yang terang dan gelap dari sebuah edge.

 

Threshold Based on Several Variables

Sensor menyediakan lebih dari satu variable untuk mengkarakterisasi setiap pixel

pada sebuah image, maka di sini diperbolehkan multispectral thresholding. Gambar

berwarna merupakan contoh dimana tiap pixelnya dikarakterikasi oleh tiga nilai RGB.

Maka sekarang bukan hanya histogram 2-D lagi, tetapi pada kasus ini 3-D. Prosedur

dasarnya sama seperti metode yang digunakan untuk satu variable. Contoh, sebuah

gambar dengan tiga variable (RGB komponen), masing-masing memiliki 16 level

kemungkinan, sebuah 16x16x16 cube. Tiap cell dari cube adalah nilai pixel yang

RGB komponennya memiliki nilai yang berkorespondensi dengan koordinat yang

mendefinisikan lokasi dari cell tertentu. Tiap nilai lalu dibagi dengan total nilai pixel

pada gambar untuk di tampilkan pada sebuah histogram.

Konsep dari thresholding sekarang menjadi satu cara untuk menemukan cluster dari

titik-titik pada ruang 3-D. Contoh, K signifikan cluster dari titik-titik yang ditemukan

pada histogram. Gambar bisa disegmentasi dengan menetapkan sebuah nilai (putih)

pada pixel yang memiliki komponen RGB yang lebih dekat pada satu cluster dan nilai

lainnya (black) pada pixel lainnya di gambar.

Hue and saturation merupakan property yang penting pada banyak aplikasi yang

menggunakan gambar untuk inspeksi secara otomatis.

2.4. Region-Based Segmentation

Tujuan dari segmentasi yaitu membagi sebuah gambar menjadi beberapa region. Pada bagian

ini membahas teknik segmentasi berdasarkan menemukan region secara langsung.

Basic Formulation

R merepresentasikan seluruh region gambar. Proses segmentasi yang mempartisi R

menjadi n subregion, R1,R2 ,…..,Rn yaitu

P(Ri) merupakan logical predicate yang mendefinisikan semua titik pada kumpulan Ri

dan  merupakan himpunan kosong

o Mengindikasikan segmentasi harus lengkap, semua pixel harus pada region

o Titik-titik pada sebuah region harus terhubung

o Region-region harus disjoint

o Kesepakatan antara property harus dipenuhi oleh pixel-pixel pada region

segmentasi. Contoh, P(Ri) = TRUE jika Ri memiliki level gray yang sama.

o Region Ri  dan Rj berbeda

Region Growing

Region growing merupakan sebuah prosedur dimana sekumpulan pixel atau subregion

hingga region yang lebih besar berdasarkan criteria yang sudah didefinisikan

Pendekatan dasar misalnya sekumpulan titik awal dan dari sini region tumbuh dengan

menambahkan pada masing-masing benih ke pixel tetangga yang memiliki property

yang sama dengan benih tersebut.

Deskriptor bisa mendapatkan hasil yang salah jika keterhubungan dan informasi pixel

yang bersebelahan tidak digunakan dalam proses growing region. Contohnya

visualisasi sebuah susunan random pixel dengan hanya tiga nilai gray level yang jelas.

Mengelompokkan pixel dengan level gray yang sama pada sebuah region tanpa

memperhatikan konektivitas yang akan menghasilkan hasil segmentasi menjadi tidak

ada artinya

Permasalahan multimodal histogram baik jika diselesaikan menggunakan pendekatan 

dasar region

Region Splitting and Merging

Selain mendiskusina grow region dari sekumpulan benih titik , alternative lainnya

dengan membagi sebuah gambar ke dalam bagian-bagian secara acak, region yang

tidak berhubungan satu sama lain, lalu merge dan/atau split region sehingga

memenuhi kondisi yang ditentukan.

Prosedurnya yaitu :

1. Split menjadi empat disjoint quadrants pada region Ri  dimana P(Ri ) =

FALSE

2. Merge region yang bersebelahan Rj  dan Rk  dimana P(Ri  U Rk) = TRUE

3. Stop ketika tidak mungkin ada lagi merge dan split

Properti yang berdasarkan mean dan standard deviasi dari pixel pada sebuah bidang

untuk menentukan texture dari sebuah region. Konsep texture segmentation

berdasarkan kegunaan ukuran textur untuk predikat P(Ri )

2.5. Segmentation by Morphological Watersheds

Segmentasi dengan watershed lebih menghasilkan segmentasi yang stabil, termasuk lanjutan

batasan segmentasi

Basic Concepts

Konsep watershed berdasarkan memvisualisasikan sebuah gambar pada tiga dimensi,

dua ruang koordinat versus level gray. Seperti sebuah interpretasi topographic, dapat

ditentukan tiga jenis titik :

a. titik yang termasuk sebuah regional minimum

b. titik pada sebuah jatuhan air, jika ditempatkan pada lokasi ini, akan menjadi

sebuah single minimum

c. titik dimana air akan seperti jatuh je lebih dari satu seperti minimum

Prinsip tujuan algoritma segmentasi berdasarkan konsep ini yaitu untuk mencari garis

batas air

Dam Construction

Pembuatan dam berdasarkan pada binary image. Cara paling sederhana untuk

membangun dam yaitu dengan cara memisahkan himpunan titik binary menggunakan

pembesaran morfologis seperti digambarkan di gambar 10.45.

 

Watershed Segmentation Algorithm

M1, M2,…., MR merupakan koordinat titik pada daerah minima dari image g(x,y).

C(Mi) adalah koordinat titik pada kolam penampungan yang berhubungan dengan

daerah minimum M. T[n] merupakan himpunan  koordinat titik pada g(x,y) di bawah

plane g(x,y)=n.

T[n]{(s,t)|g(s,t)<n}                                              

Cn(Mi) merupakan himpunan koordinat titik pada kolam penampungan yang

berhubungan dengan daerah minimum M dan meluap pada stage n.

             

C[n] adalah gabungan dari porsi kolam penampungan yang meluap pada stage n :

                   

C[max + 1] adalah gabungan dari semua kolam penampungan :

                                         

Algoritma untuk menemukan watershed lines diinisialisasi dengan

C[min+1]=T[min+1]. Algoritma berulang-ulang dengan asumsi pada step n, C[n-1]

sudah dibuat. Procedure untuk mendapatkan C[n] dari C[n-1] tergantung pada 3

kondisi sebagai berikut untuk masing-masing connected component qÎQ[n]  dimana Q

adalah himpunan dari connected component di T[n]:

o q Ç C[n-1]  kosong

o q Ç C[n-1]  berisi satu connected component dari C[n-1]   

o q Ç C[n-1]  berisi lebih dari satu connected component dari C[n-1]   

kondisi (a) terjadi jika sebuah minimum baru ditemukan dimana q disatukan dengan

C[n-1] untuk membentuk C[n]. Kondisi (b) terjadi ketika q berada di dalam kolam

penampungan dari beberapa daerah minimum dimana q disatukan dengan C[n-1]

untuk membentuk C[n]. Kondisi (c) terjadi ketika semua atau bagian dari pemisah dua

atau lebih kolam penampungan ditemukan.

The Use of Marker

Aplikasi dari Watershed Segmentation Algorithm yaitu mengarah pada

oversegmentation yang berkaitan dengan noise dan ketidakteraturan gradient lainnya.

Pendekatan untuk mrngontrol oversegmentation berdasarkan pada konsep markers.

Marker adalah sebuah connected component dari image. Internal marker berhubungan

dengan objek kepentingan sedangkan external marker berhubungan dengan

background. Procedure pemilihan marker terdiri dari preprocessing dan penentuan

himpunan criteria yang harus dipenuhi marker. Sebagai gambaran bisa dilihat pada

gambar 10.47 dan 10.48.

The Use of Motion in Segmentation

Motion adalah isyarat yang sangat kuat yang digunakan oleh manusia dan binatang untuk

memisahkan objek perhatian dari detail yang tidak relevan.

Spatial Techniques BasicApproach

Pendekatan paling sederhana untuk mendeteksi perubahan dua image frame f(x,y,ti) 

dan f(x,y,tj) pada waktu ti  dan tj  yaitu dengan membandingkan dua image per pixel

membentuk sebuah image yang berbeda. Perbedaan antara dua image pada waktu ti

dan tj yaitu:

                              

T adalah threshold yang sudah ditentukan.

Accumulative differences

Accumulative difference image (ADI) dibuat dengan membandingkan reference

image dengan setiap image berikutnya yang berurutan. Reference image merupakan

sebuah urutan image frame , ,…, . ADI terdiri atas tiga

tipe yaitu : absolute, positive, dan negative ADI. Untuk K > 1 maka nilai ADI yaitu :

                                    

                                     

                               

Dimana , ,  adalah absolute, positive, dan negative ADI.

Urutan inequalities dan tanda dari threshold pada persamaan (10.6-3) dan (10.6-4)

dibalik jika nilai tingkat keabuan dari pixel background lebih besar dari tingkat

pergerakan obyek.

Berdasarkan gambar di atas dapat disimpulkan bahwa: (1) nonzero area dari positive

ADI sama dengan ukuran pergerakan obyek. (2 lokasi positive ADI sesuai dengan

lokasi pergerakan obyek pada reference frame. (3) penghitungan pada positive ADI

berhenti ketika pergerakan obyek sudah dipindahkan semua sama seperti obyek pada

reference frame. (4) absolute ADI terdiri dari wilayah positive dan negative ADI. (5)

arah dan kecepatan dari pergerakan obyek bisa ditentukan dari entry pada absolute

dan negative ADI.

 

Establishing a reference image

Procedure untuk mendapatkan reference image yaitu menentukan image pertama

dalam urutan image untuk menjadi reference image. Ketika sebuah komponen

nonstationary sudah dipindahkan semua dari posisinya pada reference image,

background yang sesuai pada frame yang sekarang disalin pada lokasi yang ditempati

oleh objek pada reference frame. Reference image yang hanya berisi stationary

component didapatkan jika semua pergerakan obyek sudah dipindahkan semua dari

posisi aslinya. Gambar 10.50 menunjukkan dua frame gambar dari persimpangan lalu

lintas. Gambar pertama ditetapkan sebagai reference.

Frequency Domain Techniques

Pada bagian ini akan dibahas masalah penentuan estimasi pergerakan dengan Fourier

transform. Rumus Euler :

Untuk t = 0, 1,…, K-1; x = 0, 1,…,M-1; a1>=0 dan Dt adalah interval waktu antar

frame.

Untuk K digital image berukuran MxN, maka jumlah proyeksi ke x axis pada setiap

integer waktu adalah :

Sedangkan jumlah proyeksi ke y axis yaitu:

1-D Fourer Transform dari persamaan (10.6-6) dan (10.6-7) yaitu:

dan

Hubungan frequency-velocity yaitu :

                      

              

Tanda dari x-component velocity didapatkan dari perhitungan :

                                                                                

                                                                              

Karena gx sinusoidal, bisa ditunjukkan bahwa S1x dan S2x akan mempunyai tanda

yang sama pada sembarang titik, jika componen velocity v1

positif.