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

КОМПЬЮТЕРНЫЕ НАУКИ А

УДК 621.39

МЕТОД РЕКОНСТРУКЦИИ ИЗОБРАЖЕНИЙ В НЕРАВНОМЕРНОМ БАЗИСЕ СПЕКТРАЛЬНЫХ КОЭФФИЦИЕНТОВ

Применяемые методы восстановления видеоданных недостаточно эффективны при обработке изображений и не удовлетворяют требованиям, которые предъявляются к ним, по времени обработки и качеству восстановления видеоданных [2].

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

Методы восстановления изображений, реализованные на основе статистических кодов, имеют ряд существенных недостатков, основные из которых заключаются в следующем:

БАРАННИКВ.В., РЯБУХА Ю.Н., КРАСНОРУЦКИЙ А.А.___________________________

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

Введение

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

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

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

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

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

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

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

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

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

Для устранения выявленных недостатков статистических методов кодирования видеоданных был предложен метод кодирования трансформант ДКП на основе неравномерного базиса спектральных коэффициентов [3]. Метод кодирования в неравномерном базисе спектральных коэффициентов (НБСК) работает с трансформированным сегментом ортогонального

46

РИ, 2013, № 3

преобразования (ДКП). Трансформанта ДКП представлена в виде двумерного массива, элементами которого являются дискретные значения базисных функций. При одномерной выборке столбца трансформанты образуется одномерное число в неравномерном базисе спектральных коэффициентов, удовлетворяющих смешанной системе оснований. Рассмотренный метод изложен в [4]. Под одномерным кодированием трансформированного сегмента в НБСК

определен процесс формирования кода N-Z’Y) для i-го столбца Yi

процесс

кодирования i-го столбца (Z; Y) -й трансформанты ДКП определяется выражением:

n(zy) = zyij ПЧ

j=1 n=j+1 ’

Система оснований позволяет определить верхнюю границу hmax значения кода одномерного числа НБСК. Из свойств НБСК чисел следует, что максимальное значение кода определяется из неравенства:

< hmax ,

где N(jZaX) - максимально возможное значение кода для заданного вектора оснований Л(С, Y).

Знание верхней границы hmax необходимо для определения длины кодового представления d(Z,Y) одной

компоненты Yi(Z’Y) трансформанты. В этом случае принимается условие:

d

N(Z

-L ^ ГП!

Y max

где

n

П=i+1

n - весовой коэффициент элемента y ij; У ij -

элемент столбца трансформанты.

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

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

Основной материал

Разрабатываемый метод восстановления заключается в получении по значению кода числа НБСК исходной трансформанты ДКП. Реконструкция сегмента изображения производится после обратного ДКП. Данный метод имеет ряд особенностей, определяемых процессом сжатия изображения [5].

где d(Z’Y) - длина кодового представления i -го столбца трансформанты; [log2 hmax] +1 - количество двоичных разрядов на представление максимального

значения кода N(jZax) одномерного числа НБСК.

Тогда длина d(]Z1,Y) всей информационной части кодовой последовательности составит:

d(nfY) = m([log2 hmax] + 1) ,

где m - количество столбцов трансформанты; m([log2 hmax] +1) - количество разрядов на представление m кодов НБСК чисел.

Верхняя граница hmax значения кода одномерного

числа НБСК для заданной системы оснований Л(^ Y) вычисляется как накопленное произведение оснований всех элементов, т. е.

П

hmax = П^ .

П=1

С учетом выражения (2) формула (1) примет вид:

Для восстановления сегмента ДКП необходимо наличие служебной информации о размерах сегмента (Z; Y) и системе оснований Л(^. Система оснований определяет длину информационной части сжатого представления трансформанты.

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

На приемной стороне система оснований содержится в служебной части кодовой последовательности сжатого представления трансформанты.

d(Z’Y) = [log2 П^П ] + 1.

П=1

Зная длину кодового представления для одного столбца трансформанты ДКП в неравномерном базисе спектральных коэффициентов, получаем возможность

определить длину d^fY) информационной части кодовой последовательности трансформанты. Она соответствует сумме длин кодовых представлений в НБСК всех столбцов трансформанты, т.е.

