Python Learning Project: Dijkstra, OpenCV, and UI Algorithm (Part 1)

5 min


Labyrinths are a common puzzle for people, but they are an interesting programming problem that we can solve using shortest path methods such as Dijkstra’s algorithm.

Recall Dijkstra’s algorithm

Dijkstra’s algorithm is one of the most popular graph theory algorithms. It is used to find the shortest path between nodes on a directed graph. We start with the source node and the known edge lengths between the nodes.

First, we assign the distance value from the source to all nodes. The node s gets the value 0 because it is the source; the rest get ∞ values ​​to begin with.

image

Our node of interest is the raw node with the smallest value (shown in gray), i.e. s. First, we “weaken” each adjacent vertex to our node of interest, updating their values ​​to the minimum of their current value or the value of the node of interest plus the length of the connecting edge …

image

Node s is now complete (black), and its neighbors a and b have taken on new values. The new node of interest is b, so we repeat the process of “weakening” the neighboring nodes of b and finalizing the value of the shortest path for b.

image

After going through each node, we will end up with a graph showing the shortest path length from the source to each node.

image

image

image

Our final chart after running Dijkstra’s algorithm. The numbers at each node represent the shortest possible distance from the source node.

Conceptualization of maze images.

image

We can imagine the image as a matrix of pixels. Each pixel (for simplicity) has a value of RGB 0,0,0 (black) or 255,255,255 (white). Our goal is to create the shortest path that starts on white and does not go to black borders. To represent this goal, we can consider each pixel as a node and draw edges between adjacent pixels with edge lengths based on the difference in RGB values. We will use the Euclidean square distance formula and add 0.1 to ensure there is no path length of 0 – (requirement for Dijkstra’s algorithm):

image

This formula makes the intersection distance across the maze border excessively large. As we see, the shortest path from the source to the destination will clearly pass around the barrier, and not through it.

image

Implementation

We can use OpenCV, the popular Python vision library for Python, to extract pixel values ​​and display our maze images. Let’s also determine the coordinates of our start and end locations by adding points to our maze.

import cv2
import matplotlib.pyplot as plt
import numpy as np
img = cv2.imread('maze.png') # read an image from a file using
cv2.circle(img,(5,220), 3, (255,0,0), -1) # add a circle at (5, 220)
cv2.circle(img, (25,5), 3, (0,0,255), -1) # add a circle at (5,5)
plt.figure(figsize=(7,7))
plt.imshow(img) # show the image
plt.show()
image

We are creating a Vertex class that will help us track the coordinates. We also want to track the parent node so that we can restore the entire path as soon as we find the distance values.

class Vertex:
    def __init__(self,x_coord,y_coord):
        self.x=x_coord
        self.y=y_coord
        self.d=float('inf') #current distance from source node
        self.parent_x=None
        self.parent_y=None
        self.processed=False
        self.index_in_queue=None

We need to create a vertex matrix representing the two-dimensional arrangement of pixels in the image. This will be the basis for Dijkstra’s algorithm. We also maintain a queue with a minimum heap of priorities for tracking raw nodes.

def find_shortest_path(img,src,dst):
    pq=[] #min-heap priority queue
    imagerows,imagecols=img.shape[0],img.shape[1]
    matrix = np.full((imagerows, imagecols), None) 
    #access matrix elements by matrix[row][col]
    #fill matrix with vertices
    for r in range(imagerows):
        for c in range(imagecols):
            matrix[r][c]=Vertex(c,r)
            matrix[r][c].index_in_queue=len(pq)
            pq.append(matrix[r][c])
    #set source distance value to 0
    matrix[source_y][source_x].d=0
    #maintain min-heap invariant (minimum d Vertex at list index 0)
    pq = bubble_up(pq, matrix[source_y][source_x].index_in_queue)

We need some helper functions to help find the edges and the length of the edges between the vertices:

#Implement euclidean squared distance formula
def get_distance(img,u,v):
    return 0.1 + (float(img[v][0])-float(img[u][0]))**2+(float(img[v][1])-float(img[u][1]))**2+(float(img[v][2])-float(img[u][2]))**2
#Return neighbor directly above, below, right, and left
def get_neighbors(mat,r,c):
    shape=mat.shape
    neighbors=[]
    #ensure neighbors are within image boundaries
    if r > 0 and not mat[r-1][c].processed:
         neighbors.append(mat[r-1][c])
    if r < shape[0] - 1 and not mat[r+1][c].processed:
            neighbors.append(mat[r+1][c])
    if c > 0 and not mat[r][c-1].processed:
        neighbors.append(mat[r][c-1])
    if c < shape[1] - 1 and not mat[r][c+1].processed:
            neighbors.append(mat[r][c+1])
    return neighbors

Now we can implement Dijkstra’s algorithm and assign distance (d) values ​​to all the vertices of the pixels in the maze image:

while len(pq) > 0:
    u=pq[0] #smallest-value unprocessed node
    #remove node of interest from the queue
    pq[0]=pq[-1] 
    pq[0].index_in_queue=0
    pq.pop()
    pq=bubble_down(pq,0) #min-heap function, see source code 
    
    u.processed=True
    neighbors = get_neighbors(matrix,u.y,u.x)
    for v in neighbors:
        dist=get_distance(img,(u.y,u.x),(v.y,v.x))
        if u.d + dist < v.d:
            v.d = u.d+dist
            v.parent_x=u.x #keep track of the shortest path
            v.parent_y=u.y
            idx=v.index_in_queue
            pq=bubble_down(pq,idx) 
            pq=bubble_up(pq,idx)

Now we can call the shortest path function and draw a solution in our maze:

img = cv2.imread('maze.png') # read an image from a file using opencv (cv2) library
p = find_shortest_path(img, (25,5), (5,220))
drawPath(img,p)
plt.figure(figsize=(7,7))
plt.imshow(img) # show the image on the screen 
plt.show()

image

image

Let's try other mazes from all over the Internet.

image

image

image

image

Full source code available on github here.

image

Learn the details of how to get a sought-after profession from scratch or Level Up in skills and salary by taking paid SkillFactory online courses:


Read more

  • Trends in Data Scenсe 2020
  • Data Science is dead. Long live Business Science
  • The coolest Data Scientist does not waste time on statistics
  • How to Become a Data Scientist Without Online Courses
  • Sorting cheat sheet for Data Science
  • Data Science for the Humanities: What is Data
  • Steroid Data Scenario: Introducing Decision Intelligence

0 Comments

Leave a Reply