GIIT_AMA_1718_T2_Tutorial 4 (opcional)

594 days ago by GIIT_AMA_1718

Tutorial 4 (Opcional)

Obteniendo un grafo a partir de un mapa

En esta práctica, generaremos un grafo a partir de las calles de una ciudad, tratando que el grafo recoja lo máximo posible la configuración de las calles, pero con pocos vértices. Partiremos de un mapa sin etiquetas (los puedes obtener aquí o aquí). Capturamos la zona que nos interese y la subimos a "Datos..." como archivo png. Como ejemplo, está subido un mapa de Mérida.

import matplotlib.image as mpimg img=mpimg.imread(DATA+'Merida.png') matrix_plot(img) 
       

Como las carreteras están en blanco, nos quedaremos sólo con esa información. Para ello, marcamos los píxeles que estén en blanco con 1 y con 0 los que no tengan el color blanco. Podemos hacerlo, por ejemplo, sumando los canales r, g, b de la imagen y pidiendo que la intensidad resultante esté por encima de un valor.

img_bn=(img[:,:,0]+img[:,:,1]+img[:,:,2])>2.65 matrix_plot(img_bn) 
       

Queremos restringir el número de vértices del grafo a los más interesantes. Vamos a intentar quedarnos con los cruces. Necesitamos, de algún modo, poder distinguir los cruces del resto de puntos del camino. Como en los cruces confluyen varios caminos, la manera de identificarlos es porque el punto central tendrá más puntos blancos alrededor que los puntos que no sean cruces. En particular, si para cada punto blanco sumamos los píxeles vecinos, el centro del cruce será un máximo local (los puntos cercanos tendrán menos vecinos blancos que el centro del cruce).

Para calcular esto rápidamente usamos el siguiente "truco": difuminamos la imagen mediante un desenfoque gaussiano, de ese modo, el color blanco se tranforma en un valor entre 0 y 1 de modo que será más cercano a 1 cuantos más píxeles blancos tenga alrededor.

from scipy import ndimage as ndi distance = ndi.gaussian_filter(img_bn*1.0, sigma=(2.5, 2.5)) matrix_plot(distance) 
       

Y ahora nos basta tomar los máximos locales de la imagen. Estos serán los vértices de nuestro grafo.

data_max = ndi.filters.maximum_filter(distance,size=(5,5)) # size marca el entorno donde buscaremos los máximos local_maxi=(distance==data_max)*(img_bn)*1.0 # Sólo queremos los máximos que se correspondan a caminos matrix_plot(local_maxi) 
       

Ahora necesitamos las aristas. Queremos ver cuáles de los vértices anteriores son adyacentes, es decir, existe una calle que va de uno a otro. Para ello usaremos el algoritmo watershed. Este algoritmo funciona del siguiente modo:

  1. Consideramos la imagen (en blanco y negro). La pensaremos como un grafo, siendo los vértices los píxeles con el valor 1 y las aristas unen cada pixel con los 8 vecinos.
  2. Elegimos un subconjunto de los vértices (marcadores). Cada uno de estos vértices lo marcamos con una etiqueta distinta.
  3. Para cada vértice marcado con una etiqueta e, obtenemos los vértices vecinos que no estén marcados y los marcamos con la etiqueta e.
  4. Repetimos 3 hasta completar el grafo.

El resultado es que cada vértices/pixel en blanco de la imagen en blanco y negro queda marcado con la etiqueda del marcador más cercano.

from skimage.morphology import watershed markers = ndi.label(local_maxi)[0] labels = watershed(-distance, markers, mask=img_bn) matrix_plot(labels,cmap='jet') 
       

Por último vamos a construir el grafo. Creamos una función para ello, que recibirá los marcadores (que serán los vértices) y las etiquetas que ha generado el algoritmo de watershed. La función recorrerá la imagen y en una primera pasada obtendrá los marcadores y los añadirá como vértices. Después, recorre el conjunto de etiquetas del algoritmo watershed y cada vez que hay dos píxeles adyacentes con etiquetas distintas (en cualquiera de las 8 posiciones que rodean cada pixel) añade una arista entre los dos marcadores correspondientes a esas etiquetas.

def mapa_grafo(markers,labels): # Creamos un grafo vacío g=Graph({}) m,n=markers.shape posiciones={} # Recorremos el mapa for j in range(m): # para cada fila for i in range(n): # para cada columna if markers[j,i]!=0: g.add_vertex((j,i)) posiciones[markers[j,i]]=(j,i) for j in range(m): # para cada fila for i in range(n): # para cada columna # Si hay calle en la posición superior, los unimos con una arista if j>0 and labels[j-1,i]!=0 and labels[j,i]!=0 and labels[j-1,i]!=labels[j,i]: g.add_edge(posiciones[labels[j,i]],posiciones[labels[j-1,i]]) # Si hay calle a la izquierda, los unimos con una arista if i>0 and labels[j,i-1]!=0 and labels[j,i]!=0 and labels[j,i-1]!=labels[j,i]: g.add_edge(posiciones[labels[j,i]],posiciones[labels[j,i-1]]) # Si hay calle en la posición superior izquierda, los unimos con una arista if j>0 and i>0 and labels[j-1,i-1]!=0 and labels[j,i]!=0 and labels[j-1,i-1]!=labels[j,i]: g.add_edge(posiciones[labels[j,i]],posiciones[labels[j-1,i-1]]) # Si hay calle en la posición superior derecha, los unimos con una arista if j>0 and i+1<n and labels[j-1,i+1]!=0 and labels[j,i]!=0 and labels[j-1,i+1]!=labels[j,i]: g.add_edge(posiciones[labels[j,i]],posiciones[labels[j-1,i+1]]) # Borramos los vértices que nos hayan quedado sueltos for v in g: gn=g.neighbors(v) if len(gn)==0: g.delete_vertex(v) for u,v,_ in g.edge_iterator(): g.set_edge_label(u,v,sqrt((u[0]-v[0])^2+(u[1]-v[1])^2)) g.set_pos({k:(k[1],k[0]) for k in g.vertices()}) return g 
       

Dibujamos el grafo obtenido sobre el mapa de partida. Nótese que tiene algunos errores, en particular en los bordes del mapa y en las calles curvas. Estos errores se pueden corregir introduciendo filtros adicionales, siendo más conservador a la hora de definir los máximos locales o eligiendo un método distinto. Pero para una primera aproximación al problema, el método usado da una solución aceptable, con un conjunto de vértices bastante pequeño.

Nótese que, al hacerlo con bucles, este proceso es bastante lento. Sin embargo, se podría optimizar para que fuese tan rápido como los procesos anteriores.

G=mapa_grafo(markers,labels) matrix_plot(img)+G.plot(vertex_labels=false,vertex_size=10) 
       

Practica

1. Carga un mapa en DATA y prueba hacer el mismo proceso. Quizás tengas que jugar con los parámetros del desenfoque y del cálculo de máximos locales.

2. Elige un vértice en el centro del grafo. Calcula su componente conexa y represéntala en otro color.

3. ¿En qué vértice colocarías una estación de bomberos? ¿Y si tuvieses que colocar dos estaciones de bomberos?