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

На правах рукописи

005002256

Дижевский Андрей Юрьевич

ВИЗУАЛИЗАЦИЯ ТРЕХМЕРНЫХ ОБЪЕКТОВ И ГЕОМЕТРИЧЕСКИЕ АСПЕКТЫ ВЫЯВЛЕНИЯ ОСОБЕННОСТЕЙ

05.01.01 — Инженерная геометрия и компьютерная графика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1.7 НОЯ 2011

Нижний Новгород — 2011

005002256

„НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ АРХИТЕ1ПУРН9-СШттШДИ1ШЕЕа11ЕЬ

Научный руководитель

доктор физико-математических наук, профессор Клименко Станислав Владимирович

Официальные оппоненты:

доктор технических наук, профессор Утробии Владимир Александрович, кандидат технических наук, старший научный сотрудник Алешин Владимир Петрович

Ведущая организация

Институт системного анализа Российской академии наук

Защита состоится « 29 » ноября 2011 г. в 15 час. 00 мин. на заседании диссертационного совета ДМ 212.162.09 при ФГБОУ ВПО «Нижегородский государственный архитектурно-строительный университет» по адресу: 603950, г. Нижний Новгород, ул. Ильинская, 65, корпус 5, ауд. 202.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Нижегородский государственный архитектурно-строительный университет». Автореферат разослан « 27 » октября 2011 года.

Ученый секретарь диссертационного совета

кандидат педагогических наук, доцент

Н.Д. Жилина

Общая характеристика работы Актуальность работы

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

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

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

библиотек. Самым ранним алгоритмом построения триангуляции поверхности является алгоритм «марширующие кубы», представленный Лоренсеном в 1987 году. Этот алгоритм производит разбиение области пространства, содержащей исходную поверхность, на кубические ячейки и аппроксимирует пересечение исходной поверхности и каждой кубической ячейки разбиения треугольниками. Дня случая синтеза изображения по плоским сечениям вершинами каждого куба будут по четыре точки на паре соседних сечений (на каждом сечении вершины образуют квадрат), расположенные как бы друг над другом.

Однако, в триангуляции, построенной алгоритмом «марширующие кубы» могут возникать разрывы или топологические несвязности на смежной грани (face ambiguity) и внутренние топологические неточности (internal ambiguity). В 1995 году Черняевым (Chernyaev) был предложен систематизированный метод решения топологических несвязностей алгоритма «марширующие кубы», а в 2003 году Льюинером (Lewiner) был программно реализован.

Существуют алгоритмы разбиения области пространства, в которой определена поверхность, на неправильные тетраэдры и аппроксимирующие исходную поверхность внутри каждого тетраэдра. Наиболее распространенными среди алгоритмов данного класса являются: алгоритм «марширующие тетраэдры 6» (МТ6), представленный Гуезеком (Gueziec) в 1995 году, и «марширующие тетраэдры 5» (МТ5), представленный Канейро (Carneiro) в 1996 году, основанные на разбиении области пространства (обычно куб) на кубы, а каждый куб в свою очередь разбивается на 6 или 5 тетраэдров соответственно. В 2000 году Скалой (V. Skala) был представлен алгоритм, использующий разбиение пространства на кубы с последующим построением тетраэдров на стыках соседних кубов.

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

текстуры.

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

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

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

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

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

опухолей, отложения солей кальция и маркеров определенной формы по снимкам томографа;

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

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

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

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

Для достижения поставленной цели требуется решение следующих задач:

х исследование алгоритмов триангуляции к разработка единого подхода к реализации алгоритмов визуализации поверхности, основанного на разбиении пространства на различные фигуры;

х создание новых алгоритмов триангуляции, оптимальных по параметру aspect ratio;

Л создание алгоритма визуализации поверхности, вложенной в объем и заданной неявной функцией;

А разработка алгоритмов по поиску трехмерных особенностей грибовидной и шаровидной формы в массиве данных на основе серии плоских сечений.

Методами исследования являются методы аналитической геометрии, дискретной математики, алгоритмы компьютерной геометрии и графики, методы

описания физической модели в оптике и методы объектно-ориентированного программирования.

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

Научная новизна исследования состоит в том, что:

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

А представлен новый алгоритм визуализации поверхности, вложенной в объем, где поверхность задана неявной функцией;

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

Положения, выносимые на защиту:

1. Общий подход к реализации алгоритмов триангуляции, основанных на разбиении пространства на ячейки (кубы, тетраэдры, призмы и др. фигуры), й его применение при реализации новых алгоритмов, основанных на разбиении пространства на октаэдры («марширующие октаэдры» и его модификация).

2. Алгоритм визуализации неявной поверхности, вложенной в попу прозрачный объем.

3. Алгоритм поиска особенностей шаровидной и грибовидной формы в массиве данных на основе серии плоских сечений.

Практическая значимость работы

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

Работа выполнена при поддержке Российского фонда фундаментальных исследований (гранты 09-07-00512, 11-07-00329). Алгоритмы реализованы в виде программ на языке С++, которые внедрены и используются при выполнении научно-исследовательских работ в Институте физико-технической информатики, на кафедре системной интеграции и менеджмента Московского физико-технического института (государственного университета) и в Институте прикладной физики Национальной Академии наук Беларуси, о чем имеются соответствующие акты.

Апробация работы. Научные результаты и положения диссертационной работы докладывались и обсуждались на конференциях Графикон'2008 и МЕ01А8'201 ], на научных семинарах кафедры вычислительной математики механико-математического факультета МГУ и НИВЦ МГУ, научных семинарах кафедры начертательной геометрии и машинной графики ННГАСУ.

