ДонНТУ   Портал магистров

Реферат по теме выпускной работы

Содержание

Введение

Задачи визуализации объектов n-мерного пространства находят применение в системах управления технологическими процессами, в системах диагностики и распознавания образов, экспертных системах и системах принятия решений в технике, экономике и медицине, в лингвистике и психологии. В последнее время широкое распространение получили интерактивные системы принятия решений, в которых ответственное лицо принимает решение и оценивает их последствия на основе визуализированных данных[9].

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

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

1. Постановка проблемы

Проблема визуализации 3D-объектов, которые могут быть заданы различными способами, возникает во многих областях математики, физики, медицины [1]:

  1. Визуализация экспериментальных данных. Например, информации, собранной с различных датчиков, сенсорных сетей, результатов измерений, результатов имитационного моделирования.
  2. Визуализация функционального представления. Визуализация сложных трёхмерных объектов в математике, визуализация аналитически заданных поверхностей и т.п.
  3. Визуализация медицинских наборов данных. Одним из широко используемых методов диагностики является томография. Томографы, работающие на рентгеновском принципе (компьютерная томография, далее КТ) и на магнитно-резонансном принципе (далее МРТ) позволяют получить изображения множества сечений тела пациента вдоль какой-либо оси, которые дают много информации об особенностях его анатомии и физиологии. Методы визуализации позволяют реконструировать трехмерную структуру органов по множеству параллельных сечений. Визуализация всего набора данных в настоящее время реализована в программном обеспечении большинстве современных томографов, но задачи выделения трехмерных областей, визуализации области интереса, заданной набором контуров на срезах, визуализация области при радиологическом лечении пациентов, как правило, в этом программном обеспечении не реализованы.
  4. Визуализация экспериментальных и модельных данных, из других областей, таких как динамика жидкостей, геология, метеорология, молекулярный анализ.

Основная задача визуализации 3D-объектов формулируется следующим образом – необходимо найти оптимальную аппроксимацию для неизвестной поверхности так, чтобы минимизировать погрешность измерения, возникающую из-за ограничения по точности в измерительных приборах или из-за недостаточного качества поверхности физической модели.

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

2. Анализ литературы

Для визуализации объектов, имеющих большое число признаков в виде совокупности параметров, на плоскости существует множество методов[9].

В настоящее время существуют следующие классы визуализации данных: визуализация поверхности (surface rendering), объемная визуализация (volume rendering) и гибридная визуализация (hybrid rendering).

Алгоритмы визуализации поверхности (surface rendering) строят изображение поверхности в трехмерном пространстве (одним из представлений поверхности является уравнение , где — заданный уровень). Сначала исходная поверхность аппроксимируется полигонами, затем производится визуализация полигонов с помощью одной из графических библиотек[10].

Алгоритмы объемной визуализации (volume rendering) используются для представления полной картины с учетом всех окружающих объектов. Существует четыре типа алгоритмов объемной визуализации: испускание лучей, разложение на слои со сдвигающей деформацией, проектирование вокселей, отображение текстуры[11].

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

Основными алгоритмами, которые применяются при восстановлении поверхностей, являются:

  1. алгоритмы отбрасывания лучей [2];
  2. алгоритмы триангуляции [3];
  3. алгоритм марширующих кубов [4];

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

Алгоритмы триангуляции менее ресурсоёмки, при этом имеются быстрые даже в однопоточном варианте реализации. Одним из примеров такой реализации является алгоритм построения триангуляции Делоне, описанный в работе[5], который на персональном компьютере средней мощности (Core2Quad 2,83ГГц, 8Гб ОЗУ) позволяет выполнить триангуляцию поверхности из 100000 точек за 8 секунд.

Более ресурсоёмким и менее оптимизированным является алгоритм марширующих кубов [4], который, тем не менее, интересен для задач интерактивного и автоматического восстановления поверхностей объектов, представленных облаком точек, а также для построения выпуклых оболочек. Поэтому в работе будут рассматриваться пути повышения производительности именно данного алгоритма за счет распараллеливания.

3. Обзор метода триангуляции

На практике наиболее часто производится разбиение изображений на треугольники.

Это объясняется следующими причинами:

  1. треугольник является простейшим полигоном, вершины которого однозначно задают грань;
  2. любую область можно гарантировано разбить на треугольники;
  3. вычислительная сложность алгоритмов разбиения на треугольники существенно меньше, чем при использовании других полигонов;
  4. реализация процедур рендеринга наиболее проста для области, ограниченной треугольником;
  5. для треугольника легко определить три его ближайших соседа, имеющих с ним общие грани.

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

Итеративная бисекция основания

Рисунок 1 – Визуализация 3-х итераций бисекции основания треугольника алгоритма ROAM.
(анимация: 7 кадров, 5 циклов повторения, 146 килобайт)

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

