ПОД, построенное из точки первого уровня декомпозиции, имеет только корень и не имеет потомков. Алгоритм А.Льюиса и Г.Ноулеса («квантование нулевым деревом») основан на наблюдении, что если коэффициент мал, то его потомки в ПОД вероятно тоже малы. Это объясняется тем, что значимые коэффициенты возникают вблизи контуров и текстур, которые локальны. А.Льюис и Г.Ноулес использовали следующий алгоритм квантования вейвлет-коэффициентов. Вначале каждый корневой узел квантуется квантователем, оптимальным для плотности распределения Лапласа. Если значение узла меньше некоторого порога, его потомки игнорируются. Эти потомки будут восстановлены декодером как нули. Иначе осуществляется переход к четырем потомкам узла, и процедура повторяется. Если узел не имеет потомков, начинает обрабатываться следующий корневой узел и т.д. Характеристики алгоритма Льюиса и Ноулеса незначительно превосходят алгоритм сжатия JPEG, хотя визуальное качество изображений лучше. Недостатком алгоритма является способ порождения и распознавания нулевых деревьев. Как было отмечено, если коэффициент мал, то, скорее всего, его потомки будут малы, но может быть, и нет. В случае, если это не так, обнуляются значимые коэффициенты, и алгоритм Льюиса и Ноулеса ведет к большим искажениям. Преимуществом данного алгоритма является его относительная простота. Нулевые деревья порождаются путем простого сравнения амплитуд коэффициентов, не требуется дополнительной информации оо ихи местоположении. Однако эта простота приводит к невысокой эффективности. Детальный анализ этого явления привел к появлению следующего поколения кодеров с применением нулевых деревьев. Алгоритм Шапиро (EZW). Шапиро (Shapiro) разработал метод, названный алгоритмом вложенного нулевого дерева {Embedded Zerotree Wavelet coder EZW) [141]. Данный кодер учитывает возможность значимости потомков незначимого узла. Перед кодированием выполняется квантование, для чего выбирается начальный порог {initial threshold) то : если w, (G/) < 2 7"0, то »’,(£,/) = () 71 |
D(k, /) = (к,I) + D(2k,2l) + D(2k,2l +1) + D(2k + 1,2/) + D{2k + 1,2/ +1). ПОД, построенное из точки первого уровня декомпозиции, имеет только корень и не имеет потомков. Алгоритм А.Льюиса и Г.Ноулеса («квантование нулевым деревом») основан на наблюдении, что если коэффициент мал, то его потомки в ПОД вероятно тоже малы. Это объясняется тем, что значимые коэффициенты возникают вблизи контуров и текстур, которые локальны. АЛьюис и Г.Ноулес использовали следующий алгоритм квантования вейвлет-коэффициентов. Вначале каждый корневой узел квантуется квантователем, оптимальным для плотности распределения Лапласа. Если значение узла меньше некоторого порога, его потомки игнорируются. Эти потомки будут восстановлены декодером как нули. Иначе осуществляется переход к четырем потомкам узла, и процедура повторяется. Если узел не имеет потомков, начинает обрабатываться следующий корневой узел и т.д. Характеристики алгоритма Льюиса и Ноулеса незначительно превосходят алгоритм сжатия ЛЛЮ, хотя визуальное качество изображений лучше. Недостатком алгоритма является способ порождения и распознавания нулевых деревьев. Как было отмечено, если коэффициент мал, то, скорее всего, егоI потомки будут малы, но может быть, и нет. В случае, если это не так, обнуляются значимые коэффициенты, и алгоритм Льюиса и Ноулеса ведет к большим искажениям. Преимуществом данного алгоритма является его относительная простота. Нулевые деревья порождаются путем простого сравнения амплитуд коэффициентов, и не требуется дополнительной информации об их местоположении. Однако эта простота приводит к невысокой эффективности. Детальный анализ этого явления привел к появлению следующего поколения кодеров с применением нулевых деревьев. Алгоритм Шапиро (EZW). Шапиро (Shapiro) разработал метод, названный алгоритмом вложенного нулевого дерева (Embedded Zerotree Wavelet 84 |