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.gzResultados al aplicar a la imagen superior izquierda el algoritmo con 5 clases y 90 iteraciones:
