短時距傅立葉變換

短時距傅立葉變換或Time-dependent Fourier transform，用於決定隨時間變化的訊號區域性部分的正弦頻率和相位。實際上，計算短時距傅立葉變換的過程是將長時間訊號分成數個較短的等長訊號，然後再分別計算每個較短段的傅立葉轉換。通常拿來描繪頻域與時域上的變化，為時頻分析中其中一個重要的工具。與傅立葉轉換在概念上的區別.將訊號做傅立葉變換後得到的結果，並不能給予關於訊號頻率隨時間改變的任何資訊。以下的例子作為說明：formula_1傅立葉變換後的頻譜和短時距傅立葉轉換後的結果如下：由上圖可發現，傅立葉轉換只提供了有哪些頻率成份的資訊，卻沒有提供時間資訊；而短時傅立葉轉換則清楚的提供這兩種資訊。這種時頻分析的方法有利於頻率會隨著時間改變的訊號，如音樂訊號和語音訊號等分析。定義.連續短時傅立葉轉換.簡單來說，在連續時間的例子，一個函式可以先乘上僅在一段時間不為零的窗函式再進行一維的傅立葉變換。再將這個窗函式沿著時間軸挪移，所得到一系列的傅立葉變換結果排開則成為二維表象。數學上，這樣的操作可寫為：formula_2另外也可用角頻率來表示：formula_3其中formula_4是窗函式，窗函式種類有很多種，會在稍後再做仔細討論。formula_5是待變換的訊號。formula_6是formula_7的傅立葉變換。 隨著formula_8的改變，窗函式在時間軸上會有位移。經formula_7後，訊號只留下了窗函式擷取的部分做最後的傅立葉轉換，所得到的結果為一複數函式，代表著訊號隨時間與頻率變化的大小與相位。離散短時傅立葉轉換.在離散時間的例子，資料會被切割成數個大量的幀，而每組幀通常會互相重疊，避免因切割方式造成邊界的誤差。而每組幀在各自進行傅立葉轉換後所得的複數結果會再進行相加，可得到每個點時間與頻率變化的大小與相位。數學上，這樣的操作可寫為：formula_10相同地，其中formula_11是窗函式，formula_12是待變換的訊號。在這個例子裡，m是離散的且ω是連續的，但大部分實際的應用當中，短時距傅立葉轉換在電腦中都是以快速傅立葉轉換進行計算(見實現方法的快速傅立葉變換)，而此時這兩個引數都是離散且被量化的。Sliding 離散傅立葉轉換.當只想要得知特定少數的ω，或是短時距傅立葉轉換每次窗函式移動m的值，則短時距傅立葉轉換可以利用sliding DFT演演算法更有效地計算出來。反短時距傅立葉轉換.短時距傅立葉轉換是可逆的，也就是說原本的訊號可以藉由反短時距傅立葉轉換將短時距傅立葉轉換後的訊號還原。其中最廣為接受的反短時距傅立葉轉換方法是重疊-相加之摺積法，此方法也促成了更多樣的訊號處理方法。反短時距傅立葉轉換，其數學類似傅立葉轉換，但須消除窗函式的作用，首先必須先將窗函式的總面積規模化使得formula_13而從上也可輕易地得出formula_14和formula_15連續傅立葉轉換公式如下：formula_16將formula_5進行上述的替換：formula_18formula_19將積分順序進行交換：formula_20formula_21formula_22因此傅立葉轉換可以視為某種將formula_5所有的短時距傅立葉轉換的相位同調部分進行相加。而反傅立葉轉換公式如下：formula_24因此 formula_5可以從formula_26被復原formula_27或formula_28與上面所列的窗函式的式子進行比較，可得formula_29對反傅立葉轉換公式中的formula_26來說formula_31是不變的formula_32另外用角頻率來表示：formula_33窗函式.窗函式通常滿足下列特性:常見的窗函式有：方形、三角形、高斯函式等，而短時距傅立葉轉換也因窗函式的不同而有不同的名稱。而加伯轉換，即為窗函式是高斯函式的短時距傅立葉轉換，通常沒有特別說明的短時距傅立葉轉換，即為加伯轉換。非對稱窗函式.當在特殊應用時，窗函式特性的第一點可以不滿足，如下圖的非對稱窗函式formula_38，其中formula_39。左圖為窗函式原本的圖形，而在計算短時距傅立葉變換時，需將窗函式轉到formula_31軸上得出formula_41，換言之，欲得到的短時距傅立葉變換的結果需在formula_42的時間點才能算出，因此若formula_43愈小，即可愈快得結果，此種非對稱窗函式可應用在地震波、碰撞偵測...等，需要即時處理的應用。方形窗函式的短時距傅立葉轉換.概念.右圖即為方形窗函式的一個例子，其數學定義：formula_44可以隨要分析的訊號，來調整B的大小。至於B的選擇，將會在下面探討。短時傅立葉轉換可以簡化為formula_45反短時傅立葉轉換可簡化為formula_46特性.其大部分的特性都與傅立葉轉換的特性相對應formula_47formula_48formula_49若有一訊號formula_50，formula_51分別為formula_52做方形窗函式短時 距傅立葉轉換的結果，則formula_53。formula_54formula_551. 當formula_56，formula_572. 當formula_58，formula_59formula_75方形窗函式寬度formula_60的選取.結果如右圖所示，B越大則在頻率變化處(t = 10, 20)附近的頻率越不準確，即可能會有多個頻率成分出現。但同時，其他時間點的能量則較集中；沒有如B較小時，頻率散開或模糊的情形。上述也是其中一個小波轉換及多解析度分析作為改進的方向，其中多解析度分析能在高頻時有較好的時間軸解析，而在低頻時能有較好的頻率軸解析，此種組合較契合許多實際的應用。時間軸與頻率軸的解析度無法同時提升也與海森堡不確定性原理有關，即時間與頻率的標準差乘積有所限制，而高斯函式恰好能符合不確定性原理的極值，也就是兩者同時達到最好的解析度，而應用高斯函式的時頻分析方法即為加伯轉換，而在經過修改及多解析度分析後，成為了莫萊小波。其他窗函式.高斯窗函式.概念.高斯窗函式的短時距傅立葉轉換又稱為加伯轉換。以下是高斯函式的數學定義，formula_76據此，短時傅立葉轉換可以寫為formula_77三角形窗函式.概念.三角形窗函式如右圖所示，數學定義如下，formula_78formula_79可使用在震幅改變的情況下，相對於方形窗函式，可更好的濾除雜訊。海寧(Hanning/ Hann)窗函式.概念.海寧函式如右圖所示，數學定義如下，formula_80相較於三角形窗函式，海寧窗函式更為貼近現實訊號的趨勢，可進一步濾除雜訊。漢明(Hamming)窗函式.概念.漢明窗函如右圖所示，數學定義如下，formula_81跟海寧窗函式類似，但兩端不為零。海寧與漢明窗的區別.窗函式有四個指標，分別為因為漢明窗兩端不能到零，而海寧窗兩端為零。從以上頻率響應來看，漢明窗可以有效減少靠近的旁辦，但在較遠的旁辦洩漏比海寧窗嚴重。如何決定窗函式.可根據以下條件來選取窗函式，在決定複雜度跟解析率後，可利用不同的窗函式達到更好的濾雜訊效果。瑞利頻率.當Nyquist頻率是能被有意義分析的頻率最大值的限制，而瑞利頻率則是能被有限頻寬頻的窗函式解析的頻率最小值的限制。若給定一窗函式的長度是T秒，最低能被解析的頻率即為1/T Hz。瑞利頻率在短時距傅立葉變化的應用中扮演重要的角色，像是在分析神經訊號時。頻譜(Spectrogram).Spectrogram即短時傅立葉轉換後結果的絕對值平方，兩者本質上是相同的，在也常出現spectrogram這個名詞。formula_82應用.短時距傅立葉變換及其他工具經常用於分析音樂。如右圖所示，音訊工程師使用這種視覺來獲取有關音訊樣本的資訊。此外，因頻率會隨時間而改變，短時距也可使用在以下情境，若與時間無關，如卷積，照片等則不能使用短時距傅立葉變換來進行分析。而影片屬於3D訊號，其短時距傅立葉產物為6D訊號，故也不適用。短時距傅立葉變換實現方法.從連續短時距傅立葉變化的定義出發formula_83令 formula_84 ，則上述式子時域可從連續轉為離散formula_85若當formula_86上式可改寫為formula_87直接運算.限制條件.(1)要滿足Nyquist criterionformula_88formula_89的頻寬為formula_90。而formula_91的頻寬則為formula_92，formula_93的頻寬也為formula_92因為在時域相乘相當於在頻域做摺積，因此formula_95的頻寬為formula_96(通常formula_97會遠大於formula_98，所以主要影響頻寬的是formula_97)formula_100轉換到離散形式(formula_101)，其中formula_102formula_103，由於無限大的上下限實務上做不到，所以嘗試變成有限大的上下限。假設formula_104 for formula_105formula_106formula_108假設t-axis有T個取樣點，f-axis有F個取樣點，則我們總共要對TF個點做formula_109次的運算，因此可得複雜度為formula_110優點：簡單及有彈性(因為限制少)缺點：複雜度較高快速傅立葉變換.限制條件.(1)要滿足Nyquist criterionformula_111推導.標準的離散傅立葉轉換式子為formula_114由直接運算得知如下公式formula_115因此為了讓上式符合離散傅立葉轉換的上下界，令formula_116代入上式即可得formula_117其中formula_118運算步驟.假設formula_119formula_120步驟一：計算formula_121步驟二：formula_122步驟三：決定formula_123步驟四：formula_124步驟五：轉換formula_125成formula_126步驟六：設formula_127，並回到步驟三，直到formula_128formula_129藉由取樣定理可得知formula_130假設formula_131及formula_132，則經由formula_133可得formula_134formula_135及formula_136，則經由formula_137可得formula_138步驟一：formula_139步驟二：formula_140步驟三：計算formula_141步驟四：利用求得的formula_123計算快速傅立葉轉換formula_143步驟五：轉換formula_125到formula_126formula_146formula_148因此可將上式改為formula_149，其中formula_150代表取m除以N的餘數步驟六：設定formula_127，回到步驟三直到formula_152時間複雜度.利用FFT計算formula_153，其中每次FFT的時間複雜度為formula_154總時間複雜度為formula_155優缺點.優點：與直接運算相比，複雜度較低缺點：較多限制，包括formula_156使用快速傅立葉變換加上遞迴關係式.限制條件.(1)要滿足Nyquist criterionformula_157(2)formula_112(3)formula_113(4)需為方形窗函式的短時距傅立葉轉換推導.因為是方形窗函式formula_160，因此原式可由此關係變成以下式子formula_161而由此可看出n和n-1有遞迴關係，如下formula_162(1)以FFT計算formula_163其中formula_164(2)利用遞迴關係式計算算formula_165則formula_166時間複雜度.(1)FFT計算一次formula_163(2)利用遞迴關係，計算formula_169時的數值，因此共會執行T-1次遞迴，如下式formula_166每次遞迴都要計算formula_171及formula_172兩個乘法(相當於2F的複雜度)總時間複雜度 formula_174優缺點.優點：四種運算中，最低的複雜度formula_175缺點：使用Chirp-Z 轉換.限制條件.(1)要滿足Nyquist criterionformula_157推導.令formula_177即可由直接運算的式子匯出Chirp_Z變換的式子，如下所示formula_178運算步驟.Step1:formula_179 formula_180Step2:formula_181Step3:formula_182時間複雜度.當n為定值時(1)假設formula_183 相乘時間複雜度為2Q+1(2)令formula_184，則formula_185 convolution時間複雜度為 formula_186(3)formula_187相乘時間複雜度為 F因此，總時間複雜度為formula_188雖然此實現方法和使用FFT計算的時間複雜度相同，但因為convolution相當於做三次FFT，因此實際操作時運算時間約為使用FFT計算的2~3倍優缺點.優點：只有一項限制：formula_189缺點：與前四種相比，複雜度是中間的。Unbalanced Sampling for STFT and WDF.將直接法和快速傅立葉轉換方法做修正1.直接法.formula_100修正後 ：formula_191其中， formula_192 ,formula_193假設formula_194 for formula_195，則上下限可藉由以下推導而修正formula_196則上限可以寫成formula_197，下限則以此類推註：formula_198(輸入訊號的取樣間隔)formula_199(在t軸上的輸出訊號的取樣間隔)然而，formula_200是整數會是比較好的。formula_201則經由上述公式可求得S=441，代表經由unbalanced sampling，我們跟原本formula_202相比可減少441倍的取樣點。時間複雜度.由於t軸的取樣點少了S倍，因此跟原本的直接運算複雜度相比，只要把formula_203即可，如下：複雜度：formula_2042.快速傅立葉轉換.限制條件.(1) formula_205(3) formula_208，formula_209的頻寬是 formula_210i.e. formula_211 ，當 formula_212過程.formula_213令 formula_214formula_215 for formula_216formula_217for formula_218修正後：formula_219運算步驟.假設formula_220formula_221formula_222步驟一：計算formula_223步驟二：formula_224步驟三：決定formula_123步驟四：formula_124步驟五：轉換formula_227步驟六：設定formula_127及返回步驟三，直到formula_229複雜度.formula_204Non-Uniform formula_199.(1) 先用比較大的formula_199(2) 如果發現formula_233 和 formula_234 之間有很大的差異，則在formula_235，formula_236 之間選用比較小的取樣區間formula_237再用Unbalanced Sampling for STFT and WDF 中修正後的快速傅立葉轉換方法算出 formula_241，formula_242formula_243(3) 以此類推，如果 formula_244的差距還是太大，則再選用更小的取樣間隔formula_245若有一音樂訊號總共有1.6秒，formula_249formula_254，共29點可以這樣做的原因為：有些音樂訊號在和絃與和絃中間幾乎沒有變化，因此可以挑選較大的formula_199取樣;和絃在變換時，頻率會變化的較劇烈，因此變換和絃是需要用較多的取樣點。藉由此種non-uniform的取樣，可以讓我們大幅減少運算量，從最一開始的formula_256可看出我們的運算量大幅降低。