3D-плоскость с наименьшими квадратами

Каков алгоритм вычисления плоскости наименьших квадратов в пространстве (x, y, z), учитывая набор точек 3D-данных? Другими словами, если бы у меня была куча таких точек, как (1, 2, 3), (4, 5, 6), (7, 8, 9) и т. Д., Как можно было бы рассчитывать наилучшую плоскость f (x, y) = ax + на + c? Каков алгоритм получения a, b и c из набора трехмерных точек?

Если у вас есть n точек данных (x [i], y [i], z [i]), вычислите симметричную матрицу 3×3 A, элементами которой являются:

sum_i x[i]*x[i], sum_i x[i]*y[i], sum_i x[i] sum_i x[i]*y[i], sum_i y[i]*y[i], sum_i y[i] sum_i x[i], sum_i y[i], n 

Также вычислите 3-элементный вектор b:

 {sum_i x[i]*z[i], sum_i y[i]*z[i], sum_i z[i]} 

Тогда разрешите Ax = b для данных A и b. Три составляющие вектора решения являются коэффициентами для плоскости наименьшего квадрата {a, b, c}.

Обратите внимание, что это «обычное наименьшее квадратное» соответствие, что подходит только тогда, когда z ожидается как линейная функция от x и y. Если вы посмотрите в более общем плане на «наилучшую подходящую плоскость» в 3-пространстве, вы можете узнать о «геометрических» наименьших квадратах.

Также обратите внимание, что это не удастся, если ваши точки находятся в строке, в качестве ваших примерных точек.

если кто-то не скажет мне, как набирать уравнения здесь, позвольте мне просто записать окончательные вычисления, которые вам нужно сделать:

во-первых, заданные точки r_i \ n \ R, i = 1..N, вычислить центр масс всех точек:

 r_G = \frac{\sum_{i=1}^N r_i}{N} 

затем вычислим нормальный вектор n, который вместе с базовым вектором r_G определяет плоскость, вычисляя матрицу 3×3 A как

 A = \sum_{i=1}^N (r_i - r_G)(r_i - r_G)^T 

с этой матрицей нормальный вектор п теперь задается собственным вектором оператора А, соответствующим минимальному собственному значению А.

Чтобы узнать о пар собственных / собственных значениях, используйте любую библиотеку линейных алгебр по вашему выбору.

Это решение основано на теореме Рэлеяйт-Ритца для эрмитовой матрицы А.

Как и в случае с любым методом наименьших квадратов, вы выполняете следующее:

Перед началом кодирования

  1. Запишите уравнение для плоскости в некоторой параметризации, скажем, 0 = ax + by + z + d в параметрах (a, b, d) .

  2. Найти выражение D(\vec{v};a, b, d) для расстояния от произвольной точки \vec{v} .

  3. Запишите сумму S = \sigma_i=0,n D^2(\vec{x}_i) и упростите, пока она не выражается через простые суммы компонент v как \sigma v_x , \sigma v_y^2 , \sigma v_x*v_z

  4. Запишите выражения для минимизации параметра dS/dx_0 = 0 , dS/dy_0 = 0 …, который дает вам набор из трех уравнений по трем параметрам и суммам предыдущего шага.

  5. Решите эту систему уравнений для параметров.

(или для простых случаев, просто найдите форму). Использование пакета символической алгебры (например, Mathematica) может облегчить вам жизнь.

Кодирование

  • Напишите код, чтобы сформировать необходимые суммы и найти параметры из последнего установленного выше.

альтернативы

Обратите внимание: если у вас на самом деле было всего три очка, вам лучше всего найти самолет, который проходит через них.

Кроме того, если аналитическое решение в невыполнимом (не в случае плоскости, но возможно вообще), вы можете сделать шаги 1 и 2 и использовать минимизатор Монте-Карло на сумму на шаге 3.

