Background:

I am making a program that detects the grid of a maze (

Question:

What methods would you suggest for a fix to this problem?

Note: I was thinking something like pattern detection to fill in the missing data?

CodePudding user response：

You could try implementing a Hough transform extraction. It's purpose is detecting distances between imperfect object classes - and with a little bit of tweaking you can make it extract/detect your maze grid.

A transform extraction can perform groupings of edge points into object candidates.

Here's the Wikipedia article, which gives in-depth explanations on how it works: https://en.wikipedia.org/wiki/Hough_transform#Detecting_lines

I hope this helps :)

CodePudding user response：

If your input maze is guaranteed to be based on a grid, like the images you show, then I would suggest a more deterministic approach.

It is probably sufficient to find one wall on each column. So instead of averaging all pixels in a column (which loses a lot of useful information), you can measure e.g. the longest consecutive list of black pixels. If this is much longer than the width of a wall, then you know it is the length of a wall and thus you know the column lies on a grid line.

When you have done this for all columns, you get a discrete graph instead and you can choose a value somewhere in the middle of each peak for the actual column line.

Some grid lines might not have vertical walls at all though, but you can easily interpolate these when you have found at least 3 grid lines.

Another approach would be performing some signal processing and find the period of your function, but I think simple interpolation would be easier to implement and understand.

CodePudding user response：

if I understand your approach correctly you are counting the "whiteness" or "blackness" over a row/column and want to use those distributions to determine the grid

what about extracting the grid lines like you planned to do, and measure them, to find a candidate value for the grid spacing sp(the whole procedure is the same for rows and columns and can be done independantly)

from there you can create a candidate grid with that spacing

now measure the candidate the same way you measured the source...

extract only the spikes in your graph as discrete values, do that for the source image s and the candidate grid c, we are are only interested in the coordinate axis, and we will have to offset said axis so one of their respective spikes match

now for each value x_s in your discrete value list for s, find the corresponding value x_c in c, with (x_s - sp/2) < x_c < (x_s sp/2)

if there's at least one x_s that has no x_c, consider the test a fail (abort criteria for later, or the sp candidate was way off)

once all x_s values have a corresponding x_c, calculate their difference and adjust sp with the mean difference and test the new candidate ...

we are looking for the biggest sp that passes the test, and since only smaller sp values could pass (think: if sp is the grid spacing, sp/(2^x) will also pass the test), you can test if sp*2 still passes or you can look at how many x_c values have no x_s value