Как определить путь по зашумленным данным X, Y

StackOverflow https://stackoverflow.com/questions/240473

Вопрос

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

Это похоже на то, как вы использовали бы алгоритм линейной подгонки для выбора аппроксимации линейных данных.Моя проблема только сложнее, потому что путь изгибается и петляет по всему миру.альтернативный текст http://www.praeclarum.org/so/pathfinder.png

Кто-нибудь знает какие-либо стандартные / надежные / простые для понимания алгоритмы для достижения этой цели?

Q&A:

Что вы подразумеваете под шумным? Если бы у меня была идеальная реализация пути, то мой набор точек был бы выбран из этого идеального пути с добавлением гауссовского шума к элементам X и Y.Я не знаю среднего значения или стандартного отклонения этого шума.Возможно, я смогу догадаться о std-разработчике...

Лежат ли точки рядом, но не на каком-то идеальном, но сложном пути, который вы пытаетесь приблизить? ДА.

Есть ли у вас какая-либо априорная информация о форме пути?Есть какой-нибудь другой способ получить такую информацию? К сожалению, нет.

Это было полезно?

Решение

Имея несортированный список, вы на самом деле не будете знать, какие точки включить в каждый сегмент, поэтому, я думаю, вы могли бы просто выбрать ближайшую точку.

Одним из способов может быть случайный выбор начальной точки и выбор ближайшей точки в качестве следующей точки на каждом шаге.Добавьте первые две точки к набору S.

Подгоняйте линию к точкам в S до тех пор, пока среднеквадратичное значение не превысит некоторого значения, затем очистите S и начните новую линию.

Пересечение последовательных линий будет конечными точками сегментов.

Другие советы

Интерполяция Безье может соответствовать вашей проблеме.

Bezier Interpolation

Однако это не затрагивает порядок расположения точек в контуре;существует ряд подходов, которые следует рассмотреть:

  • Любой "оптимальный" тип пути (например,наименьшее изменение направления в каждой точке пути, * Кратчайший путь через все точки), вероятно, сведет к завершению NP Проблема с Коммивояжером (ЧАЙНАЯ ложка).
  • "Разумный" путь для кластеризации узлов, а затем маршрут между кластерами и внутри кластеров.Конечно, чем больше кластер или чем больше количество кластеров, тем больше эта небольшая проблема похожа на большое n TSP.
  • Упорядочивание точек по одной оси.Если осей намного больше, чем 2, некоторые уменьшение размеров стратегия может быть полезной.например ,Независимый Компонентный анализ.

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

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

Это ваш выбор, если точка находится слишком далеко для создания прямых линий.

Далее вы должны знать, нужно ли вам "посетить" каждую точку или просто нужно подойти поближе, и насколько близко это "рядом" находится.

Если вам нужно отправить курс (ы) самолету, кораблю или другому путешественнику, вам, вероятно, нужно посетить каждый пункт.Если вы получаете данные GPS от объекта, вы, вероятно, просто хотите проложить курс на экране и убрать шум.

После просмотра ваших правок: Если это объект, перемещающий какой-либо объект, который вы хотите отобразить на графике, возможно, вам захочется сгладить направление и скорость вместо значений x / y.(Если ваши измеренные значения (x) будут иметь фиксированный и увеличивающийся интервал Y, сглаживание будет намного проще.)

Вот эвристический взлом, который может решить проблему упорядочения данных, если

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

Действуйте следующим образом:

  1. Выберите (надеюсь, осмысленным, а не случайным образом) отправную точку, р1.
  2. Найдите все точки, которые лежат в пределах некоторого расстояния кластеризации, r_c из р1.Выбирай r_c маленький по сравнению с ожидаемым радиусом поворота, но большой по сравнению с разбросом.
  3. Назовите этот кластер C1.
  4. Найти точку q1 среднее число позиций в C1.
  5. Подогнать линию к точкам в C1 и проецируйте на край кластера (или сразу за ним) и найдите ближайшую точку в ваших исходных данных.Обозначьте эту точку р2.
  6. Повторяйте шаги 2-5 до тех пор, пока у вас не закончатся данные.

