Обработка и передача изображений

а) б)

в)

Рис. 1. Кадры видеопоследовательностей, с выделенными изменившимися блоками.

Литература

1. 
   Радченко Ю.С. Алгоритм сжатия изображений на основе полиномиальных преобразований/ Ю.С. Радченко// Цифровая обработка сигналов, 2002, №1, с.2-6.
   
2. 
   Радченко Ю.С. Метод сжатия и восстановления изображений на основе быстрых чебышевских преобразований // Автометрия. - 2002. - № 4. - С. 32-40.
   
3. 
   Радченко, Ю.С. Экспериментальный кодек чебышевского сжатия/восстановления изображений (GDCT) и программный комплекс для его исследования / Ю.С. Радченко, Т.А. Радченко, А.А. Агибалов, А.В.Булыгин // Цифровая обработка сигналов и ее применение -DSPA2007. Труды 9- й Международной конференции. - Москва, 2007. – выпуск IX- 2, С. 286-289 (рус.), 289 (англ.).
   
4. 
   Радченко Ю.С. Сравнительный алгоритм сжатия изображений на основе дискретного косинусного (DCT) и чебышевского (GDCT) преобразований / Ю.С. Радченко, Т.А. Радченко, А.В. Булыгин // Цифровая обработка сигналов, 2006.- №4.-С. 15-19.
   
5. 
   Радченко Ю.С. Многоальтернативное обнаружение изменений в динамических изображениях. Труды НТО РЭС им. А.С. Попова, серия «Цифровая обработка сигналов и ее применения», Москва, 2005, вып. VII-2, C.-301-303(рус), с. 303-304-англ.
   

Spectral detector subsystem of interframe changes in MGDCT codec

Radchenko Yu., Radchenko T., Bulygin A.V.

Voronezh State University

Universitetskaya pl., 1, Voronezh, 394006

The paper considers researches spectral detector subsystem of interframe changes in combined MGDCT video codec. Codec allows using DCT or GDCT transform in according to required bitrate and additional features. Spectral detector subsystem is aimed at decreasing bitrate of video.

Spectral detector subsystem of interframe changes based on spectral detection changes in frame’s block algorithm [1, 2]. Taking a decision of block changing based on comparison: (1).

Where, h₀ – threshold value for taking decision of block changing; D₀ – metric, evaluated: (2). Where, k,m – indexes of spectral coefficients block; X_k,m – spectral coefficients of current frame block; C_k,m – spectral coefficients of comparing frame block; C_0,0 – DC coefficient of comparing frame block.

Block X of spectral coefficients is considered changed if metric’s D₀ value is greater than threshold value h₀.

Changes detection algorithm allows transmitting only changed blocks. The Metric D₀ (2) computed at any block for changes detection. This metric computed for blocks in current frame and the frame which the block is changed last time. The Metric D₀ is calculated only for brightness component Y of frame. Spectral coefficients of block will transmitted to decoder if the block has been considered changed. This operation is used for all blocks of frame.

Research results prove that spectral detector subsystem could be used in systems of video compression. The subsystem allows decreasing video bitrate up to 60% depending on dynamics of video and compression rate. Experiments had shown efficiency of using GDCT transform for spectral detector subsystem creation. The subsystem hasn’t high calculation requirements for video codec.

References

1. Yu.S. Radchenko. Image compression algorithm based on polynomial transforms/Yu.S. Radchenko//Digital signal processing, 2002.-№4.-pp.2-6.

2. Yu.S. Radchenko, “Multiple-choice changes detection in dynamic images”, Digital Signal Processing and its Applications, vol. 7, №2, 2005, pp. 301-304.



ИССЛЕДОВАНИЕ РЕКУРСИВНОЙ И СЕПАРАБЕЛЬНОЙ РЕАЛИЗАЦИИ ФИЛЬТРА НЕЛОКАЛЬНОГО УСРЕДНЕНИЯ

Егорова М.А., Литвинов В.Е.

Московский инженерно-физический институт (государственный университет)

