Разработка алгоритма: отслеживание движущихся точек в трехмерном пространстве
Это вопрос, не зависящий от языка, он больше ориентирован на разработку алгоритмов.
Представьте, что у нас есть два массива точек в трехмерном пространстве (каждый выглядит как [(1, 0, 2), (2, 4, 32), ...]).
Первый массив представляет первое состояние точек, а второй представляет более позднее состояние, когда точки сдвинулись на небольшую величину (не обязательно каждая на одинаковое расстояние). Примечание: Некоторые точки могли быть удалены и добавлены новые во втором состоянии.
Проблема: Учитывая эти два массива, как можно сопоставить (с разумной степенью точности) каждую сдвинутую точку с ее исходной точкой, а также определить, какие точки являются новыми и не существовали в первом состоянии?
Идеи: Я думал, что можно применить какую-то кластеризацию k-средних, но я не уверен, как она справится с тем фактом, что некоторые точки могли быть удалены / добавлены между состояниями - поэтому я не думаю, что этот подход работать хорошо.
Редактировать:
Точки не обязательно добавляются в какое-либо конкретное место в массиве, и порядок не обязательно сохраняется для сохраняющихся точек между состояниями. Расстояние, на которое точки смещаются между состояниями, должно быть относительно небольшим по сравнению с расстоянием между уникальными точками - иначе эта проблема принципиально невозможна.
@TedHopp См. Правки.
Тогда кажется, что поиск ближайшего соседа может быть самым простым подходом. См. эта ветка, если вы хотите пойти по этому маршруту. Для других подходов взгляните на алгоритмы регистрация набора точек (a.k.a. совпадение точек).
@TedHopp, поскольку движения точек полностью случайны, вы можете довольно легко оказаться в ситуации, когда копия точки A внезапно окажется ближе к точке B, чем копия точки B, разрушая подход ближайший сосед.
@FDavidov - ОП указал, что масштаб движения «относительно мал» по сравнению с расстоянием между точками. Следовательно, описанной вами ситуации не должно быть.
@TedHopp, если вы подождете достаточно долго, это, безусловно, может произойти.
@FDavidov - Это не имеет смысла в контексте того, что описал OP. Вам даны два массива точек, которые являются снимками меняющейся совокупности точек. OP заявляет, что эти снимки удовлетворяют условию, что все перемещения точек малы по сравнению с расстоянием между точками. Нет такой вещи, как ожидание, тем более «ждать достаточно долго». OP запрашивает алгоритм для решения этого конкретного случая.
@TedHopp, пожалуйста, перечитайте вопрос: Первый массив представляет первое состояние точек и, следовательно, не развивается. Только второй массив эволюционирует с новыми точками и позициями.
@FDavidov - Второй массив не развивается. Это состояние после того, как произошла любая эволюция, и любые изменения, происходящие между двумя состояниями, удовлетворяют условию «малого движения». Кажется, вы воображаете, что алгоритм будет выполняться неоднократно, поскольку первый массив остается фиксированным, а второй массив продолжает изменяться, но это то, что вы внесли в проблему. В вопросе OP нет ничего подобного.
@TedHopp Хорошо, давайте предположим, что вы начинаете с точек п, так что расстояние между любой парой из них составляет не менее 5 метров. Теперь переместите их не более чем на 1 см в любом направлении. Видите ли вы какие-нибудь проблемы с отслеживанием их передвижения? Конечно нет!!! Поэтому представляется разумным предположить, что движение продолжится. Если мое предположение неверно, то реальной проблемы, которую нужно решать, нет. Ты бы согласился с этим?
@FDavidov - Ваше "Конечно, нет !!!" это именно то, о чем спрашивает OP. Проблема состоит в том, чтобы точно сопоставить соответствующие точки после небольшого возмущения набора точек. На самом деле это реальная проблема, потому что точки могли исчезнуть, могли появиться новые точки (предположительно, относительно далеко от существующих точек), а оставшиеся точки могут не иметь того же индекса в двух массивах. OP запрашивает алгоритм для работы с этим конкретным сценарием. Эффективно решить эту задачу нетривиально, особенно если она связана с большим количеством точек.
звучит так, будто RANSAC - это то, что вы ищете ... также это может помочь: Созданы лишние звезды, как от них избавиться?
Предположительно точки - это измерения чего-то. Без подробностей измерения и того, что есть что-то, а также некоторых деталей того, как они себя ведут, трудно ответить. Ответ будет совершенно другим, если, например, вы измеряете статические точки, идентифицированные с помощью обнаружения объектов, но движущейся камерой (поэтому измерения будут неточными, и ожидается, что точки будут двигаться только относительно камеры) или если у вас есть идеальные (или почти идеальные) GPS-местоположения людей, которые ходят вокруг и хотят отслеживать отдельных людей.
Я думаю, OP должен попытаться предоставить разумные предположения упрощения; например: разумно ли предположить, что все точки движутся в одном общем направлении с почти одинаковой скоростью (своего рода поток)? Если нет, можно ли предположить, что они делают это локально (своего рода водоворот)?
Ответы 3
При предположении, что:
- Точки могут смещаться под произвольным углом и длиной,
- Очки могут исчезнуть случайным образом,
- Очки могут добавляться случайным образом и в случайных местах,
- Точки (в каждом массиве) определяются исключительно своими координатами без какого-либо идентификатора.
Если все вышеперечисленное верно, не существует решения, которое могло бы обеспечить разумный уровень надежности.
Я могу добавить множество примеров, подтверждающих мое утверждение, но оно выглядит довольно интуитивно понятным и, следовательно, в действительности не требуется.
РЕДАКТИРОВАТЬ:
После обсуждения с Тедом Хоппом я предлагаю альтернативный подход, основанный на два ВСТАВЛЕННЫХ КРИТИЧЕСКИХ допущения:
- Точки перемещаются один раз и только один раз,
- Можно утверждать, что минимальное начальное расстояние между любыми двумя точками известно, назовем его
Lmin, а максимальное расстояние любого движения <<LMinи назовем егоMmax.
С этими двумя дополнительными предположениями вы можете представить себе механизм следующим образом (код, подобный JavaScript - не проверено!):
for (i = 0 ; i < Points.Count ; i++) {
for (j = i + 1 ; j < Points.Count ; j++) {
if ((ABS(Array1[i].x - Array2[j].x) > Mmax ) ||
(ABS(Array1[i].y - Array2[j].y) > Mmax ) ||
(ABS(Array1[i].z - Array2[j].z) > Mmax ) ) {
// Distance between two points is for sure equal or bigger than max.
continue ; // Meaning, go to check next point.
}
// The check of the distance is split into two stages
// because, if the first if is true, the actual distance
// calculation is not needed (and hence time is saved).
if (Distance_Between_Points(Array1[i],Array2[j]) > Mmax) {
// Distance between two points is for sure bigger than max.
continue ; // Meaning, go to check next point.
}
// Points appear to be related!!!!!!
..........
}
}
Несколько исправлений, точки, скорее всего, исчезнут у границ трехмерного пространства (хотя они могут исчезнуть и в середине). Точки могут перемещаться на произвольную длину и под любым углом, но всегда будут перемещаться на очень небольшое расстояние по сравнению с относительным расстоянием между уникальными точками. Я знаю, что эта задача возможна теоретически (можно было бы сделать это интуитивно, глядя на два представления точек - мне просто нужен достаточно эффективный и точный алгоритм, чтобы сделать то же самое)
Это уточнение не сильно меняет представленный вывод. Представьте себе две точки, которые медленно двигались в направлении друг друга. На каком-то этапе обе точки исчезают, и новая точка появляется в середине местоположения двух исчезающих точек. Алгоритм ошибочно свяжет новую точку (по крайней мере) с одной из двух исходных точек. Опять же, как уже говорилось, просто выберите случайное число от 1 до 1000, и я дам вам то количество примеров, которые сделают алгоритм ненадежным. Единственная возможность - добавить к правилам некоторые ограничения.
Еще одна вещь: прежде чем пытаться найти решение в 3D, посмотрите, сможете ли вы найти его в одном измерении. Если правила одинаковы, у вас все равно не будет надежного решения, если, например, точки не имеют некоторого имущество, который позволяет различать (например, ID).
Вместо того, чтобы делать предположения, которые приводят к выводу об отсутствии решения, более продуктивным подходом было бы введение предположений (ограничений проблемы), которые позволяют найти решение.
@TedHopp, я согласен и, следовательно, последнее предложение моего предыдущего комментария. OP должен добавлять ограничение, а не я (или кто-либо еще), поскольку только OP точно знает детали проблемы. Кроме того, предположим, что вы пытаетесь решить неразрешимую проблему, разве вам не нравится, что кто-то говорит вам, что вы зря тратите время? Твердое «НЕТ» иногда является лучшим ответом, на который можно надеяться.
Ваше твердое «НЕТ» относится к проблеме, о которой OP не спрашивал.
@TedHopp. Пожалуйста, прочтите мой ответ на ваш последний комментарий под исходным вопросом. Кроме того, я буду счастлив изменить или отклонить свой ответ после того, как ОП четко укажет, что я неправильно понял вопрос или изменил условия.
Это основано на одном предположении: расстояние сдвига очень мало (по существу, нечеткое измерение) по сравнению с расстоянием между уникальными точками между первым и вторым набором.
Во-первых, перенос, вращение или масштабирование существенно не влияют на общую структуру набора точек. Это дает вам довольно много вариантов.
Возьмите минимальное / максимальное значение для каждого измерения (x, y, z и т. д.). Переведите и измените масштаб двух наборов точек. Точное масштабирование не имеет значения, но вы можете пойти с ним так, чтобы все точки были положительными и находились в пределах от 0 до 100 в каждом измерении. Это позволяет сравнивать точки более последовательно. Хотя это может не быть строго необходимо и, скорее всего, его можно пропустить
Затем вы должны создать двунаправленное отображение (двунаправленный граф) между набором точек A и набором точек B, которое будет иметь вид O (| A | + | B |), где | A | и | B | размеры наборов.
Пример двунаправленного отображения:
a_to_b[(1.001,2.001)] = [(1.005,1.995)]b_to_a[(1.005,1.995)] = [(1.001,2.001)]
Если a_to_b и b_to_a сопоставляются друг с другом, то это одна и та же точка с относительно высокой вероятностью.
Если нет, то, скорее всего, вы увидите что-то вроде этого:
a_to_b[(1.001,2.007)] = [(1.005,1.995)]b_to_a[(1.005,1.995)] = [(1.500, 2.004)]
a_to_b[(1.500, 2.004)] = [(1.495, 2.009)]b_to_a[(1.495, 2.009)] = [(1.500, 2.004)]
Поскольку сопоставления 1-1 больше нет, это означает, что что-то было добавлено или удалено. Поскольку значение в a не было преобразовано обратно, оно, вероятно, было удалено. В противном случае, вероятно, было добавлено. Если он был добавлен, вы захотите повторно запустить алгоритм, чтобы попытаться определить исходную ближайшую точку.
Это можно проверить, посмотрев на другую точку и посмотрев, является ли она частью сопоставления 1-1 (и, следовательно, учтена). По сути, вы хотите учесть все точки сопоставления 1–1 (с высокой вероятностью быть одной и той же точкой), а затем попытаться отсортировать точки, которые не совпадают точно.
Вы можете захотеть получить триангуляцию Делоне для обоих наборов точек, чтобы найти ближайшего соседа для всех точек намного быстрее благодаря знанию того, какие точки пространственно смежны с данной точкой. Число ребер в графе Делоне, если я правильно помню, равно O (V), поэтому среднее число ребер на вершину равно O (1). Как только вы нашли ближайшую точку. Однако вам может потребоваться некоторая настройка делаунарных графов для учета добавленных / удаленных ребер.
Сопоставьте каждую точку с ближайшим соседом, если расстояние не превышает пороговое значение.
Если у вас есть более одного возможного совпадения, вам нужно разработать хорошую стратегию разрешения.
Считайте несовпадающие точки удаленными или добавленными.
Чтобы сделать это быстрее, поместите октодерево или файл сетки в свои данные, чтобы вам нужно было только тестировать соседние ячейки сетки, а не сравнивать каждую точку с каждой другой точкой.
Когда точки добавляются, добавляются ли они в конец массива или разбросаны внутри? Для точек, которые не добавляются или не удаляются, остаются ли они в одном и том же относительном порядке в двух массивах? Как расстояние, на которое могут перемещаться точки, соотносится в масштабе с расстоянием между точками?