df = md(Z,Y) = m([log2 П^п ] +1).

n=1

РИ, 2013, № 3

47

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

Длина d(Z;Y) собранной кодовой последовательности

всей трансформанты ДКП определяется как количество бит, которым представлена служебная часть

d(Z;Y) и длина d(Z,Y) кодового представления всех столбцов трансформанты, она выражается формулой:

d(Z; Y) = dSZ; Y)+d(ZY).

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

- размеры сегментов изображения могут быть различными;

- сегменты изображения могут иметь разную систему оснований, что объясняется разной содержательной частью трансформанты изображения (рис. 2).

Рис. 1. Основные условия, влияющие на длину информационной части кодового представления трансформанты

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

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

Для этого необходимо:

1. Отвести под длину служебной части d^j-* кодового представления числа НБСК для одной j -й строки

(Z; Y) трансформанты ДКП b бит (например, b = 8 бит). Длина кодового представления элемента основания составит:

dSZ1Y) к = K dj ... = ... ^У) = log2 b .

Тогда длина служебной части d(Z;Y) всей кодовой последовательности трансформанты ДКП соответственно определяется длинами кодовых представлений всех элементов основания:

dSZ;Y) = ndj = nlog2b ,

где n - количество строк трансформанты ДКП.

2. Выделить из собранной кодовой последовательности служебную часть. Первый бит всей кодовой последовательности является служебным, а длина ее служебной части составляет n log2 b бит. Следующий за ним nlog2 b +1 бит будет информационным.

3. Определим длину информационной части кодового представления трансформанты ДКП. Необходимо

П

перемножить все основания П*п для (Z; Y) -й транс-

п=1

форманты ДКП Y(Z; Y). Получим максимальную длину d(Z’Y) кодового представления одного столбца

трансформанты ДКП, равную: d; ’ = [log2 П^п] +1.

п=1

Затем определим длину df^ кодового представления информационной части всей кодовой последовательности N(Z,y) трансформанты ДКП:

d(jZf'Y) = m([log2 П\ + 1]).

П=1

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

48

пакеты данных

dP I dP___________________________________)

d

dinf

Рис. 1. Технология определения информационной и служебной части трансформанты ДКП

РИ, 2013, № 3

p(Z+1;Y) _ p(Z;Y) +1 p(Z;y) определяется как P1 _ p +где P - пос-

ледняя позиция кодограммы предыдущей трансформанты, которая находится как:

P(Z;Y) _ nlog2b + m([log2 П^п ] +!).

п_1

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

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

Общая схема процесса реконструкции изображения представлена на рис 3.

На вход декодера поступает совокупность ^(Z,y);N-Z’y)}: вектор оснований Л(^ и N-Z’Y) кодовые представления столбцов (z; g)^ трансформанты ДКП. Далее проводится декодирование в неравномерном базисе спектральных коэффициентов.

В результате декодирования получим трансформированный сегмент изображения Y'(Z;Y) .

При адаптивном деквантовании компонент трансформант происходит восстановление части видеоинформации, отброшенной для устранения визуальной избыточности. Эта процедура реализуется умножением компонент трансформанты y'(Z;y) на элементы матрицы квантования. Для дальнейшей обработки при обратном трансформировании используется деканто-

ванный сегмент ДКП Y''(Z,Y) . Обратное трансформирование реализуется при обратном ДКП. Далее производится сборка сегментов изображения и его восстановление. На выходе схемы восстановления получим

восстановленный массив изображения Xi,j.

Процесс декодирования кодового представления трансформанты ДКП в НБСК представлен на рис.4.

Для начала процесса декодирования в НБСК необходимо иметь вектор оснований

Л(^) _^п} и вектор весовых коэффициентов H(Z;Y) _{h(Z,Y),...,h(Z’Y),...,hnZ,Y)} элементов столбцов трансформанты.