Подавление шумов является важной задачей для улучшения качества изображений вообще и цифровых фотографий в частности. В 2005 году Buades предложил фильтр нелокального усреднения (NL-means) [1], который может рассматриваться как некое обобщение фильтра усреднения пикселов, имеющих близкие значения [2], и билатерального фильтра [3]. NL-means фильтр интуитивно понятен, в значительной степени предохраняет перепады и текстуры от размытия, обеспечивает высокое качество фильтрации в смысле критерия отношения пикового значения сигнала к шуму (PSNR) для аддитивного белого гауссового шума (AWGN). Только несколько алгоритмов, эксплуатирующие более сложные идеи, дают лучшие результаты фильтрации, например, совместная (collaborative) фильтрация [4].

На ряде вычислительных систем применению алгоритма нелокального усреднения препятствует его высокая вычислительная сложность. В последнее время было опубликовано несколько подходов для некоторого ускорения и одновременно улучшения качества NL-means фильтрации [5,6], а также редукции [7] фильтра нелокального усреднения, которая значительно уменьшила время работы, но привела к ухудшению качества фильтрации.

Целью данной работы является исследование рекурсивной и сепарабельной реализаций фильтра нелокального усреднения. Мотивацией для этого исследования явились статьи [8] и [9], которые для ускорения билатеральной фильтрации предлагают осуществлять фильтрацию с пространственным ядром в виде одномерного вектора сначала по строкам, а затем по столбцам. По аналогии с линейными сепарабельными фильтрами, такой фильтр также называют сепарабельным, что кратко и четко характеризует подобный способ обработки, хотя в строго математическом смысле это неверно. В [9] также предлагается рекурсивная реализация билатерального фильтра. Основные свойства билатерального фильтра, такие как подавление шумов и предохранение резкости контурных перепадов, при сепарабельной и рекурсивной реализации, в целом, сохраняются. Можно ожидать аналогичного сохранения свойств при рекурсивной и сепарабельной реализациях фильтра нелокального усреднения.

Традиционный NL-means фильтр является нерекурсивным и вычисляется с помощью следующих соотношений: , (1), где I – исходное изображение с шумом, I_f результирующее изображение, (r,c) – координаты текущей точки изображения, S и K – размеры скользящего окна, в пределах которого происходит усреднение пикселов исходного изображения с весами, задаваемыми функцией сходства между блоками изображения:

, (2), где M и L задают размер блока.

При нерекурсивной реализации требуется два буфера памяти: для исходного и фильтрованного изображения или их фрагментов. Это препятствует эффективной реализации на платформах, имеющих ограничения на объем используемой памяти или относительно медленный интерфейс к оперативной памяти, таких как КПК, смартфоны, мобильные телефоны, цифровые фотоальбомы, цифровые фотокамеры и камкордеры. Рекурсивный NL-means фильтр использует только один буфер для хранения изображения, что для ряда платформ позволяет реализовать более быструю обработку. При использовании рекурсивного алгоритма, каждый вновь полученный пиксел записывается в массив исходного изображения I, при усреднении и при вычислении весов используются как исходные пикселы, так и пикселы измененные на предыдущих позициях скользящего окна: . (3).

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

, . (4).

Перечисленные три варианта фильтров были реализованы в программе для персонального компьютера и 32-битной операционной системы Windows. Программа была написана на С++. Результаты работы фильтров сравнивались качественно и на основе критерия PSNR для различных изображений зашумленных аддитивным белым шумом. Также оценивались результаты билатеральной фильтрации. В целом поведение фильтров для различных изображений сходно. Большой интерес для анализа представляет способность NL-means фильтра сохранять текстуру, поэтому в данной работе мы приводим результаты для изображения barbara, на котором присутствует большое количество разнообразных текстур (рисунок 1). Пиковые отношения сигнала к шуму для различного уровня AWGN приведены в таблице 1. Были выбраны такие параметры фильтров, которые обеспечили максимум PSNR.

Таблица 1. PSNR (dB) для различного уровня AWGN и изображения barbara

Фильтр \ Дисперсия AWGN
Билатеральный	47.4842	34.5556	30.8434	28.4344
NL-means	47.4754	36.8367	33.2655	31.3161
Рекурсивный NL-means	47.4754	36.4283	32.3117	29.9079
Сепарабельный NL-means	47.4749	29.8482	28.9449	27.8376

Обычный NL-means	Рекурсивный NL-means	Сепарабельный NL-means
Рис. 1. Результаты фильтрации AWGN () изображения Barbara

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