Публикации. Результаты работы отражены в 6 научных публикациях, в том числе 3 - публикации в изданиях, рекомендованных ВАК.

Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения, списка литературы из 83 наименований. Основная часть работы (без списка литературы и приложений) изложена на 102 страницах, содержит 52 рисунка и 4 таблицы.

Основное содержание работы

Во введении обоснована актуальность выбранной темы диссертационной

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

В первой главе представлен обзор современного состояния проблемы визуализации данных на основе серии плоских сечений с помощью алгоритмов визуализации поверхности. Алгоритмы визуализации поверхности (surface rendering) обычно аппроксимируют исходную поверхность с помощью треугольников. Процесс визуализации трехмерных объектов в современных системах компьютерной графики проходит через ряд этапов:

х получение триангуляции исходной поверхности;

А ее упрощение (simplification) при необходимости;

А переупорядочивание треугольников с целью образования полос (triangle strips) и вееров (fans), ускоряющих процесс передачи данных на видеокарту;

А построение прогрессивных сетей (progressive meshes) для обеспечения разных уровней детализации и компактного хранения данных;

А сжатие данных;

А визуализация.

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

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

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

В работе предложен общий подход к построению триангуляций,

разбивающих пространство на произвольные фигуры. К разбиению предъявляются два требования: возможность склейки на смежных сторонах, топологическая связность (отсутствие дыр в триангуляции). Под склейкой подразумевается корректное сопоставление треугольников, получаемых в процессе работы алгоритма, на смежных сторонах трех и более фигур. После разбиения алгоритм определяет набор треугольников, получаемых в результате пересечения исходной поверхности и каждой фигуры. На основе предложенного общего подхода разработаны, подробно описаны и программно реализованы три новых алгоритма, разбивающие пространство на призматические, пирамидальные и октаэдрические ячейки. Предложенный алгоритм «марширующие октаэдры» строит оптимальную сеть треугольников. Сложность всех описанных алгоритмов составляет О (п), где п - число кубов, на которые разбивается исходная область пространства. Алгоритмическая сложность триангуляции Делоне в трехмерном случае (построение сети тетраэдров) составляет 0{п*1о^п)) и не исследуется в данной работе.

Рисунок I - Заполнение пространства тетраэдрами (алгоритм Скала): а) - четыре тетраэдра на стыке ячеек с вершинами (А В 1 2, А В 2 3, А В 3 4, А В 4 1); б) - отрезок АВ, соединяющий центры двух смежных кубов

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

А

а)

б)

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

Данный алгоритм обладает рядом преимуществ перед алгоритмом Скала, который дополнительно разбивает каждый октаэдр на четыре тетраэдра:

А построение сети треугольников для каждого октаэдра использует одно обращение к таблице случаев вместо четырех;

А возможность построения сети, оптимальной по определенному параметру, например, aspect ratio, который характеризует степень качества триангуляции, важного для визуализации томограмм.

Алгоритм «марширующие октаэдры» можно модифицировать так, чтобы для некоторых случаев разбиение октаэдра на тетраэдры было качественнее по параметру aspect ratio, чем в алгоритме Скала. Для этого дополнительно строятся 3 диагонали в каждом октаэдре. Например, на рисунке 1 для октаэдра А В 1 2 3 4

Рисунок 2 - Варианты пересечения октаэдра и поверхности

дополнительно строятся диагонали А В, 1-3 и 2-4.

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

Рисунок 3 - Варианты пересечения поверхности и октаэдра: а) - для случая пересечения в алгоритме Скала; б) - для случая пересечения в модифицированном алгоритме «марширующие октаэдры»

В приложении к работе находится таблица случаев пересечения октаэдра и поверхности из 64 строк (всего возможны 64 случая пересечения октаэдра и поверхности), по 25 элементов в каждой строке (возможно 8 треугольников при пересечении, на которые уходит по 3 элемента, плюс терминальный элемент -1). Все случаи соответствуют случаям пересечения в алгоритме Скала, за исключением случаев, когда значение функции на одной вершине имеет противоположный знак со значениями на других 5 вершинах. Как описано выше,

для таких случаев в октаэдр дополнительно введены 3 диагонали.

Полученная сеть треугольников будет оптимальна по параметру aspect ratio (в среднем на 3-10 % лучше), и ее построение производится в 1,5 раза быстрее, чем построение сети по алгоритму Скала (благодаря тому, что происходит одно обращение к таблице случаев для октаэдра вместо 4-х в алгоритме Скала).

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

х триангуляция (набор треугольников) с нормалями в вершинах; А несколько триангуляций (например, нескольких протезов, заданных треугольниками);

А неявная функция или набор неявных функций.

С помощью таких алгоритмов можно визуализировать медицинские данные, полученные методом компьютерной томографии. Например, можно изображать кальциевые отложения в сосудах сердца, опухоли в легких, камни в почках и т.п. Для объема применяется один из методов объемной визуализации (MIP, the attenuate operator и т.п.), а выделяемые объекты представляются поверхностями внутри объема. Результирующее изображение напоминает рентгеновский снимок с трехмерными объектами внутри него, выделенными цветом.

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

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

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

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

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

состоит из двух компонент: плотность объема и плотность треугольника.

Теперь опишем алгоритм визуализации неявной поверхности в полупрозрачной среде (рисунок 5).

Н - Плоскость 4 наблюдателя

Лучи, выпущенные ¡/

/из плоскости набл!

Область разбиения

оверхность

