algorithm - 基于点和法线识别边缘

Question

我在根据相对法线对点进行分类时遇到了一些问题。 我想做的是使用我在下面获得的信息将简化的多边形拟合到点，在一定程度上偏向 90 度角。

我有每个点的粗略(虽然不是很准确)法线，但我不确定如何根据点的接近度和法线的接近度来分离数据库。我计划在对每张脸的点进行分块后进行线性回归，因为法线有时与实际人脸不太吻合(尽管每张脸彼此靠近)

示例: alt text http://a.imageshack.us/img842/8439/ptnormals.png

理想情况下，我希望能够围绕此数据放置一个矩形。然而，多边形不需要是凸的，也不需要与轴对齐。

关于如何实现这样的目标的任何提示都很棒。

提前致谢

Answer 1

我不确定这是否是您要找的，但这是我尝试按照我的理解解决问题的方法:

我使用法向量的角度来找到属于矩形每一边的点(左、右、上、下)，然后简单地为每个点拟合一条线。

%# 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