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

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

ГАВРИЛОВ Николай Игоревич

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

Специальность: 05.13.17 - «Теоретические основы информатики» по техническим наукам

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

005059093 1 6 МАЙ 2013

Нижний Новгород - 2013 г.

005059093

Работа выполнена на кафедре математического обеспечения ЭВМ в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Нижегородский государственный университет им. Н.И. Лобачевского» (г. Нижний Новгород)

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

доктор технических наук, доцент, Турлапов Вадим Евгеньевич

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

Утробин Владимир Александрович, доктор технических наук, профессор, НГТУ им. P.E. Алексеева, кафедра «Вычислительные системы и технологии», профессор

Крылов Андрей Серджевич, доктор физико-математических наук, МГУ им. М.В.Ломоносова, кафедра математической физики, профессор

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

Институт прикладной математики им. М.В. Келдыша РАН, г. Москва

Защита диссертации состоится «23» мая 2013 г. в 15 часов на заседании диссертационного совета Д.212.165.05 в Нижегородском государственном техническом университете им. Р.Е.Алексеева по адресу: 603000, г. Нижний Новгород, ул. Минина, 24, ауд. 1258.

С диссертацией можно ознакомиться в библиотеке Нижегородского государственного технического университета им. Р.Е.Алексеева.

Автореферат разослан «23» апреля 2013 г.

Ученый секретарь г Ґу/

диссертационного совета ^ /ґ" A.C. Суркова

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Во многом причина резкого роста связана с перерастанием количества в качество: количественных характеристик применяемых приборов и вычислительной техники - в появление трехмерных технологий обработки, визуализации и исследования данных, и, на этой базе, в создание новых трехмерных методов человеко-машинного общения. Так, превращение компьютерной томографии (KT) в многосрезовую компьютерную томографию (МСКТ) с выходом в свет 320-срезового томографа (2007, Toshiba), способного выполнить томографию всего тела человека с толщиной среза менее 1 мм за время около 10-15 секунд, фактически поставило на поток получение данных для трехмерного моделирования пациента в медицине. Компания IBM, мировой лидер производства суперЭВМ, в 2008-2009 стартовала и продолжает до сих пор проекты (Smarter Planet) по использованию 3D модели пациента, как основы его медицинской карты. В 2012 ШМ стартовала проект по моделированию действия лекарств на ЗБ-аватаре конкретного человека.

Увеличение производительности ЭВМ и производительности алгоритмов сделало возможным совмещенную обработку (fusion) и 3D реконструкцию сразу двух и более томограмм обычного объема в реальном времени, появились томографы ведущих мировых производителей способные совместно исследовать ЗО-реконструкции KT и ПЭТ (позитрон-эмиссионных) или KT и ОФЭКТ (однофотонных эмиссионных), или KT и ФМРТ (функциональных МРТ) томограмм. Неоценимую поддержку способны оказать технологии трехмерной реконструкции томограмм в медицинском образовании. Так, в США в мае 2011 года появилось экспериментальная модель виртуального анатомического стола (Anatomage Table, http://anatomage.com), базовой функцией которого является интерактивная 3D реконструкция пациента в полный рост по данным томографии. Появилась теоретическая возможность слить данные всех существующих методов диагностики в одной трехмерной модели пациента.

Сегодня существует довольно много подходов, развитых в работах следующих ученых: Klaus Engel, Bernhard Kainz, Daniel Ruijters, Stefan Guthe, Johanna Beyer, Vincent Vidal, Markus Hadwiger, Daniel Weiskopf, Thomas Ertl, Wolfgang Strasser, Byeonghun Lee, Jihye Yun, Jinwook Seo, Yeong-Gil Shin, Bohyoung Kim, Byonghyo Shim, Martin Artner, Torsten Möller, Ivan Viola, Meister Gröller и др., позволяющих производить объёмную визуализацию в реальном времени с использованием вычислений на GPU. Мировой рынок предлагает в составе томографов несколько программных систем,

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

То же самое можно сказать о росте информационного потока и необходимости построения производительных методов его обработки в биологии. Наиболее критическое положение, из-за огромного объема данных, наблюдается в трехмерной обработке данных с электронного микроскопа с разрешением в единицы нанометров. В качестве примера объемов подлежащих обработке можно привести общедоступный Интернет-ресурс с данными электронной микроскопии фрагмента мозга мыши объемом в 12 терабайт (http://openconnectomeproject.org). Особенно ресурсоемкими здесь являются задачи морфологического анализа реконструированных клеток.

Несмотря на значительный прогресс в решении упомянутых выше задач существует и ряд нерешенных проблем:

• качественная трехмерная визуализация томограмм «привязана» сегодня к томографу из-за высоких требований к производительности рабочей станции, но недоступна рядовому врачу-клиницисту и, тем более, студенту, - необходим переход к программному обеспечению и технике массовой доступности без потери качества визуализации;

• объем томограмм, доступных для 3D реконструкции на GPU, ограничен размером памяти GPU (сегодня для массовых офисных видеокарт в продаже - это 1-2 GB), в то время как постоянный рост данных требует снятия ограничения на их объем и построения алгоритмов декомпозиции для параллельной поблочной обработки данных с сохранением всех возможностей и качества визуализации;

• несмотря на рост производительности и качества 3D визуализации отсутствует практика количественной оценки качества визуализации;

• существует несколько открытых и коммерческих программ для полуавтоматической трехмерной геометрической реконструкции клеток, но нет методов и программ для автоматизации детального морфологического анализа клетки, в то время как вычислительная сложность такого анализа в величинах SVR (Surface-to-Volume Ratio) пропорциональна квадрату числа вершин или треугольников 0(п2) при характерных значениях п~105 треугольников.

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

Поставленная цель требует решения следующих задач:

1) Провести анализ существующих методов трёхмерной визуализации в медицине, и науке в целом, анализ подходов к повышению качества и производительности ЗО-визуализации.

2) Развить существующие методы для их взаимодополняющего применения в условиях бюджетных GPU и создания технологии 3D-визуализации для массового применения в медицине, в том числе:

