`

СПЕЦИАЛЬНЫЕ
ПАРТНЕРЫ
ПРОЕКТА

Архив номеров

Как изменилось финансирование ИТ-направления в вашей организации?

Best CIO

Определение наиболее профессиональных ИТ-управленцев, лидеров и экспертов в своих отраслях

Человек года

Кто внес наибольший вклад в развитие украинского ИТ-рынка.

Продукт года

Награды «Продукт года» еженедельника «Компьютерное обозрение» за наиболее выдающиеся ИТ-товары

 

Городок в табакерке

0 
 

Если бы вы увидели в действии технологии, описанные в этой статье, то наверняка заподозрили бы демонстраторов в мошенничестве. Цирковые трюки, да и только! Ученые Массачусетского технологического института научились делать точные трехмерные модели из любых реальных объектов, начиная с человека и заканчивая городским кварталом.

Сейчас вылетит птичка!

Представьте, что вы заглянули в игровой компьютерный клуб следующего десятилетия. Зашли в зал, заказали себе пару часов игры и уселись за ПК. Загрузили, к примеру, недавно появившийся Duke Nukem Forever и подключились к сетевому серверу, на котором уже сражаются несколько пользователей. Выбирая себе внешний вид героя, вы обнаруживаете среди предложенных моделей... себя. Причем именно в том костюмчике, в котором вы и решили выбраться в клуб. В случае удачного дебюта вашим уязвленным и пораженным соперникам уже не надо будет спрашивать: "А кто играет под ником таким-то?".

Как такое возможно? Очень просто. На входе все посетители клуба проходят мимо -- улыбнитесь-вас-снимает-скрытая-камера -- цифрового фотоаппарата, но не вполне обычного, а стерео. Если совсем упростить, конструкция представляет собой две цифровые камеры, укрепленные на общем штативе. Камера делает серию снимков и передает их по интерфейсу Bluetooth на ПК сисадмина, где за то время, пока вы делаете шаг внутрь помещения, формируется ваша точная трехмерная модель -- mesh, насчитывающий несколько десятков тысяч полигонов. Вам остается только сесть на игровое место и выбрать игру: RPG, шутер или стратегия.

А помните материал о Нижнем Новгороде и нижегородской лаборатории Intel? Ее сотрудники предложили новую разновидность видеоконференций, для которых не потребуется значительной пропускной способности, а вполне хватит производительности обыкновенного модема. Вместо видео они решили транслировать в сети данные для анимирования трехмерной модели человека на клиентском ПК. Программа отслеживает движение контрольных точек на лице человека и соответствующим образом деформирует конечную модель. Так вот, работа ученых Массачусетского технологического сделала "виртуальные" телеконференции реальностью.

Чтобы оценить, насколько прогрессивна новая технология, необходимо сравнить ее "достижения" с лучшими показателями самых известных на сегодня трехмерных сканеров. Например, почившая в бозе MetaFlash, разработанная командой специалистов компании MetaCreation. Тоже стереокамера, тоже моментальные "трехмерные" фотографии, но даже не зная ничего более совершенного, начав изучение методики, вы были бы разочарованы ее ограничениями. Условия съемки какие-то слишком уж жесткие: никаких блестящих поверхностей, ничего прозрачного, только полумрак, размер объекта -- максимум 40 см, расстояние до него -- не более 90 см. Да еще и "сшивать" полученные изображения надо вручную в специальном редакторе, так что пользователю волей-неволей приходится изучать азы трехмерного моделирования.

А теперь вспомним об изобретении ученых MIT: первая экспериментальная установка сумела за 10 секунд изготовить фрагментарную модель головы человека, который произвольно двигался перед стереокамерой. Обработка данных осуществлялась со скоростью 7 кадров в секунду на обычном Pentium 4 c частотой 1,5 GHz.


Как поймать птичку

Городок в табакерке
Рис. 1

Все начинается с получения фотографического изображения предмета (для этого довольно и одной камеры) и карты глубин, или depth map (вот зачем необходима вторая). Как известно, карта глубин составляется на основании различий между изображениями стереопары, каждый ее пиксел определяет расстояние от поверхности до точки фотографирования. Затем делается еще одна стереофотография, потом еще одна... и так несколько раз в секунду (рис. 1). Все время, пока объект двигается перед камерой, идет процесс формирования и уточнения модели. В идеале должен получиться набор изображений, охватывающий "натурную модель" со всех сторон. Но прежде чем "панорама наоборот" будет создана, нужно состыковать имеющиеся изображения и карты глубин. Их необходимо совместить так, чтобы не было видно ни швов, ни разрывов.

Здесь вступает в действие алгоритм поиска и сопоставления точек соответствия (correspondence points). Авторы технологии оказались "хитрее Улисса": они совместили две методики "склеивания" изображений. Одна из них основывается на функции минимизации различий в распределении яркости между выбранной парой кадров. При этом используется методология морфинга (напомню -- это плавная трансформация одного изображения в другое, как в фильмах "Терминатор 2" или "Матрица"). Стыкуемый кадр таким образом ориентируется в пространстве, чтобы минимизировать поток пикселов (image flow), необходимый для трансформации изображений одного в другое. Вторая техника сшивания предусматривает реализацию той же функции, но уже для карт глубин. Вместе методики работают точнее. Дело в том, что на процесс сопоставления карт глубин не влияют изменения освещенности от кадра к кадру, что вносит свои погрешности в результаты использования яркостного алгоритма. С другой стороны, любые вращения камеры или предмета приводят к изменениям в картах глубин, в то время как для яркостной методики такие вращательные перемещения не имеют значения.

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

Теперь приходит черед алгоритма, конструирующего полигональные модели, пока из каждого кадра в отдельности. Затем полигоны, снабженные информацией о нормальном векторе (перпендикуляр к поверхности полигона) и освещенности, помещаются на свое место в "сшитом" объемном изображении. На данном этапе нам снова придется вспомнить об одном модном новшестве -- вокселах. Трехмерные пикселы постепенно перебираются из игр в серьезные приложения. Слепленная на предыдущем шаге полигональная модель на самом деле представляет собой "облако" плохо состыкованных полигонов, недаром каждый из них снабжен коэффициентом "неопределенности", или "uncertainty". Полученную "неопределенную массу" далее преобразуют в столь же неопрятную модель, но уже в связанном воксельном пространстве (linked voxel space). Для тех, кто плохо знаком со свойствами вокселов, скажу, что воксел есть трехмерный пиксел -- не математически "бестелесная" точка, а пиксел, обладающий некой толщиной и шириной.

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

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

Городок в табакерке
Рис. 2

Площадь воксела в проекции определяется путем сопоставления направления его нормального вектора и трассирующего луча. Те вокселы, чьи проекции перекрываются или располагаются рядом, считаются результатом ошибки при стыковке фотографий и объединяются. На последнем этапе из связанного воксельного пространства создается полигональная модель. Проекция позволяет значительно сократить количество полигонов по сравнению с первоначальной структурой. Рассмотрим реальный пример: полученная во время эксперимента модель головы человека насчитывала 200 тыс. вершин до упрощения и всего 18 тыс. после (рис. 2). На все вычислительные процессы потребовалась всего 1 секунда.


Городок в табакерке

-- Неужели он существует только для меня? Весь этот мир?
-- Он не очень большой, -- заявил Джори. -- Один отель в Де-Мойне. Улица за окном, на ней немного людей и машин. Ну и еще пара домов и магазинов для полноты вида из окна.
Филипп К. Дик, Убик

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

Как ни удивительно, технология, применяемая для оцифровки зданий, и технология генерирования модели человека, описанная ранее, основаны на схожих принципах. Методика практически та же, но "с точностью до наоборот": объект здесь не вращается, а изменяется ракурс съемки. Вместо вида со всех сторон получается панорамная фотография, отличающаяся от обычной лишь охватом пространства. Зона фотографирования представляет собой полусферу 360° по горизонтали на 180° по вертикали. Она покрывается 47 отдельными изображениями разрешением 1012 x 1524 каждое. Процесс автоматизирован за счет компьютера, смонтированного на той же платформе, что и камера. Точки съемки располагаются с интервалом 10 метров. В том случае, если фотографирование ведется с возвышенности (например, крыши здания), количество кадров увеличивается до 71 за счет частичного охвата нижней полусферы. Фотографии дополняются данными абсолютных координат (относительно Земли, конечно) размещения платформы и направления съемки. Для этого Argus снабжен угловыми датчиками положения (фиксируют вращения камеры) и адаптером GPS.

Городок в табакерке
Рис. 3

В результате работы "в поле" образуется невероятное количество изображений, сделанных с разных позиций и в различных ракурсах представляющих объекты, которые еще только предстоит смоделировать. Проблема в том, что даже для того чтобы получить нормальные панорамные картинки, необходимо филигранно "склеить" от 47 до 71 отдельных фотографий. И так для 81 локации -- именно столько потребовалось для первой пробной оцифровки трех зданий кампуса. Раньше эту работу выполнял человек -- футуристический аналог Золушки. Но поскольку главной целью проекта было создание полностью автоматизированной системы, ученые разработали алгоритм, использующий точки схода (vanishing points) для стыковки изображений.

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

Впрочем, до завершения разработок еще далеко, ведь цель эксперимента -- сконструировать трехмерные модели, а не опубликовать в журнале "National Geographic" хорошо состыкованные панорамные изображения. Алгоритмы генерирования моделей делятся на две основные категории: отслеживающие детали объектов (линии, группы пикселов) и базирующиеся на многоуровневых изображениях и вокселах (Seitz, Dyer).

Городок в табакерке
Рис. 4

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

Городок в табакерке
Рис. 5

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

Дальнейшие разработки ведутся в направлении уточнения и детализации моделей. По мере накопления практического опыта технология совершенствуется, и в ближайших планах -- реализация системы, способной воспроизвести интерьер помещений (что, надо отметить, является более сложной задачей, чем рендеринг зданий, имеющих в основном незамысловатую форму и структуру). Также предпринимаются попытки изготовить видеоверсию платформы, которая будет снимать панорамы с помощью видеокамеры и формировать модели в режиме реального времени подобно стереоустановке, описанной в начале статьи. Чтобы быть в курсе последних событий, посетите Web-странички, на которых собраны публикации сотрудников лаборатории, по адресу: http://graphics.lcs.mit.edu/publications.html и http://graphics.lcs.mit.edu/~seth/pubs/pubs.html.

0 
 

Напечатать Отправить другу

Читайте также

 
 
IDC
Реклама

  •  Home  •  Рынок  •  ИТ-директор  •  CloudComputing  •  Hard  •  Soft  •  Сети  •  Безопасность  •  Наука  •  IoT