Журнал «Компьютерра» № 6 от 14 февраля 2006 года

Так как же восстанавливают положение камер по кадрам? Для этого нам опять потребуются пары соответствующих точек на каждом из изображений (обычно не меньше семи пар). При смене камеры мы просто меняем центр и направление проецирования; таким образом, пара камер характеризуется вектором сдвига (он соединяет оптические центры камер) и поворотом в пространстве одной относительно другой. Если мы посмотрим на две фотографии одного предмета, сделанные с разных точек, то сможем достаточно точно указать искомые параметры пары камер. При этом мы будем руководствоваться изменением взаимного положения точек на фотографиях. Рассуждать мы будем примерно так: «вот этот отрезок стал длиннее, следовательно, теперь он стал более перпендикулярным по отношению к камере, а вот этот короче, а этот повернулся…». Руководствуясь подобными же соображениями, можно построить математическую модель и с ее помощью достаточно точно восстановить параметры пары камер.

После того как взаимное положение камер известно, можно для любой точки одного изображения найти прямую на другом, которая будет проходить через точку, соответствующую в пространстве первой. Эта прямая называется эпиполярной и соответствует проекции (e’p’, см. рис. справа внизу) на вторую камеру прямой (OP), соединяющей точку в пространстве (P) с оптическим центром первой камеры (O). Понятно, что конфигурация эпиполярных линий определяется только параметрами пары камер и не зависит от конфигурации 3D-сцены.

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

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

Вспомним про третий инструмент человеческого восприятия трехмерного пространства – выявление знакомых предметов со знакомыми размерами. Этот метод применим только для довольно узкого класса задач. Например, индустриальный робот только и делает, что перекладывает пять различных типов заготовок с места на место и вполне может их «узнавать», а вот для ориентирования в произвольном помещении такой метод вряд ли подойдет. Знаменитый робот-собака Aibo может находить и узнавать свои игрушки, но для этого они специальным образом раскрашиваются.

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

Теперь рассмотрим возможности, которые недоступны человеку, но вполне могут быть реализованы в роботах. Существенно увеличить точность восстановления 3D можно, используя третий глаз. Именно так и поступила компания Sony, спроектировав робота Qrio. Правда, он использует третий глаз не только для ориентирования в пространстве, но и для увеличения многозадачности.

Все описанные методы являются пассивными – робот не генерирует никаких сигналов. Существуют также и активные системы; некоторые из них сродни эхолотам дельфинов и акустическим радарам летучих мышей. Робот посылает направленную акустическую или электромагнитную волну и по отраженной волне, которую сам и принимает, получает информацию о расстоянии до преграды. Такой аппаратурой обычно оснащаются роботы, действующие на открытой местности, где оптические методы не всегда эффективны (выбрать соответствующие друг другу точки очень трудно из-за сложной формы объектов и обилия сильно текстурированных областей).