- PVSM.RU - https://www.pvsm.ru -
Если посмотреть на последовательность кадров, в которых движется камера, то
Перед прочтением этой статьи не помешает внимательно прочитать статью «Основы стереозрения» [2].
Итак, перед нами стоит задача превращения последовательности двумерных изображений в трехмерную структуру. Задача это не простая, и нужно ее упрощать.
Во-первых, предположим, что кадра у нас только два. Обозначим их как A и B.
Во-вторых, будем работать с конечным множеством точек, соответствующих друг другу на кадрах A и B. Точки на изображении обозначим как . Тогда точки на кадрах A и B будут и . Каждая пара точек соответствует точке в трехмерном пространстве .
Теперь необходимо определиться как искать и . Для этого на первом кадре выберем точки, с наибольшей контрастностью — «особенные» точки (features). Для этого можно использовать surf, fast или что-нибудь другое [3]. Эти точки и будут . Затем необходимо найти соответствия этим точкам на втором кадре при помощи того же алгоритма surf или оптического [4] потока [5]. А это уже точки .
А теперь мы подошли к центральному вопросу этой статьи: как из точек и (точек-соответствий, point correspondences) получить координаты точек и положение камеры в пространстве? Сначала необходимо разобраться с тем, как же точка она попадает на изображение. Нужно построить математическую модель камеры.
Так как вы, вероятно, уже прочитали статью «Основы стереозрения», эта формула должна быть знакома:
.
Или если описать более полно:
.
Здесь X — это трехмерная точка в пространстве.
x — это координата точки на изображении в однородных координатах [6], и , т. е. перевод в обычные координаты изображения будет таким: .
Процесс перевода точки в пространстве в координаты изображения можно разбить на два этапа, реализуемыми двумя матрицами в формуле:
Важным свойством этой модели является то, что точки лежащие на одной прямой в пространстве будут также лежать на одной прямой на изображении.
На самом деле, описываемая модель может быть очень неточной. В реальных камерах вступают в игру линзовые искажения, из-за которых прямые линии становятся кривыми. Это искажение называются дисторсией [7]. Существуют разные модели, исправляющие эти искажения. Здесь [8] есть некоторые их реализации. Параметры этой модели также входит в понятие внутренних параметров камеры.
С учетом дисторсии наша формула усложняется:
, где D(X) — функция, принимающая однородные координаты точек изображения и возвращающая обычные координаты на изображении. Также позже нам понадобится обратная функция — InvD(ix).
Внутренние параметры камеры должны быть известны заранее. Выяснение этих параметров — это отдельная тема, будем считать, что они уже есть.
Искажения дисторсии не зависит от глубины видимых точек, а только координат на изображении. А значит «исправить» изображение (получив прямые линии там, где они и должны быть) можно не зная внешних параметров камеры и координат точек в пространстве. Дальше тогда можно использовать модель камеры без функции D.
Изображение с дисторсией слева, и справа — «исправленное» от линзовых искажений изображение. Видно, что линии стали прямыми.
Мы договорились, что внутренние параметры нам известны, известны и координаты точек на изображении, а значит, остается найти [R|t] и Xi (положения камеры и точек в пространстве).
Наша формула выходит уже немного сложной, надо ее упрощать. Для начала сделаем так:
Выражение остается справедливым. Продолжим:
Обозначим (а если без дисторсии, то ). Так как все параметры известны, nxi можно посчитать заранее. Вспомнив как выглядит матрица K, можно понять, что nxz = 1. Это поможет при дальнейших расчетах. В результате формула становится проще:
nxi — это нормализованные точки изображения.
Итак, предположим, у нас есть два изображения, полученные от одной камеры. Нам неизвестны положения камер и координаты точек в пространстве. Договоримся ввести расчеты относительно первого кадра. Так получается, что RA = I (I — единичная матрица), tA = (0, 0, 0). Положение камеры в кадре B обозначим просто как R и t (т. е. RB = R, tB = t). [R|t] — это матрица координат второго кадра, и оно же — матрица смещения положения камеры от кадра A к кадру B. В итоге имеем получаем такую систему (без учета дисторсии!):
Используя фундаментальную матрицу F (fubdamental matrix), получим такое уравнение:
Также заметим, что F имеет размер 3х3 и должна иметь ранг равный 2.
Из фундаментальной матрицы F уже можно получить необходимые нам R и t. Однако дисторсия все портит, с ее учетом зависимость точек между кадрами будет нелинейная, и это уже не будет работать.
Но перейдем к нормализованным точкам и используем сущностную матрицу E (essential matrix). Все будет почти тем же, но проще:
— система уравнений для сущностной матрицы;
— уравнение для нее же.
А тут мы можем спокойно брать в расчет дисторсию.
Фундаментальная и сущностная матрицы связаны таким образом:
Теперь перед нами встала задача нахождения либо фундаментальной матрицы F, либо сущностной матрицы E, из которой позже сможем получить на R и t.
Вернемся к уравнению:
Эту же формулу можно переписать в таком виде (вспоминаем, что и ):
, здесь опущен параметр i ради удобства, но имеем ввиду что это справедливо для каждой точки.
Введем вектор e и матрицу M:
Тогда всю систему уравнений можно представить в виде:
Получаем однородную систему уравнений, решив которую, получим E из е. Очевидным решением здесь является нулевой вектор, но нас явно интересует не он. Для решения необходимо минимум 8 точек.
Сингулярное разложение [9] — это декомпозиция матрицы, приводящее ее к такому виду:
, где U, V — ортогональные матрицы, W — диагональная матрица. При этом диагональные элементы матрицы W принято располагать в порядке убывания. Также ранг матрицы W — это и ранг матрицы M. А так как W — диагональная матрица, то ее ранг — это количество ненулевых диагональных элементов.
Итак, было дано уравнение вида:
, где M — известная нам матрица, e — вектор, который на необходимо найти.
Строки VT, которым соответствует нулевой диагональный элемент W на этой же строке, являются нуль-пространствами матрицы M, т. е. в данном случае являются линейно-независимыми решениями нашей системы. А так как элементы W располагаются в порядке убывания, то смотреть нужно последний элемент матрицы W. И решением будет последняя строка .
При расчете сущностной матрицы, используя 8 точек, последний элемент матрицы W должен быть равен нулю — W99=0, но на практике, в следствии ошибок, там будет какое-то ненулевое значение, и по величине этого значения можно оценить величину этой ошибки. При этом мы получим лучшее решение.
Тем не менее, найденное нами решение — не единственное, более того, решений будет бесконечно много. Если умножить найденное решение на какой-либо коэффициент, оно все-равно останется решением. Таким образом в уравнении спрятался коэффициент s (который может быть любым):
.
Правда, все эти решения будут линейно зависимыми, а интересовать нас будет только одно из них.
Отсюда и матрица E может также масштабироваться. Вот только расчеты ведутся в однородном пространстве и, как следствие, от масштабирования (т. е. от коэффициента s) не зависят.
Наверное, стоит масштабировать получившуюся матрицу E так, чтобы E33 = 1.
Можно обойтись и 7-ю точками.
Если мы возьмем только 7 точек, то M будет матрицей размером 7x9.
Вернемся к выражению:
W — будет также матрицей размером 9x9, как и раньше, но теперь не только W99 будет равно нулю (ну опять же без учета ошибок вычислений), но и W88. Это значит, что имеем два линейно-независимых решения уравнения . Из них получим две матрицы E1 и E2. Решением будет выражение .
Сущностная матрица, как и фундаментальная, должна иметь ранг равный двум, а так как она имеем размер 3x3, то значит определитель матрицы равен 0 — . Следовательно . Если расписать это уравнение, то получим кубическое уравнение, имеющее 1 или 3 решения . А значит получим одну или три матрицы E.
Расписывать решение этого уравнения я не буду (оно объемное, ну и считайте это домашним заданием). В крайнем случае можете просто посмотреть сразу реализацию в opencv [10].
Так как все в этом мире несовершенно, то мы будем постоянно получать ошибки, с которыми нам необходимо бороться. Так сущностная матрица должна иметь ранг равный 2 и следовательно . На практике, однако, это будет нет так.
Чтобы увидеть в чем это выражается, возьмем фундаментальную матрицу. Сущностная матрица / фундаментальная матрица — разница лишь в том, с какими точками мы работаем (нормализованными или точками на изображении).
Луч, выпущенный из точки кадра A, ляжет в кадр B как прямая линия (или не совсем из-за дисторсии, но забудем про нее). Допустим матрица F — это фундаментальная матрица кадров A и B ().
Тогда если выпустить луч из точки , то в получим прямую l на кадре B — . Эта прямая называется эпиполярной линией, т. е. , где ix, iy — координаты точки на изображении. И то же условие для точки на изображении с однородными координатами — . Точка будет лежать на этой прямой, поэтому . Отсюда и выходит общая формула — .
На картинке изображен пример эпиполярных линий, полученных из правильной фундаментальной матрицы (ранг которой равен 2, картинка справа) и неправильной (слева).
Чтобы получить правильную фундаментальную матрицу, воспользуемся свойством сингулярного разложения — приближать матрицу к заданному рангу:
. В идеале W33 (последний элемент диагонали) должен быть равен нулю. Введем новую матрицу W’, которая равна W, только у которой элемент W'33 = 0.
Тогда исправленный вариант: .
Ровно тот же принцип работает и для сущностной матрицы.
Чтобы уменьшить ошибку, получаемую при расчетах, точки трансформируют к определенному ввиду. Выбираются такие матрицы TA и TB, которые (каждый независимо и на своем кадре) смещают среднюю координату точек в точку (0, 0) и масштабируют так, чтобы средняя дистанция дистанция до центра была равна :
А матрицы TA, B имеют вид: , где c — средняя координата точек кадров, s — коэффициент масштаба.
После этого вычисляем сущностную матрицу как обычно. После необходимо ее уточнить, как было описано выше. Обозначим полученную матрицу как Et.
Итоговая сущностная матрица — .
В итоге:
Опять же, если необходимо найти фундаментальную матрицу, все принципы сохраняются.
Введем матрицу H:
Используем сингулярное разложение на сущностной матрице:
Тогда получаем такие решения:
, где , — координаты положения камеры.
Нам же необходимо положение камеры в локальных координатах самой камеры: .
Выходит четыре решения: .
В случае 8-ми точечного алгоритма, выбираем из 4-ёх решений. В случае 7-ми точечного алгоритма, выйдет три сущностные матрицы, из которых получится 12 решений. Выбрать нужно только одно, то, которое будет давать меньше ошибок.
Снова вернемся к вычислению сущностной матрицы. У нас было уравнение:
Далее мы его решали при помощи сингулярного разложения:
Решения данного уравнения зависит от ранга матрицы W, ну или от количества нулей в диагонали этой матрицы (мы же помним, что это отражает ранг матрицы). Вот только с учетом погрешности, считаем нулем в данном случае число, достаточно близкое к нулю.
Имеем такие варианты:
Допустим сейчас у нас есть больше, чем два кадра — A, B, C, …
— положение камер кадров A, B, C,…
— нормализованные точки
Необходимо найти точку
Представим эту систему так:
В матричном виде:
С помощью сингулярного разложения находим вектор , который (способом, описанном выше). Тогда , где s — какой-то неизвестный коэффициент. Выходит .
Оценочные функции (cost functions) необходимы, чтобы получив какие-то результаты, оценить насколько достоверными они являются, или сравнить их с другими.
Возьмем нашу модель:
— предполагаемый результат.
— реальное значение точки.
Отсюда квадрат ошибки для i-ой точки будет: .
На практике одни точки будут давать более достоверные результаты, чем другие. А некоторые вообще явно будут давать неправильные. В результате возникает необходимость выбрать из общего массива точек только те точки, которым можно доверять, а остальные просто выбросить из расчетов.
Самый простой способ выбрать “достоверные” точки — выбрать какой-то лимит (допустим, 5 пикселей), и брать только те точки, которые дают ошибку меньше этого лимита (). Тут же следует отметить, что необходимо учитывать, что точка должна лежать перед камерой в обоих кадрах, иначе ее явно необходимо отбросить.
Таким образом, можно ввести оценочную функцию — количество достоверных точек. И при сравнении, выбирать тот результат, который дает большее количество “достоверных” точек.
А можно воспользоваться другим, более “тонкой” функцией:
, где limit — это выбранный нами лимит (в 5 пикселей).
Лучшим будет тот вариант, который будет давать меньшее значение. Понятно, что и здесь следует убирать “недостоверные” точки для будущих расчетов.
Изначально мы исходили из предположения, что кадра у нас было всего два.
Чтобы работать с последовательностью кадров, нужно просто разбить последовательность на последовательные пары кадров. Обрабатывая пары кадров, мы получаем смещение камеры от одного кадра к другому. Из этого можно получить координаты положения камеры в остальных кадрах.
Получив главное — положения камер, можно действовать по-разному:
В общем, действовать можно по-разному, применяя разные методы, в том числе и те алгоритмы, которые были описаны — не единственные.
Fundamental matrix [12], Essential matrix [13], Eight-point algorithm [14] — больше информации в википедии
Hartley, Zisserman — Multiple View Geometry in Computer Vision — спонсор этой статьи
Автор: MarkWatney
Источник [15]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/matematika/123592
Ссылки в тексте:
[1] мозг: http://www.braintools.ru
[2] «Основы стереозрения»: https://habrahabr.ru/post/130300/
[3] fast или что-нибудь другое: https://habrahabr.ru/post/244541/
[4] оптического: https://habrahabr.ru/post/201406/
[5] потока: https://habrahabr.ru/post/169055/
[6] однородных координатах: https://ru.wikipedia.org/wiki/%D0%9E%D0%B4%D0%BD%D0%BE%D1%80%D0%BE%D0%B4%D0%BD%D1%8B%D0%B5_%D0%BA%D0%BE%D0%BE%D1%80%D0%B4%D0%B8%D0%BD%D0%B0%D1%82%D1%8B
[7] дисторсией: https://ru.wikipedia.org/wiki/%D0%94%D0%B8%D1%81%D1%82%D0%BE%D1%80%D1%81%D0%B8%D1%8F
[8] Здесь: https://github.com/uzh-rpg/rpg_vikit/tree/master/vikit_common/src
[9] Сингулярное разложение: http://www.machinelearning.ru/wiki/index.php?title=%D0%A1%D0%B8%D0%BD%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D0%BE%D0%B5_%D1%80%D0%B0%D0%B7%D0%BB%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5
[10] opencv: https://github.com/Itseez/opencv/blob/master/modules/calib3d/src/fundam.cpp
[11] SLAM: https://ru.wikipedia.org/wiki/SLAM_(%D0%BC%D0%B5%D1%82%D0%BE%D0%B4)
[12] Fundamental matrix: https://en.wikipedia.org/wiki/Fundamental_matrix_(computer_vision)
[13] Essential matrix: https://en.wikipedia.org/wiki/Essential_matrix
[14] Eight-point algorithm: https://en.wikipedia.org/wiki/Eight-point_algorithm
[15] Источник: https://habrahabr.ru/post/301522/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best
Нажмите здесь для печати.