См. «Наименьшее квадратное соответствие данных» Дэвида Эберли для того, как я придумал это, чтобы свести к минимуму геометрическое соответствие (ортогональное расстояние от точек до плоскости).

 bool Geom_utils::Fit_plane_direct(const arma::mat& pts_in, Plane& plane_out) { bool success(false); int K(pts_in.n_cols); if(pts_in.n_rows == 3 && K > 2) // check for bad sizing and indeterminate case { plane_out._p_3 = (1.0/static_cast(K))*arma::sum(pts_in,1); arma::mat A(pts_in); A.each_col() -= plane_out._p_3; //[x1-p, x2-p, ..., xk-p] arma::mat33 M(A*At()); arma::vec3 D; arma::mat33 V; if(arma::eig_sym(D,V,M)) { // diagonalization succeeded plane_out._n_3 = V.col(0); // in ascending order by default if(plane_out._n_3(2) < 0) { plane_out._n_3 = -plane_out._n_3; // upward pointing } success = true; } } return success; } 

Время в 37 микросекунд, устанавливающее плоскость до 1000 точек (Windows 7, i7, 32-разрядная программа)

введите описание изображения здесь

 CGAL::linear_least_squares_fitting_3 

Функция linear_least_squares_fitting_3 вычисляет наилучшую подходящую 3D-линию или плоскость (в смысле наименьших квадратов) набора трехмерных объектов, таких как точки, сегменты, треугольники, сферы, шары, кубоиды или тетраэдры.

http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Principal_component_analysis_ref/Function_linear_least_squares_fitting_3.html

Уравнение для плоскости равно: ax + на + c = z. Поэтому настройте такие матрицы со всеми вашими данными:

  x_0 y_0 1 A = x_1 y_1 1 ... x_n y_n 1 

А также

  ax = bc 

А также

  z_0 B = z_1 ... z_n 

Другими словами: Ax = B. Теперь решим для x, которые являются вашими коэффициентами. Но поскольку (я полагаю) у вас более 3 баллов, система переопределена, поэтому вам нужно использовать левый псевдо-обратный. Итак, ответ:

 ab = (A^TA)^-1 A^TB c 

И вот какой-то простой код Python с примером:

 import matplotlib.pyplot as plt from mpl_toolkits.mplot3d import Axes3D import numpy as np N_POINTS = 10 TARGET_X_SLOPE = 2 TARGET_y_SLOPE = 3 TARGET_OFFSET = 5 EXTENTS = 5 NOISE = 5 # create random data xs = [np.random.uniform(2*EXTENTS)-EXTENTS for i in range(N_POINTS)] ys = [np.random.uniform(2*EXTENTS)-EXTENTS for i in range(N_POINTS)] zs = [] for i in range(N_POINTS): zs.append(xs[i]*TARGET_X_SLOPE + \ ys[i]*TARGET_y_SLOPE + \ TARGET_OFFSET + np.random.normal(scale=NOISE)) # plot raw data plt.figure() ax = plt.subplot(111, projection='3d') ax.scatter(xs, ys, zs, color='b') # do fit tmp_A = [] tmp_b = [] for i in range(len(xs)): tmp_A.append([xs[i], ys[i], 1]) tmp_b.append(zs[i]) b = np.matrix(tmp_b).T A = np.matrix(tmp_A) fit = (AT * A).I * AT * b errors = b - A * fit residual = np.linalg.norm(errors) print "solution:" print "%fx + %fy + %f = z" % (fit[0], fit[1], fit[2]) print "errors:" print errors print "residual:" print residual # plot plane xlim = ax.get_xlim() ylim = ax.get_ylim() X,Y = np.meshgrid(np.arange(xlim[0], xlim[1]), np.arange(ylim[0], ylim[1])) Z = np.zeros(X.shape) for r in range(X.shape[0]): for c in range(X.shape[1]): Z[r,c] = fit[0] * X[r,c] + fit[1] * Y[r,c] + fit[2] ax.plot_wireframe(X,Y,Z, color='k') ax.set_xlabel('x') ax.set_ylabel('y') ax.set_zlabel('z') plt.show() 

установленная плоскость

Все, что вам нужно сделать, это решить систему уравнений.

Если это ваши очки: (1, 2, 3), (4, 5, 6), (7, 8, 9)

Это дает вам уравнения:

 3=a*1 + b*2 + c 6=a*4 + b*5 + c 9=a*7 + b*8 + c 

Итак, ваш вопрос на самом деле должен быть: как я могу решить систему уравнений?

Поэтому я рекомендую прочитать этот вопрос.

Если я неправильно понял ваш вопрос, дайте нам знать.

EDIT :

Игнорируйте мой ответ, поскольку вы, вероятно, имели в виду что-то еще.

Похоже, все, что вы хотите сделать, это линейная регрессия с двумя регрессорами. Страница википедии по этому вопросу должна рассказать вам все, что вам нужно знать, а затем и некоторые.

Это сводится к проблеме « Всего наименьших квадратов» , которая может быть решена с помощью разложения SVD .

Код C ++ с использованием OpenCV:

 float fitPlaneToSetOfPoints(const std::vector &pts, cv::Point3f &p0, cv::Vec3f &nml) { const int SCALAR_TYPE = CV_32F; typedef float ScalarType; // Calculate centroid p0 = cv::Point3f(0,0,0); for (int i = 0; i < pts.size(); ++i) p0 = p0 + conv(pts[i]); p0 *= 1.0/pts.size(); // Compose data matrix subtracting the centroid from each point cv::Mat Q(pts.size(), 3, SCALAR_TYPE); for (int i = 0; i < pts.size(); ++i) { Q.at(i,0) = pts[i].x - p0.x; Q.at(i,1) = pts[i].y - p0.y; Q.at(i,2) = pts[i].z - p0.z; } // Compute SVD decomposition and the Total Least Squares solution, which is the eigenvector corresponding to the least eigenvalue cv::SVD svd(Q, cv::SVD::MODIFY_A|cv::SVD::FULL_UV); nml = svd.vt.row(2); // Calculate the actual RMS error float err = 0; for (int i = 0; i < pts.size(); ++i) err += powf(nml.dot(pts[i] - p0), 2); err = sqrtf(err / pts.size()); return err; } 
  • Есть ли встроенная функция для поиска режима?
  • Как затенять область под кривой, используя ggplot2
  • Создание равномерного распределения INTEGERS в C
  • Какой лучший способ сортировать по 5-звездочному рейтингу?
  • Вычисление среднего арифметического (один тип среднего) в Python
  • Interesting Posts

    isValidFragment Android API 19

    Использование компьютера Windows в качестве устройства ввода Bluetooth для другого компьютера / устройства

    Где я могу найти API-интерфейс для Firebase Cloud Messaging?

    Могу ли я остановить OSX от создания файлов .DS_Store / ._blah везде на NTFS?

    Может ли сильная именования сборки использоваться для проверки автора сборки?

    Является ли R применимым к семейству больше, чем синтаксический сахар?

    Как разрешить совместное использование ресурсов (CORS) в среде express.js на узле.js

    Как узнать, завершен ли загруженный ISO?

    показать значок в панели действий / панели инструментов с помощью AppCompat-v7 21

    Разработка игры типа Robocode с .Net для назначения школы

    Добавление элементов панели управления в Windows 8.1 Search

    findViewById () возвращает null, когда я вызываю его в onCreate ()

    Невозможно получить доступ к нестационарному члену внешнего типа через вложенный тип

    Когда использовать Xamarin.Forms vs Xamarin Native?

    Поиск в Windows 7 не работает в папке Google Диска

    Давайте будем гением компьютера.