小波變換和motion信號處理：第一篇

這是《小波變換和motion信號處理》系列的第一篇，基礎普及。第二篇我準備寫(xiě)深入小波的東西，第三篇講解應用。

記得我還在大四的時(shí)候，在申請出國和保研中猶豫了好一陣，骨子里的保守最后讓我選擇了先保研。當然后來(lái)也退學(xué)了，不過(guò)這是后話(huà)。當時(shí)保研就要找老板，實(shí)驗室，自己運氣還不錯，進(jìn)了一個(gè)在本校很牛逼的實(shí)驗室干活路。我們實(shí)驗室主要是搞圖像的，實(shí)力在全國也是很強的，進(jìn)去后和師兄師姐聊，大家都在搞什么小波變換，H264之類(lèi)的。當時(shí)的我心思都不在這方面，盡搞什么操作系統移植，ARM+FPGA這些東西了。對小波變換的認識也就停留在神秘的“圖像視頻壓縮算法之王”上面。

后來(lái)我才發(fā)現，在別的很廣泛的領(lǐng)域中，小波也逐漸開(kāi)始流行。比如話(huà)說(shuō)很早以前，我們接觸的信號頻域處理基本都是傅立葉和拉普拉斯的天下。但這些年，小波在信號分析中的逐漸興盛和普及。這讓人不得不感到好奇，是什么特性讓它在圖象壓縮，信號處理這些關(guān)鍵應用中更得到信賴(lài)呢?說(shuō)實(shí)話(huà)，我還在國內的時(shí)候，就開(kāi)始好奇這個(gè)問(wèn)題了，于是放狗搜，放毒搜，找遍了中文講小波變換的科普文章，發(fā)現沒(méi)幾個(gè)講得清楚的，當時(shí)好奇心沒(méi)那么重，也不是搞這個(gè)研究的，懶得找英文大部頭論文了，于是作罷。后來(lái)來(lái)了這邊，有些項目要用信號處理，不得已接觸到一些小波變換的東西，才開(kāi)始硬著(zhù)頭皮看?？戳艘恍┎牧?，聽(tīng)了一些課，才發(fā)現，還是那個(gè)老生常談的論調：國外的技術(shù)資料和國內真TNND不是一個(gè)檔次的。同樣的事情，別人說(shuō)得很清楚，連我這種并不聰明的人也看得懂; 國內的材料則繞來(lái)繞去講得一塌糊涂，除了少數天才沒(méi)幾個(gè)人能在短時(shí)間掌握的。

牢騷就不繼續發(fā)揮了。在這個(gè)系列文章里，我希望能簡(jiǎn)單介紹一下小波變換，它和傅立葉變換的比較，以及它在移動(dòng)平臺做motion detection的應用。如果不做特殊說(shuō)明，均以離散小波為例子?？紤]到我以前看中文資料的痛苦程度，我會(huì )盡量用簡(jiǎn)單，但是直觀(guān)的方式去介紹。有些必要的公式是不能少的，但我盡量少用公式，多用圖。另外，我不是一個(gè)好的翻譯者，所以對于某些實(shí)在翻譯不清楚的術(shù)語(yǔ)，我就會(huì )直接用英語(yǔ)。我并不claim我會(huì )把整個(gè)小波變換講清楚，這是不可能的事，我只能盡力去圍繞要點(diǎn)展開(kāi)，比如小波變換相對傅立葉變換的好處，這些好處的原因是什么，小波變換的幾個(gè)根本性質(zhì)是什么，背后的推導是什么。我希望達到的目的就是一個(gè)小波變換的初學(xué)者在看完這個(gè)系列之后，就能用matlab或者別的工具對信號做小波變換的基本分析并且知道這個(gè)分析大概是怎么回事。

最后說(shuō)明，我不是研究信號處理的專(zhuān)業(yè)人士，所以文中必有疏漏或者錯誤，如發(fā)現還請不吝賜教。

