Software & Systems

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

Пусть даны две видеопоследовательности, не синхронизированные аппаратным способом и полученные в результате видеосъемки двух неоткалиброванных видеокамер. Существует проблема построения стереовидеопоследовательности на основе полученных видеопоследовательностей вследствие аппаратной рассинхронизации. Необходимо разработать алгоритм коррекции рассинхронизированных видеопоследовательностей в задачах стереовидения, применяемый для точного построения стереопар, для анализа данных, полученных аэрофотосъемкой и спутниковой фотографией.

Пространственно-временная коррекция стереовидеопоследовательностей включает следующие этапы:

–      предварительная обработка сцены видеопоследовательностей, включающая фильтрацию шумов, выделение переднего плана и области фона, морфологическую обработку;

–      временная обработка сцены видеопоследовательностей; состоит из двухэтапной процедуры оценки движения: изначально производится предварительная оценка движения методом BMA (block-matching algorithm), затем – уточненная оценка на основе инвариантных моментов Ху и Зернике; после оценки движения осуществляется интерполяция кадров каждой видеопоследовательности (метод подробно рассмотрен в [1]);

–      пространственная обработка сцены видеопоследовательностей: ректификация изображений, построение карты диспаритета.

Пространственная обработка сцены видеопоследовательностей для данной задачи предполагает решение задачи реконструкции трехмерной сцены, что необходимо для точного совмещения некалиброванных пар видеокадров. Общий вид решения такой задачи зависит от того, калиброваны ли камеры. В работе [2] предложен алгоритм реконструкции некалиброванных камер, использующий метод выделения особых точек Канаде–Лукаса–Томаси, триангуляцию Хартли и позволяющий восстанавливать сложные сцены. Эффективный алгоритм реконструкции, использующий калиброванные камеры и работающий в реальном времени, рассмотрен в [3].

Постановка задачи

Процесс обработки некалиброванной пары видеокадров состоит из трех этапов.

1. Выделение и сопоставление особенностей. На начальном этапе происходит поиск особых точек на каждом изображении, инвариантных к масштабированию и вращению. Это точки в местах резкого перепада градиента на изображении по значениям x и y, которые вычисляются при помощи матрицы Гессе, фильтров Хаара, пирамид и разностей гауссианов, детектора углов Харриса. Особые точки хорошо обнаруживаются на углах, пятнах и краях линий.

После нахождения особых точек вычисляют дескрипторы – векторы, описывающие локальную окрестность вокруг особой точки. Дескрипторы используются для сравнения особых точек на разных изображениях друг с другом. Существует несколько методов поиска особых точек и извлечения дескрипторов: SIFT, SURF, ORB, ASIFT, обеспечивающих инвариантность особых точек к освещению, шуму и вращению камеры [4].

Далее осуществляется выбор из всех выделенных особых точек соответствующих пар точек, полученных на основе инвариантных дескрипторов на каждом изображении. Соответствующие точки находятся при помощи различных модификаций метода поиска ближайших соседей (KD-деревья, иерархические деревья K-средних). В работе [5] предложен быстрый и автоматически настраиваемый метод выбора соответствующих точек, а в [6] – иерархический метод поиска соответствующих точек на стереоизображениях.

2. Выравнивание изображений. Два изображения представляют собой плоскости проекций камер с центрами в С1 и С2 (рис. 1), лежащих на базовой линии. Трехмерная точка X в пространстве проецируется на изображения в точки x1 и x2. Согласно проективной геометрии, проекции любой точки X, лежащей в плоскости, пересекающие оба изображения, лежат на эпиполярных линиях l1 и l2. Множество таких линий для каждого изображения проходит через эпиполярную точку, являющуюся точкой пересечения плоскости изображения и базовой линии (e1 и e2).

