如何从嘈杂的 X、Y 数据确定路径

Question

如何从嘈杂的 X、Y 数据确定路径

9

我有一组未排序的嘈杂的X，Y点。然而，它们在世界中形成了一条路径。我想使用线段的近似数据来绘制这些数据的算法。

这类似于如何使用线拟合算法来选择线性数据的近似值。我的问题只是更难，因为路径弯曲并围绕着世界旋转。 alt text http://www.praeclarum.org/so/pathfinder.png 有人知道任何标准/稳健/易于理解的算法来完成这个任务吗？

问答：

你所说的“嘈杂”是什么意思？如果我有一个理想的路径实现，那么我的点集将从该理想路径中采样，并添加高斯噪声到X和Y元素。我不知道该噪声的平均值或标准偏差。我可能能够猜测标准偏差...

这些点是否靠近但不在某个理想但复杂的路径上，你试图对其进行近似？是的。

你是否具有关于路径形状的先验信息？获取此类信息的其他方法？不幸的是没有。

- Frank Krueger

路径已经设定，还是算法必须找出最佳路径？ - jamesh

你的问题还没有明确定义。你所说的“嘈杂”是什么意思？这些点是否靠近但不在某个理想但复杂的路径上，而你试图去逼近它？你有关于路径形状的任何先验信息吗？还有其他获取此类信息的方法吗？ - dmckee --- ex-moderator kitten

1

这些点有顺序吗？点的顺序是否随着 x、y 数据保存？ - Brad Gilbert

如果你找到了解决方案，我会很好奇的，这听起来像是一个“有趣”的问题。 - peterchen

如果您的点不是未排序的，那么这将是一个跟踪问题，我建议使用卡尔曼滤波器之类的方法。你能否更具体地说明什么是可以接受或者好的答案？例如，线条是否应该从给定的点开始和结束，或者路径是否应该是“平滑”的？ - ellisbben

显示剩余2条评论

10个回答

4

使用未排序的列表，您将不知道每个部分应包含哪些点，因此我想您可以选择最接近的点。一种方法是随机选择一个起始点，并在每个步骤中选择最近的点作为下一个点。将前两个点添加到集合S中。对S中的点拟合一条直线，直到RMS超过某个值，然后清除S并开始新的一行。连续线的交点将是段的端点。

- jakber

如果样本之间的距离与散点相比较大，并且曲线既不自交也不比采样尺度更接近自身，则这将很好地工作... - dmckee --- ex-moderator kitten

我可以预见到这个方法可能会出现几个问题。在任何有一定噪声的系统中，如果只使用RMS作为适应度的衡量标准，那么平滑曲线将很难与数据的噪声部分区分开来。此外，在算法的后期，当你到达真正路径的末尾并开始发现最近的点偏离时，很容易“错过”一些异常点（即距离它们的邻居更远，而邻居之间的距离则更近）。 - Clueless

2

如果您的点彼此靠近，则可以使用普通的“直线”（正交线）（orthogonal lines）。使用常规平滑算法。您可以将世界看作是平面的。

如果它们相距很远，您需要通过使用大圆从一个点导航到另一个点来补偿地球的弯曲。否则，您的直线将走更长的路。

如果某个点太远而无法创建直线，则由您决定。

此外，您还需要知道是否需要“访问”每个点，或者只需要靠近，并且靠近的程度如何。

如果您需要将航线发送给飞机、船只或其他旅行者，则可能需要访问每个点。如果您从对象获取GPS数据，则可能只想在屏幕上绘制航线并消除噪音。

看到您的编辑后：如果这是一个移动某些轨迹需要绘制的对象，您可能希望平滑方向和速度，而不是x/y值。（使您测量的值（x）具有固定且递增的Y间隔会使平滑变得更容易。）

- GvS

2

这里有一个启发式的技巧，可以解决数据排序问题，如果：

你有足够多的点
点之间的平均距离与路径预期的最小曲率半径相比很小
点之间的平均距离与噪声的标准偏差相比不是很大
路径没有自交（你可能会很幸运，但不能保证）

请按照以下步骤进行：

选择一个起始点p1（最好是有意义的，而不是随机的）。
查找所有位于聚类距离r_c内的点，选择r_c较小，但比散布要大的期望转弯半径。
将这个聚类称为C1。
找到C1中位置的平均值q1。
拟合C1中的点并将其投影到聚类的边缘（或者刚好超出边缘），并在原始数据中找到最近的点。将该点标记为p2。
重复步骤2-5，直到数据用完为止。

现在你有一个新的点列表q1..qn，已经排序。

