25.04.2020 20:40
YakMik 7 1100 Источник

Постановка задачи


Рассмотрим задачу нахождения угла поворота и смещения облака точек. Под облаком точек подразумевается набор точек на плоскости, сохраняющие взаимное расположение друг от друга, при их пространственном перемещении.


Т.е. есть два набора точек: исходное облако и облако преобразованное произвольным образом в пространстве (см. Рис. 1). Любое преобразование облака точек в пространстве можно интерпретировать как поворот и смещение. Таким образом, необходимо определить на какой угол требуется повернуть исходное облако точек и на какое расстояние его передвинуть от исходного облака точек, чтобы получить то самое, преобразованное произвольным образом облако точек.



Рис. 1 Пример облака точек, к которому применен поворот на 15 градусов, и смещение по оси Х: 10, по оси Y: 30



Алгоритм


1. Определение смещения облака точек


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


Для нахождения центра масс необходимо просуммировать координаты всех точек, и поделить на общее количество точек.



$inline$x_c = \frac{\sum_{n=1}^{N}{x}}{N}; y_c = \frac{\sum_{n=1}^{N}{y}}{N}$inline$

Таким образом для рассмотренного выше примера: центр масс исходного облака точек (0;0) и центр масс преобразованного облака точек (10;30). Следовательно, смещение преобразованного облака точек относительно исходного облака точек по оси Х: 10, а по оси Y: 30.


2. Определение угла поворота облака точек


Для определения угла поворота необходимо построить ортонормированный базис исходного облака точек и ортонормированный базис повернутого облака точек (см. Рис 2). Угол поворота данного ортонормированного базиса преобразованного облака точек, относительно ортонормированного базиса исходного облака точек и будет углом поворота преобразованного облака точек относительно исходного облака точек. Угол поворота будет определен с точностью до 90 градусов, таким образом перебрав 4 варианта можно однозначно определить угол поворота.



Рис. 2 Ортонормированные базисы для исходного и повернутого облака точек


Для определения ортонормированного базиса, необходимо определить собственные вектора тензора инерции облака точек. Тензор инерции, матрица, элементами которой являются моменты инерции по осям.



$inline$\begin{equation*} I = \begin{pmatrix} I_{xx} & I_{xy}\\ I_{yx} & I_{yy}\\ \end{pmatrix} \end{equation*}$inline$

, где моменты инерции по осям:



$inline$I_{xx} = \sum_{n=1}^{N}{[(x - x_c)^2]}$inline$
$inline$I_{xy} = \sum_{n=1}^{N}{[(x - x_c)(y - y_c)]}$inline$
$inline$I_{yx} = \sum_{n=1}^{N}{[(x - x_c)(y - y_c)]}$inline$
$inline$I_{yy} = \sum_{n=1}^{N}{[(y - y_c)^2]}$inline$

Собственные вектора данного тензора инерции образуют ортонормированный базис.


Рассчитаем ортонормированные базисы для рассматриваемого примера:
— Исходное облако точек имеет следующий тензор инерции: (33334 0; 0 11667), а собственные вектора будут: (1; 0) и (0; 1), что соответствует углам поворота базиса в 0 и 90 градусов.
— Преобразованное облако точек имеет следующий тензор инерции: (31882.5 -54167.5; -54167.5 13118.4), а собственные вектора будут (0.9659 -0.2588) и (0.2588 0.9659), что соответствует углам поворота -15 градусов и 75 градусов.
Таким образом, угол поворота может быть 15, 105, 195 или 285 градусов. Методом перебора и оценки погрешности повернутого облака точек и исходного, получаем угол поворота в 15 градусов.


Исходники описанного алгоритма


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


Примеры использования



Рис. 3 Определение угла поворота и смещения трансформированного облака точек с добавленным смещением и погрешностью



Рис. 4 Определение угла поворота и смещения трансформированного облака точек с добавленным смещением



Рис. 5 Определение угла поворота и смещения трансформированного облака точек с добавленным смещением и погрешностью


Вывод


С помощью описанного выше способа можно определять угол поворота и смещение исходного облака точек, относительно другого. Которое получено с помощью какого либо пространственного перемещения исходного облака точек. Дополнительно, при наличии небольшой погрешности (нормального распределения), данный способ тоже устойчиво работает (см. Рис. 3 и Рис. 5).


Данный способ так же можно использовать в цифровой обработке изображений, когда необходимо определить пространственное расположение какого-либо объекта.


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