Литература Радченко Ю. С. Алгоритм сжатия изображений на основе полиномиальных преобразований/ Ю. С. Радченко// Цифровая обработка сигналов, 2002, №1, с. 2-6




Скачать 312.68 Kb.
НазваниеЛитература Радченко Ю. С. Алгоритм сжатия изображений на основе полиномиальных преобразований/ Ю. С. Радченко// Цифровая обработка сигналов, 2002, №1, с. 2-6
страница3/4
Дата конвертации17.02.2013
Размер312.68 Kb.
ТипЛитература
1   2   3   4

Литература


  1. С. В. Умняшкин. О модификации дискретного косинусного преобразования // Изв. Тул. гос. ун-та. Сер. Математика. Механика. Информатика. Тула: ТулГУ, 1998. Т. 4. Вып. 1. с. 143-147.

  2. H. Witten, R. M. Neal, J. G. Cleary. Arithmetic coding for data compression // Communications of the ACM. – June 1987. – Vol. 30. – No. 6. p. 520-540.

  3. M. Crouse, K. Ramchadran. Joint thresholding and quantizer selection for transform image coding: entropy-constrained analysis and applications to baseline JPEG // IEEE Transactions on Image Processing. – 1997. – Vol. 6. – No. 2. p. 285-297.

  4. Z. Xiong, K. Ramchandran, M. T. Orchard. Space-frequency quantization for wavelet image coding // IEEE Transactions on image processing. – May 1997. – Vol. 6. p. 677-693.

  5. J. Rissanen. K. M. Mohiuddin. A multiplication-free multialphabet arithmetic code // IEEE Transactions on Communication. – February, 1989. – Vol. 37. p. 93-98.


AN IMAGE COMPRESSION ALGORITHM BASED ON DISCRETE PSEUDO-COSINE TRANSFORM

Kurina V., Umnyashkin S.

Moscow Institute of Electronic Technology (Technical University)

Currently a lot of fast discrete cosine transform (DCT) algorithms are known which are designed for various video and image compression applications. Although they reduce the number of multiplications for transform calculation, such operations cannot be excluded completely. In this work we propose an image compression algorithm based on multiplication-free orthogonal discrete pseudo-cosine transform (DPCT) [1] which is an approximation of the DCT. The lossy image compression algorithm is meant to be applied for devices with limited computational power such as PDAs and mobile phones.

The basic algorithm scheme includes transform calculation, scalar quantization and adaptive arithmetic encoding [2]. The image processing is performed by pixel blocks. Magnitudes of DPCT coefficients are encoded separately from their signs to reduce the arithmetic coder alphabet. Moreover, the coefficients of each block are distributed into 8 zones to be processed independently from each other. All zones in the block are described by an 8-bit key. If all the coefficients in zone number r are equal to zero then the rth bit in the key is set to 0, otherwise (there is a non-zero coefficient(s) in the zone) the rth bit is set to 1. The distribution of DPCT coefficients into zones is organized in such way that the coefficient variances are similar and the highest correlated coefficients are included into the same zone. For better adaptation of the arithmetic coder to its input data a separate entropy model is applied for encoding the coefficients of each particular zone.

The efficiency of the algorithm can be increased using rate-distortion theory. Here the problem of R-D optimization is to find such set of block keys and quantization step which minimize the Lagrange function , where D is quantization error and R is arithmetic encoding bitrate. The R-D optimization introduces additional computational complexity into the algorithm but also improves the results of compression considerably.

The proposed algorithm is comparable or even more effective than JPEG based on DCT as PSNR and compression rate show.

Работа выполнена при поддержке гранта Президента Российской Федерации МД-6172.2008.9.

Literature

  1. С. В. Умняшкин. О модификации дискретного косинусного преобразования // Изв. Тул. гос. ун-та. Сер. Математика. Механика. Информатика. Тула: ТулГУ, 1998. Т. 4. Вып. 1. с. 143-147.

  2. H. Witten, R. M. Neal, J. G. Cleary. Arithmetic coding for data compression // Communications of the ACM. – June 1987. – Vol. 30. – No. 6. p. 520-540.



