Bağlantılı Bileşen Etiketleme

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.

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 &lt 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 &lt 4;ii++)  {
                      //komşulardan 0 dan farklı en küçük olan seçiliyor
                      if(komsu[ii] &gt 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.)