Рисунок 5 - Поточечный процесс испускания лучей для гибридного алгоритма Идет поточечный процесс вычисления яркости на каждом испущенном луче как в алгоритме объемной визуализации. Единственное отличие состоит в том, что процесс останавливается, как только точка на луче достигает поверхности. Предполагается, что поверхность непрозрачная. Создаются две матрицы изображения, содержащие яркости точек в диапазоне от 0 до 1, - первая для объема, вторая для поверхности. Заполнение первой матрицы происходит так же, как и в алгоритмах объемной визуализации, использующих среднее (the attenuate operator) или максимальное (MIP) значение на луче.

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

point = point t + (pointi - point{)*(a/(a + b)), где point - искомая точка; points, point, - соседние точки на луче.

Значение яркости в точке point на поверхности вычисляется следующим образом:

value = cocff*(gnA(point), v), где co.eff - заданный коэффициент, grad (point) -

градиент поверхности в точке point, v - единичный вектор направления луча, (х, у) - евклидово скалярное произведение.

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

bitmapSurface [/] = value*transparency - bitmapVolume [/'], где transparency -коэффициент прозрачности объема; bitmapSurface и bitmapVolume - матрицы изображения для поверхности и объема соответственно; value - значение яркости (получено выше).

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

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

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

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

Рисунок 6 - Трехмерная реконструкция шаровидной особенности в данных на основе снимков томографа

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

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

Вертикальные сечения строятся перпендикулярно текущему поперечному срезу. Они проходят через отрезки длины 5, середины которых находится в центре

С исследуемого поперечного контура под разными углами (рисунок 7, б). Для надежной работы алгоритма угол между этими отрезками должен быть достаточно малым.

Для отбрасывания контуров, не соответствующих срезам шаровидных особенностей, применяется набор тестов. В тестах используется обрамляющий прямоугольник R контура. Для определения R вычисляются главные оси инерции контура как собственные вектора его тензора инерции (2х2-матрица в плоском случае). Обрамляющий прямоугольник R - это минимальный прямоугольник, содержащий контур С со сторонами, параллельными главным осям инерции контура.

К контуру С с обрамляющим прямоугольником R применяются следующие тесты:

■*> минимальный размер: минимальное измерение прямоугольника R должно быть не меньше параметра Smin;

х максимальный размер: максимальное измерение прямоугольника R должно быть не больше параметра Smax;.

х степень вытянусти: аспект прямоугольника R (отношение сторон) не должен превышать параметра Asp. Это наиболее важный параметр алгоритма, т.к. он определяет степень приближенности особенности к шаровидной форме. На

Рисунок 7 - Вертикальные контуры: а) - контуры в вертикальных сечениях; б) - направления вертикальных сечений

практике Asp ~ 2.25;

л отношение площадей контура и прямоугольника: отношение площади контура к площади объемлющего прямоугольника S(P)/S(R) должно быть не меньше параметра AreaRatio. Для круга или эллипса отношение площадей равно п1А~ 0.786, на практике используется значение AreaRatio ~ 0.45. Тест позволяет отбросить, к примеру, контуры в форме букв X или Y, для которых объемлющие прямоугольники имеют небольшой аспект;

А максимальная плотность внутри контура: внутри контура должна существовать точка, плотность в которой не меньше, чем Tin. Параметр Tin выбирается заведомо большим, чем пороговая плотность на границе опухоли Ties: например, 77as=-200, 77и=-50.

Помимо тестов, применяемых к каждому контуру по отдельности, для совокупности всех контуров в вертикальных сечениях определяются их минимальное и максимальное измерения Smm и Smax. Если Smca/Smm> Asp, то исследуемый поперечный контур также отбрасывается.

Задача поиска особенностей грибовидной формы в данных на основе снимков томографа возникает при автоматическом распознавании вогнутостей на реконструкции поверхности заданного уровня. Грибовидные особенности имеют формы утолщений, которые прикрепляются к границе контура тонкой ножкой (рисунок 8).

Задача поиска особенностей грибовидной формы в данных на основе серии плоских сечений сводится к задаче поиска шаровидных особенностей. Такие особенности лежат вне исходного контура.

Для включения таких особенностей внутрь контура исходные контуры на поперечных сечениях сглаживаются (рисунок 9). Затем все элементы матриц срезов, лежащие вне сглаженных контуров, очищаются (им присваиваются значение плотности воздуха). В результате грибовидные особенности превращаются в шаровидные и могут быть найдены основным алгоритмом.

Рисунок 8 - Трехмерная реконструкция особенности грибовидной формы, прикрепленной к стенке контура

Рисунок 9 - Сглаживание контура: а) - исходный и расширенные контуры (после оператора dilation); б) - сжатый (после

оператора erosion)

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

должен находиться вне исходного контура.

Тестирование алгоритма на реальных данных показывает, что вероятность пропуска реальных особенностей при использовании разумного набора параметров алгоритма минимальна (параметры были выбраны таким образом, чтобы для всех доступных реальных данных пропуска реальных особенностей не было). При этом вероятность ложных позитивных случаев не превосходит 30% от общего числа выявленных случаев. Например, для серии снимков томографа, расстояние между которыми 0.4 мм и общим числом снимков 801 реализованный алгоритм выявил 6 особенностей, одна из которых была ложно позитивной.

Выводы

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

2. С помощью общего подхода к реализации методов триангуляции были разработаны новые алгоритмы: «марширующие призмы», «марширующие пирамиды» и «марширующие октаэдры». Проведен сравнительный анализ существующих и новых алгоритмов построения триангуляции. Сети, построенные алгоритмом «марширующие октаэдры», оптимальны по параметру aspect ratio и, следовательно, обладают наилучшим качеством для задач визуализации томограмм.

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

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

Публикации по теме диссертационной работы

Статьи, опубликованные в изданиях, рекомендованных ВАК:

