Etichettamento di componenti connesse

Etichettamento di componenti connesse o labelling delle componenti connesse è un'applicazione algoritmica della teoria dei grafi, dove sottoinsiemi di componenti connesse sono unicamente etichetatte in base a date euristiche. Non va confusa con la segmentazione. L'etichettamento di componenti connesse è usata in computer vision per rilevare regioni connesse in immagini digitali binarie, sebbene anche immagini a colori e con dati ad alta dimensionalità possono essere elaborate.

L'etichettamento di componenti connesse è correlato con il riconoscimento di regioni.

Algoritmo a due passi

Lo pseudocodice è il seguente:

algoritmo Due passi(data)
   linked = []
   labels = structure with dimensions of data, initialized with the value of Background
   
   Primo passo
   
   for row in data:
       for column in row:
           if data[row][column] is not Background
               
               neighbors = connected elements with the current element's value
               
               if neighbors is empty
                   linked[NextLabel] = set containing NextLabel                    
                   labels[row][column] = NextLabel
                   NextLabel += 1
               
               else
                   
                   Find the smallest label
                   
                   L = neighbors labels
                   labels[row][column] = min(L)
                   for label in L
                       linked[label] = union(linked[label], L)
   
   Secondo passo
   
   for row in data
       for column in row
           if data[row][column] is not Background         
               labels[row][column] = find(labels[row][column])      
      
   return labels

Gli algoritmi find e union sono implementati come descritti in union find.

Voci correlate

• Teoria dei grafi