МНОГОМАСШТАБНЫЕ ИНТЕГРАЛЬНЫЕ ТРАНСФОРМАЦИИ В СВЕТЕ ИХ ПРИМЕНЕИЯ К РЕШЕНИЮ НЕКОТОРЫХ ЗАДАЧ ГЕОФИЗИКИ Введение. За последние 20 лет в прикладной математике. - презентация

1 МНОГОМАСШТАБНЫЕ ИНТЕГРАЛЬНЫЕ ТРАНСФОРМАЦИИ В СВЕТЕ ИХ ПРИМЕНЕИЯ К РЕШЕНИЮ НЕКОТОРЫХ ЗАДАЧ ГЕОФИЗИКИ Введение. За последние 20 лет в прикладной математике был развит и оформился в самостоятельное направление раздел, получивший название «вейвлет- преобразование» (wavelet transform)[1]. Автор этого термина Жан Морле. Свой знаменитый вейвлет он придумал и применил при обработке данных сейсморазведки [Goupilland at all, 1985]. Начиная с девяностых годов прошлого века, на основе идей вейвлет- преобразования сигналов начал интенсивно развиваться математический аппарат для многомасштабного анализа многомерных данных[2]. В настоящее время преобразование данных этого класса играет фундаментальную роль в теории аппроксимации. [1] www-stat.stanford.edu/~wavelab, [1][2] [1]www-stat.stanford.edu/~wavelab[1][2] [1]www-stat.stanford.edu/~wavelab [2][2] [2]

2 Одномерные вейвлеты оперируют двумя основными параметрами: масштабом (scale) и масштабом (scale) и положением (location). положением (location). Двумерные вейвлеты, кроме того, имеют фиксированное количество направлений, по которым они имеют повышенную чувствительность в процессе анализа многомерных данных. Но в реальных сигналах могут присутствовать совершенно другие направления, которые нужно подчеркнуть посредством трансформации данных. В последнее десятилетие появилось большое число публикаций, посвященных классу трансформаций многомерных данных, которые включают дополнительный параметр – ориентацию линейных сегментов. Наряду с алгоритмами многомасштабного анализа сигналов, индуцированными вейвлетами, этот класс интегральных трансформаций пронизывают идеи, содержащиеся в преобразовании Радона, – математическом аппарате, лежащем в основе компьютерной томографии. В отличии от вейвлетов, трансформации, о которых здесь пойдет речь, в число основных параметров включают три элемента: масштаб (scale), масштаб (scale), положение (location), положение (location), ориентацию (orientation) линейных сегментов данных. ориентацию (orientation) линейных сегментов данных.

3 Список основных интегральных трансформаций данных на основе многомасштабного анализа Приведем перечень основных модификаций интегральных преобразований рассматриваемого класса: beamlet transform (бимлет-преобразование), beamlet transform (бимлет-преобразование), curvelet transform (курвлет-преобразование), curvelet transform (курвлет-преобразование), ridgelet transform (риджлет-преобразование). ridgelet transform (риджлет-преобразование). Эти и подобные им трансформация двумерных и многомерных данных обладают высокой чувствительностью и точностью при обнаружении и выделении объектов и их границ. Для краткости иногда будем называть их одним именем бимлет-преобразования. бимлет-преобразования Основные ссылки делаются на сайты в Интернете. Beam – луч, beamlet – маленький луч, лучик, штрих, отрезок

4 Фильтрация данных Алгоритмы фильтрации данных основаны на выборе порога во множестве коэффициентов интегральных преобразований, посредством которого часть коэффициентов заменяется нулями (процедура Thresholding). После этого выполняется реконструкция данных посредством соответствующего обратного преобразования. Выбор оптимального порога является достаточно сложной математической задачей. По этой теме имеется рад интересных публикаций. Она нашла удовлетворительное решение при сжатии данных и борьбы с шумом посредством вейвлет-анализа. Некоторую информацию по проблеме можно найти в книгах [Дьяконов, 2004; Смоленцев, 2005] и описании алгоритмов программ Wavelet Toolbox СКМ MATLAB.

