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

• Нго Хыу Фук
• кандидат физико-математических наук
• 2005

Оглавление диссертации кандидат физико-математических наук Нго Хыу Фук

ВВЕДЕНИЕ.

ГЛАВА 1: ОБЗОР ИСПОЛЬЗОВАНИЯ ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЯ В

ОБРАБОТКЕ ДИСКРЕТНЫХ СИГНАЛОВ.

Введение.

1.1. Основы теории вейвлет-преобразования.

1.1.1. Непрерывное вейвлет-преобразование.

1.2. Кратномасштабное представление функций.

1.2.1. Представление функций при помощи вейвлетов.

1.3. Вейвлет-ряды дискретного времени.

1.4. Дискретное вейвлет-преобразование.

1.4.1. Матричное описание Э\¥Т.

1.4.2. Описание DWT посредством блоков фильтров.

1.5. Гладкость базисных функций.

1.6. Обзор использования вейвлет-преобразования в обработке дискретных сигналов.

1.6.1. Применение вейвлет-преобразования для сжатия данных.

1.6.2. Применение вейвлет-преобразования для кратномасштабных кривых.

1.6.3. Применение вейвлет-преобразования для поверхности.

1.6.4. Другие применения вейвлет-преобразования.

1.7. Выводы.

ГЛАВА 2: ПАРАЛЛЕЛЬНО-РЕКУРСИВНЫЕ МЕТОДЫ ВЫПОЛНЕНИЯ ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЯ ДЛЯ ОДНОМЕРНЫХ И ДВУМЕРНЫХ

СИГНАЛОВ.

Введение.

2.1. Параллельно-рекурсивные методы выполнения вейвлетпреобразования для одномерных сигналов.

2.1.1. Алгоритм параллельно-рекурсивных вейвлетов.

2.1.1.1. Разбиение сигнала.

2.1.1.2. Выполнение вейвлета в каждом разделении.

2.1.2. Работа алгоритма параллельно-рекурсивных вейвлетов. а. Временные затраты на вычисления. б. Временные затраты на обмен данными между процессорами. в. Временные затраты для полного преобразования.

2.1.3. Модифицирование алоритма параллельно-рекурсивных вейвлетов

2.1.4. Обратное вейвлет-преобразование.

2.2. Параллельно-рекурсивные методы выполнения вейвлет-преобразования для двумерных сигналов.

2.2.1. Стандартные параллельно-рекурсивные методы выполнения вейвлет-преобразования.

2.2.2. Нестандартные параллельно-рекурсивные методы выполнения вейвлет-преобразования.

2.2.3. Анализ функций двумерного преобразования.

2.3. Выводы.

ГЛАВА 3: ПРИМЕНЕНИЕ 2В МОМЕНТОВ ЛЕЖАНДРА В ЗАДАЧАХ

ОБРАБОТКИ ДИСКРЕТНЫХ СИГНАЛОВ.

Введение.

3.1. Моментные инварианты как характеристики двумерных дискретных сигналов.

3.1.1. Моментные инварианты функции двух аргументов.

3.1.2. Метод построения моментных инвариантов произвольного порядка

3.1.3. Аффинные инварианты.

3.2. 2Т> моменты Лежандра, математическая основа и применения.

3.2.1. Математическая основа. а. Центр масс. б. Ориентация. в. Рабочий прямоугольник.

3.2.2. Инварианты 20 моментов Лежандра относительно сдвига. а. Теоретическая основа. б. Экспериментальные результаты.

3.2.3. Масштабные инварианты 20 моментов Лежандра. а. Теоретическая основа. б. Экспериментальные результаты.

3.2.4. Инварианты 20 моментов Лежандра относительно преобразования поворота. а. Теоретическая основа. б. Экспериментальные результаты.

3.3. Практическое использование Ю Моментных характеристик Лежандра при обработке двумерных дискретных сигналов.

3.3.1. Задача анализа изображений.

3.3.1.1. Формирование признаков по изображению.

3.3.1.2. Основные требования к признакам, вычисляемым по изображениям.

3.3.1.3. Нормализация изображений при вычислении признаков используется в работе (в программе). а. Яркостная нормализация. б. Нормализация масштаба объекта. в. Нормализация положения объекта. г. Нормализация ориентации объекта.