1. Дижевский, А. Ю. Общий подход к реализации методов построения триангуляций неявно заданных поверхностей, использующих разбиение пространства на ячейки / А. Ю. Дижевский // Вычислительные методы и программирование. - 2007. - Т. 8. - С. 286-296.

2. Дижевский, А. Ю. Визуализация трехмерных объектов, вложенных в полупрозрачный объем / А. Ю. Дижевский // Вестник Московского Университета. Сер. 14. Вычислительная математика и кибернетика. - 2008. - Т. 4. - С. 39-45.

3. Дижевский, А. Ю. Геометрические аспекты методов визуализации трехмерных объектов / А. Ю. Дижевский // Приволжский научный журнал. - Н. Новгород, 2011. - № 3. - С. 40-46.

Другие публикации:

4. Дижевский, А. Ю. Решения несвязностей в алгоритмах построения триангуляций трехмерных объектов / А. Ю. Дижевский // ГрафиКон'2008: Тр. междунар. науч. конф. - 2008. - С. 310.

5. Дижевский, А. Ю. Распознавание шаровидных особенностей по серии томографических снимков / XV. КаШг^ег, В.В. Борисенко, А.Ю. Дижевский // ГрафиКон'2008: Тр. междунар. науч. конф. - 2008. - С. 312.

6. Дижевский, А. Ю. Геометрические аспекты визуализации томограмм / А. Ю. Дижевский, С.В.Клименко, С.И. Ротков // МЕ01А82011: Тр. междунар. науч. конф. / Лимассол, Республика Кипр. - М: Изд-во ИФТИ, 2011. - С. 6-11.

Подписано в печать Н- Формат 60x90 1/16

Бумага газетная. Печать трафаретная. Объем 1 печ.л. Тираж 100 экз. Заказ №-55?

Нижегородский государственный архитектурно-строительный университет, 603950, Н. Новгород, Ильинская, 65 Полиграфический центр ННГАСУ, 603950, Н.Новгород, Ильинская, 65

Введение.

Глава 1. Визуализация поверхности.

1.1. Общая характеристика метода и решаемые задачи.

1.2. Понятие о входных данных.

1.3. Построение триангуляции поверхности в заданной области объема

1.4. Методы, использующие кубические ячейки.

1.4.1. Разбиение области пространства на прямоугольные параллелепипеды и особенности реализации.

1.4.2. Получение триангуляции области поверхности, пересекающей параллелепипед.

1.4.3. Топологические несвязности.

1.4.4. Метод решения несвязностей по Черняеву.

1.4.5. Разбиение на тетраэдры ячейки для случаев с топологическими несвязностями.

1.5. Методы, использующие тетраэдрические ячейки.

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

1.5.2. Вычисление параметра aspect ratio для тетраэдра и тетраэдрической сети

1.5.3. Триангуляция внутри тетраэдра.

1.5.4. Алгоритм «марширующие тетраэдры 6».

1.5.5. Алгоритм «марширующие тетраэдры 5».

1.5.6. Алгоритм Скала.

1.5.7. Другие алгоритмы, использующие разбиение куба на тетраэдры с вершинами в вершинах куба.

1.5.8. Другие алгоритмы, использующие разбиение куба на тетраэдры с добавлением центров граней и центра куба.

1.5.9. Алгоритм «марширующие тетраэдры».

1.5.10. Итоговая таблица сравнения тетраэдрических сетей.

1.6. Методы, использующие другие типы ячеек.

1.6.1. Алгоритм триангуляции «марширующие призмы».

1.6.2. Триангуляция пятивершинными пирамидами.

1.6.3. Алгоритм марширующие октаэдры.

1.7. Сравнительный анализ методов визуализации поверхности.

1.8. Результат работы алгоритма визуализации поверхности.

Глава 2. Объемная и гибридная визуализации.

2.1. Особенности методов и отличия от методов визуализации поверхности.

2.2. Объемная визуализация.

2.3. Гибридная визуализация.

2.3.1. Вокселизация триангуляции.!.

2.3.2. Алгоритм двумерного хеширования.

2.3.3. Алгоритм визуализации неявной поверхности, вложенной в полупрозрачный объем.

2.3.4. Результат работы алгоритма объемной визуализации.

2.3.5. Результат работы алгоритма визуализации поверхности, вложенной в полупрозрачный объем.

Глава 3. Выявление особенностей шаровидной и грибовидной формы

3.1. Общая характеристика метода.

3.2. Постановка задачи.

3.3. Вспомогательные алгоритмы.

3.4. Алгоритм выделения контура по заданному пороговому значению

3.5. Рекурсивный алгоритм закрашивания области, ограниченной контуром.

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

3.6.1. Определение контуров легких.!.

3.6.2. Выделение шаровидных особенностей.

3.6.3. Проверка контуров, представляющих срезы шаровидных объектов

3.7. Распознавание особенностей грибовидной формы.

3.7.1. Алгоритмы сглаживания замкнутого контура.

3.7.2. Сглаживание контура с помощью морфологического оператора закрытия контура.

3.7.3. Сглаживание контура с помощью отсечения ножек грибов.

3.8. Результат работы алгоритма выявления особенностей шаровидной и грибовидной формы.

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

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

Алгоритмы визуализации поверхности (surface rendering) строят изображение поверхности в трехмерном пространстве (одним из представлений поверхности является уравнение: fix, у, z) — с = 0, где с — заданный уровень). Сначала исходная поверхность аппроксимируется полигонами, затем производится визуализация полигонов с помощью одной из графических библиотек. Самым ранним алгоритмом построения триангуляции поверхности является алгоритм «марширующие кубы», представленный Лоренсеном в 1987 году. Этот алгоритм производит разбиение области пространства, содержащей исходную поверхность, на кубические ячейки и аппроксимирует пересечение исходной поверхности и каждой кубической ячейки разбиения треугольниками. Для случая синтеза изображения по плоским сечениям вершинами каждого куба будут по четыре точки на паре соседних сечений (на каждом сечении вершины образуют квадрат), расположенные как бы друг над другом.