2.1) Разработать модификацию метода блочной декомпозиции гигавоксельных (более 10л9 вокселей) данных для визуализации на GPU, сохраняющую возможности и качество визуализации недекомпозированных данных (возможность применения трикуби-ческой интерполяции, освещения, отбрасывания теней, пропуска пустых областей, различных условий интегрирования вдоль луча,...)

2.2) Развить методы повышения производительности 3D визуализации и подавления различного рода дефектов (артефактов) визуализации рациональные в условиях GPU

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

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

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

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

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

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

аналитической геометрии; теории вероятностей; методах параллельных вычислений.

Научная новизна работы заключается в том, что:

1) Выполнена модификация метода блочной декомпозиции данных в алгоритме Ray Casting, отличающаяся оптимальной последовательностью обхода блоков, использованием оптимизированных по объему вспомогательных структур метода пропуска пустых областей (empty space leaping), обеспечением возможности построения локального освещения и теней в сочетании с использованием таблиц предынтегрированного рендеринга

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

3) Исследованы оценки качества (дефектов) изображения, принятые в теории сигналов, 2D и 3D сжатии, в оценке качества видео. На основе вычислительного эксперимента для 3 типов оценки (PSNR, SNR, SSIM) рекомендована, и адаптирована для задачи количественной оценки качества объёмной визуализации, логарифмическая оценка, подобная пиковому отношению сигнала к шуму (PSNR - Peak Signal-to-Noise Ratio). На основе этой оценки проведено сравнительное исследование ряда методов построенных на основе алгоритма Ray Casting

4) Предложен и исследован на примере геометрически сложных клеток мозга (астроцитов) высокопроизводительный метод морфологического анализа объекта, локально оценивающий эффективность взаимодействия со средой в каждой точке объекта величиной отношения площади к объёму (Surface-to-Volume Ratio) внутри пространства, ограниченного сферой заданного радиуса с центром в оцениваемой точке.

Практическая значимость исследования. Результаты исследования имеют практическую значимость и как единый продукт (программный комплекс), и как отдельные компоненты, в частности, новый метод морфологического анализа поверхностей.

Программный комплекс, реализующий разработанные модели и алгоритмы, готов к практическому использованию в подсистемах 3D визуализации данных в медицине, биологии, физике, инженерном анализе. Программный комплекс используется: институтом прикладной физики РАН в задачах научной визуализации; производителем медицинского программного обеспечения ООО «ПО ВИДАР» в составе поставляемой им медицинской информационной системы; в виде лабораторной работы по

научной визуализации в учебно-методическом комплексе «Компьютерная графика», и может быть использован в учебном процессе вузов.

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

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

Апробация работы. Основные результаты работы представлены и обсуждены на следующих конференциях:

конференция «Технологии Microsoft в теории и практике программирования» (ННГУ, 13-14 мая, 2010),

конференция «Вычисления с использованием графических процессоров в биологии и биоинформатике» (МГУ, 24-25 мая 2010),

конференция GraphiCon'2010 (20-24 сентября, Санкт-Петербург, Россия), работа заняла I место на конкурсе молодых учёных,

конференция "Высокопроизводительные параллельные вычисления на кластерных системах" (1-3 ноября 2010г, Пермь, Россия),

конференция IADIS Multi Conférence on Computer Science and Information Systems 2011 (Rome, Italy, 20 - 26 July 2011),

конференция Proc. of Ш International Symposium Topical Problems of Biophotonics - 2011 (16-22 July 2011, St.-Petersburg - Nizhny Novgorod), конференция GraphiCon '2011 (26-30 сентября, Москва, Россия), конференция "Высокопроизводительные параллельные вычисления на кластерных системах" (1-3 ноября 2011г, Нижний Новгород, Россия),

конференция IADIS Multi Conférence on Computer Science and Information Systems 2012 (Lisbon, Portugal 21 - 23 July 2012),

конференция SIGGRAPH 2012 - 39th annual conférence on Computer graphies and interactive techniques (5-9 August 2012),

конференция "Высокопроизводительные параллельные вычисления на кластерных системах" (26-28 ноября 2012г, Нижний Новгород, Россия).

Работа также прошла конкурсный отбор для участия в программе У.М.Н.И.К.

Публикации. Основные результаты исследования опубликованы в 13 работах, из них 2 - публикации в изданиях, рекомендованных ВАК.

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

1) модификация для GPU метода блочной декомпозиции данных в алгоритме Ray Casting, отличающаяся оптимальной последовательностью обхода блоков, использованием оптимизированных структур метода пропуска пустых областей (empty space leaping), возможностью

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

2) исследование методов количественной оценки уровня ошибок постклассификации и фильтрации, позволившее ввести единый критерий качества подобный PSNR и измерение производительности визуализации при заданном качестве;

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

4) метод секущих сфер для морфологического исследования сложного биологического объекта в величинах SVR (Surface-to-Volume Ratio) -отношения площади к объёму.

Структура и объем работы. Диссертация состоит из введения, четырёх глав, заключения, списка литературы из 160 наименований. Общий объем -168 стр.

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

В первой главе дан обзор и анализ существующих методов и технологий анализа данных в медицине и биологии, в особенности рассмотрены случаи трёхмерной визуализации пространственных скалярных данных, основным представителем которых в медицине являются томограммы в формате DICOM. Дан обзор программных продуктов, использующихся для анализа данных в медицине, биологии и науке в целом. Проанализированы возможности программного обеспечения различных томографов в трёхмерной визуализации медицинских данных. Рассмотрены подходы предклассификации, постклассификации и предынтегрирования в объёмном рендеринге. Основное внимание уделено группе методов на основе испускания лучей (Ray Casting), а также математическому содержанию метода, реализующего процесс накопления цвета вдоль каждого луча х(7), как процесс интегрирования скалярного поля, преобразуемого функцией классификации (Transfer Function, TF), задающей трехканальный (RGB) цвет C(s) и непрозрачность t(s) для каждого значения скалярного поля ,?(х):

