ISSN 0236-235X (P)
ISSN 2311-2735 (E)

## Next issue

3
Publication date:
16 September 2020

2020
2019
-->

## Algorithms of regular time series continuous wavelet transformation: development and software implementation

Date of submission article: 2017-10-16
UDC: 004.94
The article was published in issue no. № 4, 2017 [ pp. 765-769 ]
Abstract:One of the actively developing directions of data analysis is wavelet transformation. It is used for analyzing medical data, image processing and other purposes. This paper considers methods of calculating coefficients of continuous wavelet transformation of even time series. In the classical approach, calculation of some coefficients is redundant because the value of some wavelets is zero. To remove redundancy, the authors propose using wavelet characteristics in the time domain, which allows obtaining a wavelet window width, wich depends on the given scale. The paper gives the obtained characteristics values of mother wavelets, such as Gaussian wavelets of the 1st to the 8th order, the DOG wavelet and the Morlet wavelet. The proposed algorithm for calculating wavelet values is based on these characteristics. The algorithm allows reducing the number of readings of the used wavelet. For each given scale, there is a determined number of nonzero wavelet values and their calculated values. As a result, we get an array of all wavelet values, which are necessary for transformation. The paper proposes an algorithm for evaluating the coefficients of continuous wavelet transformation. It is based on decreasing repeated calculations of wavelets. The reduction of computations is due to taking into account wavelet invariance regarding a shift. Thus, if we calculate all nonzero wavelet values for all scale once and store it, then it is enough we to refer to the wavelet value by number in array corresponding to the shift. The developed algorithms are implemented as a software package. The paper shows that the proposed algorithm works faster than the classical one without significant loss of calculation accuracy.
Аннотация:Одним из активно развивающихся направлений анализа данных является вейвлет-преобразование, которое применяется для анализа медицинских данных, обработки изображений и в других областях. В статье рассматриваются способы вычисления коэффициентов непрерывного вейвлет-преобразования случайных процессов с регулярной дискретизацией. При классическом подходе вычисление некоторых коэффициентов может оказаться избыточным из-за того, что ряд значений вейвлетов равны нулю. Для устранения избыточности предлагается использовать характеристики вейвлетов во временной области, что позволяет получить ширину окна вейвлета, зависящую от заданного масштаба. Таблица с полученными значениями характеристик для основных вейвлетов, таких как Гаусса 1–8-го порядков, DOG-вейвлета и вейвлета Морле, приведена в статье. На их основе предложен алгоритм вычисления значений вейвлетов, который позволяет уменьшить число отсчетов используемого вейвлета: для каждого заданного масштаба определяется число ненулевых значений вейвлета и вычисляются их значения. Таким образом, в результате получаем массив всех значений вейвлетов, необходимых для преобразования. Для оценки коэффициентов непрерывного вейвлет-преобразования предложен алгоритм, основанный на сокращении повторных вычислений вейвлетов. Сокращение вычислений достигается за счет учета инвариантности вейвлетов относительно сдвига. Таким образом, вычислив один раз ненулевые значения вейвлетов для всех масштабов и сохранив их, достаточно обращаться по номеру к значению, соответствующему номеру сдвига. Разработанные алгоритмы реализованы в виде комплекса программ. Показано, что предложенный алгоритм работает быстрее классического и без значительной потери точности вычислений.
 Authors: A.A. Stolbova (anastasiya.stolbova@bk.ru) - Samara National Research University (Assistant), Samara, Russia Keywords: norm of the wavelet, radius of the wavelet, continuous wavelet transformation Page views: 3753 PDF version article Full issue in PDF (29.80Mb)

Font size:       Font:

При анализе процессов различной природы применяется частотный анализ. Одним из его наиболее распространенных методов является преобразование Фурье. Этот метод подходит для анализа стационарных процессов, но при анализе нестационарных процессов он ограничен. В таком случае для анализа применяются частотно-временные методы, к которым относятся оконное преобразование Фурье, преобразование Габора, преобразование Вигнера–Виля, а также дискретное и непрерывное вейвлет-преобразования.

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

