Detecting rectangles in maze environment

Question

[This is my first post on this site, I'll try to be as complete as possible but forgive me if my problem statement is unclear or the code formatting is not up to standards]

I am trying to detect the largest possible rectangles in a maze environment, so I can use convex optimization methods for maintaining line-of-sight connectivity in the maze. This means any other convex shape would be fine as well, although I think rectangles are easiest to implement given the map I'm using (see below) This also means the rectangles can (and should) overlap, i.e. at each maze bend there should be at least 2 overlapping rectangles.

My original idea was to determine all the edges in the maze, yielding a grid of rectangles, and then iteratively check which rectangles can be combined to form convex shapes (if there is a better way of finding these rectangles, I would love to hear it!).

The code I have thus far is shown below:

% import the maze image
I = imread('Maps/Maze1.png');

% determine edge cells using image dilation
se = strel('square',3);
I1 = imdilate(I,se);
BW = I1-I;

% obtain hough transform
[H, THETA, RHO] = hough(BW,'Theta',[-90 0]);
PEAKS = houghpeaks(H,5000,'Threshold',1e-6);        % threshold set low to find enough lines. Diagonals are deleted later
LINES = houghlines(BW, THETA, RHO, PEAKS);

% plot the original 'edge' image
subplot(2,1,1);
imshow(mat2gray(BW))
colormap('gray')
title('Original Image');

% plot the hough transform for reference
subplot(2,1,2);
imshow(imadjust(mat2gray(H)),'XData',THETA,'YData',RHO,...
      'InitialMagnification','fit');
title('Hough Transform of Image');
xlabel('\theta'), ylabel('\rho');
axis on, axis normal, hold on;
colormap(hot);

% plot the original image and all horizontal and vertical detected edges
figure;
imagesc(I);
colormap('gray')
hold on

for k = 1:length(LINES)
    xy = [LINES(k).point1; LINES(k).point2];
    plot(xy(:,1),xy(:,2),'LineWidth',2,'Color','green');
end

Although some edges are detected, most remain unmarked. Setting the peaks threshold lower didn't help. Does anyone know why the remaining edges aren't being detected? I've added the plots generated by my script below.

Result of the edge detection:

Answer 1

You can use the Hough transform for detecting straight lines. The functions you would have to use are edge(), hough(), houghpeaks(), and houghlines().