Из рис. 1 видно, что результаты фильтрации обычным и рекурсивным фильтром визуально не отличаются. Аналогичный вывод дает анализ разностных изображений исходного и фильтрованного изображений, которые Buades назвал “noise method”. Границы и текстуры при фильтрации размываются очень мало. Для малого уровня шумов отличие по PSNR также незначительно, однако с ростом шумов, как правило, начинает расти, но это зависит от содержимого изображения. Следует отметить, что часто для рекурсивной реализации сходная с нерекурсивной степень фильтрации достигается для меньшего размера скользящего окна, что сокращает время фильтрации иногда до 2 раз. Отсутствие дополнительного буфера памяти также обеспечивает прирост производительности до 20%. К недостаткам такого способа оптимизации обработки следует отнести то, что рекурсивные алгоритмы гораздо сложнее параллелизовать.

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

Литература

1. 
   A. Buades, B. Coll, and J. M. Morel, "A Non Local Algorithm for Image Denoising," Proc. IEEE Int. Conf. on Computer Vision and Pattern Recognition, vol. 2, pp. 60-65, 2005.
   
2. 
   L. Yaroslavsky, “Digital Picture Processing - An Introduction”, Springer Verlag, 1985.
   
3. 
   C.Tomasi, R.Manduchi, “Bilateral Filtering for Gray and Color Images”, IEEE conf. on Computer Vision, 1998.
   
4. 
   K. Dabov, A. Foi, V. Katkovnik, and K. Egiazarian, "Image Denoising by Sparse 3D Transform-Domain Collaborative Filtering," IEEE Transactions on Image Processing, 2006.
   
5. 
   M. Mahmoudi and G. Sapiro, "Fast Image and Video Denoising via Nonlocal Means of Similar Neighborhoods," IEEE Signal Processing Letters, vol. 12, no. 12, pp. 839–842, 2005.
   
6. 
   J.Wang, Y.Guo , Y.Ying, Y.Liu, Q.Peng “Fast non-local algorithm for image denoising”, IEEE International conference on Image Processing, 2006.
   
7. 
   A. Kharlamov, V.Podlozhnyk, CUDA: Image Denoising, NVIDIA Corp., 2007.
   
8. 
   T.Q. Pham, L.J. van Vliet, ”Separable bilateral filtering for fast video preprocessing”, Proc. IEEE International Conference on Multimedia, 2005.
   
9. 
   I.V. Safonov, M.N. Rychagov, K.M. Kang, S.H. Kim, "Automatic correction of exposure problems in photo printer", IEEE 10th International Symposium on Consumer Electronics, pp. 13-18, 2006.
   

Investigation of Recursive and Separable Implementation of Non-Local Means Filter

Egorova M., Litvinov V.

Moscow Engineering Physics Institute (State University)

Noise suppression is an important problem of digital image enhancement. Non-Local means filter preserves edges and textures from blurring, ensures high filtration quality in term of peak signal-to-noise ratio (PSNR) for additive white Gaussian noise (AWGN). We conduct an investigation of different implementations of this filter: conventional nonrecursive, recursive and separable. Traditional NL-means filter is nonrecursive and it is computed in the following way: , (1), where I – initial noised image, I_f – the resulted image, (r,c) – coordinates of the current image pixel, S and K – size of slide window used for pixels averaging in initial image with weights specified by similarity function between image blocks (which size is MхL):

. (2).

Using recursive algorithm each new pixel is written to initial image I instead of additional memory buffer. Both pixels of initial image and pixels changed at the previous steps are used while averaging and weights computing:

. (3).

If separable implementation is used at first all pixels of initial image are processed via one dimensional horizontal sliding window. Result of this step is written down to buffer I_r. Then sliding window is transposed and I_r is processed by column: , . (4).

The results of nonrecursive and recursive filtrations do not differ visually and have slight PSNR difference, edges and textures are blurred insignificantly. Recursive filter is more effective than nonrecursive in terms of processing time and used RAM. Separable filter is more rapid than NL-means using rectangular sliding window. However noise is suppressed inefficiently, texture is often blurred, and sometimes granularity artifacts appear along edges.



БЫСТРЫЙ АЛГОРИТМ ГЛОБАЛЬНОЙ КОМПЕНСАЦИИ ДВИЖЕНИЯ основанный на бинаризации кадров

