Английское название метода - Subband Coding (SC). Дословный перевод - кодирование поддиапазонов.
Цель метода - сжатие потока R-битовых элементов в предположении, что значение каждого из них отличается от значений соседних элементов незначительно: Si я Sj.i.
Основная идея состоит в том, чтобы формировать два потока: для каждой пары S2i, S2i+i сохранять полусумму (S2J + S2i+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]:
А', = Ам-А, = (Xi+l+Yi+l-ai+l)/2 - (X^Yгад/2 , (2.9)
"издержки округления" о* равны единице, если сумма соответствующих Xk+Yk нечетна, а арифметика используется целочисленная; иначе ak=0.
А',=(Х!+,-Х; +Yi+I-Yi +a; -омУ2 = (X*,+Y', + a,~ai+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-ai+i=l, то A'j * A"j, А\=А"|+1.
Например, если Xj=0, Xi+i=Yi-Yi+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, hi2(x)=(L[x-l]+L[x+l])/4, hi3(x)= -<L[x-l]+L[x+l])/2, hi4(x)= -(L[x-l]+L[x+l])/4, hij(x)=(L[x-3]+L[x-l]+L[x+l]+L[x+3])/4, и т. д.
Возьмем вторую функцию hi2 (именно этот вариант используется в алгоритме 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).
Упражнение. Каким будет набор коэффициентов, если используем hi5(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.
Характерные особенности: может быть целесообразно многократное ; применение.