Calculating the shortest path between two points in a bitmap in python

Question

I have a black and white bitmap image shown here:

The image size is 200,158.

I want to pick two points that fall on the white path and calculate the shortest distance between those two points following only the white pixels. I am not sure how to approach this problem. I want to create a function that I call with 2 sets of x,y coordinates and it returns the number of pixels following the shortest route along the white pixels only.

Any pointers would be greatly appreciated.

Answer 1

skimage.graph has an implementation of Dijkstra specifically for images, which solves your problem in just a couple lines:

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)

In this example, path will equal [(0, 0), (1, 1), (2, 2), (3, 3)] which is indeed the shortest path.

Answer 2

As stated in the comments, this problem can be reduced to Dijkstra.

The key concept behind the solution is to represent the image as a graph and then use a pre-made implementation of the shortest-path algorithm.

Firstly, observe a naive representation of an image of size 4x4:

T F F T
T T F T
F T T F
T T T T

Where T is a white dot and F is a black one. In this case, a path is a set of moves between adjacent white points.

Assuming a graph would be a set of nodes {1, 2, ..., 16}, we can map every point (i, j) to the number i * 4 + j. In the graph, the edges are a reflection of neighboring points, meaning that if (i1, j1) and (i2, j2) are adjacent in the image, then i1 * 4 + j1 and i2 * 4 + j2 are adjacent in the graph.

At this point, we have a graph on which we can compute the shortest path.

Luckily, python provides easy implementation to the image loading and to the shortest path implementation. The following code handles the path computation the visualizes the result:

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()

Disclaimer:

• I have no experience in image processing, so I'd suspect every step in the solution.
• The solution assumes a very naive adjacency-predicate. There're probably some better approaches in computetional geometry for this part.

Answer 3

I'm not a specialist of such algorithms, but at least I can help you by giving you some leads. I used to work on a similar project last year, at school. At the time, we were considering two algorithms : The Ant Colony Optimization Algorithm and Genetic Algorithms.

Ant Colony Optimization

Those algorithms are based off the behaviors of ants, when they try to find the easiest and shortest route to some food. More info here: https://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms.

Genetic Algorithms

They are more general and can be suited for a lot of problems. According to your situation, you might be interested in this paper.

I'm sorry that I can't provide you a more detailed help. I'm letting others answer, giving you that precious piece of advice you need. Good luck with your project, anyway!