О всплесковых разложениях пространств сплайнов

Теория всплесков (вэйвлетов) появилась полтора десятилетия назад и интенсивно развивается. Ключевой работой в этой области принято считать книгу И. Добеши [1]. Большой вклад в развитие этой теории внесли учёные: И. Мейер, С. Малла, Г. Стренг, Ж. Баттле, П. Ж. Лемарье, Ч. Чуй, Р. Койф-ман, В. Свелденс, С. Б. Стечкин, В. А. Рвачев, И. Я. Новиков, В. Н. Малозёмов, А. П. Петухов, М. А. Скопина, Е. Е. Тыртышников, Ю. К. Демьянович, И. В. Оселедс, В. А. Жёлудев и др.

Вэйвлеты широко применяются при решении задач вычислительной математики и цифровой обработки сигналов. Как правило, в подобных задачах требуется найти коэффициенты разложения функции по некоторому базису с целью извлечения информации о функции, для последующей обработки или анализа. В теории вэйвлетов изучаются различные базисы, последовательности базисов, последовательности вложенных пространств, а также алгоритмы преобразования коэффициентов разложений функций по этим базисам. Вложенность пространств Vi С К'+ь позволяет ввести подпространства Wi С Vi+1 так, что Vi+1 может быть представлено в виде прямой (а иногда и ортогональной) суммы: 1 = Wi + Vi. Всплесковым (вэйвлет-ным) разложением пространства Vi+i называется разложение вида V{+i = Wi+. .'+Wi-S.-Vi-S. Обычно пространство Vi рассматривают как несущее основную информацию о функции, a Wi как несущее уточняющую информацию.

Классические подходы к построению вэйвлетного разложения связаны с использованием преобразования Фурье и кратно-масштабного анализа (см., например, [1]-[8]), а также теории сплайнов ([9]-[19]). Преобразование Фурье эффективно для равномерной сетки, однако при обработке сигналов с резко меняющимися характеристиками целесообразно использовать неравномерную сетку, приспосабливаемую к обрабатываемому потоку. Для неравномерной сетки вэйвлеты рассматривались в работах [20], [23]-[26], [30], [34]. Весьма важны случаи, когда исходные данные естественным образом связаны с некоторым многообразием (примерами могут служить цифровые потоки значений мощности излучения от поверхности тел различной формы: сферической, тороидальной и др.).

В данной работе для построения всплескового разложения используются аппроксимационные соотношения, что позволяет сразу оценить порядок аппроксимации. При этом координатные вэйвлеты имеют компактный носитель минимальной индексной длины при заданном порядке аппроксимации.

Приведём пример, связанный с обработкой информации от чёрно-белого изображения. Пусть упомянутое изображение имеет К = т х п пикселей, где т — количество строк, п — столбцов. Каждому пикселю приписывается определённая яркость, так что, занумеровав пиксели по строкам, получим числовую последовательность: со,., ск-1- Если К велико, то передача изображения по каналу связи может занять много времени. В связи с этим, возникает задача уменьшения количества передаваемых чисел. Пусть К = 2Lпредполагая что соседние числа близки, можно было бы передавать, например, только числа с нечётными номерами: с1, сз,., C2L-iВ таком случае, приёмное устройство расширяет полученый числовой поток дублированием принятых значений так, чтобы в результате на местах с чётным и со следующим нечётным номером находились одинаковые числа. В результате на экране воспроизводится изображение, полученное с помощью числового потока вида ci, ci, сз, сз, С5, сз, С7,., C2L—I1C2L-1- Тем самым «восстановление» исходного потока производится с погрешностью, причём информация теряется необратимым образом (т.е. без передачи дополнительной информации приёмное устройство, вообще говоря, не в состоянии восстановить исходный поток). Такой приём (английский эквивалент downsampling — сгущение) оправдан, если полученное изображение мало отличается от исходного.

Недостатки описанного подхода состоят в следующем: 1) он применим лишь к достаточно медленно меняющемуся потоку, 2) отсутствует учёт характеристик числового потока (в некоторых частях числовой поток может меняться очень медленно, и можно было бы выбрасывать много чисел подряд, а в других частях при быстром изменении потока любые выбрасывания чисел могут существенно испортить передаваемое изображение), 3) нет средств для уточнения передаваемого потока.

Идея вэйвлетного подхода иллюстрируется следующим образом. Из исходного числового потока формируется два числовых потока а. = з^зщ ^ (1).

6j = C2,72J+1, j = 0. L- 1. (2).

Нетрудно видеть, что c2j = Qj 4- bj, c2j+1 = ajbj, j = 0,., L — 1. (3).

