Read a grid from image Python
I need suggestions on reading a grid for maze generation purposes, i don't need code to generate a maze, all i need is a way to read an m x n grid from image and be able to iterate over cells and link/ unlink those cells. I already wrote some code that generates a grid using PIL, and i will be writing code to generate mazes using different algorithms.
Example:
Given a grid that will look like this and I need for example to modify cell 0, 0 and cell 0, 1 by linking them together by removing the wall | between them. Any suggestions on how to be able to modify the walls between cells in a method that might do something like the following:
def link_cells(cell1, cell2, grid):
"""Link 2 cells in a given image.
cell1: a tuple (row, column)
cell2: a tuple (row, column)
grid: an image object (full grid)
"""
# do ...
Note: I don't need an algorithm for maze generation, just something that enables the image processing part and i will work from there.
Here's a possible approach. Calculate the means of all the rows across the image into a single column wide vector as shown on the right in the diagram. Likewise calculate the means down all the columns into a single row high vector as shown across the bottom in the diagram:
Now threshold those two vectors, and then look for transition from white to black and from black to white. That will give you the start and end rows and columns of all the black lines in the image. You can now use those to overpaint in white the cell boundaries you want to erase. I overpainted in cyan and magenta so you can see what I am doing.
#!/usr/bin/env python3
import numpy as np
from PIL import Image
# Open image and make greyscale and Numpy versions
pimRGB = Image.open('grid.jpg')
pimgrey = pim.convert('L')
nimRGB = np.array(pimRGB)
nimgrey = np.array(pimgrey)
# Work out where the horizontal lines are
rowmeans = np.mean(nimgrey,axis=1)
rowthresh = np.where(rowmeans>128,255,0)
# Difference each element with its neighbour...
diffs = rowthresh[:-1] - rowthresh[1:]
rowStarts, rowEnds = [], []
for i,v in enumerate(diffs):
if v>0:
rowStarts.append(i)
if v<0:
rowEnds.append(i)
# Work out where the vertical lines are
colmeans = np.mean(nimgrey,axis=0)
colthresh = np.where(colmeans>128,255,0)
# Difference each element with its neighbour...
diffs = colthresh[:-1] - colthresh[1:]
colStarts, colEnds = [], []
for i,v in enumerate(diffs):
if v>0:
colStarts.append(i)
if v<0:
colEnds.append(i)
# Now all our initialisation is finished
# Colour in cyan the 2nd black row starting after the 3rd black col
r, c = 2, 3
nimRGB[rowStarts[r]:rowEnds[r],colEnds[c]:colStarts[c+1]] = [0,255,255]
# Colour in magenta the 8th black column starting after the 5th black row
r, c = 5, 8
nimRGB[rowEnds[r]:rowStarts[r+1],colStarts[c]:colEnds[c]] = [255,0,255]
# Convert Numpy array back to PIL Image and save
Image.fromarray(nimRGB).save('result.png')
For reference, colthresh looks like this:
array([255, 255, 255, 255, 255, 255, 255, 255, 255, 0, 0, 0, 0,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0, 0, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 0, 0, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 0, 0, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0, 0, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 0, 0, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 0, 0, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0, 0, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 0, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 0, 0, 0, 0, 255, 255, 255, 255, 255,
255, 255, 255, 255])
And diffs look like this:
array([ 0, 0, 0, 0, 0, 0, 0, 0, 255, 0, 0,
0, -255, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 255, 0, -255, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 255, 0, -255, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 255, 0, -255,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 0,
-255, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
255, 0, -255, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 255, 0, -255, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 255, 0, -255, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 255, -255, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 0,
0, 0, -255, 0, 0, 0, 0, 0, 0, 0, 0]
And colStarts looks like this:
[8, 48, 82, 118, 152, 187, 222, 256, 292, 328]
And colEnds looks like this:
[12, 50, 84, 120, 154, 189, 224, 258, 293, 332]