Восьмиточечный алгоритм

Алгоритм восьми точек — это алгоритм, используемый в компьютерном зрении для оценки существенной матрицы или фундаментальной матрицы, связанной с парой стереокамер, из набора соответствующих точек изображения. Он был введен Кристофером Лонге-Хиггинсом в 1981 году для случая существенной матрицы. Теоретически этот алгоритм можно использовать и для фундаментальной матрицы, но на практике для этого случая лучше подходит нормализованный восьмиточечный алгоритм , описанный Ричардом Хартли в 1997 году.

Название алгоритма происходит от того факта, что он оценивает существенную матрицу или фундаментальную матрицу на основе набора из восьми (или более) соответствующих точек изображения. Однако варианты алгоритма можно использовать менее чем для восьми точек.

Ограничение копланарности

Дополнительная информация: Эпиполярная геометрия.

Пример эпиполярной геометрии. Две камеры с соответствующими центрами проекционных точек O _L и O _R наблюдают за точкой P . Проекция P на каждую из плоскостей изображения обозначается p _L и p _R . Точки E _L и E _R являются эпиполями.

можно выразить Эпиполярную геометрию двух камер и точки пространства с помощью алгебраического уравнения. Заметьте, что независимо от того, где находится точка $P$ находится в космосе, векторы ${\overline {O_{L}P}}$, ${\overline {O_{R}P}}$ и ${\overline {O_{R}O_{L}}}$ принадлежат одной плоскости. Вызов $X_{L}$ координаты точки $P$ в системе отсчета левого глаза и вызовите $X_{R}$ координаты $P$ в системе отсчета правого глаза и позвоните $R,T$ вращение и перемещение между двумя системами отсчета st $X_{R}=R(X_{L}-T)$ это связь между координатами $P$ в двух системах отсчета. Следующее уравнение всегда выполняется, поскольку вектор, созданный из $T\wedge X_{L}$ ортогонален обоим $T$ и $X_{L}$ :

$X_{L}^{T}T\wedge X_{L}-T^{T}T\wedge X_{L}=(X_{L}-T)^{T}T\wedge X_{L}=0$

Потому что $I=R^{T}R$, мы получаем

$(X_{L}-T)^{T}R^{T}RT\wedge X_{L}=0$.

Замена $(X_{L}-T)^{T}R^{T}$ с $X_{R}^{T}$, мы получаем

$X_{R}^{T}RT\wedge X_{L}=X_{R}^{T}RSX_{L}=X_{R}^{T}EX_{L}=0$

Обратите внимание, что $T\wedge$ можно рассматривать как матрицу; Лонге-Хиггинс использовал символ $S$ чтобы обозначить это. Продукт $RT\wedge =RS$ часто называют существенной матрицей и обозначают $E$.

Векторы ${\overline {O_{L}p_{L}}},{\overline {O_{R}p_{R}}}$ параллельны векторам ${\overline {O_{L}P}},{\overline {O_{R}P}}$ и, следовательно, ограничение компланарности сохраняется, если мы заменим эти векторы. Если мы позвоним $y,y'$ координаты проекций $P$ на левую и правую плоскости изображения, то ограничение компланарности можно записать как

$y'^{T}\mathbf {E} y=0$

Основной алгоритм

Здесь описан базовый алгоритм из восьми пунктов для случая оценки существенной матрицы $\mathbf {E}$. Он состоит из трех шагов. Во-первых, он формулирует однородное линейное уравнение , решение которого напрямую связано с $\mathbf {E}$, а затем решает уравнение, учитывая, что оно может не иметь точного решения. Наконец, управляются внутренние ограничения результирующей матрицы. Первый шаг описан в статье Лонге-Хиггинса, второй и третий шаги представляют собой стандартные подходы в теории оценивания.

Ограничение, определяемое существенной матрицей $\mathbf {E}$ является

