Pastilla para hacerse invisible

Hoy al fin probé la famosa pastilla para hacerse invisible, es impresionante la rapidez con que hace efecto. Os dejo un video, haber si alguien puede explicarme cómo es que funciona esta revolucionaria mezcla de ingredientes exóticos.

Implementación de k-means en OpenCV

k-means o k-medias es un algoritmo de agrupamiento (clustering), lo que significa que es usado para dividir un conjunto de datos en grupos de tal forma que los datos pertenecientes a un grupo tengan propiedades en común. También se dice que este algoritmo es de aprendizaje no supervisado, pues es capaz de clasificar datos sin tener un supervisor que durante la etapa de entrenamiento le indique la clase a la que pertenece cada dato.
Se puede usar este algoritmo para segmentar una imagen por color, clasificando los pixeles que tienen colores parecidos en un mismo grupo.

k-means funciona de la siguiente manera:

• Elige aleatoriamente k centros (uno por cada grupo)
• Se etiqueta cada dato como perteneciente al grupo cuyo centro es más cercano
• Se calcula el centro promedio de cada grupo y se repite el paso anterior.
• El algoritmo se detiene cuando el promedio de cada centro de grupo no cambia o se alcanza el número máximo de iteraciones.

El centro de cada grupo y las distancias quedan definidos por el problema.
En el caso de las imagenes RGB se define el centro como una tripleta que contiene un valor para cada color:rojo, verde y azul. La distancia que se usará en este caso es la euclídea.
Sólo hay que imaginar los colores como una coordenada en el espacio 3D y la distancia entre dos puntos como el largo de la recta que los une.

El resultado del algoritmo dependerá de los centros iniciales, si estos son escogidos aleatoriamente probablemente se obtendrán resultados diferentes en cada ejecución.

OpenCV trae implementado este algoritmo, sin embargo yo programé mi propia implementación porque el algoritmo es sencillo y me pareció interesante hacerlo.
Un poco de código:

  //calculo de centroides y matriz de clasificacion
for(it=0; it < iterations;it++) {
    for(i=0;i<size;i++) {
        red[i] = 0;
        green[i] = 0;
        blue[i] = 0;
        count[i] = 0;
    }
    for(j=0; j < image->height; j++) {
        for(i=0; i < image->width; i++) {
            tcolor = getColor(image,i,j);            
            dist = distance(centroid[0], tcolor );
            label = 0;
            for(k=1; k<size; k++) {
                temp = distance(centroid[k], tcolor );
                if( temp < dist) {
                    dist = temp;
                    label = k;
                }
            }
            ++count[label];
            red[label]   += tcolor.r;
            green[label] += tcolor.g;
            blue[label]  += tcolor.b;
            if(it == (iterations-1)) {
                labeled[i][j] = (uchar)label;
            }
        }
    }
    //actualizar centroides
    for(i=0;i<size;i++) {
        if(count[i]==0) continue; //no actualizar centroide si no se hay colores que promediar
        centroid[i].r = (uchar)(red[i]/count[i]);
        centroid[i].g = (uchar)(green[i]/count[i]);
        centroid[i].b = (uchar)(blue[i]/count[i]);    
    }
                    
}
//dejar con color de centroide mas cercano a cada pixel de la imagen a mostrar
for(i=0; i < image->width; i++) {
    for(j=0; j < image->height; j++) {
        image2->imageData[j*image->widthStep + i*image->nChannels + 2] = centroid[labeled[i][j]].r;
        image2->imageData[j*image->widthStep + i*image->nChannels + 1] = centroid[labeled[i][j]].g;
        image2->imageData[j*image->widthStep + i*image->nChannels ] = centroid[labeled[i][j]].b;
    }
}

centroid[] : contiene un color por cada clase
size: cantidad de clases
labeled[][]: almacena los resultados de la clasificación, un número de 0 a (size-1) que relaciona cada pixel con su clase.
red[],green[],blue[],cout[]: variables usadas para calcular el color promedio

En el código anterior, dados los centroides de cada clase se procede a identificar cada pixel con la clase cuyo color se encuentre más cercano a su color.
Posteriormente se actualizan los centroides de cada clase, para ello se promedian los colores de los pixeles que fueron etiquetados como pertenecientes a la clase.
El proceso se repite hasta completar la cantidad de iteraciones especificada en la variable iterations.
Código fuente completo: kmeans-2010.tar.gz

Resultados al aplicar a la imagen superior izquierda el algoritmo con 5 clases y 90 iteraciones: