How can I detect rectangles and get their coordinates in a binary image

Hi,

I'm looking for a way to extract the rectangles of a binary image and get the coordinates of the corners of the rectangles. The location and size of the rectangles can vary, but it will always be black rectangles on a white background. Also, the black border at the edge of the image will be made up of 4 rectangles, see the image below (the numbers are just there to give you an idea of the numbers of rectangles).

I have tried to use the detectHarrisFeatures function, but the problem is that I only get the coordinates of the rectangles, thus I don't know which coordinates makes up a rectangle.

I have also tried to use the bwconncomp function, as I was suggested in this post. It works, but it is slow for larger images and it is possible to end up with a lot of small row rectangles or a lot of small column rectangles. For example the top border can be seen as 2 connected rows, or 120 connected columns.

So I'm looking for a more efficient way to detect the rectangles and retrive the corner coordinates for each.

I have attached two example image in the question.

Any help is highly appriciated

[Matt J]

Your problem is a bit ill-defined, because there potentially several non-unique ways that the black regions you've shown can be partitioned into rectangles. Or is it really just the corners you are after?

[Niklas Persson]

Yes, I'm aware of the problem, that is also one of the things I'm struggling with. Of course, the optimal thing would be to get the minimum number of rectangles, but I'm happy with a suboptimal solution as well, as long as it is not too many rectangles.

I also realise now that I haven't mentioned why I want to do this. So my idea is to use a 2D binary image as above to programmatically build a 3D environment in Simulink using simscape solid brick elements. Thus, I need the coordinates of the rectangles. To speed up the building of the environment I would like to have as few rectangles as possible.

[Matt J]

Even if you could get the fewest number of rectangles, you still have ambiguities. Below is an example showing a shape that can be partitioned into the minimum number of rectangles (2) in two different ways. Does your application care which partition is chosen?

[Niklas Persson]

Ah, yes of course. Well, the application does not care about how they are partition.

Answer 1

[Image Analyst]

What I'd do first is to get the four perimeter blobs and store those, then fill in that border. Then I'd threshold for black then label the image. Then use ismember to get each blob in turn. Then I'd scan down each image until I hit the blob. Then use find() to find the first and last point in the blob and note it's width and top row. Then scan down until the width changes, which means you're now in a new rectangle so the last one had its bottom row on the prior line. I believe this should work. Give it a try. If you're still unable to do it, post the original image (with no graphics or JPG blurring) in a .PNG file.

[Niklas Persson]

Thanks! I can’t access matlab right now but I will try to follow your idea tomorrow and see if I get stuck or not.

I did attach two .png files in my original question, were they not what you had in mind?

[Image Analyst]

Yeah, those would be OK. I didn't notice them at first.

You'll have to modify my algorithm to handle cases where a row cross section might cut through two or more rectangles. The function bwlabel is useful for counting:

Here's a start. Much stuff is left out though.

[rows, columns, numbreOfcolorchannels] = size(binaryImage);
rectCounter = 0; % Keep track of number of rectangles.
width = zeros(rows, 1);
for row = 1 : rows
    thisRow = binaryImage
    [~, numRegions] = bwlabel(thisRow);
    if numRegions == 1
        col1 = find(binaryImage, 1, 'first')
        if ~isempty(col1)
            col2 = find(binaryImage, 1, 'last')  
            width(row) = col2 - col1;
        end
    else
        % Two or more regions
    end
    % Write this region to the output image with a value of rectCounter
    % Etc.
end

After this you, if you do it right, you should have a labeled image where each rectangle has its own label (ID Number). Start out easy and have just one rectangle intersecting any row. Then adapt it to handle multiple rectangles.

[Niklas Persson]

Hi again,

Thanks for the help! I manage to solve the problem in the end with inspiration of your code.

It is not the most beautiful thing ever written, but it does the work and runs quite smooth, anyway here it is if someone have the same question.

[rows, columns, numbreOfcolorchannels] = size(binaryImage);


%Find out the max number of regions so we can initlaise a matrix for the
%columns among other things..
numRegions = zeros(rows,1);
for row = 1 : rows
    thisRow = binaryImage(row,:);
    [~, numRegions(row)] = bwlabel(thisRow);
end

maxNrRegions = max(numRegions);
nrOfCols = maxNrRegions * 2;

%initalise
cols = zeros(rows, nrOfCols);
lastCol = zeros (1, nrOfCols);
heights = repmat([0 1], rows, nrOfCols/2);




%go through the image and get all the start and end columns for each label
for row = 1 : rows
    thisRow = binaryImage(row,:);
    [regions, nR] = bwlabel(thisRow);
    for regionID = 1 : nR
        col1 = find(regions == regionID, 1, 'first');
        if ~isempty(col1)  %just making sure
            col2 = find(regions == regionID, 1, 'last');
        end
        cols(row, regionID*2-1:regionID*2) = [col1 col2]; %save the index of the columns
    end
end

%find out if the columns in the current row was also present in the last
%row, if so we add to the height
for row = 1 :rows
    currentCols = cols(row,:);
    for i = 2: 2: nrOfCols
        cc = currentCols (1, i-1:i);
        if isequal(cc, [0 0]) %[0 0] happens if nrOfRegions in the row is less than the maximum number of regions
            heights(row,i) = 0;
        else
            for j = 2: 2: length(lastCol)
                if isequal (cc, lastCol(1,j-1:j))
                    heights(row,i) = heights(row-1,j)+1; %get the last height and increase it by one
                    heights(row-1,j) = 0; %set the last height to zero, makes it easier to find the correct indecies later on
                    
                end
            end

        end
    end
    lastCol = currentCols;
end

%find all heights > 0 and retrive their row & columns
linIdx = find(heights > 0);
[r,c] = ind2sub (size(heights), linIdx);
rect = zeros(length(r),4);
rectPlot = zeros(length(r),4);

%Finally, we extract the rectangles positions
for i = 1 :length(r)
    rowStart = r(i) - heights(r(i),c(i)) +1;
    rowEnd = r(i);
    colStart = cols(r(i),c(i)-1);
    colEnd = cols( r(i),c(i));
    rect(i,:) = [colStart, colEnd, rowStart,rowEnd]; 
    rectPlot (i,:) = [colStart, rowStart, colEnd-colStart, rowEnd-rowStart+1]; %just for plotting
end

%compare the results
figure
hold on
for i = 1:length(r)
    rectangle('Position', rectPlot(i,:), 'FaceColor',[0 .5 .5])
end
hold off
set(gca, 'YDir','reverse')
axis([1 120 1 120])