Ускоренное плоское прилегание ко многим точкам

Question

Я ищу подходящую плоскость к набору ~ 6-10k 3D-точек. Я стараюсь сделать это как можно быстрее, и точность не является наивысшей проблемой (откровенно говоря, плоскость может быть на +10 градусов в любой из кардинальных осей).

Мой нынешний подход - использовать наилучшее из лучших, но он невероятно медленный (я надеюсь извлечь самолеты со скоростью примерно 10-50 килограмм каждый раз, когда я запускаю алгоритм, и при таком значении он завершит в неделях, в отличие от часов), поскольку он работает во всех возможных комбинациях из 6000 пунктов, поэтому ~ 35 000 000 000 итераций, и, откровенно говоря, он имеет гораздо более высокую точность, чем мне нужно.

Кто-нибудь знает о каких-либо более слабых методах крепления самолета, которые могут значительно ускорить мой алгоритм?

EDIT:

мне удалось получить число итераций до ~ 42k путем создания плоскостей в каждом возможном 3D угол (пошагового на 5 градусов каждый раз) и тестирование существующих точек против них, чтобы найти лучшая плоскость, вместо того, чтобы подгонять плоскости к точкам, которые у меня есть.

Я уверен, что здесь есть что-то, что можно разделить и победить, хотя я волнуюсь, что могу прыгнуть прямо через лучший самолет.

Answer 1

Используйте стандартное уравнение плоской Ax + By + Cz + D = 0, и записать уравнение в виде матричного умножения. P это ваш неизвестный 4x1 [A;B;C;D]

g = [x y z 1]; % represent a point as an augmented row vector 
g*P = 0;  % this point is on the plane 

Теперь расширьте это все ваши фактические точки, матрицы NX4 G. Результат больше не равен 0, это ошибка, которую вы пытаетесь свести к минимуму.

G*P = E; % E is a Nx1 vector 

Так что вы хотите ближайший вектор к нуль-пространстве G, которая может быть найдена из СВД. Тестирование:

% Generate some test data 
A = 2; 
B = 3; 
C = 2.5; 
D = -1; 

G = 10*rand(100, 2); % x and y test points 
% compute z from plane, add noise (zero-mean!) 
G(:,3) = -(A*G(:,1) + B*G(:,2) + D)/C + 0.1*randn(100,1); 

G(:,4) = ones(100,1); % augment your matrix 

[u s v] = svd(G, 0); 
P = v(:,4);    % Last column is your plane equation 

ОК, помните, что P может варьироваться в зависимости от скаляра. Так просто, чтобы показать, что мы сопоставляем:

scalar = 2*P./P(1); 
P./scalar 

ANS = 2,0000 3,0038 2.5037 -0.9997

Answer 2

Похоже, что griddata может быть тем, что вы хотите. В этом примере есть ссылка.

Если это не поможет, возможно, зарегистрируйтесь gridfit на MATLAB File Exchange. Это сделано для более общего случая, чем griddata.

Возможно, вы не хотите, чтобы вы наматывали свою собственную поверхность, так как есть несколько хорошо документированных инструментов.

Возьмем пример из griddata:

x = % some values 
y = % some values 
z = % function values to fit to 

ti = % this range should probably be greater than or equal to your x,y test values 
[xq,yq] = meshgrid(ti,ti); 
zq = griddata(x,y,z,xq,yq,'linear'); % NOTE: linear will fit to a plane! 
Plot the gridded data along with the scattered data. 

mesh(xq,yq,zq), hold 
plot3(x,y,z,'o'), hold off 

Answer 3

Вы можете попробовать consolidator Джоном D'Errico. Он объединяет точки в пределах данного допуска, что позволит уменьшить объем данных и увеличить скорость.Вы также можете проверить функцию John's gridfit, которая обычно быстрее и гибче, чем griddata

Answer 4

В компьютерном зрении стандартным способом является использование RANSAC или MSAC в вашем случае;

1. Принимать 3 случайных точек из популяции
2. Вычислить плоскости, определяемой точками 3
3. Sum ошибки (расстояние до плоскости) для всех точек в этой плоскости.
4. Держите 3 точки, которые показывают наименьшую сумму ошибок (и попадают в порог).
5. Повторите N итераций (? См теорию RANSAC выбрать N, я могу предложить 50)

http://en.wikipedia.org/wiki/RANSAC