Компьютерная Графика и Мультимедиа Сетевой журнал

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

1. Введение

1.1 Задача восстановления

Существует три основных подхода к построению моделей:

1. Вручную с помощью распространенных программ моделирования (например, 3D Max)
2. Автоматически по шаблонам используя известные физические свойства реальных объектов
3. Восстановление модели по изображениям объекта и другой известной о нем информации

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

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

1.2 Активные и пассивные методы

Все методы восстановления сцены делятся на активные и пассивные. Активные методы используют устройства, которые находятся в прямом взаимодействии с объектами сцены, оказывают на сцену воздействие и сами являются ее участниками. К таким устройствам относятся лазерные сканеры, позволяющее с высокой точностью определять расстояние от лазера до поверхности объекта, что позволяет восстанавливать очень точную геометрическую модель объекта. Также к активным методам причисляются методы, использующие изображения объекта в условиях структурированного освещения (в свете цветных прожекторов, прожекторов с масками специальной формы). Главными недостатками всех активных подходов является высокая стоимость используемого оборудования и невозможность восстановления динамических сцен.

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

Существует целый набор подходов, на основе которых разрабатываются пассивные методы реконструкции. В данном обзоре будут рассмотрены два из них. Это реконструкция моделей по набору силуэтов объекта и на основе правила согласования цветов.

1.3 Дискретные представления

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

В противоположность этому, для задач восстановления моделей по фотографиям удобнее всего использовать дискретные(sampled) представления, т.е. такие, в которых информация об объекте известна только в определенных точках. Поэтому такие представления иногда называются точечными, но часто точечными называют один из классов дискретных представлений. Всего выделяют три класса дискретных представлений: объемные(volumetric), точечные(point) и основанные на изображениях (image-based).

Отдельный элемент объемного представления называется воксель (voxel) и хранит информацию о пространстве вокруг себя. Если это пространство пусто, то воксель считается пустым и либо помечается как прозрачный, либо удаляется из модели. Воксель, соседствующий с пустым и непустым называется граничным. Можно говорить, что граничные воксели хранят информацию о поверхности модели. Используются различные схемы дискретизации - регулярные, криволинейные, изотропные, неструктурированные. Регулярное представление наиболее удобно для обработки и хранения, поэтому именно оно используется чаще всего. Каждый воксель тогда представляется кубиком, а все пространство разбивается на множество таких одинаковых кубиков.

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

Представления на основе изображений начали широко исследоваться с 1995 года, после работы МакМиллана и Бишопа. Изображение, в котором каждому пикселю ставится в соответствие глубина (т.е. расстояние от камеры до участка поверхности, изображением которой является пиксель), называется изображением с глубиной. Т.е. каждый пиксель с глубиной хранит информацию о кусочке поверхности на расстоянии, равной глубине от камеры. Минимальный параллелепипед, содержащий соответствующий пикселю кусочек поверхности, назовем областью влияния пикселя. А все изображение с глубиной соответствует некоторой частичной поверхности в пространстве. Зная положение и ориентацию новой камеры, мы можем спроектировать все кусочные поверхности (для каждого пикселя), на ее плоскость изображения, и получить изображение частичной поверхности с другой точки зрения. Плотность расположения точек, задаваемых пикселями изображения, в пространстве является можно назвать частотой дискретизации поверхности объекта с данной камеры. Мы можем ее варьировать путем изменения разрешения изображения или приближения удаления камеры относительно объекта. Соответственно, чем больше разрешение и чем ближе камера к поверхности объекта, тем точнее частичная поверхность описывает поверхность объекта.

В 1998 году было предложено многослойное изображение с глубиной (Layered Depth Image). В каждой его точке хранится упорядоченный по глубине список пар (пиксель,глубина). Каждый пара соответствует кусочку поверхности, которая стала бы видимой, если все предшествующие поверхности были бы удалены.

В общем случае, <представлением на основе изображений>, называется двумерное дискретное представление. С концептуальной точки зрения, каждый элемент представления считается независимым (не связанным с другими элементами) каким бы то ни было способом. Элементы просто расположены на постоянном расстоянии друг от друга. Взаимосвязь элементов следует только из дополнительных знаний об объекте, представлением которого является данное. Например, как было сказано выше, если мы описываем поверхность объекта.

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

Рис 1. Воксельный куб и многослойное изображение с глубиной

