Solving Image Maze $($With Solution$)$

Given a maze as an image with a start and end point, we would like to write code to solve the maze.

An image is a $2$D matrix of pixels of a particular size that depends on its resolution. Each pixel has a color which is given by its Red, Green and Blue $($RGB$)$ values.

Given an image, we will view it as a graph where each pixel of the image is a vertex and edges connect a pixel to its neighbor. The weight of an edge should be very small if the pixel colors are similar $($i$.$e$,$ the differences between $r,g$ and $b$ values are close to zero$)$ and correspondingly large as the pixel colors diverge.

Next, given a source pixel $(i_0,j_0)$ and destination pixel, $(i_1,j_1),$ we wish find the shortest weight path from source to destination.

You should use the Dijkstra's algorithm modified in two ways:

It can exit as soon as the destination is reached.

A $10001000$ pixel image gives rise to a graph with million vertices. Storing such a graph as an adjacency list is going to be very memory intensive. Instead, your goal will be to generate the vertices and edges on$-$the$-$fly.

We will use opencv library, a popular computer vision library to load, and manipulate images of mazes.

Manipulating Images

You can directly manipulate images in python in many ways. The opencv library is considered a standard for numerous image manipulation tasks.

Here we load an image maze.png and you can see it nicely plotted with coordinates. We then show you two pixels shown in red and blue. The goal here is to detect a path from one of the colored circle to the other, in the maze without crossing the black pixels.

In $[4]$: from matplotlib import pyplot as plt

import cv$2$

# You can read png$,$ jpg and other file types

img $=$ cv$2.$imread$(\text{'}$maze$.$png$\text{'})$ # read an image from a file using opencv $($cv$2)$ library

# you can annotate images

cv$2.$circle$($img$,(5,220),3,(255,0,0),-1$ # add a circle centered at $(5,220)$ radius $3,$ color red $($RGB: $255,0,)$

cv$2.$circle$($img$,(5,5),3,(0,0,255),-1$ # add a circle centered at $(5,5)$ radius $3,$ color red $(RGB$;$0,0,255)$

plt$.$imshow$($img$)$ # show the image on the screen

plt$.$title$(\text{'}$Amazing$\text{'})$

plt$.$show$()$

img $=$ cv$2.$imread$(\text{'}$maze$-$solution.png$\text{'})$ # read an image from a file using opencv $($cv$2)$ Library

# you can annotate images

cv$2.$circle$($img$,(5,220),3,(255,0,0),-1$ # add a circle centered at $(5,220)$ radius $3,$ color red $($RGB: $255,0,0$