В триангуляции, построенной алгоритмом «марширующие кубы» могут возникать разрывы или топологические несвязности на смежной грани (face ambiguity), показанные Блюменталем (Bloomenthal) в 1988 году. Дёрстом (Durst) в работе 1988 года показано также существование внутренних топологических неточностей (internal ambiguity). Нильсон и Хамман (Nielson and Hamman) представили метод решения топологических несвязностей для граней куба. В 1995 году Черняевым (Chernyaev) был предложен систематизированный метод решения топологических несвязностей алгоритма "марширующие кубы", а в 2003 году Льюинером (Lewiner) был программно реализован.

Также существуют алгоритмы разбиения области пространства, в которой определена поверхность, на неправильные тетраэдры и аппроксимирующие исходную поверхность внутри каждого тетраэдра. Наиболее распространенными среди алгоритмов данного класса являются: алгоритм «марширующие тетраэдры 6» (МТ6), представленный Гуезеком (Gueziec) в 1995 году, и «марширующие тетраэдры 5» (МТ5), представленный Канейро (Carneiro) в 1996 году, основанные на разбиении области пространства (обычно куб) на кубы, а каждый куб в свою очередь разбивается на 6 или 5 тетраэдров соответственно. В 2000 году Скалой (V. Skala) был представлен алгоритм, использующий разбиение пространства на кубы с последующим построением тетраэдров на стыках соседних кубов.

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

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

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

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

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

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

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

Для достижения поставленной цели требуется решение следующих задач: исследование алгоритмов триангуляции и разработка единого подхода к реализации алгоритмов визуализации поверхности, основанного на разбиении пространства на различные фигуры; разработка новых алгоритмов триангуляции, оптимальных по параметру aspect ratio', создание алгоритма визуализации поверхности (заданной неявной функцией), вложенной в объем; разработка алгоритмов по поиску трехмерных особенностей грибовидной и шаровидной формы в массиве данных на основе серии плоских сечений.

Методами исследования являются аналитическая геометрия, дискретная математика, алгоритмы компьютерной геометрии и графики, физической модели в оптике и методы объектно-ориентированного программирования.

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

Научная новизна состоит в том, что: ^ предложен общий подход в области построения и реализации триангуляции поверхностей в трехмерном пространстве. С его помощью получены новые алгоритмы триангуляции, один из которых (основанный на разбиении пространства на октаэдры) по качеству триангуляции является наилучшим на текущий момент; представлен новый алгоритм визуализации поверхности, вложенной в объем, где поверхность задана неявной функцией; разработан новый алгоритм поиска геометрических особенностей шаровидной и грибовидной формы) в массиве данных на основе двумерных матриц. Алгоритм основан на анализе формы трехмерной 9 особенности с помощью вычисления ее сечений в разных направлениях и анализе контуров в полученных сечениях.

Положения, выносимые на защиту

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

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

Алгоритм поиска особенностей шаровидной и грибовидной формы в массиве данных на основе серии плоских сечений.

Практическая значимость

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

Работа выполнена при поддержке Российского фонда фундаментальных исследований (грант 07-07-00373). Алгоритмы реализованы в виде программ на языке С++, которые внедрены и используются при выполнении научно-исследовательских работ в Институте физико-технической информатики, на кафедре системной интеграции и менеджмента Московского физико-технического института (государственного университета) и в Институте прикладной физики Национальной Академии наук Беларуси, о чем имеются соответствующие акты.

Апробация работы

Материал диссертации опубликован в работах [1-6], а также докладывался и обсуждался на конференциях Графикон'2008 и ]УПЮ1А8'2011, на научных семинарах кафедры вычислительной математики механико-математического факультета МГУ, на научных семинарах НИВЦ МГУ и ННГАСУ.

Публикации. Результаты работы отражены в 6 научных публикациях, в том числе 3 публикации в изданиях, рекомендованных ВАК.

Структура и объем работы

Диссертационная работа состоит из введения, трех глав, заключения, списка литературы из 83 наименований. Основная часть работы (без списка литературы и приложений) изложена на 102 страницах, содержит 52 рисунка и 4 таблицы.

Заключение

В диссертации предложены новые алгоритмы, строящие топологически связные триангуляции и не относящиеся к семействам алгоритмов «марширующие кубы» и «марширующие тетраэдры». Данные алгоритмы значительно проще в реализации по сравнению с алгоритмом «марширующие кубы». Представлен модифицированный вариант алгоритма МТ6, улучшающий качество такой сети МТ6 по параметру aspect ratio. Также предложены два способа разбиения пространства на тетраэдры: «марширующие тетраэдры» и модификация МТ5. Способ разбиения на тетраэдры «марширующие тетраэдры» уступает по параметру aspect ratio лишь алгоритму Скала и «марширующие октаэдры». В то же время модифицированный алгоритм от МТ5 генерирует тетраэдрическую сеть, эквивалентную сети по Скала. Это дает другой взгляд на свойства сетей, построенных по алгоритмом Скала. Алгоритм «марширующие октаэдры» строит оптимальную триангуляцию.

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

