jueves, 7 de febrero de 2008

Filtro Blob

El algoritmo de blobs agrupa píxeles vecinos con las mismas características dentro de un mismo blob, formando así grupos de píxeles mas grandes dentro de la imagen.

El algoritmo de blobs se aplicará sobre una imagen ya binarizada con anterioridad.

El fin de la aplicación del algoritmo es buscar el blob que se ajuste más a nuestras necesidades: un blob con una forma determinada, que siga un parámetro de comportamiento determinado, etc, gracias al análisis de los blobs podemos obtener información del entorno y del objetivo al que Rabotron deberá seguir, así como su posible comportamiento en el futuro.

Vamos a pasar a la explicación del algoritmo:

El algoritmo es realmente sencillo, simplemente clasifica, como ya hemos dicho anteriormente, un píxel con respecto a sus vecinos creando los blobs (o grupos de objetos encontrados), por lo tanto recorremos la imagen píxel a píxel calculando un código de ponderación de cada píxel con respecto a sus vecinos y aplicando la función correspondiente según el resultado obtenido en dicho código.

Lo primero que haremos será crearnos una matriz cuadrada del tamaño de la imagen, para almacenar en ella el valor del blob al que pertenece cada pixel, por ejemplo (si la imagen fuese de 10x10 píxeles):

1

1

1

2

2

3

3

3

3

3

1

1

1

2

2

3

3

3

3

3

1

1

1

2

2

3

3

3

3

3

1

1

1

2

2

3

3

3

3

3

1

1

1

2

2

2

3

3

3

3

2

2

2

2

2

2

2

3

3

3

2

2

2

2

2

2

2

3

3

3

2

2

2

2

2

2

2

3

3

3

2

2

2

2

2

3

3

3

3

3

2

2

2

2

2

3

3

3

3

3

La ponderación aplicada a los vecinos será con una mascará de 2x2:

pixel * 1

pixel * 2

pixel * 4

Pixel examinado * 8

code = Pixel(x-1, y-1) + 2*Pixel(x, y-1) + 4*src.Pixel(x-1, y) + 8*Pixel(x, y)

Al utilizar una matriz de 2x2, los píxeles situados al borde de la imagen binarizada dejan elementos de la matriz fuera de la imagen. Para evitar esto, se rodea la imagen original con un borde de un píxel negro.

La ejecución comienza por el píxel que situado en la coordenada (1,1). Cuando examinamos cada píxel, dependiendo de si los píxeles de la máscara son blancos o negros, se obtendrán 16 códigos distintos:


A la derecha de cada cuadro se indica el tipo de operación que se aplicará cuando se encuentre una situación con el código indicado (a la izquierda):

- Operaciones de tipo I: indican operaciones donde se explora un punto negro, que se incorpora a los puntos del fondo de la imagen (no forma parte de ningún blob).

- Operaciones de tipo II: indican operaciones donde se explora un punto blanco, y alrededor no hay puntos blancos con quienes conectarlo, con lo que se iniciará en él un nuevo blob.

- Operaciones de tipo III: indican operaciones donde se explora un punto blanco, teniendo puntos blancos en alguna casilla de alrededor (P2, P3 o P4), con lo que se añadirá el nuevo punto blanco al blob que se hubiera formado previamente con estos.

- Operaciones de tipo IV: indica un caso particular de las operaciones de tipo III, donde el nuevo punto blanco detectado conecta dos blobs que antes se consideraban distintos. Lo que se hace es unir los dos blobs en uno solo, añadiendo a este nuevo blob el nuevo punto explorado.

El código java correspondiente a la clasificación del píxel examinado a un blob:

if(code<8)

regiones[x][y] = 0;

else if (code == 8 || code == 9) {

blob = new Blob();

blob.lista_x.add(x);

blob.lista_y.add(y);

lista_blobs.add(blob);

regiones[x][y] = lista_blobs.size();

}else if (code == 10 || code == 11 || code == 15) {

blob = (Blob) lista_blobs.get(regiones[x][y - 1] - 1);

blob.lista_x.add(x);

blob.lista_y.add(y);

regiones[x][y] = regiones[x][y - 1];

}else if (code == 12 || code == 13) {

blob = (Blob) lista_blobs.get(regiones[x - 1][y] - 1);

blob.lista_x.add(x);

blob.lista_y.add(y);

regiones[x][y] = regiones[x - 1][y];

} else if (code == 14) {

if (regiones[x][y - 1] != regiones[x - 1][y])

fusiona(regiones[x][y - 1], regiones[x - 1][y], regiones, lista_blobs);

blob = (Blob) lista_blobs.get(regiones[x][y - 1] - 1);

blob.lista_x.add(x);

blob.lista_y.add(y);

regiones[x][y] = regiones[x][y - 1];

}


Este proceso finalmente nos devuelve un listado de blobs de los que podemos extraer variar propiedades, entre la que destacaremos el uso del centroide.

Nos hemos creado una clase Blob, donde se almacenan los datos de cada blob en marticular, concretamente para cada blob tenemos almacenado:

- Lista de coordenada X de cada píxel perteneciente al blob --> lista_x
- Lista de coordenada Y de cada píxel perteneciente al blob --> lista_y
- Coordenada X del centroide del blob -->centro_x
- Coordenada Y del centroide del blob --> centro_y
- Variable boolena que indica si es un blob válido (si posee un número mínimo de píxeles) --> valido

La función fusiona(blob1, blob2, regiones, lista_de_blobs) junta dos bloques de píxeles pertenecientes a dos blob distintos en un mismo blob.

private void fusiona(int blob1, int blob2, int[][]regiones, ArrayList lista_blobs) {

Blob b1 = (Blob) lista_blobs.get(blob1 - 1);

Blob b2 = (Blob) lista_blobs.get(blob2 - 1);

int l2_length = b2.lista_x.size();

int[] l2x_array = b2.lista_x.toArray();

int[] l2y_array = b2.lista_y.toArray();

for (int i = 0; i <>

regiones[l2x_array[i]][l2y_array[i]] = blob1;

b1.lista_x.append(b2.lista_x);

b2.lista_x.free();

b1.lista_y.append(b2.lista_y);

b2.lista_y.free();

}


Como ejemplo de detección de blob vamos a poner una impresión de pantalla en la que pintamos (de verde) el blob mas grande detectado con el mismo color que existe justo en el punto central de la imagen.

Para este ejemplo de uso del algoritmo de detección de blob usamos como criterio para binarizar la imagen el color detectado en el punto central de la imagen, podemos observar como en la imagen binarizada aparecen varias zonas blancas distantes, gracias a la separación en blobs podemos ignorar las zonas que no nos interesan y quedarnos con el blob mas grande de la imagen (pintado de verde), que casualmente coincide con el blob central de la imagen en este caso.

Prueba 1:

Prueba 2: