Etiquetado de componentes conectadas

Para reconocer los cuerpos que existen en las imágenes hay que diferenciar las regiones y esto se logra con la técnica de etiquetado de componentes conectadas en imágenes binarias y se asigna una etiqueta única a un subconjunto de puntos llamados comúnmente objetos.
La condición para que se pertenezca a cierta región es que el pixel en debe estar conectado con la región. La conectividad se refiere al hecho de que dos pixeles se encuentren unidos. La descripción de la imagen en términos de objetos permite simplificar su análisis y eficientizar el procesamiento de la misma. A continuación se ilustra el procedimiento con una serie de figuras y se explica brevemente su funcionamiento.

Primero, con la estructura creada de cinco localidad, como se muestra en la primer figura, se empieza barriendo la imagen de arriba hacia abajo y de izquierda a derecha, hasta que la parte roja de la estructura se encuentra con un pixel, mientras las demás localidades están obteniendo localidades en cero. El pixel encontrado de valor uno (como la imagen es binaria, solo existen dos valores, ceros y unos) se procede a cambiarle de valor a uno consecutivo, como sería el dos, ver la segunda figura.



Continuando con el barrido de izquierda a derecha, si la siguiente localidad es un pixel con valor uno, se procede a cambiar el valor a dos, que es el mismo valor con el que venía anteriormente.  Ver siguientes dos figuras:


El cambio de valor de etiquetado de los pixeles de 2 a 3, o de 3 a 4 o así sucesivamente va a ocurrir cuando, durante el barrido encuentra una localidad de valor cero, como se observa en la siguientes dos figuras.
Cuando la estructura va barriendo la imagen y en vez de ceros alrededor del pixel encontrado con valor uno, encuentra valores diferentes a cero o uno, como sucede en la figura 19. Donde encuentra un dos y un cinco en sus vecindades, procede a cambiar el valor de uno por el menor valor encontrado alrededor, que en este caso sería un dos, ver figura 20.

De esta manera continua a lo largo de la imagen y se tiene como resultado penúltima figura, en donde en un círculo rojo muestra problemas de reconocimiento de regiones. Para resolverlo, se tiene que iterar de nuevo el procedimiento, con un segundo o tercer barrido de la imagen, para llegar a la imagen de la última figura. Donde finalmente se tienen reconocidas las regiones de la imagen.


Si aplicáramos el algoritmo anterior, tendríamos regiones conectadas a través de elementos en diagonal. El  código que presentaremos aplica para reconocer cuerpos que no estén conectados con elementos en diagonal por lo que los reconocerá como objetos separados. De esta manera, la estructura que barre la imagen es modificada a solo dos vecindades, arriba y a la izquierda del elemento que principal, se muestra dicha explicación en el siguiente código.

  if((imagen[y][x] == 1)
         && (imagen[y-1][x]   == 0)
         && (imagen[y][x-1]   == 0)) {
      imagen[y][x] = cmbReg;
   }
Es como si tuviéramos una conectividad tipo 4. El método que tiene esta estructura se llama discriminaRegiones4, y mientras se recorre de izquierda a derecha la estructura también tiene que identificar las regiones con cero y el cambio a un valor diferente de cero, de esto se encarga el método incContDifCeros.   La variable cmbReg, indica un valor que va cambiando conforme cambian los valores de cero a mayor o igual que dos. De acuerdo a la quinta figura, se asigna el menor valor encontrado en la frontera, este procedimiento también se encuentra en el método discriminaRegiones4. Y se muestra el código:  

  if((imagen[y][x] == 1) 
         && (imagen[y-1][x]   == 0 || imagen[y-1][x]   <= cmbReg)
         && (imagen[y][x-1]   == 0 || imagen[y][x-1]   <=  cmbReg)) {
       vm[0] = imagen[y-1][x]   >= 2 ? imagen[y-1][x]   : 99999;
       vm[1] = imagen[y][x-1]   >= 2 ? imagen[y][x-1]   : 99999;
       imagen[y][x] = nMenor(vm);
   }


Ahora de acuerdo a la séptima figura, para ajustar los valores a un valor menor, lo resuelve el método: igualaRegiones4.  Se muestra el siguiente código que resuelve esta tarea.

for (int j = 0; j < height; j++) {
 for (int i = 0; i < width; i++) {
  if(imagen[j][i] > 0) {
   igMn[0] = imagen[j+1][i] >= 2 ? imagen[j+1][i] : 99999;
   igMn[1] = imagen[j][i-1] >= 2 ? imagen[j][i-1] : 99999;
   igMn[2] = imagen[j-1][i] >= 2 ? imagen[j-1][i] : 99999;
   igMn[3] = imagen[j][i+1] >= 2 ? imagen[j][i+1] : 99999;
   menor = nMenor(igMn);
   imagen[j+1][i]=imagen[j+1][i] >=
                  menor?menor:imagen[j+1][i];
   imagen[j][i-1]=imagen[j][i-1] >=
                  menor?menor:imagen[j][i-1];
   imagen[j-1][i]=imagen[j-1][i] >=
                  menor?menor:imagen[j-1][i];
   imagen[j][i+1]=imagen[j][i+1] >=
                  menor?menor:imagen[j][i+1];                  
  }
 }
}
Este procedimiento se itera dos o tres veces para garantizar la identificación de regiones. Esto se realiza en el método reconRegConect, además de que identifica los valores asociados a cada región en la imagen.  

 A continuación se muestran los métodos útiles para realizar el algoritmo comentado.

 String cad, ar0, ar1, tmp = "0";
    /*   2
     * 3 1  
     */

 public void discriminaRegiones4(int y, int x) {
   boolean rvc;
   int []vm = new int [2];
   if(enLimite(y, x)) {
       incContDifCeros(y, x);
   if((imagen[y][x] == 1)  
        && (imagen[y-1][x] == 0) 
        && (imagen[y][x-1] == 0)) {
            imagen[y][x] = cmbReg;
   }   
   if((imagen[y][x] == 1)  
        && (imagen[y-1][x] == 0 || imagen[y-1][x] <= cmbReg) 
        && (imagen[y][x-1] == 0 || imagen[y][x-1] <= cmbReg)) {
            vm[0]=imagen[y-1][x]>=2?imagen[y-1][x]:99999;
            vm[1]=imagen[y][x-1]>=2?imagen[y][x-1]:99999;
            imagen[y][x] = nMenor(vm);
   }
 }
}
    
