Что мы мечтаем увидеть?
АрхивТема этого номера — визуализация данных. Если бы кто-нибудь захотел сегодня написать подробную книгу о визуализации, толщина такого тома была бы не ограничена ничем, кроме эрудиции и трудолюбия автора.
Тема этого номера — визуализация данных. Если бы кто-нибудь захотел сегодня написать подробную книгу о визуализации, толщина такого тома была бы не ограничена ничем, кроме эрудиции и трудолюбия автора. По-настоящему фундаментальный подход потребовал бы начать с рассказа о современном понимании термина «данные», потом проанализировать, в том числе с позиций психологии и философии, что мы имеем в виду, рассуждая о том, как эти данные можно «увидеть», подробно рассказать о жестких и мягких средствах, использующихся для создания цифровых изображений и управления ими, и только тогда можно было бы с чистой совестью переходить к разбору концепций визуализации различных типов данных и способов реализации этих концепций.
Моя задача проще — изложить все это на нескольких страницах журнала. Поэтому в алгоритмические вопросы вникать почти не будем, философию и психологию постараемся игнорировать, и вообще многое оставим за кадром. Я назову лишь некоторые интересные проблемы и направления развития этой огромной отрасли (только американский IEEE каждый год проводит несколько специализированных конференций, собирающих тысячи участников — а ведь это лишь научный авангард), приведу интересные примеры визуализации, расскажу о новых аппаратных средствах. Чуть глубже в научную визуализацию вдается автор следующей статьи Михаил Бурцев, взявший примеры из близких ему областей: искусственной жизни, эволюционного компьютинга.
Итак, не будем уточнять, что такое «данные» (слайды лекции Дэвида Донохо [David Donoho] со злободневными лозунгами на эту тему см. на www.usna.edu/MathSci/Michelson_lecture.html). Главная особенность данных в том, что их невероятно много. Скромное моделирование урагана на суперкомпьютере генерирует несколько терабайт данных. Европейский адронный коллайдер способен за год обеспечить исследователей петабайтами. Жонглируя такими цифрами, обычно мотивируют важность проблем визуализации. Говоря цинично, надо же что-то делать с этим морем битов, в создание которого уже вложены огромные ресурсы. Впрочем, мотивировка здесь если и нужна, то лишь промышленности, бизнесу, но никак не науке. Независимо от сферы применения главная задача визуализации звучит весьма научно: помочь сформулировать гипотезы о структуре и динамике данных.
Маленький подвох заключается в том, что сам выбор способа визуализации уже содержит (хоть и неявно) некоторые гипотезы о том, что именно в данных мы считаем интересным, что хотим наглядно представить и вытащить в привычный нам мир предметов, которые можно повертеть в руках. Но это уже философия, которую мы решительно оставляем за скобками и переходим к технической стороне дела.
Пещерный человек, или Виртуальные устрицы
Начнем с аппаратных средств. Блиц-опрос нескольких продвинутых студентов и аспирантов МГУ показал, что еще не все у нас знают, что такое CAVE. Хуже того, поиски в Яндексе наводят на мысль, что на территории России нет ни одного CAVE. Жванецкий когда-то шутил: давайте поспорим о вкусе устриц с теми, кто их ел. Постараюсь избежать такой оплошности применительно к самой популярной сегодня в мире системе визуализации на основе виртуальной реальности (ВР). Ее название расшифровывается так: Cave Automatic Virtual Environment. Сегодня в мире примерно сто таких «пещер»1. Созданная в 1991 году в Лаборатории электронной визуализации (EVL) Университета Иллинойса в Чикаго, конструкция (рис. 1) оказалась весьма удачной, ее используют далеко за пределами сообщества ВР — биологи, автомобилестроители, физики, архитекторы, историки [1]. Сейчас существует множество вариаций этой конструкции, реализованных в разнообразных пещероподобных сооружениях, часто называемых просто cave, с маленькой буквы. Классическая CAVE — комната 3 на 3 метра, на три стены и пол проецируется «трехмерная реальность», которую пользователь наблюдает через жидкокристаллические стереоскопические очки CrystalEyes. Очки синхронизируются с обновлением изображений на стенах и полу при помощи стереоэмиттеров с частотой 120 или 96 Гц. Сами изображения генерируются графической станцией SGI, проекторы и зеркала для стен расположены непосредственно за стенами, проектор для пола подвешен к потолку.
Пользователь взаимодействует с ВР при помощи «волшебной палочки» (wand) — трехмерной мыши с тремя кнопками, реагирующей и на силу нажатия, а также шлема с сенсором, отслеживающим движения головы (шесть степеней свободы); еще один сенсор следит за положением волшебной палочки при помощи магнитной системы2. Имеется и поддержка звука; звуковой сервер сделан на рабочей станции Indy и управляет миди-интерфейсом и синтезатором; динамики стоят в углах «пещеры». В совокупности это оборудование и обеспечивает вожделенное «погружение» (immersion). Дать некоторое представление о «вкусе устриц» поможет рис. 2.
Существует, оказывается, и такая общность людей, как пользователи CAVE, — по необходимости очень немногочисленная; даже организованных любителей «Спектрума» наверняка побольше наберется. Похоже, Пол Райлих (www.brighton.ncsa.uiuc.edu/~prajlich ) — один из неформальных лидеров этого сообщества; по крайней мере, он реализовал (в свободное от научной визуализации время) поистине суперпроект — портировал на CAVE игру Quake 2 (рис. 3).
Главный недостаток CAVE и ее аналогов, пожалуй, даже не необходимость постоянного инженерного обслуживания (такое «железо» весьма чувствительно к прикосновениям, см. инструкцию на www.evl.uic.edu/pape/CAVE/prog/CAVEGuide.html , а невозможность коллективного использования. В последние годы EVL активно работает над распределенными системами, позволяющими сочетать «погружение» с сетевым доступом к данным и результатам визуализации. Для интересующихся: ключевые слова для поиска — CAVE6D и, главное, TIDE (Tele-Immersive Data Explorer).
В отличие от устриц, ВР-пещеры сохраняют свежесть годами. Однако у совсем новых, только что выловленных экземпляров заметны следы не только технологической, но и концептуальной эволюции. Хотя речь идет о системах, предназначенных не только (и не столько) для разглядывания данных, все же стоит посвятить пару абзацев одной из них.
Система blue-c [2] (blue-c.ethz.ch) cоздана в этом году в Швейцарском федеральном институте технологий ETH3. Целью проекта было радикальное расширение возможностей телеприсутствия — достаточного, например, для виртуального консилиума врачей в процессе постановки диагноза4. Одной из важнейших задач становится интерактивная визуализация самого пользователя.
Пещера blue-c способна в реальном времени строить 3D-видеомодель находящегося в ней человека, помещая ее в виртуальный мир (рис. 4). Камеры, расположенные вне пещеры, создают серию видеопотоков с обычным, «плоским» изображением пользователя с разных точек обзора, а вычислительное ядро (Linux-кластер) на лету интегрирует эти потоки в трехмерную модель. Именно эта последняя задача была самой сложной при разработке системы. Усовершенствования (по сравнению с CAVE) в «железе» нацелены прежде всего на ее решение. Например, в качестве стен использованы стеклянные проекционные экраны, содержащие внутренний слой из жидких кристаллов, электрически переключаемый между прозрачным и непрозрачным состоянием. Это нужно для того, чтобы камеры, снимающие пользователя, могли видеть сквозь стены: видеосъемка производится в короткие интервалы смены кадров виртуального мира на стенах пещеры. Математические алгоритмы восстановления и отображения трехмерного аватара используют модные сейчас точечные модели (point-based models) трехмерных объектов, представляющие любой предмет в виде плотного облака разноцветных точек. Простота и скорость работы с такими моделями стали ключом к достижению «реального времени» обновления 3D-облика пользователя. «Реальность», впрочем, пока довольно скромная — 3D-модель весьма посредственного качества обновляется 5–9 раз в секунду. Для отображения с такой частотой полученного трехмерного видеопотока на удаленном компьютере требуется пропускная способность сети 2,5–12,5 Мбит/с, в зависимости от сложности динамики сцены (передаются только обновления изменившихся участков трехмерной модели).
Итак, теперь на данные принято смотреть через вот такие оригинальные приспособления. Эти технологии имеют массу коммерческих (к примеру, дистанционная демонстрация одежды) или общекультурных приложений (в разговорах на последнем «Графиконе» я узнал, что у «компьютерных консерваторов» памятников деревянной архитектуры из японского университета Аидзу [Aizu] в распоряжении всего одна «пещера», тогда как у создателей виртуального Пекина из Сингапурского института высокопроизводительных вычислений — целых четыре), принципиально недоступных для нынешней парадигмы визуализации (взгляд на нечто через окошко монитора). Пещера — это не очередное высокотехнологичное звено в цепи, идущей от графопостроителя на бумажной ленте к монитору современной графической станции, управляемой трехмерной мышью. Пещера — первый шаг в мир так называемых пост-WIMP-взаимодействий с «вычисляемой реальностью» (WIMP расшифровывается как Windows, Icon, Menu, Pointing). Если говорить о визуализации данных — последует ли за этим новое качество результатов, новый уровень понимания процессов, новые откровения? Гм-гм… произошло ли такое при переходе от «ничего» к WIMP? Так или иначе, успех в конечном счете определяется соображениями исследователя о том, на что и как надо смотреть. Отвлечемся теперь от физических средств отображения и познакомимся с некоторыми идеями представления данных.
1 Cave — пещера (англ.).
2 В новых версиях и вариациях CAVE используется до 6–8 сенсоров.
3 Eidgenцssische Technische Hochschule, Zьrich.
4 О системах с аналогичными задачами см. www.advanced.org/tele-immersion/publications.html ,
www.bs.hhi.de/SPAG/SPAG-publications.htm.
Метафоры, гиперболы, колеса, параллели
Одна из самых популярных идей визуализации — организовать данные в интуитивно понятные пространственные структуры, знакомые по повседневной жизни. Выбор структуры часто называют метафорой представления данных. Таких метафор совсем немного, и придумать новые — и практически применимые! — очень трудно. Дерево, здание, город — что еще? Читатели киберпанка (в частности, классической «мостовой трилогии» Уильяма Гибсона) многое знают о таких метафорах — вспомним гигантские массивы виртуальных городов и лед, иногда смертельный (биологически), как символ антихакерской защиты.
Авторы [3] реализовали наиболее употребительные метафоры в качестве средств трехмерной навигации виртуальных миров (обычными средствами, без погружения) в своей системе CyberNet (www.eurecom.fr/~abel/cybernet ). Этот проект типичен в том смысле, что реализация его прагматической цели — помочь ориентироваться в сетевых окружениях — сразу наталкивается на очень неформальное, философское, если угодно, препятствие: как подбирать подходящие метафоры для виртуальных миров в зависимости от их содержимого и от устремлений пользователя. Это труднейшая задача, и один из разумных подходов состоит в том, чтобы снабдить пользователя средствами выбора метафоры, а дальше пусть он (она) действует по обстановке. CyberNet, точнее его «маг метафор» (metaphor wizard), позволяет представить виртуальный мир как здание, город, ландшафт или «коническое дерево» (рис. 5). Например, разработчики сочли разумным отобразить сетевой трафик в виде ландшафта на прямоугольном участке поверхности, где интенсивность потоков данных на различных серверах представлена параллельными линиями трехмерных цветных столбиков (положение, высота и шкала цвета — информативные параметры). Изобретательность для применения такой метафоры нужна, признаем, довольно скромная — но главное, что структура получается простая, наглядная и удобная.
Напротив, придумать что-то новое и по-настоящему удобное для обозрения огромных деревьев файловых систем совсем не просто. Для таких иерархических структур визуальная метафора дерева сегодня вне конкуренции — хотя она и не единственно возможная. Чтобы довести наглядность визуализации больших деревьев до предела выразительности, авторам недавнего хита этого жанра — файл-менеджера Innolab 3D (см. «КТ» #511) — пришлось в буквальном смысле изобрести колесо (рис. 6).
Впрочем, картинки такого рода в задачах отображения больших графов появились гораздо раньше. Нельзя не упомянуть об одной из самых ярких идей — визуализации больших графов с использованием пространства Лобачевского5. Идея принадлежит Тамаре Мюнцнер (Tamara Munzner,
www.graphics.stanford.edu/papers/munzner_thesis ) и воплощена в нескольких продуктах — HyperViewer, Walrus и др. (см. www.caida.org/tools/visualization/walrus ). Эта технология основана на том, что деревья, узлы которых распределены в пространстве равномерно в смысле метрики Лобачевского, в обычной проекции изображаются в стилистике «рыбьего глаза». На рис. 7 — примеры изображения сетей программой Walrus. Графы компьютерных сетей, в отличие от файловой системы, не обязаны быть деревьями, что усложняет задачу — представьте, какая каша появится на экране при попытке нарисовать в трехмерье граф с миллионом узлов и соответствующим количеством связей. Здесь спасает то, что существующие сети, как правило, почти исчерпываются деревьями — то есть связей, не укладывающихся в «деревянную» структуру, совсем немного по сравнению с укладывающимися. Проще говоря, лишь малая часть узлов связаны друг с другом не через узел более высокого ранга, а напрямую. Однако даже эти связи при таком отображении можно наглядно отделить от других различными способами — не говоря уж о массе возможностей цветовой разметки ребер и вершин графа, что позволяет отображать и интенсивность трафика, и ряд других параметров.
Тем, кого интересуют подробности, особенно математические, рекомендую диссертацию Мюнцнер и приведенные там ссылки. Эта технология — один из немногочисленных пока примеров применения нетрадиционной для компьютерных наук математики в самой традиционной для этих наук задаче.
Тему визуализации сетей закончим упоминанием о социальных сетях, определяемых всевозможными взаимодействиями организаций и людей в обществе, от промышленной конкуренции до соседской дружбы. Эта исключительно популярная сейчас тема (например, многих интересует, как выявлять террористические сети по их паттернам поведения в сетях связи) дает отличный материал для визуализации, о которой исследователи думали начиная с 1930-х годов (см. замечательный обзор Линтона Фримена на zeeb.library.cmu.edu:7850/JoSS/article.html). Еще в начале 1970-х, когда компьютерная визуализация была полностью ориентирована на бумагу, специалисты умели создавать в высшей степени наглядные (и очень схожие с нынешними стереотипами) образы — например, рис. 8 показывает трехмерную карту социальных связей 450 жителей Канберры [6].
Рис. 9–11 иллюстрируют детальный анализ дружеских отношений в одном из австралийских колледжей. Были опрошены все 217 студентов, каждый назвал своих друзей и оценил силу дружественной связи. Затем был проведен так называемый анализ соответствия (correspondence analysis) — стандартная математическая процедура, группирующая опрошенных как точки в трехмерном пространстве по некоему усредненному коэффициенту близости. Общая картина показана на рис. 9. Но если покрутить картинку в пространстве, обнаруживается структура из четырех «крыльев» (рис. 10), визуально тяготеющих к обособлению от «ядра». Как выяснилось [4], во всей структуре существует девятнадцать групп с особенно тесными внутренними связями — и члены четырех из них оказались связующими, опорными звеньями каждого из четырех крыльев. На рис. 10 и 11 эти студенты обозначены золотым («религиозная группа»), серебряным («поклонники стиля грандж»), темно-синим («математики») и светло-голубым («женщины») цветами. За деталями отсылаю к первоисточникам. Вопрос же о том, хорошо или плохо, когда так дотошно изучается структура частных предпочтений и взглядов студентов, выходит далеко за рамки этого материала.
Классифицировать методы визуализации — задача для той гипотетической супермонографии, о которой упоминалось в самом начале. А в короткой статье вполне допустимо объединить совершенно разнородные технологии. Что я и делаю, завершая сей краткий экскурс рассказом об одном из самых эффективных и популярных методов «очевидизации» зависимостей в многомерных пространствах. Речь идет о методе параллельных координат. Его идея крайне проста. Предположим, интересующие нас объекты — марки автомобилей, и они изображаются точками в многомерном пространстве, где координаты — вес, расход топлива, количество цилиндров, год выпуска и др. В этом случае строятся несколько вертикальных параллельных осей на равном расстоянии друг от друга, пересекающих одну и ту же горизонтальную ось координат. Для каждого объекта отмечаем на осях удельный расход топлива, количество цилиндров и т. д. Получаем набор линий, который даже без дополнительной обработки может быть очень информативен, особенно если объектов не слишком много — в этом случае можно, если повезет, увидеть кластеры линий, указывающие на связь между различными параметрами объектов. Например, на рис. 12 можно усмотреть, что самые экономичные автомобили, как правило, мало весят. Не бог весть какой неожиданный вывод. Однако есть куда более изощренные (если не сказать иезуитские) способы применения этого подхода. Эдвард Вегман (Edward Wegman, см. его заметки по методам статистической визуализации на www.galaxy.gmu.edu/stats) применил его к анализу риска, которому подвергается банк, дающий займы тем или иным категориям граждан. По такой же технологии были построены тысячи ломаных (в качестве координат использовались возраст, клиентский стаж в данном банке, род занятий, некоторые параметры семейного статуса), а кластеры выделялись при помощи раскраски каждой из ломаных в один из цветов на светофорной (интуитивно понятной банкирам) цветовой шкале: от красного до зеленого (рис. 13). Красным обозначались траектории, соответствующие клиентам, которые залезали в слишком большие долги перед банком. Наложение траекторий теперь сопровождалось наложением цветов. Из однородной массы сразу выделились кластеры красных линий — они однозначно коррелировали с возрастом: опаснее всего банку было связываться с молодыми клиентами. Однако после применения более сложных методов визуализации, уже с выходом в многомерное пространство, выяснилось, что фактор риска — не просто возраст, а некий набор комбинаций возраста, рода занятий, семейного положения и других параметров. И вот теперь банк уже мог отказывать потенциально ненадежным клиентам, не боясь быть обвиненным в дискриминации по возрасту.
Заключение
Итак, мы познакомились с некоторыми идеями и технологиями визуализации данных. Незатронутыми остались целые пласты — например, визуализация всевозможных контекстов, корреляций в массивах текстов и т. п.6 Очень интересные системы научной визуализации описаны, скажем, здесь (www.cg.tuwien.ac.at/research/vis/dynsys/NDimViewer) и здесь (www.research.ibm.com/dx/srcDownload/index.html), причем последний линк ведет к открытым исходникам. Вообще, мне кажется, что в материале вполне достаточно ссылок, чтобы читатель, заинтересовавшийся одной из тем, мог быстро сделать первые шаги в нужном направлении.
Ответ на вопрос из заголовка теперь очевиден. На экране мы — не всегда, конечно, но чаще всего! — мечтаем увидеть готовый ответ на трудные вопросы. Это понятное, безобидное и очень сильное желание сейчас становится одним из серьезных факторов развития процесса куда более важного, чем прогресс визуализации как таковой, и даже чем ожидаемое за счет этого ускорение познания природы. Я говорю о процессе совершенствования и повсеместного проникновения в повседневную жизнь систем виртуальной реальности. Вряд ли кто-нибудь способен предсказать, какую роль сыграет ВР в формировании «дивного нового мира» — но без нее этот мир представить уже невозможно.
5 В зарубежной литературе оно обычно называется гиперболическим пространством.
6 К примеру, если применить эти методы к данной статье, можно будет обнаружить сильное влияние на нее прошлогодней статьи Филиппа Болла по научной визуализации в Nature [5].
Литература
[1] C. Cruz-Neira, D.J. Sandin, and T.A. DeFanti, «Surround-Screen Projection-Based Virtual Reality: The Design and Implementation of the CAVE». Proc. ACM Siggraph 93, Ann. Conf. Series, ACM Press, New York, 1993, pp. 135-142.
[2] Markus Gross, Stephan Wьrmlin, et al, «blue-c: a Spatially Immersive Display and 3D Video Portal for Telepresence».
[3] C. Russo Dos Santos, P. Gros, P. Abel, D. Loisel, N. Trichaud, J. P. Paris, «Metaphor-Aware 3D Navigation».
[4] C.M. Webster, «A comparison of observational and cognitive measures». Quantitative Anthropology, 4, 1994, pp. 313-328.
[5] Philip Ball, «Picture this». Nature, vol. 417, 4 July 2002.
[6] Brian Hayes, «Graph theory in practice: Part I». American Scientist, Volume 88, Number 1, Jan-Feb, 2000.
