COMPUTER VISION

REPRESENTASI & DESKRIPSI CITRA

• Tujuannya mengubah citra menjadi bentuk yang lebih mudah dimengerti oleh proses selanjutnya

• Terdapat dua pilihan :

1. Representasi berdasar karakteristik-karakteristik eksternal (batas/bentuk)

Sebuah representasi eksternal dipilih bila fokus utama adalah pada karakteristik bentuk.

Representasi berdasar karakteristik-karakteristik internal (warna/tekstur)

Representasi internal yang dipilih ketika fokus utama adalah pada sifat daerah, seperti warna dan tekstur.

Kode Rantai (Chain Code)

• Digunakan untuk mewakili batas tepi dari object.

• Digambarkan berupa rangkaian segmen yang berupa garis lurus dengan arah dan ukuran yang telah ditentukan.

• Citra Digital umumnya menggunakan format grid dengan spasi yang sama untuk arah x dan y.

• sehingga kode rantai bisa dihasilkan dengan mengikuti batas dalam arah searah jarum jam dan menetapkan arah untuk menghubungkan segmen setiap pasangan piksel.

• Representasi ini didasarkan pada 4 atau 8 konektifitas dari segmen-segmen.

• Arah dari masing-masing segmen dikodekan dengan menggunakan sebuah skema angka.

Kode Rantai (2)

• Kode rantai batas tergantung pada titik awal. Namun, kode dapat dinormalisasi sehubungan dengan titik awal dengan prosedur:
Kami hanya memperlakukan kode rantai melingkar sebagai urutan nomor arah dan mendefinisikan titik awal sehingga urutan angka yang dihasilkan membentuk suatu integer dari magnitudo minimum.

Contoh kode rantai

Kode rantai: 4-connected Kode rantai: 4-connected

Hasil dengan 4 connectivity:
0 0 3 3 3 3 3 3 2 3 2 2 1 2 1 1 1 0 1 1 0 1

Normalisasi:
0 1 0 0 3 3 3 3 3 3 2 3 2 2 1 2 1 1 1 0 1 1

Hasil dengan 8 connectivity:
0 7 6 6 6 6 5 5 3 3 2 1 2 1

Signatures

Mengubah representasi citra dari 2 dimensi menjadi 1 dimensi

Signatures (2)

Untuk obyek lingkaran, akan menghasilkan jari2 yang konstan sepanjang sudut tetha sehingga, grafik outputnya adalah garis lurus seperti gambar a.

Untuk object bujursangkar jari2 tidak konstan sehingga output terlihat seperti gambar b.

Skeleton Suatu Daerah

• Untuk merepresentasikan sebuah daerah

• Disebut skeletonizing atau thinning

• Secara iteratif menghapus titik-titik tepi, tapi :

– Tidak menghapus titik ujung (end point)

– Tidak memutus hubungan keterhubungan

– Tidak menyebabkan erosi berlebihan pada suatu daerah

Langkah 1

• Memberi flag piksel yang hendak dihapus. Syaratnya :

a) 2 <= N(p1) <= 6

b) S(p1) = 1

c) p2.p4.p6 = 0

d) p4.p6.p8 = 0

N(p1)=p2+p3+. . . +p8+p9

S(p1) = transisi 0 ke 1

Langkah 2

• Untuk langkah 1, semua syarat harus terpenuhi. Jika satu tidak memenuhi syarat maka tidak boleh diberi tanda / flag. Langkah 1 dilakukan untuk semua titik pada citra. Selanjutnya baru pixel yg ditandai diubah menjadi 0

• Hapus semua piksel yang telah ditandai !

Langkah 3

• Memberi flag piksel yang hendak dihapus. Syaratnya :

2 <= N(p1) <= 6

b) S(p1) = 1

c) p2.p4.p8 = 0

d) p2.p6.p8 = 0

N(p1)=p2+p3+. . . +p8+p9

Langkah 4

• Hapus semua piksel yang telah ditandai !

Contoh Proses Thinning

Langkah 1:

Langkah 2:

Langkah 3:

Langkah 4:

Deskripsi Citra

Hasil representasi dengan chain code dapat dideskripsikan dengan shape number dan orde.

Shape number = hasil normalisasi berdasarkan
                        perbedaan antara 2 kode yang
                        berdekatan yang dimulai dari
                        kode terkecil.

Orde = Jumlah bit untuk merepresentasikan satu
bentuk.

Contoh Deskripsi Citra Orde 4:

Cara :

kode terakhir diletakkan ke depan/dipinjam à 1 0 3 2 1) Karena 1 0 searah jarum jam, maka membaca difference adalah berlawanan jarum jam sehingga harus 1-2-3-0 à 3 langkah. Selanjutnya dari 0 ke 3 juga searah, jadi kalau berlawanan adalah 0-1-2-3 dan seterusnya sehingga didapat- kan: difference = 3 3 3 3

