BAB 3 ANALISIS DAN PENGEMBANGAN ALGORITMA
3.1
Analisis Permasalahan Pengolahan citra merupakan sebuah proses yang memiliki banyak faktor ketidakpastian. Citra tersebut terkadang belum tentu dapat diketahui objeknya, mungkin karena masih terdapat noise, ataupun adanya faktor-faktor ambiguitas pada suatu citra. Bagaimanakah cara komputer mengenali bahwa noise tersebut bukanlah bagian dari citra? Atau bagaimanakah komputer dapat memisahkan antara objek yang satu dengan objek lain yang saling bertindihan? Dan masih banyak lagi ketidakpastian dan ambiguitas lainnya yang terdapat pada sebuah citra. Suatu citra yang ingin diketahui informasinya perlu dianalisis terlebih dahulu dan memerlukan model sebagai pembandingnya. Untuk itulah dilakukan penelitian terhadap teori-teori yang merujuk kepada pengolahan citra. Dari beberapa teknik yang telah diteliti tentang bagaimana cara mengolah suatu citra, ditemukan bahwa masih banyak kekurangan yang terdapat pada teknik-teknik konvensional. Teknik-teknik konvensional yang banyak digunakan saat ini masih belum menunjukkan performa yang baik dalam mengolah suatu citra. Karena alasan itulah dilakukannya penelitian ini untuk memperkenalkan suatu cara atau teknik yang lebih dapat diandalkan dan memuaskan. Fuzzy Evolutionary Programming adalah suatu teknik yang sangat menjanjikan untuk pengolahan citra saat ini. Fuzzy Evolutionary Programming menawarkan sebuah teknik pengolahan citra yang lebih fleksibel dan optimal baik dari segi kualitas
100
101 maupun kecepatan dibandingkan dengan metode-metode konvensional lain yang digunakan saat ini. Dalam skripsi ini, dilakukan dua macam penelitian dalam pengolahan citra, yaitu pengenalan dan pengelompokan beberapa citra yang tidak sempurna dan pendeteksian tepi citra. 3.2
Pendekatan Yang Digunakan
3.2.1 Evolutionary Programming Algoritma yang digunakan pada Evolutionary Programming adalah algoritma yang ditemukan oleh Fogel: Buat sebuah populasi yang terdiri dari m kandidat υk = (υ1k , … , υnk), υjk Є [αj, βj]. Untuk setiap k = 1 ,…, m, hitung fungsi objektif dari nilai f k = f (υk). Ulangi: Untuk setiap k = 1 ,…, m, buatlah keturunan υm+k = next(υk, f k, random), dan hitung nilai fungsi objektif f m+k = f (υm+k) Untuk setiap k = 1 ,…, 2m, pilih himpunan acak U dari c yang diurutkan dari 1 sampai 2m. dan simpan angka wk dari h Є U sehingga f h ≤ f k. Pilih m vector dari himpunan {υk : k = 1 ,…, 2m} yang mempunyai nilai wk tertinggi untuk membentuk generasi selanjutnya dari populasi. Sampai telah mencapai batas.
atau sampai jumlah generasi yang ditentukan
102 Pseudo Code dari Evolutionary Programming: //Inisialisasi waktu t := 0; // inisialisasi populasi awal secara acak initpopulation P (t); // menghitung fitness dari setiap solusi evaluate P (t); // tes keadaan berhenti (waktu, fitness) while not done do // ubah setiap solusi dengan mutasi secara stokhastik P'(t) := mutate P (t); // hitung fitness yang baru evaluate P' (t); // secara stokhastik dipilih solusi untuk populasi selanjutnya P(t+1) := survive P(t),P'(t); // menambahkan hitungan waktu t := t + 1; od
3.2.2 Fuzzy Clustering Pada Fuzzy Clustering
hal pertama yang harus dilakukan adalah
mengumpulkan n objek yang direpresentasikan oleh vector X1,…,Xn. Objek disini adalah objek-objek yang ingin kita kelompokkan. Dengan ini kita akan membagi objek-objek ini kedalam c cluster, yang setiap objeknya direpresentasikan oleh sebuah vektor Oi dimana i = 1,…,c. Inilah yang disebut dengan center of the cluster. Di mana setiap pembagian cluster ini direpresentasikan oleh matriks c x n U = (μij) . Yang mana setiap μij adalah derajat objek Xj terhadap clusternya yang ke i.( i = 1,…,c dan j = 1,…,n). Di sini aturannya adalah 0 ≤ μij ≤ 1,
103 dan Σ i = 1 sampai c dari μij = 1. Tujuan umum dari fuzzy clustering adalah untuk meminimalkan fungsi objektif:
Prosedur fuzzy clustering yang paling dikenal adalah Dunn’s fuzzy cmeans algorithm (Dunn 1974). Prosedur ini menyediakan pendekatan yang efektif untuk segmentasi citra dan pengenalan. Tetapi, seperti yang telah dikemukakan oleh Bedzek(1974), fuzzy c- means algorithm dapat menemui kegagalan pada beberapa kasus dimana terdapat objek yang hanya memiliki sedikit perbedaan antara yang satu dan yang lain. Untuk itulah diperlukan pendekatan GA(Genetic Algorithm) untuk menyempurnakan teknik ini. 3.2.3 Fuzzy Evolutionary Clustering Tentukan m populasi untuk matriks Uk = (μijk) untuk k = 1,…,m, i = 1,…,c, j = 1,…,n, dimana untuk setiap uij diambil secara acak dengan interval antara 0 sampai 1. Untuk k = 1,…,m, dan i = 1,…,c, tentukan center cluster Oik dan fitness function f k dengan rumus:
Setelah itu ulangi prosedur di bawah ini sampai
atau
sampai jumlah generasi yang ditentukan telah mencapai batas: Untuk setiap k = 1,..,m, tentukanlah generasi selanjutnya Um+k dengan cara:
104
Lalu tentukanlah nilai Oim+k dan nilai fitness function yang baru
f
m+k
dengan menggunakan rumus (1) dan (2). Lalu pilihlah m matriks dari (Uk) yang paling cocok untuk membuat generasi selanjutnya.
105
Mulai
Baca gambar
Inisialisasi populasi
Hitung center
Hitung fitness
Mutasi
Hitung center
Hitung fitness
Turnamen
Tidak
fitness < ε atau waktu habis Ya Tampilkan gambar
Selesai
Gambar 3.1 Flow Chart Fuzzy Evolutionary Clustering
106 3.2.3 Generalised Fuzzy Evolutionary Hough Transformation Untuk mendeteksi bentuk yang acak dari sebuah image, langkah pertama adalah mendeteksi tepi yang terdapat pada sebuah image dengan menghitung gradien s(x) dan arah φ(x) pada x dengan persamaan s = √(Δ12 + Δ22) dan φ = tan-1(Δ2 / Δ1) di mana k =1, 2 dan Δk = Σij hk(i,j) f(x+i, y+j). f(x,y) merupakan tingkat keabu-abuan dari sebuah piksel pada image, h1 dan h2 merupakan operator Sobel.
Kemudian dengan nilai s(x) yang didapat kita dapat mendapatkan tepitepi pada image dengan cara membandingkan nilai s(x) dengan sebuah threshold yang ditentukan. Dalam hal ini digunakan metode OTSU untuk mendapatkan nilai threshold tersebut. Langkah selanjutnya adalah menentukan sebuah titik acuan Œ = (a1, a2) dan menghitung untuk setiap arah Φi, i = 1, …, p, koordinat polar (rij, αij), j = 1, …, q, dari titik xij pada kurva di mana gradient dari arahnya sama dengan Φi. Di sini rij, merupakan jarak dari xij ke Œ, dan αij adalah sudut yang terbentuk dari ector (Œ – xij) dengan garis horizontal. Untuk setiap tepi yang terdapat pada image, tentukan Ψij(x, Œ) = |x1 – a1 + rij cosαij| + |x2 – a2 + rij sinαij|
107 Dengan
menggunakan
fungsi
keanggotaan
fuzzy
!σ(0,ε$
yang
merepresentasikan fitnessi dari Œ pada titik x yang nilainya ditentukan dengan persamaan •σ(0,ε)(Ψij(x, Œ)).
Langkah selanjutnya adalah menentukan m populaso dari %ector Œk = (Œ1k, Œ2k) k = 1, …, m, di mana setiap Œlk merupakan nilai acak yang didapatkan dari interval [αl, βl], l = 1, 2. Dari k = 1, …, m, hitung nilai obyektif:
Ulangi Untuk setiap k = 1, …, m, tentukan generasi selanjutnya Œm+k dengan menghitung dari j = 1, …, n, sjk = min(ajk –αj, βj – ajk)
ajm+k = ajk ’ δajk, (+ atau – ditentukan secara acak) Dan hitung nilai obyektif fm+k dengan cara yang sama ketika menghitung fk. Lalu pilihlah m matrix dari (Œk) yang paling cocok untuk membuat generasi selanjutnya. Sampai batas (()Œk – Œk(sebelumnya) +(),)є)./.0)1.2/0)3.45)6789:72.4);.87<=
10>
Mulai
Baca gambar
Tentukan edge
Inisialisasi populasi
Hitung fitness
Mutasi
Hitung fitness
Turnamen
Tidak
fitness < ε atau waktu habis Ya Tampilkan gambar
Selesai
Gambar 3.2 Flow Chart Generalised Fuzzy Evolutionary Hough Transformation