Решена задача поиска шаровидных и грибовидных особенностей в данных по серии плоских сечений. Тестирование алгоритма на реальных данных показывает, что вероятность пропуска реальных особенностей при использовании разумного набора параметров алгоритма минимальна (параметры были выбраны таким образом, чтобы для всех доступных реальных данных пропуска реальных особенностей не было.) При этом вероятность ложных позитивных случаев не превосходит 30% от общего числа выявленных случаев. Например, для серии снимков томографа, расстояние между которыми 0.4 мм и общим числом снимков 801 реализованный алгоритм выявил 6 особенностей, одна из которых была ложно позитивной.

По результатам работы можно сделать следующие выводы:

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

2. С помощью общего подхода к реализации методов триангуляции были разработаны новые алгоритмы: "марширующие призмы", "марширующие пирамиды" и "марширующие октаэдры". Проведен сравнительный анализ существующих и новых алгоритмов построения триангуляции. Сети, построенные алгоритмом "марширующие октаэдры", оптимальны по параметру aspect ratio и, следовательно, обладают наилучшим качеством для задач визуализации томограмм.

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

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

Благодарности

Я выражаю благодарность доктору-физико математических наук, профессору Станиславу Владимировичу Клименко за ответственное руководство над диссертационной работой, кандидату физико-математических наук, старшему научному сотруднику кафедры вычислительной математики МГУ Владимиру Витальевичу Борисенко за неоценимую помощь в написании диссертационной работы.

1. Дижевский А. Ю. Общий подход к реализации методов построения триангуляций неявно заданных поверхностей, использующих разбиение пространства на ячейки // Вычислительные методы и программирование. 2007. Т.8. С.286-296

2. Дижевский А. Ю. Визуализация трехмерных объектов, вложенных в полупрозрачный объем // Вестник Московского Университета. Сер. 14. Вычислительная математика и кибернетика. 2008. Т.4. С.39-45

3. Дижевский А. Ю. Геометрические аспекты методов визуализации трехмерных объектов // Приволжский научный журнал. 2011. No.3. С.40-46

4. Дижевский А. Ю. Решения несвязностей в алгоритмах построения триангуляций трехмерных объектов // Труды международной конференции ГрафиКон'2008. Москва. 2008. С.310

5. Kallinger W., Борисенко В.В., Дижевский А. Ю. Распознавание шаровидных особенностей по серии томографических снимков // Труды международной конференции ГрафиКон'2008. Москва. 2008. С.312

6. Дижевский А. Ю., Клименко C.B., Ротков С.И. Геометрические аспекты визуализации томограмм // Труды международной конференции MEDIAS2011: Лимассол, Республика Кипр. М: Изд-во ИФТИ, 2011. С. 611

7. Lorensen W. Е., Cline H. Marching cubes: A high resolution 3d surface construction algorithm. // In Proceedings of the 14th ACM Siggraph annual conference on Computer graphics and interactive techniques. 1987. Vol. 21. pp. 163-169

8. Bloomenthal J. An Implicit Surface Polygonizer // In P. Heckbert, editor, Graphics Gems IV, Academic Press, Boston. 1994. pp. 324-349

9. Durst M. Letters: Additional Reference to Marching Cubes. // Computer Graphics. 1988. Vol.22, No.2, pp. 72-73

10. Nielson G. M., Hamann B. The Asymptotic Decider: Resolving the Ambiguity in Marching Cubes // Proceedings of Visualization '91. 1991. pp.2938

11. Lewiner T., Lopes H. Efficient implementation of Marching Cubes' cases with topological guarantees. //Journal of Graphics Tools. 2003. Vol.8, No.2. pp.1-15.

12. Chernyaev E. V. Marching Cubes 33: Construction of Topologically Correct Isosurfaces. // Technical Report CERN CN 95-17, CERN Institute for High Energy Physics, 1995.

13. Gueziec A. Exploiting Triangulated Surface Extraction Using Tetrahedral Decomposition // IEEE Transactions on Visualization and Computer Graphics. 1995. V. 1, No. 4, pp.328-342

14. Carneiro B. P., Silva C. T., Kaufman, A. E. Tetra-Cubes: An algorithm to generate 3D isosurfaces based upon tetrahedra // SIGGRAPH'96, pp.205-210

15. Montani, C., Scateni R., Scopigno, R. Discretized Marching Cubes // Visualization'94 Proceedings.//IEEE Computer Society, IEEE Computer Society Press, 1994, pp.281-287

16. Bourke P. Polygonising a scalar field using tetrahedrons. //WWW, 1997. http://local.wasp.uwa.edu.au/pbourke/geometry/polygonise/

17. Nielson G. M., Hamann B. The Asymptotic Decider: Resolving the Ambiguity in Marching Cubes // IEEE Visualization, Proceedings of the 2nd conference on Visualization '91. 1991. pp.83-91

18. Skala V. Precission of iso-surface extraction from volume data andvisualization. // Conference on Scientific Computing. 2000. pp.368-378http://www.emis.de/journals/AMUC/contributed/algo2000/skala.pdf104

19. Lewis R.W., Zheng Y., Gethin D.T. Three-Dimensional Unstructured Mesh Generation: Part 3. Volume Meshes //Computer Methods In Applied Mechanics And Engineering. 1996. Vol. 134. pp.285-310

20. Levoy M. Diplay of surfaces from volume data. // IEEE Computer graphics and applications. 1988. Vol.8, No.3, pp.29-37

21. Levoy M. Efficient ray tracing of volume data // ACM Trans. Comp. Graph. 1990. Vol.9, No.3, pp.245-261

22. Hoehne K.H., Pfiesser B., Pommert A., Riemer M., Schiemann T., Schubert R., Tiede U. A virtual body model for surgical education and rehearsal // IEEE Computer. 1996. Vol.29, No.l, pp.25-31

