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

Сжатие научных данных большого объема для обеспечения возможности их визуализации

Печать E-mail
Автор С.В. Муравьев   
27.04.2009 г.

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

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

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

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

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

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

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

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

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

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

Сжатие биологических данных

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

Сжатие биологических данных - 2

Параллельный алгоритм сжатия трехмерных скалярных

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

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

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

Последнее обновление ( 27.04.2009 г. )
 
« Пред.   След. »