|
^-,/2. Вт = Остальные уровни квантования {threshold levels'} находятся, как процессе кодирования могут формироваться четыре символа: 1) корень нулевого дерева {zerotree root}’, 2) изолированный ноль {isolatedzero}-, 3) положительно значимый {positive significant}’, 4) отрицательно значимый {negative significant}. Вероятности появления этих символов различны и существует некоторая избыточность, позволяющая эффективно использовать энтропийное кодирование. Алгоритм Саида-Пирлмана (SPIHT). А.Саид (A.Said) и У.Пирлман (W.Pearlman) улучшили алгоритм EZW. Их версия кодера называется «Установка подразделений в иерархических деревьях» {Set Partition In Hierarchical Trees SPIHT). Алгоритм SPIHT [135] является развитием EZW. Алгоритм через ПОД формирует вложенный битовый поток, используя вышеизложенные принципы прогрессивной побитовой передачи. Для изложения алгоритма вводятся следующие обозначения: множество координат детей для точки П,1), рассмотренной какG (к.1 ) 1) корень; 2) D(k,l ) _ множество координат всех потомков для точки ; 3) Нмножество координат корней; 4) L(k,l} = D(k.l) G(£,/) Термин «дети» здесь и далее обозначает четырех потомков на предыдущем уровне декомпозиции, то есть G(k,l) {m,2l),(2U1 + 1 >/2k +1,2/>/2k +1,21 + 1>}. Величина Hk d) состоит из потомков за исключением детей, то есть из «внуков», «правнуков» и так далее. Также следует заметить, что D(k.l) и L(k,i) не содержат корня ) . На начальном этапе формируется множество корней деревьев максимального размера Н. Их координаты находятся в НЧ субполосе самого старшего уровня декомпозиции. Далее формируются списковые субструктуры LIS, LIP, LSP. Эти структуры являются нововведением алгоритма 72 |
coder EZW) /194/. Данный кодер учитывает возможность значимости потомков незначимого узла. Перед кодированием выполняется квантование, для чего выбирается начальный порог (initial threshold) TQ: если wY(к,/) <27;, то wY(k,l)0. Остальные уровни квантования (threshold levels) находятся, как 7] = Г;_, / 2. В процессе кодирования могут формироваться четыре символа: 1) корень нулевого дерева (zerotree root); 2) изолированный ноль (isolatedzero); 3) положительно значимый {positive significant); 4) отрицательно значимый {negative significant). Вероятности появления этих символов различны и сущедтвует некоторая избыточность, позволяющая эффективно использовать энтропийное кодирование. Алгоритм Саида-Пирлмана (SPIHT). А.Саид (A.Said) и У.Пирлман (W.Pearlman) улучшили алгоритм EZW. Их версия кодера называется «Установка подразделений в иерархических деревьях» {Set Partition In Hierarchical Trees SPIHT). Алгоритм SPIHT /188/ является развитием EZW. Алгоритм через ПОД формирует вложенный битовый поток, используя вышеизложенные принципы прогрессивной побитовой передачи. Для изложения алгоритма вводятся следующие обозначения: 1) G{k,l) множество координат детей для точки (к,1), рассмотренной как корень; 2) D{k,l) множество координат всех потомков для точки {к,1); 3) Н множество координат корней; 4) L(k,l) =D{k,l)-G{k,l). далее уровне декомпозиции, то есть G{k,I) = {(2к,21), {2к,21+1), (2к +1,2/), (2к +1,2/ +1)}. Величина L(k,l) состоит из потомков за исключением детей, то есть из «внуков», «правнуков» и так далее. Также следует заметить, что D(k,l) и L(k,l) не содержат корня (к,1). На начальном этапе формируется множество корней деревьев максимального размера Н. Их координаты находятся в НЧ субполосе самого старшего уровня декомпозиции. Далее формируются списковые субструктуры LIS, LIP, LSP. Эти структуры являются нововведением алгоритма SPIHT, строятся над массивом вейвлеткоэффициентов и выстроенных из них деревьев и определяются следующим образом: 1) LIS список незначащих множеств (list of insignificant sets)', 2) LIP список незначащих точек (list of insignificantpixels)', 3) LSP список значащих точек (list ofsignificantpixels). Списки LIP и LSP содержат координаты (к,l) и описывают точки, находящиеся непосредственно по этим координатам. Список LIS также содержит координаты (к,1), но описывает множества, выстроенные из этих точек. Множества могут быть D(k,l) (тип А) и L(k,l) (тип В). Список LIS Ш инициализируется элементами Н, то есть всеми координатами (к,Г) НЧ субполосы старшего уровня декомпозиции. Пример формирования списка LIS приведен на рис. 1.3.6. в А А i\ ЮЪ* £ччЧ ft ’У-* з?ft -S4 ¥ * ^ I* «у.>5-v w •А* * Ч !■ % Ш Ia м V 1 i s ^ А -К Л J * * :*?П i; * з Л ^ аХ>. >wm^ Л^ Уч. ^ & 4Cw Рис. 1.3.6. Примеры элементов LIS. |