При численном интегрировании вдоль луча методом прямоугольников с шагом с1 для оценки интеграла используется аппроксимация вида:

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

t ft \ /= f C(j(x(/))) xr(s(x(t))) xexp -JY(j(x(i')))di' dt

(1)

л

і-1

Эта аппроксимация сходится к значению интеграла при длине шага луча d—*0. Выбор приемлемой величины шага оказывается зависимым, как от градиента скалярного поля s, так и от внесенных управляемыми условиями визуализации компонентов Transfer Function: функций C(s) и r(s). Вычисления по формуле (2) без специальных мер по адаптивному выбору шага интегрирования в условиях дискретности исходного представления скалярного поля приводят к достаточно большому количеству погрешностей (артефактов) визуализации. Положение усугубляется тем, что для создания эффекта объемного восприятия необходимо моделирование теней для реконструируемого объекта, сопровождающих трехмерное восприятие мира человеком. Устранение артефактов является одной из центральных проблем трехмерной визуализации, возобновляющейся с появлением каждого нового метода. Рассмотрены различные инструментарии использования GPGPU для реализации алгоритма объёмного рендеринга.

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

В разделе 2.1 рассмотрены подходы к визуализации больших массивов данных на GPU. Метод блочной декомпозиции данных исследован как способ визуализации данных большого размера и как способ оптимизации рендеринга, алгоритмизовано его применение как базового подхода в реализации метода испускания лучей. Предложено решение записи блоков данных для вычислений в форме текстур, автоматически обеспечивающее для применения на GPU кэширование доступа к блокам. Предложен алгоритм бесшовной визуализации (рендеринга) блочных данных, в сочетании с освещением методом теневых карт. Толщина перекрытия блоков для бесшовной визуализации зависит от используемого алгоритма затенения и метода фильтрации: например, в случае затенения по модели Фонга и трикубической фильтрации толщина перекрытия составит 3 вокселя.

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

рендеринге, подгонка граничных блоков и правило сохранения единой длины шага луча (d) на всём пути луча для гладкой стыковки блоков (рис.2.1).

Проведено исследование по выбору оптимального размера регулярного блока декомпозиции данных, показавшее, что оптимальный с точки зрения производительности размер блока увеличивается вместе с производительностью GPU (рис.2.2). Для массива данных размером 512x512x5382 (12-bit) и разрешении экрана 1920x1018 достигнута скорость рендеринга 13-20 fps (GeForce GTX 580 3GB).

данных (слева); иллюстрация трассировки луча внутри блоков. Сохраняя единую длину шага луча (ф на всём пути луча (справа), избегаем артефактов на стыках блоков

Рис. 2.2: Визуализация тестовых массивов данных размеров от 512x512x420 до 512x512x5382 (12-bit).

FPS

2E,00

Block

size ■ 32

15,00

20,00

10,00

0,00

5,00

■ 256

■ 96

■ 128

■ 64

■ 48

GeForce G~S 250

GeForce GTX 580

Рис. 2.3. Средняя производительность рендеринга при различных размерах блоков. Для разных видеокарт оптимальный размер блока разбиения может сильно различаться (эксперименты существенно различались объемом данных в пользу

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

Для оценки артефактов выборки мы вычисляем ошибку в каждом пикселе. Для этого методом испускания лучей с применением техники случайного старта луча (jittering) производится рендеринг серии изображений с одного и того же ракурса. Таким образом, каждому пикселю соответствует серия RGB-значений. Степень разброса этих значений характеризует ошибку пикселя. Для вычисления ошибки пикселя использованы величины дисперсии (ГУ) цвета в цветовых пространствах YCbCr и HSL. Для каждого пикселя с координатами (х,у) дисперсия вычисляется следующим образом:

GTX).

т

т

Здесь Т - число изображений в серии, С,(х,у) - цвет пикселя с координатами (х,у) из i-oro изображения. Стоит отметить, что вместо математического ожидания в формуле может быть использован цвет пикселя изображения С (ground truth image), полученного с максимально возможной частотой выборки:

т

£>(*, У) = ^ \Шх,у) - С(х, у)Iр (=i

Для оценки ошибки изображения в целом использовано пиковое

отношение сигнала к шуму (PSNR - Peak Signal-to-Noise Ratio), которое

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

сжатии изображений с потерями. В объёмном рендеринге этот подход был

использован ранее, но для оценки ухудшения качества при сжатии самих

объёмных данных, а не для оценки артефактов рендеринга:

, „, m—ln-l

(МАХ}\ 1 V V

Г £=0 /=0

D(iJ) - дисперсия или квадратичная ошибка пикселя (ij), качество которого мы оцениваем, MSE - среднеквадратическая ошибка изображения размером m х п, MAXi - максимально возможное значение пикселя, в нашем случае равное 1, N - количество нефоновых пикселей, которое в нашем случае N<т п, так как есть смысл игнорировать фоновые пиксели, которые не содержат шума и ошибка в них будет нулевая. Таким образом, оценка качества визуализации проводится с помощью оценки дисперсии пикселей. Кроме того, можно оценивать качество каждого отдельного пикселя для построения PSNR-карт. Понятие PSNR в итоге адаптировано для анализа качества изображений объёмного рендеринга. Точность вычисления PSNR зависит от Г и N. С высокой степенью корреляции (>0.9) среднеквадратичная ошибка вычисления PSNR зависит линейно от величины (TNJ~'.

PSNR: lOdB; PSNR: 20dB; PSNR: 30dB PSNR: 40dB;

SR: 1.2; SR: 2.2; Ж: 4.3; Ж: 6.9;

Рис. 2.4. Качество рендеринга при различных выборах частоты выборки БЯ (синие и зелёные области указывают на хорошее качество рендеринга).

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

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

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

Рис. 2.5. Диаграммы соотношений качество-производительность (усреднённый результат) для случая использования трилинейной фильтрации. Каждая линия соответствует одной из техник КауСаБйгщ-а. Слева диаграмма для случаев без использования локального освещения в алгоритмах, справа - с использованием.

Результат рендеринга; РЯЖ: 36.4с1В; РЯЖ: 22. Ш;

(с освещением) (без освещения) (с освещением)

Рис. 2.6: Карты РБЫЯ для метода предынтегрированного рендеринга без локального освещения (в середине) и с ним (справа); частота выборки: 2. Из-за грубого учёта затенения в предынтегрированном рендеринге возникают артефакты.

интенсивность

— • — • — Реальная интенсивность -~—■ Кубическая интерполяция интенсивности

луч

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

Ш 00

(а) (б)

Рис. 2.8. Иллюстрация причины артефактов фильтрации в объёмном рендеринге. Двумерный массив заполнен значениями 1 (белые точки) и 0 (серые точки). Данный пример демонстрирует различия между билинейной (а) и бикубической (б) интерполяциями. Три чёрные изолинии на каждом из графиков построены для значений 0.25, 0.5 и 0.75.

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

В разделе 3.1 предложен метод сфер для анализа локальной морфологии биологических объектов.

Отношение площади к объёму (Surface-to-Volume Ratio, SVR) характеризует обмен клетки с внешней средой и, чем SVR больше, тем он интенсивнее. Описан алгоритм вычисления части объёма внутренности и площади исследуемой полигональной поверхности, находящейся внутри произвольной сферы. Введено определение скалярного поля SVR на

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

Предложен алгоритм вычисления объёма тела &, ограниченного сложной полигональной поверхностью и сферой, в котором в отличие от классического метода Монте-Карло, для понижения размерности задачи объём тела 0 вычисляется через интегрирование по его поверхности 5, а не по объёму. Показана связь алгоритма с формулой Остроградского:

= |

9 5

Р ■ N dS ^ ¥(&)

Причём векторное поле Р выражается следующим образом:

Р(Х) =Х (1 - \ЩХ)\3/ \Х\3) /3

где ЩХ) - это функция от X, точка пересечения луча (Р, Р+Х) со сферой. \Я(Х)\ — это расстояние до точки пересечения со сферой. Для повышения точности работы алгоритма точка Р (названа опорной точкой) выбирается выбирается из множества пробных точек, сгенерированных датчиком случайных чисел внутри сферы, как можно дальше от треугольников поверхности. Доказано, что дивергенция поля Р равна единице во всей области определения Б, т.е. везде, кроме точки Р. В итоге, для вычисления объёма тела в мы вычисляем поток поля Р через поверхность

Р»1!(Х|

Рис. 3.1. Зависимость Я(Х) от X (слева); Схема сечения сферой О для вычисления 5УЩХ). Жирным выделена часть поверхности О, площадь которой вычисляется, зелёным помечена область, объём которой вычисляется (справа).

Для вычисления значения БУИ в точке X с применением предложенного интегрирования по поверхности, выполняются следующие 4 основные шага:

1) Создание подмножества треугольников Т, пересекающих, либо находящихся внутри секущей сферы;

2) Вычисление площади той части треугольников Т, которая находится внутри секущей сферы;

3) Нахождение опорной точки Р, находящейся внутри сферы и по возможности удалённой от треугольников Т;

