How to square the corners of a "rectangle" in a bw image with matlab

Question

I have images of rectangles or deformed rectangles with rounded corners, like this:

or this:

is there a way to make the corners squared with matlab?

And then how can i get the coordinates of those new corners?

Thank you

Answer 1

Explanation

This problem is similar to the following question. My answer will be somehow similar to my answer there, with the relevant modifications.

we want to find the parallelogram corners which fits the most to the given shape. The solution can be found by optimization, as follows:

1. find an initial guess for the 4 corners of the shape. This can be done by finding the boundary points with the highest curvature, and use kmean clustering to cluster them into 4 groups.

2. create a parallelogram given these 4 corners, by drawing a line between each pair of corresponding corners.

3. find the corners which optimize the Jaccard coefficient of the boundary image and the generated parallelogram map.

The optimization will done locally on each corner, in order to spare time.

Results

Initial corner guess (corners are marked in blue)

final results:

Code

main script

%reads image and binarize it
I = rgb2gray(imread('eA4ci.jpg')) > 50;

%finds boundry of largerst connected component
boundries = bwboundaries(I,8);
numPixels = cellfun(@length,boundries);
[~,idx] = max(numPixels);
B = boundries{idx};

%finds best 4 corners
[ corners ] = optimizeCorners(B);

%generate line mask given these corners, fills the result
linesMask = drawLines(size(I),corners,corners([2:4,1],:));
rectMask = imfill(linesMask,'holes');

%remove biggest CC from image, adds linesMask instead
CC = bwconncomp(I,8);
numPixels = cellfun(@numel,CC.PixelIdxList);
[~,idx] = max(numPixels);
res = I;
res(CC.PixelIdxList{idx}) = 0;
res = res | rectMask;

optimize corners function:

function [ corners] = optimizeCorners(xy)
%finds the corners which fits the most for this set of points

Y = xy(:,1);
X = xy(:,2);

%initial corners guess
corners = getInitialCornersGuess(xy);
boundriesIm = zeros(max(Y)+20,max(X)+20);
boundriesIm(sub2ind(size(boundriesIm),xy(:,1),xy(:,2))) = 1;

%R represents the search radius
R = 7;

%continue optimizing as long as there is no change in the final result
unchangedIterations = 0;
while unchangedIterations<4

    for ii=1:4
        %optimize corner ii
        currentCorner = corners(ii,:);
        bestCorner = currentCorner;
        bestRes = calcEnergy(boundriesIm,corners);
        cornersToEvaluate = corners;

        for yy=currentCorner(1)-R:currentCorner(1)+R
            for xx=currentCorner(2)-R:currentCorner(2)+R

                cornersToEvaluate(ii,:) = [yy,xx];
                res = calcEnergy(boundriesIm,cornersToEvaluate);
                if res > bestRes
                    bestRes = res;
                    bestCorner = [yy,xx];
                end
            end
        end
        if isequal(bestCorner,currentCorner)
            unchangedIterations = unchangedIterations + 1;
        else
            unchangedIterations = 0;
            corners(ii,:) = bestCorner;

        end
    end
end

end

function res = calcEnergy(boundriesIm,corners)
%calculates the score of the corners list, given the boundries image.
%the result is acutally the jaccard index of the boundries map and the
%lines map
linesMask =  drawLines(size(boundriesIm),corners,corners([2:4,1],:));
res = sum(sum(linesMask&boundriesIm)) / sum(sum(linesMask|boundriesIm));

end

get initial corners function:

function corners = getInitialCornersGuess(boundryPnts)
%calculates an initial guess for the 4 corners

%finds corners by performing kmeans on largest curvature pixels
[curvatureArr] = calcCurvature(boundryPnts, 5);
highCurv = boundryPnts(curvatureArr>0.3,:);
[~,C] = kmeans([highCurv(:,1),highCurv(:,2)],4);

%sorts the corners from top to bottom - preprocessing stage
C = int16(C);
corners = zeros(size(C));

%top left corners
topLeftInd = find(sum(C,2)==min(sum(C,2)));
corners(1,:) = C(topLeftInd,:);
%bottom right corners
bottomRightInd  = find(sum(C,2)==max(sum(C,2))); 
corners(3,:) = C(bottomRightInd,:);
%top right and bottom left corners
C([topLeftInd,bottomRightInd],:) = [];
topRightInd = find(C(:,2)==max(C(:,2)));
corners(4,:) = C(topRightInd,:);
bottomLeftInd = find(C(:,2)==min(C(:,2)));
corners(2,:) = C(bottomLeftInd,:);



end



function [curvatureArr] = calcCurvature(xy, halfWinSize)
%calculate the curvature of a list of points (xy) given a window size

%curvature calculation
curvatureArr = zeros(size(xy,1),1);
for t=1:halfWinSize
    y = xy(t:halfWinSize:end,1);
    x = xy(t:halfWinSize:end,2);
    dx  = gradient(x);
    ddx = gradient(dx);
    dy  = gradient(y);
    ddy = gradient(dy);
    num   = abs(dx .* ddy - ddx .* dy)  + 0.000001;
    denom = dx .* dx + dy .* dy + 0.000001;
    denom = sqrt(denom);
    denom = denom .* denom .* denom;
    curvature = num ./ denom;

    %normalizing
    if(max(curvature) > 0)
        curvature = curvature / max(curvature);
    end

    curvatureArr(t:halfWinSize:end) = curvature;

end

end

draw lines function:

function mask = drawLines(imgSize, P1, P2)
%generates a mask with lines, determine by P1 and P2 points

mask = zeros(imgSize);

P1 = double(P1);
P2 = double(P2);

for ii=1:size(P1,1)
    x1 = P1(ii,2); y1 = P1(ii,1);
    x2 = P2(ii,2); y2 = P2(ii,1);

    % Distance (in pixels) between the two endpoints
    nPoints = ceil(sqrt((x2 - x1).^2 + (y2 - y1).^2));

    % Determine x and y locations along the line
    xvalues = round(linspace(x1, x2, nPoints));
    yvalues = round(linspace(y1, y2, nPoints));

    % Replace the relevant values within the mask
    mask(sub2ind(size(mask), yvalues, xvalues)) = 1;
end