By Emy. 2 of By Emy

Copyright @ 2007 By Emy

2 of 69


1

3 of 69

Kompetensi • Mampu menjelaskan dan operasi morfologi • Mampu menerapkan konsep morfologi untuk memperoleh informasi yang menyatakan deskripsi dari suatu benda pada citra • mampu membangun aplikasi untuk mengimplementasikan konsep morfologi pada kasus riil.


4 of 69

Pendahuluan • • •

• •

Operasi morfologi adalah teknik pengolahan citra yang didasarkan pada bentuk segmen atau region dalam citra. Karena difokuskan pada bentuk obyek, maka operasi ini biasanya diterapkan pada citra biner. Segmentasi dilakukan dengan membedakan antara obyek dan latar, antara lain dengan memanfaatkan operasi pengambangan yang mengubah citra warna dan skala keabuan menjadi citra biner Nilai biner dari citra hasil merepresentasikan 2 keadaan: obyek dan bukan obyek (latar). Meskipun lebih banyak dipakai pada citra biner, operasi morfologi sering pula digunakan pada citra skala keabuan dan warna.


2

5 of 69

Pemrosesan citra secara morfologis 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

Hasil operasi morfologi dapat dimanfaatkan untuk pengambilan keputusan dengan analisis lebih lanjut. Copyright @ 2007 By Emy

6 of 69

Contoh citra masukan

S = {(0,0),(0,1),(1,0)} A = {(0,0),(0,1),(0,2), (1,0),(1,1),(1,2), (2,0),(2,1),(2,2)}

S

A

Objek S dan A dapat direpresentasikan dalam bentuk himpunan dari posisi-posisi (x,y) yang bernilai 1 (1=hitam/abu-abu, 0 = putih) Copyright @ 2007 By Emy

3

7 of 69

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)


8 of 69

Operasi Morfologi 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 Merah


4

9 of 69

Operasi Morfologi •

•

Operasi morfologi biasanya didasarkan pada nilai-nilai dari tetangga langsung di sekeliling titik obyek yang ditinjau (Moore neighborhood). Untuk operasi terhubung-4 (4connected) maka tetangga yang diperhatikan hanya yang langsung bersebelahan, yaitu titik di sebelah kiri, kanan, atas dan bawah, sedangkan untuk operasi terhubung-8 (8connected) tetangga diagonalnya diikutsertakan


10 of 69

Definisi Yang di Pakai dalam Operasi Morfologi • Titik obyek, adalah titik yang merupakan bagian dari obyek (p1 = obyek) • Titik latar, adalah titik yang merupakan bagian dari latar (p1 = latar) • B(p1) = banyaknya tetangga dari p1 yang merupakan titik obyek • A(p1) = banyaknya pola “latar, obyek” untuk urutan p2-p4-p6-p8-p2 pada operasi terhubung4 atau urutan p2-p3-p4-p5-p6-p7-p8-p9-p2 pada operasi terhubung-8 • Titik terisolasi, adalah titik obyek yang semua tetangganya adalah titik latar. B(p1) = 0


5

11 of 69

Definisi Yang di Pakai dalam Operasi Morfologi • Titik ujung, adalah titik obyek yang mempunyai tepat sebuah tetangga yang merupakan titik obyek juga. B(p1) = 1. • Titik batas, adalah titik obyek yang salah satu atau lebih tetangganya adalah titik latar. B(p1) < 4 pada operasi terhubung-4 dan B(p1) < 8 pada operasi terhubung-8. • Apabila semua titik tetangganya adalah titik obyek maka dapat dipastikan titik tersebut berada di dalam obyek (bukan titik batas). • Titik simpel, adalah titik obyek yang jika diubah menjadi titik latar maka tidak mengubah kondisi hubungan antar titik-titik obyek tetangganya.


Ilustrasi (1) Titik Terisolasi

12 of 69

Contoh bagian dari citra dengan menggunakan nilai 0 untuk titik obyek dan 1 untuk titik latar. (1) Titik Terisolasi


6

13 of 69

Ilustrasi (2) Titik Ujung


14 of 69

Ilustrasi (3) Titik Batas


7

15 of 69

Beberapa operasi morfologi Beberapa operasi morfologi yang dapat kita lakukan adalah: – pencarian batas/kontur – Dilasi, Erosi – penutupan (closing), pembukaan (opening) – Thinning, shrinking, pruning, thickening, pengerangkaan (skeletonization) – pengisian (filling), pelabelan, dll


16 of 69

Pencarian Batas/Kontur • •

• • •

