Распознавание ребер на основе точек и нормалей

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

Answer 2

Я бы попробовал следующее

1. Сгруппировать точки на основе близости и подобного угла.Я бы использовал иерархическую кластеризацию с одной связью ( LINKAGE в Matlab), поскольку вы не знаете a priori сколько будет ребер.Одиночная связь благоприятствует линейным структурам, а это именно то, что вы ищете.В качестве критерия расстояния между двумя точками можно использовать евклидово расстояние между точечными координатами, умноженное на функцию угла, который очень резко увеличивается, как только угол изменяется больше, чем, скажем, на 20 или 30 градусов.(надежная) линейная регрессия в данные.Использование нормалей может или не может помочь.Я предполагаю, что они не помогут слишком много.Для простоты вы можете сначала игнорировать нормали.
2. Найти пересечения между линиями.
3. Если вам нужно, вы всегда можете попытаться улучшить подбор, например, ограничив противоположныелинии должны быть параллельными.

Если это не удастся, вы можете попробовать реализовать подход в ЭТОТ БУМАГА , который позволяет устанавливать несколько прямых линий одновременно.

Answer 3

Вы можете получить среднее значение для координат X и Y для каждой стороны, а затем просто сделать линии на основе этого.