Теперь у вас есть новый список баллов q1..qn которые упорядочены.

Навскидку, очень грубо, и работает только при довольно хороших условиях...

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

Проблема с кривой Безье заключается в том, что на самом деле она не проходит через точки, которые вы выбрали, и даже несмотря на то, что выборки точек немного искажены;кривая Безье на самом деле может находиться в нескольких милях отсюда.

Лучшее приближение и решение, которое, по-видимому, намного лучше напоминает исходное изображение, - это Сплайн Catmull-Rom потому что он действительно проходит через все точки кривой.

Мой подход состоял бы в том, чтобы сначала отсортировать ваш список точек, затем использовать кривую Безье.

Хитрость, конечно, в сортировке.Начните с одной случайной точки и найдите ближайшую точку.Предположим, что эти два понятия связаны.Используя эти две конечные точки, найдите ближайшие к ним точки.Предположим, что тот, у которого расстояние до конечной точки меньше, подключен к этой точке.Повторяйте до тех пор, пока все точки не будут соединены.

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

Редактировать: Вы можете проделать это несколько раз с разными начальными точками, а затем посмотреть, в чем отличаются результаты.Это, по крайней мере, дает вам некоторую уверенность в том, какие точки связаны друг с другом.

Совершенно другой подход, который не требует другого ограничения, но детали могут зависеть от вашего приложения.Это должно работать лучше всего, если у вас есть "плотное облако точек" вокруг контура.

Используйте функцию "стоимость", которая определяет разницу между кривой и облаком точек.Используйте параметризованную кривую и стандартный алгоритм оптимизации.- ИЛИ - Начните с прямой кривой от начала до конца, затем используйте генетический алгоритм для ее модификации.

Типичная функция затрат состояла бы в том, чтобы взять наименьшее расстояние между каждой точкой и кривой и суммировать квадраты.

У меня недостаточно опыта, чтобы предложить оптимизацию или генетический алгоритм, но я уверен, что это можно сделать :)

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

  1. Для каждого сегмента, если rnd() < x, в середине вводится новая путевая точка.
  2. Для каждой путевой точки координаты X и Y немного изменяются.

Вам нужно будет включить общую длину в функцию стоимости.Разделение может не потребоваться, или, возможно, x ("вероятность разделения") может потребоваться уменьшить по мере ввода большего количества путевых точек.Вы можете захотеть применить (2) к начальной и конечной точкам, а можете и не захотеть.

Было бы забавно попробовать это...

Я так понимаю, что "несортированный список" означает, что, хотя ваш набор пунктов завершен, вы не знаете, в каком порядке они были пройдены?

Гауссовский шум должен быть в основном проигнорирован.Нам не предоставляется абсолютно никакой информации, которая позволила бы нам предпринять какие-либо попытки реконструировать исходный, не зашумленный путь.Поэтому я думаю, что лучшее, что мы можем сделать, это предположить, что пункты верны.

На данном этапе задача состоит в том, чтобы "найти наилучший путь через множество точек", причем слово "наилучший" остается расплывчатым.Я на скорую руку разработал некоторый код, который пытается упорядочить набор точек в евклидовом пространстве, предпочитая упорядочения, которые приводят к более прямым линиям.Хотя метрику было легко реализовать, я не мог придумать хорошего способа улучшить порядок на основе этого, поэтому я просто случайным образом меняю местами точки в поисках лучшего расположения.

Итак, вот некоторый код PLT Scheme, который делает это.

#lang scheme

(require (only-in srfi/1 iota))

; a bunch of trig
(define (deg->rad d)
  (* pi (/ d 180)))

(define (rad->deg r)
  (* 180 (/ r pi)))

(define (euclidean-length v)
  (sqrt (apply + (map (lambda (x) (expt x 2)) v))))

(define (dot a b)
  (apply + (map * a b)))