Мочалов И.С., Жуков А.А., Новожилова Т.В.

Ярославский Государственный Университет им. П.Г. Демидова

Компенсация движения в видеопоследовательности – это процесс извлечения информации о характере и параметрах «оптического» двумерного движения объектов (в плоскости кадра) по имеющейся видеоинформации. Использование этой информации позволяет существенно увеличить степень компрессии алгоритмов сжатия видео [1]. Модуль компенсации движения является составной частью практически всех современных видеокодеков, систем видеонаблюдения и наиболее качественных алгоритмов шумоподавления.

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

Рассмотрим случай, когда макроблоки (блоки пикселей N*N) одного видеообъекта испытывают однородное перемещение. Такое движение возникает при панорамной видеосъёмке, приближение камеры к сцене, различных поворотах. В таких случаях, возникает возможность передавать относительно малое число параметров движения (деформации), которое описывает глобальное изменение всей плоскости видеообъекта. Инструмент, использующий описанный выше подход называется GMC (Global Motion Compensation) глобальная компенсация движения. Механизм GMC позволяет существенно увеличить сжатие, когда большая часть макроблоков из плоскости видеообъекта имеют одинаковые характеристики движения. Для каждого пиксела индивидуальный вектор движения вычисляется с помощью интерполяции векторов GMV (Global Motion Vectors). Такой механизм позволяет строить компенсацию для широкого типа движений: различные вращения, наплывы, деформации, сдвиги и линейные перемещения.

Предлагаемый алгоритм быстрой глобальной компенсации движения позволяет вычислять GMV при аффинных преобразованиях масштабирования и сдвига. На первом этапе исходное изображение , обрабатывается фильтром Лапласа с целью выделения контуров объектов. Полученное высокочастотное изображение бинаризуется с помощью пороговой обработки. Результатом бинаризации являются два бинарных изображения и . Выбор порога зависит от уровня высокочастотного шума, который может быть оценен [2], как .

Аналогичные операции проделываются для ссылочного изображения (порог остается прежним). Результатом являются два бинарных изображения и . Пример бинарных изображений и приведен на рис. 1.

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

или .

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

а)	б)
Рис 1. Бинарные изображения а) «+» б) «-»

На втором этапе происходит определение параметров глобального движения и . Параметр масштабирования ищется на основе информации о числе ненулевых элементов в и . . После того, как найден параметр (если ) оба изображения разбиваются на блоки. Размер блоков может быть различным, но для получения существенного выигрыша (более 25 раз) в быстродействии необходимо, чтобы число пикселей в блоке было больше 100. Каждый блок представляет собой бинарное изображение размером L*L. Обозначим – множество пикселей, принадлежащих –му блоку.

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

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

. (1).

Как видно из (1) второй элемент зависит только от выбора общей области и практически не изменяется. Для вычисления первого элемента требуется 4 действия сложения/вычитания для каждого блока и каждого смещения. Пример функции , для области поиска 129*129, приведен на рис. 2. Стоит отметить, что, как и более сложные алгоритмы, данный алгоритм может быть ускорен, на основе применения алгоритма иерархического поиска.

На завершающем этапе параметр смещения уточняется до подпиксельной точности. Для этого кумулятивная сумма интерполируется на подпиксельные значения и выполняется соответствующий поиск в области найденного на предыдущем этапе .

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

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

Рис 2. Минимизируемая функция	Рис 3. Минимизируемая функция

Литература

1. Ричардсон Я. Видеокодирование. H.264 и MPEG-4 – стандарты нового поколения. ─ Москва: Техносфера, 2005.

2. Taswell C. The what, how and why of wavelet shrinkage denoising // Computing in Science and Engneering, pp. 12–19, 2000.
NEW FAST GLOBAL MOTION COMPENSATION ALGORITHM based on frame binaryzation

Mochalov I., Ghukov A., Novoghilova T.

Yaroslavl State University

Global motion compensation (GMC) is an important step in video coding and pattern recognition in video. It is needed in automatic video object segmentation for content-based video coding and useful in motion compensation.

Global motion refers to the motion which brings the background from previous frame to current frame. It can be represented in different models such as the simple 2-parameter translation, 6-parameter affine motion, etc.

