Английское название метода - Subband Coding (SC). Дословный пере­вод - кодирование поддиапазонов.

Цель метода - сжатие потока R-битовых элементов в предположении, что значение каждого из них отличается от значений соседних элементов незначительно: Si я Sj.i.

Основная идея состоит в том, чтобы формировать два потока: для каж­дой пары S2i, S₂i+i сохранять полусумму (S2J + S₂i+i)/2 и разность (S2i - S2J+1). Далее эти потоки следует обрабатывать раздельно, поскольку их характери­стики существенно различны.

В случае модели "аналоговый сигнал" физический смысл потока с полу­суммами - низкие частоты, а с разностями - высокие. Методы SC предна­значены для сжатия элементов с "количественными" данными, а не "качест­венными". Самый распространенный вид количественных данных - муль­тимедийные. Но не единственный: например, потоки смещений и длин, формируемые методом семейства LZ77, тоже содержат количественные данные.

Размер данных в результате применения SC не изменяется. Более того, в потоке с разностями размер элементов R может даже увеличиваться на I бит: R'=R+1, поскольку для сохранения разностей R-битовых элементов требуется (R+1) бит.

Для сжатия результата работы метода может быть применена любая комбинация методов - RLE, MTF, DC, PBS, HUFF, ARIC, ENUC, SEM...

Методы этой группы являются трансформирующими и поточными (т. е. могут применяться даже в том случае, когда длина блока с данными не задана). В общем случае скорость работы компрессора равна скорости де­компрессора и зависит только от размера данных, но не от их содержания: Скорость = 0(Размер). Памяти требуется всего лишь несколько байтов.

Из краткого описания общей идеи видно, что

1) к обоим получающимся потокам можно повторно применять метод этого же семейства SC;

2) метод можно применять и к параллельным потокам (например, левый и правый каналы стереозвука);

3) при сжатии аналогового сигнала с потерями степень сжатия обратно пропорциональна ширине сохраняемого диапазона частот;

4) можно сохранять не полусуммы и разности, а суммы и полуразности (поскольку сумма и разность двух чисел - либо обе четны, либо обе нечетны, одну из них можно делить на 2 без всяких осложнений).

В базовом простейшем случае иллюстрируется тремя строками:

for (i=0; i<N/2; i++) { // цикл по длине исходного массива
D[2*i]=(S[2*i]+S[2*i+l])/2; // четные - с полусуммами
D[2*i + l]=S[2*i]-S [2*i+l]; // нечетные - с разностями

} // (1)

где S[N] - исходный массив (Source, источник); D[N] - выходной массив преобразованных данных (Destination, приемник, с дельтами, т. е. разностя­ми, и полусуммами).

Если результат пишем в тот же массив S:

for (i=0; KN/2; i++) { // (2)

d=S[2*i]-S[2*i+l]; // разность, и дальше так же:
S[2*i]=(S[2*i]+S[2*i+l])/2;// четные будут с полусуммами,
S[2*i+l]=d; // нечетные элементы массива -

) //с разностями

Если же формируем два выходных массива:

for (i=0; KN/2; i++) { // (3)

A[i]=(S[2*i]+S[2*i+l])/2; // полусумма (Average)

D[i]=S[2*i]-S[2*i+l]; //разность (Delta)

}

то каждый из них - вдвое короче, чем исходный S.

Если его длина N нечетна, добавим к концу S элемент S[N], равный по­следнему S[AM]; в результате он добавится к массиву А, а к D добавится нуль:

A[N/2]=S[N-1]; // последняя полусумма
D[N/2]=0; // последняя разность

Если известно, что в результате разности может возникнуть переполне­ние, т. е. невозможно будет записать полученное значение, используя ис­ходное число битов R(R- размер элементов исходного массива S):

if ( (S[2*i]-S[2*i+1])!=(S[2*i]-S[2*i+l])mod(n) ) {} // п=(2 в степени R)

то можем поступить одним из следующих четырех способов:

1. Изначально отвести под разности массив элементов большего размера:

char A[N]; // если под полусуммы 8 бит,

short D[N]; // то под разности 9 бит, а реально даже 16

2. Формировать третий (битовый) массив с флагами переполнений:

D[i]= S[2*i]-S[2*И1]; //сохраним разность;

if(D[i]!=S[2*i]-S[2*i+l])

//если не хватило битов для записи,

Overflow[i]-l; //установим флаг в 1 else Overflow[i]=0; //иначе его значение - нуль

3. Использовать текущее значение разности для вычисления полусуммы:

(4) D[i]= S[2*i]-S[2*i+1];

// реально D[i] = (S[2*i]-S[2*i+l])mod(n); A[i]= S[2*i]-D[i]/2;

//это полусумма, если не было переполнения

4. Наоборот, использовать текущее значение суммы для вычисления по­
луразности:

(5) A[i]= S[2*i]+S[2*i+1];

// реально A[i]=(S[2*i]+S[2*i+l])mod(n); D[i]= S[2*i]-A[i]/2;

// это полуразность, если не было переполнения

Упражнение. Можно ли использовать полуразности для вычисления сумм? А полусуммы для вычисления разностей?

Обратное преобразование

Обратное преобразование ничуть не сложнее прямого:

for (i=0; i<N/2; i++) { // (3")

S[2*i]= ( 2*A[i]+D[i] ) /2 ;

S[2*i+1]=( 2*A[i]-D[i] ) /2 ; }

Если использовалась защита от переполнения и брались разности для вычисления полусумм:

S[2*i]= A[i]+D[i]/2; // (4^Ч)

S[2*i+1]= S[2*i]-D[i];

// реально D[i]=(S[2*i]-S[2*i+l])mod(n)

Пути улучшения степени сжатия

Общий случай

К получаемым потокам можно и дальше рекурсивно применять разло­жение на полусуммы (Average) и разности (Delta). При сжатии аналоговых сигналов, как правило, полезно дальнейшее разложение полусумм. Есть два пути создавать 3 выходных потока или блока: 1. Originall

Averagel+Deltal i

DA+DD

(DA - Average2, получаемая при разложении разностей Delta 1, DD - Delta2, получаемая при разложении Delta 1. Аналогично с остальными обозначе­ниями).

2. Original^ Average l i+Deltal AA+AD

Пять вариантов создания четырех:

1. Original^
Averagel+Delta 11

DA+DDl DDD+DDA

2. Originall
Averagel+Delta 1 ^

DA++DD DAD+DAA

3. Original 11
veragel+ + Delta 1^

AA+AD DA+DD

4. Original^
Averagei+Delta

aaI+ad

AAA+AAD

5. Original*
Averagel+Delta

AA+ADl ADA+ADD

Четырнадцать вариантов создания пяти и т. д.

Упражнение. Изобразите эти 14 вариантов.

При принятии решения о целесообразности разложения некоторого по­тока или блока S на А и D оказывается полезен следующий прием. Будем заглядывать на несколько шагов вперед: если непосредственные результаты разложения А и D сжимаемы суммарно хуже, чем исходный S, может ока­заться, что если разложить дальше А и/или D, то только тогда результат -три или четыре потока, по которым восстановим S, - сжимаем лучше, чем S.

Если же и эти АА, AD, DA, DD дают в сумме худшее сжатие, заглянем еще на шаг вперед, т. е. попытаемся разложить эти вторичные результаты, и т. д., пока глубина такого просмотра не достигнет заданного предела, или же дальнейшее разложение окажется невозможным из-за уменьшения длин в 2 раза на каждом шаге.

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

При сжатии параллельных потоков

