4.9. SPIHTАлгоритм SPIHT представляет собой метод сжатия изображений. На одном из его этапов применяется вейвлетное преобразование, поэтому он рассматривается в этой главе. Кроме того, основная структура данных этого алгоритма, пространственно ориентированное дерево, использует тот факт, что различные поддиапазоны отражают разные геометрические особенности образа (это обстоятельство было отмечено на стр. 220). Рис. 4.34. Вейвлет Добеши В § 4.2 было покачано, что преобразования Хаара можно применять к изображению несколько раз подряд. При этом образуются различные области (поддиапазоны), состоящие из средних и деталей данного образа. Преобразование Хаара является очень простым и наглядным, но для лучшего сжатия стоит использовать другие вейвлетные фильтры, которые лучше концентрируют энергию изображения. Представляется логичным, что различные вейвлетные фильтры будут давать разные коэффициенты сжатия для разных типов изображений. Однако исследователям пока не до конца ясно, как построить наилучший фильтр для каждого типа образов. Независимо от конкретно используемого фильтра, образ разлагается на поддиапазоны так, что нижние поддиапазоны соответствуют высоким частотам изображения, а верхние поддиапазоны отвечают низким частотам образа, в которых концентрируется основная часть энергии изображения (см. рис. 4.35). Поэтому можно ожидать, что коэффициенты деталей изображения уменьшаются при перемещении от высокого уровня к более низкому. Кроме того, имеется определенное пространственное подобие между поддиапазонами (рис. 4.7b). Части образа, такие как пики, занимают одну и ту же пространственную позицию во всех поддиапазонах. Эта особенность вейвлетного разложения используется методом SPIHT, который расшифровывается как «Set partitioning in hierarchical trees» (разложение множества по иерархическим деревьям) (см. [Said, Pearlman 96]). Рис. 4.35. Поддиапазоны и уровни вейвлетного разложения. Метод SPIHT был разработан для оптимальной прогрессирующей передачи изображений, а также для их сжатия. Самая важная особенностью этого алгоритма заключается в том, что на любом этапе декодирования качество отображаемой в этот момент картинки является наилучшим для введенного объема информации о данном образе. Другая отличительная черта алгоритма SPIHT состоит в использовании им вложенного кодирования. Это свойство можно определить следующим образом: если кодер, использующий вложенное кодирование, производит два файла, большой объема Следующий пример удачно иллюстрирует это определение. Предположим, что три пользователя ожидают некоторое отправленное им сжатое изображение. При этом им требуется различное качество этого изображения. Первому из них требуется качество, обеспечиваемое 10 KB образа, а второму и третьему пользователю необходимо качество, соответственно, в объеме 20 KB и 50 КВ. Большинству методов сжатия изображения с частичной потерей данных потребуется сжимать исходный образ три раза с разным качеством, для того, чтобы сгенерировать три различных файла, требуемых объемов. А метод SPIHT произведет для этих целей всего один файл, и пользователям будут посланы три начальных фрагмента этого файла, длины которых соответственно равны 10 KB, 20 KB и 50 КВ. Начнем с общего описания метода SPIHT. Обозначим пикселы исходного изображения Основная цель прогрессирующего метода состоит в скорейшей передаче самой важной части информации об изображении. Эта информация дает самое большое сокращение расхождения исходного и реконструированного образов. Для количественного измерения этого расхождения метод SPIHT использует среднеквадратическую ошибку MSE (mean squared error) (см. уравнение (3.2)),
где
Уравнение (4.15) показывает, что MSE уменьшается на Другой принцип основан на наблюдении, что наиболее значимые биты двоичных представлений целых чисел стремятся быть единицами, когда эти числа приближаются к максимальным значениям. (Например, в 16-битном компьютере число +5 имеет представление 0|000...0101, а большое число +65382 запишется в виде 0|111111101100110. Это наводит на мысль, что старшие биты содержат наиболее значимую часть информации, и их также следует посылать (или записывать в сжатый массив данных) в первую очередь. Прогрессирующий метод передачи SPIHT использует эти два принципа. Он сортирует (упорядочивает) коэффициенты и сначала посылает самые значимые биты этих коэффициентов. Для упрощения описания основ этого метода мы будем предполагать, что отсортированная информация непосредственно передается декодеру; в следующем параграфе обсуждается эффективный алгоритм для кодирования этой информации.
Табл. 4.36. Коэффициенты преобразования, отсортированные по модулю. Покажем теперь, как кодер метода SPIHT использует указанные принципы для прогрессирующей передачи (или записи в файл) вейвлетных коэффициентов, начиная с самой существенной информации. Предполагается, что вейвлетное преобразование уже применено к изображению (SPIHT является методом кодирования, и он может работать с любым вейвлетным преобразованием) и коэффициенты Упорядоченные данные, которые кодер должен передать, образуют последовательность
Кроме того, необходимо передать 16 знаков и 16 коэффициентов в порядке самых значимых битов. Прямая передача должна состоять из 16 чисел
что, конечно, слишком расточительно. Вместо этого кодер организует цикл, в котором на каждой итерации совершается шаг сортировки и шаг поправки. При первой итерации передается число На следующем проходе кодер должен выполнить шаг поправки, но он пропускается при первой итерации цикла. При второй итерации кодер выполняет оба шага. На шаге сортировки он передает число Полученная на данный момент информация дает возможность декодеру уточнить 16 приближенных коэффициентов, построенных на предыдущей итерации. Первые 6 из них становятся равными
а оставшиеся 10 коэффициентов не меняются, они по-прежнему равны 0. На шаге сортировки при третьей итерации кодер посылает Полученная информация позволит декодеру еще лучше уточнить 16 приближенных коэффициентов. Первые 9 из них равны теперь
а другие коэффициенты остаются нулевыми. Теперь легко понять основные шаги кодера SPIHT. Они приводятся ниже. Шаг 1: Для заданного сжимаемого изображения вычислить его вейвлетное преобразование, используя подходящие вейвлетные фильтры, разложить его на коэффициенты преобразования Шаг 2: Сортировка. Передать число Шаг 3: Поправка. Передать Шаг 4: Итерация. Уменьшить Обычно последняя итерация совершается при
|