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

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

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 соответствуют немного отличающимся нечетным/четным граничным условиям на двух концах массива.

Неофициальный обзор [ править ]

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

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

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

Однако, поскольку 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 варианта на границу), всего $2\times 2\times 2\times 2=16$ возможности. Половина этих возможностей, те, у которых левая граница нечетная, соответствуют 8 типам летнего времени; другая половина — это 8 типов DCT.

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

Определение [ править ]

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

Летнее время-I [ править ]

{\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 {nk\pi }{N+1}}\right]&k&=1,\dots ,N\end{aligned}}

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

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

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

DST-II [ править ]

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 ортогональной (с точностью до масштабного коэффициента), но нарушает прямое соответствие с действительным нечетным ДПФ полусдвинутого входного сигнала.

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

DST-III [ править ]

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 ортогональной (с точностью до масштабного коэффициента), но нарушает прямое соответствие с действительным нечетным ДПФ полусмещенного выходного сигнала.

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

Летнее время-IV [ править ]

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 .

DST V–VIII [ edit ]

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

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

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

Что касается ДПФ , коэффициент нормализации перед этими определениями преобразования является всего лишь соглашением и различается в зависимости от обработки. Например, некоторые авторы умножают преобразования на ${\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]

Ссылки [ править ]

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

Библиография [ править ]

С. А. Мартуччи, «Симметричная свертка и дискретные синусоидальные и косинусные преобразования», IEEE Trans. Сигнальный процесс. СП-42 , 1038–1051 (1994).
Маттео Фриго и Стивен Дж. Джонсон : FFTW , домашняя страница FFTW . Бесплатная ( GPL ) библиотека C, которая может вычислять быстрые DST (типы I–IV) в одном или нескольких измерениях произвольного размера. Также М. Фриго и С.Г. Джонсон, « Проектирование и реализация FFTW3 », Proceedings of the IEEE 93 (2), 216–231 (2005).
Такуя Оура: пакет БПФ общего назначения, пакет БПФ 1-Dim/2-Dim . Бесплатные библиотеки C и FORTRAN для быстрого вычисления DST в одном, двух или трех измерениях, степень двойки.
Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007), «Раздел 12.4.1. Синусоидальное преобразование» , Численные рецепты: искусство научных вычислений (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN 978-0-521-88068-8 , заархивировано из оригинала 11 августа 2011 г. , получено 13 августа 2011 г.
Р. Чивукула и Ю. Резник, « Быстрое вычисление дискретных косинусных и синусоидальных преобразований типов VI и VII », Proc. ШПИОН Том. 8135, 2011.

[[Категория:Дискретное преобразованиесреднеквадратичное значение]]

[:0-1] Jump up to: Перейти обратно: ^а ^б Британак, Владимир; Да, Патрик С.; Рао, КР (2010). Дискретные косинусные и синусоидальные преобразования: общие свойства, быстрые алгоритмы и целочисленные аппроксимации . Эльзевир . стр. 35–6. ISBN 9780080464640 .

[pubDCT-2] Ахмед, Насир ; Натараджан, Т.; Рао, КР (январь 1974 г.), «Дискретное косинусное преобразование» (PDF) , Транзакции IEEE на компьютерах , C-23 (1): 90–93, doi : 10.1109/TC.1974.223784 , S2CID 149806273

[Ahmed-3] Ахмед, Насир (январь 1991 г.). «Как я придумал дискретное косинусное преобразование» . Цифровая обработка сигналов . 1 (1): 4–5. дои : 10.1016/1051-2004(91)90086-Z .

[4] Дхамиджа, Свати; Джайн, Приянка (сентябрь 2011 г.). «Сравнительный анализ дискретного синусоидального преобразования как подходящего метода оценки шума» . Международный журнал компьютерных наук . 8 (5): 162–164 . Проверено 4 ноября 2019 г. - через ResearchGate.

[5] Абеди, М.; Сан, Б.; Чжэн, З. (июль 2019 г.). «Синусоидально-гиперболическое семейство преобразований с потенциальным применением в измерениях сжатия». Транзакции IEEE при обработке изображений . 28 (7): 3571–3583. Бибкод : 2019ITIP...28.3571A . дои : 10.1109/TIP.2019.2912355 . ПМИД 31071031 . S2CID 174820107 .

[1]

[2]

[3]

[4]

[5]