Если имеем два параллельных потока X и Y, каждая пара (Х_{, Yj) описы­вает один объект. Например, X, - адрес, Yi - длина или же X - угол, Y -расстояние. В случае "аналоговый сигнал" пара (Xj.Yj) относится к одному моменту времени tj.

Число потоков и их длина N остаются неизменными. Можно оставлять один из двух исходных потоков вместо потока с полусуммами (а при сжа­тии с потерями и вместо разностей): X+D или Y+D вместо A+D.

Теперь можно искать границы таких блоков, внутри которых один из этих четырех вариантов - X+Y, X+D, Y+D, A+D - существенно выгоднее остальных трех.

Заметим, что применение LPC, в том числе дельта-кодирования, к пото­ку полусумм А выгоднее, чем к X и/или Y: первая производная потока с по­лусуммами A'[i] не превосходит (по абсолютному значению) максимума первых производных X'[i] и Y'[i]:

А', = Ам-А, = (X_i+l+Y_i+l-a_i+l)/2 - (X^Yгад/2 , (2.9)

"издержки округления" о* равны единице, если сумма соответствующих X_k+Y_k нечетна, а арифметика используется целочисленная; иначе a_k=0.

А',=(Х_!+,-Х; +Y_i+I-Yi +a; -омУ2 = (X*,+Y', + a,~a_i+I)/2. (2.10)

Таким образом, значение А*; лежит внутри интервала [X'j ,Y'j] (рис. 2.2).

Заметим также, что (при использовании целочисленной арифметики из-за округлений) важен порядок действий: дельта-кодирование потока полу­сумм А даст другой результат, чем полусумма результатов дельта-кодиро­вания X и Y: в первом случае (2.9) и (2.10), во втором A"j= (X'j+Y'j)/2 .

Если сумма (X'j+Y'j) нечетна, а aj-a_i+i=l, то A'j * A"j, А\=А"|+1.

Например, если Xj=0, X_i+i=Yi-Y_i+i=l, то A'j =1 (по формуле (2.9)), aA"Kl+0y2-0.

Если потоков более двух, например 5 (сжатие именно пятиканального звука становится все актуальнее), возникает задача нахождения оптималь­ных пар для применения к ним субполосного кодирования. Здесь тоже воз­можны оба вышеописанных приема: и "просмотр на несколько шагов вперед", еще более усложненный, и "поиск границ интервалов времени", опти­мальных для выделяемых затем пар. Например, может выясниться, что сжа­тие существенно лучше, если использовать знание того, что на интервале между 32765-м и 53867-м элементами очень близки первая разность (при первом разложении) внутри полусуммы (1,4), т. е. полусуммы 1-го потока с 4-м, и первая разность внутри полусуммы (3,7).

Раньше на каждом этапе можно было принять одно из двух решений: применить SC-преобразование к блоку или не применять. Теперь же - одно из пяти:

1) применить SC к строкам блока;

2) применить SC к столбцам блока;

3) применить SC к строкам блока, а затем к столбцам;

4) применить SC к столбцам блока, а затем к строкам;

5) не применять SC к блоку вообще.

Пункты 3 и 4 не совсем эквивалентны при использовании целочислен­ной арифметики из-за округлений, но математическое ожидание расхожде­ния их результатов равно нулю (рис. 2.3).

При сжатии аналоговых сигналов

Появляются дополнительные возможности: ■ сжимая с потерями, округлять с заданной точностью: на каждом шаге SC

и/или после всех этапов SC;

■ сохранять только заданную субполосу, многократно применяя SC-разложение и оставляя только верхнюю половину частот (разности) либо нижнюю (полусуммы);

■ использовать дискретное вэйвлетное преобразование для нахождения низкочастотной и высокочастотной компонент.

АА2	DA2	DAi
AD2	DD2
ADi		DDi

Рис. 2.З. Вариант применения SC в двумерном случае

Дискретное вэйвлетное преобразование

ДВП отличается от SC лишь тем, что в нем для вычисления низко- и вы­сокочастотной компоненты используется не два соседних элемента сигнала, а произвольное задаваемое число элементов D>2. Причем в отличие от дру­гих контекстных методов, в частности LPC, контекст элемента S[x] состоит из элементов по обе стороны от него: S[x+i] и S[x-i], i=l,2,3,...,D/2.

