4.1.1. Обобщение на двумерный случай

Одномерное вейвлетное преобразование Хаара легко переносится на двумерный случай. Это обобщение весьма важно, поскольку преобразование будет применяться к изображениям, которые имеют два измерения. Здесь снова производится вычисление средних и полуразностей. Существует много обобщений этого преобразования. Все они обсуждаются в [Salomon, 2000]. Здесь мы остановимся на двух подходах, которые называются стандартное разложение и пирамидальное разложение.

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

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

Рис. 4.3. Стандартное вейвлетное разложение.

В итоге в левом верхнем квадранте будут стоять средние четырех квадрантов исходного образа, а в остальных квадрантах будут находиться соответствующие полу разности. Шаги 3 и 4 оперируют со строками и столбцами, в результате чего средние величины будут сконцентрированы в левой верхней подматрице (одной шестнадцатой всей исходной таблицы). Эти пары шагов применяются к все более и более маленьким подматрицам, до тех пор пока в верхнем левом углу не будет стоять среднее всей исходной матрицы, а все остальные пикселы преобразуются в разности в соответствии с ходом алгоритма. Весь процесс показан на рис. 4.5.

Преобразования, описанные в § 3.5, являются ортогональными. Они преобразуют пикселы изображения во множество чисел, из которых некоторые числа будут большими, а остальные маленькими. Вейвлетные преобразования, подобные преобразованию Хаара, работают иначе, они являются под диапазонными. Они разбивают образ на подобласти, из которых одна область содержит большие числа (средние значения в случае преобразования Хаара), а другие области состоят из малых чисел (разностей в нашем случае). Однако эти области, называемые поддиапазонами, не просто являются семействами больших и малых чисел. Они отражают различные геометрические свойства трансформируемого образа. Чтобы пояснить эту особенность, изучим маленькое равномерное изображение, содержащее вертикальную и горизонтальную линию. На рис. 4.4а показан такой образ размера 8х8, в котором все пикселы равны 12 за исключением одной вертикальной строки с пикселами, равными 14, и одной горизонтальной строки, где пикселы равны 16.

Рис. 4.4. Образ 8х8 и его под диапазонное разложение.

На рис. 4.4b приведен результат применения одного шага преобразования Хаара ко всем строкам матрицы. Правая часть преобразованной матрицы (содержащая разности) в основном состоит из нулей. В этом отражается равномерность образа. Однако след от вертикальной линии вполне заметен (подчеркнутые числа обозначают отрицательные разности).

Рис. 4.5. Пирамидальное разложение образа.

На рис. 4.4с изображен результат применения того же преобразования к столбцам матрицы (b). Верхний правый поддиапазон содержит след от вертикальной линии, а в нижнем левом поддиапазоне отчетливо виден след от горизонтальной линии. Обозначим эти поддиапазоны HL и LH, соответственно (см. рис. 4.35, хотя имеется некоторое разночтение в использовании обозначений разными авторам). Нижний правый поддиапазон обозначим НН, на котором отражаются диагональные особенности образа (в нашем случае отсутствующие). Самым интересным остается верхний левый поддиапазон, целиком состоящий из средних величин (он обозначается LL). Этот квадрант, являющийся уменьшенной копией исходного образа с пониженным качеством, содержит следы от обеих линий.

Рис. 4.6 иллюстрирует влияние диагональных особенностей образа на поддиапазон НН. На рис. 4.6а показана матрица равномерного образа с диагональной полосой чуть выше главной диагонали матрицы. На рис. 4.6b,с даны результаты двух первых шагов пирамидального преобразования. Видно, что преобразованные коэффициенты левого нижнего поддиапазона (НН) отражают диагональные особенности исходного образа, лежащие именно выше главной диагонали матрицы. Ясно также, что верхний левый поддиапазон (LL) является копией исходного изображения, но с более низким разрешением.

Рис. 4.6. Под диапазонное разложение диагональной линии.

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

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

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

Цветные изображения. До этого момента предполагалось, что пикселы образа состоят из одиночных чисел (то есть, рассматривалось изображение из одной компоненты, представляющей различные оттенки одного цвета, обычно, серого). Любой метод сжатия таких изображений легко переносится на цветные образы, состоящие из трех компонентов. Для этого достаточно разделить образ на три подобраза и каждый независимо сжать. Если разрешается потеря информации, то имеет смысл сначала сделать преобразование исходного цветового пространства, которое обычно является пространством RGB, в пространство YIQ.

Рис. 4.7. Пример пирамидального разложения образа.

В новом цветовом представлении компонента Y - это светимость, а компоненты I и Q отвечают за цветность (см. [Salomon 99]). Преимущество этого представления состоит в том, что глаз человека имеет наибольшую чувствительность к изменениям светимости (Y), а наименьшую - к изменениям компоненты цветности Q. Поэтому метод с потерей данных должен отдельно сжимать компоненту Y почти без потерь, удалять часть информации из компоненты I, а из компоненты Q удалять еще больше данных. Тогда удастся добиться значительного сжатия изображения без заметных для глаза потерь качества и мелких деталей. В § 3.7.1 приведены более подробные сведения о цветовых пространствах и компонентах светимости и цветности.

Интересно отметить, что американский стандарт для передачи цветного телевизионного сигнала также учитывает преимущества представления YIQ. В общей полосе частот сигнала компонента Y занимает 4 MHz, на компоненту I приходится 1.5 MHz, а компоненте Q отведено всего 0.6 MHz.