Рис. 7.2.5.

ПрОХОА

«снизу вверх» в алгоритме

С НуЛЬ-АЄрЄВОМ

7. Технологии вейвлет-сжатия изображений

193

чг 7.2.1. Функиия-член mark__parents класса tzerotree из прилагаемой

к книге программы на языке С++

void tzerotree:: mark__parents (int row,int col,short symbol) { // Mark the parents of this position (row,col) as having a // significant child.

// The four "children" of position (i,j) in the subtree // are: <2i-l,2j-l), (2i-l,2j), <2i,2j-l) and <2i,2j). // Here, we need to move "backward", or up the tree, and // determine the parent of a given (row, col) position, int ichild = row,jchild = col; int iparent = ichild,jparent = jchild; while ((iparent > 1)&&(jparent > 1)) { if ((ichild/2)*2 == ichild) // even

iparent = ichild/2; else // odd

iparent = (ichild+1)/2; if <(jchild/2) *2 = jchild) // even

jparent = jchild/2; else // odd

jparent = (jchild+1)/2; set(iparent,jparent,symbol); ichild = iparent; jchild = jparent; } // end while return; >

В конце прохода снизу вверх для данного диапазона все значимые коэффициенты будут определены и закодированы символами POS или NEG и все изолированные нули будут определены и закодированы символами IZ. Все оставшиеся коэффициенты - это или корни нуль-дерева (ZR), или потомки корней нуль-дерева (ZT). Чем именно они являются, определяет проход сверху вниз. Начиная с верха поддиапазона, мы проверяем массив символов, чтобы узнать, какие коэффициенты были закодированы. Так как мы начинаем сверху, то любой коэффициент, который еще не закодирован, должен являться корнем нуль-дерева. Это справедливо для всех коэффициентов, за исключением коэффициентов самого нижнего блока. Коэффициенты в нижнем блоке не имеют потомков и поэтому по определению не могут быть корнями нуль-дерева. Не закодированным коэффициентам из этого блока сопоставляется символ IZ, а не ZR. Когда корень нуль-дерева найден, все его потомки в поддереве ниже его отмечаются символом ZT. В листинге 7.2.2 представлен код для функции-члена mark_chiidren класса tzerotree, которая работает здесь.

194

Фракталы и вейвлеты для сжатия изображений в действии