Прямое линейное преобразование - Direct linear transformation

Прямое линейное преобразование (DLT) - алгоритм, который решает набор переменных из набора отношений подобия:

${displaystyle mathbf {x} _{k}propto mathbf {A} ,mathbf {y} _{k}}$ за ${displaystyle ,k=1,ldots ,N}$

куда ${displaystyle mathbf {x} _{k}}$ и ${displaystyle mathbf {y} _{k}}$ известные векторы, ${displaystyle ,propto }$ обозначает равенство с точностью до неизвестного скалярного умножения, а ${displaystyle mathbf {A} }$ представляет собой матрицу (или линейное преобразование), которая содержит неизвестные, которые необходимо решить.

Этот тип отношений часто встречается в проективная геометрия. Практические примеры включают соотношение между трехмерными точками в сцене и их проекцию на плоскость изображения объекта. камеры-обскуры,^[1] и омографии.

Вступление

Обычный система линейных уравнений

${displaystyle mathbf {x} _{k}=mathbf {A} ,mathbf {y} _{k}}$ за ${displaystyle ,k=1,ldots ,N}$

можно решить, например, переписав его в виде матричного уравнения ${displaystyle mathbf {X} =mathbf {A} ,mathbf {Y} }$ где матрицы ${displaystyle mathbf {X} }$ и ${displaystyle mathbf {Y} }$ содержат векторы ${displaystyle mathbf {x} _{k}}$ и ${displaystyle mathbf {y} _{k}}$ в соответствующих столбцах. Учитывая, что существует единственное решение, оно задается формулой

${displaystyle mathbf {A} =mathbf {X} ,mathbf {Y} ^{T},(mathbf {Y} ,mathbf {Y} ^{T})^{-1}.}$

Решения также могут быть описаны в случае, если уравнения переопределены или недоопределены.

Отличие задачи прямого линейного преобразования от приведенного выше стандартного случая заключается в том, что левая и правая части определяющего уравнения могут отличаться неизвестным мультипликативным множителем, который зависит от k. Как следствие, ${displaystyle mathbf {A} }$ невозможно вычислить, как в стандартном случае. Вместо этого отношения подобия переписываются в виде собственных линейных однородных уравнений, которые затем могут быть решены стандартным методом. Комбинация переписывания уравнений подобия в виде однородных линейных уравнений и их решения стандартными методами называется алгоритм прямого линейного преобразования или же Алгоритм DLT. DLT приписывают Ивану Сазерленду.^[2]

Пример

Предположим, что ${displaystyle kin {1,...,N}}$. Позволять ${displaystyle mathbf {x} _{k}=(x_{1k},x_{2k})in mathbb {R} ^{2}}$ и ${displaystyle mathbf {y} _{k}=(y_{1k},y_{2k},y_{3k})in mathbb {R} ^{3}}$ - два известных вектора, и мы хотим найти ${displaystyle 2 imes 3}$ матрица ${displaystyle mathbf {A} }$ такой, что

${displaystyle alpha _{k},mathbf {x} _{k}=mathbf {A} ,mathbf {y} _{k}}$

куда ${displaystyle alpha _{k}eq 0}$ неизвестный скалярный множитель, связанный с уравнением k.

Чтобы избавиться от неизвестных скаляров и получить однородные уравнения, определите антисимметричную матрицу

${displaystyle mathbf {H} ={egin{pmatrix}0&-11&0end{pmatrix}}}$

и умножим обе части уравнения на ${displaystyle mathbf {x} _{k}^{T},mathbf {H} }$ слева

${displaystyle {egin{aligned}(mathbf {x} _{k}^{T},mathbf {H} ),alpha _{k},mathbf {x} _{k}&=(mathbf {x} _{k}^{T},mathbf {H} ),mathbf {A} ,mathbf {y} _{k}alpha _{k},mathbf {x} _{k}^{T},mathbf {H} ,mathbf {x} _{k}&=mathbf {x} _{k}^{T},mathbf {H} ,mathbf {A} ,mathbf {y} _{k}end{aligned}}}$

С ${displaystyle mathbf {x} _{k}^{T},mathbf {H} ,mathbf {x} _{k}=0,}$ следующие однородные уравнения, которые больше не содержат неизвестных скаляров, находятся под рукой

${displaystyle mathbf {x} _{k}^{T},mathbf {H} ,mathbf {A} ,mathbf {y} _{k}=0}$

Чтобы решить ${displaystyle mathbf {A} }$ из этой системы уравнений рассмотрим элементы векторов ${displaystyle mathbf {x} _{k}}$ и ${displaystyle mathbf {y} _{k}}$ и матрица ${displaystyle mathbf {A} }$:

