Come trovare tutti i componenti connessi in un’immagine binaria in Matlab?

Ho cercato di trovare tutti i componenti collegati utilizzando 8 vicini in un’immagine binaria, senza utilizzare la funzione “bwlabel”.

Ad esempio, la mia matrice di input è:

a = 1 1 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 

Vorrei avere qualcosa di simile a questo:

 a = 1 1 0 0 0 0 0 1 1 0 0 2 2 0 1 1 0 0 0 2 0 1 1 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 

Ci sono 3 oggetti collegati in questa immagine.

Questo è un problema comune nell’elaborazione delle immagini. Ci sono molte varianti, come ad esempio il flood che riempie una regione in un’immagine, o che trova i pixel che appartengono alla stessa regione. Un approccio comune consiste nell’utilizzare la prima ricerca di profondità . L’idea è che attraversi la tua immagine da sinistra a destra e dall’alto verso il basso e per ogni pixel rilevato uguale a 1, li aggiungi a una pila. Per ogni pixel nel tuo stack, tieni fuori dalla pila, poi guarda i pixel vicini che circondano questo pixel. Qualsiasi pixel che si aggiunge alla pila. È necessario mantenere una variabile aggiuntiva dove sono stati già visualizzati tutti i pixel, non li si aggiunge allo stack. Quando lo stack è vuoto, abbiamo trovato quei pixel che sono un’intera regione, quindi li contrassegni con un ID univoco. Quindi ripeti questa procedura finché non rimarrai senza regioni nell’immagine.

In quanto tale, dato che la tua matrice è memorizzata in A , questo è l’algoritmo di base:

  1. Inizializza un array con le stesse dimensioni di A logical . Questo registrerà quali pixel abbiamo esaminato o visitato. Inoltre, inizializza una matrice di uscita B su tutti gli zeri che forniscono tutti i componenti collegati che stai cercando. Qualsiasi posizione che è zero alla fine non appartiene a nessun componente connesso. Inizializza anche un contatore ID che tenga traccia di quale etichetta di componente connessa avrà ciascuna di queste.

  2. Per ogni posizione che è nella nostra matrice:

    un. Se la posizione è 0 , contrassegnare questa posizione come visitata e continuare.

    b. Se abbiamo già visitato questa posizione, quindi continua.

    c. Se non abbiamo visitato questa posizione … vai al passaggio 3.

  3. Aggiungi questa posizione non visitata a una pila.

    un. Mentre questo stack non è vuoto …

    b. Fai uscire questa posizione dalla pila

    c. Se abbiamo visitato questa posizione, quindi continua.

    d. Altrimenti, contrassegnare questo luogo come visitato e contrassegnare questa posizione con l’ID dei componenti connessi.

    e. Data questa posizione, guarda gli 8 pixel vicini.

    f. Rimuovi quei pixel in questa lista che sono stati visitati, non uguale a 1 o fuori limite della matrice

    g. In qualunque posizione rimangano, aggiungili alla pila.

  4. Una volta che lo stack è vuoto, incrementa il contatore, quindi torna al passaggio 2.

  5. Continua fino a quando non abbiamo visitato tutte le posizioni nel nostro array.

Senza ulteriori indugi, ecco il codice.


 %// Step #1 visited = false(size(A)); [rows,cols] = size(A); B = zeros(rows,cols); ID_counter = 1; %// Step 2 %// For each location in your matrix... for row = 1 : rows for col = 1 : cols %// Step 2a %// If this location is not 1, mark as visited and continue if A(row,col) == 0 visited(row,col) = true; %// Step 2b %// If we have visited, then continue elseif visited(row,col) continue; %// Step 2c %// Else... else %// Step 3 %// Initialize your stack with this location stack = [row col]; %// Step 3a %// While your stack isn't empty... while ~isempty(stack) %// Step 3b %// Pop off the stack loc = stack(1,:); stack(1,:) = []; %// Step 3c %// If we have visited this location, continue if visited(loc(1),loc(2)) continue; end %// Step 3d %// Mark location as true and mark this location to be %// its unique ID visited(loc(1),loc(2)) = true; B(loc(1),loc(2)) = ID_counter; %// Step 3e %// Look at the 8 neighbouring locations [locs_y, locs_x] = meshgrid(loc(2)-1:loc(2)+1, loc(1)-1:loc(1)+1); locs_y = locs_y(:); locs_x = locs_x(:); %%%% USE BELOW IF YOU WANT 4-CONNECTEDNESS % See bottom of answer for explanation %// Look at the 4 neighbouring locations % locs_y = [loc(2)-1; loc(2)+1; loc(2); loc(2)]; % locs_x = [loc(1); loc(1); loc(1)-1; loc(1)+1]; %// Get rid of those locations out of bounds out_of_bounds = locs_x < 1 | locs_x > rows | locs_y < 1 | locs_y > cols; locs_y(out_of_bounds) = []; locs_x(out_of_bounds) = []; %// Step 3f %// Get rid of those locations already visited is_visited = visited(sub2ind([rows cols], locs_x, locs_y)); locs_y(is_visited) = []; locs_x(is_visited) = []; %// Get rid of those locations that are zero. is_1 = A(sub2ind([rows cols], locs_x, locs_y)); locs_y(~is_1) = []; locs_x(~is_1) = []; %// Step 3g %// Add remaining locations to the stack stack = [stack; [locs_x locs_y]]; end %// Step 4 %// Increment counter once complete region has been examined ID_counter = ID_counter + 1; end end %// Step 5 end 

Con la tua matrice di esempio, questo è ciò che ottengo per B :

 B = 1 1 0 0 0 0 0 1 1 0 0 2 2 0 1 1 0 0 0 2 0 1 1 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 

Per cercare in un quartiere a 4 connessioni

Per modificare il codice da cercare in una regione a 4 connessioni, ovvero solo Nord, Est, Ovest e Sud, la sezione in cui vedi %// Look at the 8 neighbouring locations , ovvero:

  %// Look at the 8 neighbouring locations [locs_y, locs_x] = meshgrid(loc(2)-1:loc(2)+1, loc(1)-1:loc(1)+1); locs_y = locs_y(:); locs_x = locs_x(:); 

Per effettuare una ricerca in modalità 4 connessa, devi semplicemente modificare questo codice per dare solo quelle direzioni cardinali:

  %// Look at the 4 neighbouring locations locs_y = [loc(2)-1; loc(2)+1; loc(2); loc(2)]; locs_x = [loc(1); loc(1); loc(1)-1; loc(1)+1]; 

Il resto del codice rimane intatto.

Per abbinare la funzione bwlabel di MATLAB

Se vuoi abbinare l’output della funzione bwlabel di MATLAB, bwlabel cerca i componenti connessi nell’ordine di colonna principale o FORTRAN. Il codice sopra cerca nella riga maggiore o nell’ordine C. Quindi devi semplicemente cercare le colonne prima anziché le righe come fa il codice precedente e lo fai scambiando l’ordine dei due cicli for .

In particolare, invece di fare:

 for row = 1 : rows for col = 1 : cols .... .... 

Dovresti fare:

 for col = 1 : cols for row = 1 : rows .... .... 

Questo dovrebbe ora replicare l’output di bwlabel .