Выравнивание облаков точек с использованием анализа основных компонентов с помощью CGAL - PullRequest
Новая
       29

Выравнивание облаков точек с использованием анализа основных компонентов с помощью CGAL

2 голосов
/ 30 марта 2011

У меня есть наборы случайно выбранных точек на поверхности трехмерных объектов. Я хочу быть в состоянии вычислить сходство между двумя различными объектами. Чтобы это работало, я сначала должен убедиться, что точки выборки обоих объектов, которые я хочу сравнить, имеют одинаковое вращение и масштаб. Я думал, что смогу сделать это, ориентируя оси главных компонентов вдоль осей x / y / z и масштабируя их так, чтобы самый длинный главный компонент имел единичную длину.

Сначала я вычисляю центр тяжести набора точек и перевожу все точки так, чтобы источник стал новым центроидом.

Я выполняю анализ главных компонентов, используя функцию CGAL linear_least_squares_fitting_3, которая дает лучшую плоскость подгонки через точки. Я вычисляю нормаль этой плоскости, взяв перекрестное произведение обоих базовых векторов: 

Plane plane;
linear_least_squares_fitting_3(points.begin(), points.end(), 
    plane, CGAL::Dimension_tag<0>());

auto dir1 = dir2vec(plane.base1().direction());
auto dir2 = dir2vec(plane.base2().direction());
auto normal = dir1 ^ dir2; // cross product
normal.normalize(); dir1.normalize(); dir2.normalize();

Функция dir2vec преобразует объект CGAL::Direction_3 в эквивалентный объект osg::Vec3d (я использую графический движок OpenSceneGraph). Наконец, я поворачиваю все по осям юнитов, используя следующий код: 

Matrixd r1, r2, r3;
r1.makeRotate(normal, Vec3d(1,0,0));
r2.makeRotate(dir1 * r1, Vec3d(0,1,0));
r3.makeRotate(dir2 * r1 * r2, Vec3d(0,0,1));
auto rotate = [&](Vec3d const &p) {
    return p * r1 * r2 * r3;
};
transform(osgPoints.begin(), osgPoints.end(), osgPoints.begin(), rotate);

Здесь osgPoints - это vector<osg::Vec3d>. В целях тестирования я перевожу центроид повернутых точек обратно в исходное положение, чтобы облака точек не перекрывались. 

Vec3d center = point2vec(centroid);
auto tocentroid = [&](Vec3d const &v) {
    return v + center;
};
transform(osgPoints.begin(), osgPoints.end(), osgPoints.begin(), tocentroid);

Чтобы проверить это, я использую две копии одного и того же набора точек, однако одна трансформируется (поворачивается и переводится). Приведенный выше код должен отменить повороты, однако результаты не соответствуют ожиданиям: см. это изображение . Красные линии обозначают базовые векторы наиболее подходящих плоскостей и их нормаль. Похоже, что результаты обоих вызовов linear_least_squares_fitting_3 дают немного разные ответы, так как одна из плоскостей немного повернута относительно другой.

Вот еще одно изображение, где оба объекта расположены с центром в центре. Теперь ясно видно, что нормали и базовые векторы падают вместе, а точки - нет.

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

Ответы [ 2 ]

3 голосов
/ 30 марта 2011

Подгонка плоскости к набору точек оставляет одну степень свободы неограниченной.Плоскость может свободно вращаться вокруг своей нормали, и посадка равна.Я ничего не знаю о CGAL, но я не удивлюсь, обнаружив, что они просто находят удобную плоскость при поиске подгонки (вероятно, ближайшую проекцию от исходных осей пространства).

Есливы сделали настоящий PCA на облаке точек, я не думаю, что у вас возникнет такая проблема.В качестве альтернативы, возможно, вы могли бы изменить масштаб (растянуть) ваши данные по нормали, обнаруженной алгоритмом подбора, а затем найти другую подгонку.Если вы достаточно растянете данные, то первая найденная плоскость будет не такой хорошей, как какая-либо ортогональная плоскость.

0 голосов
/ 31 марта 2011

Действительно, казалось, что CGAL не вычисляет все основные компоненты, как предложил JCooper.Я переключился на библиотеку ALGLIB для выполнения PCA, и теперь она работает.

...