Bağlantılı bileşen etiketleme siyah-beyaz görüntüler üzerine uygulanan ve birbiri ile komşu olan piksellerin bir grup içerisinde toplamaya yarayan bir işlemdir. Bu gruplama sonucunda, resim üzerindeki her bir grup bir nesneyi temsil edecek şekilde numaralandırılır. Daha sonra da istenen grup numaralı nesne üzerinde kolaylıkla işlem yapılabilir. Bağlantılı bileşen etiketleme algoritması 4-komşuluk ve 8-komşuluk olarak ikiye ayrılır. Burada 8 komşuluk seçilirse çapraz piksellerin de komşu olduğu kabul edilmiş olur. Uygulamalarda genellikle 8-komşuluk tercih edildiğinden kodlarda çapraz pikseller de komşu olarak işleme dahil edildi.
Algoritmanın Detayları:
Bağlantılı bileşen etiketleme için pek çok algoritma önerilse de sıklıkla kullanılan ve bence anlaması en kolay olan metot Two-Pass (Çift Geçiş) metodudur. Bu metotta ilk geçişte tüm pikseller tek tek gezilerek şu algoritma işletilir.
Piksel Siyaha Eşit Değilse
{
- Pikselin Tüm komşularına (8 adet) bak
- Tüm komşular siyah veya beyaz ise bu yeni bir pikseldir, piksele yeni bir etiket ata, diğer piksele geç
- Komşulardan en az biri etiketli (siyah veya beyaz değil) ise piksele etiketli komşu / ların en küçük etiketlisini ata, diğer etiketlerin aynı olduğunu kaydet
Algoritmayı detaylı olarak gösteren animasyon aşağıda görülmektedir. Görüldüğü üzere resim piksel piksel gezilerek yukarıdaki algoritmaya göre etiketlenmektedir. Komşu pikseller içerisinde farklı etiketlere rastlandığında ise küçük etiket piksele atanmakta ve büyük etiketin aslında küçük etiket ile aynı olduğu bilgisi saklanmaktadır. Yanda ise ilk geçiş sonrası elde edilen görüntü bulunmaktadır.
![]() | ![]() |
Görüldüğü gibi ilk geçiş sonrası oluşan şekilde 1 ve 2 numaralı nesneler farklı nesnelermiş gibi görünseler de aslında bağlantılı (aynı) nesnelerdir. İkinci geçiş bunu önlemek için vardır. İkini geçişte piksellere içerisindeki değerin gösterdiği değer yazılır. Mesela örneğimizde ikinci geçiş sonrası 2 etiketi görülen piksellere tabloya bakılarak (2->1) 1 etiketi yazılır. Böylece tüm bağımlı nesneler aynı etiket ile etiketlenmiş olur.
Böyle bir etiketleme işlemi sonucunda her ayrık nesne farklı bir etikete sahip olacaktır ancak bu etiketleri bilmeden nesneleri ayırmak mümkün olmayacağından, işlem sonrasında kullanılan etiketler bir etiket dizisi şeklinde { etiket[]={1,3,4,5} gibi (dikkat 2 yerine 1 yazıldığından 2 döndürülmüyor)} dışarıya döndürülmelidir.
Aşağıda yazılan fonksiyonda bunun yerine ben sıralı etiket oluşturmayı seçtim. Bu teknikle etiket dizisi {1,2,3,4} (yani ayrık nesne sayısına kadar sıralı) şekilde elde edildiğinden dizi döndürmek yerine etiketlerin en büyüğünü yani ayrık nesne sayısını döndürmek yeterli olacak. Bu tekniği uygulamak için sırası gelen pikselin değerinin başka bir piksele bağlı olup olmadığına bakılır. Eğer bağlı değilse bunun yeni bir nesne olduğu anlaşılır ve nesne sayısı 1 artırılarak, piksele bu sayı yazılır ve eski değerin yeni değeri işaret ettiği yeni bir vektör üzerinde işaret edilir. Bağlı ise de bağlı olduğu eleman bulunur ve bağlı olduğu elemanın gösterdiği sayı yazılır.
Kodlama Zorlukları:
- Yazılan kodda bir karışıklık yaratmaması için beyaz pikseller 255->1 şeklinde dönüştürülmüştür ve etiketler 2 den başlayarak verilmiştir. (Etiket sayısı 255 olursa bu etiket mi ? Beyaz piksel mi? karışacak)
- Resim üzerinde bir kanalda 255 renk (etiket) saklanabileceğinden etiket sayısı 255 i geçtiğinde yeni etiketler eskisini silecekti. Bu yüzden etiketler RGB kanalları toplam 24 bit olarak kullanılarak sayılan tüm etiketlerin (en fazla ~2^24) saklanması sağlanmıştır.
- Hesaplamada hız kazanmak için 8 komşudan daha etiketlenmemiş olduğu kesin olan öndeki 4 komşuya bakılmamıştır.
Verilen bir ikili resimde 8-komşuluklu bağlantılı bileşenleri etiketleme fonksiyonu şu şekilde yazılmıştır.
Burada kimebagli fonksiyonu verilen bir bileşen numarasının gerçekte kimebagli olduğunu bulmak için yazılmıştır. Yukarıdaki örneği göz önünde bulunduracak olursak kimebagli(list,1), 1 değerini döndürürken kimebagli(list,2) de 1 değerini döndürecektir. Özellikle çoklu bağlantının söz konusu olduğu durumlarda bu fonksiyon tüm bağlantıları inceleyerek en küçük bağlantı numarasını döndürecektir. Örnek olarak etiketleme devam ederken 5 numaralı bileşenin de 2 numaralı bileşene bağlı olduğu görülebilir. Bu durumda kimebagli(list, 5) ifadesi 1 değerini döndürecektir. Fonksiyonun içeriği aşağıda verilmiştir.
Örnek olarak bir önceki yazıda elde ettiğimiz plaka aday bölgeleri etiketleyelim.
içerisinde resim.pixels[i][j].red ifadesinin farklı sayılarla çarpılmasının sebebi sıralı renkler yerine farklı renkler elde ederek görünürlülüğü kolaylaştırmaktır. Resim üzerinde 14 etiket bulunduğundan dolayı tüm etiketler kırmızı kanalında olacağından da sadece kırmızı kanal kullanıldı.Kodların çalıştırılması sonucu 600x450 boyutlarındaki resim için etiketleme 31ms de tamamlandı.
BMP resim_bbe(BMP kaynak,int *etiketsayisi) {
BMP im=yenim_bmp(kaynak.bminfo.width,kaynak.bminfo.height);
long int* list;//birbiri ile baga sahip etiketler
list = new long int [(int)(kaynak.bminfo.width*kaynak.bminfo.height/4)];//en fazla kaç ayrık nesne olabilir
long int **matris;
matris = new long int* [kaynak.bminfo.width];
//etiket sayısı büyük 255 olabileceğinden resim long int yapılıyor
for(int newd=0;newd < kaynak.bminfo.width;newd++) {
matris[newd] = new long int [kaynak.bminfo.height];
}
list[0]=0;//siyah piksel
list[1]=0;//beyaz piksel
int labelcount=2;//ayrık olan nesneye verilecek etiket numarası
int komsu[4];//8 komsu için 4 üne bakmak yeterli
*etiketsayisi=0;//gerçek ayrık nesne sayısını tutar
for(int j=0;j < kaynak.bminfo.height;j++) {
for(int i=0;i < kaynak.bminfo.width;i++) {
//resim siyah beyaz olduğundan sadece 1. kanala bakmak yeterli
kaynak.pixels[i][j].red > 0 ? matris[i][j]=1:matris[i][j]=0 ;
//ve resim 0-255 den 0-1 seviyeye dönüştürülüyor.
}
}
for(int j=1;j < kaynak.bminfo.height-1;j++) {
for(int i=1;i < kaynak.bminfo.width-1;i++) {
if((int)(matris[i][j])!=0) {
komsu[0]=(int)matris[i-1][j ];
komsu[1]=(int)matris[i ][j-1];
komsu[2]=(int)matris[i-1][j-1];
komsu[3]=(int)matris[i+1][j-1];
if(komsu[0]==0 && komsu[1]==0 && komsu[2]==0 && komsu[3]==0) {
matris[i][j]=labelcount;
list[labelcount]=labelcount;
labelcount++;
}
else {
sirala(komsu);
if(komsu[0]!=0 && komsu[1]!=komsu[0]) { list[komsu[1]]=kimebagli(list,komsu[0]); }
if(komsu[1]!=0 && komsu[2]!=komsu[1]) { list[komsu[2]]=kimebagli(list,komsu[1]); }
if(komsu[2]!=0 && komsu[3]!=komsu[2]) { list[komsu[3]]=kimebagli(list,komsu[2]); }
for(int ii=0;ii < 4;ii++) {
//komşulardan 0 dan farklı en küçük olan seçiliyor
if(komsu[ii] > 0) { matris[i][j]=komsu[ii]; break;}
}
}
}//if kapanıyor
}
}
/*Etiketleri sıralı yapmak için yeni bağ listesi tanımlanıyor*/
long int yenibag[labelcount];
yenibag[0]=0;
yenibag[1]=0;
for(int bbsay=2;bbsay < labelcount;bbsay++) {
if(bbsay==kimebagli(list,bbsay)) {
(*etiketsayisi)++;//yeni nesne bulundu
//eski etiketin bu nesne numarasını temsil ettiği saklanıyor
yenibag[bbsay]=*etiketsayisi;
}
}
/* İkinci geçişte önce eski etiketler hesaplanıp yeni etiket matrisinde gösterdiği yer 24 bit olarak kaydediliyor*/
for(int j=0;j < kaynak.bminfo.height-1;j++) {
for(int i=0;i < kaynak.bminfo.width-1;i++) {
long int newlabel = yenibag[kimebagli(list,matris[i][j])];
im.pixels[i][j].red = ( newlabel & 0x0000ff );
im.pixels[i][j].green= ((newlabel & 0x00ff00) >> 8 );
im.pixels[i][j].blue = ((newlabel & 0xff0000) >> 16);
}
}
return im;
}
Burada kimebagli fonksiyonu verilen bir bileşen numarasının gerçekte kimebagli olduğunu bulmak için yazılmıştır. Yukarıdaki örneği göz önünde bulunduracak olursak kimebagli(list,1), 1 değerini döndürürken kimebagli(list,2) de 1 değerini döndürecektir. Özellikle çoklu bağlantının söz konusu olduğu durumlarda bu fonksiyon tüm bağlantıları inceleyerek en küçük bağlantı numarasını döndürecektir. Örnek olarak etiketleme devam ederken 5 numaralı bileşenin de 2 numaralı bileşene bağlı olduğu görülebilir. Bu durumda kimebagli(list, 5) ifadesi 1 değerini döndürecektir. Fonksiyonun içeriği aşağıda verilmiştir.
long int kimebagli(long int* baglistesi,long int deger) {
while(deger!=*(baglistesi+deger)) {
deger=*(baglistesi+deger);
}
return deger;
}
Örnek olarak bir önceki yazıda elde ettiğimiz plaka aday bölgeleri etiketleyelim.
yeni=resim_acm("araba_plaka.bmp");
resim=resim_bbe(yeni,&bbsayisi);
for(int j=0;j < yeni.bminfo.height;j++) {
for(int i=0;i < yeni.bminfo.width;i++) {
resim.pixels[i][j].red= (byte) resim.pixels[i][j].red*(37);
resim.pixels[i][j].green=(byte) resim.pixels[i][j].red*(21);
resim.pixels[i][j].blue=(byte) resim.pixels[i][j].red*(11);
}
}
resim_yaz(resim,"araba_plaka_bbe.bmp");
içerisinde resim.pixels[i][j].red ifadesinin farklı sayılarla çarpılmasının sebebi sıralı renkler yerine farklı renkler elde ederek görünürlülüğü kolaylaştırmaktır. Resim üzerinde 14 etiket bulunduğundan dolayı tüm etiketler kırmızı kanalında olacağından da sadece kırmızı kanal kullanıldı.Kodların çalıştırılması sonucu 600x450 boyutlarındaki resim için etiketleme 31ms de tamamlandı.
![]() | ![]() |
Son olarak sınırları zorlayan bir resim ile kodumuzu test edelim. Resim 1024x1024 büyüklükte ve çok sayıda bağlantılı nesne içeren bir resim. Bu resim için 2173 ayrık nesne 125 ms de bulundu. (resim üzerinde farklı gruplar aynı etikete sahip gibi görünse de her renk birbirinden farklıdır.)
![]() | ![]() |
Yardımcı oldu teşekkürler :)
YanıtlaSilteşekürler gayet güzel bir çalışma olmuş
YanıtlaSilHocam tekrardan merhabalar. "Burada 8 komşuluk seçilirse çapraz piksellerin de komşu olduğu kabul edilmiş olur. Uygulamalarda genellikle 8-komşuluk tercih edildiğinden kodlarda çapraz pikseller de komşu olarak işleme dahil edildi." kısmını biraz daha açar mısınız? Kolay gelsin.
YanıtlaSilBağlantılı bileşen etiketlemede her pikselin komşuları ile ilişkisi incelenir. İki boyutlu bir görüntü için komşu sayısı en fazla sekizdir ve genellikle tüm komşular ile olan durum incelenmelidir. Ancak bazı özel uygulamalarda pikselin; yukarısı, aşağısı, sağı ve solu olmak üzere sadece dört komşusu ile olan ilişkisi incelenebilir.
Sil4 veya 8 komşuluğun sonucu nasıl etkilediğini görmek için yukarıda verdiğim örnek üzerinden gidebiliriz. Bu örnekte beyaz kareleri soldan sağa artacak şekilde 1 den başlayarak numaralandıralım. Eğer uygulamada 4 komşuluk seçilmiş ise 1. satırdaki 3. kare ile 2. satırdaki 4. kare arasındaki çapraz bağ, komşuluk sayılmayacak ve bu iki kareye farklı bileşen numarası atanacaktır. Aynı durum 1. satırdaki 3. kare ile 2. satırdaki 5. kare arasında da geçerli olduğundan 1. satırdaki 3. kare ayrık bir bileşen olarak belirlenecektir. Bu durumda yukarıda verilen imgede toplam 6 farklı ayrık nesne olduğu sonucu bulunacaktır.
Dediğim gibi görsel olarak 6 farklı bileşen yokmuş gibi görünse de bazı uygulamalarda 4-komşulu yöntem tercih edilebilmektedir. Örneğin MS Paintte kullanılan doldurma işleminde 4-komşuluk kullanılmakta ve çapraz bağlı pikseller ayrık iki nesne olarak kabul edilmektedir.
Çok teşekkür ederim. "Hesaplamada hız kazanmak için 8 komşudan daha etiketlenmemiş olduğu kesin olan öndeki 4 komşuya bakılmamıştır." bu kısmı da anlamakta güçlük çekiyorum; işin aslı ben bu algoritmanın kodunu yazmaya çalışıyorum, 8 komşuyu değerlendirmek yerine 4 komşuyu değerlendip işlem yapmak beni cezbetti doğrusu. Ancak neden 8 komşuluk yönteminde 4'ünü dikkate almaya gerek yok dediğinizi hala anlayabilmiş değilim.
SilKoda dikkat edecek olursanız işlem 1. satırdan başlayarak tüm pikselleri soldan sağa taramakta ve her piksele bir bileşen numarası vermektedir. Bu nedenle herhangi bir piksel işlenirken solundaki, üst solundaki, üstündeki ve üst sağındaki 4 piksele zaten bir bileşen numarası atanmıştır. Pikselin diğer komşularına (öndeki 4 komşu ile bahsettiğim pikseller; alt sol, alt, alt sağ ve sağındaki pikseller) henüz bağlantı numarası atanmadığından, ilgili piksele numara atanırken sonucu etkilemeyeceğinden bakılmaya gerek yoktur. Bu nedenle 8 komşulukta 4 komşunun durumunu incelemek yeterlidir. 4 komşulu bağlantılı bileşen etiketlemede ise aynı şekilde 2 komşuya bakmak yeterli olacaktır.
SilHocam çok sağolun elleriniz dert görmesin.
SilMerhabalar hocam kimebagli fonksiyonu burada hangi amaçla kullandınız acaba. İçeriği hakkında biraz bilgi verirmisiniz. Yazı Çok faydalı oldu elinize sağlık
YanıtlaSilMerhabalar, yazı içeriğini kimebagli fonksiyonunu da kapsayacak şekilde güncelledim. İyi çalışmalar.
Silçok teşekkür ederim iyi çalışmalar.
Silmerhaba hocam, paylaştığınız kodları c# a aktarıyorum fakat bazı anlamadığım yerler birde takıldığım durumlar mevcut. kimebaglı fonksiyon çalışmıyor birde sırala fonksiyonunda ne gibi bir ayrıntı var paylaşabilir misiniz?
YanıtlaSilburakbekiraytac@gmail.com
545 4267298