基於點和法線識別邊緣

Question

我有點基於相對法線分類點的問題。 我想要做的是使用我得到的信息來擬合一個簡化的多邊形的點，在一定程度上偏向90度的角度。

我對每個點都有粗糙的（雖然不是很準確的）法線，但我不確定如何區分點的接近度和法線的接近度。我打算分塊的點，每個面後做線性迴歸，作爲正常線有時不與實際面合身（儘管它們彼此接近的每個面）

實施例： alt text http://a.imageshack.us/img842/8439/ptnormals.png

理想情況下，我希望能夠圍繞此數據繪製一個矩形。但是，多邊形不需要凸出，也不必與軸對齊。

任何提示如何實現這樣的東西將是非常棒的。

在此先感謝

Answer 1

我想嘗試以下

1. 集羣基礎上的接近和類似角點。我會使用單連接層次聚類（Matlab中的LINKAGE），因爲您不知道先驗會有多少條邊。單聯動有利於線性結構，這正是您要找的。作爲兩點之間的距離標準，您可以使用點座標之間的歐式距離乘以角度函數，一旦角度差異超過20或30度，角度函數就會非常陡峭地增加。
2. 對數據進行（強健）線性迴歸。使用法線可能會幫助或不會幫助。我的猜測是他們不會幫助太多。爲了簡單起見，您可能最初想要忽略法線。
3. 查找線條之間的交點。
4. 如果必須，您可以隨時嘗試和改善配合，例如通過限制相對的線條平行。

如果不成功，您可以嘗試並實施THIS PAPER中的方法，該方法允許一次擬合多條直線。

Answer 2

你可以得到每一邊的X和Y座標的平均值，然後根據這個值得到線。

Answer 3

我不知道如果這是你在找什麼，但這裏是我的，我的理解是解決問題的嘗試：

我現在用的是正常的向量的角度，找到屬於每個側分的矩形（左，右，上，下），然後簡單地適合每一條線。

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