Contoh Deskripsi Citra Orde 6:

Contoh Dekripsi Citra Orde 8:

PEMROSESAN CITRA SECARA MORFOLOGIS

DEFINISI

• Morphology à morph+logie/logy (bahasa Jerman).

• Morph à perubahan bentuk atau karakter akibat perubahan pada struktur / kompisisi (transformasi).

• Morphological image processing à operasi-operasi perubahan bentuk pada binary image/grayscale image

• Matematika morfologi adalah alat untuk mengekstraksi komponen gambar yang berguna dalam representasi dan deskripsi dari sebuah bentuk dari sebuah daerah/wilayah (region shape), seperti batas (boundaries), kerangka (skeletons), dan convex hull. Morfologi juga digunakan untuk pra atau pasca pengolahan, seperti morfologi penyaringan (filtering), penipisan (thinning), dan pemangkasan (pruning)

• Perbedaan antara pemrosesan citra secara morfologis dengan pemrosesan biasa (yang telah kita pelajari):

• Dulu kita memandang sebuah citra sebagai suatu fungsi intensitas terhadap posisi (x,y)

• Dengan pendekatan morfologi, kita memandang suatu citra sebagai himpunan

Pemrosesan citra secara morfologis

– Pemrosesan citra secara morfologi biasanya dilakukan terhadap citra biner (hanya terdiri dari 0 dan 1), walaupun tidak menutup kemungkinan dilakukan terhadap citra dengan skala keabuan 0-255

– Untuk sementara yang akan kita pelajari adalah pemrosesan morfologi terhadap citra biner

Contoh citra masukan

Operasi Morfologi

• Secara umum, pemrosesan citra secara morfologi dilakukan dengan cara mem-passing sebuah structuring element terhadap sebuah citra dengan cara yang hampir sama dengan konvolusi.

• Structuring element dapat diibaratkan dengan mask pada pemrosesan citra biasa (bukan secara morfologi)

Structuring Element

• Structuring element dapat berukuran sembarang

• Structuring element juga memiliki titik poros (disebut juga titik origin/ titik asal/titik acuan)

• Contoh structuring element seperti objek S dengan titik poros di (0,0) -> warna biru

Beberapa operasi morfologi

• Beberapa operasi morfologi yang dapat kita lakukan adalah:

– Dilasi, Erosi

– Opening, Closing

– Thinning, shrinking, pruning, thickening, skeletonizing

– dll

Dilasi

Dilasi merupakan proses penggabungan titik-titik latar (0) menjadi bagian dari objek (1), berdasarkan structuring element S yang digunakan.Cara dilasi adalah:

- Untuk setiap titik pada A, lakukan hal berikut:

- letakkan titik poros S pada titik A tersebut

beri angka 1 untuk semua titik (x,y) yang terkena / tertimpa oleh struktur S pada posisi tersebut

Contoh dilasi

Erosi

Erosi merupakan proses penghapusan titik-titik objek (1) menjadi bagian dari latar (0), berdasarkan structuring element S yang digunakan.Cara erosi adalah:

- Untuk setiap titik pada A, lakukan hal berikut:

- letakkan titik poros S pada titik A tersebut

- jika ada bagian dari S yang berada di luar A, maka

titik poros dihapus / dijadikan latar.

Opening

Opening adalah proses erosi yang diikuti dengan dilasi.

• Efek yang dihasilkan adalah menghilangnya objek-objek kecil dan kurus, memecah objek pada titik-titik yang kurus, dan secara umum men-smooth-kan batas dari objek besar tanpa mengubah area objek secara signifikan

• Rumusnya adalah:

Contoh Opening

Closing

• Closing adalah proses dilasi yang diikuti dengan erosi.

• Efek yang dihasilkan adalah mengisi lubang kecil pada objek, menggabungkan objek-objek yang berdekatan, dan secara umum men-smooth-kan batas dari objek besar tanpa mengubah area objek secara signifikan

•

Rumusnya adalah:

Contoh Closing

Hit-or-Miss transform

• Suatu structuring element S dapat direpresentasikan dalam bentuk (S1,S2) dimana S1 adalah kumpulan titik-titik objek (hitam) dan S2 adalah kumpulan titik-titik latar (putih)

Hit-or-miss transform

•

Contoh:

– S1= {b,e,h}

– S2={a,d,g,c,f,i}

Hit-and-misss transform A*S adalah kumpulan titik-titik dimana S1 menemukan match di A dan pada saat yang bersamaan S2 juga menemukan match di luar A.

