Статья: Сжатие изображений с использованием дискретного преобразования Вейля – Гейзенберга

СЖАТИЕ ИЗОБРАЖЕНИЙ С ИСПОЛЬЗОВАНИЕМ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ВЕЙЛЯ - ГЕЙЗЕНБЕРГА

В.П. Волчков, В.М. Асирян

Московский технический университет связи и информатики

Национальный исследовательский технологический университет «МИСиС»

Аннотация

Предлагается новый подход к сжатию растровых изображений, основанный на использовании двухстороннего вещественного дискретного преобразования Вейля - Гейзенберга. Данное преобразование является ортогональным и строится на основе оптимального сигнального базиса Вейля - Гейзенберга, обладающего наилучшей частотно-временной локализацией. Указанные свойства обеспечиваются за счет выбора оптимальной функции формирования базисного эталона и наилучшего соотношения его параметров. Кроме того, для оценивания потенциальных возможностей использования дискретного преобразования Вейля - Г ейзенберга (DWHT) в задачах сжатия были сформулированы основные критерии эффективности сжатия и проведено сравнение DWHT с другими известными ортогональными преобразованиями - дискретного косинусного преобразования (DCT) и дискретного преобразования Хартли (DHT). Экспериментально показано, что предложенный метод сжатия на основе DWHT обладает лучшими характеристиками по всем введенным критериям. Приводятся результаты сравнения трех методов сжатия в виде таблиц и восстановленных изображений.

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

IMAGE COMPRESSION USING DISCRETE WEYL - HEISENBERG TRANSFORM

V.P. Volchkov, V.M. Asiryan

Abstract

This article proposes a new approach to raster image compression, based on the use of the two-dimensional real discrete Weyl - Heisenberg transform (DWHT). This discrete transform is orthogonal and is based on the optimal Weyl - Heisenberg signal basis, which has the best time-frequency localization. The indicated properties are ensured by choosing the optimal forming function of the basis and the best ratio of its parameters. In addition, to assess the potential possibilities of using the discrete Weyl - Heisenberg transform in compression problems, the main criteria for compression efficiency were formulated and DWHT was compared with other well-known orthogonal transforms - discrete cosine transform (DCT) and discrete Hartley transform (DHT). It is experimentally shown that the proposed method based on discrete Weyl - Heisenberg transform has much better compression characteristics. The paper also presents the results of comparing three compression methods (DHT, DCT and DWHT) in the form of corresponding tables and figures of the restored images.

Keywords: imaging, compression, cosine transform, Hartley transform, Weyl-Heisenberg transform, good localization, optimal basis.

сжатие растровый изображение качество вейль гейзенберг

Введение

В настоящее время важнейшую роль в цифровой обработке сигналов играют дискретные ортогональные преобразования, которые активно применяются в различных задачах цифровой фильтрации и спектрального анализа. Между тем математический аппарат дискретных ортогональных преобразований находит свое применение и в области сжатия данных для последующего экономичного хранения или передачи информации. Примером тому является дискретное косинусное преобразование (DCT) [Ахмед, Рао, 1980; Smith, 1999; Ahmed et al., 1974], получившее широкую популярность и послужившее основой для разработки таких алгоритмов сжатия информации, как JPEG, MPEG и др.

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

Общей теории построения хорошо локализованных базисных систем и соответствующих спектральных разложений посвящены работы [Gabor, 1946; Wexler, Raz, 1990; Добеши, 2001; Volchkov, 2007]. Однако наиболее важными примерами таких систем являются базисы Вейля - Гейзенберга (WH-базисы) [Волчков, 2009; Volchkov, Petrov, 2009], получаемые путем равномерных сдвигов по времени и частоте одной или целого семейства сдвинутых по фазе функций, а также похожие на них по структуре фрейм-системы [Volchkov, Sannikov, 2018; Volchkov et al., 2019]. В данных работах показано, что базис Вейля - Гейзенберга, построенный на основе произвольного формирующего импульса, не будет оптимальным, поскольку частотно-временная локализация базисных функций может оказаться неприемлемой. Именно поэтому особый интерес в исследовании представляет базис Вейля - Гейзенберга, в основу которого положены оптимальные частотно-временные свойства гауссиана. Известно, что сдвиги по времени и частоте гауссовой функции приводят к базису Габора [Gabor D., 1946], но такой базис не является ортогональным, а построенные на его основе вычислительные алгоритмы спектрального разложения и обратного восстановления оказываются неустойчивыми и сложными в реализации [Волчков, 2009; Волчков, Петров, 2010]. В то же время в работах [Волчков, Асирян, 2017; Асирян, Волчков, 2018] описывается синтез вычислительно эффективных алгоритмов формирования ортогональных WH-базисов большой размерности, у которых базисные функции близки по локализации к гауссиану. Причем процедура синтеза и ее последующее применение ориентированы на обработку конечных дискретных реализаций сигнала.

Отметим, что классический метод синтеза дискретных базисов [Gabor, 1946; Добеши, 2001; Wexler, Raz, 1990] предполагает, что входные сигналы являются бесконечными последовательностями (вещественными или комплексными). Это диктует применение соответствующего аппарата Z-преобразований, сверток и разложений на бесконечном дискретном временном интервале. В результате полученная структура WH-базисов не может быть непосредственно использована для практической обработки конечных реализаций сигналов и изображений. Нужна их дополнительная модификация и доработка для перевода аналитического описания и соответствующих быстрых алгоритмов на конечный интервал.