23. Bhalerao A., Pfister H., Halle M., Kikinis R. Fast Re-Rendering Of Volume and Surface Graphics By Depth, Color, and Opacity Buffering // Medical Image Analysis. 2000. Vol.4, No.3, pp.235-251

24. Lacroute P., Levoy M. Fast volume rendering using a shear-warp factorization of the viewing transformation // SIGGRAPH '94. 1994. pp.451458

25. Westover L. Footprint evaluation for volume rendering // SIGGRAPH' 90. 1990. pp.367-376

26. Cabral B., Cam N., Foran J. Accelerated volume rendering and tomographic reconstruction using texture mapping hardware // Proceedings of the 1994 Symposium on Volume Visualization. 1994. pp.91-98

27. Huang J., Yagel R., Filippov V., Kurzion Y. An accurate method for voxelizing polygon meshes // Proc. IEEE Sym. on Vol. Vis. Research Triangle Park. 1998. USA: ACM. pp.119-126

28. Kreeger K., Kaufman A. Mixing Translucent Polygons with Volumes // IEEE Transactions on Visualization and Computer Graphics. 1999. pp. 191-198

29. Tietjen C., Isenberg T., Preim B. Combining Silhouettes, Surface, and

30. Volume Rendering for Surgery Education and Planning // EUROGRAPHICS

31. EE VGTC Symposium on Visualization. 2005. pp.303-310.105

32. Levoy M. A hybrid ray tracer for rendering polygon and volume data // IEEE Сотр. Graph. Appl. 1990. Vol.10, No.3. pp.33^10

33. Kaufman A., Yagel R., Cohen D. Intermixing surface and volume rendering // 3D-Imaging in Med.: Alg. Sys. Appl. 1990. Berlin, Germany: SpringerVerlag. pp.217-227

34. Campadelli P., Casiraghi E., Artioli D. A Fully Automated Method for Lung Nodule Detection From Postero-Anterior Chest Radiographs // IEEE Trans, on Medical Imaging. 2006. Vol.25, No. 12, pp. 1588-1603

35. Dajnowiec M., Alirezaie J., Babyn P. An Adaptive Rule Based Automatic Lung Nodule Detection System // Pattern Recognition and Image Analysis. Lect. Notes in Сотр. Sci. 2005. Vol.3687, pp.773-782

36. Schroeder W. J., Zarge J., Lorensen W. E. Decimation of Triangle Meshes. // Computer Graphics (SIGGRAPH). 1992. Vol.26, No.2. pp.65-70

37. Evans F., Skiena S., Varshney A. Efficiently generating triangle strips for fast rendering // Technical report. 1997. Department of Computer Science, State University of New York at Stonyt Brook, USA

38. Hoppe H. Progressive meshes // SIGGRAPH. 1996. pp.99-108

39. Семенихин А., Игнатенко А. Сравнительный анализ методов интерактивной триангуляции сеточных функций // On-line журнал «Графика и мультимедиа». 2004. Вып. 6

40. Бончковский Р.Н. Заполнение пространства тетраэдрами // Сборник статей по элементарной и началам высшей математики. 1935. Объединенное научно-техническое издательство НКТП СССР. № 4, С.26-40.

41. Ning P., Bloomenthal J. An evaluation of implicit surface tilers // Computer Graphics and Applications. 1993. Vol.13, No.6. pp.33-41

42. Natarajan В. K. On generating topologically consistent isosurfaces fromuniform samples // The Visual Computer: International Journal of Computer

43. Graphics. 1994. Vol. 11, No. 1. pp.52-62106

44. Tavares G., Santos R., Lopes H., Lewiner T., Vieira A. W. Topological reconstruction of oil reservoirs from seismic surfaces // In International Association for Mathematical Geology. 2002.

45. Avila R., He T., Hong L., Kaufman A., Pfister H., Silva C., Sobierajski L., Wang S. VolVis: a diversified volume visualization system // Proc. Visualization' 94. 1994. pp.31-38

46. Lopes A., Brodlie K. Improving the Robustness and Accuracy of the Marching Cubes Algorithm for Isosurfacing. // IEEE Transactions on Visualization and Computer Graphics. 2002. pp. 16-29

47. Matveev S. V. Algorithmic and Computer Methods for Three-Manifolds. // Proceedings IEEE Visualization '94, pp.288-292.

48. Bajaj C. L., Pascucci V., Schikore D. Visualization of Scalar Topology for Structural Enhancement // IEEE Visualization '98. 1998. pp.51-58

49. Hannemann M., Sobieczky H. Visualization of high speed aerodynamic configuration design. //IEEE Visualization. 1995. p.355

50. Dobashi Y., Kaneda K., Yamashita H., Okita T., Nishita T. A Simple, EfficientMethod for Realistic Animation of Clouds. //SIGGRAPH. 2000. pp.1928

51. Eltonsy N., Tourassi G., Desoky A., Elmaghraby A. A methodology for analysis extraction and visualization of CT scans. //Signal Processing and Information Technology. 2003. pp.479-482

52. Termeer M., Bescos J.O., Breeuwer M., Vilanova A., Gerritsen F., Groller M.E. CoViCAD: Comprehensive Visualization of Coronary Artery Disease. //Visualization and Computer Graphics. 2007. Vol. 13, No 6. pp. 1632-1639

53. Skotnes H., Hartvigsen G., Johansen D. 3D visualization of weather forecasts and topography // Computer Science Technical Report: 94-15. 1994

54. Rodrigo M., Silva M., Manssour I. H., Maria C., Freitas D. S. Optimizing Combined Volume And Surface Data Ray Casting // WSCG. 2000

