tamaño - ¿Cómo encontrar todos los componentes conectados en una imagen binaria en Matlab?

procesamiento de imagenes en matlab ejemplos

Question

He intentado encontrar todos los componentes conectados usando 8 vecinos en una imagen binaria, sin usar la función "etiqueta de bw".

Por ejemplo, mi matriz de entrada es:

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

Me gustaría tener algo como esto:

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

Hay 3 objetos conectados en esta imagen.

Answer 1

Este es un problema común en el procesamiento de imágenes. Hay muchas variaciones, como inundaciones que llenan una región en una imagen, o encontrar qué píxeles pertenecen a la misma región. Un enfoque común es usar la primera búsqueda de profundidad . La idea es atravesar su imagen de izquierda a derecha y de arriba a abajo y para cualquier píxel encontrado que sea igual a 1, los agrega a una pila. Para cada píxel en tu pila, saltas de la pila y luego observas los píxeles vecinos que están rodeando a este píxel. Cualquier píxel que sea 1 que agregue a la pila. Debe mantener una variable adicional donde los píxeles que ya ha visitado , no los agregue a la pila. Cuando la pila está vacía, hemos encontrado esos píxeles que son una región completa, por lo que los marca con una ID única. Luego repite este procedimiento hasta que se quede sin regiones en su imagen.

Como tal, dado que su matriz está almacenada en A , este es el algoritmo básico:

1. Inicialice una matriz que sea del mismo tamaño que A que sea logical . Esto registrará qué píxeles hemos examinado o visitado. También inicialice una matriz de salida B a todos los ceros que le brindan todos los componentes conectados que está buscando. Cualquier ubicación que sea cero al final no pertenece a ningún componente conectado. Inicialice también un contador de ID que realice un seguimiento de la etiqueta de componente conectado que tendrá cada uno de estos.

2. Para cada ubicación que está en nuestra matriz:

   a. Si la ubicación es 0 , marque esta ubicación como visitada y continúe.

   segundo. Si ya hemos visitado esta ubicación, entonces continúe.

   do. Si no hemos visitado esta ubicación ... vaya al Paso # 3.

3. Agregue esta ubicación no visitada a una pila.

   a. Si bien esta pila no está vacía ...

   segundo. Pop esta ubicación fuera de la pila

   do. Si hemos visitado esta ubicación, entonces continúe.

   re. De lo contrario, marque esta ubicación como visitada y marque esta ubicación con la ID de componentes conectados.

   mi. Dada esta ubicación, mira los 8 píxeles vecinos.

   F. Elimine los píxeles de esta lista que se han visitado, no igual a 1 o fuera de los límites de la matriz

   gramo. Cualesquiera que sean las ubicaciones restantes, agréguelas a la pila.

4. Una vez que la pila esté vacía, incremente el contador, luego regrese al Paso # 2.

5. Continúa hasta que hayamos visitado todas las ubicaciones de nuestra matriz.

Sin más preámbulos, aquí está el código.

%// 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 su matriz de ejemplo, esto es lo que obtengo para 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

Para buscar en un vecindario conectado

Para modificar el código para buscar en una región con 4 conexiones, eso es solo Norte, Este, Oeste y Sur, la sección donde ve %// Look at the 8 neighbouring locations , es decir:

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

Para buscar de una forma conectada a 4, simplemente tiene que modificar este código para dar solo esos puntos cardinales:

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

El resto del código permanece intacto.

Para que coincida con la función bwlabel de MATLAB

Si desea hacer coincidir el resultado de la función de bwlabel de bwlabel de MATLAB, bwlabel busca los componentes conectados en la columna principal o en el orden de FORTRAN. El código anterior busca en fila principal o en orden C. Por lo tanto, simplemente tiene que buscar primero a lo largo de las columnas en lugar de las filas como lo está haciendo el código anterior y lo hace intercambiando el orden de los dos lazos.

Específicamente, en lugar de hacer:

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

Tu harías:

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

Esto debería ahora replicar la salida de bwlabel .