Recognizing edges based on points and normals

Question

Hi guys, I have a bit of a problem categorizing points based on relative normals. What I would like to do is use the information I got below to fit a simplified polygon to the points, with a bias towards 90 degree angles to an extent.

I have the rough (although not very accurate) normal lines for each point, but I'm not sure how to separate the data base on closeness of points and closeness of the normals. I plan to do a linear regression after chunking the points for each face, as the normal lines sometimes does not fit well with the actual faces (although they are close to each other for each face)

Example:

Ideally, I would like to be able to fit a rectangle around this data. However, the polygon does not need to be convex, nor does it have to be aligned with the axis.

Any hints as to how to achieve something like this would be awesome.

Thanks in advance

Answer 1

I'd try the following

1. Cluster the points based on proximity and similar angle. I'd use single-linkage hierarchical clustering (LINKAGE in Matlab), since you don't know a priori how many edges there will be. Single linkage favors linear structures, which is exactly what you're looking for. As the distance criterion between two points you can use the euclidean distance between point coordinates multiplied by a function of the angle that increases very steeply as soon as the angle differs more than, say, 20 or 30 degrees.
2. Do (robust) linear regression into the data. Using the normals may or may not help. My guess is that they won't help too much. For simplicity, you may want to disregard the normals initially.
3. Find the intersections between the lines.
4. If you have to, you can always try and improve the fit, for example by constraining opposite lines to be parallel.

If that fails, you could try and implement the approach in THIS PAPER, which allows fitting multiple straight lines at once.

Answer 2

You could get the mean value for the X and Y coordinates for each side and then just make lines based on that.

Answer 3

I am not sure if this is what you are looking for, but here's my attempt at solving the problem as I understood it:

I am using the angles of the normal vectors to find points belonging to each side of the rectangle (left, right, up, down), then simply fit a line to each.

%# create random data (replace those with your actual data)
num = randi([10 20]);
pT = zeros(num,2);
pT(:,1) = rand(num,1);
pT(:,2) = ones(num,1) + 0.01*randn(num,1);
aT = 90 + 10*randn(num,1);

num = randi([10 20]);
pB = zeros(num,2);
pB(:,1) = rand(num,1);
pB(:,2) = zeros(num,1) + 0.01*randn(num,1);
aB = 270 + 10*randn(num,1);

num = randi([10 20]);
pR = zeros(num,2);
pR(:,1) = ones(num,1) + 0.01*randn(num,1);
pR(:,2) = rand(num,1);
aR = 0 + 10*randn(num,1);

num = randi([10 20]);
pL = zeros(num,2);
pL(:,1) = zeros(num,1) + 0.01*randn(num,1);
pL(:,2) = rand(num,1);
aL = 180 + 10*randn(num,1);

pts = [pT;pR;pB;pL];                 %# x/y coords
angle = mod([aT;aR;aB;aL],360);      %# angle in degrees [0,360]

%# plot points and normals
plot(pts(:,1), pts(:,2), 'o'), hold on
theta = angle * pi / 180;
quiver(pts(:,1), pts(:,2), cos(theta), sin(theta), 0.4, 'Color','g')
hold off

%# divide points based on angle
[~,bin] = histc(angle,[0 45 135 225 315 360]);
bin(bin==5) = 1;                     %# combine last and first bin

%# fit line to each segment
hold on
for i=1:4
    %# indices of points in this segment
    idx = ( bin == i );

    %# x/y or y/x
    if i==2||i==4, xx=1; yy=2; else xx=2; yy=1; end

    %# fit line
    coeff = polyfit(pts(idx,xx), pts(idx,yy), 1);
    fit(:,1) = 0:0.05:1;
    fit(:,2) = polyval(coeff, fit(:,1));

    %# plot fitted line
    plot(fit(:,xx), fit(:,yy), 'Color','r', 'LineWidth',2)
end
hold off