1.4 Требования к исходным изображениям

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

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

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

2. Силуэтные методы

2.1 Видимая оболочка (visual hull)

Сопоставим каждому исходному изображению битовую карту. Если пиксель изображения соответствует объекту, то бит ставится в 1, в противном случае в 0. Тогда силуэтом объекта на данном изображении называется множество всех равных 1 битов. Силуэтные методы восстанавливают геометрическую модель объекта только по его силуэтам. Эти методы также часто называются методами пересечения объемов (volume intersection). В 1991 году Лаурентини в свое работе доказал, что данные методы позволяют получить только <видимую оболочку> (visual hull) объекта. Видимой оболочкой называют наибольший объект, чей силуэт с любой точки обзора совпадает с силуэтом исходного объекта из этой же точки. Силуэтные методы в качестве исходных данных используют конечный набор изображений, поэтому они реконструируют <предполагаемую видимую оболочку>. Ее можно представить как пересечение телесных конусов, с вершиной в точке расположения камеры, и сечениями - силуэтами. Такие конусы называются силуэтными конусами.

Рис. 2 Предполагаемая видимая оболочка

Предполагаемая видимая оболочка обладает следующими свойствами:

1. Каждый объект целиком содержится внутри любой своей предполагаемой видимой оболочкой 

2. Размер (объем) предполагаемой видимой оболочки уменьшается с увеличением количества исходных изображений.

2.2 Силуэтные методы для воксельного представления

Первый силуэтный метод был разработан Мартином и Аггагвалом в 1983. С помощью обычного порогового фильтра яркости (intensity) они отделяли изображения фона от объекта. Морфологическая обработка полученного бинарного изображения позволяла определить силуэт. В качестве представления модели они выбрали модификацию воксельного - колонное представление. Воксельный куб задавался набором столбиков вокселей, перпендикулярный одной заданной плоскости. Каждый столбик (колонна) в этом случае описывается глубиной первого и последнего вокселя в столбике. Отрезки, соответствующие столбикам, проецировались на исходные силуэты, определялись точки пересечения проекций с силуэтом, а затем столбики обрезались - удалялась часть, проецирующаяся вне силуэта.

Рис.3 Удаление части воксельного столбца, проецирующегося вне силуэта объекта

В 1984-1986 годах Чин исследовал объемные представления на основе окто-деревьев. Исходными данными для его метода были три бинарных изображения полученные с ортогональных направлений визирования. Они затем преобразовывались в квадродеревья, и объединялись в одно окто-дерево. Такие строгие ограничения (ортогональность) на исходные изображения были главным недостатком это метода. В 1984 году Шнайер также предложил строить окто-деревья из сегментированных изображений, но реализация его идей так и не был осуществлена.

В 1987 году Потмесил разработал усовершенствованный алгоритм для реконструкции объектов по набору изображений с произвольно расположенных перспективных камер. Его алгоритм состоит из трех основных стадий. На первой стадии для каждого силуэта строится объемный конус в представлении окто-деревом. На второй эти конусы объединяются в модель. На третьей стадии вначале определяются границы каждого объекта, по соседним точкам рассчитываются нормали в каждой точки поверхности объектов. Затем каждой точке назначается определенный цвет из исходных изображений. Если данная точка видна на нескольких изображениях, то ее цвет определяется путем усреднения. Аналогичный метод был предложен в 1990 году, но все тесты его метода были проведены на синтезированных изображениях.

Метод Сзилиски, опубликованный в 1993 году, также использует окто-деревья в качестве объемного представления. Хотя его подход кажется очень похожим на подход Потмесила, их отличия весьма существенны. Потмесил строит отдельное окто-дерево по каждому изображению, а Сзилиски использует одно окто-дерево, уточняемое постепенно по новым изображениям, что значительно повышает скорость работы алгоритма.

Во второй половине 90-х годов методы получение видимых оболочек были применены для построения динамических сцен по видеопотокам, получаемым с набора видеокамер. Моэцца описывает систему из 17 камер, наблюдающих за сценой размером 1*1*2 метра. Каждый кадр обрабатывался для получения бинарного изображения - отделения фона и переднего плана. Методы пересечения силуэтных конусов применялись для построения видимых оболочек в воксельном представлении по сохраненным видеопотокам (в реальном времени на это не хватало времени). Объем одного вокселя составлял около 1 см. Из воксельной модели по методу изолиний строилась полигональная модель, для которой затем рассчитывалась текстура. Цвет текстуры получался взвешенным усреднением значений соответствующих пикселей в изображениях. В 1997 году эта технология была улучшена с помощью новых методов раскраски поверхностей.

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

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