Модифицированный метод компрессии изображений на основе кодирования древовидных структур коэффициентов вейвлет-преобразования

Коплович Д.М., Умняшкин С.В.

Московский государственный институт электронной техники (технический университет)

В настоящей работе предлагается модификация метода сжатия цифровых изображений [1,2], который основан на кодировании коэффициентов дискретного вейвлет-преобразования (ДВП), представленных в виде древовидных структур. Для повышения эффективности сжатия алгоритм [1], далее называемый базовым, использует контекстное кодирование проквантованных коэффициентов , где — исходное значение коэффициента. При этом модель адаптивного арифметического кодера выбирается исходя из прогноза модуля Pj кодируемого коэффициента wj, который, в свою очередь, строится по соседним уже закодированным коэффициентам преобразования из текущего и родительского саббэнда как некоторая взвешенная сумма их модулей [1]. Это позволяет учесть статистические связи между кодируемым коэффициентом и его соседями, повышая эффективность сжатия проквантованных коэффициентов. Для принятия решения о выборе модели используется набор пороговых значений прогноза, подобранных экспериментально.

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

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

Во-вторых, в базовой версии алгоритма положительные и отрицательные вейвлет-коэффициенты кодируются совместно. Это решение является эффективным с точки зрения простоты реализации, но неоптимальным для получения максимально высокой степени сжатия изображения. Раздельное кодирование знаков и модулей вейвлет-коэффициентов должно улучшить результаты, так как знаки коэффициентов коррелированы [3].

Предлагаемая модификация базового алгоритма заключается в более точной начальной инициализации моделей адаптивного арифметического кодера. Если в [1] использовалось фиксированное распределение, то в предложенной модификации в качестве начального распределения вероятностей выбирается экспоненциальное распределение (см. рис. 1):

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

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



Рис. 1. Инициализация моделей для кодирования коэффициентов изображения Goldhill при уровне сжатия 0,5 bpp (bit per pixel — бит на пиксел)


Знаки вейвлет-коэффициентов кодируются в 27 моделях, алфавит каждой из которых состоит из трех символов: (коэффициент отрицателен), (коэффициент нулевой), (коэффициент положителен). Символ используется для нулевых коэффициентов, исключая таким образом необходимость кодировать нули в моделях, применяемых для абсолютных значений.

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

В экспериментах использовалось 5-уровневое ДВП с теми же фильтрами, что и в работе [1]. В качестве тестовых изображений были взяты Lena, Barbara и Goldhill, каждое размером 512 на 512 пикселов. Для определения вносимых алгоритмом потерь в качестве изображения применялась метрика пикового соотношения сигнал/шум (PSNR).



Рис. 2. Сравнение модифицированного метода (фильтры 9/7) и стандартного алгоритма JPEG 2000

Предложенная модификация с фильтрами 9/7 дает результаты на 0,1…0,3 дБ лучше базового алгоритма и на 0,3…0,8 дБ лучше стандартного алгоритма JPEG 2000 (см. рис. 2). В приведенных результатах для сжатия по методу JPEG 2000 была использована программа ACDSee Pro (версия 8.1).

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

Битовые затраты, bpp

Фильтры 9/7, PSNR, дБ




Фильтры [5], PSNR, дБ

Lena

Barbara

Goldhill




Lena

Barbara

Goldhill

0,25

34,54

28,66

30,93




34,68

28,95

30,93

0,50

37,58

32,46

33,56




37,71

32,87

33,56

1,00

40,97

37,28

37,03




41,03

37,73

37,03


Применение фильтров [5] для вейвлет-преобразования позволяет дополнительно улучшить результаты (см. табл. 1): на изображении Lena наблюдается улучшение еще на 0,1 дБ, а на изображении Barbara — на 0,4 дБ. Таким образом, с фильтрами [5] улучшение по сравнению с JPEG 2000 составляет 0,4…0,9 дБ.


Работа выполнена при поддержке гранта Президента Российской Федерации МД-6172.2008.9.