${displaystyle mathbf {x} _{k}={egin{pmatrix}x_{1k}x_{2k}end{pmatrix}}}$,   ${displaystyle mathbf {y} _{k}={egin{pmatrix}y_{1k}y_{2k}y_{3k}end{pmatrix}}}$, и ${displaystyle mathbf {A} ={egin{pmatrix}a_{11}&a_{12}&a_{13}a_{21}&a_{22}&a_{23}end{pmatrix}}}$

и полученное выше однородное уравнение принимает вид

${displaystyle 0=a_{11},x_{2k},y_{1k}-a_{21},x_{1k},y_{1k}+a_{12},x_{2k},y_{2k}-a_{22},x_{1k},y_{2k}+a_{13},x_{2k},y_{3k}-a_{23},x_{1k},y_{3k}}$ за ${displaystyle ,k=1,ldots ,N.}$

Это также можно записать в матричной форме:

${displaystyle 0=mathbf {b} _{k}^{T},mathbf {a} }$ за ${displaystyle ,k=1,ldots ,N}$

куда ${displaystyle mathbf {b} _{k}}$ и ${displaystyle mathbf {a} }$ оба являются 6-мерными векторами, определенными как

${displaystyle mathbf {b} _{k}={egin{pmatrix}x_{2k},y_{1k}-x_{1k},y_{1k}x_{2k},y_{2k}-x_{1k},y_{2k}x_{2k},y_{3k}-x_{1k},y_{3k}end{pmatrix}}}$ и ${displaystyle mathbf {a} ={egin{pmatrix}a_{11}a_{21}a_{12}a_{22}a_{13}a_{23}end{pmatrix}}.}$

Пока у нас есть 1 уравнение и 6 неизвестных. Систему однородных уравнений можно записать в матричной форме

${displaystyle mathbf {0} =mathbf {B} ,mathbf {a} }$

куда ${displaystyle mathbf {B} }$ это ${displaystyle N imes 6}$ матрица, содержащая известные векторы ${displaystyle mathbf {b} _{k}}$ в его рядах. Неизвестный ${displaystyle mathbf {a} }$ может быть определена, например, разложение по сингулярным числам из ${displaystyle mathbf {B} }$; ${displaystyle mathbf {a} }$ является правым сингулярным вектором ${displaystyle mathbf {B} }$ соответствующий сингулярному значению, равному нулю. Один раз ${displaystyle mathbf {a} }$ определено, элементы матрицы ${displaystyle mathbf {A} }$ можно переставить из вектора ${displaystyle mathbf {a} }$. Обратите внимание, что масштабирование ${displaystyle mathbf {a} }$ или же ${displaystyle mathbf {A} }$ не имеет значения (за исключением того, что он должен быть ненулевым), поскольку определяющие уравнения уже допускают неизвестное масштабирование.

На практике векторы ${displaystyle mathbf {x} _{k}}$ и ${displaystyle mathbf {y} _{k}}$ может содержать шум, что означает, что уравнения подобия действительны только приблизительно. Как следствие, может не быть вектора ${displaystyle mathbf {a} }$ которое решает однородное уравнение ${displaystyle mathbf {0} =mathbf {B} ,mathbf {a} }$ точно. В этих случаях Всего наименьших квадратов решение можно использовать, выбрав ${displaystyle mathbf {a} }$ как правый сингулярный вектор, соответствующий наименьшему сингулярному значению ${displaystyle mathbf {B} .}$

Более общие случаи

В приведенном выше примере ${displaystyle mathbf {x} _{k}in mathbb {R} ^{2}}$ и ${displaystyle mathbf {y} _{k}in mathbb {R} ^{3}}$, но общая стратегия переписывания соотношений подобия в однородные линейные уравнения может быть обобщена на произвольные измерения как для ${displaystyle mathbf {x} _{k}}$ и ${displaystyle mathbf {y} _{k}.}$

Если ${displaystyle mathbf {x} _{k}in mathbb {R} ^{2}}$ и ${displaystyle mathbf {y} _{k}in mathbb {R} ^{q}}$ предыдущие выражения все еще могут привести к уравнению

${displaystyle 0=mathbf {x} _{k}^{T},mathbf {H} ,mathbf {A} ,mathbf {y} _{k}}$ за ${displaystyle ,k=1,ldots ,N}$