3.4. Выводы.

ГЛАВА 4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ПАРАЛЛЕЛЬНО-1 , РЕКУРСИВНОГО МЕТОДА ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЯ И ЕЕ г ПРИМЕНЕНИЕ ДЛЯ АНАЛИЗА СИГНАЛОВ.

Введение.

4.1. Критерии качества изображений и погрешности их дискретного представления.

4.1.1. Критерии качества изображений.

4.1.1.1. Критерий визуального восприятия.

4.1.1.2. Среднеквадратичный критерий.

4.1.1.3. Критерий максимальной ошибки (равномерного приближения)

4.1.2. Погрешности дискретного представления изображений.

4.1.2.1. Оценка погрешностей квантования параметра по уровню.

4.1.2.2. Общая погрешность цифрового представления изображений

4.2. Использование параллельно-рекурсивного вейвлет-преобразования в задаче уменьшения шума на изображениях.

4.2.1. Статистическое испытание значения.

4.2.2. Методы фильтрации.

1. Жесткий и мягкий порог.

2. Пороговая обработка k-сигмы.

3. Повторяющееся фильтрование.

4. Универсальный порог.

5. CAO пороговая обработка.

4.2.3. Удаление шума с помощью вейвлет методов.

4.2.4. Использование параллельно-рекурсивного вейвлет-преобразования в анализе изображений.

4.3. Разработка пользовательского интерфейса.

4.3.1. Общая структура программы моделирования.

4.3.2. Программирование входных изображений.

4.3.3. Программирование алгоритма параллельно-рекурсивного вейвлет-преобразования

4.3.4. Программирование удаления шума с помощью вейвлет методов

4.4. Разработка оконного графического интерфейса.

4.5. Выводы.

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

Вейвлет-преобразование (wavelet transformation) в настоящее время является одним из наиболее распространенных методов обработки сигналов. Первое упоминание о вейвлетах появилось в литературе по цифровой обработке и анализу сейсмических сигналов (работы А.Гроссмана и Ж.Морлета[8]). Так как интерес авторов заключался в анализе сигналов, набор базисных функций был избыточным. Далее, математик И.Мейер[49] показал существование вейвлетов, образующих ортонормальный базис в L2(R). Дискретизация вейвлет-преобразования была описана в статье И.Добеши[16], которая перекинула мост между математиками и специалистами в области обработки сигналов. Добеши разработала семейство вейвлет-фильтров, имеющих максимальную гладкость для данной длины фильтра[16,21,29].

И И.Добеши, и С.Маллат[63] показали, что практическое выполнение вейвлет-преобразования осуществляется посредством двухполосного банка фильтров анализа-синтеза, известного ранее в теории субполосного кодирования. Эта теория может быть описана в терминах вейвлетов. Главное различие между этими двумя направлениями заключается в критериях построения фильтров, как это будет показано далее.

При анализе дискретных двумерных сигналов большую роль играет вычисление моментных инвариантов, не зависящих от сдвига, масштабирования и вращения. Моменты Лежандра (работы C.W. Chong, P. Raveen-dran[12]) с ядром в виде полиномов Лежандра, принадлежащие классу ортогональных моментов, используются для выявления независимых характеристик сигнала. Основываясь на существующем методе вычисление моментов Лежандра, в работе вводятся и используются новые инварианты моментов Лежандра, относительно сдвига, масштабирования и поворота.

В настоящее время перспективным направлением повышения эффективности вейвлет-преобразований является параллельно-рекурсивные методы вычисления вейвлетов[42,57,59]. Эти методы могут быть использованы на многопроцессорных системах.

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

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

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

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

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

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Нго Хыу Фук

4.5. ВЫВОДЫ

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

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

ЗАКЛЮЧЕНИЕ

Итак, в диссертации были рассмотрены основные положения теории и практики вейвлет-преобразования. В ней также рассмотрены непрерывное и дискретное вейвлет-преобразования, ряды вейвлетов, быстрые алгоритмы вычислений.

В диссертации предложен эффективный параллельно-рекурсивный метод выполнения вейвлет-преобразования для одномерных и двумерных сигналов. Этот новый метод может быть использован для обработки сигналов на параллельных системах.

В качестве практического применения параллельно-рекурсивного вейвлет-преобразования рассмотрены: использование параллельно-рекурсивного вейвлет-преобразования в задаче подавления шума; использование параллельно-рекурсивного вейвлет-преобразования в задаче обнаружения особенностей сигналов;

Для системы обработки изображений рассмотрены моменты, основанные на полиномах Лежандра и их инварианты относительно аффинного преобразования. Предложен новый метод построения моментных характеристик Лежандра, инвариантных относительно поворота.

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

• предложена и программно реализована схема параллельно-рекурсивного дискретного вейвлет-преобразования для двумерных сигналов. предложены инварианты Ю момента Лежандра, относительно поворота.

• предложен и программно реализован способ применения инвариантов 20 момента Лежандра в задаче обработки двумерных сигналов.

Список литературы диссертационного исследования кандидат физико-математических наук Нго Хыу Фук, 2005 год

1. A. Cohen, I. Daubechies, and J. C. Feauveau. "Biorthogonal bases of compactly supported wavelets". Communications on Pure and Applied Mathematics, 45(5):485-500, June 1992.

2. A. Fournier, " Wavelets and their Applications in Computer Graphics", 1995.

3. A. Grossman and J. Morlet. "Decomposition of functions into wavelets of constant shape, and related transforms". In L. Streit, editor. Mathematics and Physics: Lectures on Recent Results. World Scientific, Singapore, 1985.

4. A. S. Lewis, G. Knowles, " Video compression using 3D wavelet transformsr", Electronics Letters, 26(6):396-398, 15 March 1990.

5. Andrew Certain, Jovan Popovic, Tony DeRose, Tom Duchamp, David Salesin, Werner Stuetzle, "Interactive multiresolution surface viewing". In Proceeding of SIGGRAPH '96. ACM, NewYork, 1996.

6. Anil K. Jain, "Digital Image Processing", 1989 Prentice-Hall International.

7. W. Chong, P. Raveendran, "Translation and scale invariants of Legendre moments", 2003.

8. Charles K. Chui, "An Introduction to Wavelets", Academic Press, Boston, 1992.

9. H.Christian Cenker, " Wavelet Packets and Optimization in Pattern RecognitionProc. of the 21st international workshop of the AAPR, Hallstatt, Austria, May 1997, pp. 49-58.

10. Daubechies I. "Orthonormal Bases of Compactly Supported Wavelets". Communication on Pure Applied Mathematics, 1988, vol.41.P. 906-966.

11. Daubechies I. "Ten Lectures on Wavelets". SI AM, Philadelphia, 1992

12. Daubechies I. "The wavelet transform, time-frequency localization and signal analysis". IEEE Trans. Inform. Theory, 1990, №5. P.961-1005.

13. David J. Heeger, James R. Bergen, "Pyramid-based texture analysis/synthesis", In Proceeding of SIGGRAPH '95, p. 229-238, ACM, NewY-ork, 1995.

14. David Meyers, "Multiresolution tiling', Computer Graphics Forum, 13(5):325-340, December 1994.

15. David Meyers, "Reconstruction of surfaces from planar contours", Ph.D. thesis, University of Washington, 1994.

16. David Neary B.Sc., " Wavelet transform in image processing", website Dublin City University School of Electronic Engineering, website http://www.redbrick.dcu.ie/~bolsh/thesis/node53.html:

17. G. Beylkin, R. Coifinan and V. Rokhlin, "Fast wavelet transforms and numerical algorithms", Communication on Pure and Applied Mathematics, 44(2), pp. 141-183, March 1991.

18. Gerald Farin, "Curves and Surfaces for Computer Aided Geometric DesignAcademic Press, Boston, third edition, 1993.

19. Image Analysis and Understanding, Lecture Materials: Shape representation and description, websitehttp://www.icaen.uiowa.edu/~dip/LECTURE/lecture.html.

20. J. R. Packer, "Algorithms for Image Processing and Computer Vision ", 1997.

21. Jawerth B., Sweldens W. "An overview of wavelet based multiresolution analysis". SIAMRev., 1994, №3. P.377-412.

22. Josef Hoschek, Dieter Lasser, "Fundamentals of Computer Aided Geometric Design", A. K. Peters, Wellesley, MA, third edition, 1993.

