Сравнение алгоритма кратномасштабного анализа изображений в частотной области с алгоритмом Малла
Выполнено сравнение алгоритма кратномасштабного анализа (КМА) изображений в частотной области с алгоритмом Малла. В алгоритме Малла используются масштабные коэффициенты, кратные двум, и вычисление производится итеративно с двукратным прореживанием вейвлет-коэффициентов при каждом последующем разложении. Этот алгоритм также называется быстрым дискретным вейвлет-преобразованием (ВП). В алгоритме КМА в частотной области для увеличения скорости вычисления применяется быстрое преобразование Фурье (БПФ). Вейвлет-коэффициенты вычисляются не итеративно: для каждого уровня они получаются из сигнала независимо от предыдущих уровней, и кратность анализа может быть меньше двух. Уменьшение кратности позволяет увеличить глубину декомпозиции. В отличие от алгоритма Малла применяются симметричные или антисимметричные ортогональные вейвлеты, что повышает точность реконструкции. Изображение обрабатывается не по строкам и столбцам, а прогрессивной разверткой в целом. Применение БПФ уменьшает время преобразования изображений на четыре порядка по сравнению прямым численным интегрированием, и за счет этого время декомпозиции и реконструкции не больше по сравнению с временем дискретного ВП и может быть меньше. Автор заявляет об отсутствии конфликта интересов.
Comparison of the algorithm of multiscale image analysis in the frequency domain with the Mall algorithm.pdf Вейвлет-анализ является эффективным инструментом исследования локальных свойств нестационарных сигналов. Базисные функции, называемые вейвлетами, обладают свойством частотновременной локализации, и сам анализ называется частотно-временным. Аналогом частоты для вейвлет-преобразования является обратная величина масштабного коэффициента. В настоящее время для кратномасштабного анализа (КМА) сигналов используется алгоритм Малла - быстрый способ вычисления дискретного вейвлет-преобразования (ВП) [1]. КМА - это m-шаговое дискретное ВП. Максимальное значение m называется глубиной декомпозиции (разложения). У алгоритма Малла есть недостатки: 1. Необходимо иметь масштабирующую функцию. 2. Амплитудно-частотная характеристика вейвлетов неравномерна. 3. Вейвлеты несимметричны или антисимметричны. 4. Коэффициент изменения масштаба меняется только с кратностью 2. 5. Точность вычисления уменьшается с увеличением уровня разложения, так как при каждом уровне декомпозиции длина выборки уменьшается в 2 раза. 6. Не используется прогрессивная развертка изображения при кратномпсштабном анализе. 7. Необходимо решать много уравнений для конструирования вейвлетов больших порядков. Для устранения этих недостатков актуально использование КМА в частотной области. Преимуществом алгоритма в частотной области является еще и способ вычисления. Если для определения вейвлет-коэффициентов последующего уровня в алгоритме Малла необходимо вычислить предыдущие вейвлет-коэффициенты, то в частотной области можно параллельно вычислять все вейвлет-коэффициенты. На аппаратном уровне это можно сделать, используя много устройств быстрого преобразования Фурье (БПФ), соединенных параллельно, тем самым уменьшив во много раз время КМА. Исходя из таких предположений, сравниваются алгоритм Малла и алгоритм КМА в частотной области. Для исследования нестационарных сигналов кроме ВП применяются и другие преобразования. Самое известное их них - оконное преобразование Фурье (ОПФ), когда сигнал разлагается в спектр с использованием БПФ на участках (окнах), намного меньших длительности самого сигнала [2]. Таким образом добиваются улучшения временного разрешения, т.е. того момента, когда произошло изменение частоты сигнала. При использовании ОПФ узкое окно обладает лучшим временным разрешением, широкое окно - лучшим частотным разрешением. Проблема состоит в том, что приходится выбирать фиксированное окно для всего сигнала, тогда как разные участки сигнала могут требовать применения разных окон. ОПФ покрывает плоскость время-частота прямоугольниками с неизменным разрешением по времени и частоте на всех участках, а для исследования реальных сигналов необходимо разбить плоскость время-частота прямоугольниками с разным разрешением по времени и частоте на разных участках. Около резких изменений сигнала окна должны быть узкими, а в остальной области можно использовать более широкие окна. Как раз ВП имеет хорошее разрешение по времени и плохое разрешение по частоте на высоких частотах, а на низких частотах - хорошее разрешение по частоте и плохое разрешение по времени. Когда сигнал имеет высокочастотные компоненты короткой длительности и низкочастотные компоненты протяженной длительности, использование ВП наиболее эффективно. ВП анализирует сигнал на различных частотах и с различным разрешением одновременно. 74 Семенов В.И. Сравнение алгоритма кратномасштабного анализа изображений Разновидностями ОПФ также являются преобразование (метод) Прони [3], когда применяется разложение сигнала на экспоненциально затухающие синусы или косинусы, и другие методы, использующие полиномы Чебышева, Кравчука, Шарлье и гибриды Кравчука-Чебышева [4, 5]. Затухающие экспоненциально синусы имеют перекрывающие широкие частотные характеристики, и разложение является неортогональным. Другие методы также основаны на вычислениях во временной области, используют рекуррентные соотношения и требуют много времени для полиномов большого порядка. Из-за того, что свойство локализации хуже, чем для ВП, равно как для ОПФ и других преобразований, эти преобразования в данной работе не сравниваются с алгоритмом КМА в частотной области. Целью работы является сравнение алгоритма кратномасштабного анализа сигналов в частотной области с алгоритмом Малла с точки зрения применяемых вейвлетов, глубины декомпозиции, скорости и точности вычисления. В ходе исследования сконструированы симметричные и антисимметричные вейвлеты, которые позволили увеличить точность реконструкции изображений, уменьшить время преобразования. 1. Алгоритм Малла С. Малла в своем алгоритме использовал идеи субполосного (пирамидального) кодирования речевого сигнала. При таком кодировании сигнал пропускается через древовидное соединение высокочастотных и низкочастотных фильтров (ВЧ- и НЧ-фильтры; квадратурно-зеркальные фильтры (КЗФ)). Самый простой способ ВП - это использование простейшей масштабирующей (скейлинг) функции и вейвлета Хаара, когда КЗФ получаются за счет суммирования и разности соседних отсчетов сигнала. Суммирование эквивалентно пропусканию через НЧ-фильтр, а разность - через ВЧ-фильтр. Используя более сложные вейвлеты, такие как вейвлеты Добеши «-го порядка, вычисляют взвешенные суммы и взвешенные разности, т.е. свертку сигнала с импульсной характеристикой (ИХ) ВЧ- и НЧ-фильтров, и получаются детализирующие коэффициенты и коэффициенты аппроксимации после децимации каждого 2-го отсчета. На рис. 1 представлена схема разложения сигнала. Данное разложение можно повторить несколько раз для дальнейшего увеличения частотного разрешения с дальнейшим прореживанием коэффициентов после НЧ- и ВЧ-фильтрации. Такое разложение можно представить в виде двоичного дерева, где листья и узлы соответствуют пространствам с различной частотно-временной локализацией. На рис. 2 представлено это дерево. После первого разложения все вычисления производятся с детализирующими коэффициентами и коэффициентами аппроксимации итеративно. Обратное ВП вычисляется в обратном порядке с интерполяцией коэффициентов. К j[n] I ►(Ф2)-► Аппроксимирующие коэффициенты ф] -»| h[n] I *(Ф2)-► Детализирующие коэффициенты Рис. 1. Схема разложения сигнала при дискретном вейвлет-преобразовании Fig. 1. Signal decomposition scheme for discrete wavelet transform Коэффициенты 3-ro уровня Коэффициенты 2-го уровня Коэффициенты 1-го уровня Рис. 2. Трехуровневый банк фильтров Fig. 2. Three-level filter bank 75 Обработка информации / Data processing Разложение функций на вейвлетные ряды на заданном уровне разрешения для дискретного ВП выполняется по формуле x(t) = Z Cm,k Фт.к (t) + Z A»,k V m,k (t) , k m,k где Vm,k(t) - вейвлет, фтДО - скейлинг-функция, Dm,k, Cm,k - детализирующие и аппроксимирующие коэффициенты. В результате преобразования сигнал декомпозируется на разные частотные области, которые представлены на рис. 3. Каждая область в два раза шире предыдущей частотной области с увеличением масштабного коэффициента. Так как амплитудно-частотные характеристики (АЧХ) фильтров неидеальные, происходит наложение спектров. Рис. 3. Спектры разного масштабного коэффициента Fig. 3. Spectra of different scale coefficients Для того чтобы преобразовать изображение, каждая его строка по схеме, представленной на рис. 1, декомпозируется, потом полученные коэффициенты по такой же схеме вычисляются по столбцам (сепарабельное преобразование), и процесс повторяется до максимальной глубины разложения [1, 6-8]. 2. Алгоритм прямого и обратного ВП в частотной области Для вычисления вейвлет-спектра сигнала на основе производных функции Гаусса и вейвлетов, сконструированных в частотной области, используется формула непрерывного ВП: 1 sfa где а - масштабный коэффициент вейвлета, b - параметр сдвига. С разными масштабными коэффициентами скейлинг-функция не используется. Такое преобразование эквивалентно прохождению сигнала через полосовые фильтры в разном диапазоне частот. Для вычисления ВП прямым численным интегрированием необходимо много времени, поэтому вейвлет-спектр вычисляется в частотной области с применением БПФ. Чтобы вычислить ВП сигнала в частотной области, необходимо получить Фурье-спектры сигнала и вейвлета для разных масштабных коэффициентов а, найти комплексно сопряженный спектр и обратным преобразованием Фурье комплексно сопряженных спектров получить вейвлет-спектр сигнала. Алгоритм численного вычисления прямого непрерывного быстрого ВП сигнала S(t) по формуле (1) в частотной области представлен в работе [9]. Подобно обратному ПФ существует обратное непрерывное ВП: S (t )=C-1JJV 0 -ад t - b a W (a,b) dadb a 3+k ’ (2) где - нормализующий коэффициент: ад Cv = J FX®) I2 -®"^®
Ключевые слова
вейвлет-преобразование,
декомпозиция,
реконструкция,
кратномасштабный анализ,
алгоритм Малла,
амплитудно-частотная характеристика,
фильтрАвторы
Семенов Владимир Ильич | Чувашский государственный университет | кандидат технических наук, доцент кафедры общей физики факультета прикладной математики, физики и информационных технологий | syundyukovo@yandex.ru |
Всего: 1
Ссылки
Малла С. Вейвлеты в обработке сигналов : пер. с англ. М. : Мир, 2005. 671 с.
Новиков Л.В. Основы вейвлет-анализа сигналов. М. : ИАнП РАН, 1999. 152 с.
Митрофанов Г., Прийменко В. Основы и приложения метода Пронифильтрации // Технологии сейсморазведки. 2011. № 3. С. 93-108.
Mahmmod B.M., Abdul-Hadi A.M., Abdulhussain S.H., Hussien A. On computational aspects of Krawtchouk polynomials for high orders //j. Imag. 2020. V. 6, № 8. P. 81.
Abdulhussain S.H., Ramli A.R., Mahmmod B.M., Saripan M.I., Al-Haddad S.A.R., Jassim W.A. A new hybrid form of Kraw tchouk and Tchebichef polynomials: Design and application //j. Math. Imag. Vis. 2019. V. 61, № 4. P. 555-570.
Дремин И.Л., Иванов О.В., Нечитайло В.А. Вейвлеты и их использование // УФН. 2001. Т. 171, № 5. С. 465-501.
Добеши И. Десять лекций по вейвлетам. М.-Ижевск : Регулярная и хаотическая динамика, 2001. 464 с.
Столниц Э., Де Роуз Е., Салезин Д. Вейвлеты в компьютерной графике. М.-Ижевск : Регулярная и хаотическая динамика, 2002. 271 с.
Семенов В.И., Михеев К.Г., Шурбин А.К., Михеев Г.М. Фильтрация изображений, полученных с помощью оптического микроскопа, с применением кратномасштабного анализа // Химическая физика и мезоскопия. 2014. Т. 16, № 3. С. 399-404.
Семенов В.И., Шурбин А.К., Михеев К.Г., Михеев Г.М. Конструирование ортогональных вейвлетов в частотной области для кратномасштабного анализа сигналов // Химическая физика и мезоскопия. 2018. Т. 20, № 2. С. 230-238.
Шумарова О.С., Игнатьев С.А. Оптимальный выбор вида вейвлета при обработке сигнала с вихретокового датчика // Вестник Саратовского государственного технического университета. 2013. № 4 (73). С. 128-132.
Умняшкин С.В. Теоретические основы цифровой обработки и представления сигналов. М. : ФОРУМ-ИНФРА-М, 2009. 302 с.