Система оснований известна из служебной части кодового представления трансформанты ДКП.

Весовые коэффициенты для элементов i -го столбца (z^-й трансформанты определяются на основании

выражения: h-Z’ _ П^п .

П_і+1

С учетом системы оснований Л т) для i-го столбца (z^-й трансформанты и весовых коэффициентов

'

процедура декодирования компоненты у у транс-

форманты строится по следующему правилу:

yi(Z;Y) _ [Ni Ji,j L

-] - [

N

h

] ^ i , i _ 1,

m,

где yi(jZ;Y) - декодированный элемент i -го столбца

трансформанты; N-Z’y) - кодовое представление і -го столбца трансформированного сегмента в неравномерном базисе спектральных коэффициентов; ^-основание элемента і -го столбца трансформированного сегмента НБСК.

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

Далее, производится деквантование. Для получения

»

элементов у і j деквантованного сегмента Y

трансформанты ДКП производится умножение элементов уi (Z;Y) декодированного НБСК трансформированного сегмента Y'(Z,Y) изображения на элементы

_ '

Qi,j матрицы квантования: у і j _ Уу qy.

{Л( Z,Y );N( Z ,y) }

Телекоммуникационная

сеть

Y( Z, Y )•

Адаптивное

деквантование

компонент

трансформанты

Y''

З

Этап обратного трансформирования

X

=3

изображение

Рис. 3. Общая схема восстановления трансформированного изображения

РИ, 2013, № 3

49

Согласно схеме восстановления сегментированного изображения выполняется обратное ДКП. Обратное ДКП сегмента изображения осуществляется на основе процедуры:

n-1 m-1

1J

1 n — 1 m—1 ,y ,

C(i)C(j) £ £ y'(Z;Y)cos

і=1 j=1

i,j

(2Z + 1)in" •• cos (2y+1)in

2n 2m ,

где C(x) = j ^2 ’ X 0 , xi,j - элемент восстанов-[i, x Ф 0

ленного сегмента изображения.

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

Время реконструкции T,(Z’Y) сегмента изображения определяется общим временем декодирования трансформанты ДКП, деквантования и обратного трансформирования (выполнения обратного ДКП, сборки сегментов изображения), т.е.:

T'

= dc + Tdq + Todcp ,

где Tdc - время декодирования (z; g) -го сегмента изображения на основе НБСК; TdZ,Y) - время деквантования (z; g)-ro сегмента изображения; Т0^ -

время выполнения обратного дискретного косинусного преобразования.

Временные затраты на декодирование одной трансформанты ДКП T<°Z’Y) определяется временем декодирования кода НБСК для всех столбцов трансформированного (z; g) сегмента изображения:

TdcY) = £ tdci = mtdci,

i=1

где t dci - время восстановления одного столбца трансформанты ДКП.

Время декодирования tdci одного j -го столбца трансформанты ДКП, состоящего из n элементов, определяется по формуле:

n

tdci = £tdci,j = ntdci,j ,

i=1

здесь tdci,j - время получения элемента столбца трансформанты ДКП.

Учитывая выражение (5), формула (4) примет вид:

(Z ) m n

Tdc ) = ££tdci,j = mntdci,j . i=1i=1

Время реконструкции T'(Z,Y) трансформированного (z; g)-ro сегмента изображения зависит от общего количества арифметических операций умножения, деления и вычитания, выполненных на всех этапах реконструкции трансформанты.

Кодовая последовательность N< Z ,Y) трансформированного сегмента изображения

Р служебная часть информационная часть кодовой последовательности трансформанты ^

(Z .Y) d(?.Y) d(Z ,Y) I

dt,i dt,m

Система оснований Л<с,1,)

\ / ^T-

N<Z ;y ) • • • N<Z; Y) • • • N(Z; Y) iN m

I

_ J

значения кодов НБСК Ni<Z,Y) столбцов трансформанты

Х1 • • ‘ Xn

