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

Размещено на http://allbest.ru

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

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

Введение

В настоящее время важнейшую роль в цифровой обработке сигналов играют дискретные ортогональные преобразования, которые активно применяются в различных задачах цифровой фильтрации и спектрального анализа. Между тем математический аппарат дискретных ортогональных преобразований находит свое применение и в области сжатия данных для последующего экономичного хранения или передачи информации. Примером тому является дискретное косинусное преобразование (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 %.

На рисунках 2-4 демонстрируются визуальные результаты сжатия одного и того же изображения «lena.jpg» с использованием трех дискретных ортогональных преобразований (DHT, DCT и DWHT) для трех фиксированных значений коэффициента сжатия (K = 93 %, 95 %, 97 %). Изображения обрезаны для визуального сравнения артефактов сжатия.

Рис. 2. Сжатое изображение с использованием DHT (слева), DCT (посередине), DWHT (справа) для K = 93 %

Fig. 2. Compressed image using DHT (left), DCT (middle), DWHT (right) for K = 93 %

Рис. 3. Сжатое изображение с использованием DHT (слева), DCT (посередине), DWHT (справа) для K = 95 %

Fig. 3. Compressed image using DHT (left), DCT (middle), DWHT (right) for K = 95 %

Рис. 4. Сжатое изображение с использованием DHT (слева), DCT (посередине), DWHT (справа) для K = 97%

Fig. 4. Compressed image using DHT (left), DCT (middle), DWHT (right) for K = 97%

В таблицах 2-4 приведены подробные численные результаты сжатия изображения «lena.jpg» для трех ортогональных преобразований, позволяющие количественно оценить и сравнить все три метода сжатия.

Таблица 4

Table 4

Сравнение методов сжатия (при K = 93 %)

Comparison of image compression (K = 93 %)

Таблица 2

Table 2

Сравнение методов сжатия (при K = 95 %)

Comparison of image compression (K = 95 %)

Таблица 3

Table 3

Сравнение методов сжатия (при K = 97 %)

Comparison of image compression (K = 97 %)

Заключение

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

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

Список литературы

1. Асирян В.М., Волчков В.П. 2017. Применение ортогонального преобразования Вейля - Гейзенберга для сжатия изображений. Телекоммуникации и информационные технологии. 4 (1): 50-56.

2. Асирян В.М., Волчков В.П. 2018. Вычислительно эффективная реализация прямого и обратного преобразований Вейля - Гейзенберга. Телекоммуникации и информационные технологии. 5 (1): 5-10.

3. Ахмед Н., Рао К.Р. 1980. Ортогональные преобразования при обработке цифровых сигналов. Пер. с англ./Под ред. Фоменко И.Б., М.: Связь, 248. (Ahmed N, Rao K.R. 1975. Orthogonal Transforms for Digital Signal Processing. Berlin, Heidelberg, New York: Springer-Verlag, 264).

4. Волчков В.П., Асирян В.М. 2017. Вычислительно эффективный алгоритм формирования оптимального базиса Вейля - Гейзенберга. Фундаментальные проблемы радиоэлектронного приборостроения. М., МИРЭА. Часть 4: 1151-1154.

5. Волчков В.П. 2009. Новые технологии передачи и обработки информации на основе хорошо локализованных сигнальных базисов. Научные ведомости БелГУ. Сер. История. Политология. Экономика. Информатика. 15 (70): 181-189.

6. Волчков В.П., Петров Д.А. 2009. Условия ортогональности обобщенных базисов Вейля - Гейзенберга для OFTDM сигналов. Научные ведомости БелГУ. Сер. История. Политология. Экономика. Информатика. 15 (70): 190-199.

7. Волчков В.П., Петров Д.А. 2009. Оптимизация ортогонального базиса Вейля - Гейзенберга для цифровых систем связи, использующих принцип OFDM/OQAM передачи. Научные ведомости БелГУ. Сер. История. Политология. Экономика. Информатика.1 (56): 102-112.

8. Волчков В.П., Петров Д.А. 2010. Обобщенная теорема Найквиста для OFTDM сигналов. Системы синхронизации, формирования и обработки сигналов. М., Издательский дом Медиа паблишер. 1 (1): 28-32.

9. Добеши И. 2001. Десять лекций по вейвлетам. Ижевск: РХД, 464. (Daubechies I., 1992. Ten Lectures on Wavelets. Philadelphia, Pa.: Society for Industrial and Applied Mathematics, 378).

10. Ahmed N. et al. 1974. Discrete Cosine Transform. IEEE Transactions on Computers. Vol. C-23, no. 1: 90-93.

11. Bolcskei H. et al. 1999. Efficient design of OFDM/OQAM pulse shaping filter. Proceedings of IEEE International Conference on Communications (ICC 99). Vol. 1: 559-564.

12. Gabor D. 1946. Theory of communication. J. Inst. Elect. Eng. (London), vol. 93, no. 111: 429-457.

13. Hartley R.V. 1942. A More Symmetrical Fourier Analysis Applied to Transmission Problems. Proceedings of the IRE (March), 30 (3): 144-150.

14.Smith S.W. 1999. The Scientist and Engineer's Guide to Digital Signal Processing. California Technical Publishing, 2nd ed.: 496-503.

15.Sunder R. et al. 2006. Medical image compression using 3-D Hartley transform. Computers in biology and medicine, Vol. 36: 958-973.

16. Volchkov V.P. 2007. Signal bases with good time-frequency localization. Electrosvyaz, no. 2: 21-25.

17. Volchkov V.P., Petrov D.A. 2009. Orthogonal Well-Localized Weyl-Heisenberg Basis Construction and Optimization for Multicarrier Digital Communication Systems. Proc. of ICUMT, St. Petersburg: Oct.

18. Volchkov V.P., Sannikov V.G. 2018. Algebraic approach to the optimal synthesis of real signal Weyl-Heisenberg bases. 2018 Systems of Signal Synchronization, Generating and Processing in Telecommunications (SYNCHROINFO 2018). Publ: Institute of Electrical and Electronics Engineers (IEEE), POD Publ: Curran Associates, Inc. (Oct 2018): 135-142.

19. Volchkov V. et al., 2019. Synthesis of Real Weyl-Heisenberg Signal Frames with Desired Frequency-Time Localization., 2019 24th Conference of Open Innovations Association (FRUCT), Moscow, Russia: 502-508.

20. Wexler J., Raz S. 1990. Discrete Gabor expansions. Signal Processing, vol. 21, no. 3: 207-220.

Размещено на Allbest.ru