Атомарные функции в цифровой обработке сигналов различной физической природы



Скачать 142.78 Kb.
Дата05.03.2019
Размер142.78 Kb.

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

ЭКСПЕРИМЕНТАЛЬНЫЙ КОДЕК ЧЕБЫШЕВСКОГО СЖАТИЯ/ВОССТАНОВЛЕНИЯ ИЗОБРАЖЕНИЙ (GDCT) И ПРОГРАММНЫЙ КОМПЛЕКС ДЛЯ ЕГО ИССЛЕДОВАНИЯ




Радченко Ю.С., Агибалов А.А., Булыгин А.В., Радченко Т.А.

Воронежский государственный университет, 394693, Воронеж, пл. Университетская, 1


Большинство современных стандартов, например JPEG, MPEG1-4, Н.261-264, использует дискретное косинусное преобразование (DCT) при реализации процедуры сжатия и восстановления изображений. Однако существуют и альтернативные методы сжатия. К числу последних относится способ разложения сигналов по базису классических ортогональных полиномов Чебышева (алгоритм GDCT) [1,2]. Он обладает рядом новых сервисных функций, допускает реализацию в виде “быстрых” алгоритмов преобразования и совместим с существующими стандартами на основе DCT. На основе чебышевских преобразований реализован кодек для сжатия и восстановления изображения и звука.

Для исследования характеристик алгоритма GDCT и сопоставления его с алгоритмами на основе DCT разработан программный комплекс. В данной работе дано описание кодека с указанием основных режимов и опций преобразования. Приведены показатели степени сжатия и характеристики потерь качества восстановленного изображения, заложенные в комплексе программных средств для исследования кодека.



1. Теоретические основы преобразования GDCT

Полезный сигнал s(x,y), представляющий собой блок изображения, подвергается биортогональным преобразованиям , . (1)

В (1) , =1/(dmdk), dm – норма ортогонального с весом (z) полинома pm(z), ax,ay – характерные размеры подобласти , z1=x/ax, z2=y/ay. Для последовательного вычисления интегралов в (1) использована квадратурная формула гауссовского типа . Здесь zi – нули полинома рN(z), ортогонального с весом (z); i – числа Кристоффеля. Узлы и веса zi, i однозначно определяются видом полинома рN(z). Соотношения (1) являются общими для разложения по произвольной системе ортогональных полиномов. Для полиномов Чебышева прямое и обратное преобразования (одномерный вариант для нормированного интервала z[-1,1]) имеют вид

, (2), где при m>0 и при m=0. Согласно (2), точки отсчета изображения s(z) берутся неравномерно. Восстановление изображения RM(z) по М спектральным компонентам выполняется в произвольной точке z[-1,1], а не в дискретном наборе точек отсчета, как в DCT. При восстановлении может использоваться сетка отсчетов , где  - субпиксельный сдвиг, n=0,…L-1. Если LN то восстановленное изображение подвергается геометрическому масштабированию.

В двумерном случае сэмплы изображения образуют матрицу . Эта матрица преобразуется в матрицу спектральных коэффициентов C размером MM c помощью прямоугольной матрицы прямого преобразования размером MN. При обратном преобразовании может использоваться прямоугольная матрица размером LM. То есть восстановленный блок имеет размеры LL. Прямое и обратное преобразование Чебышева (GDCT) в матричном виде определяются операциями , . (3)

Возможны два варианта представления матрицы прямого  и обратного  преобразования.

1. Преобразования с симметричными нормировочными сомножителями перед матрицами



, m=0..M-1, i=0..N-1,

, m=0..M-1, n=0..L-1. (4)

2. Преобразования с несимметричными нормировочными сомножителями перед матрицами



, m=0..M-1, i=0..N-1,

m=0..M-1, n=0..L-1 (5)

Вычисление  и  с несимметричными нормировочными сомножителями (5) приводит к спектральным компонентам меньшей амплитуды. Применение симметричных нормировочных сомножителей в (4), приводит к спектральным компонентам большей амплитуды, но упрощает переход от GDCT к DCT.

В общем случае из-за дробного вида нулей полиномов Чебышева , i=1..N, элементы матрицы S – сэмплы не совпадают со значениями изображений в исходных пикселях. Сэмплы изображения в GDCT могут выбираться двояким способом. В первом варианте при двумерном GDCT преобразовании в пределах блока из N1N1 точек берутся NN отсчетов изображения по закону

, , i,j=1..N. (6)

