 SİTE
İÇİ ARAMA |
|
|
 Blogroll |
|
|
|
|
|
|
C++ ve K-Ortalama Algoritması ile İmge Bölütleme |
|
| Gönderiliyor lütfen bekleyin... |
|
|
Bu çalışmaya Kocaeli
Üniversitesi Elektronik ve Haberleşme Mühendisliği bölümü İşaret ve Görüntü İşleme
Laboratuvarında yaz stajımda gerçekleştirdim. İlk bölümde imge bölütlemenin ne
olduğunu ve nasıl yapıldığı anlatacağım. Ardından bir imge bölütleme algoritması
olarak da kullanılan k-ortalama algoritmasının yapısı hakkında bilgi vererek,
C++ programlama dili ile nasıl gerçekleştirdiğimi anlatacağım.
İMGE
BÖLÜTLEME
İmge bölütleme, imgeyi birbiriyle
çakışmayan fakat imgenin tümünü içeren alt imge gruplarına ayırma işlemidir.
Bu gruplandırma işlemi imgenin belirli bir veya birden fazla özelliği dikkate
alınarak gerçekleştirilebilmektedir.
Bölütleme işleminde kullanılan özelliğin seçimi uygulamaya bağlı olarak değişiklik
gösterebilir. Bölütlemede kullanılan en temel özellikler gri imgelerde parlaklık,
renkli imgelerde renk bileşenleri olarak sıralanabilir. İmgedeki ayrıtlar ve
doku özellikleri de bölütleme açısından oldukça yararlı bilgiler taşıyabilmektedir.
Genelde bölütlemenin teorik
bir tabanı olmadığından bölütlemeye ilişkin standart bir yöntem bulunmamakta,
sezgisel (ad-hoc) ya da probleme özgü yöntemlerle bölütleme işlemi gerçekleştirilmektedir.
İmge bölütleme bir imgeyi
anlamlı parçalara yada nesnelere ayırma işlemidir ve otonom hedef takiplerinde
oldukça önemli bir işleve sahiptir . Bir bölütleme algoritmasından iyi bir sonuç
alınabilmesi için algoritma hangi matematiksel modele bağlanmış olursa olsun
imge hakkındaki anlamsal veriler ve önceki bilgilerden oluşan sezgiselliğin
de çözüm yöntemine katılması gerekir. Şimdiye kadar literatüre yüzlerce segmentasyon
algoritması sunulmuştur . Tüm imgeler için iyi sonuç veren genel bir algoritma
olmadığı gibi aynı algoritma farklı imgeler üzerinde farklı sonuçlar verebilmektedir
. Algoritmalar genellikle imgelerin gürültüye karşı hassasiyet, aydınlatma koşulları
ve büyüklükleri gibi özelliklerinden dolayı her zaman iyi performans gösteremeyebilmektedirler.
Büyük değişimlere ve detaylara sahip imgeler bölütlenmek istendiğinde hiçbir
algoritma bütün imgeler üzerinde başarılı olamamaktadır . Bölütleme algoritmalarının
genelleme özelliğinin ve kararlılığının (robust) artırılması ile daha fazla
imgeye uyarlanabilir olması üzerine çalışmalar yapılmaktadır. Birçok görme sisteminde
imge bölütleme için kural tabanlı tümleşik metotlar kullanılmıştır . Bu metotlar
problem ve kullanıcı tecrübesini ifade eden kurallara dayalıdır ve daha belirgin
sonuçlar ortaya koymuştur. Kural tabanlı sistemlerin en büyük dezavantajı bilgiyi
kurallara dönüştürmek gibi zor bir işlem gerektirmesidir. Çalışmada sınıflandırma
algoritmaları ile imge bölütleme anlatılmıştır ve bu uygulamaya ait sonuçlar
verilmiştir.
Bölütleme neticesinde elde edilen bölgelerin gerçek imgedeki yapısal parçalara
veya belirgin nesnelere karşı düşmesi beklenmektedir (Rush, 1993). İyi bölütlenmiş
bir imgenin özellikleri Haralick ve Shapiro (1992) tarafından şöyle verilmektedir:
• Gri ton ya da doku gibi
bir özellik açısından bölütlenmiş imgede düzenli ve türdeş bölgelerin elde edilmesi,
• Bölge içlerinin basit olması ve küçük delikler içermemesi,
• Birbirine yakın fakat farklı bögelerin düzgün oldukları özellik açısından
farklı değerler alması,
• Bölge snırlarının basit olamsı, girinti çıkıntı olmaması ve bölge sınırlarının
uzamsal olarak doğru konumda bulunması.
Ancak bu özelliklerin tümünü
aynı anda sağlayan ve her türden imge için başarılı sonçlar veren bölütleme
yöntemi bulabilmek oldukça zordur (Haralick ve Shapiro 1992).
K-ortalama algoritması:
( k-ortalama demetleme
algoritması (k-ortalama clustering algorithm))
Bu algoritma şöyle
çalışır:
a)
önce eğitim kümesinden k tane rastgele merkez seçer.
b)
Her eğitim kümesi elemanının (xi) en yakın olduğu merkezi (mj) bularak xi’i
j’inci kümeye atar.
c)
Daha sonra j’inci kümedeki bütün dökümanları kullanarak yeni bir merkez belirler.
Yeni merkez yine veri kümesinden bir elemandır ve bu elemanının o kümedeki diğer
elemanlara olan uzaklığı minimumdur.
d)
Merkezler bir önceki iterasyona göre değişmiş ise b)’den devam eder. Değişmemiş
ise algoritma durur.
Oluşturulan kümelerin
sınıfları küme içinde en çok geçen sınıf olarak belirlenir. Yeni bir test dökümanının
sınıfı bulunacağı zaman, önce test dokümanına en yakın küme merkezi bulunur.
Test dokümanının sınıfı o kümenin sınıfı olarak belirlenir.
Sınıflandırma
Genel anlamda sınıflandırma, bir veri kümesini sahip olduğu özelliklere göre
sınıf yada kategorilere ayırmaktır. Sınıflandırmanın faydası gereksiz ve tekrarlı
verileri kaldırmasıdır. Dahil oldukları sınıfa göre veriler üzerinde işlem yapılacağı
zaman da bu verilerin sınıflandırılmış olması gerekir. Veriler sınıflandırılırken
hangi sınıfa ait oldukları verilerin renk, boyut, şekil gibi bazı özelliklerine
bakılarak belirlenir. İmgelerde de imgenin sahip olduğu gri ton değerlerine
bakılarak bir sınıflandırma işlemi sağlanabilir. İyi bir sınıflandırma sonucunda
sınıflar arasındaki benzerlik minimum, sınıf içi benzerlik maksimumdur. N bir
veri kümesindeki eleman sayısı ve i=1,2,…,N olmak üzere Xi bu veri kümesindeki
i. eleman olsun. Veri kümesi S={X1,X2,…,XN} dir. Sınıflandırma ile bu N tane
veri K tane sınıftan birine atanır.
Klasik sınıflandırma
algoritmalarından K-ortalama algoritmasının temel adımları aşağıdaki gibidir:
Adım 1: K adet başlangıç sınıfı belirle
Adım 2: Her bir sınıf arası tüm Pi uzaklıklarını ve buna bağlı
olarak KxN boyutundaki uzaklık matrisini (D) hesapla
Adım 3: D matrisini kullanarak her bir noktanın en yakın olduğu
sınıfı belirle ve bu noktayı bu sınıfa ata
Adım 4: Sınıfların merkezlerini hesapla
Adım 5: Sınıflar arası benzerliğin minimum, sınıf içi benzerliğin
maksimum olması, artık hiçbir verinin sınıfının değişememesi veya algoritmanın
belirlenen sayıda icra edilmiş olması gibi durma şartlarından birisi sağlanıyorsa
algoritmayı sonlandır yoksa 2.adıma geri dön.
Sınıf içi benzerliğin
hesaplanmasında yaygın olarak öklit uzaklığı kullanılmaktadır. Bölütlemede temel
amaç öklit uzaklığının minimize edilmesiyle sınıf içi benzerliğin maksimize
edilmesidir. Öklit uzaklığı (benzerliğin tersi) verilerin sınıflarının merkezi
ile kendileri arasındaki farkların kareleri toplamının karekökünün alınması
ile hesaplanabilir.
C++
ile k-ortalama Uygulaması
C++ ile
imge okuma:
C++ ile imge okumak için "CImg.h" kütüphanesi kullanıldı. Bu programın
çalıştırılması için öcelikle bu kütüphane dosyasının yüklü olması gerekmektedir.
//_______________________________________________________________________
//İşaret ve Görüntü İşleme laboratuarı (KULIS)
#include <iostream.h>
#include <conio.h>
#include <string.h>
#include "CImg.h"
#include <math.h>
using namespace cimg_library;
CImg<unsigned char> imgek("C:/imge.bmp");
int x=imgek.dimx(),y=imgek.dimy();
int *ptr,*elemansayisi,*edegtop,*test,*merkx,*merky,*merkxy;
int i,j,s,k,g,m1,ts,adimsayisi;
CImg<int> imge1(x,y);
imgekucult()
{
for(i=0; i<x; i=i+2)
for(j=0; j<y; j=j+2)
imgek(i/2,j/2)=(imgek(i,j)+imgek(i+1,j)+imgek(i+1,j+1)+imgek(i,j+1))/4;
x=x/2; y=y/2;
return 0;
}
void oku()
{
cout<<"kume sayisi gir : ";
cin>>k;
ptr=(int *) malloc(sizeof(int *)*(k*x*y));
merkx=(int *) malloc(sizeof(int *)*(k));
merky=(int *) malloc(sizeof(int *)*(k));
merkxy=(int *) malloc(sizeof(int *)*(k));
elemansayisi=(int *) malloc(sizeof(int *)*(k));
edegtop=(int *) malloc(sizeof(int *)*(k));
test=(int *) malloc(sizeof(int *)*(k));
}
//____________1.adım _____________________
// rastgele merkezler olusturulur.
int randmerk()
{
for(i=0; i<k; i++)
{
*(merkx+i)=random(x);
*(merky+i)=random(y);
*(merkxy+i)=imgek( *(merkx+i),*(merky+i));
*(elemansayisi+i)=0;
*(edegtop+i)=0;
*(test+i)=0;
}
return 0;
}
//_________________1.adim sonu_________________
//_________________2.adim _________________
//merkeze uzaklıklar bulunur imge duzenlenir.
int merkuzak()
{
s=0;
for(i=0; i<x; i++)
for(j=0; j<y; j++)
{
m1=500; // baslangıc kosulu 255 ten buyuk olmalı
for(g=0; g<k; g++)
{*(ptr+(g*x*y)+s)=abs(imgek(i,j)-*(merkxy+g));
m1=min(*(ptr+(g*x*y)+s),m1);
}
for(g=0; g<k; g++)
{
*(ptr+(g*x*y)+s)=*(ptr+(g*x*y)+s)==m1;
*(elemansayisi+g)=*(elemansayisi+g)+*(ptr+(g*x*y)+s);
*(edegtop+g)=*(edegtop+g)+(*(ptr+(g*x*y)+s) * imgek(i,j));
}
s++;
}
return 0;
}
//_________________2.adim sonu_________________
//_________________3.adim _________________
//yeni merkezler oluşur
int yenimerk()
{
for(i=0; i<k; i++)
*(merkxy+i)=*(edegtop+i)/ *(elemansayisi+i);
return 0;
}
//_________________3.adim sonu_________________
main()
{ char c;
while(x*y>160*120)
{ cout<<"imge boyutu : "<<x<<" "<<y<<endl
<<"programi hizlandirmak ve hafiza problemi ile karsilasmamak icin"<<endl
<<"imge boyutunu kucultebilirsiniz bunun icin E ye basiniz"<<endl;
cin>>c;
if(c==E)
{imgekucult();
cout<<"yeni imge boyutu : "<<x<<" "<<y<<endl<<endl;
}
else break;
}
oku();
randmerk();
adimsayisi=0;
//_________________4.adim _________________
while(1==1)
{ adimsayisi++;
for(i=0; i<k; i++)
*(test+i)=*(merkxy+i);
merkuzak();
yenimerk();
ts=0;
for(i=0; i<k; i++)
ts+=*(test+i)==*(merkxy+i);
if(ts==k) break;
}
//_________________4.adim sonu_________________
//bolutlenmıs ımgenın olusturulması
s=0;
for(i=0; i<x; i++)
for(j=0; j<y; j++)
{
for(g=0; g<k; g++)
if(*(ptr+(g*x*y)+s))
imge1(i,j)=g*255/(k-1);
s++;
}
CImgDisplay disp1(imge1,"bölütlenmis imge");
cout<<"adimsayisi : "<<adimsayisi<<endl;
getch();
}
//_____________________________________________________________________
Açıklama:
Bu kütüphane ile, eğer bilgisayarınızda imagemagick programı yüklü değilse sadece
*.bmp uzantılı imgeler üzerinde çalışabilirsiniz.
Öncelikle "
CImg<unsigned char> image("C:/imgek.bmp"); " komutuyla
kullanılacak olan imgenin programa tanıtılması gerekmektedir.
Bu programda k-ortalama
uygulanacak imgenin boyut bilgileri kullanıldığı için
x=image.dimx();
y=image.dimy();
komutlarıyla imgenin boyularını öğrenip gerekli işaretçileri bu bilgilerle tanımlamalısınız.
( burada istenen küme sayısı k=5 olarak alındı.)
Kullanılan bilgisayarda
bellek problemi olmadığından eminseniz imgenin gerçek boyutlarıyla çalışmanız
sadece programı yavaşlatır. Emin değilseniz ‘ imgekucult(); ‘ fonksiyonu ile
imgeyi istediginiz boyutlara getirebilirsiniz.
Bu program algoritmanın
anlaşılması ve programın takibinin kolay olması için adım adım fonksiyonlar
halinde yazıldı.
programın
akış diyagramı:
1.adım:
Rastgele k adet küme merkezi için piksel değerleri belirlenir.
2.adım:
Daha sonra imgedeki her pikselin merkez piksellere mutlak uzaklıkları belirlenir
ve bir merkeze en yakın olan pikseller bir sınfta toplanır.
3.adım:
Oluşan k adet kümenin ayrı ayrı elemalarının sayı değerleri toplamı eleman
sayısına bölünerek yeni merkez piksel değerleri (sınıftaki piksel değerlerinin
ortalaması) bulunur ve 2. adıma geri donulur.
4.adım:
Eğer 3.adımda oluşan merkez piksel değerleri 2.adımdan gelen değerlerle aynı
ise program sonlandırılır.
Programdan
alınan sonuç:
Orjinal imgenin
siyah-beyaz hali:
Bölütlenmiş imge:
Kaynaklar:
1. http://cimg.sourceforge.net
2. Mehmet SEZGİN, doktora tezi
Makale:
C++ ve K-Ortalama Algoritması ile İmge Bölütleme C++ ve C++.NET dili Ersin Özüağ
|
|
|
|
|
-
-
Eklenen Son 10
-
Bu Konuda Geçmiş 10
Bu Konuda Yazılmış Yazılmış 10 Makale Yükleniyor
Son Eklenen 10 Makale Yükleniyor
Bu Konuda Yazılmış Geçmiş Makaleler Yükleniyor
|
|
|
|