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 bu yazımızda da 8-komşuluk algoritması üzerinde duruldu ve çapraz pikseller de komşu olarak işlemlere dahil edildi.
Algoritmanın Detayları
Bağlantılı bileşen etiketleme için pek çok algoritma önerilse de yazımızda bahsedeceğimiz yöntem literatürde sıklıkla kullanılan ve anlaması diğer yöntemlere göre nispeten kolay olan metot Two-Pass (Çift Geçiş) yöntemidir. Bu yöntemde ilk geçişte tüm pikseller tek tek gezilerek eğer gözek siyaha eşit değilse şu algoritma işletilir.
- 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.
| Bağlantılı Bileşen Etiketleme Animasyonu | Bağlantılı Bileşen Etiketleme Sonucu |
|---|---|
 |
 |
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 sıralı etiket oluşturmayı seçilmiştir. 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 olacaktır. 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ışabilir)
- Resim üzerinde bir kanalda 255 renk (etiket) saklanabileceğinden etiket sayısı 255 i geçtiğinde yeni etiketler eskisini silecekti. Be nedenle etiket imgesi uint32_t tipinde oluşturularak 32 bit etiket numaraları dahi saklanabilir yapılmıştır.
- Hesaplamada hız kazanmak için 8 komşudan daha etiketlenmemiş olduğu kesin olan öndeki 4 komşuya (sağ, sol alt, alt ve sağ alt) bakılmamıştır.
Verilen bir ikili resimde 8-komşuluklu bağlantılı bileşenleri etiketleme fonksiyonu şu şekilde yazılmıştır.
// connected component labeling algorithm as presented in cescript blog (buggy)
void connected_component_label(matrix_t *input, matrix_t *output, uint32_t *numCC)
{
// set the number of connected componenets to zero
numCC[0] = 0;
int cond = channels(input) == 1 && is_8u(input) && is_32u(output);
// if the condition is not met, return
if(!cond)
{
printf("input must be uint8 array with single channel and output must be uint32 array!\n");
return;
}
// get the pointer to the data
uint8_t *in_data = data(uint8_t, input);
uint32_t *out_data = data(uint32_t, output);
// resize the output label matrix
matrix_resize(output, rows(input), cols(input), 1);
// allocate the list array
uint32_t *list = calloc(volume(input) / 4, sizeof(uint32_t)); //en fazla kaç ayrık nesne olabilir
// label number for the next component, 0 background, 1 foreground
uint32_t current_label = 2;
// neighbours of the current pixel (r,c)
uint32_t neigh[4];
// make sure that the input is in 0-1 range
uint32_t idx = 0;
for(idx = 0; idx < volume(input); idx++)
{
out_data[idx] = in_data[idx] > 0 ? 1 : 0;
}
uint32_t r = 0, c = 0;
for (int r = 1; r < rows(input) - 1; r++)
{
for (int c = 1; c < cols(input) - 1; c++)
{
// if the current pixel is foreground
if (at(uint32_t, output, r,c) != 0)
{
// get the four neighbours of the current pixel
neigh[0] = at(uint32_t, output, r, c - 1);
neigh[1] = at(uint32_t, output, r - 1, c);
neigh[2] = at(uint32_t, output, r - 1, c - 1);
neigh[3] = at(uint32_t, output, r - 1, c + 1);
// check all the neighbours, if all of them are unlabeled
if (neigh[0] == 0 && neigh[1] == 0 && neigh[2] == 0 && neigh[3] == 0)
{
// set the current label of the output to the next label
at(uint32_t, output, r, c) = current_label;
// update the connection list
list[current_label] = current_label;
// go to the next label
current_label++;
}
// if one of the neighbour is labeled, find the root of the label
else
{
// sort the labels of the neighbours
sort_neighbours(neigh);
// compare the labels of the neighbours
if (neigh[0] != 0 && neigh[1] != neigh[0])
{
list[neigh[1]] = find_root(list, neigh[0]);
}
if (neigh[1] != 0 && neigh[2] != neigh[1])
{
list[neigh[2]] = find_root(list, neigh[1]);
}
if (neigh[2] != 0 && neigh[3] != neigh[2])
{
list[neigh[3]] = find_root(list, neigh[2]);
}
// starting from the smallest label, pick the first one different from the background
uint32_t l = 0;
for (int l = 0; l < 4; l++)
{
// pick the first one different from the background
if (neigh[l] > 0)
{
at(uint32_t, output, r, c) = neigh[l];
break;
}
}
}
}
}
}
// Create Consecutive Label
uint32_t *final_list = calloc(current_label, sizeof(uint32_t));
// go over all the labels one more time and make them consecutive
uint32_t l = 0;
for (l = 2; l < current_label; l++)
{
if (l == find_root(list, l))
{
// new component found
numCC[0]++;
final_list[l] = numCC[0];
}
}
// re assign the labels that are assigned previously
for (idx = 0; idx < volume(output); idx++)
{
out_data[idx] = final_list[find_root(list, out_data[idx])];
}
// clean unused arrays
free(list);
free(final_list);
}
Burada find_root fonksiyonu verilen bir bileşen numarasının gerçekte kime bağlı olduğunu bulmak için yazılmıştır. Yukarıdaki örneği göz önünde bulunduracak olursak find_root(list,1), 1 değerini döndürürken find_root(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 find_root(list, 5) ifadesi 1 değerini döndürecektir. Fonksiyonun içeriği aşağıda verilmiştir.
// find the minimum label assigned to this value by tracing the connected labels
uint32_t find_root(uint32_t *list, uint32_t value)
{
while (value != list[value])
{
value = list[value];
}
return value;
}
Örnek olarak bir önceki yazıda elde ettiğimiz plaka aday bölgeleri etiketleyebiliriz.
// read image
matrix_t *img = imread("..//data//araba.bmp");
// allocate gray, black-white and labeled image
matrix_t *grayimg = matrix_create(uint8_t, rows(img), cols(img), 1);
matrix_t *bwimg = matrix_create(uint8_t, rows(img), cols(img), 1);
matrix_t *label = matrix_create(uint32_t, rows(img), cols(img), 1);
// convert input to grayscale
rgb2gray(img, grayimg);
// binarize the grayscale image
imthreshold(grayimg, 128, bwimg);
// find connected components
uint32_t conn = 0;
//bwlabel(bwimg, label, &conn);
connected_component_label(bwimg, label, &conn);
// print the number of labels
printf("Label: %d\n", conn);
// assign different color for eack connected component
label2rgb(label, conn, img);
// test output
imwrite(img, "..//data//araba_plaka.bmp");
Kod içerisinde yer alan label2rgb içerisinde uint32_t biçiminde hesaplanan bağlantılı bileşen numaraları farklı sayılarla çarpılarak sebebi sıralı renkler yerine farklı renkler elde etmek için kullanılmaktadır. Verilen görüntü üzerinde toplam 14 bağlantılı bileşen tespit edilmiştir ve sonuçlar aşağıdaki tabloda görselleştirilmiştir.
| Bağlantılı Bileşen Etiketleme Örnek | Bağlantılı Bileşen Etiketleme Sonucu |
|---|---|
 |
 |
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 ile yapılan testlerde toplam 2173 ayrık nesne bulunmuştur (resim üzerinde farklı gruplar aynı etikete sahip gibi görünse de her renk birbirinden farklıdır).
| Bağlantılı Bileşen Etiketleme Örnek | Bağlantılı Bileşen Etiketleme Sonucu |
|---|---|
 |
 |
Yazımızda verilen örnekler ve uygulama koduna yazının GitHub Sayfasından erişebilirsiniz.
NOT: Kodda var olan bir hatadan dolayı GitHub Sayfasında da verilen karmaşık örneklerde algoritma düzgüün çalışmamaktadır. IMLAB görüntü işleme kütüphanesinde burada anlatılan yönteme göre çok daha karışık ve hızlı bir algoritma bwlabel fonksiyonu ile gerçeklenmiştir. Eğer bu işleme projenizde ihtiyaç duyuyor iseniz yazımızda verilen connected_component_label ile aynı girdi ve çıktılara sahip bwlabel fonksiyonunu kullanmanız tavsiye edilir.
Referanslar
-
Di Stefano, Luigi, and Andrea Bulgarelli. “A simple and efficient connected components labeling algorithm.” Proceedings 10th International Conference on Image Analysis and Processing. IEEE, 1999.
-
He, Lifeng, et al. “Fast connected-component labeling.” Pattern recognition 42.9 (2009): 1977-1987.