El algoritmo k-means aplicado a clasificación y procesamiento de imágenes¶
Clasificación¶
El aprendizaje de máquina (Machine Learning) estudia el aprendizaje automático a partir de datos (data-driven, gobernado por los datos) para conseguir hacer prediciones precisas a partir de observaciones con datos previos.
La clasificación automática de objetos o datos es uno de los objetivos del aprendizaje de máquina. Podemos considerar tres tipos de algoritmos:
Clasificación supervisada: disponemos de un conjunto de datos (por ejemplo, imágenes de letras escritas a mano) que vamos a llamar datos de entrenamiento y cada dato está asociado a una etiqueta (a qué letra corresponde cada imagen). Construímos un modelo en la fase de entrenamiento (training) utilizando dichas etiquetas, que nos dicen si una imagen está clasificada correcta o incorrectamente por el modelo. Una vez construído el modelo podemos utilizarlo para clasificar nuevos datos que, en esta fase, ya no necesitan etiqueta para su clasificación, aunque sí la necesitan para evaluar el porcentaje de objetos bien clasificados.
Clasificación no supervisada: los datos no tienen etiquetas (o no queremos utilizarlas) y estos se clasifican a partir de su estructura interna (propiedades, características).
Clasificación semisupervisada: algunos datos de entrenamiento tienen etiquetas, pero no todos. Este último caso es muy típico en clasificación de imágenes, donde es habitual disponer de muchas imágenes mayormente no etiquetadas. Estos se pueden considerar algoritmos supervisados que no necesitan todas las etiquetas de los datos de entrenamiento.
En esta práctica vamos a ver varios ejemplos de utilización del algoritmo de clasificación no supervisada k-means para la clasificación y procesamiento de imágenes.
El algoritmo k-means¶
K-means es un algoritmo de clasificación no supervisada (clusterización) que agrupa objetos en k grupos basándose en sus características. El agrupamiento se realiza minimizando la suma de distancias entre cada objeto y el centroide de su grupo o cluster. Se suele usar la distancia cuadrática.
El algoritmo consta de tres pasos:
- Inicialización: una vez escogido el número de grupos, k, se establecen k centroides en el espacio de los datos, por ejemplo, escogiéndolos aleatoriamente.
- Asignación objetos a los centroides: cada objeto de los datos es asignado a su centroide más cercano.
- Actualización centroides: se actualiza la posición del centroide de cada grupo tomando como nuevo centroide la posición del promedio de los objetos pertenecientes a dicho grupo.
Se repiten los pasos 2 y 3 hasta que los centroides no se mueven, o se mueven por debajo de una distancia umbral en cada paso.
El algoritmo k-means resuelve un problema de optimización, siendo la función a optimizar (minimizar) la suma de las distancias cuadráticas de cada objeto al centroide de su cluster.
Los objetos se representan con vectores reales de $d$ dimensiones $\left(\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{n}\right)$ y el algoritmo k-means construye $k$ grupos donde se minimiza la suma de distancias de los objetos, dentro de cada grupo $\mathbf{S}=\left\{ S_{1},S_{2},\ldots,S_{k}\right\}$, a su centroide. El problema se puede formular de la siguiente forma:
donde $\mathbf{S}$ es el conjunto de datos cuyos elementos son los objetos $\mathbf{x}_{j}$ representados por vectores, donde cada uno de sus elementos representa una característica o atributo. Tendremos $k$ grupos o clusters con su correspondiente centroide $\boldsymbol{\mu_{i}}$.
En cada actualización de los centroides, desde el punto de vista matemático, imponemos la condición necesaria de extremo a la función $E\left(\boldsymbol{\mu_{i}}\right)$ que, para la función cuadrática $(1)$ es
y se toma el promedio de los elementos de cada grupo como nuevo centroide.
Las principales ventajas del método k-means son que es un método sencillo y rápido. Pero es necesario decidir el valor de $k$ y el resultado final depende de la inicialización de los centroides. En principio no converge al mínimo global sino a un mínimo local.
Implementar el método k-means de forma que clasifique datos con dos dimensiones. Utilizarlo para clasificar en tres grupos los datos generados a continuación.
Generamos datos aleatorios 2D para tres clusters con la función
def genera_datos():
np.random.seed(7)
x1 = np.random.standard_normal((100,2))*0.6+np.ones((100,2))
x2 = np.random.standard_normal((100,2))*0.5-np.ones((100,2))
x3 = np.random.standard_normal((100,2))*0.4-2*np.ones((100,2))+5
X = np.concatenate((x1,x2,x3),axis=0)
return X
Generamos los $k=3$ centroides iniciales en $[0,1]\times [0,1]$ con la función
def genera_centroides(X,k):
cx = np.random.rand(k)
cy = np.random.rand(k)
centroides = np.zeros((k,2))
centroides[:,0] = cx
centroides[:,1] = cy
return centroides
Si queremos escalar un valor $x$ de $[0,1]$ a $[a,b]$
$$x_s = a + (b-a)\,x$$(a) Modificar la función anterior de forma que los valores cx estén entre el máximo y el mínimo valor de la primera coordenada de X. Y los valores cy estén entre el máximo y el mínimo valor de la segunda coordenada de X.
Nota np.min(v) y np.max(v) dan el mínimo y el máximo valor del vector unidimensional v.
(b) Escribir una función asigna_centroide(x,centroides) que, dado el valor de un punto de los datos (una fila de X) devuelve en l la fila del centroide más cercano. Usar la distancia euclídea.
(c) Escribe la función recoloca_centroides(X,etiquetas,centroides) que recalcula los centroides como el valor medio de las X cuya etiqueta se corresponda con la etiqueta del centroide.
(d) Escribir la función kmeans(k) que devuelva las etiquetas y centroides y que llamando a las funciones adecuadas:
- Genere los datos.
- Genere los centroides.
- Inicialice el array unidimensional
etiquetas, con tantos elementos como puntos enXcon 9. - Dibuje los datos con los centroides ininciales.
- Asigne los centroides a los puntos y dibuje los clústeres.
- Recoloque los centroides y vuelva a dibujar.
Repetir los pasos 5 y 6 ocho veces.
Dibujar los datos y los centroides usando la función.
def plot(X,etiquetas,centroides,s):
plt.figure()
plt.plot(X[etiquetas==9,0],X[etiquetas==9,1],'k.')
plt.plot(X[etiquetas==0,0],X[etiquetas==0,1],'r.', label='cluster 1')
plt.plot(X[etiquetas==1,0],X[etiquetas==1,1],'b.', label='cluster 2')
plt.plot(X[etiquetas==2,0],X[etiquetas==2,1],'g.', label='cluster 3')
plt.plot(centroides[:,0],centroides[:,1],'mo',markersize=8, label='centroids')
plt.legend()
plt.title(s)
plt.show()
%run Ejercicio1.py
import numpy as np
import matplotlib.pyplot as plt
En los demás ejercicios de esta práctica vamos a usar la función KMeans de la librería sklearn.
from sklearn.cluster import KMeans
Agrupamos los puntos con k-means usando $k=3$
n = 3
X = genera_datos()
k_means = KMeans(n_clusters=n)
model = k_means.fit(X)
El resultado son tres centroides en torno a los cuales se agrupan los puntos y las etiquetas para cada punto que indican a qué cluster pertenece dicho punto
centroides = k_means.cluster_centers_
etiquetas = k_means.labels_
Dibujamos ahora los puntos y los centroides, utilizando un color distinto para los puntos de cada cluster
plt.plot(X[etiquetas==0,0],X[etiquetas==0,1],'r.', label='cluster 1')
plt.plot(X[etiquetas==1,0],X[etiquetas==1,1],'g.', label='cluster 2')
plt.plot(X[etiquetas==2,0],X[etiquetas==2,1],'b.', label='cluster 3')
plt.plot(centroides[:,0],centroides[:,1],'mo',markersize=8, label='centroides')
plt.legend(loc='best')
plt.show()
Clasificación de dígitos con k-means¶
Vamos a clasificar dígitos de la base de datos contenida en la librería sklearn de python utilizando el algoritmo k-means.
Comenzamos cargando las librerías que vamos a usar:
las habituales
import numpy as np
import matplotlib.pyplot as plt
las que contienen las funciones del método k-means
from sklearn.cluster import KMeans
y para cargar las imágenes de los dígitos
from sklearn.datasets import load_digits
Cargamos los datos, que están incluídos en la librería sklearn
digits = load_digits()
data = digits.data
Quitamos las últimas columnas de la matriz de datos, que contienen las etiquetas, que no vamos a usar en este ejemplo
data = data[:,0:64]
En la matriz data, cada fila se corresponde con la imagen de un dígito. Los píxeles de la imagen rectangular de $8\times 8$ píxeles se han recolocado en una fila de $64$ elementos. Por lo tanto, cada fila es un objeto o dato. Las características o propiedades de cada objeto son las intensidades de gris de cada pixel. Es decir, tenemos, para cada imagen, $64$ propiedades.
Para visualizar mejor los dígitos, vamos a invertir los colores
data = 255-data
Fijamos la semilla para sortear los centroides iniciales, para que los resultados obtenidos aquí sean repetibles
np.random.seed(1)
Como tenemos 10 dígitos diferentes (del 0 al 9) escogemos agrupar las imágenes en $10$ clusters
n = 10
Clasificamos los datos utilizando k-means
kmeans = KMeans(n_clusters=n,init='random')
model = kmeans.fit(data)
Z = kmeans.predict(data)
Dibujamos los clusters resultantes
for i in range(0,n):
fila = np.where(Z==i)[0] # filas en Z donde están las imagenes de cada cluster
num = fila.shape[0] # numero imagenes de cada cluster
r = int(np.floor(num/10.)) # numero de filas menos 1 en figura de salida
print("cluster "+str(i))
print(str(num)+" elementos")
plt.figure(figsize=(10,10))
for k in range(0, num):
plt.subplot(r+1, 10, k+1)
imagen = data[fila[k], ]
imagen = imagen.reshape(8, 8)
plt.imshow(imagen, cmap=plt.cm.gray)
plt.axis('off')
plt.show()
Cuantificación de imágenes con k-means¶
Cuantificación es una técnica de compresión con pérdida que consiste en agrupar todo un rango de valores en uno solo. Si cuantificamos el color de una imagen, reducimos el número de colores necesarios para representarla y el tamaño del fichero de la misma disminuye. Esto es importante, por ejemplo, para representar una imagen en dispositivos que sólo dan soporte a un número limitado de colores.
Vamos a cuantificar el color de la imagen siguiente utilizando k-means.
Ahora importamos la librería OpenCV
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
import cv2 as cv
Cargamos la imagen
I = cv.imread("tienda.jpg")
Es una imagen BGR. Intercambiamos los canale R y B para obtener una imagen RGB
I = cv.cvtColor(I, cv.COLOR_BGR2RGB)
La transformamos en una matriz numpy y la visualizamos
a = np.asarray(I,dtype=np.float32)/255
plt.figure(figsize=(12,12))
plt.imshow(a)
plt.axis('off')
plt.show()
En este caso nuestros objetos son los pixeles y sus características son las intensidades de rojo, verde y azul asociada a cada uno. Por lo tanto tenemos tantos datos u objetos como píxeles y tres características o propiedades para cada píxel. Tendremos tantos colores distintos como ternas RGB diferentes. Contamos el número de colores distintos
Primero obtenemos el número de filas, columnas y canales de a.. El primero nos dará la altura en píxeles de la imagen h y el segundo la anchura w.
El número de píxeles de la imagen es w*h
h, w, c = a.shape
print('w =', w)
print('h =', h)
print('c =', c)
num_pixels = w*h
print ('Número de pixels = ', num_pixels)
Creamos un array con tantas filas como píxeles y por cada fila/pixel, 3 columnas, una para cada intesidad de color (rojo, verde y azul)
a1 = a.reshape(w*h, c)
print('filas, columnas y canales de a ', a.shape)
print('filas y columnas de a1', a1.shape)
Ahora contamos el número de colores en la imagen
colores = np.unique(a1, axis=0, return_counts=True)
print(colores)
num_colores = colores[0].shape[0]
print ('\nNúmero de colores = ', num_colores)
Para poder aplicar k-means necesitamos una matriz con tantas filas como píxeles y para cada fila/pixel 3 columnas, una para cada intensidad de color (rojo, verde y azul). Reorganizamos los elementos de la matriz en otra matriz de esas características.
Agruparemos los 172388 colores en 60 grupos o nuevos colores, que se corresponderán con los centroides obtenidos con el k-means
n = 60
k_means = KMeans(n_clusters=n)
model = k_means.fit(a1)
Los centroides finales son los nuevos colores y cada pixel tiene ahora una etiqueta que dice a qué grupo o cluster pertenece
centroides = k_means.cluster_centers_
etiquetas = k_means.labels_
print('dimensiones centroides ', centroides.shape)
print('dimensiones etiquetas ', etiquetas.shape)
A partir de las etiquetas y los colores (intensidades de rojo, verde y azul) de los centroides reconstruimos la matriz de la imagen utilizando únicamente los colores de los centroides.
a2k = centroides[etiquetas]
print('Dimensiones matriz a2k ', a2k.shape)
a3k = a2k.reshape(h,w,c)
print('Dimensiones matriz a3k ', a3k.shape)
Representamos la imagen con 60 colores
plt.figure(figsize=(12,12))
plt.imshow(a3k)
plt.axis('off')
plt.show()
Guardamos ahora la imagen en formato jpg
a4k = np.floor(a3k*255)
a5k = a4k.astype(np.uint8)
Es una imagen RGB. Intercambiamos los canales R y B para tener una imagen BGR
red = np.copy(a5k[:,:,0])
blue = np.copy(a5k[:,:,2])
a5k[:,:,0] = blue
a5k[:,:,2] = red
Guardamos la imagen en formato jpg
Ik = cv.imwrite("tienda2.jpg",a5k)
El número de píxeles es el de la foto inicial, y el número de colores de esta imagen es igual al número de centroides.
coloresk = np.unique(a2k, axis=0, return_counts=True)
num_coloresk = coloresk[0].shape[0]
num_pixelsk = a2k.shape[0]
print('Número de píxeles = ',num_pixelsk )
print('Número de colores = ', num_coloresk)
Contar el número de colores en la imagen siguiente, holi.jpg. A partir de ella crear una imagen donde el número de colores se ha reducido a diez utilizando el método k-means.
Crear una imagen $1000\times1000$ que contenga la paleta de colores de la imagen obtenida, donde cada color aparezca en una banda horizontal de $100$ pixels.
Ordenar los colores por distancia (la distancia euclidea de un color al siguiente es la menor posible) y volver a dibujar la paleta. Guardar la imagen en un fichero que se llame gama.jpg.
Nota
- Inicializar la matriz de la paleta de colores como
gama = np.zeros((1000,1000,3)).
%run Ejercicio2.py
Obtener la tercera imagen a partir de la primera imagen (che-guevara.jpg) que se muestra a continuación.
%run Ejercicio3.py
Segmentación de imágenes con k-means¶
La segmentación divide una imagen en regiones con propiedades internas coherentes. Se puede segmentar una imagen utilizando el color.
El proceso es similar al de cuantización de imágenes. La diferencia es el objetivo con el que se agrupan los píxeles: agrupamos los píxeles para separar los elementos significativos de una imagen y así poder extraer cierta información de alguno de ellos. Por ejemplo, calcular el tamaño de un tumor a partir de imágenes médicas, el porcentaje de mica en una roca granítica, el área de un lago a partir de una foto aérea.
Comencemos con este último ejemplo. Si tenemos la siguiente imagen tomada desde un satélite del lago Victoria y el área que cubre es aproximadamente 200000 km$^2$, podemos calcular, a partir del porcentaje del área de la imagen, el área del lago.
I = cv.imread("Lago_Victoria.jpg")
I1 = cv.cvtColor(I, cv.COLOR_BGR2RGB)
plt.figure(figsize=(8,8))
plt.imshow(I1)
plt.axis('off')
plt.show()
Para simplificar el problema, convertimos la imagen de color a blanco y negro
I2 = cv.cvtColor(I, cv.COLOR_BGR2GRAY)
a = np.asarray(I2,dtype=np.float32)
plt.figure(figsize=(8,8))
plt.imshow(a,cmap='gray')
plt.axis('off')
plt.show()
Preparamos la matriz para aplicar k-means. Ahora tendrá tantas filas como píxeles pero sólo una columna, la intensidad de gris.
x , y = a.shape
print('Dimensiones de a ', a.shape)
a1 = a.reshape(x*y,1)
print('Dimensiones de a1 ', a1.shape)
Agrupamos los píxeles en tres clusteres con k-means
k_means = KMeans(n_clusters=3)
modelo = k_means.fit(a1)
Extraemos el valor de los centroides y las etiquetas de cada pixel
centroides = k_means.cluster_centers_
etiquetas = k_means.labels_
Reconstruimos la imagen utilizando las tres intensidades de los centroides
a2 = centroides[etiquetas]
print('Dimensiones de a2 ', a2.shape)
a3 = a2.reshape(x, y)
print('Dimensiones de a3 ', a3.shape)
Visualizamos la foto reconstruida
plt.figure(figsize=(8,8))
plt.imshow(a3,cmap='gray')
plt.axis('off')
plt.show()
Contamos el número de píxeles de color negro (los de intensidad de gris más baja)
a4 = (a3 - np.min(a3))/(np.max(a3)-np.min(a3))*255
a5 = a4.astype(np.uint8)
Contamos el número de píxeles negros (los de intensidad más baja)
colores = np.unique(a5, return_counts=True)
print(colores)
Tenemos
print(colores[1][0], 'píxeles para la intensidad',colores[0][0],', es decir, negro')
print(colores[1][1], 'píxeles para la intensidad',colores[0][1],', es decir, gris')
print(colores[1][2], 'píxeles para la intensidad',colores[0][2],', es decir, blanco')
Calculamos el porcentaje respecto al número total de píxeles de la foto y tenemos el porcentaje del área del lago respecto al área total representada por la foto
print('Área = ', float(200000)*float(colores[1][0])/float(w*h), 'km2')
Calcular el porcentaje de mica (es el mineral de color más oscuro) en la roca de granito cuya sección muestra la foto. Ejecutar 10 veces la función k-means y quedarse con la iteración que dé menor error siendo error = k_means.inertia_.
%run Ejercicio4