Во втором варианте для определения сэмпла надо производить интерполяцию изображения s(x,y) в точках расположения нулей полиномов Чебышева по отсчетам, находящимся вблизи этих точек. Для этого используется четырехточечная интерполяционная формула Бесселя: s(x,y)=0.25(s00+ s01 + s10+s11)+0.5(u-0.5)( s10 -s00 +s11 -s01)+0.5(v-0.5)( s01-s00 +s11 - s10)+ (u-0.5)(v-0.5)( s11 -s10 - s01+s00), (7)

где u=x-x0, v=y-y0, sk,l=s(xk,yl) (k,l=0,1) - значения в ближайших четырех пикселях, окружающих точку с координатами (x,y). Применение формулы (7) целесообразно в случае, когда сэмпл находится вблизи центра межпиксельной области. Алгоритм GDCT переходит в DCT при выполнении условий: матрица прямого преобразования DCT совпадает с  в (4), где M=N. Обратное преобразование осуществляется с помощью матрицы . Заметим, что в DCT матрицы преобразований квадратные размером (N×N=MM).

Общая схема сжатия цветных цифровых изображений на основе преобразования GDCT содержит этапы. 1) Цветовая перекодировка из {RGB} в {YUV}; 2) Субдискретизация матриц Y,U,V; 3) Сжатие первой ступени путем организации сэмплов согласно формуле Гаусса-Чебышева; 4) GDCT- преобразование; 5) Сжатие второй ступени с матрицами квантования , где q-коэффициент, регулирующий сжатие; 6) сжатие третьей ступени - энтропийное кодирование. Восстановление производится в обратном порядке с возможностью формирования блоков R(LL), L/N11.



2. Реализация кодека

На рис.1 представлен интерфейс одного из вариантов кодека GDCT. В данном кодеке заложены следующие возможности. I. Выбор варианта преобразования GDCT/DCT . II. Выбор параметров GDCT/DCT: а) выбор размера блока N1xN1, б) выбор варианта субдискретизации, в) выбор параметра матрицы квантования q, г) выбор формата прореживания N1/N для GDCT, д) выбор масштаба восстановления изображения L/N1 для GDCT . III. Вычисление сэмплов путем округления до ближайшего пикселя или путем межпиксельной интерполяции. IV . Зашумление: а) изображений, б) спектров. Данная опция позволяет имитировать искажения при фоторегистации и передаче данных по каналу связи. V. Выбор вариантов энтропийного кодирования квантованных спектральных компонент с помощью алгоритмов Хаффмана, арифметического сжатия, RLE и комбинаций алгоритмов RLE + Хаффман, RLE + арифметический . Предусмотрена оптимизация битовой упаковки сжатых данных. На основе чебышевского преобразования был реализован также кодек звука.



3. Характеристики сжатия и критерии качества восстановления

Для исследования различных режимов алгоритма GDCT и сравнения его с DCT были выбраны несколько характеристик сжатия и критериев качества восстановленного изображения [3,4;5]. Степень сжатия оценивалась с помощью а) энтропии компонент и всего изображения в «битах на пиксель»,б) коэффициента сжатия объема данных.

Из критериев качества были отобраны следующие, основанные на разнице значений пикселей исходного S и восстановленного изображений R: 1) средний квадрат ошибки восстановления – MSE, 2) PSNR-(пиковое отношение сигнал/шум), 3) комплексный критерий MSSIM (mean structural similarity index – усредненный показатель структурного подобия) [4] , характеризующий близость изображений S и R по яркости, контрасту и структуре, имеет следующий вид: . Здесь SSIM: structural similarity index - индекс структурного подобия, -номер блока. Индекс выражается следующим образом: . (8). Здесь , , , - выборочные средние и дисперсии в блоках изображений S и R соответственно, - корреляционный момент между областями изображений S и R. , - малые константы[4]. Критерий (8) принимает значения от -1 до 1. Причем значение 1 получается только в том случае, если сравнивается одно и тоже изображение. 4) фактор F, характеризующий искажения высококонтрастных границ на изображении [3]:



(9)

, .

В (9) snr и Rnr исходное и восстановленное изображения, значения горизонтального и вертикального градиентов в точке (n,r), Ig(n,r)- пороговая функция, фиксирующая наличие границы в точке (n,r), -количество пикселей, удовлетворяющих граничным условиям.

Разработанный кодек и программный комплекс позволили всесторонне исследовать алгоритм GDCT и определить области его возможного использования.

Литература

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

2. Радченко Ю.С. Метод сжатия и восстановления изображений на основе быстрых чебышевских преобразований / Ю.С. Радченко // Автометрия. - 2002. - № 4. - С. 32-40.