Литература

  1. Умняшкин С.В. Вейвлет-компрессия цифровых изображений с прогнозированием статистических моделей // Известия вузов. Электроника. — № 5. — 2001. — С. 86–94.

  2. S. Umnyashkin, D. Koplovich, A. Pokrovskiy, A. Alexandrov. Image Compression Algorithm Based on Encoding of Tree-Arranged Wavelet Coefficients // Proc. of 3rd Russian-Bavarian Conference on Biomedical Engineering. Erlangen, July 2/3, 2007, pp.121–126.

  3. A. Deever, S. S. Hemami. What's Your Sign?: Efficient Sign Coding for Embedded Wavelet Image Coding // Proceedings of the 2000 IEEE Data Compression Conference, 2000, pp. 273–282

  4. Marcellin M., Gormish M., Bilgin A., Boliek M. An Overview of JPEG-2000 // Proceedings of the 2000 IEEE Data Compression Conference, Snowbird, Utah, March 2000, pp. 523–541.

  5. D. Wei, H.-T. Pai, and A. C. Bovik. Antisymmetric Biorthogonal Coiflets for Image Coding // Proceedings of IEEE International Conference on Image Processing, Chicago, IL, Oct. 1998, vol. 2, pp. 282–286.


A Modification of Image Compression Algorithm Based on Encoding of Tree-Arranged Wavelet Coefficients

Koplovich D., Umnyashkin S.

Moscow Institute of Electronic Technology (Technical University)

In [1], a computationally effective image compression algorithm was proposed, which applied multi-model arithmetic encoding for RD-optimized zerotree structured wavelet coefficients. This algorithm outperformed JPEG 2000, but some opportunities for further improvement were still opened.

The basic algorithm relies on a special prognosis value calculated for each quantized coefficient. The value is composed as a weighted sum of its parent and neighbor coefficients absolute values [1]. Based on this prognosis value, a decision is made which statistical model will be used for adaptive arithmetic encoding of the coefficient. Such multi-model approach exploits non-linear dependencies between each coefficient and its neighbors and parent, making lossless compression ratio of quantized coefficients substantially higher.

There are ten statistical models in the arithmetic coder applied for the basic algorithm: 6 for wavelet coefficients (one of them for the LL subband) and 4 for zerotree map indices. This solution is obviously not optimal in terms of coding efficiency.

First, using lots of models reduces data volume each of them encodes. The more models are used, the more sensitive they are to initial model statistics distribution, which is uniform by default in the basic algorithm, but the actual data distribution is certainly not uniform. Hence, model initialization is significant for the overall performance of the compression algorithm.

Second, encoding positive and negative coefficients together is simplest in the sense of implementation, but not the best for getting good compression. Separate encoding of each coefficient’s sign and absolute value is preferable because wavelet coefficient signs are themselves correlated, and this correlation should be exploited.

First of all, signs were separated from the coefficients; absolute values and signs were encoded independently.

To model initial statistics of the absolute values of wavelet coefficients we applied exponential distribution and maximum likelihood estimation for the distribution parameter in each model. Prognosis value calculation and model selection rules used for absolute values encoding remain virtually the same as in the basic algorithm excepting zero coefficients which are encoded by sign models.

Coefficient signs were encoded separately using 27 models with three symbols available for each model: (coefficient is negative), (coefficient is zero), (coefficient is positive).

Dependencies between signs were taken into account by context encoding. Instead of prognosis calculation and thresholding we used simpler approach similar to JPEG 2000: model choice for each sign symbol was strictly determined by its three neighbor sign values (upper, left and upper left), which results in 27 different combinations.

We also conducted experiments using Lena, Barbara and Goldhill test images. Proposed modification performs 0.1…0.4 dB (PSNR) higher than the basic algorithm and 0.4…0.9 dB higher than JPEG 2000.
1   2   3   4

Похожие:

Литература Радченко Ю. С. Алгоритм сжатия изображений на основе полиномиальных преобразований/ Ю. С. Радченко// Цифровая обработка сигналов, 2002, №1, с. 2-6 iconАдаптивная обработка сигналов
Обработки сигналов» и «Радиотехнические цепи и сигналы». Знания и навыки, полученные при изучении дисциплины «Адаптивные системы»,...