Operasi ini digunakan untuk menentukan batas/kontur dari segmen obyek. Operasi ini dilakukan terhadap titik-titik obyek, yaitu apabila titik obyek tersebut bukan titik batas maka titik tersebut diubah menjadi titik latar, sedangkan titik-titik batas akan dipertahankan. Untuk mengetahui apakah suatu titik obyek adalah titik batas atau tidak dilakukan dengan cara memeriksa semua titik tetangganya. Apabila ada salah satu saja dari semua tetangga tersebut yang merupakan titik latar, maka titik tersebut adalah titik batas. Sedangkan apabila semua tetangganya adalah titik obyek, maka titik tersebut bukanlah titik batas.


8

17 of 69

Pencarian Batas/Kontur •

Algoritma untuk operasi pencarian batas citra


18 of 69

Pencarian Batas/Kontur

• Contoh program operasi di atas tidak mempertimbangkan batas luar dari citra, sehingga jika ada titik obyek berada tepat di tepi citra, maka hal ini akan mengakibatkan error. • Error tersebut disebabkan pada saat program memeriksa titik tetangganya, sementara titik tetangga tersebut berada di luar citra, maka terjadi operasi terhadap komponen matriks citra dengan indeks di luar ukuran matriks yang telah didefinisikan (yaitu indeks 0 dan indeks yang nilainya lebih besar dari lebar atau tinggi citra). Copyright @ 2007 By Emy

9

19 of 69

Pencarian Batas/Kontur •

• •

Pemeriksaan apakah sebuah titik obyek merupakan titik batas dilakukan dengan memeriksa semua tetangganya, yaitu apabila ada tetangganya (minimal 1) yang merupakan titik latar, maka titik tersebut adalah titik batas. Operasi logika yang digunakan adalah operasi ATAU (OR). Cara lain yang dapat dilakukan adalah dengan menggunakan operasi logika DAN (AND), yaitu apabila semua tetangga titik obyek yang ditinjau adalah titik obyek juga, maka titik tersebut bukanlah titik batas.


20 of 69

Dilasi • Operasi dilasi dilakukan untuk memperbesar ukuran segmen obyek dengan menambah lapisan di sekeliling obyek. • Terdapat 2 cara untuk melakukan operasi ini, yaitu – dengan cara mengubah semua titik latar yang bertetangga dengan titik batas menjadi titik obyek, atau lebih mudahnya set setiap titik yang tetangganya adalah titik obyek menjadi titik obyek. – dengan mengubah semua titik di sekeliling titik batas menjadi titik obyek, atau lebih mudahnya set semua titik tetangga sebuah titik obyek menjadi titik obyek.

• Algoritma untuk operasi dilasi citra biner


10

21 of 69

Dilasi

• • • • • • •

Program operasi dilasi di atas juga tidak mempertimbangkan batas luar dari citra. Untuk menghindari error, maka indeks yang digunakan untuk titik yang ditinjau dimuali dari 2 sampai dengan lebar-1 untuk arah horisontal, serta dari 2 sampai dengan tinggi-1 untuk arah vertikal. Jika semua titik hendak dioperasikan, maka program di atas perlu ditambah dengan pemeriksaan untuk mengetahui apakah titik tetangga yang sedang ditinjau ada di luar batas citra. Jika titik tersebut berada di luar batas citra, maka jangan dilakukan pengubahan terhadap titik tetangga tersebut. Cara lain yang lebih tepat untuk dilakukan adalah dengan menambah ukuran citra sebanyak 2 titik baik ke arah lebar maupun ke arah tinggi citra kemudian citra asli digeser 1 titik ke kanan dan 1 titik ke bawah. Dengan cara ini, operasi dilasi tidak dilakukan terhadap titik-titik yang ada di bagian tepi citra. Dengan demikian tidak akan terjadi operasi terhadap titik yang ada di luar indeks yang diperbolehkan.


22 of 69

Dilasi

D( A, S) = A⊕ S 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 Copyright @ 2007 By Emy

11

23 of 69

Contoh dilasi

S = {(0,0),(0,1),(1,0)} = {poros,(+0,+1),(+1,+0)}

S

A

D

A = {(0,0),(0,1),(0,2), (1,0),(1,1),(1,2), (2,0),(2,1),(2,2)} Posisi poros ( (x,y) ∈ A )

Sxy

(0,0)

{(0,0),(1,0),(0,1)}

(0,1)

{(0,1),(1,1),(0,2)}

(0,2)

{(0,2),(1,2),(0,3)}

.....

......

(2,2)

{(2,2),(2,3),(3,2)}

D Capture proses pada saat posisi poros S ada di (2,2)


24 of 69

Contoh dilasi


