Формирование трехмерных моделей органов с помощью алгоритма марширующих кубов

Formation of three-dimensional models of bodies by means of an algorithm of the marching cubes

Grigory Volkov

student of the magistracy, Mari State University, Russian Federation, Yoshkar-Ola

Ksenia Volkova

student of the magistracy, Mari State University, Russian Federation, Yoshkar-Ola

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

Abstract. In this article formation of three-dimensional models of bodies by means of an algorithm of the marching cubes is considered. The most popular method of creation of isosurfaces is the marching cubes (marching cubes). In this article, there is the complete and short description of this algorithm.

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

Keywords: formation of model; three-dimensional model of body; the marching cubes; segmentation; a surface contour; intraoperative navigation; low-invasive operation; an isosurface; the computer tomogram; the bitmap; configurations of grounds.

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

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

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

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

Далее находятся скалярные функции, градиенты которых лучше всего соответствуют полученному векторному полю. На основании данных таких функций создает искомая изоповерхность. Для отображе­ния результатов построения поверхности необходимо дискретизировать полученную изоповерхность. Ее нужно представить в виде набора стандартных элементов – полигонов, что представляет собой процедуру триангуляции. Триангуляция осуществляется на основе воксельных алгоритмов [3].

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

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

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

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

• значение 1 соответствует вершине, которая является объектом отображения;
• значение 0 соответствует вершине, которая не является объектом отображения (рисунок 1).

Рисунок 1. Кубический шаблон метода «Марширующие кубы»

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

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

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

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

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