Любая поверхность может быть аппроксимирована с необходимой точностью сеткой треугольников. Точность аппроксимации определяется количеством треугольников и способом их выбора. Для качественной визуализации объекта, находящегося вблизи точки наблюдения, требуется учесть во много раз больше треугольников, чем в ситуации, когда тот же объект расположен на удалении. Даже достаточно грубая сетка полезна на практике, так как методы сглаживания, применяемые в процессе отображения, могут значительно улучшить представление о кривизне поверхности[12].

4. Описание алгоритма

Согласно [4], алгоритм состоит из двух основных стадий. Первая стадия: построение неявной функции F: D->R, где D принадлежит R3 -окрестность поверхности. Функция F представляет собой оценку расстояния от любой точки из D до поверхности. Вторая стадия: триангуляция поверхности нулевого уровня функции F при помощи алгоритма марширующих кубов.

ля построения оценки расстояния мы, ассоциируем с каждой точкой набора {x1,…,xn} ориентированную касательную плоскость Tp(xi) , которую можно найти при помощи метода главных компонент, примененного к k ближайшим соседям точки x i. Вычисление функции расстояния осуществляется по формуле:

 

F(p) = (p-oi)ni ,                (1)

 

где oi – ближайший к p «центр» касательной плоскости (центроид k ближайших соседей), а ni– соотвестсвующая ему нормаль.

Алгоритм «Марширующие кубы», можно разбить на два этапа:

1. Разбиение области G пространства R3 на конечное множество ячеек, поиск ячеек пересекаемых искомой поверхностью.

2. Аппроксимация поверхности в найденных ячейках.

Две эти подзадачи являются независимыми. Рассмотрим их подробнее.

Первый этап.

Основные проблемы этого этапа заключается в следующем [4]:

1. Разбить область G на ячейки.

2. Выбрать ячейки, которые пересекаются с искомой поверхностью.

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

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

При большом размере ячейки некоторые части искомой поверхности не будут видны. Однако выбирать ячейки очень маленького размера не очень хорошо с точки зрения быстродействия. Поэтому размер ячейки надо выбирать не меньше допустимой погрешности построения искомой поверхности.

Форма ячейки в алгоритме «Марширующие кубы» - параллелепипед. Однако это не единственно возможный вариант. Форма ячейки определяет дальнейшую триангуляцию ячейки. Причем, если вершина ячейки находится вне объема ограниченного искомой поверхностью, то значение этого бита 0, иначе - 1. Тогда количество разных типов триангуляции будет 2N. Отсюда видно, что использовать в качестве ячейки, например, икосаэдр не оптимально.

Итак, допустим, что область G уже разбита на ячейки. Тогда главной проблемой становится поиск ячеек пересекаемых искомой поверхностью. Пусть С - множество ячеек, тогда Cv - множество ячеек пересекаемых поверхностью F(P)=v. Тогда можно считать, что поверхность пересекает ячейку, если существуют такие P1 и P2  - вершины ячейки, что:

   F(p1) <v< F(p2),                                      (2)

Это условие выполняется, когда выполняется:

   Mini F(pi) <v< Maxj F(pj),                                (3)

где pi и pj  – вершины ячейки.

Таким образом, проблема свелась к следующему: из множества ячеек C выбрать подмножество Cv ячеек, удовлетворяющих условию (3).

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

Необходимо определить, сколько способов триангуляции имеет параллелепипед. Пусть имеется 8-битовый индекс. Тогда сопоставим каждой вершине один бит в индексе. Причем, если вершина ячейки находится вне объема ограниченного искомой поверхностью, то значение этого бита 0, иначе - 1. Тогда количество разных типов триангуляции будет 28=256.

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

5. Применение распараллеливания

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

вычисление идентификаторов точек;

переупорядочение точек;

выделение вокселей сетки;

вычисление шаблонов ячеек;

генерация треугольников.

Так как эти задачи предполагают однотипные операции над большим количеством данных, то распараллелить их было бы достаточно хорошо, используя даже вычислительные системы, относящиеся к классу SIMD. К таким системам относятся современные графические ускорители [6]. Для наиболее универсального ускорения расчетов с использованием GPGPU предлагается вариант распараллеливания алгоритма с применением OpenCL, что позволит применять ускорители nVidia, AMD и Intel. Использование графических ускорителей при решении данной задачи аргументируется тем, что выполнение расчётов с использованием графического ядра дает хорошие результаты в алгоритмах, использующих параллельную обработку больших массивов данных. В нашем случае отношение числа арифметических инструкций, которые придется исполнять при построении поверхности, достаточно велико по отношению к числу обращений к памяти, что обычно даёт лучшие результаты при реализации с применением GPGPU вычислений.

Алгоритм должен содержать следующие шаги:

  1. Реализация ускоряющей структуры, для входного набора данных.
  2. Восстановление поля нормалей.
  3. Вычисление оценки расстояний.
  4. Нахождение поверхности нулевого уровня оценки расстояния (алгоритм «марширующих кубов»).

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

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