12

25 of 69

Contoh dilasi


26 of 69

Erosi •

• •

Operasi erosi adalah kebalikan dari operasi dilasi. Erosi merupakan proses penghapusan titik-titik objek (1) menjadi bagian dari latar (0), berdasarkan structuring element S yang digunakan. Pada operasi ini, ukuran obyek diperkecil dengan mengikis sekeliling obyek. Cara yang dapat dilakukan juga ada 2. – dengan mengubah semua titik batas menjadi titik latar – dengan menset semua titik di sekeliling titik latar menjadi titik latar.

•

Algoritma untuk operasi erosi citra biner


13

27 of 69

Erosi

E( A, S) = A⊗S 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.


28 of 69

Contoh erosi

S = {(0,0),(0,1),(1,0)} = {poros,(+0,+1),(+1,+0)}

S

A

E

A = {(0,0),(0,1),(0,2), (1,0),(1,1),(1,2), (2,0),(2,1),(2,2)} Posisi poros Sxy ( (x,y) ∈ A )

Ko de

(0,0)

{(0,0),(1,0),(0,1)}

1

(0,1)

{(0,1),(1,1),(0,2)}

1

(0,2)

{(0,2),(1,2),(0,3)}

0

.....

......

(2,2)

{(2,2),(2,3),(3,2)}

0

D Capture proses pada saat posisi poros S ada di (2,2). Titik (2,2) akan dihapus karena ada bagian dari S yang berada di luar A


14

29 of 69

Contoh Erosi


30 of 69

Opening • • •

•

Opening adalah proses erosi yang diikuti dengan dilasi. Citra asli didilasi terlebih dahulu, kemudian hasilnya dierosi. Efek yang dihasilkan adalah menghilangnya atau menutup objek-objek kecil atau lubang-lubang kecil yang ada dalam segmen obyek 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:

Ao S = (A ⊗ S) ⊕ S Copyright @ 2007 By Emy

15

31 of 69

Opening • • •

Operasi penutupan juga digunakan untuk menggabungkan 2 segmen obyek yang saling berdekatan (menutup sela antara 2 obyek yang sangat berdekatan). Pada citra asal terdapat 2 buah segmen obyek, namun pada citra hasil hanya tinggal sebuah segmen obyek gabungan. Operasi penutupan dapat juga dilakukan dalam beberapa rangkaian dilasi-erosi (misalnya 3 kali dilasi, lalu 3 kali erosi) apabila ukuran lubang atau jarak antar obyek cukup besar.


32 of 69

Contoh Opening

A ⊗ S

A

( A ⊗ S ) ⊕ S

S Copyright @ 2007 By Emy

16

33 of 69

Contoh Opening


34 of 69

Closing • Operasi pembukaan (Closing) juga merupakan kombinasi antara operasi erosi dan dilasi yang dilakukan secara berurutan, tetapi citra asli dierosi terlebih dahulu baru kemudian hasilnya didilasi. • Efek yang dihasilkan adalah mengisi lubang kecil pada objek, menggabungkan objek-objek yang berdekatan, dan secara umum mensmooth-kan batas dari objek besar tanpa mengubah area objek secara signifikan Rumusnya adalah:

A• S = (A⊕ S) ⊗ S Copyright @ 2007 By Emy

17

35 of 69

Closing • Operasi ini digunakan untuk memutus bagian-bagian dari obyek yang hanya terhubung dengan 1 atau 2 buah titik saja. • Seperti terlihat, pada citra asal terdapat 2 buah obyek, namun pada citra hasil (b) menjadi 3 segmen karena obyek pertama dipisah menjadi 2. • Operasi ini juga digunakan untuk menghilangkan obyek yang sangat kecil. • Pada citra hasil (c), obyek kecil di kanan atas tidak muncul lagi.


36 of 69

Contoh Closing

A

A ⊕ S

( A ⊕ S ) ⊗ S

S


18

37 of 69

Contoh Closing


38 of 69

Contoh opening dan closing


19

39 of 69

Hit-or-Miss transform

A∗ S = ( A⊗S1) ∩( Ac ⊗S2 ) 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) Copyright @ 2007 By Emy

40 of 69

Hit-or-miss transform Contoh: – S1= {b,e,h} – S2={a,d,g,c,f,i}

a

b

c

d

e

f

g

h

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.


20

41 of 69

Contoh hit-or-miss transform

A

S

A*S ÆYang match dipertahankan ÆYang tidak match dihapus


42 of 69