private int nMenor(int []vec) {
   int menor = vec[0];
   for(int i = 1; i < vec.length; i++){
      if ( vec[i] < menor){
          menor = vec[i];
      }
   }
   return menor;
}

private void incContDifCeros (int y, int x) {
  cad = tmp;
  if(imagen[y][x] > 0) {
      ar1 = "1";
      cad += ar1;
      tmp = ar1;
  } 
  if(imagen[y][x] == 0) {
      ar0 = "0";
      cad += ar0;
      tmp = ar0;
  } 
  if(cad.equals("01")) {
       cmbReg++;
  }
  cad = "";
}


Para evaluar el programa se introduce la siguiente matriz:

{ {0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0},
  {0,  0,  0,  1,  1,  1,  0,  1,  1,  0,  0,  0},
  {0,  1,  1,  1,  1,  1,  0,  0,  0,  0,  0,  0},
  {0,  1,  1,  0,  1,  1,  0,  0,  0,  0,  0,  0},
  {0,  1,  1,  1,  1,  1,  0,  0,  0,  0,  1,  0},
  {0,  1,  1,  1,  1,  1,  0,  0,  0,  1,  1,  0},
  {0,  1,  1,  1,  0,  0,  0,  1,  1,  1,  1,  0},
  {0,  0,  0,  0,  1,  1,  0,  1,  1,  1,  1,  0},
  {0,  0,  0,  1,  1,  1,  0,  1,  1,  1,  1,  0},
  {0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0} };

El resultado es el siguiente:

   0   0   0   0   0   0   0   0   0   0   0   0
   0   0   0   2   2   2   0   3   3   0   0   0
   0   2   2   2   2   2   0   0   0   0   0   0
   0   2   2   0   2   2   0   0   0   0   0   0
   0   2   2   2   2   2   0   0   0   0   8   0
   0   2   2   2   2   2   0   0   0   8   8   0
   0   2   2   2   0   0   0   8   8   8   8   0
   0   0   0   0  13  13   0   8   8   8   8   0
   0   0   0  13  13  13   0   8   8   8   8   0
   0   0   0   0   0   0   0   0   0   0   0   0


Si te fue útil esta información, recuerda ponerme como referencia para tus trabajos o proyectos.


Referencias

·         Burger Wilhelm and Burge Mark, Digital Image Processing, Primera Edición, Editorial Springer, 2008.


Comentarios

Publicar un comentario

Entradas populares de este blog

Los diagramas de Voronoi y la triangulación Delaunay

Imagen
Los diagramas de Voronoi La mente humana a forjado un dominio espacial durante la evolución de su ser, para nosotros es importante comprender y delimitar áreas espaciales, ya sea para conocimiento de espacios territoriales, búsquedas más cortas de recursos e inclusive para la estética visual. Poco a poco se van mostrando una gran variedad de casos  de alcance limitado, pero conforme el paso del tiempo va llamando la atención de especialistas, da lugar a diversos estudios y aplicaciones hasta llegar a formar una área de investigación. Los diagramas de Voronoi (ver figura 1) nos ayudan a formar una descomposición ordenada de un espacio determinado y de acuerdo a un conjunto de elementos puntuales (sitios de Voronoi). Este concepto fue utilizado para dar una de las soluciones a la conjetura de Kepler sobre el empaquetamiento óptimo de esferas y Descartes lo emplea en el libro Principios de Filosofía publicado en 1644 para aplicar la teoría de vórtices al funcionamiento del uni...
Leer más

Códigos Cadena

Imagen
Una manera para encontrar los contornos, es utilizar el algoritmo de códigos de cadena. Los códigos de cadena tienen como objetivo  representar un contorno por medio de una sucesión conexa de segmentos de longitud y dirección especificadas. La conexión de los segmentos se lleva a cabo en entornos de 4 vecinos o de 8 vecinos. Cuando se usa un entorno de 4 vecinos tendremos cuatro orientaciones para los segmentos, como se muestra en la siguiente figura,  y utilizaremos los números 0,1,2 y 3 para especificar la  orientación de los segmentos. Si se usa un entorno de 8 vecinos tendremos 8 orientaciones  posibles (ver siguiente figura). El código de cadena genera una secuencia de números que representan las orientaciones de los segmentos conectados consecutivamente, partiendo de un punto del contorno y siguiendo el sentido de las agujas del reloj. Por ejemplo, la cadena 0033333323221211101101 representa el contorno  del objeto de la figura  posterior c...
Leer más