2010 г.
Творцы виртуальной Земли
Сергей Кузнецов
Обзор июньского, 2010 г. номера журнала Computer (IEEE Computer Society, V. 43, No 6, июнь 2010).
Авторская редакция.
Также обзор опубликован в журнале "Открытые системы"
В этом году июньский номер журнала Computer посвящен различным методам создания цифрового представления Земли. В тематической подборке четыре большие статьи. Приглашенным редактором тематической части номера является Оливер Бимбер (Oliver Bimber, Johannes Kepler University Linz, Austria). Его вводная заметка называется «Запечатление мира» («Capturing the World»).
В 1796 г. Александр фон Гумбольдт (Alexander von Humboldt) написал своему другу Марку-Августу Пикте (Marc-Auguste Pictet): «Je conçus l’idee d’une physique du monde», т.е. у него возникла идея составить физическое описание мира. Только три года спустя он отправился в свое величайшее путешествие, посвященное исследованию Латинской Америки. Вместе со своим компаньоном Еме Бонпланом (Aimé Bonpland) он прошел 1725 миль (2776 км) вдоль русла реки Ориноко (Orinoco) по дикой и малообитаемой стране. Они пытались определить высоту горы Чимборасо (Chimborazo), находящейся на территории современного Эквадора, и достигли высоты в 19286 футов (5878 м), что в то время являлось мировым рекордом. Для определения координат своего местоположения и выполнения других измерений Гумбольт использовал около 50 современных приборов, включая секстанты, телескопы и астрономические квадранты. Эта легендарная экспедиция, в конечном счете, привела к образованию физической географии. Через 40 лет после написания своего письма Пикте и после своей экспедиции в Россию, во время которой он прошел 9614 миль (15472 км), Гумбольт приступил к созданию четырехтомного труда своей жизни «Космос: набросок физического описания мира» («Kosmos – Entwurf einer physischen Welbeschreibung»).
За прошедшие 200 лет многое изменилось, но стремление запечатлеть и описать мир в целом по-прежнему существует. Сегодня на поверхности Земли на площади около 58 квадратных миль (150 млн. км2) в примерно 1,5 млрд. домов проживает почти 7 млрд. человек. С точки зрения геометрии, для создания физического описания мира (увы!) больше не требуются рискованные экспедиции. Горстку исследователей заменили миллиарды туристов, вместо секстантов используются спутники Земли, самолеты, специальные наземные транспортные средства, цифровые камеры и мобильные телефоны. Однако за все эти годы не изменилось одно обстоятельство. Ровно так же, как планы Гумбольта несколько раз изменялись из-за Наполеона Бонапарта, запечатлению мира сегодня продолжают мешать политические проблемы и военные конфликты.
Первая основная статья тематической подборки написана Францом Леберлом, Херстом Бишофом, Томасом Поком, Арнольдом Иршара и Стефаном Клюкнером (Franz Leberl, Horst Bischof, Thomas Pock, Arnold Irschara, Stefan Kluckner, Graz University of Technology, Austria) и называется «Надземное машинное зрение для поддержки трехмерной виртуальной среды обитания» («Aerial Computer Vision for a 3D Virtual Habitat»).
В 2005 г. Билл Гейтс представил обществу свою идею виртуальной Земли: «Вы сможете прогуливаться по центру Лондона и видеть все магазины, все, что происходит вокруг. Можно будет зайти в магазин и посмотреть, что в нем продается. И все это будет доступно в режиме виртуальной реальности, а не на основе двухмерного интерфейса, свойственного сегодняшнему Web’у».
Эта идея привела к Виртуальной Земле (Virtual Earth) компании Microsoft, называемой теперь службой Bing Maps. Естественно, при реализации этого проекта используются нетривиальные данные: для поддержки стандартной фоновой карты мира с геометрическим разрешением около 15 см, получаемой из инфракрасных-красных-зеленых-синих изображений с высоким уровнем перекрытия, требуются исходные данные объемом примерно 200 петабайт. Кроме того, для реализации идеи Гейтса требуются объекты, которые люди могут рассмотреть, находясь на улице, – чтобы можно было прочитать уличные вывески, нужно обеспечить геометрическое разрешение примерно в 2 см; для полноценного посещения виртуальных магазинов и музеев требуется моделирование внутренних помещений и находящихся в них объектов, и для этого нужно обеспечить геометрическое разрешение в 0,5 см.
Среда обитания людей охватывает 150 миллионов км2 поверхности Земли. На этой площади расположено около 1,5 миллиардов строений. Создание и поддержка трехмерной модели этой среды обитания на основе Internet может обеспечить повсеместную доступность детальной информации о местоположениях, уже частично реализованную в Google Earth и Bing Maps. Повышение уровня детализации для поддержки передвижения пешеходов приводит к появлению приложений для мобильных телефонов и «дополненной реальности» (augmented reality).
На первый взгляд, аэрофотосъемка конкурирует с получением изображений с искусственных спутников Земли, особенно, при потребности в получении данных о запретных районах, контролируемых недружественными властями. Однако спутниковые изображения с разрешением 50 см на пиксель недостаточны для размещения на картах объектов масштаба человека, в то время как аэрокамеры могут обеспечить разрешение от 5 до 15 см на пиксель, требуемое для представления таких подробностей, а для обеспечения полной автоматизации они могут предоставить десятикратную избыточность без дополнительных расходов.
Эволюция карт. Традиционные уличные схемы являются разреженными и обычно используются автомобилистами для простой навигации. Больше информации появляется на аэроснимках в ортографической проекции (в середине). И, наконец, наиболее полную информацию обеспечивают трехмерные данные (в нижней части рисунка показано трехмерное изображение строения в Денвере, шт. Колорадо).
Аэрофотоснимки на уровне улиц для всего мира занимают экзабайт памяти. Виртуальная Земля основана на информации, извлекаемой из этих данных. Она состоит из трехмерной модели «голой» Земли и трехмерных объектов (естественных и произведенных людьми), расположенных на ее поверхности. В виртуальной среде обитания к виртуальной Земле добавляются объекты внутри и вне зданий, представляющие интерес для людей. Это не только позволяет полностью реализовать идею Гейтса о поиске в Internet с использованием деталей текущего местоположения человека, но также обеспечивает основу для возникновения «окружающего интеллекта» (ambient intelligence). Вооружив виртуальную среду обитания датчиками, подключенными к Internet, мобильными устройствами и RFID-маркерами, можно будет отслеживать перемещения людей и объектов, определять их текущее положение и обеспечивать соответствующие средства поиска в Internet.
Статья «Google Street View: запечатление мира на уровне улиц» («Google Street View: Capturing the World at Street Level») представлена Драгомиром Ангеловым, Кэрол Дюлон, Дэниэлом Филипом, Кристином Фрю, Стефаном Лафоном, Ричардом Лионом, Адхиджитом Огале, Люком Винцентом и Джошем Вевером (Dragomir Anguelov, Carole Dulong, Daniel Filip, Christian Frueh, frueh@google.com, Stéphane Lafon, Richard Lyon, Abhijit Ogale, Luc Vincent, Josh Weaver, jweaver@google.com).
Несколько лет назад соучредитель компании Google Ларри Пейдж проехал на машине вдоль области залива Сан-Франциско и отснял несколько часов чернового видеоматериала, ориентируясь на фасады домов. По его мнению, миссией Google является организация информации по всему миру и обеспечение ее доступности и полезности, а в уличных изображениях такого типа кроется масса информации. Идея Ларри состояла в организации исследований и разработок, направленных на то, чтобы сделать подобные изображения полезными в крупном масштабе. Его энтузиазм и личное участие привели к началу совместного проекта CityBlock со Стэндфордским университетом, и на основе результатов этого проекта вскоре появилась служба Google Street View.
Этот проект иллюстрирует два основных принципа, которыми руководствуется Google. Один из них заключается в том, что новые проекты начинаются без долгих обсуждений наилучших способов их выполнения. Инженеры и менеджеры предпочитают сразу получить некоторые результаты, а потом итерационным образом их совершенствовать. Второй принцип состоит в том, что Google основном берется за решение крупных проблем. Этим принципам, безусловно, отвечает проект Street View, направленный на получение, обработку и обслуживание уличных изображений в мировом масштабе.
Транспортные платформы Street View: (a) специализированные автомобили второго (справа) и третьего (слева) поколений; (b) трайк; (c) модифицированный снегоход. По данным Всемирной книги фактов (The World Factbook), издаваемой ЦРУ, в 219 странах мира имеется примерно 50 миллионов миль дорог, с покрытием и без покрытия. Объехать все их по одному разу – это все равно, что 1250 раз объехать Землю по экватору. Даже для Google эта задача ужасающе масштабна. Команде Street View предстоит долго работать для завершения проекта, но эта работа выполняется по шагам. Разрабатывая специализированное программное и аппаратное обеспечение, совершенствуя операционные процессы, команда достигла значительного прогресса: услугами Street View ежедневно пользуются миллионы пользователей Google, получая доступ к панорамным изображениям улиц в сотнях городов двадцати стран, расположенных на четырех континентах.
Авторами статьи «Воссоздание Рима» («Reconstructing Rome») являются Самир Агарвал, Ясутака Фурукава, Ноа Сневели, Брайан Кэлесс, Стивен Сейц и Ричард Зелиски (Sameer Agarwal, Yasutaka Furukawa, Google, Noah Snavely, Cornell University, Brian Curless, Steven M. Seitz, University of Washington, Richard Szeliski, Microsoft Research ).
Когда-то любительская фотография была, в основном, частным делом людей. Традиционно человек с фотоаппаратом фиксировал на пленку какое-то событие и показывал снимки небольшому числу друзей и членов семьи, возможно, вставляя лучшие фотографии в фотоальбомы и сохраняя сотни других снимков в коробке из-под обуви. Однако появление цифровой фотографии и сайтов, поддерживающих совместное использование фотографий, таких как Flickr, привело к радикальным изменениям в фотографии и использовании фотоколлекций. Сегодня фотоснимок, сделанный любителем и выложенный им в Internet, потенциально могут увидеть миллионы людей.
Соответственно, у людей, создающих трехмерные модели городов, теперь имеется доступ к огромной, постоянно расширяющейся коллекции фотографий, которые охватывают весь земной шар, и на которых запечатлены все города и архитектурные памятники несчетное число раз. Например, в ответ на запрос по ключевому слову «Rome» Flickr возвращает более двух миллионов фотографий. Эта коллекция представляет собой все более полный фотографический архив города; в ней содержатся фотографии всех популярных мест города, фасадов и интерьеров зданий, фонтанов, скульптур, живописных произведений, ресторанов и кафе и т.д. Практически все, что может заинтересовать людей в Риме, запечатлено в разных ракурсах, при различном освещении и погодных условиях. В частности, фонтану Треви в Flickr посвящено более 50000 фотографий.
Какие трехмерные модели Рима можно построить на основе этой фотоколлекции? В принципе, изображения Рима из коллекции Flickr являются идеальным набором данных для исследований в области трехмерного моделирования, поскольку представлены городские достопримечательности во всех деталях и в разных ракурсах. Однако построение высококачественных трехмерных моделей на основе этой коллекции чрезвычайно проблематично по нескольким причинам. Во-первых, фотографии не структурированы, они делались беспорядочно, без какого-либо известного выбора точки съемки. Во-вторых, они не калиброваны – фотографии делаются тысячами людей, и очень мало известно об установочных параметрах их фотокамер. В-третьих, огромен масштаб проблемы. Если в предыдущих методах трехмерного моделирования использовалось не более нескольких тысяч фотографий, то теперь нужно обработать коллекции, объем которых на два-три порядка больше. Наконец, алгоритм должен быть быстрым. Требуется научиться создавать трехмерную модель города за один день, чтобы обеспечить возможность охватить все значительные мировые культурные центры.
Трехмерные модели городов могут использоваться в различных приложениях. В секторе государственного управления модели требуются для планирования и визуализации развития городов. Модели не менее важны и в научных дисциплинах, включая историю, археологию, географию и т.д. Цифровые модели городов играют центральную роль в Internet-приложениях типа Google Earth и Bing Maps, а также в навигационных системах, основанных на GPS. В близком будущем эти модели обеспечат появление средств «дополненной реальности» (augmented-reality), которые позволят распознавать и аннотировать объекты на дисплеях мобильных телефонов со встроенными фотокамерами и других мобильных устройств. Такие средства помогут туристам в поиске интересующих их достопримечательностей, выборе правильного направления движения и т.д.
Исследователи из области машинного зрения изучили много подходов к трехмерному моделированию городов. Однако существующие крупномасштабные системы опираются на данные, полученные из структурированных источников, например, например, на аэрофотоснимки, полученные со специальных летательных аппаратов, или на изображения улиц, запечатленные с движущегося автомобиля. Такие системы рассчитаны на использование фотоснимков, сделанных одинаково калиброванными фотокамерами, которые производят фотографирование с одинаковой частотой и обычно оснащаются дополнительными датчиками, такими как GPS и инерциально-навигационные устройства (inertial navigation unit). Это значительно упрощает вычисления.
Слева направо: исходные фотографии; разреженная модель; плотная модель.
У изображений, собираемых в Web, отсутствуют эти упрощающие характеристики. Такие фотоснимки делаются фотокамерами разного вида при разных условиях освещения, с ними связана в лучшем случае минимальная географическая информация, часто отсутствуют данные о калибровке фотокамеры. Поэтому основной упор в исследовании авторов делается на разработку новых методов трехмерного машинного зрения, которые могли бы создавать трехмерные модели городов на основе огромных коллекций разнородных изображений.
Последняя статья тематической подборки называется «Воссоздание сцен на основе фотоколлекций сообществ» («Scene Reconstruction from Community Photo Collections») и написана Микаэлом Геселе, Йенсом Акерманом, Симоном Фурманном, Ронни Кловски, Фабианом Ланггутом, Патриком Мюке и Мартином Рицом (Michael Goesele, Jens Ackermann, Simon Fuhrmann, Ronny Klowsky, Fabian Langguth, Patrick Mücke, TU Darmstadt, Martin Ritz, Fraunhofer IGD).
Открытый в феврале 2004 г. Web-сайт Flickr позволяет пользователям закачивать фотографии, добавлять к ним тэги и географическую привязку и использовать эти фотографии (а теперь и видео) совместно с сообществом. Пользователи могут просматривать чужие фотографии, производить поиск по тегам и описаниям и добавлять комментарии. На сегодня пользователи Flickr закачали на сайт 4,5 миллиона файлов, образующих громадную, быстро растущую базу данных аннотированных изображений.
Появление и доступность такого нового, огромного и разнотипного набора данных немедленно поставили перед исследователями несколько вопросов. Для чего его можно было бы использовать? Насколько это будет полезно? Пригоден ли этот набор данных для обработки методами машинного зрения, машинной графики и т.д. И на самом деле, вскоре после открытия Flickr исследователи поняли, что у этого ресурса имеется огромный потенциал. Первые исследования концентрировались на двух областях: совместная расстановка тэгов (community tagging) и способы взаимодействия пользователей. В 2006 г. Александр Джаффе (Alexander Jaffe) со своими коллегами разработал средство обобщения визуальных сцен на основе изображений с географическими привязками. Ноа Сневели и его коллеги создали систему Photo Tourism, которая строит трехмерное представление сцены, используемое затем в интуитивно понятном интерфейсе. С тех пор исследования, основанные на использовании фотоколлекций сообществ, распространились на разные области, включая обработку изображений и распознавание объектов.
В статье обсуждается один конкретный вопрос: каким образом можно воссоздать визуальную сцену на основе фотоколлекций сообществ. Авторы концентрируются на проблемах сложности и разнородности изображений.
Традиционно вне тематической подборки опубликованы две большие статьи. Статью «Беспроводная PKI-безопасность и мобильное голосование» («Wireless PKI Security and Mobile Voting») представили Йаак Тепанди, Станислав Васильев и Илья Захиров (Jaak Tepandi, Stanislav Vassiljev, Tallinn University of Technology, Estonia, Ilja Tšahhirov, InVision Software AG).
Инфраструктура сертификации открытых ключей (public key infrastructure, PKI) позволяет пользователям самостоятельно аутентифицироваться по отношению к Web-сервисам, пользоваться электронной подписью и шифровать тексты. PKI связывает личности пользователей с их открытыми ключами средствами сертифицирующих органов (certificate authority, CA).
PKI может поддерживать важные, критические по безопасности приложения, такие как банковские транзакции, системы электронной подписи и электронное голосование. Это предполагает соблюдение некоторых требований CA – регистрацию пользователей и наличие среды PKI. Для удовлетворения этих требований уполномоченные государством CA могут выпускать «проверенные сертификаты» (qualified certificate), сохраняемые в идентификационных карточках.
В Эстонии, стране с населением из 1,4 миллионов человек, выпущено более миллиона идентификационных карточек. Электронные подписи используются в договорах и других официальных документах. По состоянию на февраль 2010 г. CA выпустили около 27 миллионов электронных подписей. Основные банки Эстонии признают безопасность PKI на основе идентификационных карточек (ID-PKI) и требуют, чтобы все транзакции на сумму, превышающую некоторый порог, аутентифицировались и авторизовались с использованием идентификационных карточек. В Эстонии местные выборы в 2005 г., парламентские выборы в 2007 г. и выборы в Европейский парламент в 2009 г. проводись с использованием электронного голосования через Internet на основе ID-PKI.
В то время как ID-PKI обеспечивает значительные преимущества в отношении безопасности по сравнению с традиционными методами аутентификации, такими как списки одноразовых паролей и аппаратные аутентификационные жетоны, у этого подхода имеется проблема пригодности для использования, поскольку для аутентификации требуется устройство чтения идентификационных карточек, а также компьютер. Однако такие устройства не всегда доступны. Более удобно было бы использовать устройства, получившие в последние годы повсеместное распространение, – мобильные телефоны. В приложениях, критичных по безопасности, можно использовать компьютеры и мобильные телефоны, оснащенные картой Universal Subscriber Identity Module (USIM), для аутентификации и создания электронной подписи.
Наконец, последнюю статью июньского номера написали Анита Сарма, Дэвид Редмайлс и Андре ван дер Хок (Anita Sarma, University of Nebraska, Lincoln, David Redmiles, André van der Hoek, University of California, Irvine). Статья называется «Категоризация спектра технологий координации» («Categorizing the Spectrum of Coordination Technology»).
Эффективная координация, играющая центральную роль в любой групповой работе, – это, по существу, управление зависимостями заданий с применением объединения, упорядочивания заданий или устранения результатов некоторых, уже выполненных работ. В области разработки программного обеспечения отсутствие координации приводит к задержкам при выполнении проектов и возрастанию трудозатрат. Для координации даже одиночного централизованного проекта требуется существенный труд разработчиков, поскольку им требуется управлять многочисленными зависимостями каждого артефакта. Рассредоточение разработчиков по подгруппам, помещениям или странам значительно повышает уровень трудозатрат, требуемых для координации. Несмотря на наличие многочисленных инструментальных средств и использование прочно установившихся процессов, координация часто нарушается: системы рекомендаций указывают на одного и того же эксперта, системы конфигурационного управления не выявляют несовместимые изменения различных артефактов и т.д.
Оптимальное решение координации состоит в передаче правильной информации правильным участникам проекта в нужное время. Такой проект был бы совершенным по отношению к накладным расходам на координацию, интеграции совместной работы и развитию проекта в целом. Проблемами координации являются намеренные или случайные отклонения от этого оптимума. Таким образом, назначение инструментов координации является двойственным: снизить частоту возникновения проблем и смягчить воздействие возникающих проблем. Подобные проблемы могут проявляться в виде накладывающихся изменений, приводящих к конфликту при их слиянии, нарушения зависимостей, приводящего к неудачному построению очередной версии создаваемой системы или к разработке тестового набора независимо от кода системы, что не позволяет их интегрировать.
Технология координации состоит из инструментальных средств, поддерживающих совместную разработку программного обеспечения. Доступно огромное число таких средств. Для сравнения различных технологических средств на основе некоторой конкретной парадигмы (например, парадигм структурированных процессов или раскрытия информации) полезно использовать фреймворки. Однако традиционные фреймворки основываются только на какой-то одной парадигме, что ограничивает области их применения.
Для обеспечения возможности получения более полной картины авторы создали Пирамиду координации (Coordination Pyramid), в которой увязываются пять разных парадигм координации и обеспечивается классификация технологий координации в соответствии с основными поддерживаемыми ими парадигмами. Пирамида координации помогает организациям оценить и четко сформулировать свои потребности в координации, а также подобрать набор инструментов, удовлетворяющих эти потребности. Поскольку в Пирамиде технология в целом представляется на основе иерархии парадигм координации, Пирамида помогает формулировать и документировать тенденции развития технологии, а также выявлять перспективные направления исследований и области применения.