要講小波變換，我們必須了解傅立葉變換。要了解傅立葉變換，我們先要弄清楚什么是”變換“。很多處理，不管是壓縮也好，濾波也好，圖形處理也好，本質(zhì)都是變換。變換的是什么東西呢?是基，也就是basis。如果你暫時(shí)有些遺忘了basis的定義，那么簡(jiǎn)單說(shuō)，在線(xiàn)性代數里，basis是指空間里一系列線(xiàn)性獨立的向量，而這個(gè)空間里的任何其他向量，都可以由這些個(gè)向量的線(xiàn)性組合來(lái)表示。那basis在變換里面啥用呢?比如說(shuō)吧，傅立葉展開(kāi)的本質(zhì)，就是把一個(gè)空間中的信號用該空間的某個(gè)basis的線(xiàn)性組合表示出來(lái)，要這樣表示的原因，是因為傅立葉變換的本質(zhì)，是。小波變換自然也不例外的和basis有關(guān)了。再比如你用Photoshop去處理圖像，里面的圖像拉伸，反轉，等等一系列操作，都是和basis的改變有關(guān)。

既然這些變換都是在搞基，那我們自然就容易想到，這個(gè)basis的選取非常重要，因為basis的特點(diǎn)決定了具體的計算過(guò)程。一個(gè)空間中可能有很多種形式的basis，什么樣的basis比較好，很大程度上取決于這個(gè)basis服務(wù)于什么應用。比如如果我們希望選取有利于壓縮的話(huà)，那么就希望這個(gè)basis能用其中很少的向量來(lái)最大程度地表示信號，這樣即使把別的向量給砍了，信號也不會(huì )損失很多。而如果是圖形處理中常見(jiàn)的線(xiàn)性變換，最省計算量的完美basis就是eigenvector basis了，因為此時(shí)變換矩陣T對它們的作用等同于對角矩陣( Tv_n = av_n，a是eigenvalue )?？偟膩?lái)說(shuō)，拋開(kāi)具體的應用不談，所有的basis，我們都希望它們有一個(gè)共同的特點(diǎn)，那就是，容易計算，用最簡(jiǎn)單的方式呈現最多的信號特性。

好，現在我們對變換有了基本的認識，知道他們其實(shí)就是在搞基。當然，搞基也是分形式的，不同的變換，搞基的妙處各有不同。接下來(lái)先看看，傅立葉變換是在干嘛。

傅立葉級數最早是Joseph Fourier 這個(gè)人提出的，他發(fā)現，這個(gè)basis不僅僅存在與vector space，還存在于function space。這個(gè)function space本質(zhì)上還是一個(gè)linear vector space，可以是有限的，可以是無(wú)限的，只不過(guò)在這個(gè)空間里，vector就是function了，而對應的標量就是實(shí)數或者復數。在vector space里，你有vector v可以寫(xiě)成vector basis的線(xiàn)性組合，那在function space里，function f(x)也可以寫(xiě)成對應function basis的線(xiàn)性組合，也有norm。你的vector basis可以是正交的，我的function basis也可以是正交的(比如sin(t)和sin(2t))。唯一不同的是，我的function basis是無(wú)窮盡的，因為我的function space的維度是無(wú)窮的。好，具體來(lái)說(shuō)，那就是現在我們有一個(gè)函數，f(x)。我們希望將它寫(xiě)成一些cos函數和一些sin函數的形式，像這樣

again，這是一個(gè)無(wú)限循環(huán)的函數。其中的1，cosx, sinx, cos2x …..這些，就是傅立葉級數。傅立葉級數應用如此廣泛的主要原因之一，就是它們這幫子function basis是正交的，這就是有趣的地方了。為什么function basis正交如此重要呢?我們說(shuō)兩個(gè)vector正交，那就是他倆的內積為0。那對于function basis呢?function basis怎么求內積呢?

現在先復習一下vector正交的定義。我們說(shuō)兩個(gè)vector v,w如果正交的話(huà)，應符合：

那什么是function正交呢?假設我們有兩個(gè)函數f(x)和g(x)，那是什么?我們遵循vector的思路去想，兩個(gè)vector求內積，就是把他們相同位置上對應的點(diǎn)的乘積做一個(gè)累加。那移過(guò)來(lái)，就是對每一個(gè)x點(diǎn)，對應的f和g做乘積，再累加。不過(guò)問(wèn)題是，f和g都是無(wú)限函數阿，x又是一個(gè)連續的值。怎么辦呢?向量是離散的，所以累加，函數是連續的，那就是…….積分!