4) Вычисление объёма фигуры, ограниченной треугольниками Т и сферой путем интегрирования по поверхности треугольников Т.

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

В параллельном алгоритме для GPU в каждом потоке вычислялась величина SVR и, соответственно площадь и объём дня своей вершины (для каждой вершины организовывался свой поток). Хранение геометрической модели биологического объекта (астроцита) организовано в двух 4-канальных текстурах размером 5122, соответственно для хранения вершин (координат) и треугольников (индексов вершин). Дополнительно в отдельной текстуре хранятся опорные точки Р — каждой вершине соответствует одна опорная точка, которая используется при вычислении объёма. Опорные точки формируются заранее и записываются в текстуру.

Число вершин в полигональной модели реального астроцита насчитывает порядка п=105 вершин (треугольников). Вычислительная трудоемкость задачи составляет 0(п2). Для обеспечения работоспособности графического процессора применен блочный метод загрузки тестируемой порции треугольников поверхности биологического объекта, при котором каждый поток обрабатывает только часть от всех треугольников поверхности, т.е. текстура с треугольниками обрабатывается блоками. Исследована зависимость производительности и работоспособности алгоритма от размеров блока. Построена таблица (таблица 3.1), определяющая зону неработоспособности (помечена знаком «х» - отказ драйвера GPU) и позволяющая выбрать размеры блока оптимальные или близкие к оптимальным.

Таблица 3.1. Зависимость времени работы (в минутах) GPU в алгоритме раскраски модели астроцитов (57 406 вершин, 115 753 тр.) от размеров блока (ширина, высота)

^^^ -ДПирина 1 8 16 32 64 128 256 512

Высота "^^ 2 4

1 31,87 17,43 10,07 6,26 4,48 3,18 2,46 1,99 1,66 1,48

2 16,90 9,71 5,92 4,04 3,01 2,42 1,92 1,67 1,48 1,38

4 9,34 5,81 3,84 2,84 2,29 1,87 1,66 1,50 1,39 X

8 5,50 3,71 2,70 2,21 1,81 1,59 1,48 1,39 X X

16 3,75 2,64 2,04 1,69 1,53 1,43 1,36 1,30 X X

32 2,40 1,88 1,51 1,36 1,24 1,15 1Д2 X X X

64 1,69 1,42 1,21 1,10 1,04 1,01 X X X X

128 1,18 0,95 0,85 0,80 0,78 X X X X X

256 0,82 0,73 0,70 0.67 0,65 X X X X X

512 0,87 0,81 0,76 X X X X X X X

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

методом Монте-Карло - CPUV , оптимизированный с интегрированием по поверхности методом Монте-Карло - CPUs, оптимизированный для GPU. Тестирование проводились как на модели реального астроцита, так и на трех сравнительно небольших тестовых объектах (рис.3.2)

Таблица 3.2. Время расчёта SVR во всех вершинах модели при различных способах вычисления объёма и сравнение с реализацией вычисления SVR на GPU

