find out the orientation, length and radius of capped rectangular object

Question

I have a image as shown as fig.1. I am trying to fit this binary image with a capped rectangular (fig.2) to figure out:

1. the orientation (the angle between the long axis and the horizontal axis)
2. the length (l) and radius (R) of the object. What is the best way to do it? Thanks for the help.

My very naive idea is using least square fit to find out these information however I found out there is no equation for capped rectangle. In matlab there is a function called rectangle can create the capped rectangle perfectly however it seems just for the plot purpose.

Answer 1

I solved this 2 different ways and have notes on each approach below. Each method varies in complexity so you will need to decide the best trade for your application.

First Approach: Least-Squares-Optimization: Here I used unconstrained optimization through Matlab's fminunc() function. Take a look at Matlab's help to see the options you can set prior to optimization. I made some fairly simple choices just to get this approach working for you.

In summary, I setup a model of your capped rectangle as a function of the parameters, L, W, and theta. You can include R if you wish but personally I don't think you need that; by examining continuity with the half-semi-circles at each edge, I think it may be sufficient to let R = W, by inspection of your model geometry. This also reduces the number of optimization parameters by one.

I made a model of your capped rectangle using boolean layers, see the cappedRectangle() function below. As a result, I needed a function to calculate finite difference gradients of the model with respect to L, W, and theta. If you don't provide these gradients to fminunc(), it will attempt to estimate these but I found that Matlab's estimates didn't work well for this application, so I provided my own as part of the error function that gets called by fminunc() (see below).

I didn't initially have your data so I simply right-clicked on your image above and downloaded: 'aRIhm.png'

To read your data I did this (creates the variable cdata):

image = importdata('aRIhm.png');
vars = fieldnames(image);
for i = 1:length(vars)
    assignin('base', vars{i}, image.(vars{i}));
end

Then I converted to double type and "cleaned-up" the data by normalizing. Note: this pre-processing was important to get the optimization to work properly, and may have been needed since I didn't have your raw data (as mentioned I downloaded your image from the webpage for this question):

data = im2double(cdata); 
data = data / max(data(:));
figure(1); imshow(data); % looks the same as your image above

Now get the image sizes:

nY = size(data,1);
nX = size(data,2);

Note #1: you might consider adding the center of the capped rectangle, (xc,yc), as optimization parameters. These extra degrees of freedom will make a difference in the overall fitting results (see comment on final error function values below). I didn't set that up here but you can follow the approach I used for L, W, and theta, to add that functionality with the finite difference gradients. You will also need to setup the capped rectangle model as a function of (xc,yc).

EDIT: Out of curiosity I added the optimization over the capped rectangle center, see the results at the bottom.

Note #2: for "continuity" at the ends of the capped rectangle, let R = W. If you like, you can later include R as an explicit optimization parameter following the examples for L, W, theta. You might even want to have say R1 and R2 at each endpoint as variables?

Below are arbitrary starting values that I used to simply illustrate an example optimization. I don't know how much information you have in your application but in general, you should try to provide the best initial estimates that you can.

L = 25;
W = L;
theta = 90;
params0 = [L W theta]; 

Note that you will get different results based on your initial estimates.

Next display the starting estimate (the cappedRectangle() function is defined later):

capRect0 = reshape(cappedRectangle(params0,nX,nY),nX,nY);
figure(2); imshow(capRect0);

Define an anonymous function for the error metric (errorFunc() is listed below):

f = @(x)errorFunc(x,data);

% Define several optimization parameters for fminunc():
options = optimoptions(@fminunc,'GradObj','on','TolX',1e-3, 'Display','iter');

% Call the optimizer:
tic
[x,fval,exitflag,output] = fminunc(f,params0,options);
time = toc;
disp(['convergence time (sec) = ',num2str(time)]);

% Results:
disp(['L0 = ',num2str(L),'; ', 'L estimate = ', num2str(x(1))]);
disp(['W0 = ',num2str(W),'; ', 'W estimate = ', num2str(x(2))]);
disp(['theta0 = ',num2str(theta),'; ', 'theta estimate = ', num2str(x(3))]);
capRectEstimate = reshape(cappedRectangle(x,nX,nY),nX,nY);