3. M. Miyahara, K. Kotani, V.R. Algazi Objective Picture Quality Scale (PQS) for Image codong. IEEE Trans. On Comm. 1998, v.46, № 9.

4. Z. Wang, A. C. Bovik, H. R. Sheikh, E. P. Simoncelli, “Image Quality Assessment: From Error Visibility to Structural Similarity”, IEEE Transactions on Image Processing, vol. 13, No. 4, pp.600-612, Apr. 2004.

5. Прэтт У. Цифровая обработка изображений: в 2-х т. / У. Прэтт; – перевод с англ. – М.: Мир, 1982. – Т. 1. – 204 с



EXPERIMENTAL CODEC OF CHEBYSHEV IMAGE COMPRESSION/RECOVERY (GDCT) AND SOFTWARE USED FOR RESEARCH OF SAID CODEC




Radchenko Y., Agibalov A., Bulygin A., Radchenko T.

Voronezh State University, 394693, Voronezh, pl. Universitetskaya, 1.


Most up-to-date standards such as JPEG, MPEG1-4, Н.261-264 use discrete cosine transformation (DCT) when implementing image compression/recovery. However, alternative compression techniques can also be used. These techniques include a method of signal decomposition based on the classical Chebyshev orthogonal polynomials (GDCT algorithm) [1,2]. It has a number of new service function, allows implementation in the form of “fast” transformation algorithms and is compatible with the current standards based on DCT.

The paper provides theoretical basis of the GDCT transformation. It is shown that the transformation using orthogonal polynomials leads to an additional stage of compression. One of the new features of the GDCT algorithm is a possibility of subpixel shift and geometric scaling of the recovered image. In a particular case the Chebyshev compression algorithm goes over into DCT.

A general procedure of colored image compression based on GDCT transformation consists of the following stages. 1) Color conversion from {RGB} to {YUV}; 2) Sub-discretization of matrices Y,U,V; 3) Compression of the first stage by arranging the samples by Gauss-Chebyshev formula; 4) GDCT-conversion; 5) Compression of the second stage using the quantization matrices , where q is a compression control factor; 6) Compression of the third stage using entropy coding. The image is recovered in the reverse order with an opportunity of forming blocks of a different size.

We provide an interface of one of the versions of the GDCT codec. The codec has the following capabilities: I. Selection of the GDCT/DCT transformation type. II. The choice of GDCT/DCT parameters: a) choice of the N1xN1 block size, b) choice of the sub-discretization option, c) choice of the quantization matrix parameter q, d) choice of the N1/N decimation format for the GDCT, e) choice of the image recovery scale. III. Accurate and simplified samples formation. IV. Noise masking of images and spectra to simulate distortions during photoregistration and data transmission over the communications channel. V. Choice of entropy coding options of the quantized spectral components using Haffman algorithm, arithmetic compression, RLE and their combinations.

The software is developed to study the GDCT algorithm performance and to compare it with DCT based algorithms. The software implements the following quality criteria: MSE, PSNR, MSSIM, and some others. The compression factor is characterized by the following: entropy of components and the whole image in “bits per pixel” and compression factor of the data amount. The developed codec and software enable performing detailed analysis of the GDCT algorithm and determining its possible application areas.

References

1. Yuri Radchenko. A method of image compression and recovery based on fast Chebyshev transformations / Yuri Radchenko // Autometria. - 2002. - № 4. - p. 32-40.

2. Yuri Radchenko. RESEARCH OF SIGNAL RECOVERY, SUPPRESSION AND PROCESSING ALGORITHMS BASED ON POLYNOMIAL TRANSFORMATIONS. The 6th World Multiconference of Systhemics, Cybernetics and Informatics. July 14-18 2002, Orlando, Florida, USA. Proceedings, v. VIX, Image, Acoustic, Speech and Signal Processing III, p.262-266.


Повышение эффективности методов внутрикадрового предсказания стандартА H.264 при использовании цифровых сигнальных процессоров

Кутелев А.С., Рудникович А.С.


Томский государственный университет систем управления и радиоэлектроники
634050, г. Томск, пр. Ленина, 40, Тел.: (382-2) 413-439, e-mail: kutelev@tu.tusur.ru
Непрерывно возрастающая потребность в передаче всё большего количества информации при ограниченной полосе пропускания линий связи, приводит к разработке всё более сложных алгоритмов сжатия данных, в том числе видеоданных. В настоящее время широкое распространение получили такие стандарты как MPEG-2 и MPEG-4. Наиболее эффективным в настоящее время является стандарт H.264 [1, 2]. Одним из методов повышения степени сжатия, применённым в данном стандарте, является внутрикадровое предсказание яркостных и цветоразностных отсчётов изображения по закодированным и реконструированным элементам соседних блоков.

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