Примеры моделей (Рис.6) [вершины, треугольники] CPUy Гмин! CPUs [мині GPUS Гмині Ускорение GPUs/CPUs Ускорение GPUs/CPUv

57 406 вершин, 115 753 тр. 1294,89 294,03 4,79 61,40 270,38

408 вершин, 822 тр. 5,47 1,12 0,10 11,39 55,51

364 вершин, 728 тр. 0,86 0,18 0,04 4,33 20,43

1 364 вершин, 2 724 тр. 8,06 1,62 0,17 9,77 48,59

(2) (3) (4)

Рис.3.2. Тестовые полигональные поверхности: (1) астроцит - см. на рис.3.3. Сферы рядом с моделями показывают, какой радиус сферы использовался в эксперименте

Рис.3.3. SVR-раскраска поверхности астроцитов методом сфер с радиусом сферы

600HM.

В разделе 3.2 возможности метода сфер апробированы на исследовании морфологии астроцитов мозга мыши реконструированного в 3D со сканов электронного микроскопа с разрешением 8 нм и толщиной среза -80 нм, отличающихся сложной геометрической формой (см. рис.3.3). С помощью анализа SVR поверхности астроцитов можно выяснить, располагаются ли астроциты таким образом, чтобы иметь возможность поглотить больше медиатора через свою поверхность. В результате выявлены зависимости различных свойств астроцитов от расстояния до ближайшего синапса (до постсинаптического уплотнения, PSD). На рис.3.4 показаны все объекты, участвующие в эксперименте по исследованию отношений «астроцит-синапс», «астроцит-депо кальция», «синапс-депо кальция».

Рис.3.4. Визуализация исследуемых биологических объектов (серые дендритные шипики, красные PSD, зелёные астроциты, синие и жёлтые депо кальция).

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

о 500

н

= 400

ZOO

S 10 1 5 20 25 ЗО 35 40

SVR астроцита (ції)'1)

100 200 300 400 500 ООО

Расстояние до PSD (nm)

Рис.3.5. Медиана и квартили для: расстояния до Р5П(8УК), зависимости доли объёма астроцита в пространстве от расстояния до синапса для тонких и крупных шипиков.

0.20

0.18

ж 0 16

5 — 0.14

% 0.12

ас К 0.10

х ф 0 08

О 0.00

І2. CZ 0.04

0 02

006

- 0.05

g

2 0 04

—1—1 10

-т— 15

20

-г-25

-г 30

і

35

0 02 0.01 О

lllluu

SVR астроцита ((.mr1)

10 20 ЗО

SVR астроцита (цпГ1)

40

Рис. 3.6. Зависимость (медиана и квартили) содержания кальция в астроците от SVR поверхности астроцита (слева) и гистограмма SVR астроцита (справа).

В четвертой главе дано описание программного комплекса. В разделе 4.1 описаны функциональные его свойства, в том числе, доступные в разработанной системе способы визуализации и анализа данных. Благодаря использованию метода испускания лучей доступно большое количество различных техник визуализации данных (алгоритмов накопления цвета). Реализованы техники: 1) проекция максимальной интенсивности (MIP); 2) проекция минимальной интенсивности (MinIP); 3) имитация рентгеновского снимка; 4) метод прямого объёмного рендеринга (DVR); 5)непрозрачная затенённая изоповерхность (SSD); 6)серия полупрозрачных изоповерхностей и др. Доступен множественный вывод, т.е. визуализация различными алгоритмами в разные части окна. Каждая область вывода снабжена своими настройками: передаточная функция (Transfer Function), параметры для полупрозрачных изоповерхностей, центр и ширина окна (т.е. яркость и контрастность) и т.д. Система также может быть использована сторонними программными продуктами путём запуска программы с указанием необходимых параметров.

В разделе 4.2 описана архитектура комплекса, состав модулей системы и связь между ними. Раскрываются особенности архитектуры части системы, работающей с GPU, т.е. модуля трёхмерной визуализации. Описана структура шейдерных программ на языке GLSL (шейдерный язык OpenGL) для трассировки луча, приведён список используемых переменных и макросов, используемых в алгоритмах.

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

Основными результатами исследования являются следующие:

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

Предложен, реализован и исследован новый метод морфологического анализа геометрически сложных клеток мозга - астроцитов.

В ходе работы получены в частности следующие новые результаты:

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

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

3) Исследованы оценки качества (дефектов) изображения, принятые в теории сигналов, 2D и 3D сжатии, в оценке качества видео. На основе вычислительного эксперимента для 3 типов оценки (PSNR, SNR, SSIM) рекомендована, и адаптирована для задачи количественной оценки качества объёмной визуализации, логарифмическая оценка, подобная пиковому отношению сигнала к шуму (PSNR - Peak Signal-to-Noise Ratio). На основе этой оценки проведено сравнительное исследование ряда методов построенных на основе алгоритма Ray Casting.

4) Предложен и исследован метод морфологического анализа объекта, локально оценивающий эффективность взаимодействия со средой в каждой точке поверхности объекта величиной отношения площади к объёму (Surface-to-Volume Ratio) внутри пространства, ограниченного сферой заданного радиуса с центром в оцениваемой точке.

5) Создан программный комплекс, реализующий разработанные модели и алгоритмы, готовый к практическому использованию в подсистемах 3D- и стерео- визуализации данных в медицине, биологии, физике, инженерном анализе. Комплекс используется: институтом прикладной физики РАН в задачах научной визуализации; производителем медицинского программного обеспечения ООО «ПО ВИДАР» в составе поставляемой им медицинской информационной системы; внедрен в учебный процесс ННГУ им. Н.И. Лобачевского.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Статьи в изданиях, рекомендованных ВАК

1. Гаврилов, Н.И. Турлапов, В.Е.. Оценка качества визуализации медицинских и научных данных в величинах отношения пикового сигнала к шуму // Вестн. Нижегородского гос. университета. Информационные технологии. 2012.-№5(2), с. 264-273