5 Непрерывное одномерное вейвлет-преобразование Пусть фиксирована функция, имеющая нулевое интегральное среднее и достаточно быстро стремящаяся к нулю при. Назовем ее вейвлетом или всплеском. На основе вейвлета путем сдвигов и изменения масштаба построим функцию которой – параметр масштаба, – параметр сдвига в которой – параметр масштаба, – параметр сдвига. Прямое и обратное преобразование

6 Одномерное вейвлет-преобразование Сейсмологический сигнал

7 Одномерное дискретное вейвлет-преобразование Кратно-масштабный анализ сейсмологических данных Аппроксимации сигнала Детали различного уровня

8 Одномерное вейвлет-преобразование Иллюстрация кратно-разрешающего анализа (КРА) Вейвлет-коэффициенты Детали разного уровня

9 Одномерное вейвлет-пребразование Сверху вниз изображены: сейсмологическая трасса, детали и вейвлет-коэффициенты одного уровня, вейалет sym8(16 ).

10 Двумерная масштабирующая функция (вверху слева) Двумерные вейвлеты (вверху справа и внизу)

11 ПРЕОБРАЗОВАНИЕ РАДОНА Двумерное преобразование Радона функции двух переменных состоит в ее интегрировании вдоль прямых. Непрерывное преобразование Радона Прямое преобразование Радона есть отображение функций в функции, определяемое формулой Обратное преобразование Радона дает формула

12 Преобразование Радона тестовых сигналов Дискретное преобразование Непрерывное преобразование Тестовый сигнал

13 Фильтрация тестовых данных по Радону Матрица данных Данные + белый шумом N(0,1) Результат прямого преобразования данных с щумом

14 Результаты фильтрации данных по Радону Коэффициенты, выделенные по заданному порогу Т (слева), и реконструкция данных по этим коэффициентам (справа). Т=0.75 Т=0.50

15 RIDGELET TRANSFORM (Риджлет-преобразование) Риджлет-функции. Пусть функция является вейвлетом. Для любых, и определяется двумерный риджлет Графики риджлетов. Риджлет постоянен вдоль прямых.

16 Прямое непрерывное риджлет- преобразование Пусть дана интегрируемая функция двух переменных f(x,y). Ее риджлет-преобразование определяется посредством интеграла Обратное непрерывное риджлет- преобразование

17 Риджлет-анализ можно трактовать как вейвлет-анализ в области Радона. Tрансформация состоит в применении одномерного вейвлет-преобразования к строкам (или столбцам) массива Радон-коэффициентов, в направлении в которых параметр сдвига t изменяется, а угловая переменная является постоянной. Одна из возможных схем риджлет-преобразования

18 Данные. Синтетическая сейсмограмма Исходные данные. Синтетическая сейсмограмма Синтетическая сейсмограмма, Осложненная шумом. Отношение сигнал/шум равно 1/4 (SNR=1/4).

19 Сравнение исходных данных Иллюстрация соотношения полезного сигнала (график синего цвета) и того же сигнала с добавлением шума (график зеленого цвета) на примере одной сейсмотрассы, проходящей через центр сейсмограммы.

20 Фильтрация данных посредством преобразования Радона (слева) или двумерного вейвлет-преобразования (справа) Фильтрация данных по Радону. Фильтрация посредством WT2D.

21 Фильтрация данных посредством последовательного применения преобразования Радона и последующего одномерного вейвлет- преобразования: одномерного (слева) и двумерного (справа) WT1D-фильтрация после применения Радон-фильтраци. WT2D-фильтрация после применения Радон-фильтраци.

22 Фильтрация данных посредством применения риджлет- преобразования на основе вейвлет- преобразования: одномерного (слева) и двумерного (справа) Риджлет-фильтрация на основе WT1D в области Радон-коэффициентов Риджлет-фильтрация на основе WT2D в области Радон-коэффициентов