n

h

Весовые

коэффициенты H<Z,Y)

h1 • • • hn

n<Z:y) [h(Z:Y) ]

N < Z :Y) /

( h(Z :Y) Vх i

N<Z:Y) /

M i] xi

___________ (— ) ___________

L_________________________________________

y' <Z-Y) y i,J

Ж ж

Рис. 4. Схема декодирования элементов столбцов трансформированного сегмента изображения в НБСК

Yl n Hh 0 Hi 1

и 0 0 io Б

0 ) 0 P

0 ) 0 P

0 Го P

и 0 0 Го 1

II 0 Го P

II 0 1—5-і a I

Y^y).

декодированный НБСК квантованный столбец трансформанты

50

РИ, 2013, № 3

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

ки распространяются только в пределах одного кода одномерного числа в неравномерном базисе спектральных коэффициентов. Следовательно, их влияние распространится только на один столбец трансформанты;

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

Оценка потерь качества восстановления проводится по критерию среднеквадратичного отклонения значений элементов исходного сегмента изображения и значений элементов восстановленного сегмента изображения:

“Z

ід

2

О

i=1j=1

m Z n

Z n Y

,(Z>Y) „ .

где Xi j - восстановленный элемент сегмента изоб-

ат)

ражения; xy - исходный элемент сегмента изобра-

жения.

Выводы

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

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

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

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

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

Литература: 1. GonzalesR.C. Digital image processing /R.C. Gonzales, R.E. Woods. Prentice Inc. Upper Saddle River, New Jersey 2002. 779 p. 2. Баранник В.В., ПоляковВ.П., Кодирование трансформированных изображений в инфоком-муникационных системах. Х. ХУПС. 2010. 210 с. 3. Баранник В.В. Метод сжатия изображений на основе неравновесного позиционного кодирования битовых плоскостей /В.В. Баранник, Н.К. Гулак, Н.А. Королева //Радіоелектронні і комп’ютерні системи. Х.: ХНАУ “ ХАІ”, 2009. Вип. 1. С. 55- 61. 4. BarannikV. Image Encoding Design Based On 2-D Combinatory Transformation / V. Barannik., V. Hahanov // International Symposium [ІЕЕЕ East-West Design & Test], (Yerevan, Armenia, September 7 - 10, 2007) / Yerevan: 2007. P. 124 - 127. 5. Баранник В.В. Кодирование трансформированных изображений в инфокоммуникационных системах / В. В. Баранник, В.П. Поляков. Х.: ХУПС, 2010. 212 с.

Поступила в редколлегию 12.08.2013

Рецензент: д-р тех. наук, проф. Хаханов В. И.

Баранник Владимир Викторович, д-р техн. наук, проф., начальник кафедры Харьковского университета Воздушных Сил. Научные интересы: обработка информации в инфокоммуникационных системах. Адрес: Украина, 61000, Харьков, ул. Сумская, 77/79, тел. (057) 704-96-53.

Рябуха Юрий Николаевич, канд. техн. наук, соискатель кафедры Боевого применения и эксплуатации АСУ Харьковского университета Воздушных Сил. Научные интересы: кодирование и защита информации для передачи в телекоммуникационных сетях. Адрес: Украина, 61000, Харьков, ул. Сумская, 77/79, E-mail: barannik_v_v@mail.ru.

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

Красноруцкий Андрей Александрович, канд. техн. наук, начальник кафедры бортового оборудования и аэрокосмической разведки Харьковского университета Воздушных Сил. Научные интересы: кодирование и защита информации для передачи в телекоммуникационных сетях. Адрес: Украина, 61000, Харьков, ул. Сумская, 77/79, тел. (057) 704-96-53. E-mail: barannik_v_v@mail.ru.

Арифметические операции Декодирование компоненты трансформанты

Деление 2 2mn - -

Умножение 2 2mn mn 2mnlog2 mn

Вычитание (сложение) 1 mn - 2mnlog2 mn

РИ, 2 013, № 3

51