2. Гаврилов, Н.И., Турлапов, В.Е., Патрушев, И.В., Семьянов, A.B. Локальное численное исследование морфологии 3d реконструкций биологических объектов в величинах svr - отношения площади к объему // Вестн. Нижегородского гос. университета. Математическое моделирование и оптимальное управление - 2012.-№5(2), с. 47-56

Публикации в других изданиях

3. Gavrilov, N.I., Turlapov, V.E., General implementation aspects of the GPU-based volume rendering algorithm II Scientific Visualization, 2011, Quarter: 1, Vol. 3,N. 1,P. 19-32

4. Гаврилов, Н.И., Турлапов, B.E. Подходы к оптимизации gpu-алгоритма volume raycasting для применения в составе виртуального анатомического стола II Scientific Visualization, 2012, Кв. 2, Т. 4, № 2, С.21 - 56

5. Gavrilov, N., Turlapov, V. Advanced GPU-based Ray Casting for Bricked Dataset И Proc. ACM SIGGRAPH'2012, 5-9 Aug 2012, Los Angeles. Posters Article No. 123. ACM New York, NY, USA, 2012. ISBN: 978-1-4503-1682-8

6. Гаврилов, Н.И., Иерархические SD-текстуры в реализации метода трассировки лучей на GPU для качественной стереовизуализации томограмм И Материалы конференции «Технологии Microsoft в теории и практике программирования» Н.Новгород, 13-14 мая, 2010, стр.58-60

7. Гаврилов, Н.И. Качественная визуализация на основе шейдеров II Материалы конференции «Вычисления с использованием графических процессоров в биологии и биоинформатике», Московский

государственный университет имени М.В.Ломоносова. 24-25 мая 2010, стр. 42-44

8. Гаврилов, Н., Белокаменская, А. Стерео-визуализация научных и медицинских объемных данных трассировкой лучей в реальном времени И Материалы конференции ГрафиКон'2010, 20-24 сентября, Санкт-Петербург, Россия. С.350-352

9. Гаврилов, Н., Белокаменская, А. Организация потоковых вычислений на GPU в задаче стереовизуализации томограмм II Материалы X Международной конференции "Высокопроизводительные параллельные вычисления на кластерных системах" 1-3 ноября 20 Юг, Пермь, Россия, стр. 58-61

10. Turlapov, V.E., Bogolepov, D.K., Gavrilov, N.I. High Performance Engine for 3D-Visualization and Reconstruction of Volumetric Data in Biomedicine II Proc. of 1П International Symposium Topical Problems of Biophotonics - 2011, 16-22 July 2011, St.-Petersburg - Nizhny Novgorod . P. 110-111

11. Gavrilov, N., Belokamenskaya, A., Turlapov, V. Several approaches for improvement of the Direct Volume Rendering in scientific and medical visualization II Материалы конференции ГрафиКон'2011, 26-30 сентября, Москва, Россия. С. 88-91

12. Гаврилов, Н.И., Турлапов, В.Е. Повышение качества и производительности трёхмерной визуализации томограмм II Материалы XI Международной конференции "Высокопроизводительные параллельные вычисления на кластерных системах" 1-3 ноября 2011г, Нижний Новгород, Россия, стр. 63-67.

13. Гаврилов, Н.И., Турлапов, В.Е. Качественная объёмная визуализация гигавоксельных массивов в блочном представлении на примерах данных из медицины // Материалы конференции ГрафиКон'2012, 1-5 октября, Москва, Россия. С. 174-179

Личный вклад автора. Степень личного участия соискателя в публикациях (№ - печ. листов): 1 - 0,9 п.л.; 2 - 0,9; 3 - 1,26; 4 - 3,4; 5 - 0,1; 6 -0,13; 7 - 0,13; 8 - 0,16; 9 - 0,34; 10 - 0,11; 11 - 0,28; 12 - 0,39; 13 - 0,51. Все научные результаты, выносимые на защиту, получены Н.И.Гавриловым лично. Является автором всех алгоритмов и системных решений, выносимых на защиту, в коллективных работах выполнял роль лидера в части выносимой на защиту. Научному руководителю, принадлежит участие в постановке задачи и работе над окончательным видом публикаций.

Подписано в печать 18.04.2013. Формат 60 х 84 Vie. Бумага офсетная. _Печать офсетная. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ 314._

Нижегородский государственный технический университет им. P.E. Алексеева. Типография НГТУ. 603950, ГСП-41, г. Нижний Новгород, ул. Минина, 24.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ

ФЕДЕРАЦИИ

Нижегородский государственный университет им. Н.И.Лобачевского

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

04201360625 ГАВРИЛОВ Николай Игоревич

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

медицине и биологии

Специальность: 05.13.17 - «Теоретические основы информатики» по

техническим наукам

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель: доктор технических наук Турлапов В.Е.

И130611145637

Нижний Новгород -2013

Аннотация

Целью диссертационной работы является развитие теоретических основ и технологий визуализации пространственных научных и медицинских данных. В работе предложен метод численной оценки качества визуализации методом прямого объёмного рендеринга. На основе этой оценки проведено сравнительное исследование ряда известных оптимизированных вариантов алгоритма Ray Casting. Предложены и исследованы модификации этих алгоритмов, развивающие подходы к устранению артефактов визуализации. Также развит известный метод блочной декомпозиции данных: реализован оптимальный обход блоков, использованы оптимизированные по объему вспомогательные структуры для пропуска пустых областей (empty space leaping). Описаны функции, архитектура и информационно-технологические решения системы для 3D визуализации и анализа томограмм.

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

Оглавление

Введение 7

Глава 1 Обзор методов и программного обеспечения по теме исследования 12

1 1 Задача трехмерной визуализации скалярных и векторных полей в медицинской и научной визуализации в целом 12

111 Визуализация скалярных полей, заданных на регулярных и нерегулярных сетках 12

Задание исследуемых полей на регулярных и нерегулярных сетках 13

112 Задача трехмерной визуализации векторных полей в медицине и науке в целом 14