The estimation of global motion parameters (GMP) can be achieved in many different ways. A common approach focuses on minimizing the squared intensity differences between the current and prediction frames. Optimization is performed to find the GMP which gives the minimum intensity difference. The high computation is due to the need of computing many sets of GMPs for each consecutive two frames. In this paper, we propose a new fast GMC method based on binarization of frame.

This method allows compute global motion parameters if referred image was translate or scale. Firstly current image, for edges detection processes by Laplace filter. Then output image transformed into binary and. This operation also employed to refer image and.

To find scaling parameter and translation parameter next maximization tasks mast be solved

or .

For fast definition we purpose to use integral image, that allow to fast getting sum of elements belong to square region of image.

Due to integral image this task can be writing ,

where is common region of current and scaled refer image.

On last stage translate parameter precise to achieve half-sample or quarter-sample precision. For this task cumulative sum interpolates. Purposed algorithm allows decry low complexity.




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

Курина В.В., Умняшкин С.В.

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

В настоящее время известно множество быстрых алгоритмов вычисления дискретного косинусного преобразования (ДКП), разработанных для различных задач сжатия изображений и видео. Они дают возможность сократить количество операций умножения, необходимых для выполнения преобразований, но, тем не менее, не позволяют полностью исключить эту операцию. В данной работе предлагается использовать для сжатия изображений с потерями дискретное псевдокосинусное преобразование (ДПКП) [1] – простую в вычислении аппроксимацию ДКП, сохраняющую свойство ортогональности. Матрица преобразования W получается с помощью замены значений тригонометрических функций в матрице ДКП их приближенными значениями, что позволяет представить её в виде произведения двух матриц специального вида: . Матрица состоит только из чисел {-2, -1, 1, 2}, а, следовательно, при умножении на эту матрицу можно использовать только операции сложения. Умножение вектора на нормирующую диагональную матрицу можно объединить с процедурой скалярного квантования. Алгоритм сжатия изображений на основе такого преобразования будет востребован в устройствах с ограниченными аппаратными ресурсами, например, карманных компьютерах или мобильных телефонах, а также при реализации в СБИС.

Базовая «JPEG-подобная» схема сжатия включает стандартные этапы: выполнение преобразования, квантование и арифметическое кодирование. Обработка изображения производится по блокам размера . На этапе вычисления двумерного ДПКП сначала строки каждого блока изображения, затем столбцы полученной матрицы умножаются на матрицу . Скалярное квантование объединяется с умножением на матрицу благодаря введению специального шага квантования .

Арифметическое кодирование выполняется с адаптивными статистическими моделями [2]. Для сокращения объема алфавита арифметического кодирования модули коэффициентов кодируются отдельно от их знаков, кроме того, каждый блок разделяется на 8 зон, кодируемых независимо друг от друга. Зоны выбирались таким образом, чтобы дисперсии коэффициентов были близки, и наиболее коррелированные коэффициенты входили в одну зону.

Пусть – проквантованный коэффициент ДПКП с номером в блоке с координатами (начало координат – блок в левом верхнем углу), нумерация внутри блока – от левого верхнего угла по строкам. Зону, в которой все коэффициенты равны нулю, будем называть нулевой. Для описания нулевых зон каждому блоку поставим в соответствие 8-ми битовый ключ. Если все коэффициенты -ой зоны равны нулю, то -ый бит ключа для этого блока равен 0, если хотя бы один коэффициент отличен от нуля, то -ый бит равен 1. Для арифметического кодирования ключей формируется отдельный поток данных.

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

1. 
   Арифметическое кодирование постоянной составляющей. Вычисление разности для двумерной дифференциальной импульсно-кодовой модуляции (ДИКМ): . Абсолютное значение разности кодируется в отдельном потоке. Если , то знак (1 бит) записывается в поток знаков.
   
2. 
   Формирование ключа блока и его арифметическое кодирование.
   
3. 
   Арифметическое кодирование спектральных коэффициентов из ненулевых зон. Просматриваем последовательно все коэффициенты блока за исключением постоянной составляющей. Пусть , тогда, если , закодировать арифметическим кодером, используя модель с номером , и, если , записать в файл знаков. Если , пропустить коэффициент.
   

