Восьмиточный алгоритм - Eight-point algorithm

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

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

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

Пример эпиполярной геометрии. Две камеры с соответствующими центрами точек проецирования О_L и О_р, обратите внимание на точку п. Проекция п на каждую из плоскостей изображения обозначается п_L и п_р. Точки E_L и E_р это эпиполи.

Можно выразить эпиполярная геометрия двух камер и точки в пространстве с алгебраическим уравнением. Обратите внимание, где бы ни находилась точка ${displaystyle P}$ находится в пространстве, векторы ${displaystyle {overline {O_ {L} P}}}$ , ${displaystyle {overline {O_ {R} P}}}$ и ${displaystyle {overline {O_ {R} O_ {L}}}}$ принадлежат к одной плоскости. Вызов ${displaystyle X_ {L}}$ координаты точки ${displaystyle P}$ в системе отсчета левого глаза и вызовите ${displaystyle X_ {R}}$ координаты ${displaystyle P}$ в системе отсчета правого глаза и вызовите ${displaystyle R, T}$ вращение и перевод между двумя системами отсчета s.t. ${Displaystyle X_ {R} = R (X_ {L} -T)}$ это связь между координатами ${displaystyle P}$ в двух системах отсчета. Следующее уравнение всегда выполняется, потому что вектор, созданный из ${displaystyle Twedge X_ {L}}$ ортогонален обоим ${displaystyle T}$ и ${displaystyle X_ {L}}$ :

{displaystyle X_ {L} ^ {T} Twedge X_ {L} -T ^ {T} Twedge X_ {L} = (X_ {L} -T) ^ {T} Twedge X_ {L} = 0}

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

{displaystyle (X_ {L} -T) ^ {T} R ^ {T} RTwedge X_ {L} = 0}

.

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

{Displaystyle X_ {R} ^ {T} RTwedge X_ {L} = X_ {R} ^ {T} RSX_ {L} = X_ {R} ^ {T} EX_ {L} = 0}

Заметьте, что ${displaystyle Twedge}$ можно рассматривать как матрицу; Лонге-Хиггинс использовал символ ${displaystyle S}$ чтобы обозначить это. Продукт ${displaystyle RTwedge = RS}$ часто называют основная матрица и обозначен ${displaystyle E}$ .

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

{displaystyle y '^ {T} mathbf {E} y = 0}

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

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

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

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

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

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

С

{displaystyle mathbf {y} = {egin {pmatrix} y_ {1} y_ {2} 1end {pmatrix}}}

и

{displaystyle mathbf {y} '= {egin {pmatrix} y' _ {1} y '_ {2} 1end {pmatrix}}}

и

{displaystyle mathbf {E} = {egin {pmatrix} e_ {11} & e_ {12} & e_ {13} e_ {21} & e_ {22} & e_ {23} e_ {31} & e_ {32} & e_ {33} конец {pmatrix}}}

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

{displaystyle 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,}

или же

{displaystyle mathbf {e} cdot {ilde {mathbf {y}}} = 0}

куда

{displaystyle {ilde {mathbf {y}}} = {egin {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} 1end {pmatrix}}}

и

{displaystyle mathbf {e} = {egin {pmatrix} e_ {11} e_ {12} e_ {13} e_ {21} e_ {22} e_ {23} e_ {31} e_ {32} } e_ {33} конец {pmatrix}}}

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

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

{displaystyle mathbf {e} cdot {ilde {mathbf {y}}} _ {k} = 0}

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

{displaystyle mathbf {e} ^ {T}, mathbf {Y} = mathbf {0}}

Это означает, что ${displaystyle mathbf {e}}$ это решение однородное линейное уравнение.

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

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

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

{displaystyle | mathbf {e} ^ {T}, mathbf {Y} |}

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

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

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

{displaystyle | mathbf {E} '-mathbf {E} _ {m {est}} |}

куда ${displaystyle mathbf {E} _ {m {est}}}$ матрица, полученная на шаге 2, а Норма матрицы Фробениуса используется. Решение проблемы дается сначала вычислением разложение по сингулярным числам из ${displaystyle mathbf {E} _ {m {est}}}$ :

{displaystyle mathbf {E} _ {m {est}} = mathbf {U}, mathbf {S}, mathbf {V} ^ {T}}

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

{displaystyle mathbf {S} '= {egin {pmatrix} s_ {1} & 0 & 0 0 & s_ {2} & 0 0 & 0 & 0end {pmatrix}},}

куда ${displaystyle s_ {1}, s_ {2}}$ - наибольшее и второе наибольшее сингулярные значения в ${displaystyle mathbf {S}}$ соответственно. Ну наконец то, ${displaystyle mathbf {E} '}$ дан кем-то

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

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

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

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

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

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

{displaystyle mathbf {f} ^ {T}, mathbf {Y} = mathbf {0}}

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

Сложность

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

Причина

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

{displaystyle mathbf {y} = {egin {pmatrix} y_ {1} y_ {2} 1end {pmatrix}}}

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

Решение

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

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

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

{displaystyle mathbf {ar {y}} = mathbf {T}, mathbf {y}}

{displaystyle mathbf {ar {y}} '= mathbf {T}', mathbf {y} '}

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

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

{displaystyle 0 = (mathbf {ar {y}} ') ^ {T}, ((mathbf {T}') ^ {T}) ^ {- 1}, mathbf {F}, mathbf {T} ^ {- 1}, mathbf {ar {y}} = (mathbf {ar {y}} ') ^ {T}, mathbf {ar {F}}, mathbf {ar {y}}}

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

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

{displaystyle mathbf {F} = (mathbf {T} ') ^ {T}, mathbf {ar {F}}, mathbf {T}}

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

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

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

Каве Фатиан и др. предложены алгоритмы для пяти, шести и семи точек, которые обходят вычисление существенной матрицы, вычисляя кватернион вращения напрямую.^[1]^[2]

Смотрите также

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

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

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

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

[1] Фатиан, Кавех (2018). «QuEst: подход на основе кватернионов для оценки движения камеры по минимальным характерным точкам». Письма IEEE по робототехнике и автоматизации. arXiv:1704.02672. Дои:10.1109 / LRA.2018.2792142.

[2] Фатиан, Кавех (2018). «Оценка относительной позы камеры для визуального следящего с использованием кватернионов». Робототехника и автономные системы. Дои:10.1016 / j.robot.2018.05.014.

[1]

[2]