55. Aggarwal A., Guibas L. J., Saxe J., and Shor P. W. A linear-time algorithm for computing the Voronoi diagram of a convex polygon //Discrete Comput. Geom. 1989. Vol. 4, No. 6. pp.591-604

56. Chew L. P. Building Voronoi diagrams for convex polygons in linear expected time. //Technical Report PCS-TR90-147, Dept. Math. Comput. Sci., Dartmouth College, Hanover, NH, 1986

57. O. Delivers, M. Teillaud Perturbations and Vertex Removal in a 3D Delaunay Triangulation. //14-ACM Symp. on Algorithms (SODA). 2003. pp.313-319

58. Afanasev A., Sukhoroslov О., Posypkin М., Tarasov A. Applied Mathematical Problems in the Distributed Computing Environment. // Proc. of XXI International Symposium on Nuclear Electonics & Computing., Dubna: JINR, 2008. pp. 15-19

59. Tost D., Pluig A. and Navazo I. Visualization of mixed scenes based on volume and surface. //In Proceedings of the Fourth Eurographics Workshop on Rendering. 1993. pp.281-294

60. Kaufman A., Shimony E. 3D Scan Conversion algorithms for voxel based graphics // Proceedings ACM Workshop on Interactive 3D Graphics, Chapel Hill, NC. 1986. pp.45-75

61. Kaufman A. Efficient algorithms for 3D Scan-Conversion of parametric Curves. Surfaces and Volumes // Computers and Graphics. 1987. Vol. 21, No. 4. pp.171-179

62. Kaufman A. Efficient algorithms for 3D Converting Polygons // Computers and Graphics. 1988. Vol. 12, No. 2. pp.213-219

63. Payne B.A. and Toga A.W. Distance field manipulation of surface models //IEEE Computer Graphics and Applications. 1992. Vol. 12, No. 1. pp.65-71

64. Sramek M. Non-binary Voxelization for Volume Graphics //In Proceedings of Spring Conference on Computer Graphics, 2001. pp.35-51.

65. Cignoni P., Montani C., and Scopigno R. A Comparison of Mesh Simplification Algorithms // Computers and Graphics. 1998. Vol. 22, No. 1. pp.3 7-54

66. Heckbert P. and Garland M. Survey of Polygonal Surface Simplification Algorithms // Siggraph 97 Course Notes. ACM Press, New York. 1997. No. 25. pp. 1-29

67. Low K-L. and Tan T.S. Model Simplification Using Vertex Clustering // Proc. 1997 Symp. Interactive 3D Graphics, ACM Press, New York. 1997. pp.75-82

68. Hoppe H. View-Dependent Refinement of Progressive Meshes // Computer Graphics (Proc. Siggraph 97), ACM Press, New York. 1997. Vol. 31. pp. 189198

69. Hoppe H. Efficient Implementation of Progressive Meshes //Computers and Graphics. 1998. Vol. 22, No. 1. pp.27-36

70. Saupe D., Kuska J. Compression of isosurfaces //In Proceedings of Vision, Modeling and Visualization '01. 2001. pp.330-340

71. Waschbusch M., Wurmlin S., Lamboray E. C., Eberhard F., Gross M.: Progressive compression of point-sampled models //In Eurographics Symposium on Point Based Graphics. 2004. pp.95-102

72. Kruger J., Schneider J., Westermann R. Compression and Rendering of Iso-Surfaces and Point Sampled Geometry // Visual Computer. 2006. Vol.22, No.8. pp.517-530

73. El-Sana J., Azanli E. and Varshney A. Skip strips: Maintaining triangle strips for view dependent rendering //In IEEE Visualization '99 Proceedings. 1999. pp.131-138

74. Velho L., L. de Figueiredo, and Gomes J. Hierarchical generalized triangle strips //The Visual Computer. 1999. Vol. 15, No. 1. pp.21-35

75. Shreiner D. OpenGL Programming Guide, Version 3.0 and 3.1, 7th Edition. Addison-Wesley Publishing Company, 2009

76. Li Q., Sone S, Doi K. Selective enhancement filters for nodules, vessels, and airway walls in two- and three-dimensional CT scans. //Med. Phys. 2003. Vol.30, No.8. pp.2040-2051

77. Delogu, P. et al. Preprocessing methods for nodule detection in lung CT. //Computer Assisted Radiology and Surgery; Proc. 19th International Congress and Exhibition, Berlin, Germany. International Congress Series 1281. 2005. pp. 1099-1104

78. Fetita C., Preteux F., Beigelman-Aubry C., and Grenier P. Pulmonary airways: 3-D reconstruction from multi-slice CT and clinical investigation. // IEEE Transactions on Medical Imaging. 2004. Vol. 23, No.ll. pp.1353-1364

79. Chiang, C.-H., Jong, B.-S., Lin, T.-W. Regular Mesh Simplification // Computer and Management (CAMAN), 2011 International Conference. 2011. pp.1-4

80. Wee L.K., Chai H.Y., Eko S. Surface Rendering of 3D Ultrasound Images Using VTK 11 Journal of Scientific and Industrial Research. 2011. Vol.70. pp.421-426

81. Fogal T. and Kruger J. Tuvok, an Architecture for Large Scale Volume Rendering. // In Proceedings of the 15th International Workshop on Vision, Modeling, and Visualization. November 2010. pp.139-146

82. Pedro Machado Manhaes de Castro. Practical Ways to Accelerate Delaunay Triangulations. These de doctorat en sciences, Université de Nice Sophia Antipolis, France. 2010.

83. Buchin K., Loffler M., Morin. P., and Mulzer. W. Preprocessing imprecise points for Delaunay triangulation: Simplified and extended. // Algorithmica. 2011. Vol.61, No.3. pp.674-693