如何在Matlab中找到二進制圖像中的所有連接組件？

Question

我一直在試圖找到所有連接的組件使用八個二進制圖像中的鄰居，而不使用函數「bwlabel」。

例如，我輸入矩陣是：

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 

我想有這樣的事情：

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 

有此圖像中3級連接的對象。

Answer 1

這是圖像處理中的常見問題。有很多變化，例如洪水填充圖像中的區域，或查找屬於同一區域的像素。一種常用的方法是使用depth first search。這個想法是，你從左到右和從上到下遍歷你的圖像，遇到的任何像素等於1，你將它們添加到堆棧。對於堆棧中的每個像素，從堆棧彈出，然後查看該像素周圍的相鄰像素。您添加到堆棧的任何像素都是1。您需要保留一個額外的變量，其中任何像素已經訪問，您不需要將這些添加到堆棧中。當堆棧爲空時，我們發現這些像素是整個區域，因此您使用唯一的ID標記這些像素。然後重複此過程，直到圖像中的區域用完。

這樣，因爲你的基質儲存在在A，這是基本的算法：

1. 初始化一個數組，是相同大小A即logical。這將記錄我們已檢查或訪問的像素。同時將輸出數組B初始化爲全零，爲您提供所需的所有連接組件。任何零到最後的位置都不屬於任何連接的組件。同時初始化一個ID計數器，記錄每個連接組件的標籤。

2. 對於每個在我們的矩陣位置：

   一個。如果位置爲0，請將此位置標記爲已訪問並繼續。

   b。如果我們已經訪問過這個位置，然後繼續。

   c。如果我們還沒有訪問過這個位置......請轉到第3步。

3. 將此未訪問位置添加到堆棧。

   a。雖然這個堆棧不是空的...

   b。從堆棧中彈出此位置

   c。如果我們訪問過這個位置，然後繼續。 d）。否則，將此位置標記爲已訪問，並使用連接的組件標識標記此位置。

   e。給定這個位置，看看8個相鄰像素。

   f。刪除已經訪問過的列表中的那些像素，不等於1或超出矩陣的範圍

   g。無論位置是什麼，將這些添加到堆棧中。

4. 堆棧清空後，增加計數器，然後回到步驟＃2。

5. 繼續前進，直到我們訪問了我們陣列中的所有位置。

不用再說了，這裏是代碼。

---

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

你的榜樣矩陣，這是我得到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 

---

要在4連接附近

搜索要修改代碼搜索4連通區域，即僅北部，東部，西部和南部，您看到的部分%// Look at the 8 neighbouring locations，那就是：

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

要在4連接的方式進行搜索，你只需要修改這個代碼，只給那些主要的方向：

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

代碼的其餘部分保持不變。

要如果你想MATLAB的bwlabel函數的輸出，bwlabel搜索欄主要還是爲了FORTRAN連接的部件匹配匹配MATLAB的bwlabel功能

。上面的代碼以行主或C順序搜索。因此，您只需要首先搜索列而不是按照上面的代碼所做的操作，然後通過交換兩個for循環的順序來執行此操作。

具體，而不是做：

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

你會做：

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

這個現在應該複製的bwlabel輸出。