77300

Некоторые методы многомерной визуализации

Научная статья

Информатика, кибернетика и программирование

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

Русский

2015-02-02

835.5 KB

4 чел.

Некоторые методы многомерной визуализации

П. А. Васёв, Д. С. Перевалов

2000 г.

Содержание


1.
Введение

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

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

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

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

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

Заметим, что часто необходимы и невизуальное представления множества. Например, когда M - многообразие, являющееся фазовой траекторией движения механической системы, то может быть интересно, какое это многообразие (его размерность и топологический тип), гладкая ли его поверхность, имеет ли множество симметрию, выпуклость и т.д. Если точно известно, какая требуется невизуальная характеристика, то зачастую существует готовый алгоритм ее расчета. Но для того, чтобы понять, какую информацию нужно извлечь, неплохо знать, как это множество “выглядит”. То есть методы визуального представления требуются, во-первых, для решения задач интерпретации, а во-вторых, для выяснения особенностей исследуемого объекта и понимания, какие нужны невизуальные средства его анализа.


2. Визуальное представление точек многомерной сферы

Здесь мы рассмотрим случай, когда множество M является подмножеством единичной сферы в n-мерном пространстве. Такие множества возникают при изучении задачи о контактных числах и задачи Таммса (также известной как задача о диктаторах [2]. Суть этих задач в следующем: как расположить m точек на единичной сфере в n-мерном пространстве, чтобы точки лежали возможно дальше друг от друга, то есть минимум попарных расстояний d между точками было максимальным (задача Таммса)? Аналогично, сколько можно расположить точек на сфере, чтобы минимальное расстояние между ними не было меньше некоторого d (общий вариант задачи о контактных числах)?

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

Точное решение задачи оптимального размещения известно лишь в частных случаях. В частности, неизвестно, можно ли расположить 25 точек на сфере в 4-х мерном пространстве так, чтобы угловое расстояние между любой парой точек не было меньше 60 градусов. (Аналогичный вопрос не решен для 5-мерной сферы и 41 точки и т. д.). Это может быть связано с тем, что математик не обладает геометрической интуицией при работе с точками на многомерной сфере.

Мы рассмотрим два метода для визуального представления точечных множеств многомерной сферы. Это требуется для анализа симметрии множества, нахождения подобных множеств, контроля работы итерационных алгоритмов построения оптимальных размещений. (Библиотека лучших размещений, найденных на сегодняшний день, находится по адресу http://www.research.com/~njas/packings.)

2.1 Метод проекций

Метод заключается в понижении размерности множества M из n-мерного пространства путем проецирования его на двумерное подпространство P и отображения полученных точек на плоскость экрана.

Пусть M – точечное множество. Каждая точка есть вектор - n-ка вещественных чисел x = (x1, x2, x3, ..., xn). Например, воспользуемся перспективной проекцией. Сначала спроецируем n-мерный вектор в (n-1)-пространство по формуле

x’i = xi * 1 / ( 1 + xn / f)           i=1..n-1,

где f = const – фокальное расстояние. В результате отображения получим вектор x’ размерности на 1 ниже, чем исходный.

Применим указанную операцию к x’.

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

Результат применения описанного метода проекций для вершин 5-мерного куба изображен на рис. 3.

К сожалению, для произвольного M из полученного представления трудно извлечь полезную информацию. Соединим теперь “близкие” точки M отрезками. Условие для соединения точек x и y может быть различным. Например, будем соединять точки, расстояние между которыми меньше заданной константы и/или только те точки, cкалярное произведение которых попадает в заданный интервал. Наконец, мы можем обладать явным указанием, какие точки следует соединить.

Результат применения такой операции к 4- и 5-мерным кубам изображены на рис. 1 и рис. 4 соответственно. Отметим, что этой меры тоже может быть недостаточно - структура многомерного объекта все равно не ясна исследователю.

Попробуем изобразить M в динамике – с течением времени будем изменять параметры визуализации, генерируя кадры анимационного фильма. Например, используем аффинные преобразования - поворот, перенос и масштабирование. Поворот определяется набором из (n-1) коэффициентов–углов; перенос – n-мерным вектором; масштаб – одним коэффициентом. Плавно изменяя эти параметры, мы получим трансформацию визуального образа, которая, вероятно, позволит человеку лучше понять геометрическое устройство множества.

Пример вращения 5-мерного куба показан на рис. 5.

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

Заметим, что психология человеческого восприятия устроена так, что по плоскому изображению оно пытается реконструировать видимый плоский объект до 3-х мерного образа (тем более, когда изображение динамическое). Когда человек видит образ, полученный методом проекций, его сознание автоматически пытается реконструировать изображение в 3-х мерный объект. Но ведь это изображение многомерного объекта! Геометрическая интуиция отказывается принять постоянство воспринимаемого объекта, так как изображение на экране трансформируется по законам, отличным от законов изменения изображений жестких трехмерных тел. Поэтому метод проекций недостаточен для изучения многомерных структур, хотя и является первичным.

2.2 Метод скалярных гистограмм

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

Сопоставим множеству M функцию f, определенную на отрезке [-1,1], по правилу: значение f(t) для t из [-1,1] равно количеству пар точек множества M, скалярное произведение между которыми равно t. Например, если M состоит из одной точки x с единичной сферы, то имеется всего одна пара точек: (x, x). Скалярное произведение x с x равно 1, поэтому f(1)=1 и  f  равна 0  в точках полуинтервала [-1,1). Если M состоит из вершин куба, вписанного в единичную сферу в трехмерном пространстве, то, как нетрудно убедиться, соответствующая f будет отлична от нуля в точках -1, -1/3, 1/3, 1 и f(-1)=f(1)=8,

f(-1/3)=f(1/3)=24, см. рис. 20.

Заметим, что область определения f - конечное множество точек и сумма значений f равна квадрату мощности множества M; важно, что функция не меняется при поворотах множества относительно центра координат.

Построенную функцию f назовем скалярной гистограммой множества M. График этой функции есть визуальное представление множества, позволяющее выяснить, как распределены точки, какова степень их взаимной близости. Например, если f(1) равна мощности M и равна нулю в точках [a,1) для -1<a<1, это значит, что угловое расстояние между любой парой различных точек M не меньше arccos(a). Это следует из того, что для двух точек единичной сферы с центром в начале координат их скалярное произведение есть косинус угла между ними.

На рис. 21 изображена скалярная гистограмма лучшего на сегодняшний день размещения 25 точек на сфере в 4-х мерном пространстве (множество взято из упомянутой выше библиотеки размещений). Угловое расстояние между его точками не меньше 59.0029024 градусов, что приблизительно равно arccos 0.537 (на рис. значение выводится с округлением).

Рис. 22 показывает гистограмму для 595 точек, полученных проекцией случайного набора точек на поверхности 10-мерного куба на сферу в 10-мерном пространстве. Хорошо видна статистическая закономерность расположения точек.

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

Метод позволяет работать с множествами произвольной размерности без усложнения образа.

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


3. Множества, имеющие выпуклые сечения вдоль некоторой оси

В этом параграфе мы рассмотрим ситуацию, когда множество M является многогранником в n-мерном пространстве, заданным своими вершинами, причем имеется ось w такая, что сечения M перпендикулярно этой оси есть выпуклые многогранники (в n-1-мерном пространстве).

Сначала остановимся на случае n = 4, то есть когда M - четырехмерный многогранник, сечения которого вдоль оси w есть выпуклые трехмерные тела.

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

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

3.1 Метод осевого искажения с оператором тени

Основой метода служит известный факт: по плоской тени, отбрасываемой при вращении трехмерным выпуклым многогранником, человек мысленно восстанавливает вид этого тела.

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

Тело T и есть результат применения метода осевого искажения с оператором тени  к множеству M.

Если вращать T (“менять положение внешней камеры наблюдения”), то в силу выпуклости сечений человек полностью поймет его структуру. Кроме того, можно изменять положение плоскости, на которую проецируется тень каждого сечения исходного множества M. Другими словами, “менять положение внутренней камеры”, преобразующей трехмерные сечения множества M в двумерные изображения, из которых строится тело T.

Используя упомянутый факт о свойствах восприятия, мы получаем, что путем внутреннего вращения (то есть при вращении внутренней камеры) можно добиться, чтобы человек восстановил трехмерную структуру каждого отдельного сечения M. С учетом того, что при внешнем вращении (при движении внешней камеры) воспринимается структура всех сечений, получаем окончательный вывод: если тело T вращается с использованием внешних и внутренних поворотов, то человек восстанавливает трехмерный вид всех сечений M, которые он воспринимает одновременно. Значит, человек воспринимает 4-х мерную структуру множества M.

Для иллюстрации рассмотрим процесс деформации трехмерного куба   [-1,1]x[-1,1]x[-1,1] в пирамиду, при котором точки верхнего основания куба равномерно сходятся в точку (0,0,1). Приняв отрезок времени деформации за четвертую ось, получим четырехмерное тело, сечения которого вдоль этой оси есть куб, усеченная пирамида и пирамида. Применим описанный метод к этому множеству. Рис. 9 и 10 показывают различные виды этого множества при разных углах поворота внешней и внутренней камер.

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

Метод осевого искажения с оператором тени работает с 4-х мерными множествами. Для преодоления этого ограничения был разработан метод, объединяющий скалярные гистограммы и метод искажения.

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

Пусть теперь M - многогранник размерности n с выпуклыми n-1-мерными сечениями. Если n > 4, то метод, описанный в предыдущем пункте, неприменим, так как восприятие человека не приспособлено к восстановлению многомерного тела по вращению его двумерной тени. Тем не менее заманчиво получить стопку двумерных представлений сечений множества M и далее построить тело T как в методе осевого искажения с тенью.

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

Опишем построение скалярной гистограммы сечения S множества M. Предполагаем, что начало координат расположено внутри S и S лежит внутри единичного шара с центром в начале координат. Множество S есть точечная аппроксимация некоторой многомерной поверхности, поэтому количество точек априори велико. Рассчитаем скалярную гистограмму f для S методом 2.2 и определим функцию g как f, деленную на квадрат мощности S. Такая нормированная скалярная гистограмма g есть искомое представление. Например, скалярная гистограмма для трехмерной сферы - константа.

На рис. 6 и 7 показаны гистограммы поверхностей куба и пирамиды соответственно. Обратите внимание на связь непрерывной гистограммы куба и дискретной, изображенной на рис. 20.

Рис. 8 иллюстрирует применение метода искажения с оператором гистограмм для рассмотренного в п. 3.2 процесса трансформации куба в пирамиду.

Гистограмма дает описание “выгнутости” множества. По виду гистограммы обычно трудно определить, какое множество она представляет. Однако приведенный метод позволяет работать с множествами произвольной размерности, он позволяет выяснять непрерывность изменений сечений вдоль фиксированной оси. Есть гипотеза, что гистограмма однозначно определяет регулярные в некотором смысле многогранники.

Мы рассмотрели методы визуализации дискретных и непрерывных множеств, которые обладают определенной выпуклостью.

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


4. Визуализация множества QUADRO

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

Несколько таких множеств  было любезно предоставлено А. Г. Ивановым. Мы приведем примеры обработки одного из множеств, которое будем называть QUADRO.

1. Было обнаружено, что сечения множества QUADRO вдоль 4-й оси являются выпуклыми множествами. Это позволило получить его представление методом осевого искажения с тенью (см. пункт 3.1), изображенное на рис. 16.

2. Кроме того, был модифицирован метод проекций: при выводе 3-х мерных проекций точек P из QUADRO мы снабдили каждую выводимую точку цветом, зависящим от 4-й координаты P – это так называемый метод раскраски. См. результат применения метода раскраски на рис. 17.

3. Используя априорную информацию о том, что при построении множества координаты точек (x, y, z, w) естественным образом группировались в пары (x, y) и (z, w), было разработано средство “2x2” представления ортогональной двумерной проекции (x,y) множества QUADRO с возможностью вывода сечения (z, w) для произвольной точки проекции (x, y). Полученное представление см. на рис. 18.

4. Наконец, мы применили метод раскраски для отображения цветом мощности сечений (z, w) множества QUADRO в “2x2” (см. рис. 19).

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


5. Визуализация функций комплексного переменного

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

Основная идея состоит в передаче цветом информации о значении функции в точке. Мы “раскрашиваем” область определения однозначной функции f в зависимости от значений f(z). В конкретной точке z цвет определяется реальной частью f(z), мнимой частью, аргументом или модулем. Предъявив несколько различных представлений функции, мы максимально дадим информацию о её поведении. На рис. 11 показана “раскраска” тождественного отображения f(z) = z. Реальная и мнимая части передаются градацией цвета красный-черный-золотой. Положительные значения соответствуют золотому цвету, отрицательные – красному. Модуль передаётся градацией черный-красный. Абсолютно чёрному цвету соответствует |f(z)|=0. Цветопередача аргумента реализуется переходом золотой (0) – белый (+) – синий (-).

Имея некоторый опыт, пользователь по данным представлениям может проанализировать функцию, а в простых случаях даже сказать, что это за функция. Смотрите, например, набор представлений функции f(z) = ln(z) на рис. 13.


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

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

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

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

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

Мы уверены, что работа окажется полезной другим разработчикам систем многомерной визуализации.


7. Литература

1. В. Л. Авербух, А. И. Зенков, Т. Р. Исмагилов и др. Разработка    специализированных систем научной визуализации, в сб. “Алгоритмы и средства параллельных вычислений”, вып. 4, Ек-рг: ИММ УрО РАН, 2000 г.

2. Conway J.H., Sloane N.J.A. Sphere Packings, Lattices and Groups (Second Edition) Springer-VerLag, NY, 1993, 679 pp.

3. Visualization in Scientific Computing, Special Issue, ACM SIGRAPH Computer Graphics, V. 21, N 6, November 1987.

4. Steve Hollasch, Four-space visualization of 4D Objects, http://www.research.microsoft.com/~hollasch/thesis/default.html

5. А. Г. Иванов, В. П. Краснов, С. И. Кумков. Расчет констант скоростей элементарных реакций процесса динамического кинетического расщепления, готовится к печати.









                                   

Рис. 20

Скалярная гистограмма вершин

3-х мерного-куба

Рис. 21

Скалярная гистограмма 25 точек оптимального размещения на сфере в 4-х мерном пространстве

Рис. 22

Скалярная гистограмма 595 точек на сфере

в 10-мерном пространстве

4


 

А также другие работы, которые могут Вас заинтересовать

13371. Дослідження автоматичної системи регулювання температури 371.5 KB
  Лабораторна робота №8 на тему: Дослідження автоматичної системи регулювання температури 1.Мета роботи 1. Дослідити систему автоматичного регулювання АСР температури та визначити динамічні характеристики обєкта керування. 2. Теоретичні відомості 2....
13372. Створення тестів в MS Excel 242 KB
  Автори: Бондар Н.П. Глушак О.М. Дисципліна Інформаційні технології та ТЗН ЛАБОРАТОРНА РОБОТА №18. Тема: Створення тестів в MS Excel. Мета: Формувати практичні вміння та навички роботи розроблювати дидактичні матеріали з автоматичним визначенням правильно...
13373. Построение фигур в CorelDRAW 415.68 KB
  Лабораторная работа N 1 Построение фигур в CorelDRAW Объектноориентированный подход в редакторе CorelDRAW CorelDRAW представляет собой интегрированный объектноориентированный пакет программ для работы с иллюстративной графикой. Под словами интегрированный пакет следует...
13374. Построение линий в CorelDRAW 355.53 KB
  Лабораторная работа N 2 Построение линий в CorelDRAW Для представления различных классов линий в CorelDRAW предусмотрено несколько классов объектов. Объекты объединяются в один класс по признакам общей структуры и поведения то есть реакции на действия с ними. При этом действ...
13375. Налаштування роботи в мережі Internet 43.5 KB
  исципліна Інформаційні технології та ТЗН ЛАБОРАТОРНА РОБОТА №1 19. Тема: Налаштування роботи в мережі Internet. Мета: Сформувати практичні вміння та навички роботи та налаштування різних браузерів. Основні поняття: ...
13376. Поняття компютерної мережі та їх класифікація 6.27 MB
  исципліна Інформаційні технології та ТЗН Теоретичний матеріал. Поняття комп’ютерної мережі та їх класифікація. Під комп’ютерною мережею розуміють сукупність взаємозалежних через канали передачі даних компютерів що забезпечують користувачів засоб...
13377. Використання пошукових систем та тематичних каталогів при роботі з навчальною інформацією у мережі Internet 50 KB
  Автори: Бондар Н.П. Глушак О.М. Дисципліна Інформаційні технології та ТЗН ЛАБОРАТОРНА РОБОТА №3 21. Тема: Використання пошукових систем та тематичних каталогів при роботі з навчальною інформацією у мережі Internet. Мета: Сформувати практичні вміння та навич
13378. Пошук інформації в Інтернет 780 KB
  Автори: Бондар Н.П. Глушак О.М.Дисципліна Інформаційні технології та ТЗН Теоретичний матеріал. Пошук інформації в Інтернет. В Інтернет розміщено кілька мільярдів документів у вигляді вебсторінок. Для швидкого пошуку інформації у мережі використовуєт...
13379. Словники перекладачі енциклопедії електронні бібліотеки освітні ресурси 68.5 KB
  Тема: Словники перекладачі енциклопедії електронні бібліотеки освітні ресурси. Мета: Сформувати практичні вміння та навички роботи в мережі Internet. ...