java - 如何比较两条曲线(点数组)

Question

我无法找到比较两条轨迹(曲线)的方法。 第一个原件包含点 (x,y)。 第二个可以是偏移、更小或更大的比例，并且可以旋转 - 也是带有点 (x,y) 的数组

我所做的第一个方法是找到两点之间的最小距离，并在每次迭代中重复此过程，求和并除以点数 - 然后我的结果告诉我每个点的平均误差值: http://www.mathopenref.com/coorddist.html

我还发现了这个方法: https://help.scilab.org/docs/6.0.0/en_US/fminsearch.html

但我不知道如何使用它。 我想比较两个轨迹，但我的结果必须包括旋转，或者至少包括开始的偏移。

我当前的结果是计算每点(距离)的误差

1. 获取坐标 (x,y) 第二条轨迹。
2. 在循环中，我尝试找到 1 中的 (x,y) 与原始轨迹中的点之间的最小距离。
3. 添加我在两步中找到的最小距离。
4. 将最小距离之和除以第二条轨迹的点数。

如果我们与原始轨迹进​​行比较，我的结果描述了每点的平均误差(距离)。

但是我不知道如何处理轨迹旋转、缩放或移动的情况。

请看我的示例轨迹:

1. http://pokazywarka.pl/trajectory/

2. http://pokazywarka.pl/trajectory2/

Answer 1

因此，您需要比较两条曲线在旋转、平移和缩放方面不变的形状。

解决方案

假设有 2 个正弦波进行测试。两者都经过旋转和缩放，但具有相同的纵横比，并且其中一个增加了噪点。我用 C++ 生成它们，如下所示:

struct _pnt2D
    {
    double x,y;
    // inline
    _pnt2D()    {}
    _pnt2D(_pnt2D& a)   { *this=a; }
    ~_pnt2D()   {}
    _pnt2D* operator = (const _pnt2D *a) { *this=*a; return this; }
    //_pnt2D* operator = (const _pnt2D &a) { ...copy... return this; }
    };
List<_pnt2D> curve0,curve1;         // curves points
_pnt2D p0,u0,v0,p1,u1,v1;           // curves OBBs

const double deg=M_PI/180.0;
const double rad=180.0/M_PI;
void rotate2D(double alfa,double x0,double y0,double &x,double &y)
    {
    double   a=x-x0,b=y-y0,c,s;
    c=cos(alfa);
    s=sin(alfa);
    x=x0+a*c-b*s;
    y=y0+a*s+b*c;
    }

// this code is the init stuff:
int i;
double x,y,a;
_pnt2D p,*pp;
Randomize();
for (x=0;x<2.0*M_PI;x+=0.01)
    {
    y=sin(x);

    p.x= 50.0+(100.0*x);
    p.y=180.0-( 50.0*y);
    rotate2D(+15.0*deg,200,180,p.x,p.y);
    curve0.add(p);

    p.x=150.0+( 50.0*x);
    p.y=200.0-( 25.0*y)+5.0*Random();
    rotate2D(-25.0*deg,250,100,p.x,p.y);
    curve1.add(p);
    }

1. 面向OBB的边界框

   计算OBB这将找到两条曲线的旋转角度和位置，因此旋转其中一条曲线，使它们从相同的位置开始并具有相同的方向。

   如果 OBB 大小差异太大，则曲线会不同。

   对于上面的示例，它会产生以下结果:

   

   每个OBB由起点P定义和基 vector U,V哪里|U|>=|V|和 U x V 的 z 坐标是积极的。这将确保所有 OBB 具有相同的绕组。可以在OBBox_compute中完成将其添加到末尾:

   // |U|>=|V|
   if ((u.x*u.x)+(u.y*u.y)<(v.x*v.x)+(v.y*v.y)) { _pnt2D p; p=u; u=v; v=p; }
   // (U x V).z > 0
   if ((u.x*v.y)-(u.y*v.x)<0.0)
       {
       p0.x+=v.x;
       p0.y+=v.y;
       v.x=-v.x;
       v.y=-v.y;
       }
   

   所以curve0有p0,u0,v0和curve1有p1,u1,v1 .

   现在我们要重新缩放、平移和旋转curve1匹配curve0可以这样完成:

   // compute OBB
   OBBox_compute(p0,u0,v0,curve0.dat,curve0.num);
   OBBox_compute(p1,u1,v1,curve1.dat,curve1.num);
   // difference angle = - acos((U0.U1)/(|U0|.|U1|))
   a=-acos(((u0.x*u1.x)+(u0.y*u1.y))/(sqrt((u0.x*u0.x)+(u0.y*u0.y))*sqrt((u1.x*u1.x)+(u1.y*u1.y))));
   // rotate curve1
   for (pp=curve1.dat,i=0;i<curve1.num;i++,pp++)
    rotate2D(a,p1.x,p1.y,pp->x,pp->y);
   // rotate OBB1
   rotate2D(a,0.0,0.0,u1.x,u1.y);
   rotate2D(a,0.0,0.0,v1.x,v1.y);
   // translation difference = P0-P1
   x=p0.x-p1.x;
   y=p0.y-p1.y;
   // translate curve1
   for (pp=curve1.dat,i=0;i<curve1.num;i++,pp++)
       {
       pp->x+=x;
       pp->y+=y;
       }
   // translate OBB1
   p1.x+=x;
   p1.y+=y;
   // scale difference = |P0|/|P1|
   x=sqrt((u0.x*u0.x)+(u0.y*u0.y))/sqrt((u1.x*u1.x)+(u1.y*u1.y));
   // scale curve1
   for (pp=curve1.dat,i=0;i<curve1.num;i++,pp++)
       {
       pp->x=((pp->x-p0.x)*x)+p0.x;
       pp->y=((pp->y-p0.y)*x)+p0.y;
       }
   // scale OBB1
   u1.x*=x;
   u1.y*=x;
   v1.x*=x;
   v1.y*=x;
   

   您可以使用Understanding 4x4 homogenous transform matrices一步完成这一切。结果如下:

   

2. 抽样

   如果曲线之间或曲线之间的任何部分之间的点密度不均匀或差异很大，您应该重新采样曲线以获得共同的点密度。为此，您可以使用线性或多项式插值。您也不需要将新采样存储在内存中，而是可以构建函数，返回从开始开始按弧长参数化的每条曲线的点。

   point curve0(double distance);
   point curve1(double distance);
   

3. 比较

   现在您可以将两条曲线相减并求出差异的绝对值。然后将其除以曲线长度并对结果进行阈值处理。

   for (double sum=0.0,l=0.0;d<=bigger_curve_length;l+=step)
    sum+=fabs(curve0(l)-curve1(l));
   sum/=bigger_curve_length;
   if (sum>threshold) curves are different
    else curves match
   

即使旋转 +180 度，您也应该尝试此操作，因为与 OBB 的方向差异只有真实范围的一半。

这里有一些相关的 QA:

• compare shapes
• How can i produce multi point linear interpolation?