codeabbey任务
我试图解决这个问题，我不知道下一步该怎么做。
链接到问题
问题陈述：
假设已经完成了一些初步的图像预处理，并且您在两张图片上以星号坐标的形式存在数据。 这些图片大约为100x100毫米，坐标也以毫米为单位给出。 看看下面的原理图代表： 
你会发现在这两张照片中，星星都显示为大致圆形的区域（将其视为我们望远镜的光圈），并且可以发现它们代表了同一片天空 - 稍微旋转并轻微移动。
您还可以看到其中一颗星星（标有红色箭头）相对于其他星星改变了位置。
你的任务是找出这样一个“徘徊的恒星”，因为它可能是彗星或小行星，并且发生概率很高。
请注意，靠近边缘的一些恒星可能不在一张照片中（由于偏移） - 但“流星”离中心不远，因此会出现在两张图像上。
输入数据包含两个对应于两个图像的部分。 每个序列以单个整数开始 - 列出的恒星数量。 然后是星星的坐标（X和Y）。
答案应分别给出第一节和第二节流浪之星的两个索引（从0开始）。
这个例子和上面的图片一样。 坐标为（-18.2,11.1）的第一部分的星形＃29与坐标为（-19.7,6.9）的第二部分的星形＃3相同。 示例输入数据：
94＃第1节包含94颗星
-47.5 -10.4
19.1 25.9
18.9 -10.4
-2.1 -47.6
...
...
92＃第2节包含92颗星
-14.8 10.9
18.8 -0.1
-11.3 5.7
-19.7 6.9
-11.5 -16.7
-45.4 -15.3
6.0 -46.9
-24.1 -26.3
30.2 27.4
...
...
我面临的问题
问题是矢量不匹配，甚至没有相同的大小。 例如，第一部分中的第一个矢量与第二部分中的第一个矢量不匹配，所以我无法基于此计算旋转矩阵。 我也试图根据每个部分的质心来计算它，但边缘上的某些点可能不存在，所以它们会有不同的质心（我试过只包括长度小于40的矢量，大小仍然不匹配） 。
所以我的问题是我的计算基础是什么？ 如何找到一些匹配向量，以便我可以计算它们上的旋转矩阵？ 我需要一个正确的方向。
我所做的是实现函数来查找两个给定向量之间的旋转矩阵。 我正在使用的公式：
transformed_vector = R * original_vector + t
其中R是旋转矩阵，并且由于矢量也沿轴移动了一点，我还加了t
现在我所需要的只是两个向量来进行计算。
编辑：我应该提到，我实际上给了两个向量阵列，每个图像一个，我实际上没有给图像。 我需要找到基于这些载体移动的恒星。
谢谢！
[edit2]完整的reedit
已经找到了一些时间/心情，使其更加强大
xy0[],xy1[]为输入星号列表 max_r成为附近的搜索区域treshld max_err成为最大可接受的集群匹配错误 所以这里是算法：
xy0[]找到星团 max_r cl0[]集群添加到cl0[]集群列表 xy1[],cl1[] cl0[]中找到的集群中取2个集群 xy0[],xy1[]之间的转换 这是视觉效果：
xy0[]集 xy1[]集 xy0[] xy1[] [笔记]
我使用我自己的List<T>模板...
List<int> x; 与int x[];相同int x[]; x[i]是项目访问 x.num是数组中的项目数 x.add(5); 与x[x.num]=5; x.num++; x[x.num]=5; x.num++; 从这一点你可以检查xy0 and transformed xy1之间的匹配
max_err使用一些阈max_err ix0[],ix1[]作为结果输出 [edit3]其余的工作
//---------------------------------------------------------------------------
// answer: 29 3
// input data:
const int n0=94; double xy0[n0][2]=
{
-47.5,-10.4,19.1,25.9,18.9,-10.4,-2.1,-47.6,41.8,-12.1,-15.7,12.1,-11.0,-0.6,
-15.6,-7.6,14.9,43.5,16.6,0.1,3.6,-33.5,-14.2,20.8,17.8,-29.8,-2.2,-12.8,
44.6,19.7,17.9,-41.3,24.6,37.0,43.9,14.5,23.8,19.6,-4.2,-40.5,32.0,17.2,
22.6,-26.9,9.9,-33.4,-13.6,6.6,48.5,-3.5,-9.9,-39.9,-28.2,20.7,7.1,15.5,
-36.2,-29.9,-18.2,11.1,-1.2,-13.7,9.3,9.3,39.2,15.8,-5.2,-16.2,-34.9,5.0,
-13.4,-31.8,24.7,-29.1,1.4,24.0,-24.4,18.0,11.9,-29.1,36.3,18.6,30.3,38.4,
4.8,-20.5,-46.8,12.1,-44.2,-6.0,-1.4,-39.7,-1.0,-13.7,13.3,23.6,37.4,-7.0,
-22.3,37.8,17.6,-3.3,35.0,-9.1,-44.5,13.1,-5.1,19.7,-12.1,1.7,-30.9,-1.9,
-19.4,-15.0,10.8,31.9,19.7,3.1,29.9,-16.6,31.7,-26.8,38.1,30.2,3.5,25.1,
-14.8,19.6,2.1,29.0,-9.6,-32.9,24.8,4.9,-2.2,-24.7,-4.3,-37.4,-3.0,37.4,
-34.0,-21.2,-18.4,34.6,9.3,-45.2,-21.1,-10.3,-19.8,29.1,31.3,37.7,27.2,19.3,
-1.6,-45.6,35.3,-23.5,-39.9,-19.8,-3.8,40.6,-15.7,12.5,-0.8,-16.3,-5.1,13.1,
-13.8,-25.7,43.8,5.6,9.2,38.6,42.2,0.2,-10.0,-48.6,14.1,-6.5,34.6,-26.8,
11.1,-6.7,-6.1,25.1,-38.3,8.1,
};
const int n1=92; double xy1[n1][2]=
{
-14.8,10.9,18.8,-0.1,-11.3,5.7,-19.7,6.9,-11.5,-16.7,-45.4,-15.3,6.0,-46.9,
-24.1,-26.3,30.2,27.4,21.4,-27.2,12.1,-36.1,23.8,-38.7,41.5,5.3,-8.7,25.5,
36.6,-5.9,43.7,-14.6,-9.7,-8.6,34.7,-19.3,-15.5,19.3,21.4,3.9,34.0,29.8,
6.5,19.5,28.2,-21.7,13.4,-41.8,-25.9,-6.9,37.5,27.8,18.1,44.7,-43.0,-19.9,
-15.7,18.0,2.4,-31.6,9.6,-37.6,15.4,-28.8,43.6,-11.2,4.6,-10.2,-8.8,38.2,
8.7,-34.6,-4.7,14.1,-1.7,31.3,0.6,27.9,26.3,13.7,-1.2,26.3,32.1,-17.7,
15.5,32.6,-14.4,-12.6,22.3,-22.5,7.0,48.5,-6.4,20.5,-42.9,4.2,-23.0,31.6,
-24.6,14.0,-30.2,-26.5,-29.0,15.7,6.0,36.3,44.3,13.5,-27.6,33.7,13.4,-43.9,
10.5,28.9,47.0,1.4,10.2,14.0,13.3,-15.9,-3.4,-25.6,-14.7,10.5,21.6,27.6,
21.8,10.6,-37.8,-14.2,7.6,-21.8,-8.6,1.3,6.8,-13.3,40.9,-15.3,-10.3,41.1,
6.0,-10.8,-1.5,-31.4,-35.6,1.0,2.5,-14.3,24.4,-2.6,-24.1,-35.3,-29.9,-34.7,
15.9,-1.0,19.5,7.0,44.5,19.1,39.7,2.7,2.7,42.4,-23.0,25.9,25.0,28.2,31.2,-32.8,
3.9,-38.4,-44.8,2.7,-39.9,-19.3,-7.0,-0.6,5.8,-10.9,-44.5,19.9,-31.5,-1.2,
};
//---------------------------------------------------------------------------
struct _dist // distance structure
{
int ix; // star index
double d; // distance to it
_dist(){}; _dist(_dist& a){ *this=a; }; ~_dist(){}; _dist* operator = (const _dist *a) { *this=*a; return this; }; /*_dist* operator = (const _dist &a) { ...copy... return this; };*/
};
struct _cluster // star cluster structure
{
double x,y; // avg coordinate
int iy; // ix of cluster match in the other set or -1
double err; // error of cluster match
List<int> ix; // star ix
List<double> d; // distances of stars ix[] against each other
_cluster(){}; _cluster(_cluster& a){ *this=a; }; ~_cluster(){}; _cluster* operator = (const _cluster *a) { *this=*a; return this; }; /*_cluster* operator = (const _cluster &a) { ...copy... return this; };*/
};
const double max_r=5.0; // find cluster max radius
const double max_err=0.2; // match cluster max distance error treshold
const double max_rr=max_r*max_r;
const double max_errr=max_err*max_err;
int wi0,wi1; // result wandering star ix ...
int ix0[n0],ix1[n1]; // original star indexes
List<_cluster> cl0,cl1; // found clusters
double txy1[n1][2]; // transformed xy1[]
//---------------------------------------------------------------------------
double atanxy(double x,double y)
{
const double pi=M_PI;
const double pi2=2.0*M_PI;
int sx,sy;
double a;
const double _zero=1.0e-30;
sx=0; if (x<-_zero) sx=-1; if (x>+_zero) sx=+1;
sy=0; if (y<-_zero) sy=-1; if (y>+_zero) sy=+1;
if ((sy==0)&&(sx==0)) return 0;
if ((sx==0)&&(sy> 0)) return 0.5*pi;
if ((sx==0)&&(sy< 0)) return 1.5*pi;
if ((sy==0)&&(sx> 0)) return 0;
if ((sy==0)&&(sx< 0)) return pi;
a=y/x; if (a<0) a=-a;
a=atan(a);
if ((x>0)&&(y>0)) a=a;
if ((x<0)&&(y>0)) a=pi-a;
if ((x<0)&&(y<0)) a=pi+a;
if ((x>0)&&(y<0)) a=pi2-a;
return a;
}
//---------------------------------------------------------------------------
void compute()
{
int i0,i1,e,f;
double a,x,y;
// original indexes (to keep track)
for (e=0;e<n0;e++) ix0[e]=e;
for (e=0;e<n1;e++) ix1[e]=e;
// sort xy0[] by x asc
for (e=1;e;) for (e=0,i0=0,i1=1;i1<n0;i0++,i1++)
if (xy0[i0][0]>xy0[i1][0])
{
e=ix0[i0] ; ix0[i0] =ix0[i1] ; ix0[i1] =e; e=1;
a=xy0[i0][0]; xy0[i0][0]=xy0[i1][0]; xy0[i1][0]=a;
a=xy0[i0][1]; xy0[i0][1]=xy0[i1][1]; xy0[i1][1]=a;
}
// sort xy1[] by x asc
for (e=1;e;) for (e=0,i0=0,i1=1;i1<n1;i0++,i1++)
if (xy1[i0][0]>xy1[i1][0])
{
e=ix1[i0] ; ix1[i0] =ix1[i1] ; ix1[i1] =e; e=1;
a=xy1[i0][0]; xy1[i0][0]=xy1[i1][0]; xy1[i1][0]=a;
a=xy1[i0][1]; xy1[i0][1]=xy1[i1][1]; xy1[i1][1]=a;
}
_dist d;
_cluster c,*pc,*pd;
List<_dist> dist;
// find star clusters in xy0[]
for (cl0.num=0,i0=0;i0<n0;i0++)
{
for (dist.num=0,i1=i0+1;(i1<n0)&&(fabs(xy0[i0][0]-xy0[i1][0])<=max_r);i1++) // stars nearby
{
x=xy0[i0][0]-xy0[i1][0]; x*=x;
y=xy0[i0][1]-xy0[i1][1]; y*=y; a=x+y;
if (a<=max_rr) { d.ix=i1; d.d=a; dist.add(d); }
}
if (dist.num>=2) // add/compute cluster if found
{
c.ix.num=0; c.err=-1.0;
c.ix.add(i0); for (i1=0;i1<dist.num;i1++) c.ix.add(dist[i1].ix); c.iy=-1;
c.x=xy0[i0][0]; for (i1=0;i1<dist.num;i1++) c.x+=xy0[dist[i1].ix][0]; c.x/=dist.num+1;
c.y=xy0[i0][1]; for (i1=0;i1<dist.num;i1++) c.y+=xy0[dist[i1].ix][1]; c.y/=dist.num+1;
for (e=1,i1=0;i1<cl0.num;i1++)
{
pc=&cl0[i1];
x=c.x-pc->x; x*=x;
y=c.y-pc->y; y*=y; a=x+y;
if (a<max_rr) // merge if too close to another cluster
{
pc->x=0.5*(pc->x+c.x);
pc->y=0.5*(pc->y+c.y);
for (e=0;e<c.ix.num;e++)
{
for (f=0;f<pc->ix.num;f++)
if (pc->ix[f]==c.ix[e]) { f=-1; break; }
if (f>=0) pc->ix.add(c.ix[e]);
}
e=0; break;
}
}
if (e) cl0.add(c);
}
}
// full recompute clusters
for (f=0,pc=&cl0[f];f<cl0.num;f++,pc++)
{
// avg coordinate
pc->x=0.0; for (i1=0;i1<pc->ix.num;i1++) pc->x+=xy0[pc->ix[i1]][0]; pc->x/=pc->ix.num;
pc->y=0.0; for (i1=0;i1<pc->ix.num;i1++) pc->y+=xy0[pc->ix[i1]][1]; pc->y/=pc->ix.num;
// distances
for (pc->d.num=0,i0= 0;i0<pc->ix.num;i0++)
for ( i1=i0+1;i1<pc->ix.num;i1++)
{
x=xy0[pc->ix[i1]][0]-xy0[pc->ix[i0]][0]; x*=x;
y=xy0[pc->ix[i1]][1]-xy0[pc->ix[i0]][1]; y*=y;
pc->d.add(sqrt(x+y));
}
// sort by distance asc
for (e=1;e;) for (e=0,i0=0,i1=1;i1<pc->d.num;i0++,i1++)
if (pc->d[i0]>pc->d[i1])
{
a=pc->d[i0]; pc->d[i0]=pc->d[i1]; pc->d[i1]=a; e=1;
}
}
// find star clusters in xy1[]
for (cl1.num=0,i0=0;i0<n1;i0++)
{
for (dist.num=0,i1=i0+1;(i1<n1)&&(fabs(xy1[i0][0]-xy1[i1][0])<=max_r);i1++) // stars nearby
{
x=xy1[i0][0]-xy1[i1][0]; x*=x;
y=xy1[i0][1]-xy1[i1][1]; y*=y; a=x+y;
if (a<=max_rr) { d.ix=i1; d.d=a; dist.add(d); }
}
if (dist.num>=2) // add/compute cluster if found
{
c.ix.num=0; c.err=-1.0;
c.ix.add(i0); for (i1=0;i1<dist.num;i1++) c.ix.add(dist[i1].ix); c.iy=-1;
c.x=xy1[i0][0]; for (i1=0;i1<dist.num;i1++) c.x+=xy1[dist[i1].ix][0]; c.x/=dist.num+1;
c.y=xy1[i0][1]; for (i1=0;i1<dist.num;i1++) c.y+=xy1[dist[i1].ix][1]; c.y/=dist.num+1;
for (e=1,i1=0;i1<cl1.num;i1++)
{
pc=&cl1[i1];
x=c.x-pc->x; x*=x;
y=c.y-pc->y; y*=y; a=x+y;
if (a<max_rr) // merge if too close to another cluster
{
pc->x=0.5*(pc->x+c.x);
pc->y=0.5*(pc->y+c.y);
for (e=0;e<c.ix.num;e++)
{
for (f=0;f<pc->ix.num;f++)
if (pc->ix[f]==c.ix[e]) { f=-1; break; }
if (f>=0) pc->ix.add(c.ix[e]);
}
e=0; break;
}
}
if (e) cl1.add(c);
}
}
// full recompute clusters
for (f=0,pc=&cl1[f];f<cl1.num;f++,pc++)
{
// avg coordinate
pc->x=0.0; for (i1=0;i1<pc->ix.num;i1++) pc->x+=xy1[pc->ix[i1]][0]; pc->x/=pc->ix.num;
pc->y=0.0; for (i1=0;i1<pc->ix.num;i1++) pc->y+=xy1[pc->ix[i1]][1]; pc->y/=pc->ix.num;
// distances
for (pc->d.num=0,i0= 0;i0<pc->ix.num;i0++)
for ( i1=i0+1;i1<pc->ix.num;i1++)
{
x=xy1[pc->ix[i1]][0]-xy1[pc->ix[i0]][0]; x*=x;
y=xy1[pc->ix[i1]][1]-xy1[pc->ix[i0]][1]; y*=y;
pc->d.add(sqrt(x+y));
}
// sort by distance asc
for (e=1;e;) for (e=0,i0=0,i1=1;i1<pc->d.num;i0++,i1++)
if (pc->d[i0]>pc->d[i1])
{
a=pc->d[i0]; pc->d[i0]=pc->d[i1]; pc->d[i1]=a; e=1;
}
}
// find matches
for (i0=0,pc=&cl0[i0];i0<cl0.num;i0++,pc++) if (pc->iy<0){ e=-1; x=0.0;
for (i1=0,pd=&cl1[i1];i1<cl1.num;i1++,pd++) if (pc->d.num==pd->d.num)
{
for (y=0.0,f=0;f<pc->d.num;f++) y+=fabs(pc->d[f]-pd->d[f]);
if ((e<0)||(x>y)) { e=i1; x=y; }
}
x/=pc->d.num;
if ((e>=0)&&(x<max_err))
{
if (cl1[e].iy>=0) cl0[cl1[e].iy].iy=-1;
pc->iy =e; cl1[e].iy=i0;
pc->err=x; cl1[e].err=x;
}
}
// compute transform
double tx0,tx1,ty0,ty1,tc,ts;
tx0=0.0; tx1=0.0; ty0=0.0; ty1=0.0; tc=1.0; ts=0.0; i0=-1; i1=-1;
for (e=0,f=0,pc=&cl0[e];e<cl0.num;e++,pc++) if (pc->iy>=0) // find 2 clusters with match
{
if (f==0) i0=e;
if (f==1) { i1=e; break; }
f++;
}
if (i1>=0)
{
pc=&cl0[i0]; // translation and offset from xy0 set
pd=&cl0[i1];
tx1=pc->x;
ty1=pc->y;
a =atanxy(pd->x-pc->x,pd->y-pc->y);
pc=&cl1[pc->iy]; // translation and offset from xy1 set
pd=&cl1[pd->iy];
tx0=pc->x;
ty0=pc->y;
a-=atanxy(pd->x-pc->x,pd->y-pc->y);
tc=cos(a);
ts=sin(a);
}
// transform xy1 -> txy1 (in xy0 coordinate system)
for (i1=0;i1<n1;i1++)
{
x=xy1[i1][0]-tx0;
y=xy1[i1][1]-ty0;
txy1[i1][0]=x*tc-y*ts+tx1;
txy1[i1][1]=x*ts+y*tc+ty1;
}
// sort txy1[] by x asc (after transfrm)
for (e=1;e;) for (e=0,i0=0,i1=1;i1<n1;i0++,i1++)
if (txy1[i0][0]>txy1[i1][0])
{
e= ix1[i0] ; ix1[i0] = ix1[i1] ; ix1[i1] =e; e=1;
a=txy1[i0][0]; txy1[i0][0]=txy1[i1][0]; txy1[i1][0]=a;
a=txy1[i0][1]; txy1[i0][1]=txy1[i1][1]; txy1[i1][1]=a;
}
// find match between xy0,txy1 (this can be speeded up by exploiting sorted order)
int ix01[n0],ix10[n1];
for (i0=0;i0<n0;i0++) ix01[i0]=-1;
for (i1=0;i1<n1;i1++) ix10[i1]=-1;
for (i0=0;i0<n0;i0++){ a=-1.0;
for (i1=0;i1<n1;i1++)
{
x=xy0[i0][0]-txy1[i1][0]; x*=x;
y=xy0[i0][1]-txy1[i1][1]; y*=y; x+=y;
if (x<max_errr)
if ((a<0.0)||(a>x)) { a=x; ix01[i0]=i1; ix10[i1]=i0; }
}}
// find the closest stars from unmatched stars
a=-1.0; wi0=-1; wi1=-1;
for (i0=0;i0<n0;i0++) if (ix01[i0]<0)
for (i1=0;i1<n1;i1++) if (ix10[i1]<0)
{
x=xy0[i0][0]-txy1[i1][0]; x*=x;
y=xy0[i0][1]-txy1[i1][1]; y*=y; x+=y;
if ((wi0<0)||(a>x)) { a=x; wi0=i0; wi1=i1; }
}
}
//---------------------------------------------------------------------------
void draw()
{
bmp->Canvas->Font->Charset=OEM_CHARSET;
bmp->Canvas->Font->Name="System";
bmp->Canvas->Font->Pitch=fpFixed;
bmp->Canvas->Font->Color=0x00FFFF00;
bmp->Canvas->Brush->Color=0x00000000;
bmp->Canvas->FillRect(TRect(0,0,xs,ys));
_cluster *pc;
int i,x0,y0,x1,y1,x2,y2,xx,yy,r,_r=4;
double x,y,m;
x0=xs/6; x1=3*x0; x2=5*x0;
y0=ys/2; y1= y0; y2= y0;
x=x0/60.0; y=y0/60.0; if (x<y) m=x; else m=y;
// clusters match
bmp->Canvas->Pen ->Color=clAqua;
bmp->Canvas->Brush->Color=0x00303030;
for (i=0,pc=&cl0[i];i<cl0.num;i++,pc++)
if (pc->iy>=0)
{
x=pc->x*m; xx=x0+x;
y=pc->y*m; yy=y0-y;
bmp->Canvas->MoveTo(xx,yy);
x=cl1[pc->iy].x*m; xx=x1+x;
y=cl1[pc->iy].y*m; yy=y1-y;
bmp->Canvas->LineTo(xx,yy);
}
// clusters area
for (i=0,pc=&cl0[i];i<cl0.num;i++,pc++)
{
x=pc->x*m; xx=x0+x;
y=pc->y*m; yy=y0-y;
r=pc->d[pc->d.num-1]*m*0.5+_r;
bmp->Canvas->Ellipse(xx-r,yy-r,xx+r,yy+r);
bmp->Canvas->TextOutA(xx+r,yy+r,AnsiString().sprintf("%.3lf",pc->err));
}
for (i=0,pc=&cl1[i];i<cl1.num;i++,pc++)
{
x=pc->x*m; xx=x1+x;
y=pc->y*m; yy=y1-y;
r=pc->d[pc->d.num-1]*m*0.5+_r;
bmp->Canvas->Ellipse(xx-r,yy-r,xx+r,yy+r);
bmp->Canvas->TextOutA(xx+r,yy+r,AnsiString().sprintf("%.3lf",pc->err));
}
// stars
r=_r;
bmp->Canvas->Pen ->Color=clAqua;
bmp->Canvas->Brush->Color=clBlue;
for (i=0;i<n0;i++)
{
x=xy0[i][0]*m; xx=x0+x;
y=xy0[i][1]*m; yy=y0-y;
bmp->Canvas->Ellipse(xx-r,yy-r,xx+r,yy+r);
}
for (i=0;i<n1;i++)
{
x=xy1[i][0]*m; xx=x1+x;
y=xy1[i][1]*m; yy=y1-y;
bmp->Canvas->Ellipse(xx-r,yy-r,xx+r,yy+r);
}
// merged sets
r=_r;
bmp->Canvas->Pen ->Color=clBlue;
bmp->Canvas->Brush->Color=clBlue;
for (i=0;i<n0;i++)
{
x=xy0[i][0]*m; xx=x2+x;
y=xy0[i][1]*m; yy=y2-y;
bmp->Canvas->Ellipse(xx-r,yy-r,xx+r,yy+r);
}
r=_r-2;
bmp->Canvas->Pen ->Color=clGreen;
bmp->Canvas->Brush->Color=clGreen;
for (i=0;i<n1;i++)
{
x=txy1[i][0]*m; xx=x2+x;
y=txy1[i][1]*m; yy=y2-y;
bmp->Canvas->Ellipse(xx-r,yy-r,xx+r,yy+r);
}
// wandering star
r=_r+5;
bmp->Canvas->Pen ->Color=0x00FF8000;
bmp->Canvas->Font ->Color=0x00FF8000;
bmp->Canvas->Brush->Style=bsClear;
x=xy0[wi0][0]*m; xx=x2+x;
y=xy0[wi0][1]*m; yy=y2-y;
bmp->Canvas->Ellipse(xx-r,yy-r,xx+r,yy+r);
bmp->Canvas->TextOutA(xx+r,yy+r,ix0[wi0]);
bmp->Canvas->Pen ->Color=0x0040FF40;
bmp->Canvas->Font ->Color=0x0040FF40;
x=txy1[wi1][0]*m; xx=x2+x;
y=txy1[wi1][1]*m; yy=y2-y;
bmp->Canvas->Ellipse(xx-r,yy-r,xx+r,yy+r);
bmp->Canvas->TextOutA(xx+r,yy+r,ix1[wi1]);
bmp->Canvas->Brush->Style=bsSolid;
Form1->Canvas->Draw(0,0,bmp);
}
//---------------------------------------------------------------------------
最终的结果是：
首先，为了简单起见，我们首先假装没有徘徊的恒星，并且一幅图像中的每颗恒星都在另一幅图像中 - 也就是说，图像B是通过仅应用（可能为零）偏移从图像A产生的和（可能为零）旋转。
签名
我认为解决这个问题的最好方法是“忘掉”每张图片中每颗恒星的位置，而是为每颗恒星记录一个签名：一些信息不会因换档（平移）或旋转而改变。 然后你可以查看图像A中的每个签名，并尝试将它与图像B中的签名进行匹配。如果我们以合理的方式制作签名，那么他们应该很好地区分星星，这样就不会有两颗星在同一图像中获得相同或高度相似的签名。
对于给定的恒星，不会因为移动或旋转而改变的是它与同一图像中任何其他恒星的距离。 因此，您可以将所有其他n-1个星星的完整距离作为恒星的签名（存储为无序集合，因为我们不知道“哪些恒星是哪个恒星”）。 但是，仅仅使用其中的一个子集就足够了（而且速度更快，并且最终更稳健），在这种情况下，到最近邻居的距离可能是最具信息量的（除非您有重复出现的恒星模式）。 有多少使用？ 我首先计算每个恒星在同一图像中与其最近邻居的距离; 如果在图像A中，所有这些距离都“足够不同”（即，在您选择的某个任意阈值以下具有差异），并且同样在图像B中，则完成 - 即，您拥有的签名计算已经足够好地区分星星 - 否则返回，并且对于每个星星，将距离其第二近邻的距离插入其签名中，重复此操作直到实现签名的“唯一性”。
比较签名
这提出了如何确定当签名包含多于一个距离时两个签名是否“足够不同”的问题。 现在你正在比较两组数字，而不是两个数字。 一种方法是对每个签名中的距离进行排序，然后通过计算点之间距离的度量来比较它们，如平方差的总和（例如，如果每个签名包含3个距离，则这将是（u [1] -v对于两个恒星u和v来说，^ 2 +（u [2] -v [2]）^ 2 +（u [3] -v [3]）^ 2，其中u [i]在你的例子数据集中，我猜测每个星星可能有3-4个距离就足够了。
强大而高效的签名比较
然而，一旦流浪和失踪的恒星被考虑后，这将变得不是特别强大：假设图像A中的某个恒星u具有流星v作为其最近的邻居，并且在图像B中，v已经移开，因此它现在是现在与你最近的邻居。 那么，如果我们将图像A中的u的签名与图像B中的签名进行比较，我们将得到一个不正确的较大距离，因为我们将“盲目地”比较uA [1]和uB [1]等等，而不是比较uA [ 2]与uB [1]，uA [3]与uB [2]等等，因为我们希望（因为这些距离将是相等的）。 因此，比较两个签名的更好方法是将每个签名的距离排序，然后让数字“滑动，直到它们适合”另一个数字。
令人高兴的是，这可以通过列表合并在线性时间内完成。 给定两个排序的数字X和Y的列表，我们执行通常的列表合并策略，从两个列表中选择最小的元素，将其从列表中移除并写出，但我们也跟踪两个候选部分解决方案：Bm，分数是最近输出的数字与之前的数字匹配的最佳部分解决方案，以及Bf（它是免费的（与任何事物尚未匹配）的最佳部分解决方案的分数）。 选择惩罚成本p以分配给与其他列表中的任何数字不匹配的数字，以及评分函数分数（a，b），当a = b和更高的值时，分数值为0，a和b越大是（例如，分数（a，b）=（a - b）^ 2）。 那么可以使用下式来计算最佳分数sigDiff（X，Y）：
例如，假设我们有两个距离列表（即两个签名）X = [10,20,30,40]和Y = [11,18,41,50]，惩罚是20，score（）是平方差的总和如上。 上述算法将按如下方式“对齐”两个序列：
X 10 20 30 40
matches /
Y 11 18 41 50
cost 1 4 20 1 20 Total cost: 46
相比之下，“朴素”的和平方法会给出：
X 10 20 30 40
matches | | | |
Y 11 18 41 50
cost 1 4 121 100 Total cost: 226
匹配两个图像之间的签名
我们已经建立了所有这些机器，以便我们可以通过匹配它们的签名来匹配两幅图像之间的星星。 可以说，这样做的“正确”方法是解决图中一边的顶点是图A中星的签名的图上的二分最大加权匹配问题，另一边的顶点是在图像B中存在星形，并且从一侧的每个顶点X到另一侧的每个顶点Y具有重量-igDiff（X，Y）（由于我们希望使总差异最小化而被否定）的边缘。
然而，解决这个问题可能需要一段时间，而且这种算法也可能会发现一些不正确的“近似”匹配，试图获得总体最低成本。 我们宁愿专注于那些我们确定相互对应的恒星对。 基于以下想法，启发式可以更快地完成：基于这样的想法，如果对于图像A中最近的星形（基于sigDiff（））的图像A中的星形X是Y，则可以发现图像A中Y最接近的星形是也就是X（即，如果X的最佳匹配的最佳匹配是X），那么我们可以确信X和Y真的匹配。 这些自信的匹配对可以快速找到，并用于使用最小二乘估计从图像A到图像B的仿射变换。
忽略缺少的星星
我们首先计算图像B的恒星的凸包。 然后，使用由自信星对确定的变换，将图像A中的每个星变换为其在图像B中估计的相应位置，并且取该变换图像的凸包。 然后我们将这两个凸包相交：落在这个交点内的任何一个图像中的每个星星都是我们期望在这两个图像中找到的一颗星。 最后，我们扔掉所有在这个相交的凸包外的图像中的所有星星，然后重新开始！
在再次运行一切后（可能实际上没有必要重新运行一切），我们应该发现图像A中有一颗恒星，图像B中有一颗恒星与其他图像中的所有其他恒星差不多（如像往常一样sigDiff（））。 这些“两个”明星当然是单一的“流浪”明星:)
链接地址: http://www.djcxy.com/p/25633.html上一篇: codeabbey task