Таким образом, если исходный поток заменить двумя потоками (1)-(2), то после их передачи можно восстановить исходный поток, используя формулы (3).

Общее количество чисел в потоках (1)-(2) и (3) совпадает, однако заметим, что если соседние числа в исходном потоке близки, то поток (2) состоит из чисел, близких к нулю, так что может оказаться, что этот поток вообще не нужен и его можно отбросить. Если некоторые фрагменты потока (1) не дают достаточной точности, то можно использовать соответствующие фрагменты (с теми же диапазонами индексов) потока (2), и произвести расчёты по формулам (3) — это приведёт к точному восстановлению исходного потока на соответствующих участках (подобная технология передачи используется, в частности, при передаче изображений в Интернете: сначала появляются основные контуры изображения, позволяющие оценить его содержание и прервать передачу, если в ней нет необходимости, и лишь затем происходит уточнение, и окончательное завершение передачи изображения). Поток чисел (1) называют основным, а поток (2) — вэйвлетным (всплесковым) потоком. Полученный основной поток можно рассматривать как сжатие исходного потока, а поток (2) как поправку к основному потоку, позволяющую восстановить исходный поток.

Если поток (1) ещё велик для передачи, то аналогичной процедурой его расщепляют на два потока: новый основной поток и соответствующий вэй-влетный поток. Возможно дальнейшее продолжение процесса расщепленияна к-м шаге получим расщепление исходного потока на к + 1 потоков: основной и к вэйвлетных потоков, последовательное добавление которых к основному потоку приводит к последовательному уточнению результата сжатия вплоть до полного восстановления исходного потока. Излагаемая методика похожа на разложение по формуле Тейлора, где производные заменены соответствующими разностями. Такой процесс расщепления иногда применяют и к упомянутым вэйвлетным потокамполучающийся результат называют вэйвлет-пакетом.

Цельдиссертационной работы состоит в том, чтобы.

1. построить пространства сплайнов лагранотева и эрмитова типов на неравномерной сетке и сплайнов на многообразии на основе аппрокси-мационных соотношений;

2. построить вэйвлетное разложение и получить формулы декомпозиции / реконструкции в упомянутых случаях;

3. установить оценки устойчивости и порядка аппроксимации;

4¦ представить результаты апробации теоретических результатов на модельных примерах.

Данная работа носит теоретический характер, однако полученные результаты могут быть применены для создания эффективных алгоритмов решения многих прикладных задач, связанных с обработкой больших потоков числовой информации, в частности, к обработке изображений, к задачам интерполяции и аппроксимации, к численному решению ряда задач математической физики.

Приведём краткий обзор содержания диссертации. Работа состоит из введения, четырёх глав, пяти рисунков, одной таблицы и списка литературы.

1. 1. Daubechies Ten Lectures on Wavelets. SIAM, Philadelphia, PA, 1992. (Пер. на русский: И. Добеши Десять лекций по вейвлетам. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2004. 464 с.).

2. С. К. Chui An Introduction to Wavelets. Academic Press, NY, 1992. (Пер. на русский: К. Чуй Введение в вэйвлеты. М.: Мир, 2001. 412 с.).

3. S. Mallat A wavelet tour of signal processing. Academic Press. 1999. (Пер. на русский: С. Малла Вэйвлеты в обработке сигналов. М.: Мир, 2005. 671 с.).

4. Новиков И. Я., Стечкин С. Б. Основы теории всплесков. // Успехи мате-матич. наук. 1998. Т. 53, № 6. С.53−128.

5. Новиков И. Я., Протасов В. Ю., Скопина М. А. Теория всплесков. М.: Физматлит, 2005. 612 с.

6. Skopina М. Multiresolution analysis of periodic functions./ / East Journal on Approximations. 1997. Vol.3, № 2. P.614−627.

7. Петухов А. П.

Введение

в теорию базисов всплесков. СПб., 1999. 132 с.

8. Малозёмов В. Н., Машарский С. М. Основы дискретного гармонического анализа. СПб.: НИИММ, 2003.

9. Завьялов Ю. С., Квасов Б. И., Мирошниченко В. Л. Методы сплайн-функций. М.: Наука, 1980.

10. Малозёмов В. Н., Певный А. Б. Полиномиальные сплайны. Л., 1986.120с.

11. Schumaker L. L. Spline Functions. Basic Theory. Waley Interscience, NY. 1981. 548 p.

12. Максименко И. E., СкопинаМ.А. Многомерные периодические всплески // Алгебра и анализ (2003), Т. 15. № 2. С.1−39.

13. Стечкин С. Б., Субботин Ю. Н. Сплайны в вычислительной математике. М., 1976. 248 с.