figure(3); imshow(capRectEstimate);

Below is the output from fminunc (for more details on each column see Matlab's help):

 Iteration        f(x)          step          optimality   CG-iterations
     0           0.911579                       0.00465                
     1           0.860624             10        0.00457           1
     2           0.767783             20        0.00408           1
     3           0.614608             40        0.00185           1

     .... and so on ...

    15           0.532118     0.00488281       0.000962           0
    16           0.532118      0.0012207       0.000962           0
    17           0.532118    0.000305176       0.000962           0

You can see that the final error metric values have not decreased that much relative to the starting value, this indicates to me that the model function probably doesn't have enough degrees of freedom to really "fit" the data that well, so consider adding extra optimization parameters, e.g., image center, as discussed earlier.

EDIT: Added optimization over the capped rectangle center, see results at the bottom.

Now print the results (using a 2011 Macbook Pro):

Convergence time (sec) = 16.1053
    L0 = 25;      L estimate = 58.5773
    W0 = 25;      W estimate = 104.0663
theta0 = 90;  theta estimate = 36.9024

And display the results:

EDIT: The exaggerated "thickness" of the fitting results above are because the model is trying to fit the data while keeping its center fixed, resulting in larger values for W. See updated results at bottom.

You can see by comparing the data to the final estimate that even a relatively simple model starts to resemble the data fairly well.

You can go further and calculate error bars for the estimates by setting up your own Monte-Carlo simulations to check accuracy as a function of noise and other degrading factors (with known inputs that you can generate to produce simulated data).

Below is the model function I used for the capped rectangle (note: the way I did image rotation is kind of sketchy numerically and not very robust for finite-differences but its quick and dirty and gets you going):

function result = cappedRectangle(params, nX, nY)
[x,y] = meshgrid(-(nX-1)/2:(nX-1)/2,-(nY-1)/2:(nY-1)/2);
L = params(1);
W = params(2);
theta = params(3); % units are degrees
R = W; 

% Define r1 and r2 for the displaced rounded edges:
x1 = x - L;
x2 = x + L;
r1 = sqrt(x1.^2+y.^2);
r2 = sqrt(x2.^2+y.^2);

% Capped Rectangle prior to rotation (theta = 0):
temp = double( (abs(x) <= L) & (abs(y) <= W) | (r1 <= R) | (r2 <= R) );
cappedRectangleRotated = im2double(imrotate(mat2gray(temp), theta, 'bilinear', 'crop'));

result = cappedRectangleRotated(:);

return

And then you will also need the error function called by fminunc:

function [error, df_dx] = errorFunc(params,data)
nY = size(data,1);
nX = size(data,2);

% Anonymous function for the model:
model = @(params)cappedRectangle(params,nX,nY);

% Least-squares error (analogous to chi^2 in the literature):
f = @(x)sum( (data(:) - model(x) ).^2  ) / sum(data(:).^2);

% Scalar error:
error = f(params);
[df_dx] = finiteDiffGrad(f,params);

return

As well as the function to calculate the finite difference gradients:

function [df_dx] = finiteDiffGrad(fun,x)
N = length(x);
x = reshape(x,N,1);

% Pick a small delta, dx should be experimented with:
dx = norm(x(:))/10;

% define an array of dx values;
h_array = dx*eye(N); 
df_dx = zeros(size(x));

f = @(x) feval(fun,x); 

% Finite Diff Approx (use "centered difference" error is O(h^2);)
for j = 1:N
    hj = h_array(j,:)';
    df_dx(j) = ( f(x+hj) - f(x-hj) )/(2*dx);
end  

return

---

Second Approach: use regionprops()

As others have pointed out you can also use Matlab's regionprops(). Overall I think this could work the best with some tuning and checking to insure that its doing what you expect. So the approach would be to call it like this (it certainly is a lot simpler than the first approach!):

data = im2double(cdata); 
data = round(data / max(data(:)));

s = regionprops(data, 'Orientation', 'MajorAxisLength', ...
    'MinorAxisLength', 'Eccentricity', 'Centroid'); 

And then the struct result s:

>> s
s = 
           Centroid: [345.5309 389.6189]
    MajorAxisLength: 365.1276
    MinorAxisLength: 174.0136
       Eccentricity: 0.8791
        Orientation: 30.9354

This gives enough information to feed into a model of a capped rectangle. At first glance this seems like the way to go, but it seems like you have your mind set on another approach (maybe the first approach above).

Anyway, below is an image of the results (in red) overlaid on top of your data which you can see looks quite good:

---

EDIT: I couldn't help myself, I suspected that by including the image center as an optimization parameter, much better results could be obtained, so I went ahead and did it just to check. Sure enough, with the same starting estimates used earlier in the Least-Squares Estimation, here are the results:

Iteration        f(x)          step          optimality   CG-iterations
     0           0.911579                       0.00465                
     1           0.859323             10        0.00471           2
     2           0.742788             20        0.00502           2
     3           0.530433             40        0.00541           2
     ... and so on ...
    28          0.0858947      0.0195312       0.000279           0
    29          0.0858947      0.0390625       0.000279           1
    30          0.0858947     0.00976562       0.000279           0
    31          0.0858947     0.00244141       0.000279           0
    32          0.0858947    0.000610352       0.000279           0

By comparison with the earlier values we can see that the new least-square error values are quite a bit smaller when including the image center, confirming what we suspected earlier (so no big surprise).

The updated estimates for the capped rectangle parameters are thus:

Convergence time (sec) = 96.0418
    L0 = 25;     L estimate = 89.0784
    W0 = 25;     W estimate = 80.4379
theta0 = 90; theta estimate = 31.614

And relative to the image array center we get:

xc = -22.9107 
yc = 35.9257

The optimization takes longer but the results are improved as seen by visual inspection:

If performance is an issue you may want to consider writing your own optimizer or first try tuning Matlab's optimization parameters, perhaps using different algorithm options as well; see the optimization options above.

Here is the code for the updated model:

function result = cappedRectangle(params, nX, nY)
[X,Y] = meshgrid(-(nX-1)/2:(nX-1)/2,-(nY-1)/2:(nY-1)/2);

% Extract params to make code more readable:
L = params(1);
W = params(2);
theta = params(3); % units are degrees
xc = params(4); % new param: image center in x
yc = params(5); % new param: image center in y

% Shift coordinates to the image center:
x = X-xc;
y = Y-yc;

% Define R = W as a constraint:
R = W;

% Define r1 and r2 for the rounded edges:
x1 = x - L;
x2 = x + L;
r1 = sqrt(x1.^2+y.^2);
r2 = sqrt(x2.^2+y.^2);

temp = double( (abs(x) <= L) & (abs(y) <= W) | (r1 <= R) | (r2 <= R) );
cappedRectangleRotated = im2double(imrotate(mat2gray(temp), theta, 'bilinear', 'crop'));

result = cappedRectangleRotated(:);

and then prior to calling fminunc() I adjusted the parameter list:

L = 25;
W = L;
theta = 90;
% set image center to zero as intial guess:
xc = 0; 
yc = 0;
params0 = [L W theta xc yc]; 

Enjoy.

Answer 2

First I have to say that I do not have the answer to all of your questions but I can help you with the orientation.

I suggest using principal component analysis on the binary image. A good tutorial on PCA is given by Jon Shlens. In Figure 2 of his tutorial there is an example what it can be used for. In Section 5 of his paper you can see some sort of instruction how to compute the principal components. With singular value decomposition it is much easier as shown in Section 6.1.

To use PCA you have to get measurements for which you want to compute the principal components. In your case each white pixel is a measurement which is represented by the pixel location (x, y)'. You will have N two-dimensional vectors that give your measurements. Thus, your measurement 2xN matrix X is represented by the concatenated vectors.

When you have built this matrix proceed as given in Section 6.1. The singular values are representing the "strength" of the different components. Thus, the largest singular value represents the long axis of your ellipse. The second largest singular value (and it should only be two at all) is represents the other (perpendicular) axis.

Remember, if the ellipse is a circle your singular values should be equal but with your discrete image representation you will not get a perfect circle.