He estado tratando de encontrar todos los componentes conectados con 8 vecinos en una imagen binaria, sin utilizar la función «bwlabel».

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.

OriginalEl autor Pepe López | 2014-10-13

1 Comentario

  1. 14

    Este es un problema común en el procesamiento de imágenes. Hay muchas variaciones, tales como inundaciones llenado de una región de una imagen, o la búsqueda de lo que los píxeles que pertenecen a la misma región. Un enfoque común es el uso de primero la profundidad de búsqueda. La idea es que se recorren su imagen, de izquierda a derecha y de arriba a abajo y para cualquier píxeles encontrado que son iguales a 1, se agrega a una pila. Para cada píxel en su pila, pop fuera de la pila, y luego mirar a la vecina píxeles que rodean a este píxel. Los píxeles que se encuentran 1 de agregar a la pila. Usted necesita para mantener una variable adicional donde los píxeles que ya ha visitado, no agregar a la pila. Cuando la pila está vacía, hemos encontrado que los píxeles que son toda una región, por lo que la marca de estos con un IDENTIFICADOR único. Usted, a continuación, repita este procedimiento hasta que se ejecute fuera de las regiones en la imagen.

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

    1. Inicializar una matriz del mismo tamaño que A que es logical. Esto registrará píxeles que hemos examinado o visitado. También inicializar una matriz de salida B a todos los ceros que le da todos los componentes conectados que usted está buscando. Los lugares que son cero en la final no pertenecen a ninguno de los componentes conectados. También se inicializa un contador de ID que realiza un seguimiento de qué componente conectado etiqueta de cada una de estas tendrá.

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

      una. Si la ubicación es 0, marca este lugar ya visitado y continuar.

      b. Si ya hemos visitado este lugar, y luego continuar.

      c. Si no hemos visitado este lugar… vaya al Paso #3.

    3. Agregar este no visitados ubicación a una pila.

      una. Mientras esta pila no está vacía…

      b. Pop esta ubicación de la pila

      c. Si hemos visitado este lugar, y luego continuar.

      d. Otra cosa, la marca de este lugar ya visitado y que marca este lugar con los componentes conectados ID.

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

      f. Eliminar los píxeles en esta lista que han sido visitados, no es igual a 1 o fuera de los límites de la matriz

      g. Lo ubicaciones son restante, agregar a la pila.

    4. Una vez que la pila está vacía, incrementar el contador, a continuación, vaya al Paso #2.

    5. Seguir adelante hasta que hemos visitado todos los lugares en 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 ejemplo de la matriz, esto es lo que me pasa por 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 4-conectado barrio

    Para modificar el código para buscar en un 4-conectados de la región, que es sólo al Norte, Este, Oeste y Sur, la sección donde se ve %//Look at the 8 neighbouring locations, que es:

     %//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 en un 4-conectados de la moda, simplemente tienes que modificar este código para que sólo dan los 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 se mantiene intacta.

    Para que coincida con MATLAB de la bwlabel función

    Si quieres que coincida con la salida de MATLAB del bwlabel función, bwlabel busca de componentes conectados en la columna principal o FORTRAN orden. En el código anterior, busca en la fila principal o C de la orden. Por lo tanto, usted simplemente tiene que buscar a lo largo de las columnas primera vez de las filas como de lo que el código anterior está haciendo y usted puede hacer esto por cambiar el orden de los dos for bucles.

    Específicamente, en lugar de hacer:

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

    Que haría:

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

    Esta ahora debe replicar la salida de bwlabel.

    Su código es increíble, hace lo Que realmente quiere. Es un poco difícil de entender, pero lo tengo, eres un excelente programador, muchas gracias de nuevo.
    Buen código. Podría usted por favor decirme cómo mostrar todos los caminos en un grafo en las matrices. Por ejemplo : un camino se veía así : path_1 =[3,2,6,7,4,8,5];
    No tengo idea de lo que estás preguntando. Por favor me dan el resultado esperado con el ejemplo que he dado en mi respuesta anterior.

    OriginalEl autor rayryeng

Dejar respuesta

Please enter your comment!
Please enter your name here