Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Вычисление средних и полуразностей

Мы начнем с одномерного массива данных, состоящего из N элементов. В принципе, этими элементами могут быть соседние пикселы изображения или последовательные звуковые фрагменты. Для простоты предположим, что число N равняется степени двойки. (Это будет предполагаться на протяжении всей главы, но в этом нет ограничения общности. Если длина N имеет другие делители, то можно просто удлинить массив, добавив в конце нули или повторив последний элемент нужное число раз. После декомпрессии, добавленные элементы просто удаляются.) Примером будет служить массив чисел (1,2,3,4,5,6, 7,8). Сначала вычислим четыре средние величины (1+2)/2 = 3/2, (3+4)/2 = 7/2, (5+6)/2 = 11/2 и (7+8)/2 = 15/2. Ясно, что знания этих четырех полусумм не достаточно для восстановления всего массива, поэтому мы еще вычислим четыре полуразности (1 - 2)/2 = -1/2, (3 - 4)/2 - -1/2 и (5 - 6)/2 = -1/2, которые будем называть коэффициентами деталей. Мы будем равноправно использовать термины «полуразность» и «деталь». Средние числа можно представлять себе крупномасштабным разрешением исходного образа, а детали необходимы для восстановления мелких подробностей или поправок. Если исходные данные коррелирова-ны, то крупномасштабное разрешение повторит исходный образ, а детали будут малыми.

Массив (3/2,7/2,11/2,15/2,-1/2,-1/2,-1/2,-1/2), состоящий из четырех полусумм и четырех полуразностей, можно использовать для восстановления исходного массива чисел. Новый массив также состоит из восьми чисел, но его последние четыре компоненты, полуразности, имеют тенденцию уменьшаться, что хорошо для сжатия. Воодушевленные этим обстоятельством, повторим нашу процедуру применительно к четырем первым (крупным) компонентам нашего нового массива. Они преобразуются в два средних и в две полуразности. Остальные четыре компонента оставим без изменений. Получим массив (10/4,26/4, -4/4, -4/4, -1/2, -1/2, -1/2, -1/2). Следующая и последняя итерация нашего процесса преобразует первые две компоненты этого массива в одно среднее (которое, на самом деле, равно среднему значению всех 8 элементов исходного массива) и одну полу разность. В итоге получим массив чисел (36/8,-16/8,-4/4,-4/4,-1/2,-1/2,-1/2,-1/2), который называется вейвлетным преобразованием Хаара исходного массива данных.

Из-за взятия полуразностей вейвлетное преобразование приводит к уменьшению значений исходных пикселов, поэтому их будет легче сжать с помощью квантования и кодирования длинами серий (RLE), методом Хаффмана, или, быть может, иным подходящим способом (см. [Salomon 2000]). Сжатие с потерей части информации достигается, как обычно, с помощью квантования или простого удаления наименьших полуразностей (заменой их на нули).

Перед тем как двигаться дальше, интересно (и полезно) оценить сложность этого преобразования, то есть, число арифметических операций как функцию размера данных. В нашем примере требуется 8 + 4 + 2 = 14 операций (сложений и вычитаний). Это число можно выразить как 14 = 2(8 — 1). В общем случае, пусть имеется N = 2П элементов массива. На первой итерации потребуется 2П операций, на второй - 2n_1 операций, и так далее до последней итерации, в которой будет 2n~(n_1) = 21 операции.

Таким образом, для совершения преобразования Хаара массива из N элементов потребуется совершить 2(7V — 1) арифметических операций, то есть, сложность преобразования имеет порядок O(N). Результат просто замечательный.

Удобно с каждой итерацией процесса связать величину, называемую ее разрешением, которая равна числу оставшихся средних в конце итерации. Разрешение после каждой из трех описанных выше итераций равно 4(= 22), 2(= 21) и 1(= 2°). В § 4.2.1 показано, что каждую компоненту вейвлетного преобразования следует нормализовать с помощью деления на квадратный корень из разрешения соответствующей итерации (это относится к ортонормированному преобразованию Хаара, которое также обсуждается в § 4.2.1). Итак, наш пример вейвлетного преобразования дает массив

/36/8 -16/8 -4/4 -4/4 -1/2 -1/2 -1/2 -1/2\

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

Две процедуры на рис. 4.1 иллюстрируют, как вычисляется нормализованное веивлетное преобразование массива из п компонентов (п равно степени 2). Обратное преобразование, которое восстанавливает исходный массив, показано в двух процедурах на рис. 4.2.

procedure NWTcalc(a:array of real, n:int); comment: n - размер массива (степень 2) a:=a/>/n comment: разделить весь массив j:=n;

while j>2 do NWTstep(a, j); j:=J/2; endwhile; end;

procedure NWTstep(a:array of real, j:int); for i=l to j/2 do

b[i]: = <a[2i-l]+a[2i])A/2; b[j/2+i] : = (а[21-1]-а[21])/л/2; endfor;

a:=b; comment: переместить весь массив end;

Рис. 4.1. Вычисление нормализованного вейвлетного преобразования (псевдокод).

procedure NWTreconst(a:array of real, n:int); j:=2;

while j<n do NWTRstep(a, j); j:=2j; endwhile a:=a>/n; comment: умножение всего массива end;

procedure NWTRstep(a:array of real, j:int); for i=l to j/2 do

b[2i-l]:-(a[i]+a[j/2+i])A/2; b[2i]: = (a[i]-a[j/2+i])/>/2; endfor;

a:=b; comment: переместить весь массив end;

Рис. 4.2. Обратное нормализованного вейвлетного преобразования (псевдокод).

Эти процедуры, на первый взгляд, отличаются от взятия средних и полуразностей, которые обсуждались выше, поскольку происходит деление на \/2, а не на 2. Первая процедура начинается делением всего массива на у/п, а вторая делает обратное. Окончательный результат, тем не менее, совпадает с массивом, указанным выше. Начиная с массива (1,2,3,4,5,6,7,8), получаем после трех итераций процедуры NWTcalc необходиміе массивы