Например, Бобцов

МЕТОД СЖАТИЯ ТРЕХМЕРНЫХ БИОМЕДИЦИНСКИХ ИЗОБРАЖЕНИЙ НА ОСНОВЕ ПРЕДСТАВЛЕНИЯ ИНФОРМАЦИИ В ФОРМЕ ОКТОДЕРЕВА

И.Н. Жданов, А.С. Потапов, О.В. Щербаков

УДК 004.932.2
МЕТОД СЖАТИЯ ТРЕХМЕРНЫХ БИОМЕДИЦИНСКИХ ИЗОБРАЖЕНИЙ НА ОСНОВЕ ПРЕДСТАВЛЕНИЯ ИНФОРМАЦИИ В ФОРМЕ ОКТОДЕРЕВА
И.Н. Жданов, А.С. Потапов, О.В. Щербаков
Рассмотрен метод сжатия без потерь трехмерных биомедицинских изображений на основе их представления в форме октодерева. Предложена модификация метода, реализующая сжатие с потерями с использованием предварительной фильтрации и подавления шума. Показано, что предлагаемый метод превосходит по эффективности методы сжатия двумерных изображений как с потерями, так и без потерь (JPEG и PNG), примененные к трехмерным изображениям послойно. Ключевые слова: сжатие изображений, биомедицина, октодерево.
Введение
Использование трехмерных данных становится все более распространенным в самых разнообразных информационно-телекоммуникационных системах. В частности, большое значение такие данные приобретают для биомедицинских систем, в которых объемные изображения биологических тканей несут важную информацию для проведения диагностики заболеваний. При этом сложность задач хранения информации и ее передачи по каналам связи в случае трехмерных изображений оказывается существенно выше, и одной из основных проблем становится эффективное представление трехмерных данных. При решении этой проблемы, однако, в качестве основы используются преимущественно традиционные представления изображений. Например, в работе [1] рассматривается алгоритм сжатия трехмерных изображений, основная идея которого состоит в преобразовании трехмерных изображений в двумерные и в последующей их компрессии с использованием известных алгоритмов – JPEG и PNG. Представления, разработанные для двумерных изображений, могут быть неоптимальными в случае трехмерных изображений, поэтому они дополняются некоторыми элементами, повышающими их эффективность.
В частности, в работе [2] предложен двухэтапный метод компрессии изображений, основанный на сжатии разных областей изображения с разными параметрами качества. На первом этапе осуществляется выделение «областей интереса» на изображении. На втором этапе осуществляется компрессия изображения с помощью JPEG, при этом для «областей интереса» и остальных областей используются разные параметры качества.
Повышение эффективности сжатия может достигаться путем замены дискретного косинусного преобразования вейвлет-преобразованием. Однако при этом в случае многослойных изображений центральными становятся вопросы быстродействия. В частности, в [3] предложен гибридный алгоритм, основанный на применении дифференциальной импульсно-кодовой модуляции, целочисленных вейвлетпреобразований и вейвлет-преобразований с вложенными нуль-деревьями. Для решения проблем быстродействия подобные кодеки приходится реализовывать на спецпроцессорах.
Альтернативным (но тоже уже достаточно традиционным) является фрактальный подход к сжатию. Так, в работе [4] предложен метод компрессии изображений в спутниковых системах связи, основанный на концепциях мультимасштабного анализа сигналов. Однако исследования авторов [5] показывают, что фрактальные представления являются недостаточно эффективными в случае некоторых классов биомедицинских изображений. Таким образом, в задачах компрессии трехмерных изображений используется весьма ограниченный набор представлений информации, заимствованный из области сжатия двумерных изображений. В этой связи разработка и исследование эффективных представлений трехмерных изображений является весьма актуальной задачей.
Эффективность трехмерных представлений изображений важна при решении не только задач компрессии изображений, но также и задач их реконструкции и визуализации в масштабе реального времени. Для этих целей распространенным является представление в форме октодерева [6, 7]. Эффективность такого класса представлений была по отдельности показана как для описания биомедицинских изображений [8], так и для задач сжатия трехмерных данных [9].
В настоящей работе представлены результаты исследования возможностей компрессии трехмерных биомедицинских изображений с использованием представления в форме октодерева, пригодного для последующей визуализации в масштабе реального времени. Поскольку представление в форме октодерева очень удобно для визуализации, то вполне естественно рассмотреть вопрос хранения информации в такой форме для минимизации вычислительной сложности последующих операций. Показано, что использование представлений в форме октодерева достаточно эффективно для хранения сжатых трехмерных биомедицинских изображений.
Представление трехмерных изображений в форме октодерева
Октодерево является структурой, описывающей последовательное разбиение объема изображения (который обычно ограничен прямоугольным параллелепипедом) на элементы уменьшающегося объема.