В данной статье предлагается алгоритм быстрого поиска оптимального режима пространственного предсказания для блоков яркости размером 4x4 элемента в соответствии со стандартом H.264. Алгоритм оптимизирован для использования на сигнальных процессорах TMS320C64xx компании Texas Instruments Inc. Выбор процессоров семейства TMS320C64xx для решения поставленной задачи обусловлен уникальной архитектурой и системой команд данных процессоров.

Конфигурация отсчётов соответствующая рассматриваемому случаю приведена на рис. 1. Элементы a-p предсказываются по отсчётам A-M. Всего возможно девять режимов предсказания, восемь направленных режимов и режим номер 2 (DC). На рис. 1 также изображены направления прогноза соответствующие различным направленным режимам предсказания.


Рис. 1

Одним из наиболее эффективных алгоритмов быстрого пространственного предсказания является алгоритм, использующий карту краёв [3]. Для работы подобного алгоритма необходимо предварительно обработать исходное изображение двумя ядрами оператора Собеля (рис. 2). Таким образом, каждому элементу (кроме крайних элементов) изображения сопоставляется свой граничный вектор  со своей амплитудой и направлением. Математически точно амплитуда вектора вычисляется как корень из суммы квадратов, однако для ускорения быстродействия в рамках применения данного алгоритма рекомендуется пользоваться соотношением . Точно определять направление вектора также не требуется, поскольку в стандарте H.264 число направлений, к которым может применяться пространственное предсказание, ограничено. Необходимо лишь знать какому из 8 возможных направлений соответствует отношение .


Рис. 2 – Маски ядер оператора Собеля

, , . 

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

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

Таким образом, пирамидальные алгоритмы для принятия решения выполняют прогноз блока не во всех 9-ти возможных режимах, а в 4-х или 6-ти, в зависимости от конкретного алгоритма. Работа подобных алгоритмов, не требует ни какой предварительной обработки исходного изображения. На рис. 3а приведена блок схема алгоритма AP55P2. Данный алгоритм является наиболее точным среди пирамидальных алгоритмов. Все остальные алгоритмы могут быть получены путём его упрощения. Например, алгоритм с названием AP55 отличается от алгоритма AP55P2 отсутствием в блок схеме режима номер 2, а алгоритмы AP33, AP33_1 не учитывают режимы с номерами 2, 3 и 4. В свою очередь, алгоритмы AP55_1, AP55_2 являются модификациями алгоритма AP55. Внесённые в них изменения позволяют существенно повысить быстродействие при незначительно потере точности.

На рис. 3б приведена блок схема алгоритма реализованного на базе цифрового сигнального процессора. Экспериментальные данные показали, что данный алгоритм является оптимальным при реализации на базе выбранного сигнального процессора.

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

, , где – яркостные отсчёты исходного блока; – яркостные отсчёты предсказанного блока.


а) б)
Рис. 3 – Блок-схемы пирамидальных алгоритмов

Для выбора оптимального алгоритма при реализации его на базе сигнального процессора была проведена серия экспериментов с алгоритмами, реализованными на персональном компьютере в среде Microsoft Visual C++. При сборе экспериментальных данных использовались пять видео потоков продолжительностью по сто кадров. В таблице 1 приведены экспериментальные данные для различных пирамидальных алгоритмов. В данной таблице приведено процентное увеличение суммы абсолютных ошибок (SAE) относительно эталонного алгоритма, выполняющего полный перебор. Так же в таблице приведено нормированное время, затрачиваемое на анализ одного блока (t/tmax), где tmax – время, затрачиваемое алгоритмом AP55P2 на обработку одного блока.



Таблица 1 – Характеристики алгоритмов пирамидального поиска




Алгоритм

AP55P2

AP55

AP55_1

AP55_2

AP33

AP33_1

SAE, %

2,38

4,13

4,53

5,49

10,46

13,11

t/tmax

1,00

0,94

0,80

0,74

0,76

0,70

Обычно при решении задач сжатия видеоданных находится компромисс между качеством и быстродействием. Исходя из этого, логичным было бы выбрать, например, алгоритм AP55_1 или AP55_2. Данные алгоритмы занимают среднее положение по быстродействию и дают относительно небольшое увеличение ошибки. Однако, поскольку основной задачей являлась разработка алгоритма для сигнального процессора TMS320C64xx, способного выполнять до 8000 MIPS, был выбран алгоритм AP55P2, имеющий наибольшую точность. Данный выбор является оптимальным, поскольку в этом случае имеется возможность максимально использовать ресурсы процессора. Отметим так же, что основной задачей являлась реализация алгоритма на языке программирования Ассемблер. Данный выбор обусловлен жесткими требованиями к быстродействию алгоритма. Практика показывает, что программирование на языке Ассемблер позволяет в разы (от 4 до 10) увеличь быстродействие прототипов, написанный на языке Си.

В процессе реализации алгоритма AP55P2 на базе сигнального процессора, в целях достижения оптимальных параметров, структура алгоритма была несколько изменена. В итоге был получен более точный алгоритм с ошибкой SAE менее одного процента (0,76%). Блок схема полученного алгоритма была приведена на рис. 3б. На поиск оптимального режима предсказания и предсказание блока в найденном режиме с расчётом разностного блока алгоритм тратит в среднем 80 тактов. При сжатии стандартного видеосигнала процессор с тактовой частотой 600 МГц затрачивает 9 процентов вычислительного ресурса на предсказание для яркостной составляющей. Отметим, что современные процессоры семейства TMS320C64xx имеют тактовые частоты до 1 ГГц.

В работе предлагается алгоритм пирамидального поиска оптимального режима предсказания для блоков яркости размером 4x4 элемента в соответствии со стандартом H.264. Алгоритм был реализован на базе цифрового сигнального процессора TMS320C64xx на языке программирования Ассемблер с учётом аппаратных особенностей. Реализованный алгоритм не требует никакой предварительной обработки изображения и выделения дополнительной памяти.

При реализации алгоритма на базе цифрового сигнального процессора, наиболее выгодным, оказалось, выполнять перебор 8-ми из 9-ти режимов (рис. 3б) для каждого блока, что практически соответствует алгоритму полного перебора. Таким образом, применение сигнального процессора TMS320C64xx позволило удовлетворить одновременно двум противоречивым требованиям, то есть обеспечить высокую скорость и точность предсказания.


Литература


  1. ITU-T H.264. Advanced Video Coding for Generic Audiovisual Services. ITU-T, 2003.

  2. Richardson I.E.G. H.264 and MPEG-4 Video Compression. John Wiley & Sons, 2003.

  3. Feng PAN, Xiao LIN, Rahardja SUSANTO, Keng Pang LIM, Zheng Guo LI, Ge Nan FENG, Da Jun WU, Si WU. Fast Mode Decision for Intra Prediction // Doc. JVT-G013, 2003.



increasing the efficiency of intra prediction methods for standard H.264 using digital signal processors


Kutelev A., Roudnikovitch A.

Tomsk state university of control systems and radioelectronics


Department of television and control
634050, 40, Lenin Ave., Tomsk, Russia Ph.: +7 (3822) 41-34-39

Increasingly growing need in transferring of more information though the limited bandwidth of communication lines results in development of more complex data compression algorithms including video. Nowadays such standards as MPEG-2 and MPGE-4 have become widely spread. Today the most efficient standard is H.264. One of the methods to increase the compression ratio applied in this standard is Intra frame prediction of luma and chroma blocks of image according to already coded and reconstructed elements of neighbor blocks.

In the present work an algorithm of fast search for optimum mode of Intra prediction for luma blocks of 4x4 elements in size according to standard H.264 is offered. Realization of an algorithm on the basis of digital signal processor TMS320C64xx of Texas Instruments is considered.

One of the most effective algorithms of fast Intra prediction is an algorithm that uses edge map, for operation of which it is necessary to preliminarily process the initial image by two kernels of Sobel operator. Since this algorithm requires a extra amount of memory to be allocated and does not allow many calculations to be carried out at the same time, its realization on the basis of the chosen processor was turned down.

Several algorithms of pyramidal search for optimal mode of Intra prediction were offered as an alternative. Their core principle lies in predicting blocks in a certain sequence, depending on results of previous calculation.

In the end an algorithm that produces an error less than one percent (0.76%) was invented. It spends about 80 cycles in average to search for an optimal mode of prediction and to predict a block in the found mode calculating a difference block. During compression of standard video signal a 600 MHz processor spends 9% of computational resource to predict the luma component. Note that modern processors of TMS320C64xx family have clock rate up to 1 GHz.

So the application of TMS320C64xx signal processor made it possible for the two contradicting requirements to be met - to enable high speed and precision of prediction.

The algorithm was realized on the basis of digital signal processor TMS320C64xx using Assembler programming language taking into account the hardware features. The realized algorithm does not require any preliminary processing of image and allocation of extra memory.







Цифровая обработка сигналов и ее применение

Digital signal processing and its applications


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©vossta.ru 2017
обратиться к администрации

    Главная страница