如何比较两条曲线(点阵)
我有问题找到方法来比较两条轨迹(曲线)。 第一个原稿包含点(x,y)。 第二个可以偏移,更小或更大的比例,并与旋转 - 也与点(x,y)排列如何比较两条曲线(点阵)
我的第一个方法是找到两点之间的最小距离,并重复此过程迭代,它的总和除以点数 - 那么我的结果告诉我珍惜每点的平均误差: http://www.mathopenref.com/coorddist.html
,也是我觉得这个方法: https://help.scilab.org/docs/6.0.0/en_US/fminsearch.html
,但我不能想出如何用它。 我想比较两个轨迹,但我的结果必须包括旋转,或至少偏移开始。
我当前结果是每点计算误差(距离)
- 获得坐标(x,y)的第二轨迹。
- 在循环中,我尝试从1中找到(x,y)之间的min_distance并指向原始轨迹。
- 添加smallest_distance我发现在2步骤。
- 从第二个轨迹除以点数的最小距离的总和。
我的结果描述了每个点的平均误差(距离),如果我们比较原始轨迹。
但我不知道如何处理如果轨迹旋转,缩放或移位。
请大家看我的例子轨迹:
所以你需要比较2条曲线上旋转,平移和尺度不变的形状。
解决方案
让我们假设2个sinwaves进行测试。旋转和缩放都具有相同的宽高比和一个增加的噪音。我生成它们在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);
}
-
OBB方向包围盒
计算OBB其中将找到曲线的旋转角度和位置,从而使它们旋转的一个,这样便开始在相同的位置并具有相同的方向。
如果OBB尺寸太差,那么曲线就不同了。
对于上面的例子中它yealds这个结果:
每个OBB由开始点和
P
基本向量U,V
定义,其中的U x V
为正|U|>=|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做到这一切在一个步骤。这里的结果:
-
取样不均匀或曲线之间或其任何部分之间非常不同的点密度的情况下
你应该重新品尝你的曲线有共同点密度。您可以对此使用线性或多项式插值。您也不需要将新采样存储在内存中,而是可以构建函数,该函数返回从起点开始按照弧长参数化的每条曲线的点。
point curve0(double distance); point curve1(double distance);
-
比较
现在你可以在。减去2条曲线和总结的差异腹肌。然后将其除以曲线长度并将结果阈值。
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
你应该试试这个,即使+ 180deg旋转的方位差从OBB只有真正的范围的一半。
以下几个相关的问题答案:
你应该用'[算法]'如果你想要的东西通用的,或者你应该指定编程语言,你想将其标记为实现这一点,并提供您当前的结果。 –
谢谢你的建议。我正在写*软件,如scilab或八度。 – anna95