Трансформация между двумя наборами точек

У меня есть объект, который можно сказать на образ модели. Я хочу вычислить преобразование (смещение, масштаб, вращение) между объектом на образ модели и объектом на целевом изображении. Я хочу сделать предположение, что объект можно рассматривать как 2D, поэтому должны вычисляться только двумерные преобразования.

Сначала я хочу сделать это вручную. Пользователь выбирает базовую точку на образ модели, а затем целевую точку на целевом изображении. Количество очков должно определяться пользователем (но не менее чем минимум 2-3 очка). Когда точки дают различную информацию, преобразование должно быть усреднено, и, например, из этого может быть вычислено качество соответствия.

Итак, вопросы скорее касаются вычисления преобразования двух наборов точек, но поскольку я хочу сделать это на изображении, я добавил тег обработки изображений.

Особенно приветствуются ссылки и советы с некоторыми фрагментами кода или псевдокода.

С двумя точками это очень простая проблема, нужно брать только поворот, масштаб и смещение линии, но как это сделать с большим количеством точек и усреднением и вычислением некоторых факторов качества.

Текущее решение:

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();
}

Только оптимизация, которую я могу найти в этом коде, заключается в том, чтобы исключить из масштабов и вращений те значения, которые слишком сильно отличаются от остальных.

Я ищу коды или псевдокоды предложений решений. Он также может быть ссылкой на некоторые коды.

До сих пор от ответов я знаю, что:

Можно использовать алгоритм RANSAC
Мне нужно искать алгоритм вычисления аффинного преобразования в наименьшем квадратичном смысле

Ответы

Ответ 1

Сначала обобщите задачу в простом аффинном преобразовании с матрицей аффинного преобразования 3x3: i.e.

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

Поскольку мы уже знаем, что третья строка всегда будет [0 0 1], мы можем просто игнорировать ее.

Теперь мы можем описать проблему как следующее матричное уравнение

[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 - исходные координаты.

Позвольте называть это

proj = M * trans

Затем мы можем вычислить подмножество наименьших квадратов для преобразования через

trans = pinv(M) * proj

где pinv - псевдо-обратный.

Это дает нам аффинное преобразование, которое наилучшим образом соответствует точкам, указанным в смысле наименьших квадратов.

Теперь очевидно, что это также даст сдвиг, координатные сальто, а также неравномерное масштабирование, которое вам не нужно, поэтому нам нужно каким-то образом ограничить аффинное преобразование, чтобы избежать сдвига. Это оказывается довольно простым, мы можем использовать один вектор для описания вращения (направления вектора) и масштабирования (величины вектора), другой вектор будет просто ортогонален ему. Это уменьшает степень свободы на два.

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]

и вычислить M21 и M22 из M12 и M11 после решения вышеуказанного матричного уравнения.

Ответ 2

Я бы попробовал Итеративный алгоритм ближайшей точки.

Здесь вы найдете реализацию с масштабированием. (SICP)

Еще одна полезная ссылка

Ответ 3

Для простоты предположим, что ваши входы x1,...,xn и выходы y1,...,yn являются комплексными числами.

Вы можете вычислить среднее смещение, вычислив avg(y) - avg(x), и как только это будет сделано, вы можете вычесть среднее значение как для x, так и y, чтобы они были центрированы вокруг 0.
Теперь вы хотите найти поворот и масштаб. Вы можете представить как единое комплексное число z, так что x*z должно быть как можно ближе к y. Но x*z является R -линейной функцией (реальных) координат (zx,zy) of z: поэтому вы можете использовать классическую линейную алгебру для решения для z, так что x*z как можно ближе к y в наименьшем квадратном смысле.

Объединяя все это, это дает оптимальное преобразование в наименьшем квадратном смысле.

Ответ 4

Ваше преобразование - это аффинное преобразование, которое может быть записано в матрице 3 * 3. Таким образом, ваша проблема заключается в том, чтобы в основном вычислять аффинное преобразование с наименьшим квадратом ошибки из одного набора точек в другие.

Эта проблема довольно просто решена в общей литературе по вычислительной геометрии. Хорошая классическая книга: http://www.robots.ox.ac.uk/~vgg/hzbook/hzbook1.html (нет рекламы, это просто справочник для большинства людей). Вы найдете всю информацию о 2D и 3D-геометрии. Быстрый google в таких словах, как "аффинное преобразование LMSE", также даст вам информацию и, возможно, коды.

Кроме того, вы также можете использовать другие типы алгоритмов, надежные, такие как RANSAC. В зависимости от вашего приложения может быть интересно идти дальше в этом направлении.

Ответ 5

Подробнее простой и понятный код в Matlab, который может дать вам преобразование.

И более сложный код на С++ (с использованием VXL lib) с включенной оболочкой python и matlab.

Или вы можете использовать некоторый модифицированный алгоритм ICP (итеративная ближайшая точка), который устойчив к шуму.