куда ${displaystyle mathbf {A} }$ сейчас ${displaystyle 2 imes q.}$ Каждый k дает одно уравнение в ${displaystyle 2q}$ неизвестные элементы ${displaystyle mathbf {A} }$ и вместе эти уравнения можно записать ${displaystyle mathbf {B} ,mathbf {a} =mathbf {0} }$ для известных ${displaystyle N imes 2,q}$ матрица ${displaystyle mathbf {B} }$ и неизвестно 2кв.-мерный вектор ${displaystyle mathbf {a} .}$ Этот вектор можно найти так же, как и раньше.

В самом общем случае ${displaystyle mathbf {x} _{k}in mathbb {R} ^{p}}$ и ${displaystyle mathbf {y} _{k}in mathbb {R} ^{q}}$. Основное отличие от предыдущей в том, что матрица ${displaystyle mathbf {H} }$ сейчас ${displaystyle p imes p}$ и антисимметричный. Когда ${displaystyle p>2}$ пространство таких матриц уже не одномерно, а размерно

${displaystyle M={frac {p,(p-1)}{2}}.}$

Это означает, что каждое значение k обеспечивает M однородные уравнения типа

${displaystyle 0=mathbf {x} _{k}^{T},mathbf {H} _{m},mathbf {A} ,mathbf {y} _{k}}$ за ${displaystyle ,m=1,ldots ,M}$ и для ${displaystyle ,k=1,ldots ,N}$

куда ${displaystyle mathbf {H} _{m}}$ это M-мерный базис пространства ${displaystyle p imes p}$ антисимметричные матрицы.

Пример п = 3

В случае, если п = 3 следующие три матрицы ${displaystyle mathbf {H} _{m}}$ можно выбрать

${displaystyle mathbf {H} _{1}={egin{pmatrix}0&0&0�&0&-1�&1&0end{pmatrix}}}$,   ${displaystyle mathbf {H} _{2}={egin{pmatrix}0&0&1�&0&0-1&0&0end{pmatrix}}}$,   ${displaystyle mathbf {H} _{3}={egin{pmatrix}0&-1&01&0&0�&0&0end{pmatrix}}.}$

В этом частном случае однородные линейные уравнения можно записать как

${displaystyle mathbf {0} =[mathbf {x} _{k}]_{ imes },mathbf {A} ,mathbf {y} _{k}}$ за ${displaystyle ,k=1,ldots ,N}$

куда ${displaystyle [mathbf {x} _{k}]_{ imes }}$ это матричное представление векторного векторного произведения. Обратите внимание, что это последнее уравнение является векторным; левая часть - нулевой элемент в ${displaystyle mathbb {R} ^{3}}$.

Каждое значение k дает три однородных линейных уравнения относительно неизвестных элементов ${displaystyle mathbf {A} }$. Однако, поскольку ${displaystyle [mathbf {x} _{k}]_{ imes }}$ имеет ранг = 2, не более двух уравнений линейно независимы. Поэтому на практике обычно используются только две из трех матриц ${displaystyle mathbf {H} _{m}}$, например, для м= 1, 2. Однако линейная зависимость между уравнениями зависит от ${displaystyle mathbf {x} _{k}}$, а значит, в неудачных случаях лучше было бы выбрать, например, м= 2,3. Как следствие, если количество уравнений не вызывает беспокойства, может быть лучше использовать все три уравнения, когда матрица ${displaystyle mathbf {B} }$ построен.

Линейная зависимость между полученными однородными линейными уравнениями является общей проблемой для случая п > 2, и с этим нужно бороться либо путем сокращения набора антисимметричных матриц ${displaystyle mathbf {H} _{m}}$ или разрешив ${displaystyle mathbf {B} }$ стать больше, чем необходимо для определения ${displaystyle mathbf {a} .}$

Рекомендации

1. Abdel-Aziz, Y.I .; Карара, Х. (2015-02-01). «Прямое линейное преобразование из координат компаратора в координаты пространства объекта в фотограмметрии ближнего действия». Фотограмметрическая инженерия и дистанционное зондирование. Американское общество фотограмметрии и дистанционного зондирования. 81 (2): 103–107. Дои:10.14358 / чел. 81.2.103. ISSN  0099-1112.
2. Сазерленд, Иван Э. (апрель 1974 г.), «Трехмерный ввод данных с помощью планшета», Труды IEEE, 62 (4): 453–461, Дои:10.1109 / PROC.1974.9449

• Ричард Хартли и Эндрю Зиссерман (2003). Многоканальная геометрия в компьютерном зрении. Издательство Кембриджского университета. ISBN  978-0-521-54051-3.

внешняя ссылка

• Оценка гомографии Элан Дуброфски (§2.1 набрасывает "Базовый алгоритм DLT")

• Решатель DLT на основе MATLAB Сян-Джен (Джонни) Чиен