Pengisian (Filling) • Operasi pengisian merupakan kebalikan dari operasi pencarian batas citra. • Pada operasi ini, citra masukan adalah citra batas/kontur, kemudian dilakukan pengisian sehingga diperoleh segmen obyek yang pejal/solid. • Prosesnya dimulai dengan menentukan titik awal pengisian yang terletak di dalam obyek, kemudian bergerak ke arah titik-titik tetangganya. • Operasi dilakukan secara rekursif dan berhenti jika sampai di batas obyek. Perbedaan lokasi titik awal ini dapat mengakibatkan citra hasil pengisian yang diperoleh berbeda satu sama lain, seperti terlihat pada Gambar dibawah ini


21

43 of 69

Pengisian (Filling) Algoritma untuk operasi pengisian citra secara terhubung-4


44 of 69

Pengisian (Filling) • Operasi di atas akan dilakukan dengan cara mengisi obyek dengan arah ke atas sampai menabrak batas obyek Artinya, sebelum menabrak batas (yang berupa titik obyek), maka lokasi yang sedang ditinjau merupakan titik latar. • kemudian ke arah kanan sampai menabrak batas, lalu ke bawah dan akhirnya ke kiri. • Urutan arah di atas dapat diatur menurut kehendak kita sendiri. • Untuk operasi pengisian terhubung-8, maka langkah rekursif di atas ditambahkan juga untuk tetangga diagonalnya (ada 4 titik).


22

45 of 69

Pelabelan Obyek •

• •

•

Operasi pelabelan objek dilakukan apabila dalam suatu citra terdapat lebih dari satu obyek, maka seringkali perlu untuk membedakan antara sebuah obyek dengan obyek yang lain yang terdapat pada citra tersebut. Pada intinya operasi ini hampir mirip dengan operasi pengisian, yakni menggunakan teknik rekursi. Mula-mula dideteksi lokasi sebuah titik yang merupakan bagian dari sebuah obyek, lantas dengan rekursi dilakukan pengisian dengan suatu nilai (label) terhadap obyek tersebut dari lokasi tersebut sampai menemui batas luarnya (menabrak titik latar). Kemudian lanjutkan mendeteksi lokasi yang merupakan titik obyek namun belum terisi oleh operasi tadi atau belum diberi label (dengan kata lain merupakan bagian dari obyek yang lain).


46 of 69

• • •

Pengerangkaan (Skeletonization) Pengerangkaan adalah suatu proses pengikisan sebuah obyek sebanyak mungkin dengan tetap mempertahankan bentuk umum dari polanya. Setalah sebagian besar titik pada obyek tersebut dihilangkan, maka pola dari obyek tersebut harus tetap dapat dikenali. Pola yang tertinggal ini disebut sebagai kerangka (skeleton), di mana sifat-sifatnya adalah: 1. Ketipisan: kerangka obyek berukuran setipis mungkin (1 atau 2 titik) 2. Konektivitas: kerangka dari suatu obyek terhubung satu sama lain sesuai dengan topologi pola aslinya 3. Posisi: letak kerangka berada tepat di tengah obyek 4. Stabilitas: setelah suatu bagian kerangka diperoleh, maka bagian tersebut tidak akan terkikis lagi oleh operasi pengikisan berikutnya


23

47 of 69

Pengerangkaan (Skeletonization) •

•

• •

•

Operasi perangkaan ini sangat berguna ketika kita lebih tertarik pada pola realtif obyek ketimbang ukuran obyek, misalnya pada aplikasi pengenalan karakter (character recognition), pengenalan kromosom, dsb. Terdapat beberapa algoritma yang dapat digunakan untuk operasi perangkaan, antara lain: – algortima Hilditch, dan – algoritma Rosenfeld.

Algoritma Hilditch dengan ukuran jendela (window) 3 x 3, yakni menggunakan tetangga Moore dari titik yang kita tinjau. Pada algoritma yang merupakan operasi terhubung-8 ini dilakukan beberapa kali iterasi pengikisan pada suatu obyek, di mana pada setiap pengikisan dilakukan pemeriksaan pada semua titik dalam citra dan melakukan Pengubahan sebuah titik obyek menjadi titik latar apabila memenuhi keempat kriteria berikut ini: 1. 2 ≤ B(p1) ≤ 6 2. A(p1) =1 3. p2, p4, atau p8 ada yang merupakan titik latar, atau A(p2) ≠ 1 4. p2, p4, atau p6 ada yang merupakan titik latar, atau A(p4) ≠ 1


48 of 69