这是一个非常粗略的方法，只能在相当好的条件下使用...

自交行为可能可以通过在步骤（5）中要求新的投影线与前一条线之间的最大角度来改善。

- dmckee

2

Bezier曲线的问题在于它实际上并没有通过你所采样的点，即使这些采样点稍微有些扭曲；而贝塞尔曲线可能会相差很远。

更好的逼近方法，也是一种似乎更好地类似于原始图像的解决方案是使用Catmull-Rom样条曲线，因为它确实通过曲线中的所有点。

- Jasper Bekkers

1

我理解“未排序列表”是说，虽然你的点集是完整的，但你不知道它们穿过的顺序是什么？

高斯噪声基本上必须被忽略。我们没有任何信息可以尝试重建原始的、无噪声的路径。因此，我认为我们能做的最好的事情就是假设这些点是正确的。

此时，任务就是“在一系列点中找到最佳路径”，其中“最佳”朦胧不清。我编写了一些代码，尝试在欧几里得空间中对一组点进行排序，更喜欢导致直线更直的排序。虽然度量很容易实现，但我想不出一个基于它来改进排序的好办法，所以我只是随机交换点，寻找更好的排列。

因此，这里是一些 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)

- Jay

感谢您的杰出贡献。我正在尝试将您的代码融入我的框架中。我很喜欢您采取的方法。不过，我的数据有一点多余（这就是为什么我称其为嘈杂），但我相信使用某种小波降噪的后处理方法可以得到我想要的结果。 - Frank Krueger

1

我的方法是先对点列表进行排序，然后使用贝塞尔曲线。

关键是排序。从一个随机点开始，找到最近的点。假设这两个点相连。通过这两个端点，找到距离它们最近的点。假设距离其端点较小的那个点与该点相连。重复此过程，直到所有点都相连。

我认为这种方法仍存在一些问题，但也许你可以将其用作起点（双关语）。

编辑：您可以使用不同的起始点多次执行此操作，然后查看结果的差异。至少这给了你一些信心，哪些点彼此相连。

- Treb

1

一种完全不同的方法，不需要其他约束条件，但细节可能取决于您的应用程序。如果路径周围有“密集的点云”，则应该效果最佳。

使用“成本”函数定义曲线和点云之间的差异。使用参数化曲线和标准优化算法。- 或 - 从起点到终点开始使用直线曲线，然后使用遗传算法进行修改。

典型的成本函数是取每个点与曲线之间的最小距离，并求平方和。

我没有足够的经验来建议优化或遗传算法，但我相信它可以完成 :)

我可以想象一个遗传算法如下：

路径将由航点构建。从起点到终点的直线上放置N个航点。（N可以根据问题选择）。突变可能是：

对于每个段，如果rnd（）＜x，则在中间引入新的航点。
对于每个航点，略微变化X和Y坐标。

在成本函数中，您需要包括总长度。可能不需要分割，或者随着引入更多航点，“分割机会”x可能需要减少。您可以选择是否将（2）应用于起点和终点。

尝试一下会很有趣...

- peterchen

0

从你对问题的回答中看来，你似乎知道“黄金曲线”，我建议像@jamesh建议的那样找到“黄金曲线”的贝塞尔曲线并绘制它。

- Kenny

0

你有多少个点？
如上所述，如果你只有相对较少的点，贝塞尔曲线是一个不错的选择。如果你有很多点，可以像dmckee建议的那样构建簇。

然而，你还需要另一个约束条件来定义点的顺序。已经有许多好的建议来选择点，但除非你引入另一个约束条件，否则任何一个都会给出可能的解决方案。

我能想到的可能的约束条件：

最短路径
最直的线段
最小总绝对旋转
方向偏好（即水平/垂直比交叉更可能）

在所有情况下，为了满足约束条件，你可能需要测试序列的所有排列。如果你从一个“好的猜测”开始，你可以快速终止其他的测试。

- peterchen

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jamesh · Accepted Answer

贝塞尔曲线插值可能适合您的问题。

然而，这并没有解决点的排序成路径的问题；有许多方法可供考虑：

任何“最优”类型的路径（例如，在路径上每个点的最小方向变化、*穿过所有点的最短路径）都可能归结为NP完全的旅行商问题（TSP）。
一个“合理”的路径是将节点聚类，然后在群集之间和群集内部进行路由。当然，群集越大，或者群集数量越多，这个较小的问题就越像一个大n TSP。
按一个轴对点进行排序。如果轴超过2个，则一些降维策略可能会有用。例如：独立成分分析。