$(\mathbf {y} ')^{T}\,\mathbf {E} \,\mathbf {y} =0$

для соответствующих точек изображения, представленных в нормализованных координатах изображения $\mathbf {y} ,\mathbf {y} '$. Задача, которую решает алгоритм, заключается в определении $\mathbf {E}$ для набора совпадающих точек изображения. На практике на координаты точек изображения влияет шум, и решение также может быть переопределено, что означает, что найти его может быть невозможно. $\mathbf {E}$ которое удовлетворяет указанному выше ограничению точно для всех точек. Эта проблема решается на втором этапе алгоритма.

Шаг 1: Формулировка однородного линейного уравнения

С

$\mathbf {y} ={\begin{pmatrix}y_{1}\\y_{2}\\1\end{pmatrix}}$ и $\mathbf {y} '={\begin{pmatrix}y'_{1}\\y'_{2}\\1\end{pmatrix}}$ и $\mathbf {E} ={\begin{pmatrix}e_{11}&e_{12}&e_{13}\\e_{21}&e_{22}&e_{23}\\e_{31}&e_{32}&e_{33}\end{pmatrix}}$

ограничение также можно переписать как

$y'_{1}y_{1}e_{11}+y'_{1}y_{2}e_{12}+y'_{1}e_{13}+y'_{2}y_{1}e_{21}+y'_{2}y_{2}e_{22}+y'_{2}e_{23}+y_{1}e_{31}+y_{2}e_{32}+e_{33}=0\,$

или

$\mathbf {e} \cdot {\tilde {\mathbf {y} }}=0$

где

${\tilde {\mathbf {y} }}={\begin{pmatrix}y'_{1}y_{1}\\y'_{1}y_{2}\\y'_{1}\\y'_{2}y_{1}\\y'_{2}y_{2}\\y'_{2}\\y_{1}\\y_{2}\\1\end{pmatrix}}$ и $\mathbf {e} ={\begin{pmatrix}e_{11}\\e_{12}\\e_{13}\\e_{21}\\e_{22}\\e_{23}\\e_{31}\\e_{32}\\e_{33}\end{pmatrix}}$

то есть, $\mathbf {e}$ представляет собой существенную матрицу в виде 9-мерного вектора, и этот вектор должен быть ортогональным вектору ${\tilde {\mathbf {y} }}$ который можно рассматривать как векторное представление $3\times 3$ матрица $\mathbf {y} '\,\mathbf {y} ^{T}$.

Каждая пара соответствующих точек изображения создает вектор ${\tilde {\mathbf {y} }}$. Учитывая набор 3D-точек $\mathbf {P} _{k}$ это соответствует набору векторов ${\tilde {\mathbf {y} }}_{k}$ и все они должны удовлетворять

$\mathbf {e} \cdot {\tilde {\mathbf {y} }}_{k}=0$

для вектора $\mathbf {e}$. Учитывая достаточное количество (не менее восьми) линейно независимых векторов ${\tilde {\mathbf {y} }}_{k}$ можно определить $\mathbf {e}$ прямым способом. Собрать все векторы ${\tilde {\mathbf {y} }}_{k}$ как столбцы матрицы $\mathbf {Y}$ и тогда должно быть так, что

$\mathbf {e} ^{T}\,\mathbf {Y} =\mathbf {0}$

Это означает, что $\mathbf {e}$ является решением однородного линейного уравнения .

Шаг 2: Решение уравнения

Стандартный подход к решению этого уравнения подразумевает, что $\mathbf {e}$ является правым сингулярным вектором $\mathbf {Y}$ соответствующее сингулярному значению , равному нулю. При условии, что не менее восьми линейно независимых векторов ${\tilde {\mathbf {y} }}_{k}$ используются для построения $\mathbf {Y}$ то этот сингулярный вектор единственен (без учета скалярного умножения) и, следовательно, $\mathbf {e}$ а потом $\mathbf {E}$ можно определить.

В случае, если для построения используется более восьми соответствующих точек $\mathbf {Y}$ возможно, что он не имеет какого-либо единственного значения, равного нулю. На практике такой случай имеет место, когда на координаты изображения влияют различные виды шума. Общий подход к решению этой ситуации состоит в том, чтобы описать ее как задачу полного наименьших квадратов ; находить $\mathbf {e}$ что сводит к минимуму

$\|\mathbf {e} ^{T}\,\mathbf {Y} \|$

когда $\|\mathbf {e} \|=1$. Решение состоит в том, чтобы выбрать $\mathbf {e}$ как левый сингулярный вектор, соответствующий наименьшему сингулярному значению $\mathbf {Y}$. Изменение порядка этого $\mathbf {e}$ обратно в $3\times 3$ матрица дает результат этого шага, называемый здесь $\mathbf {E} _{\rm {est}}$.

Шаг 3. Обеспечение соблюдения внутреннего ограничения

Другим последствием работы с зашумленными координатами изображения является то, что результирующая матрица может не удовлетворять внутреннему ограничению основной матрицы, то есть два ее сингулярных значения равны и ненулевые, а другое равно нулю. В зависимости от применения, меньшие или большие отклонения от внутреннего ограничения могут быть проблемой, а могут и не быть. Если критично, чтобы оцененная матрица удовлетворяла внутренним ограничениям, этого можно добиться, найдя матрицу $\mathbf {E} '$ ранга 2, что минимизирует

$\|\mathbf {E} '-\mathbf {E} _{\rm {est}}\|$

где $\mathbf {E} _{\rm {est}}$ — это результирующая матрица, полученная на этапе 2, и норма матрицы Фробениуса используется . Решение проблемы дается путем сначала вычисления сингулярным значениям разложения по $\mathbf {E} _{\rm {est}}$:

$\mathbf {E} _{\rm {est}}=\mathbf {U} \,\mathbf {S} \,\mathbf {V} ^{T}$

где $\mathbf {U} ,\mathbf {V}$ являются ортогональными матрицами и $\mathbf {S}$ - диагональная матрица, содержащая сингулярные значения $\mathbf {E} _{\rm {est}}$. В идеальном случае один из диагональных элементов $\mathbf {S}$ должно быть равно нулю или, по крайней мере, мало по сравнению с двумя другими, которые должны быть равны. В любом случае ставьте

$\mathbf {S} '={\begin{pmatrix}s_{1}&0&0\\0&s_{2}&0\\0&0&0\end{pmatrix}},$

где $s_{1},s_{2}$ являются крупнейшими и вторыми по величине сингулярными значениями в $\mathbf {S}$ соответственно. Окончательно, $\mathbf {E} '$ дается

$\mathbf {E} '=\mathbf {U} \,\mathbf {S} '\,\mathbf {V} ^{T}$

Матрица $\mathbf {E} '$ — результирующая оценка существенной матрицы, предоставляемая алгоритмом.

Нормализованный алгоритм

Базовый восьмиточечный алгоритм в принципе можно использовать и для оценки фундаментальной матрицы. $\mathbf {F}$. Определяющее ограничение для $\mathbf {F}$ является

$(\mathbf {y} ')^{T}\,\mathbf {F} \,\mathbf {y} =0$

где $\mathbf {y} ,\mathbf {y} '$ являются однородными представлениями соответствующих координат изображения (не обязательно нормализованными). Это означает, что можно сформировать матрицу $\mathbf {Y}$ аналогично существенной матрице и решаем уравнение

$\mathbf {f} ^{T}\,\mathbf {Y} =\mathbf {0}$

для $\mathbf {f}$ который представляет собой переработанную версию $\mathbf {F}$. Следуя описанной выше процедуре, можно определить $\mathbf {F}$ из набора из восьми совпадающих точек. Однако на практике полученная фундаментальная матрица может оказаться бесполезной для определения эпиполярных ограничений.

Сложность

Проблема в том, что в результате $\mathbf {Y}$ часто плохо кондиционирован . В теории, $\mathbf {Y}$ должно иметь одно единственное значение, равное нулю, а остальные ненулевые. Однако на практике некоторые ненулевые сингулярные значения могут стать меньшими по сравнению с большими. Если для построения используется более восьми соответствующих точек $\mathbf {Y}$, где координаты верны только приблизительно, может не быть четко определенного сингулярного значения, которое можно было бы идентифицировать как приблизительно ноль. Следовательно, решение однородной линейной системы уравнений может быть недостаточно точным, чтобы быть полезным.

Причина

Хартли обратился к этой проблеме оценки в своей статье 1997 года. Его анализ проблемы показывает, что проблема вызвана плохим распределением координат однородного изображения в их пространстве. $\mathbb {R} ^{3}$. Типичное однородное представление координат двумерного изображения. $(y_{1},y_{2})\,$ является

$\mathbf {y} ={\begin{pmatrix}y_{1}\\y_{2}\\1\end{pmatrix}}$

где оба $y_{1},y_{2}\,$ лежат в диапазоне от 0 до 1000–2000 для современной цифровой камеры. Это означает, что первые две координаты в $\mathbf {y}$ изменяются в гораздо большем диапазоне, чем третья координата. Кроме того, если точки изображения, используемые для построения $\mathbf {Y}$ лежат в относительно небольшой области изображения, например на $(700,700)\pm (100,100)\,$, снова вектор $\mathbf {y}$ точки более или менее в одном и том же направлении для всех точек. Как следствие, $\mathbf {Y}$ будет иметь одно большое единственное значение, а остальные малы.

Решение

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

• Начало новой системы координат должно быть центрировано (иметь начало координат) в центроиде (центре тяжести) точек изображения. Это достигается путем перевода исходного источника в новый.
• После перевода координаты равномерно масштабируются так, что среднее значение расстояний от начала координат до точек равно ${\sqrt {2}}$.

Этот принцип обычно приводит к отдельному преобразованию координат для каждого из двух изображений. В результате появляются новые однородные координаты изображения. $\mathbf {\bar {y}} ,\mathbf {\bar {y}} '$ даны

$\mathbf {\bar {y}} =\mathbf {T} \,\mathbf {y}$

$\mathbf {\bar {y}} '=\mathbf {T} '\,\mathbf {y} '$

где $\mathbf {T} ,\mathbf {T} '$ — это преобразования (перенос и масштабирование) из старых нормализованных координат изображения в новые . Эта нормализация зависит только от точек изображения, которые используются в одном изображении, и, как правило, отличается от нормализованных координат изображения, создаваемых нормализованной камерой.

Эпиполярное ограничение, основанное на фундаментальной матрице, теперь можно переписать как

$0=(\mathbf {\bar {y}} ')^{T}\,((\mathbf {T} ')^{T})^{-1}\,\mathbf {F} \,\mathbf {T} ^{-1}\,\mathbf {\bar {y}} =(\mathbf {\bar {y}} ')^{T}\,\mathbf {\bar {F}} \,\mathbf {\bar {y}}$

где $\mathbf {\bar {F}} =((\mathbf {T} ')^{T})^{-1}\,\mathbf {F} \,\mathbf {T} ^{-1}$. Это означает, что можно использовать нормированные однородные координаты изображения. $\mathbf {\bar {y}} ,\mathbf {\bar {y}} '$ оценить преобразованную фундаментальную матрицу $\mathbf {\bar {F}}$ используя базовый алгоритм из восьми пунктов, описанный выше.

Цель нормализационных преобразований состоит в том, чтобы матрица $\mathbf {\bar {Y}}$, построенный из нормализованных координат изображения, в целом имеет лучшее число обусловленности, чем $\mathbf {Y}$ имеет. Это означает, что решение $\mathbf {\bar {f}}$ более четко определяется как решение однородного уравнения $\mathbf {\bar {Y}} \,\mathbf {\bar {f}}$ чем $\mathbf {f}$ относительно $\mathbf {Y}$. Один раз $\mathbf {\bar {f}}$ было определено и преобразовано в $\mathbf {\bar {F}}$ последний может быть денормализован, чтобы дать $\mathbf {F}$ в соответствии с

$\mathbf {F} =(\mathbf {T} ')^{T}\,\mathbf {\bar {F}} \,\mathbf {T}$

В общем, эта оценка фундаментальной матрицы является лучшей, чем была бы получена путем оценки по ненормализованным координатам.

Использование менее восьми точек

Каждая пара точек вносит свой вклад в одно ограничивающее уравнение для элемента в $\mathbf {E}$. С $\mathbf {E}$ имеет пять степеней свободы, поэтому для определения достаточно всего пяти пар точек. $\mathbf {E}$. Дэвид Нистер предложил эффективное решение для оценки существенной матрицы по набору пяти парных точек, известное как алгоритм пяти точек. Хартли и др. ал. позже предложил модифицированный и более стабильный пятиточечный алгоритм, основанный на алгоритме Нистера.

См. также

• Основная матрица
  • Основная матрица § Извлечение вращения и перевода
• Фундаментальная матрица
• Трифокальный тензор

Дальнейшее чтение

• Ричард И. Хартли (июнь 1997 г.). «В защиту восьмиточечного алгоритма». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 19 (6): 580–593. дои : 10.1109/34.601246 . S2CID   16919747 .

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

• Х. Кристофер Лонге-Хиггинс (сентябрь 1981 г.). «Компьютерный алгоритм восстановления сцены по двум проекциям». Природа . 293 (5828): 133–135. Бибкод : 1981Natur.293..133L . дои : 10.1038/293133a0 . S2CID   4327732 .