В работах [Волчков, Петров, 2009; Волчков, Петров, 2010; Bolcskei et al., 1999] используется алгебраический подход к синтезу оптимальных сигнальных WH-базисов, который изначально предполагает конечную длительность обрабатываемых сигналов. При этом используется алгебраический аппарат временных и спектральных преобразований на конечном интервале с групповыми операциями сложения и вычитания по модулю. Поэтому синтезированные на их основе базисные функции имеют циркулянтную структуру сдвигов по времени и частоте, согласованную с конечным интервалом обработки, и создаются предпосылки для построения эффективных вычислительных алгоритмов с использованием полифазных циркулянтных разложений и быстрых конечных спектральных преобразований. Таким образом, реализуется известный математический принцип - синтезировать оптимальные алгоритмы обработки следует в таких евклидовых пространствах, которые согласованы со структурой обрабатываемых сигналов.

В данной статье предлагается и исследуется новый подход к сжатию растровых изображений, основанный на применении дискретного ортогонального WH-базиса, специально оптимизированного под задачу обработки вещественных изображений. Для этого строится двухстороннее вещественное преобразование Вейля - Гейзенберга (DWHT), обладающее свойством ортогональности и наилучшей частотно-временной локализацией. Указанные свойства обеспечиваются за счет выбора оптимальной формирующей функции базиса и наилучшего соотношения его параметров. Для того чтобы оценить потенциальные возможности дискретного WH-преобразования в задаче сжатия изображения формулируются критерии эффективности сжатия, основанные на вычислении коэффициента сжатия, вычислении нормы разности исходного и сжатого изображений, а также их визуальном сравнении. В качестве альтернативы для сравнения по указанным критериям используются два других известных дискретных ортогональных преобразования: косинусное (DCT, [Ахмед, Рао, 1980; Smith, 1999; Ahmed et al., 1974]) и преобразование Хартли (DHT, [Hartley, 1942]).

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

1. Дискретные ортогональные преобразования

Основная идея дискретных ортогональных преобразований заключается в изменении сигнала с целью придания ему другой формы, в которой он имеет, возможно, непривычный вид, но обладает полезными свойствами. Главной особенностью ортогональных преобразований являются их обратимость, вычислительная устойчивость и простота реализации. Это значит, что преобразованный сигнал, изменивший свою форму и вид, можно легко вернуть в первоначальное состояние [Асирян, Волчков, 2018; Асирян, Волчков, 2017].

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

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

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

где a - вектор-столбец элементов сигнала, b - вектор-столбец элементов спектра, а - вектор-столбец элементов восстановленного сигнала.

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

где A - матрица элементов изображения, B - матрица элементов спектра изображения, А - восстановленное изображение. В частности, А = А при отсутствии дополнительных процедур сжатия и выполнении условия унитарности (1).

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

В 1942 году Р. Хартли опубликовал интегральное преобразование, тесно связанное с комплексным преобразованием Фурье, но отображающее вещественные сигналы в вещественный спектр. В дальнейшем данное преобразование получило название в честь фамилии автора и стало называться преобразованием Хартли. В 1983 году Р. Брейсуэллом был представлен его дискретный вариант и один из алгоритмов его эффективной вычислительной реализации. В работе [Sunder et al., 2006] отмечаются перспективы применения дискретного преобразования Хартли для обработки изображений, в том числе и в области сжатия.

На рис. 1 представлены исходное монохромное квадратное изображение «lena.jpg» (512 х 512 пикселей) и его двухсторонние дискретные ортогональные преобразования (DHT, DCT и DWHT). В свою очередь в таблице 1 приведены результаты восстановления исходного изображения «lena.jpg» с использованием трех дискретных ортогональных преобразований (DHT, DCT и DWHT).

Очень малые ошибки восстановления в данном случае обусловлены только вычислительной погрешностью, поскольку сжатия нет, т. е. A = А.

2. Пороговое сжатие изображений

Сжатие данных по пороговому значению представляет собой процедуру обнуления всех тех значений преобразованного изображения, модуль которых меньше определенного значения порога T. Данный процесс представляет собой сжатие с потерями. Ниже представлен алгоритм сжатия данных вещественной матрицы В = (B, _у) по пороговому значению T.

О, при B, j | < T,

. В,j, иначе.

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

Рис. 1. Исходное изображение (слева вверху), DHT (справа вверху), DCT (слева снизу) и DWHT (справа снизу)

Fig. 1. Original image (top-left), DHT (top-right), DCT (bottom-left) and DWHT (bottom-right)

Таблица 1

Результаты восстановления изображения

Table 1

Results of image reconstruction

После обнуления определенного количества элементов спектра, заданного коэффициентом сжатия K, восстановленное изображение становится моделью исходного изображения и уже A ф А. Кроме того, чем более корректно выбран базис, тем более качественно модель отображает исходное изображение при заданном количестве не обнуленных элементов спектра P = N_T - N_z. При этом существует некоторое критическое значение P = р, называемое факторной размерностью изображения, ниже которого качество восстановления аномально падает. Соответствующие элементы редуцированного спектра можно рассматривать как базовые факторные параметры модели изображения для выбранного базиса. Эксперимент показал, что факторный размер модели изображения для DWHT метода равен P_o = 7865, что соответствует коэффициенту сжатия K = 97 %.