Научно-технический вестник информационных технологий, механики и оптики, 2012, № 3 (79)

103

МЕТОД СЖАТИЯ ТРЕХМЕРНЫХ БИОМЕДИЦИНСКИХ ИЗОБРАЖЕНИЙ …
Формирование октодерева удобнее всего описать в рекурсивной форме. В корневом узле октодерева находится весь объем изображения. Далее каждый узел может иметь восемь потомков, если соответствующий элемент объема, или блок (прямоугольный параллелепипед), разделен на подблоки (которые, как правило, берутся равными по размеру и форме). Например, на рис. 1 показано небольшое октодерево, состоящее из четырех уровней, включая корневой узел, и соответствующий результат разделения исходного объема на блоки.

абв
Рис. 1. Пример октодерева: верхний уровень дерева (а); дальнейшее разделение 4-го блока на подблоки (б); структура результирующего октодерева (в)
Для использования представления в форме октодерева в целях сжатия можно предложить следующий алгоритм рекурсивного разбиения. 1. Сформировать октодерево, состоящее из одного корневого узла, соответствующего всему объему
изображения. Пометить данный узел как активный. 2. Для каждого активного узла проверить равенство яркостей всех пикселей в соответствующем блоке
(объеме изображения). Если равенство выполняется, сделать узел неактивным (пометить его как лист), в противном случае породить восемь узлов-потомков, которые пометить как активные, разделив текущий блок на подблоки. 3. Выполнять шаг 2, пока остаются активные узлы на дереве.
В процессе рекурсивного разбиения в файл может отдельно записываться структура октодерева, которая описывается последовательностью битов, указывающих, был ли разбит некоторый блок изображения на подблоки. При фиксированном порядке обхода октодерева никакую дополнительную информацию сохранять не нужно.
Отдельно требуется сохранять яркости пикселей в блоках, соответствующих листьям октодерева. Аналогично, здесь достаточно указывать для каждого листа одно значение яркости и ничего более: при детерминированном порядке обхода октодерева и его известной структуре можно однозначно восстановить яркости всех пикселей.
Файл со структурой октодерева может быть дополнительно сжат, поскольку верхние уровни октодерева, которые, как правило, имеют потомков, будут приводить к записи битов со значением 1 в начале файла, тогда как листья октодерева, не имеющие потомков, будут преимущественно приводить к появлению в конце файла битов со значениями 0. Вместе с тем к файлу, содержащему значения яркости, может быть применено энтропийное кодирование, учитывающее неравномерность гистограммы распределения яркостей. В настоящей работе структура октодерева и яркости в его листьях записывались в два отдельных файла и сжимались с использованием архиваторов общего назначения.
Описанный алгоритм обеспечивает сжатие без потерь, что нередко является необходимым для биомедицинских изображений. Однако полезно также модифицировать алгоритм для осуществления сжатия с потерями. Для этого вполне естественно ослабить условие на то, чтобы внутри блоков яркости всех пикселей были абсолютно одинаковы. Из-за этого условия можно ожидать, что для зашумленных изображений размеры блоков в октодереве будут получаться слишком маленькими (и, соответственно, небольшим окажется коэффициент сжатия).
Достаточно естественно принимать решение о разделении блока на подблоки на основе критерия дисперсии яркостей. При этом вместо использования одного строгого порога на величину дисперсии можно применить адаптивный выбор порога по критерию минимальной длины описания по аналогии с тем, как это было сделано авторами в случае построения квадродерева при фрактальном сжатии двумерных изображений [10].
В случае трехмерных изображений, однако, вычисление значения дисперсии яркостей для каждого блока оказывается неприемлемым из-за существенного снижения быстродействия, поскольку при этом число обращений к каждому пикселю оказывается пропорциональным числу уровней в октодереве. В то же время при использовании требования равенства всех яркостей внутри блоков оказывается необходимым в среднем проверять лишь несколько пикселей в каждом блоке, что для больших блоков, находящихся на верхних уровнях октодерева, приводит к существенному сокращению числа операций.
Поскольку причиной, по которой допустимо использование сжатия с потерями, является отсутствие необходимости сохранять шум, можно в явном виде использовать предобработку изображения путем фильтрации с подавлением шума. Такая фильтрация должна привести к тому, что вариативность