(define (angle-ratio a b)
  (/ (dot a b)
     (* (euclidean-length a) (euclidean-length b))))

; given a list of 3 points, calculate the likelihood of the
; angle they represent. straight is better.
(define (probability-triple a b c)
  (let ([av (map - a b)]
        [bv (map - c b)])
    (cos (/ (- pi (abs (acos (angle-ratio av bv)))) 2))))

; makes a random 2d point. uncomment the bit for a 3d point
(define (random-point . x)
  (list (/ (random 1000) 100)
        (/ (random 1000) 100)
        #;(/ (random 1000) 100)))

; calculate the likelihood of an entire list of points
(define (point-order-likelihood lst)
  (if (null? (cdddr lst))
      1
      (* (probability-triple (car lst)
                             (cadr lst)
                             (caddr lst))
         (point-order-likelihood (cdr lst)))))

; just print a list of points
(define (print-points lst)
  (for ([p (in-list lst)])
    (printf "~a~n"
            (string-join (map number->string
                              (map exact->inexact p))
                         " "))))

; attempts to improve upon a list
(define (find-better-arrangement start
                                 ; by default, try only 10 times to find something better
                                 [tries 10]
                                 ; if we find an arrangement that is as good as one where
                                 ; every segment bends by 22.5 degrees (which would be
                                 ; reasonably gentle) then call it good enough. higher
                                 ; cut offs are more demanding.
                                 [cut-off (expt (cos (/ pi 8))
                                                (- (length start) 2))])
  (let ([vec (list->vector start)]
        ; evaluate what we've started with
        [eval (point-order-likelihood start)])
    (let/ec done
      ; if the current list exceeds the cut off, we're done
      (when (> eval cut-off)
        (done start))
      ; otherwise, try no more than 'tries' times...
      (for ([x (in-range tries)])
        ; pick two random points in the list
        (let ([ai (random (vector-length vec))]
              [bi (random (vector-length vec))])
          ; if they're the same...
          (when (= ai bi)
            ; increment the second by 1, wrapping around the list if necessary
            (set! bi (modulo (add1 bi) (vector-length vec))))
          ; take the values from the two positions...
          (let ([a  (vector-ref vec ai)]
                [b  (vector-ref vec bi)])
            ; swap them
            (vector-set! vec bi a)
            (vector-set! vec ai b)
            ; make a list out of the vector
            (let ([new (vector->list vec)])
              ; if it evaluates to better
              (when (> (point-order-likelihood new) eval)
                ; start over with it
                (done (find-better-arrangement new tries cut-off)))))))
      ; we fell out the bottom of the search. just give back what we started with
      start)))

; evaluate, display, and improve a list of points, five times
(define points (map random-point (iota 10)))
(define tmp points)
(printf "~a~n" (point-order-likelihood tmp))
(print-points tmp)
(set! tmp (find-better-arrangement tmp 10))
(printf "~a~n" (point-order-likelihood tmp))
(print-points tmp)
(set! tmp (find-better-arrangement tmp 100))
(printf "~a~n" (point-order-likelihood tmp))
(print-points tmp)
(set! tmp (find-better-arrangement tmp 1000))
(printf "~a~n" (point-order-likelihood tmp))
(print-points tmp)
(set! tmp (find-better-arrangement tmp 10000))
(printf "~a~n" (point-order-likelihood tmp))
(print-points tmp)

Похоже, что вы знаете "золотую кривую" из ваших ответов на вопросы, я бы предложил найти кривую Безье "золотой кривой", как предложил @jamesh, и нарисовать ее.

Сколько у вас очков?
Кривая Безье, как уже упоминалось, является хорошей идеей, если у вас сравнительно мало точек.Если у вас много точек, создавайте кластеры, как предлагает dmckee.

Однако вы также нужно другое ограничение для определения порядка расположения точек.Было много хороших предложений о том, как выбрать точки, но если вы не введете другое ограничение, любое из них даст возможное решение.

Возможные ограничения, о которых я могу думать:

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top