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:

martes, 5 de febrero de 2008

Filtro K-means (K-Medias)

Como ya hicimos hace muchisimo tiempo con el filtro Equalize, volvemos a presentar uno de los filtros que finalmente hemos decidido incorporar a nuestro proyecto gracias a sus buenos resultados en las pruebas, el filtro kmeans ( ó filtro de las k medias ).

La función del algoritmo kmeans es clusterizar la imagen en K grupos distintos, entiéndase por cluster: agrupación de elementos similares. El proceso de Clusterización (Clustering) consiste en la división de los datos en grupos de objetos similares (en nuestro caso particular esa similitud se hará entre los píxeles de la imagen). Para calcular la similitud entre píxeles se suele utilizar diferentes algoritmos de distancia: distancia euclídea, de Manhatan, de Mahalanobis, etc.

El nombre de kmeans (kmedias) viene porque representa cada uno de los clusters por la media (o media ponderada) de sus puntos, es decir, por su centroide. La representación mediante centroides tiene la ventaja de que tiene un significado gráfico y estadístico inmediato .

En el filtro kmeans aplicado en nuestro proyecto robótico agruparemos cada sector de la imagen en k cluster, para ello usaremos la imagen en color RGB y creamos tantos cluster distintos como le indiquemos al algoritmo (si indicamos solo un cluster todos los píxeles pertenecerán al mismo sector, con dos cluster el algoritmo agrupará los píxeles en dos grupos distintos, y así sucesivamente). Mediante este algoritmo perdemos gran cantidad de detalles en la imagen, pero simplificaremos el procesamiento de los misma.

Para comenzar el algoritmo inicializa los valores de las clases de manera que estos queden repartidos uniformente.

public void buscaValoresColor(int clases, int[]valoresR, int[]valoresG, int[]valoresB) {

int[] vectorR= new int [tamano/3];

int[] vectorG= new int [tamano/3];

int[] vectorB= new int [tamano/3];

int aux=1;

//guardamos los pixeles en distintos arrays de color

for (int k = 0; k < tamano/3; k++) {

aux= k*3;

vectorR[k] = imageRGB[aux];

vectorG[k] = imageRGB[aux+1];

vectorB[k] = imageRGB[aux+2];

}

//ordenamos de menor a mayor, solo ordenamos el array rojo, los otros, se ordenarán a partir del rojo

Arrays.sort (vectorR);

Arrays.sort (vectorG);

Arrays.sort (vectorB);

int longi = vectorR.length;

int sep = longi/clases;

int j=0;

int i=0;

//clasificación provisional de cluster

while (i <>

valoresR[j] = vectorR[i]; valoresG[j] = vectorG[i]; valoresB[j] = vectorB[i];

i = i + sep;

j++;

}

}


Una vez hecho esto nos guardamos los valores de los píxeles originales de la imagen, estos valores no se modificarán nunca en el algoritmo.

for (int k = 0; k < tamano/3; k++) {

aux= k*3;

valorPixelR[k] = imageRGB[aux];

valorPixelG[k] = imageRGB[aux+1];

valorPixelB[k] = imageRGB[aux+2];

}


Una vez hecho esto, comenzamos con el algoritmo de distancia mínima (algoritmo de distancia mínima euclídea) para saber a que clase pertenece cada píxel, haremos tantas iteraciones como sean necesarias para que cada píxel acabe agrupado en su clase mas cercana, la finalización de este proceso se hará cuando no haya variación entre un conjunto de clusteres y los obtenidos en la siguiente iteración.

do {

//examinamos cada pixel de la imagen y asignamos un cluster dependiendo de la distancia minima (euclidea)

for (int i=0; i

min_dif=1000;

for (int j=0;j

dif1=(double)Math.abs(valorPixelR[i] - valoresR[j]);

dif2=(double)Math.abs(valorPixelG[i] - valoresG[j]);

dif3=(double)Math.abs(valorPixelB[i] - valoresB[j]);

sumaPotencias=Math.pow(dif1, 2) + Math.pow(dif2, 2) + Math.pow(dif3, 2);

diferencia = (int)Math.sqrt(sumaPotencias);

if (diferencia <>

min_dif = diferencia;

min_clase = j;

}

}

cluster[i] = min_clase;

}

//guardamos valores de la ultima iteracion

int elems[] = new int[cjtos];

for (int i=0; i

valorAntR[i]=valoresR[i]; valorAntG[i]=valoresG[i]; valorAntB[i]=valoresB[i];

valoresR[i]=0; valoresG[i]=0; valoresB[i]=0;

elems[i]=0;

}

for (int j=0; j

valoresR[cluster[j]] += valorPixelR[j];

valoresG[cluster[j]] += valorPixelG[j];

valoresB[cluster[j]] += valorPixelB[j];

elems[cluster[j]]++;

}

//recalculamos el centroide de cada cluster

for (int j=0; j

if (elems[j]==0) {//it avoids that no class has 0 elements

Random alea = new Random(); //it chooses random coordinates

int x=alea.nextInt(w) ;

int y=alea.nextInt(h);

valoresR[j] = imageRGB[(y*w)+x];

valoresG[j] = imageRGB[(y*w)+x+1];

valoresB[j] = imageRGB[(y*w)+x+2];

elems[j]++;

}

else {

valoresR[j] /= elems[j];

valoresG[j] /= elems[j];

valoresB[j] /= elems[j];

}

//comprobamos si hubo cambios en esta iteracion

salir = true;

for (int i=0; i

if (valoresR[i]!=valorAntR[i]){

salir=false;

break;

}

}

} while (!salir);


Finalmente copiamos los valores calculados en una nueva imagen, en la cual al mostrarla por pantalla podemos ver los distintos cluster formados por el algoritmo.

Algoritmo kmeans con 2 cluster (K=2):
Algoritmo kmeans con 3 cluster (K=3):
Algoritmo kmeans con 4 cluster (K=4):
Algoritmo kmeans con 6 cluster (K=6):
Algoritmo kmeans con 8 cluster (K=8):
Algoritmo kmeans con 10 cluster (K=10):
Algoritmo kmeans con 20 cluster (K=20):