К приведенному базовому алгоритму можно применить ряд модификаций, что позволит повысить эффективность сжатия, но в той или иной степени увеличит вычислительную сложность. Так, можно использовать квантование с нулевой зоной (dead zone quantization). В этом случае пороги квантования имеют вид: {..., –3kq, –2kq, –kq, kq, 2kq, 3kq,…}, а уровни квантования вычисляются как среднее арифметическое соседних порогов. Такое квантование при k = 1 используется, например, в стандартах JPEG2000, MPEG-2, H.263. Результаты обработки нескольких изображений показали, что оптимальным также является значение k = 1.

Для лучшей адаптации арифметического кодера ко входным данным коэффициенты каждой зоны можно кодировать с помощью нескольких моделей. Например, можно использовать не одну, а две статистические модели. Правило выбора модели кодирования в этом случае будет иметь вид: . (2). Здесь r – номер зоны, в которой содержится коэффициент , – порог для выбора модели кодирования, соответствующий зоне r, – прогноз, то есть величина, которая представляет собой функцию регрессии от уже обработанных контекстных коэффициентов, имеющих высокую корреляцию со значением модуля коэффициента .

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

Возможности повышения эффективности алгоритма сжатия исследуется с помощью теории «битовые затраты-искажение» (rate-distortion theory, R-D theory). Этот подход описан для алгоритмов сжатия изображений, основанных на ДКП [3] и вейвлет-преобразовании [4]. Задача RD-оптимизации заключается в следующем: необходимо найти такой набор ключей блоков и такую величину шага квантования , которые бы обеспечивали минимум функции Лагранжа:

. (3). Здесь – всевозможные наборы ключей блоков; – заданный неотрицательный параметр, определяющий соотношение ошибки восстановления изображения и битовых затрат на его кодирование: чем больше значение , тем хуже качество изображения, и тем меньше битовые затраты; D – ошибка квантования (в силу ортогональности ДПКП равная ошибке восстановления изображения), , R – битовые затраты на арифметическое кодирование.

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

Пусть () – значение (минимальное) функции Лагранжа для блока с координатами ; () – значение (минимальное) функции Лагранжа для всего спектра, ; и – ошибка квантования и битовые затраты на кодирование блока с координатами соответственно. Функция возвращает оценку вероятности символа w в соответствии с текущим состоянием модели кодирования с номером r. Поиск набора ключей блоков , минимизирующего функцию L при заданных значениях q и , выполняется по следующему алгоритму (последовательно для каждого блока):

Определить базовый ключ блока .

3. 
   Определить значение разности для двумерной ДИКМ.
   
4. 
   Вычислить – функцию Лагранжа для данного блока: , .
   
5. 
   Выполнить перебор всевозможных ключей. С текущим значением ключа k вычислить . Если , то , .
   
6. 
   При l = 1,…, 63, если и , то положить .
   
7. 
   Выполнить виртуальное кодирование блока с ключом .
   

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

Количество итераций в процедуре RD-оптимизации можно уменьшить за счет сокращения вариантов поиска оптимальных значений шага квантования и ключей. Так, например, эксперименты показали, что перебор всевозможных ключей на шаге (5) не требуется. Достаточно рассмотреть ключи, получаемые из базового заменой на каждой итерации одного бита, равного 1, на 0. Также выяснилось, что связь между значением шага квантования q и параметра может быть приближенно описана соотношением: , где С – некоторая общая для различных изображений константа, что позволяет сузить интервал поиска оптимального шага квантования.

RD-оптимизация вносит дополнительную вычислительную нагрузку в алгоритм сжатия, но, вместе с тем, значительно улучшает характеристики базового алгоритма (по соотношению величины PSNR и битовых затрат на кодирование).

На графике (Рисунок 1) приведены результаты, полученные при сжатии изображений «Barbara» и «Lena» модифицированным вариантом предлагаемого алгоритма и алгоритмом JPEG на основе ДКП. Сжатие по стандарту JPEG выполнялось с помощью программы Advanced Batch Converter 3.9.24. При анализе экспериментальных результатов из размера полученного файла JPEG вычиталась длина его заголовка.


Рис. 1. График зависимости величины PSNR от количества бит на пиксель изображения
Таким образом, нами предложен алгоритм сжатия изображений, не использующий операции умножения при выполнении преобразования. Его вычислительную сложность можно дополнительно сократить, используя арифметический кодер, реализуемый без операций умножения [5], но при этом также незначительно уменьшится эффективность кодирования.

