Есть два изображения плоского предмета (например книга). Найден набор нумерованных ключевых точек на обоих фото. Установлено их соответствие. Требуется найти линейное преобразование (масштаб, поворот, перспектива) от одного фото к другому.
Понятно, что для любых четвёрток точек можно составить систему линейных уравнений, и решив её, получить параметры преобразования плоскости.
Но дело в том, что такие четвёрки можно выбрать множеством способов, и решения систем будет немного различаться (в силу неточности координат распознанных ключевых точек). Т.е. есть избыточное количество конкурирующих систем линейных уравнений.
Не могу придумать как быстро получить параметры наилучшего преобразования. Перебор всех вариантов формирования четвёрток — не реален, да и понятно, что это в целом плохой путь. А как быть?
Критерий наилучшести — минимум суммы среднеквадратичных отклонений образов всех точек первого фото от фактических точек второго фото.
А визуально - можете пример привести? (было бы проще обсуждать)
Ещё вопрос: предметы - одинаковые (т.е., экземпляр) или подобные (т.е., книга "A" и книга "Б")?
Оси вращения и оси симметрии - нужно искать первым делом на основе топологии объекта по контрольным точкам.
Один и тот же предмет. Установлен большой набор парных ключевых точек. Предмет произвольно повёрнут в пространстве и масштабирован. Упрощающий момент: поверхность предмета плоская.
По любой четвёрке находим ориентировочное решение. Далее, задав точность, применяем найденное решение с поправкой на +-delta. Находим наиболее оптимальное дельта по указанному критерию.
Поясню:
1) нашли афинное преобразование: +10 - сдвиг всех точек на 10 вправо
2) задаём точность: 0,01
3) в цикле оцениваем ваш критерий для всех сдвигов вправо от 5 до 15 с шагом 0,01
4) выбираем лучший сдвиг
Спасибо, Griboks, но вы сильно упростили задачу. Вы пишите об одном преобразовании — трансляции. У меня же многопараметрическая задача. В ней так перебирать "подвижки" четырёх параметров в различных сочетаниях — совершенно не вариант.
У меня: 3 угла вращения пространства, плюс 3 компоненты вектора трансляции, плюс 1 масштабный фактор, минус 3 параметра за счёт того, что все точки на одной плоскости. Равно 4 свободных параметра.
Пусть координаты точек первой картинки = P[i], второй = V[i] (каждая координата = вектор с двумя значениями).
Далее надо записать линейное преобразование:
P[i] -> A + B*P[i]
(A и B тоже имеют по две компоненты; A = вообще нормальный обычный вектор).
Ищем разницу, возводим в квадрат:
(A + B*P[i] - V[i])^2
суммируем это по i (по всем точкам).
Теперь берём четыре частные производные по каждой компоненте A и B, приравниваем их к нулю. Получаем четыре линейных уравнения.
Ну а решать линейные уравнения - должен уметь всякий.
Upd1: Что такое "перспектива" - я не понял. Наклон фотоаппарата, что ли?
Если B - это одна компонента, то алгоритм остаётся прежний.
Upd2: Если надо учитывать ещё и возможность поворота на определённый угол - будет сложнее; но преобразование всё равно линейное.
У нас есть функция "суммарное квадратичное отклонение". И мы берём частные производные от этой функции по A и по B.
То, что A является вектором, а B является матрицей - нас не пугает. Мы просто получаем больше переменных: A1, A2, B11, B12, B21, B22.
В начальный момент решения задачи - это не числа, а переменные, значение которых мы ищем. Т.е. это параметры функции "суммарное квадратичное отклонение" - и мы ищем частные производные этой функции по каждому из шести параметров.
Слово "частная производная" означает, что когда я беру производную по одному из параметров - остальные "замирают" и считаются константами. В Википедии это д.б. написано.
Karpion, спасибо за советы. В принципе по такой схеме у надо действовать. Пояснять тонкости сложно, но нам надо оставаться в определённом классе преобразование движения пространства, а не вообще всех любых линейных преобразований. Может так статься, что простой минимум отклонений (почти наверняка) окажется за пределами нужного класса (группы) преобразование. Поэтому надо брать в качестве параметров не просто В11, В11, а какие-то "правильно" параметризованные компоненты матрицы (например через углы поворотов), чтобы преобразование оставалось в группе.
Ну, Вы бы для начала расписали полный список возможных преобразований. Никто не любит внезапной смены условий задачи.
Есть такой метод решения:
Сначала мы хоть как-то (можно криво) линеаризуем задачу. Линейные уравнения решаются легко.
Допустим, возможные преобразования - это сдвиг, масштаб и поворот: итого четыре параметра. Но мы решим это по вышеприведённой схеме и получим шесть параметров.
После этого мы считаем. что сдвиг посчитан верно, а из матрицы B как-то вычисляем масштаб и поворот (как - я пока не придумал; если будет актуально, подумаю ещё). Полученные {сдвиг, масштаб и поворот} мы можем использовать как отправную точку для дальнейших поисков - например, симплекс-методом.