104

Научно-технический вестник информационных технологий, механики и оптики, 2012, № 3 (79)

И.Н. Жданов, А.С. Потапов, О.В. Щербаков
значений яркостей близких точек уменьшится, что облегчит формирование блоков большего размера на октодереве и повысит степень сжатия. Дополнительным преимуществом такого подхода является то, что он не будет (в отличие от традиционных подходов сжатия с потерями) приводить к появлению артефактов сжатия, обусловленных спецификой, например, блочного представления изображений. Поскольку те изображения, для которых разрабатываются данные методы, характеризуются высоким уровнем шума, явное подавление шума как косвенный способ повышения степени сжатия является вполне приемлемым. Здесь нами были рассмотрены простейшие фильтры – медианный и гауссов.
Экспериментальная проверка Для проведения экспериментальной проверки были использованы трехмерные изображения биотканей, полученные с помощью метода оптической когерентной томографии. На рис. 2 показаны несколько слоев (B-сканов) одного изображения (инвертированного по яркости), а на рис. 3 показаны примеры слоев других изображений. Представленные на рисунках изображения имеют размеры 1214×416×500 пикселей (рис. 2), 640×1000×511 пикселей (рис. 3, а), 971×416×400 пикселей (рис. 3, б), 1280×500×92 пикселей (рис. 3, в).
аб
вг Рис. 2. Последовательные слои одного из трехмерных изображений (а–г)
б a
в

Рис. 3. Примеры одного слоя изображений разных объектов (а–в)

В табл. 1 представлены результаты сжатия без потерь представленных изображений с использованием октодерева. Для сравнения приведены размеры архивов, содержащих файлы с B-сканами в PNGформате (данный формат также обеспечивает сжатие без потерь), и объемы несжатых изображений.

Номер изображения
1
2
3
4

Объем (октодерево), МБ
109
174
75
9,2

Объем (PNG), МБ
156
206
105
11,7

Объем (несжатый), МБ
240,8
312
154
56,2

Таблица 1. Результаты сжатия трехмерных изображений без потерь

Как видно, рассмотренный метод компрессии на основе октодерева оказывается эффективным в смысле коэффициента сжатия. Выигрыш по сравнению с форматом PNG составляет 18%–43%.
Рассмотрим теперь вопрос сжатия с потерями. Для оценки потерь использовалась информационная мера, которая оценивалась как количество битов, необходимых для кодирования различий между восстановленным после сжатия и исходным изображениями. Для этого считалась попиксельная разность

Научно-технический вестник информационных технологий, механики и оптики, 2012, № 3 (79)

105

МЕТОД СЖАТИЯ ТРЕХМЕРНЫХ БИОМЕДИЦИНСКИХ ИЗОБРАЖЕНИЙ …