Основная же идея - та же, что в SC: сформировать два потока - с низки­ми Н[х] и высокими частотами Цх] - так, чтобы по половине значений Н[х] и половине значений Цх] можно было восстановить исходный поток S[x]. Оставляются либо четные Н[2-х] и нечетные Ц2х+1], ллбо наоборот.

При разжатии сначала по Н[2х] и L[2-x+l] восстанавливаем четные S[2-x],затем по S[2-x] и L[2x+1] находим нечетные S[2-x+l].

Если D=3, L[x]=S[xHS[x-l]+S[x+l])/2,

H[x]=S[x]+hi(x).

Функция hi(S[i]) должна быть выбрана так, чтобы она была выражаема через L[x+j],j=2k+l. Например, Ы,(х)=(Цх-1]+Цх+1])/2, hi₂(x)=(L[x-l]+L[x+l])/4, hi₃(x)= -<L[x-l]+L[x+l])/2, hi₄(x)= -(L[x-l]+L[x+l])/4, hij(x)=(L[x-3]+L[x-l]+L[x+l]+L[x+3])/4, и т. д.

Возьмем вторую функцию hi₂ (именно этот вариант используется в алго­ритме JPEG 2000) и посмотрим, каким образом Н выражается через S. H[x]=S[x]+(L[x-l]+L[x+l])/4 =

=S[x]+ ( S[x-1] - (S[x-2]+S[x])/2 + S[x+1] - (S[x]+S[x+2])/2 ) /4 -=S[x]+ (2-S[x-l] - S[x-2] - S[x] + 2-S[x+l] - S[x] - S[x+2]) /8 = =( -S[x-2] + 2S[x-l] + 6S[x] + 2-S[x+l] - S[x+2]) /8.

ДВП обычно задается в виде набора коэффициентов, в данном случае (-1/8,2/8,6/8,2/8,-1/8).

Упражнение. Каким будет набор коэффициентов, если используем hi₅(L[i])?

Итак, при таком построении вэйвлет-фильтров формируется два выход­ных потока:

L[2x+l]=S[2x+l]+lo(S[2x+j]), j - четные: j= ±2k; (2.11)

H[2-x]=S[2-x]+hi(L[2-x+i]), i - нечетные: i= ±(2m+l).

Если сжимаем с потерями, функция 1о может использовать любые S[x], а не только четные.

Обратное преобразование: сначала найдем все четные элементы: S[2x]=H[2x] - hi(L[2x+i]), i - нечетные; затем, на основании найденных четных, восстановим все нечетные элементы: S[2x+l]=L[2x+l]-lo(S[2x+j]),j-четные.

Если, наоборот, берем четные L и нечетные Н, это ничего по сути не ме­няет.

Заметим, что при сжатии с потерями существует и альтернативный путь. В прямом преобразовании сначала вычисляется

H[2-x+l]=C-S[2-x+l]+hi(S[2x+j]), j - четные: j= ±2k, 0<C<1; затем L[2-x]=S[2x]+lo(H[2-x+i]), i - нечетные: i= ±(2m+l). Сравните с (2.11). Например, если D=3, Н[х]=( S[x]+(S[x-l]+S[x+l])/2 ) /2.

И еще заметим, что для улучшения сжатия применимо все то, что написано выше для SC. Но, кроме того, здесь, как и в ЛПК, можно через каждые К эле­ментов выбирать фильтр, оптимальный для последних М обработанных эле­ментов (К, М - задаваемые параметры). Причем метод может даже не записы­вать номер выбранного фильтра в поток в явном виде, поскольку аналогичный анализ может выполняться на этапе обратного преобразования.

Характеристики методов семейства SC:

Степень сжатия: увеличивается обычно в 1.1-1.9 раза.

Типы данных: методы предназначены для сжатия количественных I данных.

Симметричность по скорости: в общем случае 1:1.

Характерные особенности: может быть целесообразно многократное ; применение.