Каждая точка на изображении определяет эпиполярную линию на другом изображении, поэтому, зная однородные координаты соответствующих точек x1 и x2, можно связать отношения точек при помощи фундаментальной матрицы F. Фундаментальная матрица представляет собой линейный оператор, сопоставляющий каждой точке x1 соответствующую ей эпиполярную линию l2. Для каждой пары соответствующих точек верно

.                                                              (1)

Для точного определения фундаментальной матрицы выбирают наилучшие сопоставленные пары точек при помощи 5-, 7-, 8-точечных алгоритмов, RANSAC (Random Sample Consensus), алгоритма наименьшей медианы квадратов (LMedS). Чтобы матрица была хорошо обусловлена, используют нормированный 8-точечный алгоритм, применяя нелинейные алгоритмы, оптимизацию Макварда–Левенберга. На основании вычисленной фундаментальной матрицы определяют эпиполярные точки e1 и e2 на обоих изображениях.

Ректификация изображения представляет собой перенос двух плоскостей изображений в одну плоскость таким образом, чтобы все эпиполярные линии были параллельны оси абсцисс и соответствующие эпиполярные линии на обоих изображениях имели одинаковые ординаты. Находится проективное преобразование H2, переносящее эпиполярную точку e2 в бесконечно удаленную точку (1, 0, 0)T, аналогично – для проективного преобразования H1. Данное проективное преобразование включает в себя поворот и параллельный перенос относительно изображений и вычисляется минимизацией суммы  на множестве точечных соответствий. Первое изображение преобразуется в соответствии с проективным преобразованием H1, второе – в соответствии с H2. Изображения будут находиться в одной плоскости и иметь равные y-координаты, эпиполярные линии совпадут со строками изображений.

Данная ректификация используется, если центры двух камер сдвинуты друг от друга на небольшое расстояние, эпиполярные точки находятся вне изображения, удалены в бесконечность, эпиполярные линии параллельны. Если камера движется вперед или назад, то стереобаза будет перпендикулярна плоскости изображения; спроецировать изображение на перпендикулярную плоскость сложно, поскольку размер изображения исказится и станет бесконечного размера, что проблематично при сопоставлении. Эпиполярные точки будут находиться внутри изображений. В таком случае используется полярная ректификация: множество эпиполярных линий индексируется углом поворота, эпиполярные линии последовательно копируются в соответствующие горизонтали ректифицированных изображений. Если центры камер движутся одновременно и вперед, и в стороны, планарная и полярная ректификации могут преобразовать изображения, сделав неограниченными в пространстве либо слишком вытянутыми вдоль оси. В таком случае применяется цилиндрическая ректификация [7], которая обеспечивает границы преобразованных изображений.