(1)

где x(t) – случайный процесс; ψ(t) – выбранный базовый вейвлет; a ≠ 0 – параметр масштаба; b ≥ 0 – параметр сдвига [1–3].

Принимая во внимание то, что исследуемые данные являются дискретными, формула (1) преобразуется в следующие выражения:

– в случае с интегрированием методом прямоугольников:

,                         (2)

– в случае с интегрированием методом трапеций:

,              (3)

где N – число отсчетов исходного процесса.

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

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

Характеристики вейвлетов. Центр и эффективный радиус являются одними из характеристик вейвлетов во временной области [5–7]:

– центр,

– радиус,

где  – норма вейвлета.

В работах [8, 9] рассмотрены наиболее часто используемые вейвлеты. В таблице 1 приведены дан- ные характеристики вейвлетов Гаусса 1–8-го по- рядков, DOG-вейвлета и вейвлета Морле.

Используя данные характеристики, можно вычислить ширину окна вейвлета, необходимую для оценки коэффициентов вейлет-преобразования: wt = 8aDt, где a – параметр масштаба вейвлета.

Ширина вейвлета Гаусса 8-го порядка в зависимости от параметра масштаба показана на рисунке 1.

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

1.    Определить число отсчетов вейвлета, попадающих в ширину wt для текущего значения масштаба ai: , где ent[] – операция взятия целой части; Dt0 – интервал дискретизации вейвлета.

2.     Вычислить значения вейвлета:

, где .

3.    Повторить пункты 1 и 2 для каждого i-го масштаба.

Блок-схема данного алгоритма приведена на рисунке 2.

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

1.    Загрузить исходный процесс со значениями xk(tk), числом отсчетов N и интервалом дискретизации Dt:

 x0 x1 … … … xk-1 xk xk+1 … xn-1

2. Получить массив масштабов:

,

где i = 0, …, Na – 1; wmin – минимальная частота; Dw – интервал дискретизации частоты;

 a0 a1 … … … ai-1 ai ai+1 … …

3. Рассчитать значения вейвлетов для всех масштабов a при сдвиге b = 0 по алгоритму, рассмотренному выше. В результате получается таблица значений масштабированных вейвлетов:

4. В зависимости от номера сдвига j и масштаба i сформировать индексы перемножаемых отсчета сигнала и масштабированного вейвлета из таблицы , где ni – число отсчетов i-го вейвлета; K – шаг сдвига.

5. Рассчитать значения коэффициентов вейвлет-преобразования, используя выражение (2) или (3):

6. Повторить пункты 4 и 5 для всех значений i и j.

На рисунке 3 представлена блок-схема алгоритма формирования индексов и вычисления коэффициента вейвлет-преобразования Wij.

Программный комплекс. Программный комплекс [10] был разработан на основе алгоритмов, рассмотренных в данной работе, и реализован на языке C# на платформе .NET. Структурная схема комплекса представлена на рисунке 4. Модуль получения исходного сигнала предназначен для генерации сигналов: детерминированных и случайных, равномерно и неравномерно дискретизированных, стационарных и нестационарных. Предложенные алгоритмы реализованы в модуле построения вейвлетов и вычислителе вейвлет-преобразования с регулярной дискретизацией. Модуль вычисления погрешностей предназначен для оценки погрешности расчета вейвлет-коэффициентов с помощью предложенных алгоритмов вейвлет-преобразования.

Экспериментальные исследования. Продемонстрируем работу алгоритмов с помощью разработанного комплекса программ. В качестве экспериментального сигнала используются синусоида с частотой 2 рад/c и вейвлет Гаусса 8-го порядка.

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

, где W – точное значение коэффициента;  – оценка коэффициента.

Для сравнения скейлограмм вейвлет-преобразования введем следующую величину:

,

где  – оценка скейлограммы.

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

Таблица 2

Сравнение алгоритмов

Table 2

Comparison of algorithms

 Параметр Классический Оптимальный t, мс 2 563 110 dск 0 0,0053

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