113 Современные особенности данных и задач трехмерной визуализации в медицине 17

1 2 Программные комплексы для трехмерной визуализации в медицине 21

12 1 Пакеты программ для научной визуализации 22

12 2 Пакеты программ для медицинской визуализации 24

12 3 Исследовательские системы объемного рендеринга и системы реалистичного объемного рендеринга для фотореалистичной ЗБ-визуализации медицинских данных

28

1 3 Обзор методов прямого объемного рендеринга 30

13 1 Методы, разработанные до появления технологии вычислений на графических процессорах бросания снежков, сдвига-деформации, слоев 30

13 2 Основной современный метод объемной визуализации, метод испускания лучей - ray casting, и его возможности 33

13 3 Интегрирование классифицированных данных скалярного поля вдоль луча, как основная математическая модель объемного рендеринга 38

1 3 7 Проблема предклассификации и постклассификации 39

13 8 Мультиобъемный рендеринг 42

13 9 Многомерные передаточные функции 44

13 10 Основные технологии программирования GPU для задач объемного рендеринга 45

1 4 Количественное исследование морфологии 3D реконструкций биологических объектов 46

1 5 Выводы к Главе 1 48

Глава 2 Система методов высокопроизводительной 3D визуализации томограмм, их взаимодополняющая модификация и адаптация для графических процессоров 49

2 1 Модификация метода блочной декомпозиции для GPU с целью повышения производительности и сохранения качества объемного рендеринга 49

2 11 Решение проблемы сохранения необходимой степени непрерывности данных

при декомпозиции данных на блоки 49

2 12 Анализ проблем реализации метода блочной декомпозиции в условиях

сохранения высокого качества 3D визуализации 50

2 1 3 Методы устранения дефектов визуализации на границах блоков 52

2 1 4 Методы обеспечения моделирования локального освещения и теней при

блочной декомпозиции данных 54

2 15 Методы ускорения вычислений для алгоритма испускания лучей в условиях

блочной декомпозиции 56

2 16 Метод отсечения невыпуклой полигональной сеткой и ее использование в

качестве ускоряющей структуры 58

2 17 Адаптация метода пропуска пустых областей для случая блочных данных

Оптимизация порядка обхода блоков 60

2 18 Экспериментальное исследование оптимальных размеров блока разбиения 63

2 2 Исследование методов количественной оценки качества 3D визуализации

медицинских пространственных данных 65

2 2 1 Анализ основных видов дефектов (артефактов) в трехмерной визуализации

томограмм 66

2 2 2 Природа артефактов фильтрации в объемном рендеринге 68

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

71

2 2 3 Сравнительное исследование оценок, применяемых для оценки качества в

смежных областях Пиковое отношение сигнала к шуму 74

2 2 4 Пример применения аналога PSNR для исследования распределение шума на

изображении 75

2 3 Исследование проблемы повышения качества синтеза изображений методом

испускания лучей 76

2 3 1 Стратегии повышения точности интегрирования вдоль луча 77

2 3 2 Зависимость качества и производительности 85

2 3 3 Оптимизация методов рендеринга 86

2 3 4 Сравнение методов рендеринга 89

2 3 5 Влияние способа интерполяции и локального освещения на уровень шума 91

2 3 6 Анализ эффективности суперсэмплинга в методе Ray Casting 92

2 3 7 Влияние шага луча на качество и производительность 94

2 3 8 Отслеживание артефактов рендеринга 95

2 3 9 Применение метрики SSIM в компьютерной графике 96

2 3 10 Способы количественной оценки артефактов фильтрации в объемном

рендеринге 97

4

2 3 11 Возможность использования метрик PSNR и SSIM для выявления наличия

артефактов фильтрации в объемном рендеринге 99

2 3 12 Выбор размера окна в SSIM для адекватной оценки качества изображения 100

2 4 Выводы к Главе 2 102

Глава 3 Разработка высокопроизводительного метода исследования морфологии

биологических объектов 104

3 1 Метод сфер для анализа морфологии сложных биологических объектов в величинах SVR 104

3 11 Оценка локального SVR геометрических объектов в окрестности произвольной точки пространства 105

3 12 Вычисление объема геометрического тела методом Монте-Карло 106

3 13 Связь предложенного алгоритма вычисления объема интегрированием по

поверхности с формулой Остроградского 108

3 14 Использование псевдо- и квазислучайных последовательностей чисел в 110

3 15 Алгоритм вычисления локального SVR на графических ускорителях и его

реализация 113

3 2 Пример применения метода сфер для морфологического анализа и исследования

локальных свойств астроцитов 119

3 2 1 Зависимость SVR от расстояния до синапса в отношении «синапс-астроцит» 119

3 2 2 Зависимость содержания EPR в астроците от расстояния до синапса 120

3 2 3 Зависимость SVR астроцита от расстояния до синапса 123

3 24 Зависимость содержания EPR в астроците от SVR астроцита 125

3 2 6 Оценка размера шипика 126

3 3 Выводы к Главе 3 128 Глава 4 Создание системы трехмерной визуализации медикобиологических данных 129

4 1 Функциональная характеристика системы 129 411 Синтез отображения данных несколькими методами одновременно 129

4 12 Возможности работы с передаточными функциями и их развитие 130 4 13 Использование ортогональной и перспективной проекций в системе 131 4 14 Совместный рендеринг объемных данных и полигональной геометрии 131 4 15 Возможности мультиобъемного рендеринга, реализованные в системе 132 4 16 Возможности стереовизуализации в системе 133 4 17 Возможности работы с DICOM-форматом 134 4 18 Поддержка бинарного формата исходных данных 136 4 19 Вызов системы из программной строки 137

4 110 Выделение области интереса на томограмме невыпуклой полигональной

сеткой управляемой пользователем 138

4 111 Вычисление объемов, заданных плоскими замкнутыми контурами 138

4 1 12 Мультиплоскостная реконструкция (МПР) и инструменты измерений в 1пУо1э

139

4 2 Архитектура программного комплекса 139

42 1 Исследование рациональной организации шейдерной программы 139

