Sebagian besar dari algoritma thinning adalah iteratif. Disetiap iterasinya, piksel sisi diperiksa apakah memenuhi kriteria untuk dihilangkan atau tidak. Terdapat beberapa algoritma thinning di komputer yang sequential dan parallel. Algoritma sequential menggunakan hasil dari iterasi sebelumnya dan hasil yang didapat pada iterasi sekarang digunakan untuk memproses piksel berikutnya. Sedangkan dengan algoritma yang parallel, hanya hasil dari iterasi sebelumnya yang berpengaruh keputusan untuk menghilangkan titik pada iterasi sekarang. Kebanyakan aplikasi menggunakan salah satu dari dua strategi tersebut untuk melakukan thinning pada berbagai bentuk yang berbeda. Satu algoritma menghasilkan skeleton yang bagus untuk beberapa bentuk tertentu tetapi menghasilkan skeleton yang kurang bagus untuk bentuk yang lainnya. Sangatlah sulit untuk mengembangkan algortima thinning yang dapat menghasilkan hasil skeleton yang memuaskan untuk semua variasi bentuk pola.
Sebenarnya thinning merupakan sebuah task yang sederhana bagi manusia. Mereka dapat menerapkan algoritma thinning pada pola dengan variasi bentuknya tanpa kesulitan sedikitpun. Ini tampak bahwa pertama kali mereka menangkap sudut pandang global terhadap bentuk, kemudian menerapkan algoritma thinning yang berbeda untuk bentuk yang berbeda dari bagian yang berbeda dari suatu pola yang sama. Sehingga, skeleton yang dihasilkan biasanya merupakan reference skeleton¸ yaitu selalu menjadi yang terbaik dari penerapan algoritma thinning.
Salah satu masalah terbesar pada algoritma thinning adalah deformation bentuk dari skeleton yang dihasilkan yang terletak diujung dan daerah persilangan seperti tampak pada gambar 1 :
Masalah tersebut timbul sesuai dengan fakta bahwa ketika proses generating skeleton dari dua piksel p1 dan p2 terhubung seperti gambar 2 (a) tidak sesuai harapan yaitu seperti gambar 2 (b) :
Kekurangan lainnya adalah saat mengenerate dua piksel untuk daerah kurva (curved) seperti tampak pada gambar 3 :
Masalah tersebut timbul sesuai dengan fakta bahwa piksel yang ditunjukkan pada gambar 2 (a) terkoneksi seperti gambar 2 (b). Sehingga ini terlihat dua masalah yang saling kontradiksi satu dengan lainnya.
Masalah connectivity dan thick skeleton yang banyak dihasilkan oleh algoritma thinning ketika layer terluar dari piksel sebuah obyek dihilangkan dan struktur dari obyek yang dihasilkan tidak diketahui. Di dalam kasus algoritma serial, batasan diperkenalkan untuk memastikan konektivitas sedemikian rupa sehingga dalam beberapa peristiwa, suatu skeleton yang tebal diproduksi. Sedangkan didalam kasus algoritma paralel, solusi untuk membagi ke dalam beberapa subiterations atau pada memperoleh informasi tentang tetangga dari suatu piksel.
Penjelasan Algoritma
(1)Dalam algoritma Distance Based, kita mengasumsikan image yang diproses image monokrom. Jadi akan ada dua bagian dalam image, yaitu bagian foreground (sebagai objek dari image) dan bagian background. Kemudian dari source image akan dibuat dua temporary image dengan ukuran yang sama dengan source image untuk proses thinning. Dua temporary image tersebut diisi dengan 0 untuk semua pikselnya.
(2)Kemudian temporary image 2 akan diisikan dengan melihat dari source image dengan aturan, semua posisi piksel pada temporary image 2 akan diisi 1 yang sesuai dengan posisi foreground pada source image, sedangkan sisanya dibiarkan 0.
(3)Kemudian masih pada temporary image 2, apabila piksel yang bernilai 1 keempat tetanggnya bernilai >= 1, maka piksel tersebut diubah menjadi 2. Proses ini terus dijalankan sampai seluruh piksel dalam temporary image 2 diproses.
(4)Setiap piksel pada temporary image 2 kemudian dibandingkan dengan ke 8 tetangganya, apabila piksel yang lebih besar berjumlah <= 1, maka posisi yang sama dari temporary image 1 akan diisikan dengan 255, sedangkan sisanya dibiarkan 0. Temporary image 1 inilah sebagai result dari proses distance based thinning.
Implementasi Distance-Based Thinning
//distance-based algorithm
//ipimage = image source
//ipimage1 = image destination
public void distSkeleton(IpImage ipimage, IpImage ipimage1)
{
IpImage ipimage2 = new IpImage();
//bikin temp image (array of int)
ipimage2.createImage(ipimage);
ipimage2.Set(0); //set pixel = 0
ipimage1.Set(0); //set pixel image destination = 0
//jika pixel ipimage != 0,
//set pixel ipimage2 = 1
for(int l = 0; l < ipimage.imageHeight; l++){
for(int i = 0; i < ipimage.imageWidth; i++)
if(ipimage.get(i, l) != 0)
ipimage2.set(i, l, 1);
}
int l1 = 1;
int i2 = 0;
int k1;
do
{
//set counter untuk menghitung jumlah
//pixel yang diubah menjadi 2
k1 = 0;
if(++i2 > 0x186a0) //untuk menghandel tampilan applet
break;
for(int i1 = 0; i1 < ipimage.imageHeight; i1++){
for(int j = 0; j < ipimage.imageWidth; j++)
//jika pixel tengah(current pixel) dan keempat
//tetangganya >= 1,
//set pixel tengah = 2
if(ipimage2.get(j, i1) == l1 //pixel tengah
&& ipimage2.get(j - 1, i1 ) >= l1 //pixel sebelah kiri
&& ipimage2.get(j + 1, i1 ) >= l1 //pixel sebelah kanan
&& ipimage2.get(j , i1 - 1) >= l1 //pixel sebelah atas
&& ipimage2.get(j , i1 + 1) >= l1)//pixel sebelah bawah
{
ipimage2.set(j, i1, l1 + 1);
k1++;
}
}
l1++;
} while(k1 > 0);
for(int j1 = 1; j1 < ipimage2.imageHeight - 1; j1++)
{
for(int k = 1; k < ipimage2.imageWidth - 1; k++)
//deteksi pixel image as foreground
if(ipimage.get(k, j1) != 0)
{
int j2 = 0;//variabel temporary sebagai counter
//jika pixel tengah (curent pixel) > salah satu pixel 8-tetangga,
//increment counter j2
if(ipimage2.get(k - 1, j1 - 1) > ipimage2.get(k, j1))
j2++;
if(ipimage2.get(k , j1 - 1) > ipimage2.get(k, j1))
j2++;
if(ipimage2.get(k + 1, j1 - 1) > ipimage2.get(k, j1))
j2++;
if(ipimage2.get(k - 1, j1 ) > ipimage2.get(k, j1))
j2++;
if(ipimage2.get(k + 1, j1 ) > ipimage2.get(k, j1))
j2++;
if(ipimage2.get(k - 1, j1 + 1) > ipimage2.get(k, j1))
j2++;
if(ipimage2.get(k , j1 + 1) > ipimage2.get(k, j1))
j2++;
if(ipimage2.get(k + 1, j1 + 1) > ipimage2.get(k, j1))
j2++;
//jika counter j2 <= 1,
//set current pixel image destination menjadi putih
if(j2 <= 1)
ipimage1.set(k, j1, 255);
}
}
}
Contoh Eksekusi Program
Tidak ada komentar:
Posting Komentar