Литература

1.     Прохоров С.А., Столбова А.А. Вейвлет-преобразование нерегулярных процессов без восстановления пропущенных отсчетов // Перспективные информационные технологии (ПИТ 2017): тр. Междунар. науч.-технич. конф. Самара, 2017. С. 154–156.

2.     Mallat S.A. Wavelet tour of signal processing. The sparse way. Elsivier, 2009, 805 p.

3.     Чуи Ч. Введение в вейвлеты; [пер. с англ.]. М.: Мир, 2001. 412 с.

4.     Витязев В.В. Анализ неравномерных временных рядов. СПб: Изд-во СПб. ун-та, 2001. 68 с.

5.     Астафьева Н.М. Вейвлет-анализ: основы теории и при- меры применения // Успехи физических наук. 1996. Т. 166. № 11. С. 1145–1170.

6.     Cohen L. Time-frequency analysis: theory and applications. Prentice-Hall, NJ, 1995, 315 р.

7.     Короновский А.А., Храмов А.Е. Непрерывный вейвлетный анализ и его приложения. М.: Физматлит, 2003. 176 с.

8.     Добеши И. Десять лекций по вейвлетам; [пер. с англ.]. Ижевск, 2001. 464 с.

9.     Дьяконов В.П. Вейвлеты. От теории к практике. М.: СОЛОН-Р, 2002. 448 с.

10.   Прохоров С.А., Столбова А.А. Программный комплекс для проведения вейвлет-анализа: свид. о гос. регистр. прогр. для ЭВМ. № 2015617561; заявл. 06.04.2015; опубл. 20.08.2015.

References
1.    Prokhorov S.A., Stolbova A.A. Wavelet transformation of even processes without reconstructing ignored samples. Perspektivnye informatsionnye tekhnologii (PIT 2017): tr. Mezhdunar. nauch.-tekhnich. konf. [Proc. Int. Sci. and Tech. Conf. Advanced Information Technologies (PIT 2017)]. Samara, 2017, pp. 154–156 (in Russ.).
2.    Mallat S.A. Wavelet Tour of Signal Processing. The Sparse Way. Elsivier Publ., 2009, 805 p.
3.    Chui Ch.K. An Introduction to Wavelets. Academic Press, NY, 1992, 266 p. (Russ. ed.: Moscow, Mir Publ., 2001,
412 p.).
4.    Vityazev V.V. Analiz neravnomernykh vremennykh ryadov [Analysis of Uneven Time Series]. St. Petersburg, St. Petersburg Univ. Publ., 2001, 68 p.
5.    Astafeva N.M. Wavelet analysis: basic theory and some applications. Uspekhi fizicheskikh nauk [Physics-Uspekhi]. 1996, vol. 166, no. 11, pp. 1145–1170 (in Russ.).
6.    Cohen L. Time-Frequency Analysis: Theory and Applications. Prentice-Hall Publ., NJ, 1995, 315 р.
7.    Koronovsky A.A., Khramov A.E. Nepreryvny veyvletny analiz i ego prilozheniya [Continuous Wavelet Analysis and its Applications]. Moscow, Fizmatlit Publ., 2003, 176 p.
8.    Daubechies I. Ten Lectures on Wavelets. PA, USA, 1992, 357 p. (Russ. ed.: Izhevsk, 2001, 464 p.).
9.    Dyakonov V.P. Veyvlety. Ot teorii k praktike [Wavelets. From theory to practice]. Moscow, SOLON-R Publ., 2002, 448 p.
10.    Prokhorov S.A., Stolbova A.A. Programmny kompleks dlya provedeniya veyvlet-analiza [A software complex for wavelet analysis]. State registration certificate of a computer program. no. 2015617561, 2015 (in Russ.).

 Permanent link:http://swsys.ru/index.php?page=article&id=4381&lang=en PDF version articleFull issue in PDF (29.80Mb) The article was published in issue no. № 4, 2017 [ pp. 765-769 ]

Perhaps, you might be interested in the following articles of similar topics: