Сравните трехмерные структуры
Если вы исправляете функцию сна, подобную этой
var sleep = function(period, decision, callback){
var interval = setInterval(function(){
if (decision()) {
interval = clearInterval(interval);
callback();
}
}, period);
}
, и у вас есть асинхронная функция для многократного вызова
var xhr = function(url, callback){
// make ajax request
// call callback when request fulfills
}
И вы настраиваете свой проект следующим образом:
var ready = false;
function xhr1(){
xhr(url1, function(){ ready = true;});
}
function xhr2(){
xhr(url2, function(){ ready = true; });
}
function xhr3(){
xhr(url3, function(){ ready = true; });
}
Тогда вы можете сделать это:
xhr1();
sleep(100, function(){ return done; }, xhr2);
sleep(100, function(){ return done; }, xhr3);
sleep(100, function(){ return done; }, function(){
// do more
});
Вместо бесконечного отступа обратного вызова, как это:
xhr(url1, function(){
xhr2(url2, function(){
xhr3(url3, function(){
// do more
});
});
});
7 ответов
Я бы сделал это следующим образом:
- Поместите наборы в центр масс
- Вычислите тензор инерции . Это дает вам три оси координат. Поверните к ним. [*]
- Запишите список точек в заданном порядке (например, сверху вниз, слева направо) с необходимой точностью.
- Примените любой алгоритм, который вы хотите, для результирующего массива.
Чтобы сравнить два набора, если вам не нужно заранее сохранять хеш-результаты, просто примените свой любимый алгоритм сравнения к наборам точек шага 3. Это может быть, например, вычисление расстояния между двумя наборами.
Я не уверен, могу ли я порекомендовать вам алгоритм для шага 4, поскольку кажется, что ваши требования противоречат друг другу. Все, что называется хешированием , обычно имеет свойство, заключающееся в том, что небольшое изменение входных данных приводит к очень разным выходным данным. В любом случае, теперь я свел проблему к массиву чисел, так что вы сможете во всем разобраться.
[*] Если две или три оси совпадают, выберите координаты каким-либо другим способом, например, как наибольшее расстояние. Но это крайне редко для случайных точек.
спиновых изображений являются одним из способов решения этой проблемы.
Seems like a numerical optimisation problem to me. You want to find the parameters of the transform which transforms one set of points to as close as possible by the other. Define some sort of residual or "energy" which is minimised when the points are coincident, and chuck it at some least-squares optimiser or similar. If it manages to optimise the score to zero (or as near as can be expected given floating point error) then the points are the same.
Googling
least squares rotation translation
turns up quite a few papers building on this technique (e.g "Least-Squares Estimation of Transformation Parameters Between Two Point Patterns").
Update following comment below: If a one-to-one correspondence between the points isn't known (as assumed by the paper above), then you just need to make sure the score being minimised is independent of point ordering. For example, if you treat the points as small masses (finite radius spheres to avoid zero-distance blowup) and set out to minimise the total gravitational energy of the system by optimising the translation & rotation parameters, that should work.
Там куча публикаций SIGGRAPH, которые могут оказаться полезными для вас.
например, «Глобальное нежесткое выравнивание 3-D сканирований» Брауна и Русинкевич:
http://scholar.google.com/scholar?q=siggraph+point+cloud+registration
Ваша первая мысль может быть связана с попыткой найти поворот, который отображает один объект на другой, но это очень сложная тема ... и на самом деле в этом нет необходимости! Вы не спрашиваете, как лучше всего сопоставить эти два, вы просто спрашиваете, совпадают они или нет.
Охарактеризуйте вашу модель списком всех расстояний между точками. Отсортируйте список по этому расстоянию. Теперь сравните список для каждого объекта. Они должны быть идентичными, так как на межточечные расстояния не влияет сдвиг или вращение.
Три проблемы:
1) Что, если количество точек велико, это большой список пар (N * (N-1) / 2). В этом случае вы можете оставить только самые длинные, или, что еще лучше, оставить 1 или 2 самых длинных для каждой вершины, чтобы каждая часть вашей модели вносила свой вклад. Однако удаление подобной информации меняет проблему на вероятностную, а не детерминированную.
2) При этом для определения формы используются только вершины, а не ребра. Это может быть хорошо (и на практике будет), но если вы ожидаете получить фигуры с одинаковыми вершинами, но с разными соединительными ребрами. Если это так, сначала проверьте сходство вершин. Если это пройдет, присвойте уникальную маркировку каждой вершине, используя это отсортированное расстояние. У самого длинного ребра две вершины. Для каждой из ЭТИХ вершин найдите вершину с самым длинным (оставшимся) ребром. Обозначьте первую вершину 0 и следующую вершину 1. Повторите по порядку для других вершин, и вам будут назначены теги, которые не зависят от сдвига и поворота. Теперь вы можете точно сравнить топологии ребер (убедитесь, что для каждого ребра в объекте 1 между двумя вершинами есть ' соответствующее ребро между теми же двумя вершинами в объекте 2) Примечание: это начинает становиться действительно сложным, если у вас есть несколько одинаковых расстояний между точками, и поэтому вам нужны сравнения для разрешения конфликтов, чтобы сделать назначения стабильными и уникальными.
3) Есть вероятность, что два фигуры имеют одинаковые длины ребер, но они не идентичны ... это верно, когда один объект является зеркальным отображением другого. Это довольно неприятно обнаруживать! Один из способов сделать это - использовать четыре некомпланарных точки (возможно, те, которые были помечены от 0 до 3 на предыдущем шаге) и сравнить «маневренность» системы координат, которую они определяют. Если рука не совпадает, объекты являются зеркальными отображениями.
Обратите внимание, что список расстояний позволяет легко отбрасывать неидентичные объекты. Он также позволяет добавлять "нечеткие" принятие, допуская определенную ошибку в заказах. Возможно, использование среднеквадратичной разницы между двумя списками в качестве «меры сходства» будет хорошо работать.
Изменить: Похоже, ваша проблема - облако точек без краев. Тогда раздражающая проблема соответствия краев (№2) даже не применима и ее можно игнорировать! Тем не менее, вы все равно должны быть осторожны с проблемой зеркального отображения №3.
Если вы хотите оценить жесткость преобразовать между двумя похожими облака точек можно использовать устоявшийся Итерационный метод ближайшей точки . Этот метод начинается с грубого оценка трансформации и затем итеративно оптимизирует преобразование, вычисляя ближайший соседей и минимизация связанная функция стоимости. Может быть эффективно реализовано (даже в реальном времени) и есть доступные реализации, доступные для matlab, c ++ ... Этот метод был расширен и имеет несколько вариантов, включая оценку нежестких деформации, если вам интересно в расширениях вы должны смотреть на Решение задач компьютерной графики проблема регистрации сканирования, где ваша проблема - решающий шаг. Для отправную точку см. Википедию страница в итеративной ближайшей точке который имеет несколько хороших внешних ссылки. Просто тизер из реализации Matlab , который был разработан для сопоставления с облаками точек:
(источник: mathworks.com )После согласования можно было окончательно мера ошибки, чтобы сказать, насколько похожи два облака точек есть, но это очень специальное решение, там должен быть лучше.
Используя дескрипторы формы , можно вычислить отпечатки пальцев форм, которые часто инвариантны относительно переводы / вращения. В большинстве случаев они определены для сеток, а не облаков точек, тем не менее, существует множество дескрипторов форм, поэтому в зависимости от ваших входных данных и требований вы можете найти что-то полезное. Для этого вам следует изучить область анализа формы , и, вероятно, презентация курса SIGGRAPH 2004 года может дать представление о том, что люди делают для вычисления дескрипторов формы.
Может быть, вам также стоит прочитать об алгоритме RANSAC. Он обычно используется для объединения панорамных изображений, что немного похоже на вашу проблему, только в двух измерениях. Просто введите в Google RANSAC, панораму и / или склейку, чтобы получить отправную точку.