Определение параметров трансформации облака точек

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

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

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

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

Алгоритм

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

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

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

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

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

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

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

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

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

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

Рассчитаем ортонормированные базисы для рассматриваемого примера:
— Исходное облако точек имеет следующий тензор инерции: (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).

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

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