14. Малозёмов В. Н., Селянинова Н. А. Прямая лифтинговая схема. // Семинар «DHA & CAGD». Избранные доклады. 26 апреля 2005 г. http://www.dha.spb.ru/.

15. Морозов В. А. Теория сплайнов и задача устойчивого вычисления значений неограниченных операторов. // Ж. выч. матем. и матем. физики. 1971. Т. И т. С. 545−558.

16. ВагерБ.Г., Серков Н. К. Сплайны при решении прикладных задач метеорологии и гидрологии. JL: Гидрометеоиздат, 1987. 160 с.

17. ЖёлудевВ.А. О вэйвлетах на базе периодических сплайнов, j j Докл. РАН. 1994. Ш. С.9−13.

18. Жёлудев В. А., Певный А. Б. Биортогональные вейвлетные схемы, основанные на интерполяции дискретными сплайнами // Журн. выч. мат. и матем. физ. 2001. Т. 41. № 4. С. 537−548.

19. Певный А. Б. Дискретные сплайны и вейвлеты: Учебное пособие. Сыктывкар: Изд-во Сыктывкарского университета. 2004. 166 с.

20. J.M.Ford, I.V. Oseleds, Е. Е. Tyrtyshnikov. Matrix approximations and solvers using tensor products and non-standard wavelet transforms related to irregular grids. Rus. J. Numer. Anal, and Math. Modelling. Vol.19, No.2 (2004), 185−204.

21. Оселедс И. В. Применение разделённых разностей и В-сплайнов для построения быстрых дискретных преобразований вейвлетовского типана неравномерных сетках. // Ж. Математические заметки. 2005. Т. 77, вып.5. С.743−752.

22. Тыртышников Е. Е. Методы численного анализа. М., Изд. центр «Академия», 2007. 320 с.

23. Wim Sweldens The Lifting Scheme: A new philosophy in biorthogonal wavelet constructions // Wavelet applications in signal and image processing III. pp. 68−79. Proc. SPIE 2569. 1995.

24. Wim Sweldens, Peter Schroeder Building your own wavelets at home. In «Wavelets in Computer Graphics», ACM SIGGRAPH Course Notes, 1996.

25. Wim Sweldens The lifting scheme: A construction of second generation wavelets. // SIAM J. Math. Anal., 29(2):511 546, 1997.

26. Daubechies I., Guskov I., Sweldens W. Commutation for Irregular Subdivision. // Const. Approx., 17(4),(2001). P.479−514.

27. Демьянович Ю. К. Локальная аппроксимация на многообразии и минимальные сплайны СПб, 1994. 356 с.

28. Бурова И. Г., Демьянович Ю. К. Теория минимальных сплайнов. СПб, 2000. 316 с.

29. Демьянович Ю. К. Всплески и минимальные сплайны СПб, 2003. 200 с.

30. Демьянович Ю. К. Всплесковые разложения в пространствах сплайнов на неравномерной сетке. // Докл. РАН. 2002. Т. 382. № 3. С. 313−316.

31. Демьянович Ю. К. Локальный базис всплесков на неравномерной сетке. Зап. научн. семин. ПОМИ, 2006. Т. 334. С.84−110.

32. Демьянович Ю. К. Сплайн-вэйвлетные разложения на многообразии. Проблемы математического анализа. 2007. Т. 36. С. 15−22.

33. Демьянович Ю. К. Калибровочное соотношение для В-сплайнов на неравномерной сетке. // Математическое моделирование. 2001. Т. 13. № 9. С. 98−100.

34. Демьянович Ю. К. Гладкость пространств сплайнов и всплесковые разложения. // Доклады РАН. 2005. Т.401, Ж. С. 1−4.

35. Демьянович Ю. К., ЗиминА. В. Всплесковое (вэйвлетное) разложение пространств периодических В-сплайнов второй степени на неравномерной сетке. // Вестник СПбГУ, Серия 1. 2006. № 4. С.72−77.

36. Демьянович Ю. К., Зимин А. В. О всплесковом разложении сплайнов эрмитова типа, // Проблемы матем. анализа. 2007. Т. 35. С.33−45.

37. Зимин А. В. Вэйвлетная схема, основанная на аппроксимации кубическими В-сплайнами на неравномерной сетке сб. Методы вычислений. 2008. Т. 23. С.56−73.

38. Демьянович Ю. К., Зимин А. В. Вэйвлетные разложения на многообразии. Зап. научн. семин. ПОМИ, 2007, Т. 346. С.1−13.

39. Макаров А. А. Об одном алгебраическом тождестве в теории В<�р-сплайнов второго порядка. // Вестн. С.-Петерб. ун-та. Сер. 1. 2007. Вып. 1. С. 96−98.