23 Данные. Фрагмент синтетической сейсмограммы Фрагмент сейсмограммы Сейсмограмма с шумом SNR=1/4

24 Фильтрация данных посредством применения риджлет- преобразования на основе одномерного вейвлет- преобразования: одномерного (слева) и двумерного (справа) Здесь использована часть сейсмограммы, не содержащая данных вблизи источника. Риджлет-фильтрация (RT+WT1D) Риджлет-фильтрация (RT+WT2D)

25 Данные. Фрагмент синтетической сейсмограммы Сейсмограмма с шумом SNR=1/8 Риджлет-фильтрация (RT+WT1D)

26 2. Практический пример Проиллюстрируем работу риджлет-преобразования на практических электроразведочных данных ВРЭ ЗАО «НПЦ ГЕОНЕФТЕГАЗ». Размер матрицы исходных данных 1024х64 (рис. 26). В процессе риджлет-преобразования использовалось одномерное быстрое вейвлет-преобразование с вейвлетом sym6, порог усечения коэффициентов Tw = Т, lev = 4. Матрица данных прямоугольная, поэтому при выполнении Радон-преобразования, которое в процессе работы оперирует квадратными матрицами, использовались перекрывающиеся квадратные окна 64х64. Их наложение составляло половину ширины окна. Результаты риджлет-фильтрации полевых данных, изображенных на рис. 26, приведены на рис. 27. Элементы, выделенные фильтрацией, весьма слабо видны на исходных данных.

27 2. Практический пример (продолжение) Исходные данные Результат риджлет- фильтрации

28 CURVELET TRANSFORM (Курвлет- преобразование) ( Curve – кривая; изгиб, сurvelet – маленький изгиб ). Курвлет-преобразование выполняет многомасштабный анализ сигнала и состоит из выполнения двух шагов: двумерное дискретное вейвлет-преобразование данных (WT 2D). двумерное дискретное вейвлет-преобразование данных (WT 2D). на каждом фиксированном масштабе, полученном в результате применения WT 2D, выполняется дискретное риджлет-преобразование. на каждом фиксированном масштабе, полученном в результате применения WT 2D, выполняется дискретное риджлет-преобразование. Схема этого преобразования изображена на следующем слайде.

29 Схема курвлет-преобразования

30 Фильтрация изображения посредством курвлет-преобразования Слева рисунок с шумом, справа – рисунок после курвлет-фильтрации. Особенно хорошо восстановлены края шляпы и другие границы. Однако вблизи граней можно увидеть осциллирующие структуры (артефакты), которых не было в исходном изображении

31 BEAMLET TRANSFORM (Бимлет-преобразование) Бимлет-преобразование реализует идею многомасштабного анализа данных (изображений), в которых линейные сегменты играют роль, аналогичную роли, которую играли точки в вейвлет-анализе. Бимлет-структура имеет 5 ключевых компонент. 1. Бимлет-словарь – диадно-организованная библиотека линейных сегментов в семействе позиций, ориентаций и масштабов, которые дают многомасштабную аппроксимацию набора всех линейных сегментов. 2. Бимлет-преобразование образа f(x;y) - набор всех интегралов по линиям изображения вдоль бимлетов из бимлет-словаря. 3. Бимлет-пирамида является коллекцией коэффициентов бимлет- преобразования, расположенных в структуре данных с иерархической многомасштабной природой. 4. Бимлет-граф имеет структуру графа, в которой вершины соответствуют угловым пикселям в основном изображении, а грани соответствуют бимлетам, объединенным в пары таких угловых пикселей. Путь через этот граф соответствует многоугольнику в оригинальном изображении. 5. Бимлет-алгоритмы извлекают данные из бимлет-пирамиды по пути, определенном структурой бимлет-графа, например, алгоритмы движения по сети или алгоритмы рекурсивного бинарного разделения. Используя первые четыре компонента бимлет-структуры, мы можем сформулировать базирующиеся на бимлетах алгоритмы, которые способны идентифицировать и извлекать бимлеты и цепи бимлетов со специальными свойствами

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

