close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
144
ИЗВЕСТИЯ ВолгГТУ
Секция 5
ПОСТРОЕНИЕ СЕТЕЙ И ЗАЩИТА ИНФОРМАЦИИ
УДК 681.32
А. Н. Земцов
О ВЫБОРЕ ОПТИМАЛЬНОГО ВЕЙВЛЕТ-БАЗИСА В ЗАДАЧЕ КОМПРЕССИИ
ТРИАНГУЛЯЦИОННЫХ МОДЕЛЕЙ РЕЛЬЕФА ПОВЕРХНОСТИ
Волгоградский государственный технический университет
В результате изучения стандартных пакетов, использующих для компрессии изображений базис вейвлетов, были выявлены недостатки, которые обусловили необходимость разработки и реализации программной системы экспериментального моделирования компрессии изображений.
Одним из основных недостатков является принципиальная сложность реализации методов компрессии трехмерных изображений. Необходимо отметить, что в связи с продолжающимся быстрым ростом производительности вычислительных систем стремительно растут и объемы обрабатываемой информации, особенно, размеры трехмерных моделей рельефа, содержащих миллиарды
треугольников [5].
Математическая модель рельефа поверхности описывается с помощью аппарата двумерных
дискретных сигналов, то есть функций, определенных на плоскости и оцифрованных с заданным
конечным разрешением. Хранение модели рельефа поверхности в виде двумерного массива значений высот представляется нерентабельным. Альтернативным подходом является триангуляция
рельефа поверхности, преимущественно адаптивная, то есть полученная на основе анализа структуры заданной модели. В данном случае триангуляционная модель является менее избыточной,
при этом исходный объект можно восстановить без потерь или с заданной погрешностью.
В [9] приводится обзор существующих методов компрессии триангуляционных моделей, таких
как:
1) методы, основанные на прореживании вершин [10];
2) методы, основанные на склеивании ребер [11];
3) методы, основанные на вейвлет-преобразовании [12].
В настоящее время приобретают все большую популярность методы компрессии изображений на
основе вейвлет-преобразования, благодаря тому, что они превосходят существующие подходы по
многим параметрам [1], [2].
Идея компрессии изображений на основе вейвлет-преобразования, как и других методов на основе ортогональных преобразований, довольно проста. Первоначально, в результате преобразования, из полученного изображения удаляются некоторые коэффициенты. Оставшееся множество
коэффициентов, как правило, кодируется. Сжатое изображение восстанавливается путем декодирования коэффициентов, если это необходимо, и применением обратного преобразования к результату. Предполагается, что в процессе децимации коэффициентов преобразования теряется не
слишком много информации [3].
Однако необходимо отметить, что для получения высокого значения точности и коэффициента
компрессии необходимо выбрать оптимальный для данного типа изображений базис вейвлетов.
Этот вопрос рассматривается в работе [4]. Авторы этой работы предлагают определять количество
детализирующей информации в изображении, с целью упростить выбор аппроксимирующего базиса вейвлетов. Кроме того, необходимо исследовать влияние длины разрядной сетки на точность
преобразования. Разработанная программная система предназначена для моделирования инструментальных (обусловленных ограничением разрядной сетки) и методических (обусловленных
процессом квантования) ошибок, возникающих при компрессии изображений на основе различных типов вейвлет-преобразований и анализа влияния ограничения разрядной сетки, процесса
квантования на точность преобразований и величину коэффициента сжатия изображения. Рассматриваемая реализация основывается на идее нуль-дерева и битовых плоскостей, использованной в [6], [7] и [8].
Будем называть адаптивным такой кратномасштабный анализ, в котором используются вейвлет-функции, выбранные с учетом априорной информации об анализируемых данных.
Выбор оптимального базиса вейвлетов для кодирования изображения в общем случае является
ИЗВЕСТИЯ ВолгГТУ
145
трудной и вряд ли решаемой задачей. Известен ряд критериев построения оптимального базиса,
среди которых наиболее важными являются гладкость, точность аппроксимации, величина области определения, частотная избирательность фильтра. Тем не менее наилучшая комбинация этих
свойств неизвестна. Кроме того, базис, дающий хорошие результаты для одного класса трехмерных моделей, для другого класса может совершенно не подходить. В данной работе делается попытка найти оптимальное вейвлет-преобразование для адаптивного кратномасштабного анализа
конкретной триангуляционной модели. В качестве критерия оптимальности используется среднеквадратическое отклонение триангуляционной модели, полученной в результате компрессии, от
исходной модели при заданном постоянном коэффициенте сжатия.
Для выбора оптимального преобразования используется моделирование процесса сжатия, так
как аналитическое решение данной задачи довольно сложно и до настоящего момента не существует математической модели, достаточно эффективно описывающей все типы триангуляционных
моделей. В программе реализован стандартный набор из 37 различных типов вейвлетпреобразований, скалярное однородное и неоднородное квантование, энтропийное кодирование
коэффициентов. Кроме того, пользователю предоставляется возможность реализации и хранения
собственных фильтров во внутренней базе данных фильтров программы. Достижение постоянного
коэффициента сжатия реализуется за счет специального алгоритма оптимального распределения
бюджета бит при квантовании спектра. При распределении также оптимизируется среднеквадратическое отклонение.
Предложена многомасштабная схема представления триангуляционных моделей. Основными
требованиями к модели являются требование универсальности и адекватности при заданном требуемом размере аппроксимации исходной модели. На основе предложенной схемы проведена
классификация методов компрессии. Выделены следующие методы ортогонального разложения:
преобразование Адамара, Карунена-Лоэва, дискретное косинусное преобразование и вейвлетпреобразование. Проведенный сравнительный анализ первых трех методов показал, что при одинаковой степени компрессии моделей показатели ошибки при восстановлении для метода на основе преобразования Адамара и дискретного косинусного преобразования близки по значениям и в
среднем на 20 % выше, чем метода на основе преобразования Карунена-Лоэва, что объясняется
плохим соответствием базисных функций преобразований структуре исходной модели. В случаях,
когда априори известна корреляционная функция кодируемого сигнала и не предъявляется высоких требований к вычислительной сложности, целесообразно применять преобразование Карунена-Лоэва. В случаях, когда кодируемое изображение близко по своей структуре к кусочнопостоянным функциям, то удовлетворительные результаты компрессии могут быть достигнуты с
помощью преобразования Адамара. При априорной неопределенности о свойствах кодируемого
сигнала и высоких требованиях к скорости вычисления целесообразно применять дискретное косинусное преобразование.
Для триангуляционных моделей, которые являются нестационарными сигналами с локальными особенностями лучшее решение задачи компрессии обеспечивает разработанный метод на основе вейвлет-преобразования, поскольку имеет лучшие декоррелирующие свойства при аппроксимации нестационарных сигналов и в среднем на 15–40 % эффективнее (среднеквадратичное отклонение при компрессии в 20 раз в среднем меньше 5) приближает исходные модели с помощью
выбранного в результате проведенного моделирования вейвлет-базиса (результаты показаны на
рис. 1).
На рис. 2 показаны полученные аппроксимации модели рельефа методом, описанным в [13].
Исходная регулярная триангуляционная модель (фрагмент модели представлен на рис. 3) получена с помощью карты высот и состоит из 58081 вершины и 115200 граней. Представленные модели
содержат 7332 вершин/14452 граней и 1488 вершин/2885 граней соответственно.
146
ИЗВЕСТИЯ ВолгГТУ
Среднеквадратичное отклонение
6
5
4
3
2
1
0
5
10
15
20
25
30
35
40
45
50
Степень компрессии
Хаара
Добеши db2
Добеши db3
Добеши db4
Антонини
Вилласенора 1810
Адельсона
Брислауна br1
Брислауна br2
Вилласенора vs1
Вилласенора vs2
Вилласенора vs3
Биортогональный bior4
Биортогональный bior10
Симмлет sym14
Одегарда
Рис. 1. Результаты компрессии триангуляционной модели рельефа поверхности
Рис. 2. Аппроксимация модели рельефа поверхности (слева – 7332 вершин/14452 граней, справа – 1488 вершин/2885
граней). Рамкой показан фрагмент, изображенный на рис. 3
Рис. 3. Фрагмент исходной триангуляционной модели рельефа поверхности (58081 вершин/115200 граней)
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Daubechies, I. Ten lectures on wavelet. Vol 61 of CBMS/NSF Regional Conference Series in Applied Math. SIAM, 1992.
2. Jawerth B., Sweldens W. An overview of Wavelets based Multiresolution Analysis. SIAM Review, 1994.
3. Stollnitz E., DeRose T., Salesin D. Wavelets for Computer Graphics. Morgan Kaufmann, 1996.
ИЗВЕСТИЯ ВолгГТУ
147
4. Mandal M., Panchanathan S., Aboulnasr T. Choice of Wavelets for Image Compression, Lecture Notes in Computer Science, Vol.1133, pp. 239–249.
5. Скворцов А. В. Построение сверхбольшой триангуляции Делоне // Изв. вузов. Физика. – 2002. – № 6.
6. Lewis A., Knowles G. Image Compression using the 2D Wavelet Transform. IEEE Trans. On Image Proc., Vol. 1, No.2,
pp. 244–250.
7. Said A., Pearlman W. A New Fast and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees. IEEE
Trans. On Circuits and Systems for Video Technology., Vol.6, pp. 243–250.
8. Shapiro J. Embedded Image Coding Using Zerotrees of Wavelet Coefficicents. IEEE Trans. On Signal Proc., Vol. 41, No.
12, pp. 3445–3462.
9. Paul S. Heckbert, Michael Garland. Survey of polygonal surface simplification algorithm. School of computer science,
Carnegie Mellon University, Pittsburg.
10. Soucy M., Laurendau D. Multiresolution surface modeling based on hierarchical triangulation. Computer vision and image
understanding, Vol. 63, No. 1, January 1996, pp. 1–14.
11. Hoppe H. Progressive meshes. Computer Graphics SIGGRAPH’ 96 Proceedings, pp 98–108.
12. Michael Lounsbery. Multiresolution Analysis for Surfaces of Arbitrary Topological Type. PhD thesis, Dept. of Computer Science and Engineering, University of Washington, 1994.
13. Земцов А. Н. Компрессия триангуляционных моделей с адаптивным уточнением. – Современные проблемы информатизации в непромышленной сфере и экономике: Сб. трудов. Вып. 10 / Под ред. проф. О. Я. Кравца. – Воронеж:
Изд-во Научная книга, 2005. – 140 с.
Документ
Категория
Без категории
Просмотров
4
Размер файла
358 Кб
Теги
оптимальное, выбор, компрессор, базиса, поверхности, моделей, триангуляционной, задачи, рельеф, вейвлет
1/--страниц
Пожаловаться на содержимое документа