между этими изображениями, строилась гистограмма отклонений, по которой вычислялась энтропия. Эта энтропия, умноженная на число пикселей в изображении, и является информационной оценкой потерь при сжатии.
В табл. 2 приведены объемы файлов, полученные при сжатии с помощью октодерева при различных масках медианного фильтра, а также величины потерь. Результаты сжатия при использовании гауссова фильтра оказались хуже, что связано, видимо, с тем, что при такой фильтрации получаются промежуточные значения яркостей, тогда как при медианной фильтрации происходит замена яркостей некоторых пикселей на яркости соседних пикселей. Последнее позволяет формировать блоки октодерева большего размера. В табл. 3 приведены аналогичные результаты для сжатия методом JPEG. Как видно, уменьшение объема сжатого файла сопровождается возрастанием информационных потерь. При этом при равных объемах сжатых файлов потери при компрессии методом октодерева оказываются более чем на 17% меньше, чем при сжатии JPEG. Для изображения, представленного на рис. 3, в, выигрыш превышает 2 раза, а для изображения на рис. 3, б, выигрыш составляет 7% (при этом при равных информационных потерях коэффициент сжатия методом октодерева в 1,36 раза выше, чем методом JPEG). Однако для изображения на рис. 3, а, при равных размерах сжатых файлов информационные потери более чем в 2 раза оказываются меньшими для JPEG, что может быть связано с особой структурой этого изображения. Таким образом, метод на основе октодерева оказывается в среднем лучше, чем метод JPEG, хотя в случае большой избыточности изображения в частотной области сжатие JPEG может оказаться эффективнее.

Размер маски Объем, МБ Потери, МБ

3 5 7 9 11 13 15 59,9 40,7 34,9 32,4 30,8 29,5 28,3 95,4 100,1 101,7 102,6 103,2 103,6 104,1

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

Качество Объем, МБ Потери, МБ

80 45,5 116,9

60 25,0 129,9

40 15,8 136,2

20 6,67 149,5

Таблица 3. Результаты сжатия JPEG с разными значениями параметра качества Заключение

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

1. Karpinsky N., Zhang S. Composite phase-shifting algorithm for three-dimensional shape compression // Opt. Eng. – 2010. – V. 49. – P. 063604.
2. Shao X., Gao K., Lv L., Ni G. A new efficient method for color image compression based on visual attention mechanism // Proc. of SPIE. – 2010. – V. 7850. – P. 78501G.
3. Fan J., Zhou J., Chen X., Shen W. Hyperspectral image data compression based on DSP // Proc. of SPIE. – 2010. – V. 7850. – P. 78500H.
4. Bagmanov V., Kharitonov S., Meshkov I., Sultanov A. Multiscale image compression for satellite telecommunication systems // Proc. of SPIE. – 2008. – V. 7026. – P. 70260E.
5. Гуров И.П., Окунев В.В., Потапов А.С. Исследование эффективности фрактальных методов компрессии биомедицинских изображений с помощью принципа минимальной длины описания // Изв. вузов. Приборостроение. – 2011. – Т. 54. – № 12. – С. 17–21.
6. Soares L., Menier C., Raffin B., Roch J.-L. Parallel Adaptive Octree Carving for Real-time 3D Modeling // IEEE Virtual Reality Conference, VR'07. – 10–14 March 2007. – P. 273–274.
7. Szeliski R. Rapid Octree Construction from Image Sequences // CVGIP: Image Understanding. – 1993. – V. 58. – № 1. – P. 23–32.
8. Kochunov P.V., Lancaster J.L., Fox P.T. Accurate High-Speed Spatial Normalization Using an Octree Method // NeuroImage. – 1999. – V. 10. – P. 724–737.

106

Научно-технический вестник информационных технологий, механики и оптики, 2012, № 3 (79)

И.Н. Жданов, А.С. Потапов, О.В. Щербаков

9. Siddiqui R.A., Celasun I., Bayazit U. Octree Based Compression of Volumetric and Surface 3D Point Cloud Data // Proc. 13th Int'l Conf. on Virtual Systems and Multimedia, VSMM 2007. – Brisbane, Australia. – 23– 26 Sept. 2007. – P. 278–282.
10. Окунев В.В., Потапов А.С. Оптимизация разбиения изображения в форме квадродерева по критерию минимальной длины описания во фрактальном сжатии // Научно-технический вестник СПбГУ ИТМО. – 2011. – № 3 (73). – С. 34–38.

Жданов Иннокентий Николаевич Потапов Алексей Сергеевич Щербаков Олег Викторович

– Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, студент,
avenger15@yandex.ru – Санкт-Петербургский национальный исследовательский университет
информационных технологий, механики и оптики, доктор технических наук, профессор, pas.aicv@gmail.com – Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, студент,
ScherbakovOlegDK@yandex.ru

Научно-технический вестник информационных технологий, механики и оптики, 2012, № 3 (79)

107