Wie finde ich alle verbundenen Komponenten in einem Binärbild in Matlab?

Question

Ich habe versucht, alle verbundenen Komponenten mit 8 Nachbarn in einem Binärbild zu finden, ohne die Funktion "bwlabel" zu verwenden.

Zum Beispiel meiner Eingangsmatrix ist:

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 

ich so etwas haben würde:

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 

Es gibt 3 verbundene Objekte in diesem Bild.

Answer 1

Dies ist ein häufiges Problem in der Bildverarbeitung. Es gibt viele Variationen, z. B. das Überfüllen einer Region in ein Bild oder das Auffinden von Pixeln, die zur selben Region gehören. Ein gängiger Ansatz ist die Verwendung von depth first search. Die Idee ist, dass Sie Ihr Bild von links nach rechts und von oben nach unten durchqueren, und für alle gefundenen Pixel, die gleich 1 sind, fügen Sie sie einem Stapel hinzu. Für jedes Pixel in Ihrem Stapel blättern Sie den Stapel aus und sehen sich dann die benachbarten Pixel an, die dieses Pixel umgeben. Alle Pixel, die 1 sind, fügen Sie dem Stapel hinzu. Sie müssen eine zusätzliche Variable beibehalten, in der Sie alle Pixel , die Sie bereits besucht haben, nicht hinzufügen. Wenn der Stapel leer ist, haben wir die Pixel gefunden, die eine ganze Region sind, also markieren Sie diese mit einer eindeutigen ID. Sie wiederholen diesen Vorgang, bis keine Bereiche in Ihrem Bild mehr vorhanden sind.

Als solche gegeben, dass Ihre Matrix in A gespeichert ist, ist dies der Grund-Algorithmus:

1. ein Array initialisieren, die die gleiche Größe wie A ist, die logical ist. Dies zeichnet auf, welche Pixel wir untersucht oder besucht haben. Initialisieren Sie außerdem ein Ausgabearray B auf alle Nullen, die Ihnen alle gesuchten verbundenen Komponenten zur Verfügung stellen. Alle Orte, die am Ende Null sind, gehören nicht zu den verbundenen Komponenten. Initialisiere auch einen ID-Zähler, der verfolgt, welche verbundene Komponentenbezeichnung jede dieser Komponenten haben wird.

2. Für jeden Standort, die in unserer Matrix ist:

   a. Wenn der Standort 0 lautet, markieren Sie diesen Standort als besucht und fahren Sie fort.

   b. Wenn wir diesen Standort bereits besucht haben, fahren Sie fort.

   c. Wenn wir diesen Ort nicht besucht haben, gehen Sie zu Schritt 3.

3. Fügen Sie diesen nicht besuchten Ort einem Stapel hinzu.

   a. Während dieser Stapel nicht leer ist ...

   b. Pop diese Stelle aus dem Stapel

   c. Wenn wir diesen Ort besucht haben, fahren Sie fort.

   d. Andernfalls markieren Sie diesen Ort als besucht und markieren Sie diesen Ort mit der ID der verbundenen Komponenten.

   e. Betrachte diesen Ort und sieh dir die 8 benachbarten Pixel an.

   f.Entfernen Sie die Pixel in dieser Liste, die besucht wurden, nicht gleich 1 oder außerhalb der Grenzen der Matrix.

   g. Welche Standorte auch immer übrig bleiben, fügen Sie diese dem Stapel hinzu.

4. Sobald der Stapel leer ist, erhöhen Sie den Zähler, und gehen Sie zurück zu Schritt # 2.

5. Gehen Sie weiter, bis wir alle Standorte in unserem Array besucht haben.

Ohne weitere Umschweife, hier ist der Code.

---

%// 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 

Mit Ihrem Beispiel Matrix, ist es das, was ich für B bekommen:

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 

---

in einer 4-verbunden Nachbarschaft suchen

Um den Code zu ändern, um suche in einer 4-vernetzten Region, also nur Norden, Osten, Westen und Süden, den Abschnitt, wo dusiehst 210, das heißt:

%// 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(:); 

in einer 4-verbunden Mode zu suchen, geben Sie einfach diesen Code zu ändern, um nur die Himmelsrichtungen zu geben:

%// 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]; 

Der Rest des Codes unberührt bleibt.

Um MATLAB bwlabel Funktion

Wenn Sie möchten, passen die Ausgabe von MATLAB bwlabel Funktion, bwlabel sucht nach angeschlossenen Komponenten in einer Spaltenhaupt oder Fortran-Reihenfolge entsprechen. Der obige Code sucht in der Reihenfolge Haupt- oder C-Reihenfolge. Daher müssen Sie zuerst nach Spalten und nicht nach Zeilen suchen, was der obige Code tut, und Sie tun dies, indem Sie die Reihenfolge der zwei for Schleifen vertauschen.

Insbesondere anstatt das zu tun:

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

Sie tun würde:

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

Dies sollte nun die Ausgabe von bwlabel replizieren.