Статья: Эффективное сжатие изображений на базе дифференциального анализа

эффективное сжатие изображений на базе дифференциального анализа

А. Ю. Гришенцев

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики

Аннотация

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

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

Abstract

In this paper we propose a method for image compression based on the analysis of the differential structure. Was initially given the task of developing a method of compression specific high contrast satellite images in order to reduce costly traffic due to the spacecraft. As a result of the development made on the basis of SPb ITMO was obtained new image compression method based on the analysis of the differential structure. The resulting method has shown the possibility of applying to a wide range of graphic images in particular, and field in general. The paper discusses the concept of method, options software implementation, advanced techniques that improve the efficiency of the method, as well as examples and numerical estimates. This method of compression can be used for static and dynamic (video) images. Laid the basis for the conception principles allow you to create multi-threaded computing solutions both hardware and software, and only hardware. Computational complexity of the core compression algorithm (in its simplest implementation) can be estimated as the product of the linear dimensions of static images. Image compression based on the analysis of the differential structure is comparable to the degree of compression JPEG, the quality of the images obtained by the numerical criterion (,,) above, that may be important for computer image processing. To compress a relatively small number of operations that can have a positive impact on the loading of computing power spacecraft carrying the transferof images.

Key words: compression, compression, data compression, image compression, the compression algorithm, the analysis of the differential image structure, differential compression.

1. Введение

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

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

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

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

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

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

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

2. Предпосылки к формированию компактной формы на базе анализа дифференциальной структуры

Рассмотрение цифровых сигналов как полевых структур позволяет использовать численные методы расчёта полей к анализу и преобразованию цифровых сигналов. Наиболее интересны методы частотного и дифференциального анализа. Основы методов частотного анализа цифровых сигналов, в том числе с целью последующего сжатия, хорошо разобраны в ставшей уже классической литературе по цифровой обработке сигналов [1-5], поэтому сконцентрируем внимание на рассмотрении пространственного анализа сигналов. Существует ряд способов формирования компактного вида цифровых сигналов путём анализа пространственной структуры. В частности для получения компактного вида изображений применяют векторизацию, т.е. в ходе морфологического анализа изображения выявляют графические примитивы (прямые, окружности, прямоугольники и т.д.), совокупность описания которых позволяет в некоторых случаях получить компактную форму. Данный способ не является универсальным, т.е. не все изображения можно, с целью сжатия, эффективно разделить на графические примитивы. Разделением на графические примитивы наиболее эффективно можно сжимать техническую графику (чертежи, эскизы и др.) и некоторые виды изображений, объекты которых имеют чёткие границы и относительно простые формы. Морфологический анализ изображений в большинстве случаев является достаточно сложной вычислительной задачей.

Следующим способом является фрактальное сжатие, основанное на том, что изображение можно представить более компактно, с помощью коэффициентов системы итерируемых функций (фракталов) [6]. С точки зрения вычислений, фрактальное сжатие является очень затратным способом, но на некоторых образцах изображений показывает очень хорошие результаты. Известен способ, в котором из изображения, применяя метод «brush fire» (лесной пожар), формируют скелет многоугольника, толщиной 1-2 пикселя, являющийся диаграммой Вороного [7]. Данный способ так же достаточно затратен с точки зрения вычислений и не получил широкого распространения. Существуют и другие способы пространственного анализа цифровых сигналов с целью получения компактной формы.

Способ дельта-кодирования. В самом простом случае дельта кодирование строится следующим образом: для элементов цифрового сигнала , вычисляется ряд дельта-кода , в силу того, что соседние элементы исходного сигнала обычно отличаются друг от друга значительно меньше диапазона допустимых значений , полученный ряд дельта-кода может быть эффективно сжат [8]. Фактически значения ряда дельта-кода являются производной . Для восстановления исходного сигнала, кроме самого ряда дельта-кода, необходимо знать начальное условие. Рассмотрим пример получения и некоторые особенности дельта-кода: диаграмма (рис. 1) и ряды численных значений (таблица 1), соответственно. Очевидно, что значения дельта-кода имеют меньшую амплитуду и для их кодирования потребуется меньшее число разрядов. Значения дельта-кода будут чаще повторяться и, следовательно, к ним может быть эффективно применено статистическое кодирование.

Рис. 1. Исходный сигнал и дельта-код .

Таблица 1. Значения функции и её дельта-кода .

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

Рассмотрим основные типы уравнений математической физики с частными производными второго порядка для двух- и трёх мерных пространств (- координаты пространства, - координата времени) [9].

Волновые уравнения:

, (1)

. (2)

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

Уравнения теплопроводности, или уравнения Фурье:

, (3)

. (4)

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

Уравнения Лапласа и Пуассона:

, (5)

. (6)

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

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

Можно записать выражение, связывающее производную порядка (где любое из чисел ) и члены ряда Фурье функции :

, (7)

где: - коэффициенты ряда Фурье функции . Из уравнения (7) следует, что производные более высокого порядка более зависимы от высокочастотных составляющих ряда Фурье.

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

3. Анализ дифференциальной структуры и формирование паттерна краевых условий цифрового сигнала

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