Алгоритм для быстрого сравнения массивов и замены элементов с ближайшим значением. (Точки отслеживания)

Question

У меня есть два массива currPoints и prevPoints. Оба они не обязательно одинакового размера. Я хочу сравнить каждый элемент в currPoints с prevPoints и заменить значение в prevPoints, которое ближе всего к значению в currPoints.

Пример:

prevPoints{2,5,10,13,84,22} 
currPoints{1,15,9,99} 

После применения алгоритма

prevPoints{1,5,9,15,99,22} 

Так что это лучший алгоритм/метод для этого? Он должен быть быстрым.

Контекст: Если это помогает, я пытаюсь работать над алгоритмом отслеживания, который берет точки из двух последовательных кадров в видео и пытается выяснить, какие точки в первом кадре соответствуют точкам во втором кадре. Я надеюсь отслеживать объекты и пометить их идентификатором таким образом. Скорость имеет решающее значение, поскольку обработка должна выполняться в реальном времени.

Answer 1

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

Так после сортировки:

prevPoints{2,5,10,13,22,84} 
currPoints{1,9,15,99} 

Теперь вы в основном должны выяснить, какие из currPoints должен попасть в prevPoints. Алгоритм будет похож на слить 2 отсортированных массива, чтобы вы не слились, вместо этого замените значения.

Первоначально оба указателя находятся в начале соответствующих массивов. 1 из currpoints должно заменить 2 в prevPoints на основании того факта, что значение в currPoints меньше, чем prevPoints, и вы знаете, что следующие пункты в PrevPoints будут только выше 2 (отсортировано arry, помните). Замените и переместите указатели.

Теперь текущий указатель находится в точке 9, а превотор - в точке 5. Рассчитайте абсолютную разницу и сохраните запас минимальной абсолютной разности, обнаруженной до сих пор, а также значение числа, вызвавшего наименьшую абсолютную разницу (. 4 в этом случае). Переместите указатель вперед, когда указатель указывает на более высокое значение.

В настоящее время prevpointer at 10 и currpointer at 9. 9 меньше 10, и поэтому необходимо выполнить замену. Как это минимальная абсолютная разница меньше, чем раньше (1 < 4), так что 10 будет заменен 9.

Сейчас prevpointer находится на 13 и currpointer находится в 15

Действуйте таким же образом.

Перестройте массив prevPoints в исходную ориентацию.

Надеюсь, это поможет !!!

Answer 2

Мы сортируем первый список по положению x, а второй - по позициям y. Таким образом, каждый пункт имеет позицию в каждом списке. Теперь, как вы это делаете для поиска ближайшего соседа (по крайней мере, я придумал), вы находите позицию точки в каждом списке через двоичный поиск.Тогда мы знаем 4 направления, либо + -1 x, либо + -y, и в основном мы путешествуем в каждом из этих направлений до тех пор, пока лучшая длина пока не будет больше, чем расстояние от одной координаты.

Итак, мы ищем в каждом направлении. И скажем, что ближайшая точка находится на расстоянии 25, тогда, если наша следующая координата в направлении + X будет выше 25 только в направлении + X, мы можем остановиться, потому что, даже если изменение в Y равно 0, оно не может быть ближе.

Это обеспечивает очень эффективный и быстрый n (log (n)) алгоритм ближайшей точки, чтобы найти одну точку. Но также, поскольку нам нужны только два отсортированных списка, когда у нас есть те, что указаны в n (log (n)) времени, мы можем найти ближайшую точку для всех остальных точек в чем-то вроде log (n) времени. Найдите позицию в отсортированном списке x, найдите позицию в отсортированном списке y. Затем прокрутите до тех пор, пока вы не усечете и, несомненно, найдете ближайшую точку. Но, поскольку строительные леса одинаковы в каждом случае, они должны просто оказаться довольно быстрыми.

Несмотря на то, что данный фактический тестовый пример, вы можете придумать что-то, что является просто очень эффективной эвристикой.

---

Просто прослеживая точки кажется очень наивным, если мы трассировку то же самое от кадра к кадру он должен быть так, что точка от F0 до F1 в F2 должен быть фактически равна расстоянию он путешествовал в F0 - F1. Если мы предположим, что все эти точки перемещаются примерно по прямой, мы можем сделать гораздо лучшую работу, чем просто ближайшие точки. Обычно можно найти кривые, которые берут эти точки. Если мы предположим, что их позиция должна быть «F2» путем интерполяции F0 и F1 и низкого уровня, и вот позиция точки действительно очень близка. Тогда мы можем быть совершенно уверены, что мы пригвоздили это.

В равной степени объекты, которые можно было бы предположить, имеют все точки, перемещаемые примерно в одном направлении. Как и каждое перемещение точек + 5, + 5 от F0 до F1, мы не только можем угадать их позиции F2, но мы можем знать, что эти объекты довольно эффективно составляют один и тот же объект.