3.  Вычисление карты диспаритета. Поскольку после выравнивания строки изображений будут соответствовать друг другу, для каждого пиксела левого изображения (x1, y1) выполняется поиск соответствующего пиксела (x2, y1) на правом изображении. При этом предполагается, что пиксел на правом изображении имеет координаты (x1­–d, y1), где d – диспаритет, величина смещения, равная расстоянию между соответственными пикселами двух изображений. Поиск соответственного пиксела выполняется несколькими методами. Корреляционные методы (Konolige's Block Matching Algorithm и др.) основаны на сравнении яркости пикселов в некоторой окрестности потенциально соответствующих точек, где корреляционная функция достигает максимума на тех участках изображений, значения яркостей окон которых отличаются только смещением и постоянным множителем. Данные методы работают лучше всего на сценах с текстурой, выполняются в реальном времени, а при отсутствии текстуры дают большую погрешность при построении карты диспаритета. Методы вырезки графа [8] дают более точный результат, но работают медленно и не выполняются в реальном времени. Метод полуглобального сопоставления [9] заключается в минимизации функции энергии с использованием принципа динамического программирования вдоль восьми направлений. Метод работает в реальном времени, сохраняет границы сложных объектов, устойчив к шуму.

Предлагаемый алгоритм совмещения некалиброванных видеокадров

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

1.     Определяются особые точки, вычисляются их дескрипторы для каждого изображения при помощи алгоритмов SURF и SIFT.

2.     Каждый дескриптор первого изображения сравнивается со всеми дескрипторами второго изображения. Для каждого дескриптора на левом изображении при помощи метода k-ближайших соседей находятся по два лучших соответственных дескриптора с правого изображения. Ана- логичная процедура выполняется для каждого дескриптора правого изображения. Результатом данного сравнения будут два множества дескрипторов с сопоставленными кандидатами для каждого дескриптора, содержащих как подходящие, так и ложные соответствия.

3.     После того как для каждого особого дескриптора будут получены два соответствующих дескриптора-кандидата, производится проверка отношения расстояний между кандидатами и дескриптором. Для этого сравнивается мера расстояния относительно выбранного дескриптора и его дескрипторов-кандидатов dist(k1) и dist(k2) согласно выражению

.                                                          (2)

Если отношение расстояния первого кандидата dist(k1) и второго кандидата dist(k2) относительно выбранного дескриптора не превышает заданный порог r, обозначающий максимальное расстояние между кандидатами, то оба кандидата принимаются. Если эта мера расстояния очень маленькая для первого кандидата и слишком большая для второго, принимается первый кандидат. Если два кандидата находятся на относительно близком расстоянии, существует вероятность того, что будет допущена ошибка при выборе одного из этих кандидатов, и в этом случае отбрасываются оба кандидата. Данный этап предназначен для уменьшения количества ложных соответствий в исходных множествах дескрипторов.

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

5.     На основе соответственных пар лучших точек вычисляется фундаментальная матрица. Для более точной оценки фундаментальной матрицы пары соответственных точек должны состоять только из хороших точек, исключая ложные. Поскольку невозможно гарантировать, что в полученных парах соответствующих точек не будет ложных точек, основным методом оценки фундаментальной матрицы предлагается метод RANSAC. Случайным образом выбираются несколько точек из множества соответствующих пар точек, производится их оценка. Число выбранных точек должно быть минимальным. Фундаментальная матрица оценивается при помощи случайных восьми пар точек из данных пар, а все остальные соответствующие пары точек проверяются на условие эпиполярного ограничения (точки должны лежать на эпиполярных линиях). Эти сопоставленные пары точек формируют основной набор точек для вычисления точной фундаментальной матрицы. Все сопоставленные пары, в которых точка находится на расстоянии от ее эпиполярной линии, превышающем пороговое значение, считаются ложными и отбрасываются. Чем больше основной набор точек, тем выше вероятность того, что матрица будет вычислена правильно. Количество выборок повторяется несколько раз, матрица с наибольшим основным набором точек считается наиболее вероятной. В результате формируется набор наилучших сопоставленных пар точек с исключенными ложными точками для формирования точной фундаментальной матрицы.

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

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

Данная процедура повторяется для исходного кадра левой последовательности и каждого интерполированного кадра правой видеопоследовательности, на основании полученной карты глубины выбирается наиболее точный интерполированный откалиброванный кадр для дальнейшего построения стереокадра.

Экспериментальные исследования

Для оценки точности фундаментальной матрицы и карт диспаритета использовалась база изображений [10], которая представляет множество пар ректифицированных изображений и точные карты диспаритета. Для оценки предлагаемого алгоритма были выбраны четыре пары изображений – «Tsukuba», «Venus», «Teddy», «Cones» и их точные карты диспаритета. Тестирование производилось на персональном компьютере производительностью 15 Гфлопс, для этого был разработан программный продукт на языке C++ при помощи библиотеки OpenCV.

Поскольку тестовые изображения (рис. 2, а) являются ректифицированными, они преобразуются в некалиброванные различными аффинными преобразованиями при помощи сжатия, поворота, сдвига (рис. 2, б). После нахождения лучших сопоставленных точек между парой некалиброванных изображений (рис. 2, в) и найденной точкой фундаментальной матрицы оба изображения при помощи перспективного преобразования переносятся в одну плоскость. Соответствующие эпиполярные линии на обоих изображениях имеют одинаковые ординаты, изображения становятся ректифицированными (рис. 2, г). Эталонная карта диспаритета преобразуется в плоскость ректифицированных изображений при помощи вычисленной матрицы гомографии, затем удаляются лишние пиксели, полученные при трансформации (рис. 2, д). Преобразованная эталонная карта диспаритета сравнивается с различными картами диспаритета (рис. 2, е) в зависимости от выбранного алгоритма поиска особенностей (SIFT, SURF, ORB) и оценки фундаментальной матрицы (RANSAC, LMedS, 7-точечный алгоритм, 8-точеч­ный алгоритм, модифицированный алгоритм). Предлагаются две метрики сравнения алгоритмов: вычисление среднеквадратичной ошибки R и процента плохих пикселов B:

,                  (3)

,            (4)

где N – общее количество пикселей изображения; dC(x, y) – диспаритет пиксела, вычисленный одним из рассматриваемых алгоритмов; dТ(x, y) – эталонный диспаритет пиксела тестового изображения; ρd – пороговое значение, обозначающее допустимую ошибку диспаритета, равное 10.

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

Сравнение точности карт диспаритета алгоритмов поиска особенностей и оценки фундаментальной матрицы, %

В работе предлагается пространственная обработка несинхронизованных видеопоследовательностей на основе алгоритма совмещения некалиброванных видеокадров, повышающего количество точных соответствий и их качество, устойчивость фундаментальной матрицы, точность карт диспаритета. Анализ полученных данных позволяет говорить о том, что предлагаемый алгоритм совмещения некалиброванных пар видеокадров с использованием SIFT в качестве поиска особенностей превосходит другие алгоритмы на 3–4 %. Рассматриваемая пространственная обработка сцены видеопоследовательностей успешно сочетается с временной коррекцией рассинхронизированных видеопоследовательностей в задачах стереовидения, применяемой для точного построения стереопар, полученных аэрофотосъемкой и спутниковой фотографией.

Литература

1.     Пьянков Д.И. Интерполяция кадров в задачах пространственно-временной коррекции стереовидеопоследовательностей // Цифровая обработка сигналов и ее применение: матер. 13-й междунар. конф. М., 2011. Т. 2. С. 173–176.

2.     Pollefeys M., Gool L.V., Vergauwen M., Verbiest F., Cornelis K., Tops J., Koch R., Intern. Journ. of Computer Vision, 2004, Vol. 59, pp. 207–232.

3.     Nister D., Davison A., IEEE Conf. on Computer Vision and Pattern Recognition, San Diego, 2005.

4.     Lowe D.G., Distinctive Image Features from Scale-Invariant Keypoints. Intern. Journ. of Computer Vision, 2004. Vol. 60, no. 2, pp. 91–110.

5.     Muja M., Lowe D.G., Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration, Intern. Conf. on Computer Vision Theory and Applications (VISAPP'09), 2009.

6.     Фаворская М.Н., Тупицын И.В. Иерархический метод поиска соответствующих точек на стереоизображениях // Вестн. СибГАУ. 2012. Вып. 1 (47). С. 62–67.

7.     Nouidui-Tchagou A., Epipolar image rectification using cylinder Geometry, Institute of Computer Science in the Technical Faculty of Christian-Albrechts-University of Kiel, student project, 2006.

8.     Kolmogorov V., PhD Thesis, Cornell University, 2003, September.

9.     Hirschmüller H., IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, Vol. 30 (2), pp. 328–341.

10.  Scharstein D., Szeliski R., Middlebury Stereo Datasets. URL: http://vision.middlebury.edu/stereo/data/ (дата обращения: 21.11.2012).