Etichettamento di componenti connesse

Etichettamento di componenti connesse, o labelling delle componenti connesse, è un'applicazione algoritmica della teoria dei grafi, nella quale sottoinsiemi di componenti connesse vengono etichettate in modo univoco sulla base di dati euristici. Non va confusa con la segmentazione di immagini. L'etichettamento di componenti connesse è di uso in computer vision per rilevare regioni connesse in immagini digitali binarie, sebbene si presti anche all'elaborazione di immagini a colori e con dati ad alta dimensionalità.

La tecnica di etichettamento di componenti connesse è correlata con il riconoscimento di regioni.

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.

• Teoria dei grafi
• riconoscimento di regioni
• Computer vision