23. L. A. Torres-Méndez, J. C. Ruiz-Suárez, L. E. Sucar, G. Gómez, "Translation, Rotation and Scale Invariant Object Recognition", website http://www.mor.itesm.mx/~giovani/ieee/nodel.html.

24. Mallat S. "A theory for multiresolution signal decomposition: the wavelet representation". IEEE Trans. Pattern Analysis and Machine Intelligence, 1989, P.674-693.

25. Mallat, Zhong, "Characterization ofSighnals from Multiscale Edges", 1992.

26. Max Fomitchev, "Введение в вейвлеты и вейвлет-преобразования", 1998, website http://www.smolensk.m/user/sgma/MMORPH/N-4-html/l.htm.

27. Michael J. Andrews, " Moment Representation of Blobs in 2-D Intensity Images", website http://www.gweep.net/~rocko/Moment/paper.html.

28. Nira Dyn, David Levin, "The subdivision experience", In P.-J. Laurent, A. Le Mehaute, L. L. Schumaker, editor, "Wavelets, Images, and Surface Fitting", p. 229-244. A. K. Peters, Wellesley, MA, 1994.

29. Rioul O., Vetterli M. " Wavelets and signal processing". IEEE Signal Processing Magazine, 1991, №10. P. 14-38.

30. Roberto Hirata Junior, "Multiresolution Design of Aperture Operators", 2002 Journal of Mathematical Imaging and Vision.

31. Schumaker L., Webb G., editors.11 Recent Advances in Wavelet Analysis". Academic Press, New York, 1993.480 p.

32. Shigeru Muraki, " Volume data and wavelet transforms", IEEE Computer Graphics and Applications, 13(4):50-56, July 1993.

33. Stephane Mallat, "Multiresolution representation signal decomposition: The wavelet representation", IEEE Transactions on Pattern Analysis and Machine Intelligence, 11(7): 674-693, July 1989.

34. Stephane Mallat, Sifen Zhong," Wavelet transform maxima and multiscale edges", In M. B. Ruskai et al., editor, Wavelets and Their Applications, p. 67-104, Jones and Bartlett, Boston, 1992.

35. Steven J. Gortler, Michael F. Cohen, "Hierarchical and variational geometric modeling with wavelets", In Proceeding of the 1995 Symposium on Interactive 3D Graphics, p. 35-42, ACM, NewYork, 1995.

36. Strang G. "Wavelets and dilation equations: A brief introduction". SIAM Rev., 1989, №4. P.614-627.

37. Tanaka Nobuatsu, "Parallel processing of Haar-wavelet-preconditioned conjugate gradient methodsTransactions of JSCES, Paper No.2001003.

38. Taswell, C. "Handbook of Wavelet Transform Algorithms", Boston, MA: Birkhâuser, 1996.

39. Teolis, A. "Computational Signal Processing with Wavelets", Boston, MA: Birkhâuser, 1997.

40. Tony D. DeRose, Michael Lounsbery, Leena Maija Reissell, "Curvers and surfacesIn Alain Fourier, editor, SIGGRAPH '95 Course Notes 26: Wavelets and Their Applications in Computer Graphics, p. 123-154, ACM, NewYork, 1995.

41. Tudor Barbu, "A pattern recognition approach to image segmentation", Proceedings of the Romanian Academy, Series A, Volume 4, number 2/2003.

42. Vetterli M., Herley C. " Wavelets and Filter Banks: Theory and Design". IEEE Transactions on Signal Processing, 1992, v.40. P. 2207-2232.

43. Winser E. Alexander, Douglas S. Reeves, Clay S. Gloster JR, "Parallel Image Processing with the Block Data Parallel Architecture", IBM J. RES. DEVELOP Vol. 44, No. 5, September 2000.

44. Yves Meyer. "Ondelettes et fonctions splines". Technical report, Séminaire EDP, Ecole Polytechnique, Paris, 1986.

45. Yves Meyer, " Wavelets: Algorithms and Applications", SIAM, Philadelphia, 1993, Translated by Robert D. Ryan.

46. Астафьева H.M. "Вейвлет-анализ: основы теории и некоторые приложенияУспехи физических наук, 1996, №11. С. 1145-1170.

47. В.А. Сойфера, "Методы компьютерной обработки изображений 2003.

48. Желудев В.А. "О вейвлетах на базе периодических сплайновДокл. 1994, №1. С. 9- 13.

49. Кравченко В. Ф., Рвачев В. А., Пустовойт В. И. "Ортонормированные системы типа wavelet на основе атомарных функций". Докл. РАН,1996, С. 16-18.

50. Л. Левкович-Маслюк, А. Переберин, "Дв<я курса по вейвлет-анализу website AlgoList.Manual.ru,http://algolist.manual.ru/compress/image/leo lev/lecturel/wavl l.php.

51. Н. X. Фук, "Translation, scale and rotation invariant of2DLegendre moment: Mathematical foundation and applications", 8 International Conference on Pattern Recognition and Information Processing (PRIP'05), C. 1317.

52. H. X. Фук,"Алгоритм параллельно-рекурсивного вейвлет-преобразо-вания", международная конференция "Ломоносов 2005", С. 43-44.

53. Н. X. Фук, "Применение вейвлет-преобразования для анализа информативности двумерных сигналов", V международная конференция по неравновесным процессам в соплах и струях (NPNJ-2004), С. 155-156.

54. Н. X. Фук, "Применение параллельно-рекурсивных методов вейвлет-преобразования для обработки двумерных сигналов", Труды МАИ.

55. Петухов А. П. "Периодические дискретные всплески". Алгебра и анализ, №3. С. 151-183.

56. С. Гудман, С. Хидетниеми, "Введение в разработку и анализ алгоритмов", издательство "МИР" Москва 1981.

57. Э. Столниц, Т. ДеРоуз, Д. Салезин, "Вейвлеты в компьютерной графике: теория и приложения", Москва, Ижевск, 2002.

58. Stephane Mallat. "Mult ¡resolution representation and wavelets", Ph.D. thesis, University of Pennsylvania, 1988.

59. Е.Ковачевич, руководителя подразделения лаборатории Bell, занимающегося вейвлетами: website: http://cm.bell-labs.com/who/jelena/papers/papers.html.

60. М. Teague, "Image analysis via the general theory of moments", J. Opt, Soc, Am. 70 (8) (1980) pp. 920-930.

61. M.K. Mandal, T. Aboulnasr, S. Panchanathan, "Image indexing using moments and wavelets", IEEE Trans. Consumer Electron. 42 (3) (1996), pp. 557-565.

62. J. Haddadnia, K. Faez, P. Moallem, "Neural network based face recognition with moment invariant', Proceedings of International Conference on Image Processing, Vol. 1, 2001, pp. 1018-1021.

63. H. Qjidaa, L. Radouane, "Robust line fitting in a noisy image by the method of moments", IEEE Trans. Pattern Anal. Mach. Intell. 21 (11) (1999), pp. 1216-1223.

64. R. Mukundan, K.R. Ramakrishnan, "Moment Functions in Image Analysis", Theory and Applications, World Scientific, Singapore, 1998.

65. Анисимов Б.В., Курганов В.Д., Злобин В.К., "Распознавание и цифровая обработка изображений", (М.: высшая школа, 1983).

66. Abu-Mostafa У., Psaltis D., IEEE Trans. Pattern Anal. Mach. Intell. PAMI-7(1)46(1985).

67. Maghsoodi R., Rezaie В., "Methods of Handling and Processing Imagery", SPIE 757 58(1987).

68. Abu-Mostafa Y., Psaltis D., IEEE Trans. Pattern Anal. Mach. Intell. PAMI-6(6) 698 (1984).

69. Буреев В.А. и др. "Зарубежная радиоэлектроника", 4 52 (1980).

70. Виттих В.А., Сергеев В.В, Сойфер В.А., "Обработка изображении в автоматизированных системах научных исследований", М.: Наука, 1982.

71. A. Lega, Н. Sholl, J. М. Alimi, A. Bijaoui, and P. Bury, "A parallel algorithm for structure detetion based on wavelet and segmentation analysis", Parallel Computing, 21: 265-285, April 1995.

72. Robert Lang and Andrew Spray, "The 2d wavelet transform on a massively parallel machine", In Proceedings of the Australasion Conference on Parallel and Real-Time Systems, pages 325-332, Freemantle, Western Australia, 28-29 September 1995.