Дискретное синусоидальное преобразование

В математике дискретное синусоидальное преобразование (ДСП) — это преобразование Фурье, похожее на дискретное преобразование Фурье (ДПФ), но использующее чисто действительную матрицу . Оно эквивалентно мнимым частям ДПФ примерно вдвое большей длины, работающим с действительными данными с нечетной симметрией (поскольку преобразование Фурье действительной и нечетной функции является мнимым и нечетным), где в некоторых вариантах входные и/или выходные данные смещены на половину выборки.

DST связано с дискретным косинусным преобразованием (DCT), которое эквивалентно DFT действительных и четных функций. См. статью DCT для общего обсуждения того, как граничные условия связывают различные типы DCT и DST. Как правило, DST выводится из DCT путем замены условия Неймана при x = 0 на условие Дирихле . ^[1] И DCT, и DST были описаны Насиром Ахмедом , Т. Натараджаном и К. Р. Рао в 1974 году. ^{[2] [3]} DST типа I (DST-I) был позже описан Анилом К. Джайном в 1976 году, а DST типа II (DST-II) был затем описан Х. Б. Кекрой и Дж. К. Соланкой в ​​1978 году. ^[4]

Приложения

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

Неофициальный обзор

Иллюстрация неявных четных/нечетных расширений входных данных DST для N =9 точек данных (красные точки) для четырех наиболее распространенных типов DST (типы I–IV).

Как и любое преобразование Фурье, дискретные синусоидальные преобразования (ДСП) выражают функцию или сигнал в виде суммы синусоид с различными частотами и амплитудами . Как и дискретное преобразование Фурье (ДПФ), ДСП работает с функцией в конечном числе дискретных точек данных. Очевидное различие между ДСП и ДПФ заключается в том, что первое использует только синусоидальные функции , тогда как второе использует как косинусы, так и синусы (в форме комплексных экспонент ). Однако это видимое различие является всего лишь следствием более глубокого различия: ДСП подразумевает иные граничные условия, чем ДПФ или другие связанные преобразования.

Преобразования Фурье, которые работают с функцией в конечной области , такие как DFT или DST или ряд Фурье , можно рассматривать как неявно определяющие расширение этой функции за пределы области. То есть, как только вы записываете функцию как сумму синусоид, вы можете вычислить эту сумму в любой , даже для , где оригинал не был указан. DFT, как и ряд Фурье, подразумевает периодическое расширение исходной функции. DST, как и синусное преобразование , подразумевает нечетное расширение исходной функции. ${\displaystyle f(x)}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle f(x)}$

Однако, поскольку DST работают с конечными дискретными последовательностями , возникают две проблемы, которые не применимы к непрерывному синусоидальному преобразованию. Во-первых, необходимо указать, является ли функция четной или нечетной как на левой, так и на правой границе домена (т. е. на границах min- n и max- n в определениях ниже соответственно). Во-вторых, необходимо указать, вокруг какой точки функция является четной или нечетной. В частности, рассмотрим последовательность ( a , b , c ) из трех равноотстоящих точек данных и скажем, что мы указываем нечетную левую границу. Есть две разумные возможности: либо данные нечетны относительно точки, предшествующей a , в этом случае нечетное расширение равно (− c ,− b ,− a , 0, a , b , c ), либо данные нечетны относительно точки на полпути между a и предыдущей точкой, в этом случае нечетное расширение равно (− c ,− b ,− a , a , b , c ).

Эти выборы приводят ко всем стандартным вариациям DST, а также к дискретным косинусным преобразованиям (DCT). Каждая граница может быть как четной, так и нечетной (2 выбора на границу) и может быть симметричной относительно точки данных или точки на полпути между двумя точками данных (2 выбора на границу), для общего числа возможностей. Половина этих возможностей, те, где левая граница нечетная, соответствуют 8 типам DST; другая половина — 8 типам DCT. ${\displaystyle 2\times 2\times 2\times 2=16}$

Эти различные граничные условия сильно влияют на применение преобразования и приводят к уникальным полезным свойствам для различных типов DCT. Наиболее непосредственно, при использовании преобразований Фурье для решения уравнений в частных производных спектральными методами , граничные условия напрямую указываются как часть решаемой задачи.

Определение

Формально дискретное синусное преобразование представляет собой линейную обратимую функцию F  : RN -> RN (где R обозначает множество действительных чисел ) или, что эквивалентно, квадратную матрицу N × N. Существует несколько вариантов DST с немного измененными определениями. N ^{действительных} чисел ^x ₀ ,..., x _{N − 1} преобразуются в N действительных чисел X ₀ ,..., X _{N − 1} по одной из формул:

ДСТ-I

Дискретное синусоидальное преобразование (https://www.desmos.com/calculator/r0od93dfgp).

${\displaystyle {\begin{aligned}X_{k}&=\sum _{n=0}^{N-1}x_{n}\sin \left[{\frac {\pi }{N+1}}(n+1)(k+1)\right]&k&=0,\dots ,N-1\\X_{k-1}&=\sum _{n=1}^{N}x_{n-1}\sin \left[{\frac {\pi nk}{N+1}}\right]&k&=1,\dots ,N\end{aligned}}}$

Матрица DST-I является ортогональной (с точностью до масштабного коэффициента).

DST-I в точности эквивалентно DFT действительной последовательности, которая нечетна вокруг нулевой и средней точек, масштабированной на 1/2. Например, DST-I из N =3 действительных чисел ( a , b , c ) в точности эквивалентно DFT из восьми действительных чисел (0, a , b , c , 0,− c ,− b ,− a ) (нечетная симметрия), масштабированной на 1/2. (В отличие от этого, типы DST II–IV включают сдвиг на половину выборки в эквивалентном DFT.) Это причина N  + 1 в знаменателе синусоидальной функции: эквивалентное DFT имеет 2( N +1) точек и имеет 2π/2( N +1) в своей частоте синусоиды, поэтому DST-I имеет π/( N +1) в своей частоте.

Таким образом, DST-I соответствует граничным условиям: x _n нечетно вблизи n  = −1 и нечетно вблизи n = N ; аналогично для X _k .

ДСТ-II

$${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}\sin \left[{\frac {\pi }{N}}\left(n+{\frac {1}{2}}\right)(k+1)\right]\quad \quad k=0,\dots ,N-1}$$

Некоторые авторы дополнительно умножают член X _{N − 1} на 1/ √ 2 (см. ниже соответствующее изменение в DST-III). Это делает матрицу DST-II ортогональной (с точностью до масштабного коэффициента), но нарушает прямое соответствие с действительно-нечетным DFT полусмещенного входа.

DST-II подразумевает граничные условия: x _n нечетно около n  = −1/2 и нечетно около n  =  N  − 1/2; X _k нечетно около k  = −1 и четно около k  =  N  − 1.

ДСТ-III

$${\displaystyle X_{k}={\frac {(-1)^{k}}{2}}x_{N-1}+\sum _{n=0}^{N-2}x_{n}\sin \left[{\frac {\pi }{N}}(n+1)\left(k+{\frac {1}{2}}\right)\right]\quad \quad k=0,\dots ,N-1}$$

Некоторые авторы дополнительно умножают член x _{N − 1} на √ 2 (см. выше соответствующее изменение в DST-II). Это делает матрицу DST-III ортогональной (с точностью до масштабного коэффициента), но нарушает прямое соответствие с действительно-нечетным DFT полусмещенного выхода.

DST-III подразумевает граничные условия: x _n нечетно около n  = −1 и четно около n  =  N  − 1; X _k нечетно около k  = −1/2 и нечетно около k  =  N  − 1/2.

ДСТ-IV

$${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}\sin \left[{\frac {\pi }{N}}\left(n+{\frac {1}{2}}\right)\left(k+{\frac {1}{2}}\right)\right]\quad \quad k=0,\dots ,N-1}$$

Матрица DST-IV является ортогональной (с точностью до масштабного коэффициента).

DST-IV подразумевает граничные условия: x _n нечетно около n  = −1/2 и четно около n  =  N  − 1/2; аналогично для X _k .

Летнее время V–VIII

Типы DST I–IV эквивалентны вещественно-нечетным DFT четного порядка. В принципе, на самом деле существует четыре дополнительных типа дискретного синусного преобразования (Martucci, 1994), соответствующих вещественно-нечетным DFT логически нечетного порядка, которые имеют множители N +1/2 в знаменателях аргументов синуса. Однако эти варианты, по-видимому, редко используются на практике.