Предложенный алгоритм по характеристикам PSNR и степени сжатия не уступает JPEG на базе ДКП, более того, на мелко-детальных «высокочастотных» изображениях (типа «Barbara») показывает преимущества, а значит в приложениях, имеющих ограничения на аппаратные ресурсы, может успешно его заменить.

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

Литература

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 r^th bit in the key is set to 0, otherwise (there is a non-zero coefficient(s) in the zone) the r^th 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], далее называемый базовым, использует контекстное кодирование проквантованных коэффициентов , где — исходное значение коэффициента. При этом модель адаптивного арифметического кодера выбирается исходя из прогноза модуля P_j кодируемого коэффициента w_j, который, в свою очередь, строится по соседним уже закодированным коэффициентам преобразования из текущего и родительского саббэнда как некоторая взвешенная сумма их модулей [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.

References

1. 
   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.
   



метод выделения контуров в ЦИФРОВЫХ ПОЛУТОНОВЫХ ИЗОБРАЖЕНИях

Медведева Е.В., Петров Е.П., Тимофеев Б.О.

Вятский государственный университет, г. Киров

Для распознавания объекта на изображении надо искать набор частей изображений, которые соответствуют частям объекта и удовлетворяют соответствующим ограничениям [1].

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

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

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

Для вычисления количества информации в элементах изображения в качестве математической модели (ММ) ЦПИ выбрано одностороннее марковское случайное поле (ОМСП), называемое также двумерной марковской цепью на несимметричной полуплоскости (НСПП) [2,3].

Представление ЦПИ набором из разрядных двоичных изображений (РДИ) позволяет свести задачу построения ММ ЦПИ к построению ММ из РДИ, каждое из которых представляет собой однородную двумерную цепь Маркова с двумя равновероятными значениями , и матрицами вероятностей переходов (МВП) от значения к соседнему значению по горизонтали и вертикали изображения ().

Рис. 1. Области ОМСП с окрестностью из трех элементов	Рис. 2. Фрагмент двумерного бинарного изображения

На рис. 1 представлено ОСМП ЦПИ, разделенное на области , элементы которых являются цепью Маркова различной размерности. Наибольшую сложность представляет алгоритм вычисления количества информации элементов области . Элемент области зависит от трех соседних элементов, входящих в окрестность (рис. 2).

Количество информации в элементе относительно элементов (рис.2) определится выражением вида [3] , (1), где , элементы матрицы .

Для элементов -го РДИ, принадлежащих области (рис.1), количество информации между элементом и различными сочетаниями значений элементов окрестности можно определить по матрице П (2):

,		(2)

где , , и .

Очевидно, что количество информации в элементе РДИ будет минимально, если окрестные элементы , имеют знаки одинаковые с [4].

В случае появления на РДИ областей другой яркости, на границе области один или два окрестных элементов будут иметь разные с знаки, и количество информации в элементе увеличивается. Сравнивая значения вычисленной величины количества информации в элементе изображения с порогом, определяем, будет ли данная точка являться точкой контура.

Значение порога определяется из условия:

. (3).

Толщина линии контура на одном РДИ будет составлять 1 элемент. Известно, что основные детали области можно выделить на старших РДИ (при ), а младшие РДИ (при ) будут составлять фон изображения в виде двумерного шума. На основе моделирования большой совокупности ЦПИ было определено, что для определения контуров изображений достаточно двух старших РДИ (8-го и 7-го).

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

По аналогии с выражением (1), получена формула для вычисления количества информации в элементе относительно элементов окрестности .

, (4), где - элементы матриц вероятностей переходов , - по горизонтали; , - по вертикали; .

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

,		(5)

где элементы матрицы удовлетворяют условию нормировки ; , ; .

Элементы матрицы можно определить по формулам (6) – (11)

		(6)
;		(7)
; ; ; ;		(8)
; ; ; ;		(9)
; ; ;		(10)
; ; ;		(11)

Для удаления точечных помех (1-2 элементов другой яркости) значения вычисленной величины количества информации в элементе изображения сравнивают с порогом .

Значение порога определяется из условия: