Решение обратной проблемы N-мерных аффинных самоподобных функций методом голосования для всплеск-максимумов тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Елистратов, Николай Александрович

• Елистратов, Николай Александрович
• кандидат физико-математических наук
• 2011

Оглавление диссертации кандидат физико-математических наук Елистратов, Николай Александрович

Введение

1 Аффинные самоподобные фракталы

1.1 Аффинные самоподобные множества

1.2 Аффинные самоподобные функции

1.2.1 Носитель с пустой внутренностью.

1.2.2 Носитель с непустой внутренностью.

2 Непрерывное всплеск-преобразование

2.1 НВП с вращениями

2.1.1 Основные определения.

2.1.2 Самоподобие всплеск-максимумов.

2.2 Обобщение НВП с вращениями.

2.2.1 Аффинное самоподобие всплеск-максимумов.

2.2.2 Всплеск-максимумы аффинных самоподобных функций.

3 Восстановление параметров аффинного самоподобия

3.1 Вычислительные алгоритмы

3.1.1 Всплеск-преобразование.

3.1.2 Линии всплеск-максимумов.

3.1.3 Алгоритм голосования.

3.2 Результаты экспериментов

3.2.1 Примеры вычислений.

3.2.2 Восстановление из зашумленных данных.

Введение диссертации (часть автореферата) на тему «Решение обратной проблемы N-мерных аффинных самоподобных функций методом голосования для всплеск-максимумов»

В настоящее время значительный интерес для таких областей как компьютерная графика, распознавание образов, обработка и сжатие изображений, теория динамических систем, геофизика, всплеск-анализ, психология и многих других представляет изучение фрактальных объектов.

Термин "фрактал" (лат. fractus — дробленый, разломанный, разбитый) впервые введен Мандельбротом [43, 66] в 1975 г. для обозначения таких объектов, для которых характерно самоподобие в достаточно широком смысле. Такие объекты являются в точности самоподобными, то есть составлены из уменьшенных преобразованных "копий" самих себя, или же представляют собой некоторое приближение к таким точным самоподобным объектам. Так, термин "фрактальное множество" имеет строгое математическое определение, а словосочетание "природный фрактал" может применяться к достаточно широкому классу естественных структур, которые так или иначе могут быть описаны с помощью фрактальных множеств.

На настоящий момент имеется большое количество литературы и научных работ, посвященных самоподобным фракталам. Понятие самоподобного множества было введено Хатчинсоном (Hutchinson) в работе [29]. Дальнейшим развитием теории занимались Барнсли (Barnsley) [18, 17], Фальконер

1)Слово "самоподобие" здесь понимается в широком сысле, то есть для произвольных отображений Т\, , TN самоподобное множество есть объединение образов этих отображений на самом множестве.

Falconer) [26, 27, 25], Бандт (Bandt) [12, 13, 14, 15, 16] и другие. Важной характеристикой при изучении самоподобных множеств является размерность Хаусдорфа. Особенностью самоподобных множеств является, то, что размерность Хаусдорфа может отличаться от топологической (в частности, может быть дробной).

Модели самоподобных детерминированных и случайных фракталов успешно применяются при описании изображений природных объектов [43, 66, 18]. Изучение моделей хаотической динамики, таких как DLA (diffusion limited aggregation), модели роста, ограниченного диффузией) и странных аттракторов, показывает, что они также обладают свойствами самоподобия [33, 6, 64]. В теории всплесков самоподобные фракталы применяются для, построения кратномасштабных анализов (КМА) [19, 68].

В настоящей работе проведено исследование класса многомерных самопоV добных фракталов — аффинных самоподобных функций, описываемых функциональными уравнениями с уточняющим оператором. Уточняющий оператор представляет собой сумму аффинных функциональных операторов. В частности, масштабирующие функции КМА являются примерами аффинных самоподобных функций [68]. Аттракторы-IFS (Iterated Function Systems, системы итерируемых функций) [18, 64] можно описать с помощью их характеристических функций, которые также являются аффинными-самоподобными.

Важным свойством самоподобных фракталов является то, что довольно сложные структуры, имеющие фрактальную природу, можно описать с помощью небольшого набора параметров. Генерирование самоподобных фракталов является довольно простой задачей, нашедшей применение при получении изображений природных ландшафтов и текстур в компьютерной графике. В то время как численный анализ свойств самоподобия сигналов является более сложной обратной задачей. Зная параметры самоподобия, можно эффективно кодировать видео и изображения [17, 32]. Не менее важным является получение фрактальных характеристик при изучении физических явлений, например, таких как землетрясения [39]. В одномерном случае известно решение обратной задачи методом моментов [28], а также при помощи всплесков [8, 31]. Для решения такой задачи в двумерном случае применяют геометрические методы [24], метод моментов и всплеск-анализ [47]. Решение двумерной задачи получено для довольно узкого класса фракталов, поэтому значительный интерес представляет данная задача в многомерном случае для аффинных самоподобных функций. Таким образом, разработка новых методов получения фрактальных характеристик многомерных аффинных самоподобных функций является актуальной научной проблемой диссертационного исследования.

При изучении самоподобных фракталов мощные средства предоставляет непрерывный всплеск-анализ. Теория всплесков возникла сравнительно недавно'. Само название всплеск (или вейвлет (wavelet)) возникло менее 30 лет назад в работах Морле (Morlet), Аренса (Arens), Форже (Fourgeau) и Жи-ара (Giard) [45], Морле [44], Гроссмана (Grossman) и Морле [34]. Исследованием приложений всплесков к анализу сигналов (таких как звук и изображения) занимались Кроланд-Мартин (Kroland-Martinet), Морле, Гроссман [36], Малла (Mallat) [40, 41, 42], Добеши (Daubechies) [22]. Международный стандарт сжатия изображений JPEG2000 основан на разложении изображений по базису всплесков [49]. Анализу фракталов при помощи непрерывного всплеск-преобразования посвящены работы Арнеодо (Arneodo) и др. [5, 6, 9, 8]. Результатом является разработанный метод WTMM (wavelet transform modulus maxima, метод максимумов модуля всплеск-преобразования) для вычисления спектра особенностей мультифрактальных сигналов, имеющий важные применения в ряде проблем, таких как развитая турбулентность (fully developed turbulence), метеорология, физиология, анализ ДНК [7] и геофизика [39]. Для анализа многомерных сигналов метод WTMM использует векторное всплеск-преобразование, представляющее собой градиент сглаженного сигнала. Другой подход к анализу многомерных сигналов, основанный на направленных всплесках (directional wavelets) разработан Муренци (Murenzi), Антуаном (Antoine) и Вандергейнстом (Vandergheynst) [1, 2, 3], использует непрерывное всплеск-преобразование, ассоциированное с группой подобий евклидова пространства (НВП с вращениями) [46]. Этот подход успешно применяется для распознавания образов (изображений, контуров, рукописных текстов, симметрий), имеет ряд приложений в астрономии, геофизике, гидродинамике и др. [4]. В настоящей работе для анализа многомерных фракталов используется НВП с вращениями и вводится его обобщение.

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

Достижение поставленной цели потребовало решения следующих задач:

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

2. Обобщение одномерного подхода Хвонга (Hwang) и Малла [31]. для восстановления параметров самоподобных функций на случай многомерных аффинных самоподобных функций. Был разработан алгоритм численного восстановления указанных параметров. Данный алгоритм при1 7 надлежит к классу алгоритмов с голосованием, таких как алгоритм Хафа (Hough) [10].

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

4. Численная реализации НВП. Был разработан алгоритм вычисления НВП с применением быстрого преобразования Фурье.

5. Разработка комплекса программ с использованием современного математического программного обеспечения.

6. Тестирование разработанных алгоритмов, методов и комплекса программ на модельных примерах аффинных самоподобных функций.

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

Объектами исследования являются многомерные аффинные самоподобные функции и их непрерывное всплеск-преобразование.

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

Основные научные результаты работы, имеющие новизну:

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

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

3. Разработан алгоритм вычисления обобщенного непрерывного всплеск-преобразования, вычислительная сложность которого ниже по сравнению с прямым методом за счет использования быстрого преобразования Фурье.

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

К практически значимым результатам относятся разработанные методы, вычислительные алгоритмы и комплексы программ, которые могут быть использованы при решении следующих задач:

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

2. Распознавание образов объектов, обладающих свойствами аффинного самоподобия.

3. Анализ объектов, описываемых моделями хаотической динамики в молекулярной физике, геофизике и метеорологии.

Также отметим, что установленное свойство обобщенного непрерывного всплеск-преобразования о распространении его всплеск-максимумов до самых малых масштабов является важной характеристикой, позволяющей разрабатывать новые методы анализа многомерных сигналов, такие как локализация особенностей и оценка спектра [42, 9],[65, глава 6].

В работе применяются методы функционального анализа [63], методы теории интегральных и дискретных преобразований, таких как преобразование Фурье [73, 59] и всплеск-преобразование [65, 60, 53, 72], методы теории самоподобных фракталов [29, 64, 27, 26], теории всплесков [68, 74], теории матриц [58, 57, 52, 69, 61], методы теории компьютерного зрения [10, 11, 48]. Разработка программного обеспечения проводилась в среде МАТЬАВ [50].

Диссертационная работа состоит из введения, трех глав, заключения, списка использованной литературы из 75 наименований. Общий объем диссертации— 120 страниц, включая 16 рисунков, 1 таблицу и 1 приложение.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Елистратов, Николай Александрович

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

Заключение

В диссертационной работе получены следующие результаты:

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

2. На основе выявленных свойств самоподобия непрерывного всплеск-преобразования (НВП) с вращениями для самоподобных функций было получено обобщенное НВП, которое обладает такими же свойствами самоподобия в отношении аффинных самоподобных функций.

3. Разработан алгоритм численного восстановления параметров аффинного самоподобия, причем восстановление происходит посредством голосования для всплеск-максимумов обобщенного НВП в пространстве параметров аффинных операторов.

4. Получено обоснование того, что точки всплеск-максимумов обобщенного НВП для всплесков Гаусса принадлежат кривым, распространяющимся до самых малых масштабов, что позволяет повысить устойчивость алгоритма к численным погрешностям в тех областях, где НВП близко к нулю.

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

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

7. Проведен численный анализ эффективности разработанного алгоритма в случае, когда входной сигнал содержит шумы.

Список литературы диссертационного исследования кандидат физико-математических наук Елистратов, Николай Александрович, 2011 год

1. Antoine J.-P. and Murenzi R. Two-dimensional directional wavelets and the scale-angle representation. Signal Process., 1996, 52, pp. 259—281.

2. Antoine J.-P., Murenzi R., and Vandergheynst P. Two-dimensional directional wavelets in image processing. International Journal of Imaging Systems and Technology, 1996, 7(3), pp. 152-165.

3. Antoine J.-P., Murenzi R., and Vandergheynst P. Directional wavelets revisited: Cauchy wavelets and symmetry detection in patterns. Appl. Comput. Harmon. Anal., 1999, 6, pp. 314-345.

4. Antoine J.-P., Murenzi R., Vandergheynst P., Ali S.T. Two-Dimensional Wavelets and their Relatives. Cambridge University Press, 2004.

5. Argoul F., Arneodo A., Elezgaray J., Greasseau G. and Murenzi R. Wavelet transform of fractal aggregates. Phys. Lett. A, 1989, 135(6-7), pp. 327-336.

6. Arneodo A., Argoul F., Bacry E., Muzy J.F., and Tabard M. Golden Mean Arithmetic in the Fractal Branching of Diffusion-Limited Aggreagtes. Phys. Rev. Lett., 1992, 68(23), pp. 3456-3459.

7. Arneodo A., Audit В., Kestener P., Roux S. Wavelet-based multifractal analysis. Scholarpedia, 2008, 3(3), 4103. http://www.scholarpedia.org/article/

8. Wavelet-basedmultifractalanalysis

9. Arneodo A., Bacry E., Muzy J.F. Solving the inverse fractal problem from wavelet analysis. Europhys. Lett., 1994, 25(7), pp. 479-484.

10. Bacry E., Muzy J.F., Arneodo A. Singularity spectrum of fractal signals from wavelet analysis: exact results. Journ. of Statistical Physics, 1993, 70(3-4), pp. 635-674.

11. Ballard D. Generalizing the Hough transform to derect arbitrary shapes. Pattern Recognition 13(2), 1981, pp. 111-122.

12. Ballard D.H., Brown C.M. Computer vision. Prentice-Hall, 1982.

13. Bandt C. Self-Similar Sets 1. Topological Markov chains and mixed self-similar sets. Math. Nachr., 1989, 142(1) pp. 107-123.

14. Bandt C., Keller K. Self-Similar Sets 2. A Simple Approach to the Topological Structure of Fractals. Math. Nachr., 1991, 154(1), pp. 27-39.

15. Bandt C. Self-similar sets 3. Constructions with sofic systems. Monatsh. Math., 1989, 108(2-3), pp. 89-102.

16. Bandt C. Self-similar sets 5. Integer matrices and fractal tilings of Mn. Proceedings of the AMS, 1991, 112(2), pp. 549-562.

17. Bandt C., Graph S. Self-similar sets 7. A characterization of self-similar fractals with positive Hausdorff measure. Proceedings of the AMS, 1992, 114(4), pp. 995-1001.

18. Barnsley М. and Sloan A. A better way to compress images. Byte Magazine, January 1988, pp. 215-223.

19. Barnsley M.F. Fractals Everywhere. Academic Press, 1988

20. Cabrelli, C.A., Heil C., Molter U.M. Self-Similarity and Multiwavelets in Higher Dimensions. Memoirs of the AMS, 2004, 170(807), 82p.

21. Cabrelli C.A., Motler U.M. Generalized self-similarity. J. of Math. Anal and Appl., 1999, 230, pp. 251-260.

22. Chu E., George A. Inside the FFT Black Box: Serial and Parallel Fast Fourier Transform Algorithms. CRC Press, 2000.

23. Daubechies I. The wavelet transform, time-frequency localization and signal analysis. IEEE Trans. Inform. Theory, 1990, 36(5), pp. 961-1005.

24. Daubechies I., Lagarias J. Two-scale difference equations I. Existence and global regularity of solutions. SIAM J. Math. Anal, 1991, 22(5), pp. 13881410

25. Deliu A., Geronimo J. and Shonkwiler R. On the inverse fractal problem for two-dimensional attractors. Phil. Trans. R. Soc. bond., 1997, 355(1726), pp. 1017-1062.

26. Falconer K. Sub-Self-Similar Sets. Transactions of the AMS, 1995, 347(8), pp. 3121-3129.

27. Falconer K. Fractal Geometry: Mathematical Foundations and Applications. 2nd Edition, John Wiley & Sons Ltd, 2003.

28. Falconer K. Techniques in Fractal Geometry. John Wiley & Sons Ltd, 1997.

29. Handy C.R., Mantica G. Inverse problems in fractal construction: Moment method solution. Phys. D, 1990, 43(1), pp. 17-36.

30. Hutchinson J.E. Fractals and Self Similarity. Indiana Univ. Math. J., 1981, 30(5), pp. 713-747.

31. Hummel В., Moniot R. Reconstruction from zero-crossings in scale-space. IEEE Trans. Acoust., Speech, and Signal Proc., December 1989, 37(12), pp. 2111-2130.

32. Hwang W.L. and Mallat. S. Characterization of self-similar multifractals with wavelet maxima. J. of Appl. and Comput. Harmonic Analysis, 1994, 1, pp. 316-328.

33. Gharavi-Alkhanasri M., Huang T.S. Fractal-Based Image and Video Coding, in Video Coding: The Second Generation Approach. Torres L., Kunt M., Springer; 1st ed., 1996, pp. 265-304.

34. Goold N.R., Somfai E. and Ball R.C. Anisotropic diffusion limited aggregation in three dimensions: Universality and nonuniversality. Phys. Rev. E, 2005, 72(3), 031403, 10p.

35. Grossmann A., Morlet J. Decomposition of Hardy Functions into Square Integrable Wavelets of Constant Shape. SIAM J. Math. Anal., 1984, 15(4), pp. 723-736.

36. Káenmáki A., Vilppolainen M. Dimension and Measure on Sub-Self-Affine Sets. Montash. Math., 2010, 161(3), pp. 271-293.

37. Kroland-Martinet R., Morlet J., Grossman A. Analysis of sound patterns through wavelet transforms. Internat. J. Pattern Recognition and Artificial Intelligence, 1987, 1, pp. 273-301.

38. Lau К., Xu Y. On the boundary of attractors with non-void interior. Proc. Amer. Math. Soc., 2000, 128, pp. 1761-1768.

39. Lee J.S. Digital Image Enhancement and Noise Filtering by Use of Local Statistics. IEEE Trans. Patt. Anal. Machine Intell., 1980, 2(2), pp. 165-168.

40. Lyubushin A.A. Synchronization Trends and Rhythms of Multifractal Parameters of the Field of Low-Frequency Microseisms. Izvestiya, Physics of the Solid Earth, 2009, 45(5), pp. 381-394.

41. Mallat S. A Theory for Multiresolution Signal Decomposition: The Wavelet Representation. IEEE Trans. Patt. Anal, and Mach. Intell, 1989, 11(7), pp. 674-693.

42. Mallat S. Multifrequency Channel Decomposition of Images and Wavelet Models. IEEE Trans. Acoust. Speech Signal Process., 1989, 37(12), pp. 20912110.

43. Mallat S. and Hwang W.L. Singularity Detection and Processing with Wavelets. IEEE Trans. Info. Theory, 1992, 38(2), pp. 617-643.

44. Mandelbrot B.B. The Fractal Geometry of Nature, W. H. Freeman and Company, New York, 1982

45. Morlet J. Sampling theory and wave propagatioin. NATO ASI Series, 1, Issues in Acoustic signal/Image processing and recognition, C.H. Chen, ed., SpringerVerlag, Berlin, pp. 233-261.

46. Morlet J., Arens G., Forgeau I., Giard D. Wave Propagation and Sampling Theory. Geophysics 1982, 47(2), pp. 203-236.

47. Murenzi R. Wavelet transforms associated to the n-dimensional Euclidean group with dilations: signals in more than one dimension, in Wavelets, J.M. Combes, A.Grossman, and Ph.Tchamitchian, eds., Springer-Verlag, Berlin, 1989, pp. 239-246.

48. Rinaldo R., and Zakhor A. Inverse and Approximation Problem for Two-Dimensional Fractal Sets. IEEE Trans. Image Proc., 1994, 3(6), pp. 802-820.

49. Ritter G.X., Wilson J.N. Handbook of computer vision algorithms in image algebra. 2nd. ed., 2001, CRC Press LLC.

50. Taubman D.S., Marcellin M.W. JPEG2000: image compression fundamentals, standards and practice. Kluwer Academic Publishers, 2002.

51. Yang W.Y., Cao W., Chung T.S., Morris J. Applied numerical methods using MATLAB®. John Wiley & Sons, 2005.

52. Yuille A., Poggio T. Scaling theorems for zero-crossings. IEEE Trans. Patt. Anal, and Mach. Intell., 8(1), 1986, pp. 15-25.

53. Веллман P. Введение в теорию матриц. Москва: Мир, 1969.

54. Блаттер К. Вейвлет-анализ. Основы теории. Москва: Техносфера, 2006.

55. Божокин С.В., Паршин Д.А. Фракталы и мультифракталы. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001.

56. Бронштейн И.Н., Семендяев К.А. Справочник по математике для инженеров и учащихся втузов. 13-е изд., испр., Москва: Наука, Гл. ред. физ.-мат. лит., 1986.

57. Винберг Э.Б. Курс алгебры. 2-е изд., Москва: Факториал пресс, 2001.

58. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. Москва: Наука, 1984.

59. Гантмахер Ф.Р. Теория матриц, 5-е изд., Москва: Физматлит, 2010.

60. Даджион Д., Мерсеро Р. Цифровая обработка многомерных сигналов. Москва: Мир, 1988.

61. Добеши И. Десять лекций по вейвлетам. пер. с англ., Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001.

62. Желобенко Д.П. Компактные группы Ли и их представления. Москва: Наука, 1970.

63. Кашин B.C., Саакян A.A. Ортогональные ряды. 2-е изд., доп, Москва: Изд-во АФЦ, 1999.

64. Колмогоров А.Н., Фомин C.B. Элементы теории функций и функционального анализа. 7-е изд., Москва: Физматлит, 2004.

65. Кроновер P.M. Фракталы и хаос в динамических системах. Основы теории. Москва: Постмаркет, 2000.

66. Малла С. Вейвлеты в обработке сигналов, пер. с англ., Москва: Мир, 2005.

67. Мандельброт Б. Фрактальная геометрия природы, пер. с англ., Москва: Институт компьютерных исследований, 2002.

68. Михлин С.Г. Линейные уравнения в частных производных. Москва: Высшая школа, 1977.

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

70. Понтрягин Л.С. Непрерывные группы. 3-е изд., испр., Москва: Наука, 1973.

71. Рихтмайер Р. Принципы современной математической физики, т. 2, пер. с англ., Москва: Мир, 1984.

72. Сергиенко А.Б. Цифровая обработка сигналов. СПб.: Питер, 2002.

73. Столниц Э., ДеРоуз Т., Салезин Д. Вейвлеты в компьютерной графике, пер. с англ., Ижевск: НИЦ «Регулярная и хаотическая динамика», 2002.

74. Хёрмандер Л. Анализ линейных дифференциальных операторов с частными производными: в 4-х т., т. 1., Теория распределений и анализ Фурье, пер. с англ., Москва: Мир, 1986.

75. Чуй Ч.К. Введение в вейвлеты. пер. с англ., Москва: Мир, 2001.