Pengerangkaan (Skeletonization) • Algoritma dihentikan apabila pada suatu iterasi tidak ada lagi titik yang diubah. • Kriteria 1 – menunjukkan bahwa tidak ada titik terisolasi, B(p1) = 0, ataupun titik ujung, B(p1) = 1, yang terkikis, sebagaimana ditunjukkan pada Gambar dibawah ini. – Demikian juga titik yang ada di dalam obyek seperti pada (d), sedangkan titik pada (c) juga tidak boleh dihilangkan untuk mencegah pengecilan kerangka.


24

49 of 69

Pengerangkaan (Skeletonization) • Kriteria 2

•

– menunjukkan sifat konektivitas, di mana jika kita menghilangkan suatu titik mempunyai nilai A lebih dari 1, seperti pada Gambar dibawah ini, maka pola atau kerangka akan menjadi terputus. – Dengan demikian titik p1 pada contoh-contoh tersebut tidak boleh dihapus.


50 of 69

Pengerangkaan (Skeletonization) • Kriteria 3 – digunakan untuk menghindarkan terhapusnya garis horisontal dengan lebar 2 titik, seperti pada Gambar dibawah ini. – Dalam gambar tersebut, titik obyek pada (a) tidak memenuhi kriteria 3 sehingga tidak boleh dihapus, sedangkan titik p1 pada (b) dan (c) memenuhi kriteria, sehingga mungkin akan dihapus.


25

51 of 69

Pengerangkaan (Skeletonization) • Kriteria 4 – mirip dengan kriteria 3, namun digunakan untuk menghindarkan terhapusnya garis vertikal berlebar 2 titik. – Titik p1 pada (a) tidak memenuhi kriteria tersebut sehingga tidak boleh dihapus, sedangkan pada (b) dan (d) memenuhi syarat, sehingga mungkin dapat dihapus.


52 of 69

Contoh Hasil Operasi Pengerangkaan (Skeletonization)


26

53 of 69

Kelemahan Algoritma Hilditch • tidak dapat digunakan untuk memperoleh kerangka dari semua obyek. • Ada beberapa pola yang akan akan terkikis habis


54 of 69

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


27

55 of 69

Thinning 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


56 of 69

Contoh Thinning


28

57 of 69

Contoh Thinning


58 of 69


29

59 of 69

Key Stages in Digital Image Processing Image Restoration

Morphological Processing

Image Enhancement

Segmentation

Image Acquisition

Object Recognition

Problem Domain

Representation & Description

Colour Image Processing

Image Compression


Images taken from Gonzalez & Woods, Digital Image Processing (2002)

60 of 69

Key Stages in Digital Image Processing: Image Aquisition Image Restoration


Image Enhancement

Segmentation

Image Acquisition

Object Recognition

Problem Domain



Image Compression


30


61 of 69

Key Stages in Digital Image Processing: Image Enhancement Image Restoration


Image Enhancement

Segmentation

Image Acquisition

Object Recognition

Problem Domain



Image Compression



62 of 69

Key Stages in Digital Image Processing: Image Restoration Image Restoration


Image Enhancement

Segmentation

Image Acquisition

Object Recognition

Problem Domain



Image Compression


31


63 of 69

Key Stages in Digital Image Processing: Morphological Processing Image Restoration


Image Enhancement

Segmentation

Image Acquisition

Object Recognition

Problem Domain



Image Compression



64 of 69

Key Stages in Digital Image Processing: Segmentation Image Restoration


Image Enhancement

Segmentation

Image Acquisition

Object Recognition

Problem Domain



Image Compression


32


65 of 69

Key Stages in Digital Image Processing: Object Recognition Image Restoration


Image Enhancement

Segmentation

Image Acquisition

Object Recognition

Problem Domain



Image Compression



66 of 69

Key Stages in Digital Image Processing: Representation & Description Image Restoration


Image Enhancement

Segmentation

Image Acquisition

Object Recognition

Problem Domain



Image Compression


33

67 of 69

Key Stages in Digital Image Processing: Image Compression Image Restoration


Image Enhancement

Segmentation

Image Acquisition

Object Recognition

Problem Domain



Image Compression



68 of 69

Key Stages in Digital Image Processing: Colour Image Processing Image Restoration


Image Enhancement

Segmentation

Image Acquisition

Object Recognition

Problem Domain



Image Compression


34

69 of 69

Tugas • Buatlah makalah mengenai implementasi pemanfaatan pengolahan citra digital pada kasus riil • Carilah dari jurnal-jurnal terbaru lewat internet • Tugas dikerjakan secara kelompok maksimal 3 orang dan dipresentasikan pada pertemuan terakhir


70 of 69

Thank you very much for listening and good luck in your exams Copyright @ 2007 By Emy

35

By Emy. 2 of By Emy

Recommend Documents