4 2 2 Схема работы подсистемы визуализации 143

4 2 3 Основные программные модули системы 147

4 3 Выводы к Главе 4 148

Заключение 149

Список литературы 152

Приложение А Используемая терминология 165

Приложение Б ОЬБЬ код шейдерной программы, вычисляющей площадь и объем

полигональной поверхности внутри сфер 167

Введение

Актуальность темы исследования

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

Во многом причина резкого роста связана с перерастанием количества в качество: количественных характеристик применяемых приборов и вычислительной техники - в появление трехмерных технологий обработки, визуализации и исследования данных, и, на этой базе, в создание новых трехмерных методов человеко-машинного общения. Так, превращение компьютерной томографии (KT) в многосрезовую компьютерную томографию (МСКТ) с выходом в свет 320-срезового томографа (2007, Toshiba), способного выполнить томографию всего тела человека с толщиной среза менее 1 мм за время около 10-15 секунд, фактически поставило на поток получение данных для трехмерного моделирования пациента в медицине. Компания ШМ, мировой лидер производства суперЭВМ, в 2008-2009 стартовала и продолжает до сих пор проекты (Smarter Planet) по использованию 3D модели пациента, как основы его медицинской карты. В 2012 ЮМ стартовала проект по моделированию действия лекарств на 30-аватаре конкретного человека.

Увеличение производительности ЭВМ и производительности алгоритмов сделало возможным совмещенную обработку (fusion) и 3D реконструкцию сразу двух и более томограмм обычного объема в реальном времени, появились томографы ведущих мировых производителей способные совместно исследовать ЗО-реконструкции KT и ПЭТ (позитрон-эмиссионных) или KT и ОФЭКТ (однофотонных эмиссионных), или KT и ФМРТ (функциональных МРТ) томограмм. Неоценимую поддержку способны оказать технологии трехмерной реконструкции томограмм в медицинском образовании. Так, в США в мае 2011 года появилось экспериментальная модель виртуального анатомического стола (Anatomage Table, http://anatomage.com), базовой функцией которого является интерактивная 3D реконструкция пациента в полный рост по данным томографии. Появилась теоретическая возможность слить данные всех существующих методов диагностики в одной трехмерной модели пациента.

Сегодня существует довольно много подходов, развитых в работах следующих ученых: Klaus Engel, Bernhard Kainz, Daniel Ruijters, Stefan Guthe, Johanna Beyer, Vincent

Vidal, Markus Hadwiger, Daniel Weiskopf, Thomas Ertl, Wolfgang Strasser, Byeonghun Lee, Jihye Yun, Jinwook Seo, Yeong-Gil Shin, Bohyoung Kim, Byonghyo Shim и др., позволяющих производить объёмную визуализацию в реальном времени с использованием вычислений на GPU. Мировой рынок предлагает в составе томографов несколько программных систем, обеспечивающих слияние и трехмерную визуализацию томограмм. Эти коммерческие системы используют наиболее производительные версии коммерческих 3D визуализаторов.

То же самое можно сказать о росте информационного потока и необходимости построения производительных методов его обработки в биологии. Наиболее критическое положение, из-за огромного объема данных, наблюдается в трехмерной обработке данных с электронного микроскопа с разрешением в единицы нанометров. В качестве примера объемов подлежащих обработке можно привести общедоступный Интернет-ресурс с данными электронной микроскопии фрагмента мозга мыши объемом в 12 терабайт (http://openconnectomeproject.org). Особенно ресурсоемкими здесь являются задачи морфологического анализа реконструированных клеток.

Несмотря на значительный прогресс в решении упомянутых выше задач существует и ряд нерешенных проблем:

• качественная трехмерная визуализация томограмм «привязана» сегодня к томографу из-за высоких требований к производительности рабочей станции, но недоступна рядовому врачу-клиницисту и, тем более, студенту, - необходим переход к программному обеспечению и технике массовой доступности без потери качества визуализации;

• объем томограмм, доступных для 3D реконструкции на GPU, ограничен размером памяти GPU (сегодня для массовых офисных видеокарт в продаже - это 1-2 GB), в то время как постоянный рост данных требует снятия ограничения на их объем и построения алгоритмов декомпозиции для параллельной поблочной обработки данных с сохранением всех возможностей и качества визуализации;

• несмотря на рост производительности и качества 3D визуализации отсутствует практика количественной оценки качества визуализации;

• существует несколько открытых и коммерческих программ для полуавтоматической трехмерной геометрической реконструкции клеток, но нет методов и программ для автоматизации детального морфологического анализа клетки, в то время как вычислительная сложность такого анализа в величинах SVR (Surface-to-Volume Ratio) пропорциональна квадрату числа вершин или

2 с

треугольников 0(п ) при характерных значениях п~10 треугольников.

8

Цели и задачи исследования

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

Поставленная цель требует решения следующих задач:

1) Провести анализ существующих методов трёхмерной визуализации в медицине, и науке в целом, анализ подходов к повышению качества и производительности 3D-визуализации.

2) Развить существующие методы для их взаимодополняющего применения в условиях бюджетных GPU и создания технологии ЗО-визуализации для массового применения в медицине, в том числе:

2.1) Разработать модификацию метода блочной декомпозиции гигавоксельных (более 10^ вокселей) данных для визуализации на GPU, сохраняющую возможности и качество визуализации недекомпозированных данных (возможность применения трикуби-ческой интерполяции, освещения, отбрасывания теней, пропуска пустых областей, различных условий интегрирования вдоль луча,...)

2.2) Развить методы повышения производительности 3D визуализации и подавления различного рода дефектов (артефактов) визуализации рациональные в условиях GPU

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

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

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

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

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

Методы исследования

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

Научная новизна работы заключается в том, что:

1) Выполнена модификация метода блочной декомпозиции данных в алгоритме Ray Casting, отличающаяся оптимальной последовательностью обхода блоков, использованием оптимизированных по объему вспомогательных структур метода пропуска пустых областей (empty space leaping), обеспечением возможности построения локального �