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ı.


bağlantılı bileşen etiketleme bağlantılı bileşen etiketleme

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.)

bağlantılı bileşen etiketleme bağlantılı bileşen etiketleme

11 yorum:

  1. Yardımcı oldu teşekkürler :)

    YanıtlaSil
  2. teşekürler gayet güzel bir çalışma olmuş

    YanıtlaSil
  3. Hocam 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ıtlaSil
    Yanıtlar
    1. Bağ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.

      4 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.

      Sil
    2. Ç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.

      Sil
    3. Koda 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.

      Sil
    4. Hocam çok sağolun elleriniz dert görmesin.

      Sil
  4. Merhabalar 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ıtlaSil
    Yanıtlar
    1. Merhabalar, yazı içeriğini kimebagli fonksiyonunu da kapsayacak şekilde güncelledim. İyi çalışmalar.

      Sil
    2. çok teşekkür ederim iyi çalışmalar.

      Sil
  5. merhaba 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?

    burakbekiraytac@gmail.com
    545 4267298

    YanıtlaSil

Görüntü işleme ile ilgili yeni yazıları ve bu sitede yer alan yazıların güncellenmiş sürümlerini www.imlab.io veya cescript.github.io adreslerinden takip edebilirsiniz.

X