2.3 Видимая оболочка на основе изображений (image-based visual hull)

В 2000 году была предложена идея видимой оболочки на основе изображений (image-based visual hull). Это разновидность многослойного изображения с глубиной. Для каждого пикселя изображения с силуэтом объекта хранится список заполненных отрезков. Если пиксель не входит в силуэт (т.е. принадлежит фону) это список пуст. В противном случае, список содержит интервалы пространства, принадлежащие видимой оболочке объекта. Каждый интервал представляет собой часть телесного конуса с вершиной в точке камеры и сечением-пикселем, т.е. часть видимой оболочки, проецирующейся в данный пиксель. Объединение всех таких интервалов дает нам дискретизацию видимого тела для данной точки обзора. Каждый интервал храниться в виде пары точек (ближняя и дальняя границы), заданных глубиной и цветом. Считается, что цвет любой точки интервала интерполируется по цветам граничных точек.

Рис.4 Набор отрезков, составляющих видимую оболочку на основе изображений

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

3. Согласование по цветам

3.1 Условие согласования по цветам

Группа методов <раскраски вокселей> основана на условии согласовании по цветам (color consistency), впервые описанном Сайтцем в 1997 году. Используя это правило, можно определить, лежит ли данная точка на поверхности объекта, или нет. Предположим, что все поверхности наблюдаемых объектов - диффузны. Пусть камеры A и B наблюдают одну и ту же точку в пространстве С. Обозначим за P(C,A) и P(C,B) пиксели на полученных с камер А и B изображениях, соответствующих точке С. Если С - лежит на поверхности некоторого объекта, то цвета пикселей P(C,A) и P(C,B) приблизительно равны, тогда С называется согласованной по цвету. Если же точка С - воображаемая точка в пустом пространстве, то цвета обоих пикселей соответствует цветам двух различных точек D и Е, а значит, скорее всего будут различны.

Рис.5 Случаи выполнения и невыполнения условия согласования по цветам

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

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

Рис.6 Возможная ошибка согласования цветов

 

3.2 Методы согласования по цветам с ограничением на расположение камер

Первый метод, использующий согласование был разработан Фромхерцем в 1995 году. Он использовал идею согласованности по яркости в дополнение к основному алгоритму пересечения объемов. В 1997 году Сайтц и Дир продемонстрировали, что хорошо раскрашенные сцены могут быть восстановлены и с помощью одного метода согласования цветов, без использования пересечения объемов. Они назвали свой алгоритм - <раскраска вокселей> (voxel coloring).

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

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

Сайтц и Дир накладывали определенное ограничение на расположение камер, с которых получали исходных изображений, названное ими ограничением на порядок видимости (ordinal visibility constraint). Оно требовало такого расположения камер, чтобы все воксели могли быть просмотрены за один проход, в порядке от ближайших к самым удаленным относительно каждой камеры. Обычно такому требованию удовлетворяло расположения всех камер по одну сторону от сцены, и обход воксельного тело последовательно по слоям, от ближнего к дальнему. Поэтому воксели, которые могли загораживать другие, проверялись на согласованность в первую очередь. Это гарантировало то, что видимость каждого вокселя не изменялась после его просмотра. Для каждого исходного изображения дополнительно задавалась битовая карта видимости (occlusion bit map). Вначале, все ее биты устанавливались равными нулю. Если проецирующийся в данный пиксель воксель помечался как согласованный и непрозрачный, то бит видимости для него устанавливался в 1.

