Структура деревьев, на которые распадается множество вейвлет-коэффициентов.

Верхний левый квадрант распадается на четверки коэффициентов. В каждой четверке три коэффициента (кроме закрашенного черным) имеют «потомков» – четверки коэффициентов на нижних уровнях; каждыйиз коэффициентов в этих четверках имеет своих отпрысков, и т.д. Узлу(i,j) соответствуют потомки с координатами(2i,2j), (2i,2j+1), (2i+1,2j), (2i+1,2j+1). В качестве изначального разбиения берется именно этот набор поддеревьев. Многие из них действительно состоят только из несущественных коэффициентов, так как малые значения на верхних уровнях почти всегда соответствуют малым значениям на нижних уровнях (если двигаться по направлению стрелок на рис. 5). Не углубляясь в дальнейшие подробности, отметим еще одну особенность этого красивого алгоритма: передается (запоминается) не таблица положений коэффициентов, а ключевые шаги процесса сортировки, что существенно компактнее (при декодировании этот процесс фактически воспроизводится в обратном порядке). Так как обычно многие поддеревья оказываются “нулевыми”, шагов сортировки будет не очень много.

Литература

1. I. Daubechies,Ten Lectures on Wavelets. SIAM, 1992.

2. И.Я.Новиков, С.Б.Стечкин, Основные конструкции всплесков, Фундаментальная и прикладная математика, т. 3, вып. 4, стр.999-1028, 1997.

3. S. G. Mallat, A Wavelet Tour of Signal Processing, 1998.

4. B.Jawerth, W.Sweldens, An overview of wavelet based multiresolution analyses, SIAM Review, v. 36, p. 377-412, 1994.

5. А. Said, W.Pearlman, A New Fast and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees, IEEE Trans. on Circuits and Systems for Video Technology, V.6, June 1996.

6. “Всплеск” (подборка популярных статей о теории и приложениях вейвлет-анализа), Компьютерра, №8 (236), 2 марта 1998, стр. 28-53 (http://www.computerra.ru/1998/8/).

7. http://www.mathsoft.com/ - электронная библиотека по теории и приложениям вейвлетов.

8. http://www.wavelet.org/ - электронный вейвлет-дайджест(Wavelet Digest), выходит с 1992 года.

9. http://playfair.stanford.edu/~wavelab –WAVELAB, бесплатная библиотека вейвлетных программ на языкеMatlab.

10. http://www.cs.dartmouth.edu/~gdavis – Программы (на Си) Джеффри Дэвиса (Geoffrey Davis) для экспериментов с вейвлетным сжатием изображений.

Л. Левкович-Маслюк, А. Переберин. Вейвлет-анализ и его приложения. 0