33 Дискретное бимлет-преобразование продолжение)

34 Схема бимлет-преобразования (слева) и результат его работы (справа) Дискретное бимлет-преобразование продолжение)

35 Бимлет-преобразование. Примеры. Пример 1. Картина Пикассо. Выделение границ фигур на разных масштабах путем выбора коэффициентов, превышающих некоторый порог

36 Бимлет-преобразование. Фильтрация данных. Пример 2. Картина Пикассо, осложненная шумом Пример 2. Реконструкция картины посредством бимлет-фильтрации бимлет-фильтрации

37 Бимлет-преобразование. Пример 3. Фильтрация данных посредством бимлетов на основе двоичного разделения области на части

38 Литература Averbuch, R. Coifman, D. Donoho, M. Israeli and J. Walden (2001). Fast Slant Stack: A notion of Radon Transform for data on a Cartesian grid which is Rapidly Computable, Algebraically Exact, Geometrically Faithful, and Invertible. Technical Report, Department of Statistics, Stanford University, Stanford, CA May. 4. E. J. Candès and D. L. Donoho, Curvelets, [Online] Available: stat.stanford.edu/~donoho/Reports/1999/curvelets.pdf, stat.stanford.edu/~donoho/Reports/1999/curvelets.pdfhttp://www- stat.stanford.edu/~donoho/Reports/1999/curvelets.pdf 5. E. Candès and D. Donoho. Ridgelets: the key to high-dimensional intermittency. Phil. Trans. R. Soc. Lond. A., 357: , S. Choi, D. Donoho, A. G. Flesia, X. Huo, O. Levi, D. Shi. About BeamLab – a Toolbox for New Multiscale Methodologies. Stanford University, Stanford, CA Georgia Institute of Technology, Atlanta, GA , Available: S. R. Deans. The Radon Transform and Some of Its Applications. New York: Wiley, D. L. Donoho. Orthonormal ridgelets and linear singularities, SIAM J. Math Anal., vol. 31, no. 5, pp. 1062–1099, D. Donoho and X. Huo (2001). Beamlets and Multiscale Image Processing. In Multiscale and Multiresolution Methods. Eds T.J. Barth, T. Chan, and R. Haimes, Springer Lecture Notes in Computational Science and Engineering, Vol. 20, pp

39 10. D. Donoho and X. Huo. Beamlet pyramids: A new form of multiresolution analysis, suited for extracting lines, curves, and objects from very noisy image data. In Proceedings of SPIE, volume 4119, July D. Donoho and O. Levi (2002). Fast X-Ray and Beamlet Transforms for Three- Dimensional Data. Technical Report, Department of Statistics, Stanford University, Stanford, CA March. In Modern Signal Processing, D. Rockmore and D. Healy, eds., Mathematical Sciences Research Institute Publications, Cambridge University Press. To appear. 12. D.L. Donoho Ridge Functions and Orthonormal Ridgelets. Available: D.L.Donoho and M.R. Duncan (2000). Digital Curvelet Transform: Strategy, Implementation, Experiments. Technical Report, Department of Statistics, Stanford University, Stanford, CA March D.L. Donoho and A. Flesia (2001). Digital Ridgelet Transform Based on True Ridge Functions. Technical Report, Department of Statistics, Stanford University, Stanford, CA To appear in Beyond Wavelets. J. Stoeckler and G.Welland (Eds). Academic Press, December. 14. D.L. Donoho and M. Duncan. Digital Curvelet Transform:Strategy, Implementation and Experiments. Department of Statistics.Stanford University. November, 1999 Available: D.L. Donoho and X. Huo. Beamlet Pyramids: A New Form of Multiresolution Analysis, suited for Extracting Lines, Curves, and Objects from Very Noisy Image Data. Available: D.L. Donoho and X. Huo. Beamlets and Multiscale Image Analysis. Available:

40 17. Falsie, H. Hel-Or, A. Averbuch, E. Candès, R. Coifman, D. Donoho, (2002). Digital Implementation of Ridgelet Packets. Technical Report, Department of Statistics, Stanford University, Stanford, CA To appear in Beyond Wavelets. J. Stoeckler and G. Welland (Eds). Academic Press, December. 18. Goupilland P., Grossman A., Morlet J. Cycle-octave and related transforms in seismic signal analysis // Geoexploration, , 23, J.-L. Starck, D.L. Donoho, and E.J. Candès. Very High Quality Image Restoration by Combining Wavelets and Curvelets. Available: stat.stanford.edu/ spie01_vhqr.pdf. stat.stanford.edu/ stat.stanford.edu/ 20. И.Добеши. Десять лекций по вейвлетам. М., Мир, В.П. Дьяконов. Вейвлеты. От теории к практике. СОЛОН-Пресс. М., 2004, 400 с. 22. Малла С. Вэйвлеты в обработке сигналов. М., Мир, 2005, 671 с. 23. Ф. Наттерер. Математические аспекты компьютерной томографии. М., Мир, 1990, 288 с. 24. Сейсмическая томография. Под ред. Г.Нолета. М., Мир,1990,416 с. 25. Смоленцев Н.К. Основы теории вейвлетов. Вейвлеты в МATLAB. ДМК. М., 2005, 304 с. 26. К.Чуи. Введение в вэйвлеты. М., Мир, 2001, 412 с. 27. М.Н.Юдин, Ю.А.Фарков, Д.М. Филатов. Введение в вейвлет-анализ. М., МГГА, 2000, 72 с.

41 28. Дудова К.А., Юдин М.Н. Бимлет-преобразование. Новая форма кратномасштабного анализа.//VI Международная конференция «Новые идеи в науках о земле». Материалы докладов, том IV. М., МГГРУ, Юдин М.Н., Юдин О.М.. Исследование возможности применения бимлет- преобразо-вания, SVD-разложения и преобразования Радона для анализа данных сейсморазведки. //VI конференция Международная «Новые идеи в науках о земле». Материалы докладов, том 2, М., МГГРУ, 2005, с Юдин М.Н., Калишенко Т. В., Юдин В.М. О применении вейвлет- преобразования и альтернирующего метода Шварца для решения некоторых задач геоэлектрики. «Новые идеи в науках о земле». Избранные доклады, М., МГГРУ, 2002, с

42 Совместное применение SVD-разложения и преобразования Радона для анализа данных Название SVD-разложение или сингулярное разложение произошло от английских слов Singular Value Decomposition. Сингулярному разложению более ста лет. Его независимо открыли Белтрами в 1873 г. и Жордан в 1874 г. для случая квадратных матриц. В 30-е годы XX в. Эккарт и Янг распространили это разложение на прямоугольные матрицы. Пусть А – произвольная тхп-матрица, причем m >= n. Тогда справедливо представление, где матрица U имеет размер mxn и удовлетворяет соотношению, матрица V квадратная порядка n и удовлетворяет соотношению, a, где. Столбцы матрицы U называются левыми сингулярными векторами (матрицы А). Столбцы матрицы V называются правыми сингулярными векторами. Величины сигма называются сингулярными числами. (При m < n нужно рассматривать SVD транспонированной матрицы А).

43 SVD-разложение На левом рисунке изображены исходные данные - матрица 129х65. Сигнал, равный 1, записан в строку 24 и диагональ матрицы. К сигналу добавлен шум в два раза превышающий величину сигнала. График сингулярных чисел Матрица данных с шумом

44 SVD-анализ данных, осложненных шумом Восстановление данных по первому сингулярному числу Восстановление данных по сингулярным числам 2-64

45 Радон-преобразование данных SVD-анализа Радон-фильтрация половины матрицы SVD данных, выделенных по первому сингулярному числу. Порог Т=0.9. Радон-фильтрация половины матрицы SVD данных, выделенных по сингулярным числам со 2 по 64. Порог Т=0.9.