Литература Радченко Ю. С. Алгоритм сжатия изображений на основе полиномиальных преобразований/ Ю. С. Радченко// Цифровая обработка сигналов, 2002, №1, с. 2-6 iconЛитература. Обработка изображений
Ярославский Л. П. Цифровая обработка сигналов в оптике и голографии. М.: Радио и связь, 1987. 296 с

Литература Радченко Ю. С. Алгоритм сжатия изображений на основе полиномиальных преобразований/ Ю. С. Радченко// Цифровая обработка сигналов, 2002, №1, с. 2-6 iconЦифровая обработка сигналов
...

Литература Радченко Ю. С. Алгоритм сжатия изображений на основе полиномиальных преобразований/ Ю. С. Радченко// Цифровая обработка сигналов, 2002, №1, с. 2-6 iconУчебно-методический комплекс (умк) дисциплины «Цифровая и аналоговая обработка сигналов» для специальности кафедры ту
Курячий М. И. Цифровая обработка сигналов: Учебное пособие для вузов с грифом умо. – Томск: Томск гос ун-т систем упр и радиоэлектроники,...

Литература Радченко Ю. С. Алгоритм сжатия изображений на основе полиномиальных преобразований/ Ю. С. Радченко// Цифровая обработка сигналов, 2002, №1, с. 2-6 iconНовые книги, поступившие в библиотеку с 16-29 февраля 2012 г. Автоматизация сельского хозяйства
Радченко Г. Е. Автоматизация сельскохозяйственной техники : учебно-методическое пособие / Г. Е. Радченко. Минск : ивц минфина, 2011....

Литература Радченко Ю. С. Алгоритм сжатия изображений на основе полиномиальных преобразований/ Ю. С. Радченко// Цифровая обработка сигналов, 2002, №1, с. 2-6 iconАлгоритм вейвлет-сжатия неподвижных цифровых изображений с использованием оптимального базиса на соответствующих уровнях разложения
Овых изображений с использованием оптимального базиса класса Добеши на каждом уровне разложения Показано, что предложенный алгоритм...

Литература Радченко Ю. С. Алгоритм сжатия изображений на основе полиномиальных преобразований/ Ю. С. Радченко// Цифровая обработка сигналов, 2002, №1, с. 2-6 iconЦифровая обработка многомерных сигналов модифицированный билатеральный фильтр для улучшения качества jpeg-изображений
Для удаления блочного эффекта в сжатых изображениях можно использовать билатеральный фильтр (БФ) [4, 5]. Однако прямое его применение...

Литература Радченко Ю. С. Алгоритм сжатия изображений на основе полиномиальных преобразований/ Ю. С. Радченко// Цифровая обработка сигналов, 2002, №1, с. 2-6 iconСжатие изображений на основе их сегментного представления
Рассматривается алгоритм восстановления изображения из кода и приводится оценка коэффициента сжатия, полученная на разработанной...

Литература Радченко Ю. С. Алгоритм сжатия изображений на основе полиномиальных преобразований/ Ю. С. Радченко// Цифровая обработка сигналов, 2002, №1, с. 2-6 iconАлгоритм сжатия неподвижных цифровых изображений с использованием оптимального базиса класса Добеши на каждом уровне вейвлет разложения
Добеши на каждом уровне разложения Показано, что предложенный алгоритм при обработке 8-ми битных монохромных изображений превосходит...

Литература Радченко Ю. С. Алгоритм сжатия изображений на основе полиномиальных преобразований/ Ю. С. Радченко// Цифровая обработка сигналов, 2002, №1, с. 2-6 iconВ. В. Сюзев цифровая обработка сигналов: методы и алгоритмы
Включен так же ряд оригинальных результатов в области разработки быстрых алгоритмов обработки на скользящих интервалах времени и...


Разместите кнопку на своём сайте:
lib.convdocs.org


База данных защищена авторским правом ©lib.convdocs.org 2012
обратиться к администрации
lib.convdocs.org
Главная страница