Ten en cuenta que en las ciencias cualquier problema casi siempre tiene diferentes resoluciones, pero aquí te compartiremos lo más óptimo y mejor.
Solución:
Como se indica en los comentarios, este problema se puede reducir a Dijkstra.
Él key El concepto detrás de la solución es representar la imagen como un gráfico y luego usar una implementación prefabricada del algoritmo de ruta más corta.
En primer lugar, observe una representación ingenua de una imagen de tamaño 4×4:
T F F T
T T F T
F T T F
T T T T
Donde T es un punto blanco y F es un negro En este caso, un camino es un conjunto de movimientos entre puntos blancos adyacentes.
Suponiendo que un gráfico sería un conjunto de nodos 1, 2, ..., 16podemos mapear cada punto (i, j) al número i * 4 + j. En el gráfico, los bordes son un reflejo de los puntos vecinos, lo que significa que si (i1, j1) y (i2, j2) son adyacentes en la imagen, entonces i1 * 4 + j1 y i2 * 4 + j2 son adyacentes en el gráfico.
En este punto, tenemos un gráfico en el que podemos calcular el camino más corto.
Afortunadamente, Python proporciona una implementación fácil para la carga de imágenes y para la implementación de la ruta más corta. El siguiente código maneja el cálculo de la ruta y visualiza el resultado:
import itertools
from scipy import misc
from scipy.sparse.dok import dok_matrix
from scipy.sparse.csgraph import dijkstra
# Load the image from disk as a numpy ndarray
original_img = misc.imread('path_t_image')
# Create a flat color image for graph building:
img = original_img[:, :, 0] + original_img[:, :, 1] + original_img[:, :, 2]
# Defines a translation from 2 coordinates to a single number
def to_index(y, x):
return y * img.shape[1] + x
# Defines a reversed translation from index to 2 coordinates
def to_coordinates(index):
return index / img.shape[1], index % img.shape[1]
# A sparse adjacency matrix.
# Two pixels are adjacent in the graph if both are painted.
adjacency = dok_matrix((img.shape[0] * img.shape[1],
img.shape[0] * img.shape[1]), dtype=bool)
# The following lines fills the adjacency matrix by
directions = list(itertools.product([0, 1, -1], [0, 1, -1]))
for i in range(1, img.shape[0] - 1):
for j in range(1, img.shape[1] - 1):
if not img[i, j]:
continue
for y_diff, x_diff in directions:
if img[i + y_diff, j + x_diff]:
adjacency[to_index(i, j),
to_index(i + y_diff, j + x_diff)] = True
# We chose two arbitrary points, which we know are connected
source = to_index(14, 47)
target = to_index(151, 122)
# Compute the shortest path between the source and all other points in the image
_, predecessors = dijkstra(adjacency, directed=False, indices=[source],
unweighted=True, return_predecessors=True)
# Constructs the path between source and target
pixel_index = target
pixels_path = []
while pixel_index != source:
pixels_path.append(pixel_index)
pixel_index = predecessors[0, pixel_index]
# The following code is just for debugging and it visualizes the chosen path
import matplotlib.pyplot as plt
for pixel_index in pixels_path:
i, j = to_coordinates(pixel_index)
original_img[i, j, 0] = original_img[i, j, 1] = 0
plt.imshow(original_img)
plt.show()
Descargo de responsabilidad:
- No tengo experiencia en el procesamiento de imágenes, por lo que sospecharía de cada paso de la solución.
- La solución asume un predicado de adyacencia muy ingenuo. Probablemente haya algunos enfoques mejores en geometría computacional para esta parte.
skimage.graph tiene una implementación de Dijkstra específicamente para imágenes, que resuelve su problema en solo un par de líneas:
import numpy as np
import skimage.graph
T,F = True,False
array = np.asarray(
[[T, F, F, T],
[T, T, F, T],
[F, T, T, F],
[T, T, T, T]])
costs = np.where(array, 1, 1000)
path, cost = skimage.graph.route_through_array(
costs, start=(0,0), end=(3,3), fully_connected=True)
En este ejemplo, path igualará [(0, 0), (1, 1), (2, 2), (3, 3)] que es de hecho el camino más corto.
Si guardas algún dilema o disposición de ascender nuestro artículo puedes ejecutar una interpretación y con gusto lo observaremos.