1. Introduzione
Gli algoritmi di labelling di componenti connesse cercano di raggruppare i pixel di un’immagine (binaria o in scala di grigi) in base alla loro connettività, la quale può essere di varia natura, sia effettiva (pixel adiacenti) sia qualitativa (pixel con la stesso valore di intensità). una volta che tutti i gruppi sono stati determinati, ad ogni pixel viene associata un’etichetta di colore in base al gruppo a cui questo è stato assegnato. Rilevare questi gruppi e eseguirne il labelling di gruppi di pixel disgiunti è il punto fondamentale in molte applicazioni di analisi di immagini.
1.1 Approfondimento: Connettività tra pixel
La notazione di pixel connectivity descrive la relazione tra due o più pixel. Due pixel sono considerati connessi se soddisfano una certa condizione sul valore del pixel stesso, oppure sulla loro vicinanza spaziale. Per formulare il concetto di “adiacenza” o “vicinanza spaziale” dobbiamo introdurre il concetto di vicinato. Dato un pixel p di coordinate (x,y) l’insieme dei pixel di coordinate
{(x+1, y), (x-1, y), (x, y+1), (x, y-1)}
è detto 4-neighbors. 8-neighbors invece aggiunge, oltre ai pixel indicati sopra, anche i pixel in diagonale. Un insieme di pixel in cui tutti sono connessi con gli altri è detto componente connessa. Trovare tutte le componenti connesse di un’immagine è il compito dell’algoritmo di labelling descritto in questo articolo.
2. Funzionamento
Questo algoritmo esegue uno scan pixel a pixel (dall’alto in basso e da destra a sinistra) in modo da indentificare regioni di pixel spazialmente connessi che condividono la stesso valore del pixel V. Se l’immagine è binaria V può assumere solo un valore, se invece è in scala di grigi un insieme di valori. Prendiamo come esempio la seguente immagine
L’algoritmo assegna ad ogni zona trovata un valore in scala di grigi
é conveniente passare dalla scala di grigi al colore per il labelling in modo che siano più facilmente distinguibili, ottenendo così la seguente immagine
L’algoritmo ottiene risultati migliori quando l’immagine è stata preprocessata da qualche algoritmo di segmentazione (come il thresholding) o schema di classificazione.
3. Applicazioni
L’applicazione più comune di questo algoritmo è contare il numero di oggetti in un’immagine. Per esempio, nell’esempio indicato sopra, avere 8 colori diversi significa che nell’immagine sono presenti 8 oggetti. Prendiamo come esempio l’immagine seguente, in cui il nostro obiettivo è contare il numero di galline
Per prima cosa eseguo un algoritmo di thresholding per ottenere un’immagine binaria
e lanciando l’algoritmo di labelling ottengo
come versione in scala di grigi e
con label colorate. Il numero di colori diversi in questa immagine è 196, che non è assolutamente il numero di polli ricercato. Questo esempio mostra come l’algoritmo di labelling è solo il passo finale, la parte difficile è ottenere una buona immagine binaria in ingresso che mi rappresenti fedelmente quanto voglio ricercare e che separi in maniera netta gli oggetti interessanti (foreground) dagli oggetti da scartare (background).