Прямое линейное преобразование (DLT) - алгоритм, который решает набор переменных из набора отношений подобия:
за ![, k = 1, ldots, N](https://wikimedia.org/api/rest_v1/media/math/render/svg/68e1d42aadf6846d3b9704d4b2c793f84f055d1b)
куда
и
известные векторы,
обозначает равенство с точностью до неизвестного скалярного умножения, а
представляет собой матрицу (или линейное преобразование), которая содержит неизвестные, которые необходимо решить.
Этот тип отношений часто встречается в проективная геометрия. Практические примеры включают соотношение между трехмерными точками в сцене и их проекцию на плоскость изображения объекта. камеры-обскуры,[1] и омографии.
Вступление
Обычный система линейных уравнений
за ![, k = 1, ldots, N](https://wikimedia.org/api/rest_v1/media/math/render/svg/68e1d42aadf6846d3b9704d4b2c793f84f055d1b)
можно решить, например, переписав его в виде матричного уравнения
где матрицы
и
содержат векторы
и
в соответствующих столбцах. Учитывая, что существует единственное решение, оно задается формулой
![{mathbf {A}} = {mathbf {X}}, {mathbf {Y}} ^ {{T}}, ({mathbf {Y}}, {mathbf {Y}} ^ {{T}}) ^ { {-1}}.](https://wikimedia.org/api/rest_v1/media/math/render/svg/1d76d52600ef10411dca421e8288b7385af83326)
Решения также могут быть описаны в случае, если уравнения переопределены или недоопределены.
Отличие задачи прямого линейного преобразования от приведенного выше стандартного случая заключается в том, что левая и правая части определяющего уравнения могут отличаться неизвестным мультипликативным множителем, который зависит от k. Как следствие,
невозможно вычислить, как в стандартном случае. Вместо этого отношения подобия переписываются в виде собственных линейных однородных уравнений, которые затем могут быть решены стандартным методом. Комбинация переписывания уравнений подобия в виде однородных линейных уравнений и их решения стандартными методами называется алгоритм прямого линейного преобразования или же Алгоритм DLT. DLT приписывают Ивану Сазерленду.[2]
Пример
Предположим, что
. Позволять
и
- два известных вектора, и мы хотим найти
матрица
такой, что
![альфа _ {{k}}, {mathbf {x}} _ {{k}} = {mathbf {A}}, {mathbf {y}} _ {{k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e1836ab366369f559725fc7f005dc86e2b89ac60)
куда
неизвестный скалярный множитель, связанный с уравнением k.
Чтобы избавиться от неизвестных скаляров и получить однородные уравнения, определите антисимметричную матрицу
![{mathbf {H}} = {egin {pmatrix} 0 & -1 1 & 0end {pmatrix}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d0d476dceea8b50749284028cdaf59f67614e2c)
и умножим обе части уравнения на
слева
![{displaystyle {egin {выравнивается} (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} конец {выровнено}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/257bc599e3d0f21997708e457938044ff1f5c363)
С
следующие однородные уравнения, которые больше не содержат неизвестных скаляров, находятся под рукой
![{displaystyle mathbf {x} _ {k} ^ {T}, mathbf {H}, mathbf {A}, mathbf {y} _ {k} = 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc412bb7591b0ad0af1a5060765ee67c7577cd8a)
Чтобы решить
из этой системы уравнений рассмотрим элементы векторов
и
и матрица
:
,
, и ![{mathbf {A}} = {egin {pmatrix} a _ {{11}} & a _ {{12}} & a _ {{13}} a _ {{21}} & a _ {{22}} & a _ {{23}} конец {pmatrix}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee4042f3dce75ef30b5332bb4f5e639cce5f265d)
и полученное выше однородное уравнение принимает вид
за ![, k = 1, ldots, N.](https://wikimedia.org/api/rest_v1/media/math/render/svg/0f6dc74aa238a4cc1b1267d6f55c0607c2e7c95a)
Это также можно записать в матричной форме:
за ![, k = 1, ldots, N](https://wikimedia.org/api/rest_v1/media/math/render/svg/68e1d42aadf6846d3b9704d4b2c793f84f055d1b)
куда
и
оба являются 6-мерными векторами, определенными как
и ![{mathbf {a}} = {egin {pmatrix} a _ {{11}} a _ {{21}} a _ {{12}} a _ {{22}} a _ {{13}} a _ {{ 23}} конец {pmatrix}}.](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a1d0b147ffa8e0b0bdb5f643e7df475c99460ea)
Пока у нас есть 1 уравнение и 6 неизвестных. Систему однородных уравнений можно записать в матричной форме
![{mathbf {0}} = {mathbf {B}}, {mathbf {a}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d35677df68c1308a5f6e28247a77eac6ec0a29b)
куда
это
матрица, содержащая известные векторы
в его рядах. Неизвестный
может быть определена, например, разложение по сингулярным числам из
;
является правым сингулярным вектором
соответствующий сингулярному значению, равному нулю. Один раз
определено, элементы матрицы
можно переставить из вектора
. Обратите внимание, что масштабирование
или же
не имеет значения (за исключением того, что он должен быть ненулевым), поскольку определяющие уравнения уже допускают неизвестное масштабирование.
На практике векторы
и
может содержать шум, что означает, что уравнения подобия действительны только приблизительно. Как следствие, может не быть вектора
которое решает однородное уравнение
точно. В этих случаях Всего наименьших квадратов решение можно использовать, выбрав
как правый сингулярный вектор, соответствующий наименьшему сингулярному значению ![{mathbf {B}}.](https://wikimedia.org/api/rest_v1/media/math/render/svg/50aa2166ab057f61bca09362e494694450541512)
Более общие случаи
В приведенном выше примере
и
, но общая стратегия переписывания соотношений подобия в однородные линейные уравнения может быть обобщена на произвольные измерения как для
и ![{mathbf {y}} _ {{k}}.](https://wikimedia.org/api/rest_v1/media/math/render/svg/7850e49540eabd74da1ee3d5536d4195fd9a7ec3)
Если
и
предыдущие выражения все еще могут привести к уравнению
за ![, k = 1, ldots, N](https://wikimedia.org/api/rest_v1/media/math/render/svg/68e1d42aadf6846d3b9704d4b2c793f84f055d1b)
куда
сейчас
Каждый k дает одно уравнение в
неизвестные элементы
и вместе эти уравнения можно записать
для известных
матрица
и неизвестно 2кв.-мерный вектор
Этот вектор можно найти так же, как и раньше.
В самом общем случае
и
. Основное отличие от предыдущей в том, что матрица
сейчас
и антисимметричный. Когда
пространство таких матриц уже не одномерно, а размерно
![M = {гидроразрыв {p, (p-1)} {2}}.](https://wikimedia.org/api/rest_v1/media/math/render/svg/2bd7528f537a85ccbf33039b557b455ea3f3943c)
Это означает, что каждое значение k обеспечивает M однородные уравнения типа
за
и для ![, k = 1, ldots, N](https://wikimedia.org/api/rest_v1/media/math/render/svg/68e1d42aadf6846d3b9704d4b2c793f84f055d1b)
куда
это M-мерный базис пространства
антисимметричные матрицы.
Пример п = 3
В случае, если п = 3 следующие три матрицы
можно выбрать