两组点之间的变换 [英] Transformation between two set of points

问题描述

我有对象让我们在模型图像上说.我想计算模型图像上的对象和目标图像上的对象之间的变换(位移、缩放、旋转).我想假设对象可以被视为 2D，因此应该只计算 2D 转换.

I have object let's say on model image. I want to compute transformation (displacement, scale, rotation) between object on model image and object on target image. I want to make assumption that object's can be treated as 2D so only 2D transformations should be computed.

首先我想以手动辅助的方式进行.用户在模型图像上选择基点，然后在目标图像上选择目标点.点数应由用户定义(但不少于至少 2-3 个点).当点给出不同的信息时，应该对变换进行平均，例如从中可以计算出匹配的质量.

First I want to to it in manually assisted way. The user selects base point on model image and then target point on target image. The number of points should be defined by user (but no less than some minimum 2-3 points). When points gives different information, the transformation should be averaged and for example from this the quality of matching can be computed.

所以问题是关于计算两组点的转换，但是因为我想在图像上做这件事，所以我添加了图像处理标签.

So the questions is rather about computing transformation of two sets of points, but as I want to do it on image I've added image processing tag.

特别欢迎带有一些代码或伪代码的参考和建议.

Especially welcomed are references and advices with some pieces of code or pseudocode.

两点是很简单的问题，只需要线的旋转，缩放和位移，但是如何用更多的点来做，并且平均它并计算一些质量因素.

With two points it's very easy issue, only rotation, scale and displacement of line should be taken, but how to do it with more points, and with averaging it and computing some quality factors.

目前的解决方案是:

void transformFnc(std::vector<PointF> basePoints, std::vector<PointF> targetPoints,
                  PointF& offset, double rotation, double scale)
{
    std::vector<Line> basePointsLines;
    std::vector<Line> targetPointsLines;
    assert(basePoints.size() == targetPoints.size());
    int pointsNumber = basePoints.size();

    for(int i = 0; i < pointsNumber; i++)
    {
         for(int j = i + 1; j < pointsNumber; j++)
         {
             basePointsLines.push_back(Line(basePoints[i], basePoints[j]));
             targetPointsLines.push_back(Line(targetPoints[i], targetPoints[j]));
         }
    }
    std::vector<double> scalesVector;
    std::vector<double> rotationsVector;
    double baseCenterX = 0, baseCenterY = 0, targetCenterX = 0, targetCenterY = 0;
    for(std::vector<Line>::iterator it = basePointsLines.begin(), i = targetPointsLines.begin();
        it != basePointsLines.end(), i != targetPointsLines.end(); it++, i++)
    {
        scalesVector.push_back((*i).length()/(*it).length());
        baseCenterX += (*it).pointAt(0.5).x(); 
        baseCenterY += (*it).pointAt(0.5).y();
        targetCenterX += (*i).pointAt(0.5).x();
        targetCenterY += (*i).pointAt(0.5).y();
        double rotation;
        rotation = (*i).angleTo((*it));
        rotationsVector.push_back(rotation);
    }
    baseCenterX = baseCenterX / pointsNumber;
    baseCenterY = baseCenterY / pointsNumber;
    targetCenterX = targetCenterX / pointsNumber;
    targetCenterY = targetCenterY / pointsNumber;

    offset = PointF(targetCenterX - baseCenterX, targetCenterY - baseCenterY);
    scale = sum(scalesVector) / scalesVector.size();
    rotation = sum(rotationsVector) / rotationsVector.size();
}

我能在这段代码中找到的唯一优化是从缩放和旋转中消除那些与其他值相差太大的值.

Only optimization I can find in this code is to eliminate from scales and rotations those values which differs too much from the rest.

我正在寻找解决方案命题的代码或伪代码.也可以是一些代码的引用.

到目前为止，我所知道的答案是:

So far from answers I know that:

• 可以使用RANSAC算法
• 我需要寻找一些最小二乘意义上的仿射变换计算算法

推荐答案

首先用 3x3 仿射变换矩阵将问题概括为一个简单的仿射变换:即

First generalize the problem in a simple affine transformation with a 3x3 affine transformation matrix: i.e.

[M11 M12 M13]
[M21 M22 M23]
[M31 M32 M33]

由于我们已经知道第三行将始终为 [0 0 1]，我们可以直接忽略它.

Since we already know that the third row will always be [0 0 1] we can simply disregard it.

现在我们可以将问题描述为以下矩阵方程

Now we can describe the problem as the following matrix equation

[xp0]     [x0 y0 1  0  0  0 ]
[yp0]     [0  0  0  x0 y0 1 ]     [M11]
[xp1]     [x1 y1 1  0  0  0 ]     [M12]
[yp1]  =  [0  0  0  x1 y1 1 ]  *  [M13]
[xp2]     [x2 y2 1  0  0  0 ]     [M21]
[yp2]     [0  0  0  x2 y2 1 ]     [M22]
[xp3]     [x3 y3 1  0  0  0 ]     [M23]
[yp3]     [0  0  0  x3 y3 1 ]

其中 xp 和 yp 是投影坐标，x 和 y 是原始坐标.

where xp and yp are the projected coordinates and x and y are the original coordinates.

我们称之为

proj = M * trans

然后我们可以计算出适合变换的最小二乘

We can then calculate a least squares fit for the transformation by

trans = pinv(M) * proj

其中 pinv 是伪逆.

where pinv is the pseudo inverse.

这为我们提供了一个最适合最小二乘意义中给出的点的仿射变换.

This gives us an affine transformation that best fits the points given in the least squares sense.

现在显然这也会产生剪切、坐标翻转以及您不想要的非均匀缩放，因此我们需要以某种方式限制仿射变换以避免剪切.事实证明这很容易，我们可以使用单个向量来描述旋转(向量的方向)和缩放(向量的大小)，另一个向量将与其正交.这将自由度减少了两个.

Now obviously this will also give shear, coordinate flips as well as non-uniform scaling which you did not want so we need to limit the affine transformation in some way to avoid shear. This turns out to be quite easy, we can use a single vector to describe the rotation (direction of the vector) and scaling (magnitude of the vector,) the other vector will simply be orthogonal to it. This reduces the degrees of freedom by two.

M21 = -M12
M22 = M11

所以减少到

[xp0]     [x0  y0 1 0]
[yp0]     [y0 -x0 0 1]
[xp1]     [x1  y1 1 0]     [M11]
[yp1]  =  [y1 -x1 0 1]  *  [M12]
[xp2]     [x2  y2 1 0]     [M13]
[yp2]     [y2 -x2 0 1]     [M23]
[xp3]     [x3  y3 1 0]
[yp3]     [y3 -x3 0 1]

在我们求解了上述矩阵方程后，从 M12 和 M11 计算出 M21 和 M22.

and calculate M21 and M22 from M12 and M11 after we have solved the above matrix equation.

这篇关于两组点之间的变换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！