Время восстановления сцены по алгоритму Сайтца и Дира пропорционально количеству вокселей в представлении сцены. Прок в 1998 году показал, что модификация их алгоритма с переменной разрешающей способностью (multiresolution) позволяет достичь в некоторых случаях десятикратного прироста в скорости. Вначале сцена восстанавливалась с низким разрешением. Некоторые воксели в этом случае помечались как пустые, т.к. лишь малую часть их объема занимали объекты сцены. Но если разбить такой большой воксель на несколько маленьких, то некоторые из маленьких окажутся почти полностью заполненными. Поэтому все соседние с невырезанными вокселями обратно добавляются в модель, и помечаются как непрозрачные. Такая модифицированная модель в низком разрешении направляется на последующую обработку. Каждый непрозрачный воксель разбивается обычно на 8 маленьких. Затем они все снова проверяются на согласованность цветов. Полученная промежуточная модель будет исходной точкой для следующей итерации алгоритма. Программа продолжает работать до тех пор, пока не будет получена модель в требуемом разрешении. Такой подход является развитием силуэтного метода и использует согласование цветов.

3.3 Алгоритмы согласования по цветам с произвольным расположением камер

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

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

Данный алгоритм будет работать корректно, если ни один воксель, который должен быть признан согласованным в результирующей модели не будет вырезан на предыдущих стадиях. В 1998 году Кутулакос сформулировал условие монотонности меры согласованности, при выполнении которого обеспечивается корректность его работы. Монотонность обозначает, что если множество вокселей было признано несогласованным, то любое их надмножество тоже будет несогласованным. Т.к. алгоритм может только удалять воксели, но не добавлять их в сцену, то видимость вокселя может только повыситься, т.е. пиксели, из которых виден данный воксель в данный момент обязательно будут только подмножеством тех пикселей, из которых он будет виден в последующем. Т.к. алгоритм не удаляют те воксели, которые окажутся согласованными по цвету в результирующей модели, то говорится, что процесс удаления (<вырезания>) консервативен. Кроме того, Кутулакос и Сайтц доказали, что найденная модель будет содержать в себе любую модель данной сцены из согласованных вокселей. Такая модель называется фото-оболочкой.

Кутулакос и Сайтц описали реализацию подобного алгоритма, получившего название <Резьба по пространству> (Space carving). Для определения согласованности вокселей используется обычный алгоритм раскраски вокселей, в каждый момент времени просматривается один слой вокселей. Метод обеспечивает просмотр слоев от ближнего-к-дальнему относительно камер, используя в данный момент времени только изображения, полученных с камер расположенных по одну сторону от просматриваемой плоскости слоя. Поэтому, когда воксель просматривается, те из вокселей, которые могли его загораживать для используемых камер, уже были просмотрены. Т.к. процесс консервативен, то множество невырезанных вокселей в данный момент времени будет надмножеством вокселей искомого множества согласованных вокселей.

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

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

3.4 Обобщенная раскраска вокселей

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

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

Рис.7 Обычный и многослойный буфер элементов

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

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

3.5 Метод множества гипотез (multi-hypothesis)

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

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

Рис.8 Проверка выдвинутых гипотез о вокселе

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

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

3.6 Деформированный объем (volumetric warping)

Практически все описанные методы могут эффективно применяться только для восстановления относительно близко расположенных к камерам моделей. Если попытаться применить их для больших сцен, со множеством удаленных от камер поверхностей, исходный воксельный объем становится очень большим. Для достижения приемлемой точности потребуется очень высокое его разрешение, а значит, необходимо обработать гигантское количество вокселей. Кроме того, предпочтительнее было бы восстанавливать модели удаленных объектов с меньшим, чем у близкорасположенных, разрешением. Соответственно, размер одного вокселя должен выбираться в зависимости от расстояния от камеры до объекта. В 2000 году Слэбо предложил деформировать воксельное пространство таким образом, чтобы большие сцены можно было бы восстанавливать без обработки огромных массивов вокселей. Согласно его идее, все воксельное пространство разбивается на две области: внутреннюю и внешнюю. Деформация не затрагивает внутреннюю область, поэтому близкие к камерам объекты восстанавливаются с заданной точностью. Воксели во внешней области деформируются согласно специальной функции деформации, которая определяет их размеры в зависимости от расстояния до внутренней области. Воксели на внешней границе деформируются таким образом, что их объем становится равным бесконечности. Не смотря на то, что воксели во внешней области имеют разные размеры, воксельно пространство все равно сохраняет свойства трехмерной решетки. Используя метод обобщенной раскраски вокселей, авторы сумели восстановить модель сложной внешней (outdoor) сцены.

Рис. 9 Деформированный воксельный куб

3.7 Связанные воксельные пространства

