Прямое линейное преобразование - 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}) в mathbb {R} ^ {2}}$ и ${displaystyle mathbf {y} _ {k} = (y_ {1k}, y_ {2k}, y_ {3k}) в 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 & -1 1 & 0end {pmatrix}}}$

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

${displaystyle {egin {align} (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} конец {выровнено}}}$

С ${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} в mathbb {R} ^ {2}}$ и ${displaystyle mathbf {y} _ {k} в mathbb {R} ^ {3}}$, но общая стратегия переписывания соотношений подобия в однородные линейные уравнения может быть обобщена на произвольные измерения как для ${displaystyle mathbf {x} _ {k}}$ и ${displaystyle mathbf {y} _ {k}.}$

Если ${displaystyle mathbf {x} _ {k} в mathbb {R} ^ {2}}$ и ${displaystyle mathbf {y} _ {k} в 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} в mathbb {R} ^ {p}}$ и ${displaystyle mathbf {y} _ {k} в 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 & 0 & -1 0 & 1 & 0end {pmatrix}}}$,   ${displaystyle mathbf {H} _ {2} = {egin {pmatrix} 0 & 0 & 1 0 & 0 & 0 -1 & 0 & 0end {pmatrix}}}$,   ${displaystyle mathbf {H} _ {3} = {egin {pmatrix} 0 & -1 & 0 1 & 0 & 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}.}$

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

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

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

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

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