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

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

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

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

Приложения [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

Матрица 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 включают сдвиг на половину выборки в эквивалентном ДПФ.) Это причина 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 и четно около 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.

DST-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 [ править ]

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

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

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

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

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

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

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

SA Martucci, "Симметричная свертка и дискретные синусоидальные и косинусные преобразования", IEEE Trans. Сигнальный процесс. СП-42 , 1038–1051 (1994).
Маттео Фриго и Стивен Джонсон : FFTW , http://www.fftw.org/ . Бесплатная ( GPL ) библиотека C, которая может вычислять быстрые DST (типы I – IV) в одном или нескольких измерениях произвольного размера. Также М. Фриго и С. Г. Джонсон, « Разработка и реализация FFTW3 », Протоколы IEEE 93 (2), 216–231 (2005).
Такуя Оура: Универсальный пакет БПФ, http://www.kurims.kyoto-u.ac.jp/~ooura/fft.html . Бесплатные библиотеки C и FORTRAN для вычисления быстрых DST в одном, двух или трех измерениях, мощность двух размеров.
Нажмите, WH; Теукольский, С.А. Феттерлинг, Вашингтон; Фланнери, BP (2007), «Раздел 12.4.1. Синусоидальное преобразование» , Численные рецепты: Искусство научных вычислений (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN 978-0-521-88068-8.
Р. Чивукула и Ю. Резник, " Быстрое вычисление дискретных косинусных и синусоидальных преобразований типов VI и VII ", Proc. SPIE Vol. 8135, 2011.

[1] Abedi, M .; Вс, В .; Чжэн, З. (июль 2019 г.). «Синусоидально-гиперболическое семейство преобразований с потенциальными приложениями при измерении сжатия». IEEE Transactions по обработке изображений . 28 (7): 3571–3583. Bibcode : 2019ITIP ... 28.3571A . DOI : 10.1109 / TIP.2019.2912355 . PMID 31071031 .

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

[pubDCT-3] Ахмед, Насир ; Натараджан, Т .; Рао, KR (январь 1974), "дискретного косинусного преобразования" (PDF) , IEEE Transactions на компьютерах , C-23 (1): 90-93, DOI : 10,1109 / TC.1974.223784

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

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

[1]