Хорошая реализация параллельного алгоритма поиска касательной приведена в работе [7]:

  1. Получить из глобальной памяти обрабатываемую точку.
  2. Определить целочисленные координаты вокселя (x,y,z).
  3. Выполнить выборку индексов точек вокселя (x,y,z) и его соседей.
  4. Скопировать точки с полученными индексами в локальную память и отсортировать точки по возрастанию расстояния.
  5. Выбрать из локальной памяти координаты ближайших точек.
  6. Вычислить центроид и поместить его в выходной буфер.
  7. Вычислить матрицу ковариации для выбранных точек, найти минимальное собственное число и поместить соответствующий ему собственный вектор в выходной буфер.

Для вычисления оценки расстояния предлагается помещать центроиды в ускоряющую структуру, что позволяет использовать следующую параллельную схему:

  • Получить из глобальной памяти обрабатываемую точку.
  • Определить целочисленные координаты вокселя (x,y,z).
  • Найти ближайший центроид и соответствующую ему нормаль.
  • Вычислить оценку расстояния.

    • Алгоритм марширующих кубов, распараллеленный с использованием OpenCL, состоит из следующих шагов: вычисление шаблонов ячеек; вычисление адресов вершинного буфера; генерация треугольников. Такая техника позволяет получить выходные данные различной длины от каждого потока в один буфер параллельно.

    Следует отметить, что, несмотря на свою популярность и широкое применение, алгоритм марширующих кубов имеет существенный недостаток: на достаточно простых участках поверхности он выполняет слишком большое количество разделений. Например, на поверхности, которая может быть аппроксимирована с помощью 440 полигонов, классический алгоритм может сгенерировать порядка 67000 [8]. Это подчеркивает выигрыш в производительности от распараллеливания, но также говорит о необходимости улучшения базового алгоритма.

    Заключение

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

    Список источников

    1. Сравнительный анализ методов интерактивной триангуляции сеточных функций/ Интернет-ресурс. - Режим доступа: www/URL:http://cgm.computergraphics.ru/content/view/63#_.
    2. Volume ray casting / Интернет-ресурс. – Режим доступа: www/URL: http://en.wikipedia.org/wiki/Volume_ray_casting
    3. А. В. Скворцов Триангуляция Делоне и её применение. – Томск: Изд-во Томского ун-та, 2002. – 128с.
    4. Lorensen, W. E., And Cline, H. E. 1987. Marching cubes: A highresolution 3d surface construction algorithm. In Proceedings of SIG-GRAPH’87, 163–169.
    5. V. Domiter, B. Zalik Sweep-line algorithm for constrained Delaunay triangulation / Int. Journal of Geographical Information Science, Vol. 22, No. 4, April 2008. – P. 449-462.
    6. NVIDIA Corporation. NVIDIA CUDA Compute Uni?ed Device Architecture Programming Guide. Version 3.2.2010.
    7. GPU-алгоритм восстановления поверхности из облака точек/Интернет-ресурс.-URL:http://nano.msu.ru/files/conferences/GPU-2010-05/abstracts.pdf
    8. S. Schaefer, J. Warren, Dual Marching Cubes: Primal Contouring of Dual Grids / PG '04 Proceedings of the Computer Graphics and Applications, 12th Pacific Conference, 2004. – P.70-76.
    9. Научная библиотека диссертаций и авторефератов disserCat. Интернет-ресурс. - Режим доступа: www/URL: http://www.dissercat.com/content/metod-i-ustroistvo-vizualizatsii-prostranstvenno-raspredelennykh-obrazov-so-slozhnymi-topolo#ixzz2XKkRwcKZ.
    10. Визуализация данных поверхности. Интернет-ресурс. - Режим доступа: www/URL: http://docs.autodesk.com/CIV3D/2013/RUS/index.html?url=filesCTU/GUID-58270E7F-E5E0-4196-B194-4965255695F6.htm,topicNumber=CTUd30e10204.
    11. Гаврилов Н.И. Организация потоковых вычислений на GPU для интерактивной визуализации медицинских объемных данных. Интернет-ресурс. - Режим доступа: www/URL: http://escience.ifmo.ru/cms/content/Gavrilov.pdf
    12. Романюк Александр, Сторчак Александр Алгоритмы триангуляции Интернет-ресурс. - Режим доступа: www/URL:http://thalion.kiev.ua/idx.php/4/249/article
    13. Бугров Н.В., Голубев В.И., Дижевский А.Ю., Какауридзе Д.Г., Клименко А.С., Обоймов А.С., Фролов П.В. Обзор алгоритмов гибридной визуализации поверхности, вложенной в полупрозрачный объем Интернет-ресурс. - Режим доступа: www/URL: https://googledrive.com/host/0B8dxsp-U3fIiRnc5WEpmTThQRVU/MEDIAS2012-22-FrolovPV-Tomo3D.pdf