我們知道函數內積是這樣算的了，自然也就容易證明，按照這個(gè)形式去寫(xiě)的傅立葉展開(kāi)，這些級數確實(shí)都是兩兩正交的。證明過(guò)程這里就不展開(kāi)了。好，下一個(gè)問(wèn)題就是，為什么它們是正交basis如此重要呢?這就牽涉到系數的求解了。我們研究了函數f，研究了級數，一堆三角函數和常數1，那系數呢?a0, a1, a2這些系數該怎么確定呢?好，比如我這里準備求a1了。我現在知道什么?信號f(x)是已知的，傅立葉級數是已知的，我們怎么求a1呢?很簡(jiǎn)單，把方程兩端的所有部分都求和cosx的內積，即：

然后我們發(fā)現，因為正交的性質(zhì)，右邊所有非a1項全部消失了，因為他們和cosx的內積都是0!所有就簡(jiǎn)化為

這樣，a1就求解出來(lái)了。到這里，你就看出正交的奇妙性了吧:)

好，現在我們知道，傅立葉變換就是用一系列三角波來(lái)表示信號方程的展開(kāi)，這個(gè)信號可以是連續的，可以是離散的。傅立葉所用的function basis是專(zhuān)門(mén)挑選的，是正交的，是利于計算coefficients的。但千萬(wàn)別誤解為展開(kāi)變換所用的basis都是正交的，這完全取決于具體的使用需求，比如泰勒展開(kāi)的basis就只是簡(jiǎn)單的非正交多項式。

有了傅立葉變換的基礎，接下來(lái)，我們就看看什么是小波變換。首先來(lái)說(shuō)說(shuō)什么是小波。所謂波，就是在時(shí)間域或者空間域的震蕩方程，比如正弦波，就是一種波。什么是波分析?針對波的分析拉(囧)。并不是說(shuō)小波分析才屬于波分析，傅立葉分析也是波分析，因為正弦波也是一種波嘛。那什么是小波呢?這個(gè)”小“，是針對傅立葉波而言的。傅立葉所用的波是什么?正弦波，這玩意以有著(zhù)無(wú)窮的能量，同樣的幅度在整個(gè)無(wú)窮大區間里面振蕩，像下面這樣：

那小波是什么呢?是一種能量在時(shí)域非常集中的波。它的能量是有限的，而且集中在某一點(diǎn)附近。比如下面這樣：

這種小波有什么好處呢?它對于分析瞬時(shí)時(shí)變信號非常有用。它有效的從信號中提取信息，通過(guò)伸縮和平移等運算功能對函數或信號進(jìn)行多尺度細化分析，解決了傅立葉變換不能解決的許多困難問(wèn)題。恩，以上就是通常情況下你能在國內網(wǎng)站上搜到的小波變換文章告訴你的。但為什么呢?這是我希望在這個(gè)系列文章中講清楚的。不過(guò)在這篇文章里，我先點(diǎn)到為止，把小波變換的重要特性以及優(yōu)點(diǎn)cover了，在下一篇文章中再具體推導這些特性。

小波變換的本質(zhì)和傅立葉變換類(lèi)似，也是用精心挑選的basis來(lái)表示信號方程。每個(gè)小波變換都會(huì )有一個(gè)mother wavelet，我們稱(chēng)之為母小波，同時(shí)還有一個(gè)scaling function，中文是尺度函數，也被成為父小波。任何小波變換的basis函數，其實(shí)就是對這個(gè)母小波和父小波縮放和平移后的集合。下面這附圖就是某種小波的示意圖：

從這里看出，這里的縮放倍數都是2的級數，平移的大小和當前其縮放的程度有關(guān)。這樣的好處是，小波的basis函數既有高頻又有低頻，同時(shí)還覆蓋了時(shí)域。對于這點(diǎn)，我們會(huì )在之后詳細闡述。

小波展開(kāi)的形式通常都是這樣(注意，這個(gè)只是近似表達，嚴謹的展開(kāi)形式請參考第二篇)：

其中的