Varian dari erosi dan dilasi

• Shrinking:

– Erosi yang dimodifikasi sehingga piksel single tidak boleh dihapus. Hal ini berguna jika jumlah objek tidak boleh berubah

• Thinning:

– Erosi yang dimodifikasi sehingga tidak boleh ada objek yang terpecah. Hasilnya adalah berupa garis yang menunjukkan topologi objek semula.

Thinning

•

Tujuan: me-remove piksel tertentu pada objek sehingga tebal objek Tersebut menjadi hanya satu piksel.

• Thinning tidak boleh:

- Menghilangkan end-point

- Memutus koneksi yang ada

- Mengakibatkan excessive erosi

• Salah satu kegunaan thinning adalah pada proses pengenalan karakter/huruf

• Ada banyak cara mengimplementasikan thinning, salah satu diantaranya adalah dengan hit-or-miss transform

• Thinning dapat didefinisikan sebagai:

– Thinning(A,{B}) = A – (A * {B})

= A – ((...(A*B1)*B2)..Bn)

Dengan B1, B2, B3..Bn adalah

Structuring element.

Note:

A-(A*B) berarti kebalikan dari A*B

à Yang match dihapus

à Yang tidak match dipertahankan

Contoh Thinning

Segmentasi Citra

Topik

• Pendahuluan

• Edge based:

– Mendeteksi discontinuities

– Edge Linking and Boundary detection

• Region based:

– Thresholding

– Region Growing

– Region Merging and Splitting

– Clustering

• Hybrid

Pendahuluan

• Segmentasi merupakan proses mempartisi citra menjadi beberapa daerah atau objek

• Segmentasi citra pada umumnya berdasar pada sifat discontinuity atau similarity dari intensitas piksel

• Pendekatan discontinuity:

– mempartisi citra bila terdapat perubahan intensitas secara tiba-tiba (edge based)

• Pendekatan similarity:

– mempartisi citra menjadi daerah-daerah yang memiliki kesamaan sifat tertentu (region based)

– contoh: thresholding, region growing, region splitting and merging

Pendekatan 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)

Mendeteksi discontinuity

• Terdiri dari: deteksi titik, deteksi garis, deteksi sisi

• Dapat menggunakan mask/kernel, berbeda untuk setiap jenis deteksi

• Khusus untuk deteksi sisi, dapat menggunakan cara-cara yang telah dibahas sebelumnya, seperti dengan menggunakan operator gradien (Roberts, Sobel, Prewitt), atau Laplacian.

Deteksi titik

Edge Linking & Boundary detection

• Hasil dari deteksi sisi seringkali tidak menghasilkan sisi yang lengkap, karena adanya noise, patahnya sisi karena iluminasi, dan lain-lain.

• Oleh karena itu proses deteksi sisi biasanya dilanjutkan dengan proses edge linking.

• Dari sekian banyak cara, yang akan dibahas:

– Local Processing

– Global Processing dengan teknik Graph-Theoretic

Local Processing

• Merupakan cara paling sederhana, dengan menggunakan analisa ketetanggaan 3x3 atau 5x5.

• Sifat utama yang digunakan untuk menentukan kesamaan piksel sisi adalah

– Nilai gradien: Ñ¦(x,y) = |G_x| + [G_y|

– Arah gradien: a(x,y) = tan-¹(G_x/G_y)

• Jika piksel pada posisi (x₀,y₀) adalah piksel sisi, maka piksel pada posisi (x,y) dalam jendela ketetanggaan yang sama bisa dikategorikan sisi pula jika

– |Ñ¦(x,y) - Ñ¦(x₀,y₀)|£ E

– |a (x,y) - a (x₀,y₀)| < A

– E dan A adalah nilai ambang non negatif

Global Processing with Graph theoretic

• Dapat mengatasi noise

• Komputasi lebih sulit

• Global : langsung mencakup seluruh citra, bukan menggunakan jendela ketetanggan

• Menggunakan representasi graph

– Setiap piksel dianggap sebagai node

– Setiap piksel hanya bisa dihubungkan dengan piksel lain jika mereka bertetangga (4-connected)

– Edge yang menghubungkan piksel (node) p dan q pada graf memiliki nilai (weighted graph):

• C(p,q) = H – [f(p) – f(q)]

• H: nilai intensitas keabuan tertinggi pada citra

• f(p) dan f(q): nilai keabuan piksel p dan q

– Kemudian dicari lintasan sisi dengan cost terendah

Pada contoh ini, ukuran citra hanya berukuran 3x3.

Untuk memudahkan, diasumsikan bahwa edge mulai dari baris teratas dan berakhir di baris terakhir.

Dkl, edge hanya bisa berawal dari (1,1)(1,2) atau (1,2)(1,3), dan berakhir di (3,1)(3,2) atau (3,2)(3,3),

REGION BASED

Thresholding
Region Growing
Region Merging and Splitting
Clustering

Thresholding

• Sering digunakan untuk segmentasi karena mudah dan intuitif.

• Diasumsikan setiap objek cenderung memiliki warna yang homogen dan terletak pada kisaran keabuan tertentu

Pendekatan Region-Based

• Kekurangannya: belum tentu menghasilkan wilayah-wilayah yang bersambungan

•

Prosedur:

– Memerlukan criteria of uniformity (kriteria)

– Memerlukan penyebaran seeds atau dapat juga dengan pendekatan scan line

– Dilakukan proses region growing

unidentified region

Region-based

Konsep Dasar

Anggap himpunan R adalah seluruh daerah citra. Kita akan mempartisi R menjadi daerah-daerah R₁, R₂,… R_n, sedemikian hingga:

– R₁ÈR₂ÈR₃È…R_n= R (segmentasi hrs lengkap, setiap piksel hrs berada dlm sbh region

– R_i adalah daerah yang terhubung (untuk i = 1,2,…n) (point2 dlm region hrs tersambung)

– R_i Ç R_j = Æ untuk semua i,j, i ¹j (region2 hrs disjoint)

– P(R_i) = TRUE untuk i = 1,2,…,n (properti yg hrs dpenuhi piksel2 dl sebuah daerah segmentasi) ex:jika semua piksel dalam Ri mempunyai grey level yg sama

– P(R_i È R_j) = FALSE untuk i ¹j (indikasi bhw region Ri dan Rj adalah berbeda )

• P adalah predikat/kriteria tertentu yang harus dimiliki suatu daerah.

Region Growing

• Tentukan beberapa piksel seed.

– Seed bisa ditentukan manual atau secara random

• Untuk setiap piksel seed, lihat 4 atau 8 tetangganya, jika kriterianya sama (kriteria bisa berupa perbedaan keabuan dengan seed, dll) maka tetangga tersebut bisa dianggap berada dalam 1 region/daerah dengan piksel seed.

• Teruskan proses dengan mengecek tetangga dari tetangga yang sudah kita cek, dst.

• Tidak bisa hanya digunakan kriteria saja, tanpa melihat konektivitas ketetanggaan, karena bisa tidak membentuk daerah

• Stopping rule kadang tidak mencakup semua kemungkinan sehingga pada akhir region growing ada piksel yang belum dicek sama sekali.

Region Splitting n Merging

• Splitting: membagi citra menjadi beberapa daerah berdasarkan kriteria tertentu (teknik quadtree)

• Merging: gabungkan daerah-daerah berdekatan yang memiliki kriteria yang sama.

• Kriteria: bisa varian keabuan dll

• Prosedur umum:

– Split R menjadi 4 kuadran disjoint jika P(R) = FALSE

– Merge sembarang daerah berdekatan R_i, R_jjika P(R_i È R_j) = TRUE

– Berhenti jika tidak ada proses split n merge yang bisa dilakukan

Pendeteksian Tepi (Edge Detection)

Pendeteksian tepi

• Tepi

– Edge, perubahan nilai intensitas derajat keabuan yang mendadak dalam jarak yang singkat

– Terdapat pada batas antara dua daerah pada citra

– Dapat diorientasikan dengan suatu arah, yang dapat berbeda bergantung pada perubahan intensitas

• Ada 3 macam tepi dalam citra digital :

– Tepi curam, arah berkisar 900– Tepi landai/ lebar, sudut arah kecil. Dianggap terdiri dari sejumlah tepi-tepi lokal yang lokasinya berdekatan

– Tepi yang mengandung noise. Perlu dilakukan image enhancement.

Tujuan Deteksi Tepi

• Meningkatkan penampakan garis batas suatu daerah atau objek di dalam citra

• Mencirikan batas objek dan berguna untuk proses segmentasi dan identifikasi objek

• Karena termasuk dalam komponen berfrekuensi tinggi, perlu filter high-pass.

Teknik Mendeteksi Tepi

• Karena termasuk dalam komponen berfrekuensi tinggi, perlu High-Pass Filter (HPF).

• Teknik mendeteksi tepi :

– Operator Gradient Pertama (differential gradient, center difference, Sobel, Prewitt, Roberts)

– Operator Turunan Kedua (Laplacian, Laplacian of Gaussian /LoG)

– Operator Kompas

Operator Gradient Pertama

Perubahan intensitas yang besar dalam jarak yang singkat dipandang sebagai fungsi yang memiliki kemiringan yang besar. Kemiringan dilakukan dengan menghitung turunan pertama (gradient).