如何检测可以在蒙版上绘制的最大矩形？
How can I detect the maximum-sized rectangle that I can draw onto the mask?
我正在做一个图像处理项目，我卡在了项目的一个步骤中。情况是这样的；
这是我的面具：
并且我想像这样检测可以放入此掩码的最大尺寸矩形。
我正在为我的项目使用 MATLAB。你知道实现这个目标的任何快速方法吗？任何代码示例、方法或技术都会很棒。
编辑 1：下面的两种算法适用于很多情况。但在一些困难的情况下，它们都给出了错误的结果。我在我的项目中同时使用了它们。
您图像中的黑色边界是弯曲的并且没有闭合。例如，在右上角，黑色边界不会相交并形成闭合轮廓。因此，我的一个评论中的一个简单的策略是行不通的。
我现在为您提供一个代码框架，您可以使用它并根据需要添加条件。我的想法如下：
要找到矩形的左侧 x 坐标，首先计算图像每列包含的白色像素：
%I assume that the image has already been converted to binary.
whitePixels=sum(img,1);
然后求变化率：
diffWhitePixels=diff(whitePixels);
如果你看到diffWhitePixels的条形图，那么你会观察到各种大条目（这表明白色区域仍然不在一条直线上，并且不适合放置矩形左垂直边缘）。小条目（在您的图像中，少于 5 个）表示您可以将矩形边缘放在那里。
您可以做类似的事情来确定矩形的右边缘、上边缘和下边缘位置。
讨论：
首先，这个问题在我看来是不适定的。最大尺寸的矩形是什么意思？是最大面积还是边长？在所有可能的情况下，我认为上述方法不能得到正确的答案。我现在可以想到上述方法会失败的两三种情况，但如果您调整值，它至少会在与给定图像相似的图像上为您提供正确答案。
一旦知道图像的外观，就可以设置一些限制条件。例如，如果黑色边界在内部弯曲，您可以说您不想要 [0;0;...0;1;1;...0;0;...;0;1;1;...;1] 之类的列，即零被一包围。另一个约束可能是您希望允许多少个黑色像素？您还可以裁剪图像直到删除多余的黑色像素。在您的图像中，您可以（以编程方式）从左侧和底部边缘裁剪图像。裁剪图像可能是必要的，而且绝对是更好的做法。
这种方法从整个图像开始，逐个像素依次缩小每个边框，直到找到可接受的矩形。
在示例图像上 运行 大约需要 0.02 秒，因此相当快。
编辑：我应该澄清一下，这并不是一个通用的解决方案。该算法依赖于居中的矩形并具有与图像本身大致相同的纵横比。但是，在适当的情况下，它很快。 @DanielHsH 提供了一个他们声称在所有情况下都有效的解决方案。
代码：
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)
这张图片的结果：
Elapsed time is 0.027032 seconds.
params =
10 25 457 471
area =
199362
可视化结果的代码：
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);
另一个示例图片：
这是正确答案。
你必须使用动态规划！其他直接计算方法（例如从每条边切掉 1 个像素）可能会产生次优结果。我的方法保证它选择适合掩码的最大可能矩形。我假设面具有 1 个任何形状的大凸白色斑点，周围有黑色背景。
我写了2个方法。 findRect() 找到可能的最佳正方形（从 x,y 开始，长度为 l）。第二种方法 LargestInscribedImage() 是如何找到任何矩形（任何长宽比）的示例。诀窍是调整蒙版图像的大小，找到一个正方形并将其调整回来。
在我的示例中，该方法找到可以适合掩码的大矩形，该矩形具有与掩码图像相同的纵横比。例如，如果蒙版图像的大小为 100x200 像素，那么算法将找到纵横比为 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
我正在做一个图像处理项目，我卡在了项目的一个步骤中。情况是这样的；
这是我的面具：
并且我想像这样检测可以放入此掩码的最大尺寸矩形。
我正在为我的项目使用 MATLAB。你知道实现这个目标的任何快速方法吗？任何代码示例、方法或技术都会很棒。
编辑 1：下面的两种算法适用于很多情况。但在一些困难的情况下，它们都给出了错误的结果。我在我的项目中同时使用了它们。
您图像中的黑色边界是弯曲的并且没有闭合。例如，在右上角，黑色边界不会相交并形成闭合轮廓。因此，我的一个评论中的一个简单的策略是行不通的。
我现在为您提供一个代码框架，您可以使用它并根据需要添加条件。我的想法如下：
要找到矩形的左侧 x 坐标，首先计算图像每列包含的白色像素：
%I assume that the image has already been converted to binary.
whitePixels=sum(img,1);
然后求变化率：
diffWhitePixels=diff(whitePixels);
如果你看到diffWhitePixels的条形图，那么你会观察到各种大条目（这表明白色区域仍然不在一条直线上，并且不适合放置矩形左垂直边缘）。小条目（在您的图像中，少于 5 个）表示您可以将矩形边缘放在那里。
您可以做类似的事情来确定矩形的右边缘、上边缘和下边缘位置。
讨论：
首先，这个问题在我看来是不适定的。最大尺寸的矩形是什么意思？是最大面积还是边长？在所有可能的情况下，我认为上述方法不能得到正确的答案。我现在可以想到上述方法会失败的两三种情况，但如果您调整值，它至少会在与给定图像相似的图像上为您提供正确答案。
一旦知道图像的外观，就可以设置一些限制条件。例如，如果黑色边界在内部弯曲，您可以说您不想要 [0;0;...0;1;1;...0;0;...;0;1;1;...;1] 之类的列，即零被一包围。另一个约束可能是您希望允许多少个黑色像素？您还可以裁剪图像直到删除多余的黑色像素。在您的图像中，您可以（以编程方式）从左侧和底部边缘裁剪图像。裁剪图像可能是必要的，而且绝对是更好的做法。
这种方法从整个图像开始，逐个像素依次缩小每个边框，直到找到可接受的矩形。
在示例图像上 运行 大约需要 0.02 秒，因此相当快。
编辑：我应该澄清一下，这并不是一个通用的解决方案。该算法依赖于居中的矩形并具有与图像本身大致相同的纵横比。但是，在适当的情况下，它很快。 @DanielHsH 提供了一个他们声称在所有情况下都有效的解决方案。
代码：
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)
这张图片的结果：
Elapsed time is 0.027032 seconds.
params =
10 25 457 471
area =
199362
可视化结果的代码：
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);
另一个示例图片：
这是正确答案。 你必须使用动态规划！其他直接计算方法（例如从每条边切掉 1 个像素）可能会产生次优结果。我的方法保证它选择适合掩码的最大可能矩形。我假设面具有 1 个任何形状的大凸白色斑点，周围有黑色背景。
我写了2个方法。 findRect() 找到可能的最佳正方形（从 x,y 开始，长度为 l）。第二种方法 LargestInscribedImage() 是如何找到任何矩形（任何长宽比）的示例。诀窍是调整蒙版图像的大小，找到一个正方形并将其调整回来。
在我的示例中，该方法找到可以适合掩码的大矩形，该矩形具有与掩码图像相同的纵横比。例如，如果蒙版图像的大小为 100x200 像素，那么算法将找到纵横比为 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