How can I determine the maximum size rectangle that I can draw on the mask?

Question

I am doing an image processing project and I am stuck in one of the project steps. Here is the situation:

This is my mask:

and I want to detect a rectangle of maximum size that can fit into this mask as follows.

I am using MATLAB for my project. Do you know a quick way to achieve this goal. Any code sample, approach or technique would be great.

EDIT 1: Below are two workflow algorithms. But both of them give wrong results in some difficult cases. I use both of them in my project.

Answer 1

This approach starts with the whole image and compresses each border, in turn, pixel-by-pixel, until it finds an acceptable rectangle.

It takes ~ 0.02 seconds to run on an example image, so it is fast enough.

EDIT : I have to clarify that this should not be a universal solution. This algorithm is based on the centering of the rectangle and has approximately the same aspect ratio as the image itself. However, in cases where it is appropriate, it is quick. @DanielHsH proposed a solution that they claim works in all cases.

---

The code:

clear; clc; tic; %% // read image imrgb= imread('box.png'); im = im2bw(rgb2gray(imrgb)); %// binarize image im = 1-im; %// convert "empty" regions to 0 intensity [rows,cols] = size(im); %% // set up initial parameters ULrow = 1; %// upper-left row (param #1) ULcol = 1; %// upper-left column (param #2) BRrow = rows; %// bottom-right row (param #3) BRcol = cols; %// bottom-right column (param #4) parameters = 1:4; %// parameters left to be updated pidx = 0; %// index of parameter currently being updated %% // shrink region until acceptable while ~isempty(parameters); %// update until all parameters reach bounds %// 1. update parameter number pidx = pidx+1; pidx = mod( pidx-1, length(parameters) ) + 1; p = parameters(pidx); %// current parameter number %// 2. update current parameter if p==1; ULrow = ULrow+1; end; if p==2; ULcol = ULcol+1; end; if p==3; BRrow = BRrow-1; end; if p==4; BRcol = BRcol-1; end; %// 3. grab newest part of region (row or column) if p==1; region = im(ULrow,ULcol:BRcol); end; if p==2; region = im(ULrow:BRrow,ULcol); end; if p==3; region = im(BRrow,ULcol:BRcol); end; if p==4; region = im(ULrow:BRrow,BRcol); end; %// 4. if the new region has only zeros, stop shrinking the current parameter if isempty(find(region,1)) parameters(pidx) = []; end end toc; params = [ULrow ULcol BRrow BRcol] area = (BRrow-ULrow)*(BRcol-ULcol) 

---

Results for this image:

 Elapsed time is 0.027032 seconds. params = 10 25 457 471 area = 199362 

Code for visualizing the results:

 imrgb(params(1):params(3),params(2):params(4),1) = 0; imrgb(params(1):params(3),params(2):params(4),2) = 255; imrgb(params(1):params(3),params(2):params(4),3) = 255; imshow(imrgb); 

Another example image:

Answer 2

Here is the correct answer. You must use dynamic programming! Other methods of direct calculation (for example, cutting 1 pixel from each edge) may lead to suboptimal results. My method ensures that it selects the maximum possible rectangle that fits in the mask. I assume that the mask has 1 large convex white drop of any shape with a black background around it.

I wrote 2 methods. findRect() , which finds the best square (starting with x, y with length l). The second LargestInscribedImage() method is an example of how to find any rectangle (any aspect ratio). The trick is to resize the mask image, find the square and resize it. In my example, the method finds a large rectangle that can be placed in a mask with the same aspect as the image of the mask. For example, if the mask image has a size of 100x200 pixels, than the algorithm will find the largest rectangle with an aspect ratio of 1: 2.

 % ---------------------------------------------------------- function LargestInscribedImage() % ---------------------------------------------------------- close all im = double(imread('aa.bmp')); % Balck and white image of your mask im = im(:,:,1); % If it is colored RGB take only one of the channels b = imresize(im,[size(im,1) size(im,1)]); Make the mask square by resizing it by its aspect ratio. SC = 1; % Put 2..4 to scale down the image an speed up the algorithm [x1,y1,l1] = findRect(b,SC); % Lunch the dyn prog algorithm [x2,y2,l2] = findRect(rot90(b),SC); % rotate the image by 90deg and solve % Rotate back: x2,y2 according to rot90 tmp = x2; x2 = size(im,1)/SC-y2-l2; y2 = tmp; % Select the best solution of the above (for the original image and for the rotated by 90degrees if (l1>=l2) corn = sqCorn(x1,y1,l1); else corn = sqCorn(x2,y2,l2); end b = imresize(b,1/SC); figure;imshow(b>0); hold on; plot(corn(1,:),corn(2,:),'O') corn = corn*SC; corn(1,:) = corn(1,:)*size(im,2)/size(im,1); figure;imshow(im); hold on; plot(corn(1,:),corn(2,:),'O') end function corn = sqCorn(x,y,l) corn = [x,y;x,y+l;x+l,y;x+l,y+l]'; end % ---------------------------------------------------------- function [x,y,l] = findRect(b,SC) b = imresize(b,1/SC); res = zeros(size(b,1),size(b,2),3); % initialize first col for i = 1:1:size(b,1) if (b(i,1) > 0) res(i,1,:) = [i,1,0]; end end % initialize first row for i = 1:1:size(b,2) if (b(1,i) > 0) res(1,i,:) = [1,i,0]; end end % DynProg for i = 2:1:size(b,1) for j = 2:1:size(b,2) isWhite = b(i,j) > 0; if (~isWhite) res(i,j,:)=res(i-1,j-1,:); % copy else if (b(i-1,j-1)>0) % continuous line lineBeg = [res(i-1,j-1,1),res(i-1,j-1,2)]; lineLenght = res(i-1,j-1,3); if ((b(lineBeg(1),j)>0)&&(b(i,lineBeg(2))>0)) % if second diag is good res(i,j,:) = [lineBeg,lineLenght+1]; else res(i,j,:)=res(i-1,j-1,:); % copy since line has ended end else res(i,j,:) = [i,j,0]; % Line start end end end end % check last col [maxValCol,WhereCol] = max(res(:,end,3)); % check last row [maxValRow,WhereRow] = max(res(end,:,3)); % Find max x= 0; y = 0; l = 0; if (maxValCol>maxValRow) y = res(WhereCol,end,1); x = res(WhereCol,end,2); l = maxValCol; else y = res(end,WhereRow,1); x = res(end,WhereRow,2); l = maxValRow; end corn = [x,y;x,y+l;x+l,y;x+l,y+l]'; % figure;imshow(b>0); hold on; % plot(corn(1,:),corn(2,:),'O') return; end 

Answer 3

The black borders of your image are curved and not closed. For example, in the upper right corner, black borders will not meet and form a closed loop. Therefore, a simple strategy in one of my comments will not work.

Now I provide you with a code skeleton that you can play with and add conditions to suit your needs. My idea is this:

To find the left side of the x coordinate of the rectangle, first count the white pixels, each image column contains:

 %I assume that the image has already been converted to binary. whitePixels=sum(img,1); 

Then find the rate of change:

 diffWhitePixels=diff(whitePixels); 

If you see the diffWhitePixels hatching diffWhitePixels , then you will see various large entries (which show that the white area is still not in a straight line, and this is not a suitable place to place the rectangles to the left vertically), Small entries (in your image less than 5 ) indicate that you can put a rectangle there.

You can do similar things to determine the correct, top and bottom positions of the rectangles.

Discussion

First of all, the problem, in my opinion, is inappropriate. What do you mean by a rectangle of maximum size? Is this the maximum area or side length? In all possible cases, I do not think that the method can get the right answer. I can think of two or three cases right now when the above method will fail, but it will at least give you the correct answer to images like this image, provided that you adjust the values.

You can set some restrictions as soon as you know how your images will look. For example, if inside the border of the black border you can say that you do not need a column, for example [0;0;...0;1;1;...0;0;...;0;1;1;...;1] , that is, zeros surrounded by ones. Another limitation could be how many black pixels do you want to resolve? You can also crop the image to remove excess black pixels. In your image, you can crop the image (programmatically) on the left and bottom. Cropping an image is probably necessary, and certainly better done.