Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Постановка задачи
Рассмотрим задачу нахождения угла поворота и смещения облака точек. Под облаком точек подразумевается набор точек на плоскости, сохраняющие взаимное расположение друг от друга, при их пространственном перемещении.
Т.е. есть два набора точек: исходное облако и облако преобразованное произвольным образом в пространстве (см. Рис. 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).
Данный способ так же можно использовать в цифровой обработке изображений, когда необходимо определить пространственное расположение какого-либо объекта.
Основная мысль данной статьи, чтобы читатель сходу мог применить описанный способ, если когда-нибудь столкнется с подобной задачей, и не тратил на это время.