Обратные преобразования

Обратный DST-I — это DST-I, умноженное на 2/( N  + 1). Обратный DST-IV — это DST-IV, умноженное на 2/ N . Обратный DST-II — это DST-III, умноженное на 2/ N (и наоборот).

Что касается DFT , нормировочный фактор перед этими определениями преобразований является просто соглашением и отличается в зависимости от обработки. Например, некоторые авторы умножают преобразования на так, чтобы обратное преобразование не требовало никакого дополнительного мультипликативного фактора. ${\textstyle {\sqrt {2/N}}}$

Вычисление

Хотя прямое применение этих формул потребовало бы O( N ² ) операций, можно вычислить то же самое со сложностью всего лишь O( N log N ) путем факторизации вычисления, аналогичного быстрому преобразованию Фурье (БПФ). (Можно также вычислить DST с помощью БПФ в сочетании с O( N ) этапами предварительной и последующей обработки.)

DST-III или DST-IV можно вычислить из DCT-III или DCT-IV (см. дискретное косинусное преобразование ), соответственно, путем изменения порядка входов и знака каждого другого выхода, и наоборот для DST-II из DCT-II. Таким образом, следует, что типы II–IV DST требуют точно такого же количества арифметических операций (сложений и умножений), как и соответствующие типы DCT.

Обобщения

Существует семейство преобразований, состоящее из синусоидальных и синусоидальных гиперболических функций; эти преобразования производятся на основе собственных колебаний тонких квадратных пластин с различными граничными условиями . ^[5]

Ссылки

1. Британак, Владимир; Йип, Патрик К.; Рао, КР (2010). Дискретные косинусные и синусные преобразования: общие свойства, быстрые алгоритмы и целочисленные приближения. Elsevier . стр. 35–6. ISBN 9780080464640.
2. Ахмед, Насир ; Натараджан, Т.; Рао, КР (январь 1974 г.), «Дискретное косинусное преобразование» (PDF) , IEEE Transactions on Computers , C-23 (1): 90–93, doi :10.1109/TC.1974.223784, S2CID  149806273
3. Ахмед, Насир (январь 1991 г.). «Как я придумал дискретное косинусное преобразование». Цифровая обработка сигналов . 1 (1): 4–5. doi :10.1016/1051-2004(91)90086-Z.
4. Дхамиджа, Свати; Джейн, Приянка (сентябрь 2011 г.). «Сравнительный анализ дискретного синусоидального преобразования как подходящего метода оценки шума». International Journal of Computer Science . 8 (5): 162–164 . Получено 4 ноября 2019 г. – через ResearchGate.
5. Абеди, М.; Сан, Б.; Чжэн, З. (июль 2019 г.). «Синусоидально-гиперболическое семейство преобразований с потенциальными применениями в компрессионном измерении». Труды IEEE по обработке изображений . 28 (7): 3571–3583. Bibcode : 2019ITIP...28.3571A. doi : 10.1109/TIP.2019.2912355. PMID  31071031. S2CID  174820107.

Библиография

• SA Martucci, «Симметричная свертка и дискретные синусные и косинусные преобразования», IEEE Trans. Signal Process. SP-42 , 1038–1051 (1994).
• Маттео Фриго и Стивен Г. Джонсон : FFTW , домашняя страница FFTW. Бесплатная ( GPL ) библиотека C, которая может вычислять быстрые DST (типы I–IV) в одном или нескольких измерениях произвольного размера. Также М. Фриго и С. Г. Джонсон, «Проектирование и реализация FFTW3», Труды IEEE 93 (2), 216–231 (2005).
• Такуя Оура: Пакет БПФ общего назначения, Пакет БПФ 1-мерный / 2-мерный. Бесплатные библиотеки C и FORTRAN для вычисления быстрых DST в одном, двух или трех измерениях, размеры степени 2.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), «Раздел 12.4.1. Синусоидальное преобразование», Numerical Recipes: The Art of Scientific Computing (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN 978-0-521-88068-8, заархивировано из оригинала 2011-08-11 , извлечено 2011-08-13.
• Р. Чивукула и Я. Резник, «Быстрое вычисление дискретных косинусных и синусных преобразований типов VI и VII», Труды SPIE, том 8135, 2011.