Вывести матрицу преобразования с учетом изображения и преобразованного изображения?

Question

Я работаю над проектом, включающим поиск путей с использованием алгоритма A * (Спасибо, Патрик Лестер, за отличный учебник) . Предоставляется серия карт PNG, точки интереса определяются координатами, полученными от веб-службы, и проблема состоит в том, чтобы показать пути между этими точками. Сначала это было что-то вроде катастрофы, потому что различные уровни не были расположены в одной и той же системе координат, и поэтому перемещение с одного уровня на другой приводило к непреднамеренному сдвигу координат x и y, а не только к изменению z - что делает стоимость и эвристику изменение уровня совершенно странное, с некоторыми очень неоптимальными путями.

Чтобы исправить это, я мог бы разбить расчет пути на решения для каждого уровня с переходом на новый уровень в качестве промежуточного, не рассчитанного шага. Вместо этого я решил сделать все карты уровней частью одной системы координат, чтобы при взгляде на лифт на одном уровне лифт присутствовал на всех уровнях, которых он достигал с одинаковыми координатами x и y.

Единственная проблема - это координаты точек интереса, используемые оригинальными картами. Эти координаты не соответствуют чему-либо значимому на новых картах. Хотя я уверен, что теперь путь работает хорошо, система в целом не работает, потому что начальная и конечная точки пути неправильно отображаются в системе карт.

Чтобы получить новые карты (все они находятся в одном координатном пространстве) из старых карт, каждая из них была преобразована простым и воспроизводимым способом. Я полагаю, что если я получу координату и применю к ней то же преобразование, что и к карте, на которую она ссылается, все будет хорошо. Карты повернуты, изменены в размере и переведены.

Для изображения и полученного преобразованного изображения существует ли способ получить матрицу преобразования? Это проект для iPhone, поэтому в идеале я ищу CGAffineTransform. Для каждой карты я мог бы снова манипулировать старой картой, чтобы получить новую карту и записать выполняемое преобразование, но мне любопытно, есть ли способ работать в обратном направлении.

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

Answer 1

Для нахождения преобразования вам необходим минимум точечных координат (исходный и преобразованный), равный количеству параметров.

Если вы работаете с изображениями, а не с идеальными геометрическими объектами, вычисление Наименьших квадратов будет намного лучше.Используя больше точек, вы уменьшаете ошибки, вызванные квантованием пространства (т. Е. Пиксели).

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

HTH!

Answer 2

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

xA = B

//Where A is the original image, B is the transform, and x is the transform matrix. 
//Now to find x:

x = B(A^-1)

т.е. умножение обеих сторон на инверсию A позволит вам найти x, матрицу преобразования (см. здесь подробнее о инверсии матрицы).

Как бы вы применили это к CGAffineTransform или нашли инверсию изображения в вашем случае, я не слишком уверен! Но приведенная выше математика показывает, что то, что вы просите, вполне выполнимо. Надеюсь, это поможет!