如何找出迷宫图片的出入口位置 [英] How to find out the locations of entry and exit from a maze picture

问题描述

想知道是否可以找出图片中迷宫的出入口吗?

Just wondering is it possible to find out the entry and exit points of a maze in a picture?

为了便于说明，我用红色和蓝色突出显示了这两个点，但是它们并不存在于原始图片中，所以请不要指望它们.

I have highlighted the 2 points with red and blue for explaining purpose, but they do not exist in the original picture, so please don't count on them.

入口和出口的位置可以变化，例如它们可以位于边缘的中间，但不仅限于拐角或中间的位置.

The locations of the entry and exit can be vary, e.g. they could be in the middle of an edge, but not limited to the locations which are the corner or the middle.

我注意到有2个黑色箭头指向2个位置，但是如何在没有这2个箭头的帮助下找到2个位置?

I notice that there are 2 black arrows pointing to the 2 locations, but how to locate the 2 locations without the help of these 2 arrows?

我应该在这里上传经过处理的图像:

I should upload the processed image here:

应用一些图像处理程序后，我得到了提取的迷宫.但这不是我要问的，让我们回到主题，提取的迷宫图像应该是这个问题的起点.

After applied some image processing procedures, I have gotten the extracted maze. But this is not what I am asking, let's get back to the topic and the extracted maze image should be the starting point for this question.

推荐答案

我从提取的迷宫图像开始.首先要做的是找到迷宫的四个角.我们可以通过只寻找四个最极端(最接近图像拐角)的点来找到它们.我们可以将这四个角连接起来，以形成一个包围迷宫的(某种)矩形.

I started with your extracted maze image. The first thing to do is to find the four corners of the maze. We can find them by just looking for the four most extreme (closest to the corner of the image) points. We can connect up these four corners to make a (sort of) rectangle that encloses our maze.

这个想法是找到与矩形矩形边缘垂直的最长的非占用(白色)点线.为了简化数学运算，因为我们知道四个角，所以我们可以校正图像.

The idea is to find the longest line of non-occupied (white) points that is perpendicular to the edges of our rectangle. To simplify the math for this we can rectify the image since we know the four corners.

穿过边缘并射线投射".直到碰到墙，这是一些沿着每个边缘找到的每条线的长度的图形.

Running through the edges and "raycasting" until we hit a wall, here are some graphs of the length of each line found along each edge.

上边缘

左边缘

底边缘

右边缘

现在我们可以找到每个边缘的最长线，取最高的两条线，这些就是我们进入迷宫的入口.

Now we can just find the longest line for each edge, take the highest two, and those are our entrances to the maze.

import cv2
import numpy as np
import matplotlib.pyplot as plt

# tuplifies a point for opencv
def tup(p):
    return (int(p[0]), int(p[1]));

# load image
img = cv2.imread("maze.png");

# resize
scale = 0.5;
h, w = img.shape[:2];
h = int(h*scale);
w = int(w*scale);
img = cv2.resize(img, (w,h));
copy = np.copy(img);

# mask image
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY);
mask = cv2.inRange(gray, 100, 255);

# find corners
corners = [[[0,0], 0] for a in range(4)];
for y in range(h):
    # progress check
    print(str(y) + " of " + str(h));
    for x in range(w):
        # check pixel
        if mask[y][x] == 0:
            # scores
            scores = [];
            scores.append((h - y) + (w - x)); # top-left
            scores.append((h - y) + x); # top-right
            scores.append(y + x); # bottom-right
            scores.append(y + (w - x)); # bottom-left
            
            # check corners
            for a in range(len(scores)):
                if scores[a] > corners[a][1]:
                    corners[a][1] = scores[a];
                    corners[a][0] = [x, y];

# draw connecting lines
for a in range(len(corners)):
    prev = corners[a-1][0];
    curr = corners[a][0];
    cv2.line(img, tup(prev), tup(curr), (0,200,0), 2);

# draw corners
for corner in corners:
    cv2.circle(img, tup(corner[0]), 4, (255,255,0), -1);

# re-orient to make the math easier
rectify = np.array([[0,0], [w,0], [w,h], [0,h]]);
numped_corners = [corner[0] for corner in corners];
numped_corners = np.array(numped_corners);
hmat, _ = cv2.findHomography(numped_corners, rectify);
rect = cv2.warpPerspective(copy, hmat, (w,h));

# redo mask
gray = cv2.cvtColor(rect, cv2.COLOR_BGR2GRAY);
mask = cv2.inRange(gray, 100, 255); 

# dilate
kernel = np.ones((3,3), np.uint8);
mask = cv2.erode(mask, kernel, iterations = 5);

# find entrances
top = []; # [score, point]
# top side
for x in range(w):
    y = 0;
    while mask[y][x] == 255:
        y += 1;
    top.append([y, [x,0]]);
# left side
left = [];
for y in range(h):
    x = 0;
    while mask[y][x] == 255:
        x += 1;
    left.append([x, [0,y]]);
# bottom side
bottom = [];
for x in range(w):
    y = h-1;
    while mask[y][x] == 255:
        y -= 1;
    bottom.append([(h - y) - 1, [x, h-1]]);
# right side
right = [];
for y in range(h):
    x = w-1;
    while mask[y][x] == 255:
        x -= 1;
    right.append([(w - x) - 1, [w-1,y]]);

# combine
scores = [top, left, bottom, right];

# plot
for side in scores:
    fig = plt.figure();
    ax = plt.axes();
    y = [score[0] for score in side];
    x = [a for a in range(len(y))];
    ax.plot(x, y);
    plt.show();

# get the top score for each side
highscores = []; # [score, [x, y]];
for side in scores:
    top_score = -1;
    top_point = [-1, -1];
    for score in side:
        if score[0] > top_score:
            top_score = score[0];
            top_point = score[1];
    highscores.append([top_score, top_point]);

# get the top two (assuming that there are two entrances to the maze)
one = [0, [0,0]];
two = [0, [0,0]];
for side in highscores:
    if side[0] > one[0]:
        two = one[:];
        one = side[:];
    elif side[0] > two[0]:
        two = side[:];

# draw the entrances
cv2.circle(rect, tup(one[1]), 5, (0,0,255), -1);
cv2.circle(rect, tup(two[1]), 5, (0,0,255), -1);

# show
cv2.imshow("Image", img);
cv2.imshow("Rect", rect);
cv2.waitKey(0);

这篇关于如何找出迷宫图片的出入口位置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！