Все описанные методы могут применяться для восстановления моделей динамических сцен, путем последовательного применения алгоритма для каждого момента времени (для каждого кадра). Однако в этом случае никак не учитывается временная связность (temporal coherence). В работе под руководством Ведулы был предложен новый метод раскраски вокселей, оперирующий в 6-и мерном пространстве, состоящим из произведения двух последовательных 3-х мерных воксельных пространств. Каждая точка такого пространства получила название хексель, и состоит из вокселя в момент времени t1 из первого пространства, и связанного с ним другого вокселя из второго пространства в момент времени t1. Идея метода заключалась в том, чтобы одновременно восстанавливать и модель объекта, и его движение на данный момент времени.

Для этого авторы обобщили понятие согласованности по цвету для 6-и мерного пространства и назвали его фото-согласованность (photo-consistency). Хексель объявляется фото-согласованным, если оба составляющих его вокселя проектируются в пиксели примерно того же цвета на всех изображениях, на которых они видны. Авторы также предложили алгоритм для обхода такого 6-и мерного пространства для удаления лишних хекселей. Они показали, что использование более сильного определения фото-согласования позволяет удалять и те воксели, которые оказываются не согласованными по движению. Модель восстанавливается с более высоким качеством, чем при применении обычных алгоритмов отдельно к каждому из кадров.

4. Заключение

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

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

5. Список литературы:

1. S.M. Seitz, C.R. Dyer. "Photorealistic Scene Reconstruction by Voxel Coloring" Proc. IEEE CVPR, pp. 1067-1073, June 1997
2. L. Nyland, D. McAllister, V. Popescu, C. McCue, A. Lastra, P. Rademacher, M. Oliveira, G. Bishop, G. Meenakshisundaram, M.Cutts, H.Fuchs "The Impact of Dense Range Data on Computer Graphics" http://www.cs.unc.edu/~ibr/
3. L. McMillan. "An Image-based Approach to Three-Dimensional Computer Graphics" Ph.d. dissertation, University of North Carolina at Chapel Hill, 1997.
4. J. Shade, S. Gortler, L.-w. Hey, and R. Szeliski. "Layered depth images" Proceedings of the SIGGRAPH 98, Orlando, FL, 1998.
5. P. Eisert, E. Steinbach, and B. Girod, "Multi-Hypothesis, Volumetric Reconstruction of 3-D Objects From Multiple Calibrated Camera Views" Proceedings of the International Conference on Acoustics, Speech, and Signal Processing, 1999, pp. 3509-3512.
6. K. N. Kutulakos and S. M. Seitz, "A Theory of Shape by Space Carving" International Journal of Computer Vision, Vol. 38, No. 3, July 2000, pp. 199-218.
7. A. Laurentini, "The Visual Hull Concept for Silhouette-Based Image Understanding" IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 16, No. 2, Feb. 1994.
8. G. Slabaugh, W. B. Culbertson, T. Malzbender, and R. Schafer, "Improved Voxel Coloring Via Volumetric Optimization" Center for Signal and Image Processing Technical Report TR3, Georgia Institute of Technology, 2000. Available online at http://www.ece.gatech.edu/~slabaugh/
9. E. Steinbach, B. Girod, P. Eisert, and A. Betz, "3-D Object Reconstruction Using Spatially Extended Voxels and Multi-Hypothesis Voxel Coloring" Proceedings of the International Conference on Pattern Recognition, 2000.
10. E. Steinbach, B. Girod, P. Eisert, and A. Betz, "3-D Reconstruction of Real-World Objects Using Extended Voxels" Proceedings of the International Conference on Image Processing, 2000, Vol. III, pp. 138-141.
11. S. Vedula, S. Baker, S. Seitz, and T. Kanade, "Shape and Motion Carving in 6D" Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2000.
12. S. Seitz, K. Kutulakos. "Plenoptic image editing" In Proc. 5th Int. Conf.on Computer Vision, 1998.
13. B.Curless, S.Seitz "3D Photography" Siggraph 2000 course
14. S.Seitz "An Overview of passive vision techniques" Carnegie Mellon University http://www.cs.cmu.edu/~seitz 1999

Дополнительная информация

Ссылка: 

Антон Конушин. Реконструкция модели объекта по силуэтам и по согласованию цветов. Компьютерная графика и мультимедиа. Выпуск №1(3)/2003. http://cgm.computergraphics.ru/content/view/44

Выпуск: 

Выпуск №1(3)/2003