雙正交小波變換提升格式的簡化算法

分類號密級UDC編號桂林電子科技大學(xué)碩士學(xué)位論文題目基于提升小波變換的圖像壓縮方法研究（英文）TheStudyofImagecompressionarithmeticbasedonLiftingWaveletTransform研究生姓名：李輝指導(dǎo)教師姓名、職務(wù)：朱芳來教授申請學(xué)位：工學(xué)碩士學(xué)科、專業(yè)：控制理論與控制工程提交論文日期：2006年4月論文答辯日期：2006年6月 年月日獨創(chuàng)性（或創(chuàng)新性）聲明本人聲明所呈交的論文是我個人在導(dǎo)師指導(dǎo)下進行的研究工作及取得的研究成果。盡我所知，除了文中特別加以標(biāo)注和致謝中所羅列的內(nèi)容以外，論文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果；也不包含為獲得桂林電子科技大學(xué)或其它教育機構(gòu)的學(xué)位或證書而使用過的材料。與我一同工作的同志對本研究所做的任何貢獻(xiàn)均已在論文中做了明確的說明并表示了謝意。申請學(xué)位論文與資料若有不實之處，本人承擔(dān)一切相關(guān)責(zé)任。本人簽名： 日期：關(guān)于論文使用授權(quán)的說明本人完全了解桂林電子科技大學(xué)有關(guān)保留和使用學(xué)位論文的規(guī)定，即：研究生在校攻讀學(xué)位期間論文工作的知識產(chǎn)權(quán)單位屬桂林電子科技大學(xué)。本人保證畢業(yè)離校后，發(fā)表論文或使用論文工作成果時署名單位仍然為桂林電子科技大學(xué)。學(xué)校有權(quán)保留送交論文的復(fù)印件，允許查閱和借閱論文；學(xué)?？梢怨颊撐牡娜炕虿糠謨?nèi)容，可以允許采用影印、縮印或其它復(fù)制手段保存論文。（保密的論文在解密后遵守此規(guī)定）本學(xué)位論文屬于保密在____年解密后適用本授權(quán)書。本人簽名： 日期：導(dǎo)師簽名： 日期：基于提升小波變換的圖像壓縮方法研究i摘要提升算法以其通用性和靈活性及高效的實現(xiàn)方法，成為目前小波領(lǐng)域研究的熱點問題。圖像信息是人們認(rèn)識世界的主要信息來源，如何用較少的數(shù)據(jù)來表示圖像信號，是許多研究領(lǐng)域需要解決的問題。本文主要對提升格式的小波變換算法，及提升小波變換后如何進行小波系數(shù)的有效壓縮進行研究。研究結(jié)果具體如下：1)在用傳統(tǒng)的Euclidean算法對第一代小波濾波器進行提升時，發(fā)現(xiàn)并不是所有小波濾波器的提升格式都很簡單。有時經(jīng)過提升之后算法雖較之原來的第一代小波的卷積運算有所簡化，但仍然要進行效率不高的卷積運算。為了使每一步的提升或?qū)ε继嵘雍啙?，本文通過重新定義多項式帶余除法，提出了一種改進的Euclidean算法并在此基礎(chǔ)之上給出了一種提升格式的簡化算法。在該提升實現(xiàn)算法中，用簡單的數(shù)乘運算代替了原來小波變換提升實現(xiàn)算法中的卷積運算，使得算法中的核心部分——提升及對偶提升步驟的計算更加簡單直接，更加易于硬件實現(xiàn)。2)通過分析提升小波變換后各個子塊的小波系數(shù)與整個圖像變換后的小波系數(shù)之間的關(guān)系，發(fā)現(xiàn)每個子塊的子帶在整個圖像的相同子帶內(nèi)的空間位置，與子塊在原始圖像中的空間位置相同。利用該結(jié)論，很容易的實現(xiàn)小波變換及其編碼的并行處理以及ROI特殊區(qū)域編碼。3)通過引入EBCOT的子帶分塊編碼的思想，提出了一種基于提升小波變換的改進SPIHT算法。該算法不但具有傳統(tǒng)SPIHT算法的優(yōu)點，而且能實現(xiàn)碼流多分辨率表示和ROI區(qū)域編碼。試驗結(jié)果表明，該算法是綜合性能比較好的一種小波系數(shù)壓縮算法。4)基于前面的工作，給出了一種有效的基于提升小波變換的圖像壓縮系統(tǒng)。該系統(tǒng)把圖像分割成小塊后，單獨進行提升小波變換及編碼處理，并在解碼端恢復(fù)后進行重新組合。試驗結(jié)果表明該系統(tǒng)在碼流的多分辨表示和ROI區(qū)域編碼情況下的壓縮壓縮效果都比較好。關(guān)鍵字：圖像壓縮；簡化的提升格式；小波變換；SPIHT壓縮算法；Euclidean算法PAGE1AbstractBecauseofitsgenerality,flexibilityandhighimplementationefficiency,atpresent,theliftingschemehasbeenahotquestioninthefieldsofwavelet.Theimagesignalsarethemainsourceofinformationthroughwhichpeoplecanknowtheworld.Sohowtoexpresstheimagesignalsbyusinglessdatahasbeenakeyquestionmanyfieldsneedtosolve.Inthispaper,themainjobistostudythealgorithmofliftingwavelettransformandhowtocompressthewaveletcoefficientseffectively.Thestudyresultscanbesaidasfollow:1)AtthetimeofliftingthefirstgenerationwaveletfiltersbyusingthetraditionalEuclideanalgorithm,wefindnotallliftingschemeofthefiltersareverysimple.Sometimesitmustemployconvolutionoperationswithverylowimplementationefficiency,thoughthealgorithmhasbeenalittlesimplerthanbeforeafterlifting.Tomakeeachliftingordual-liftingstepsimpler,inthispaperasimplifiedliftingschemeforwavelettransformisproposedbyredefiningtheEuclideanalgorithmwithanewdivisionforLaurentpolynomials.Inthesimplifiedalgorithmtheconvolutionoperationisreplacedbysimplenumericdivisionoperation.Itmakesthekernelpartofthealgorithm(liftingandduallifting)andhardwarerealizationeasier.2)Afterliftingwavelettransform,byanalyzingtherelationsofthecoefficientsbetweeneachsonblockandthewholeimage,wecanfindtheindexpositionofthesub-bandofeachsonblockinthesamesub-bandofthewholeimageissameasthatofthesonblockintheoriginimage.Usingtheconclusion,theparallelprocessingofwavelettransformandcoding,andROIcodingcanberealizedveryeasily.3)ByintroducingtheideaoftheblockcodinginEBCOT,amodifiedSPIHTalgorithmisproposed.ThealgorithmnotonlyhasalltheadvantagesofconventionalSPIHT,butalsocanrealizebit-streamwithmulti-resolutionandROIcoding.Theexperimentresultsshowitisagoodalgorithmforwaveletcoefficientscompression.4)Onthebasisoftheworkabove,amoreefficientimagecompressionsystembasedonliftingwavelettransformisgiven.Afterdividingtheimageintoblocks,eachblockisliftingwavelettransformedandencodedlonely,andthenatthetimeofdecoding,allthedataisrecombined.Theexperimentresultsshowthesystemhasverygoodperformancetothemulti-resolutionexpressionofthebit-streamandROIcoding.Keywords:Imagecompression;CompactLiftingScheme;WaveletTransform;SPIHT;EuclideanAlgorithm.目錄摘要 iAbstract ii目錄 iii第一章緒論 1§1.1圖像壓縮編碼的必要性 1§1.2圖像壓縮編碼的可能性 2§1.3小波圖像壓縮技術(shù)研究進展 3§1.3.1小波提升技術(shù)的研究進展 3§1.3.2圖像壓縮編碼技術(shù)的研究進展 4§1.4本文研究的內(nèi)容 6第二章小波變換 8§2.1連續(xù)小波變換 8§2.2離散小波變換 9§2.3多分辨分析及Mallat算法 9§2.3.1一維正交多分辨分析及Mallat算法 10§2.3.2二維張量積多分辨分析及Mallat算法 15§2.4緊支撐雙正交小波基的構(gòu)造 20§2.5本章小結(jié) 24第三章提升小波變換的簡化實現(xiàn) 25§3.1小波分解與重構(gòu)的多相位表示 25§3.2Laurent多項式的Euclidean算法 27§3.3改進的Laurent多項式Euclidean算法 28§3.4多相位矩陣的因子分解 32§3.5小波變換的提升實現(xiàn)的傳統(tǒng)算法 36§3.6小波變換的提升實現(xiàn)的簡化算法 37§3.7提升算法舉例 39§3.8整數(shù)小波變換 43§3.9本章小結(jié) 44第四章基于提升小波變換的圖像壓縮編碼 45§4.1常用的小波編碼算法簡析 45§4.2新小波編碼算法的一些必要準(zhǔn)備 47§4.2.1 嵌入式編碼 47§4.2.2 一維信號分段下的提升小波變換 47§4.2.3 二維圖像信號分塊下的提升小波變換 48§4.2.4 邊界問題處理 51§4.2.5 細(xì)節(jié)樹組塊重要性的概念 52§4.3一種改進的SPIHT算法 53§4.3.1SPIHT編碼算法 54§4.3.2改進SPIHT編碼算法 56§4.4ROI特殊區(qū)域編碼 58§4.5一種基于提升的小波編碼系統(tǒng) 59§4.6新系統(tǒng)性能分析 63§4.7本章小結(jié) 63第五章試驗及結(jié)果分析 64第六章結(jié)論 69參考文獻(xiàn) 70發(fā)表論文目錄 73致謝 74第一章緒論§1.1圖像壓縮編碼的必要性隨著經(jīng)濟全球化進程的不斷推進，世界各國之間的聯(lián)系更加緊密，人們之間的交流更加的廣泛和頻繁。對信息的需求量大大的增加。人們不僅要和周圍的人進行面對面的交流，還需要與遠(yuǎn)方的人們進行遠(yuǎn)距離交流。這就要求我們要對信息進行遠(yuǎn)距離的傳輸。而據(jù)分析，人類感知的所有外部信息當(dāng)中，聲音和圖像占據(jù)了其中的主要部分。其中，通過聽覺接收的信息約占接收到總信息量的20％，通過視覺接收的信息則占到60％以上[38]。因此，人們要了解遠(yuǎn)處的信息，就必然要對聲音和圖像信號進行存儲和遠(yuǎn)距離傳輸。而對其中圖像信號的存儲和傳輸尤為重要。然而，由于圖像信息（包括靜止圖像和活動圖像）是高維信息，圖像信號的內(nèi)容非常復(fù)雜，其數(shù)據(jù)量非常龐大。從而給圖像信息的存儲、處理和傳輸都帶來許多問題。給信息的遠(yuǎn)距離交流帶來不便。例如，對于真彩色活動圖像，其分辨率為，每個分量的精度為，則每分鐘的數(shù)據(jù)量為存儲1分鐘這樣的視頻需要近的存儲空間。如果要進行實時傳輸，需要同時占用路數(shù)字電話線（每路）。如果不進行壓縮處理，存儲和傳輸如此海量的數(shù)據(jù)，所消耗的資源是難以接受的。為此，人們想盡各種方法去尋找新的圖像替代表示方法以減少表示一幅圖像所需的數(shù)據(jù)量，這就是圖像編碼所要解決的主要問題，在這個意義上圖像編碼也可以稱作圖像壓縮。圖像壓縮的主要目的就是：在有限的存儲空間內(nèi)，存放更多的圖像信息。減少數(shù)據(jù)量，以便于在有限的信道容量內(nèi)傳輸更多的圖像信息。若不經(jīng)過壓縮就直接進行傳輸或存儲，將消耗大量的通信和存儲資源，給圖像信息傳輸與存儲帶來困難，增加了信息保持的成本。顯然，壓縮比例越大，有限存儲空間和有限的信道容量就可以存放和傳輸?shù)膱D像信息就越多。在圖像壓縮領(lǐng)域進行研究的目的就是尋找到一種有效壓縮編碼方法使得圖像壓縮比例盡可能的大，同時要或者保持圖像的內(nèi)容不變；或者把內(nèi)容的差別控制在一定的范圍內(nèi)；或者保證一定觀察效果的主觀質(zhì)量。第一種情況稱為無失真或無損編碼，后兩種情況為有限失真或有損編碼。根據(jù)不同的需求，應(yīng)用在不同的場合。在一些醫(yī)學(xué)診斷和航天探測圖像就需要無損壓縮編碼，而對于一般的日常圖像多采用有損壓縮編碼。有損壓縮要比無損壓縮的效率要高，且壓縮比更大，同時圖像質(zhì)量沒有明顯的損傷?！?.2圖像壓縮編碼的可能性圖像信號之所以能夠壓縮，是因為圖像中存在著大量的冗余信息。研究圖像壓縮，就是要研究如何減少或者消除這些冗余。在數(shù)字圖像中，有3中最基本的數(shù)據(jù)冗余[39]：1.編碼冗余圖像編碼中，用碼本表示數(shù)據(jù)圖像，如圖1.1所示碼本由一系列碼字組成，每個碼字是一個符號序列，其中的符號個數(shù)稱為碼長。圖1.1圖像編碼數(shù)據(jù)的一般結(jié)構(gòu)設(shè)離散隨機變量表示圖像的灰度值，，出現(xiàn)的概率近似為其中，表示灰度總級數(shù)；表示第個灰度級出現(xiàn)的次數(shù)；表示象素總數(shù)。編碼中若用個比特表示的值，則每個象素所需的平均比特數(shù)為：不同的編碼方法將得到不同的。如果編碼所用的碼本不能使達(dá)到最小，則說明存在編碼冗余。產(chǎn)生編碼冗余是沒有充分利用編碼對象的概率特性所致。例如對每個象素灰度采用自然二進制碼編碼（如均勻量化的PCM碼），不論灰度級出現(xiàn)的概率大小，一律賦予同樣碼長的比特數(shù)，就會產(chǎn)生編碼冗余。而統(tǒng)計編碼（如Huffman編碼）就是利用圖像的統(tǒng)計特性減少編碼冗余的編碼方法。2.象素間冗余象素間冗余是一種與象素間相關(guān)性有關(guān)的數(shù)據(jù)冗余，也稱作空間冗余或幾何冗余。對于一幅隨機圖像樣本，幀內(nèi)存在象素間冗余；對連續(xù)序列圖像，則表現(xiàn)為幀間冗余。存在象素間冗余的圖像，其每個象素值都可用與它鄰近的若干象素值的線性組合來表示，或者說可由鄰近象素值進行預(yù)測。減少象素間冗余的典型編碼方法就是預(yù)測編碼法。3.心理視覺冗余心理視覺冗余是與視覺信息及人的視覺特性密切相關(guān)的一種數(shù)據(jù)冗余。人眼是圖像最終的接受者，而由于人眼對各種視覺信息有著不同的視覺靈敏度，因此，去除那些對于人眼并不敏感的信息（冗余信息），人眼并不會感覺到圖像質(zhì)量的變化。從而達(dá)到壓縮數(shù)據(jù)的目的。量化就是去除心理視覺冗余的過程。其將導(dǎo)致視覺信息的損失，因而是不可逆的。量化是造成圖像信息損失的主要根源，也是圖像高效壓縮編碼的關(guān)鍵。充分利用人眼的視覺特性，就可以得到高效的圖像壓縮編碼方法?！?.3小波圖像壓縮技術(shù)研究進展§1.3.1小波小波變換的概念是由法國從事石油信號處理的工程師J.Morlet在1974年首先提出的。它與Fourier變換、窗口Fourier變換（Gabor變換）相比，這是一個時間和頻率的局域變換，因而能有效的從信號中提取信息，通過伸縮和平移等運算功能對函數(shù)或信號進行多尺度細(xì)化分析（MultiscaleAnalysis），解決了Fourier變換不能解決的許多困難問題，小波變化被譽為“數(shù)學(xué)顯微鏡”，它是調(diào)和分析發(fā)展史上里程碑式的進展。小波分析的應(yīng)用是與小波分析的理論研究緊密地結(jié)合在一起地?，F(xiàn)在，它已經(jīng)在科技信息產(chǎn)業(yè)領(lǐng)域取得了令人矚目的成就。電子信息技術(shù)是六大高新技術(shù)中重要的一個領(lǐng)域，它的重要方面是圖像和信號處理?，F(xiàn)今，信號處理已經(jīng)成為當(dāng)代科學(xué)技術(shù)工作的重要部分，信號處理的目的就是：準(zhǔn)確的分析、診斷、編碼壓縮和量化、快速傳遞或存儲、精確地重構(gòu)（或恢復(fù)）。從數(shù)學(xué)的角度來看，信號與圖像處理可以統(tǒng)一看作是信號處理（圖像可以看作是二維信號），在小波分析地許多分析的許多應(yīng)用中，都可以歸結(jié)為信號處理問題?，F(xiàn)在，對于其性質(zhì)隨實踐是穩(wěn)定不變的信號，處理的理想工具仍然是傅立葉分析。但是在實際應(yīng)用中的絕大多數(shù)信號是非穩(wěn)定的，而特別適用于非穩(wěn)定信號的工具就是小波分析。小波分析用于信號與圖像壓縮是小波分析應(yīng)用的一個重要方面。它的特點是壓縮比高，壓縮速度快，壓縮后能保持信號與圖像的特征不變，且在傳遞中可以抗干擾?；谛〔ǚ治龅膲嚎s方法很多，比較成功的有小波包最好基方法，小波域紋理模型方法，小波變換零樹壓縮，小波變換向量壓縮等。小波變換理論是近幾年興起的時（空）頻域分析理論，通過對原始圖像進行小波變換，可以將圖像信號由時間域（空間域）表示變換到小波域表示。利用小波變換的正交或雙正交變換特性，解除圖像像素間的相關(guān)性，消除圖像信號在空間的冗余，并集中圖像信號的能量，為后面的系數(shù)量化、系數(shù)位建模、算術(shù)編碼等提供前提，為高效的圖像編碼奠定基礎(chǔ)。傳統(tǒng)的卷積小波（第一代小波）變換，由于采用卷積運算方法，過程復(fù)雜，運算量大，實時性較差，不利于硬件的實現(xiàn)。1995年Sweldens提出了一種不依賴于傅立葉變換的新的小波構(gòu)造方法——提升格式（Liftingscheme）[1-5]，稱之為第二代小波變換。這種提升格式不但保持了第一代小波的特性，同時又克服了其平移和伸縮的不變性。許多中外學(xué)者對提升格式小波變換進行了廣泛研究，取得了豐碩的成果[1-12,19,20]。小波提升方案為第一代小波變換提供了一種新的更快速的實現(xiàn)方法。第一代小波變換都可以通過Euclidean算法得到其等效的提升結(jié)構(gòu)[1,6]。提升方法不但是構(gòu)造第二代小波的基本工具[5]，還使得第一代小波的構(gòu)造不再依賴于Fourier變換構(gòu)造，大大降低了構(gòu)造第一代小波的難度，并且已經(jīng)證明提升可以實現(xiàn)所有的第一代小波變換[1,6]。利用提升方案可以構(gòu)造出不同的小波，如Daubechies雙正交小波[7]和差值雙正交小波[8]。提升方法提供了一個有效的構(gòu)造非線性小波的方法,構(gòu)造出的非線性小波同傳統(tǒng)小波變換相比,計算簡單快速,而且適合于自適應(yīng)、非線性、非奇異采樣和整數(shù)到整數(shù)的變換。雙正交小波變換因為具有線形性而廣泛應(yīng)用于圖像壓縮領(lǐng)域，目前研究證明任何具有FIR結(jié)構(gòu)的雙正交小波變換都可以由惰性變換經(jīng)過有限步交替的提升和對偶提升過程得到[1]。小波提升方案的復(fù)雜度只有原來卷積方法的一半左右，而且實時性好，運算簡單，因此成為計算離散小波變換的主流方法。離散小波變換提升實現(xiàn)的快速算法是最近研究的熱點。新一代靜止圖像壓縮標(biāo)準(zhǔn)JPEG2000也將離散小波變換納入標(biāo)準(zhǔn)之中，成為其編碼系統(tǒng)的核心算法?！?.3.2圖像壓縮編碼技術(shù)的研究進展 上個世紀(jì)40年代末脈沖編碼調(diào)制技術(shù)（PCM）出現(xiàn)不久，人們就開始了對電視信號的數(shù)字化研究。經(jīng)典的圖像編碼方法是基于Shannon信息論，其中最基本的Huffman編碼（熵編碼）、預(yù)測編碼和變換編碼理論就產(chǎn)生并發(fā)展于上個世紀(jì)五六十年代，并影響至今，在目前已知的圖像壓縮編碼的國際標(biāo)準(zhǔn)中，仍然被普遍使用。之后，人們在探索一些新的高效編碼方法方面不斷取得進展。例如，算術(shù)編碼已經(jīng)被許多編碼標(biāo)準(zhǔn)所采用，其最大的優(yōu)點就是可以在編碼過程中調(diào)整信號的概率模型，是一類高效、普遍適用的無失真編碼；其他還有矢量量化、方塊截斷編碼、比特面編碼、亞抽樣與內(nèi)插、子帶編碼和小波變換編碼等。另外，隨著人們對視覺特征的認(rèn)識不斷提高，出現(xiàn)了許多結(jié)合人類視覺系統(tǒng)特性（HVS）和多種編碼算法的綜合算法，編碼效率不斷改善。這些基于Shannon信息理論發(fā)展起來的經(jīng)典圖像編碼方法，也稱為第一代編碼方法。上個世紀(jì)90年代以來，Kunt等人提出了第二代編碼的概念。他們認(rèn)為傳統(tǒng)的編碼方法是基于信號波形的方法，衡量編碼方法的效果主要以重建信號與原始信號的波形一致性程度為評價準(zhǔn)則；而新一代編碼方法則是基于對象模型的描述方法，可獲得比經(jīng)典算法要高的壓縮效率。但第二代編碼方法實現(xiàn)起來大都比較復(fù)雜，而且在對一般的自然圖像進行處理時，所獲得的編碼增益也沒有理論上預(yù)期的好。因此，第二代編碼方法尚處于理論研究階段。有待進一步研究出復(fù)雜度較低，較實用的編碼方法。近年來，一種新的變換編碼技術(shù)——小波變換編碼，日益受到人們的重視，特別是1993年J.M.Shapiro提出嵌入式零樹小波編碼（EmbeddedZerotreeWaveletsEncoding，EZW）算法[13]，該算法不但具有優(yōu)良的壓縮性能，還提供了天然的多尺度、多分辨率的圖像描述方法。是一種有效且計算簡單的圖像壓縮技術(shù)，受到這一方法的啟發(fā)，人們后來開發(fā)出了更加有效的SPIHT算法(Setpartitioninginhierarchicaltrees)[14]，CREW[15](Compressionwithreversibleembeddedwavelets)，集合分裂嵌入塊編碼器SPECK[30]算法以及最佳截斷嵌入碼塊編碼（Embeddedblockcodingwithoptimizedtruncation，EBCOT)[17]算法等。由于小波提升算法和EBCOT小波系數(shù)編碼算法的優(yōu)越性能，國際標(biāo)準(zhǔn)化組織（ISO）和國際電聯(lián)電信委員會（ITU-T）于2000年底制定出JPEG2000新的圖像壓縮標(biāo)準(zhǔn)。該標(biāo)準(zhǔn)具有以下6個部分[27,28,38,40]：⑴JPEG2000圖像編碼系統(tǒng)（核心部分）⑵應(yīng)用擴展（在核心上擴展更多特性）⑶運動JPEG2000⑷兼容性（即包容性與繼承性）⑸參考軟件（目前主要為JAVA與C程序）⑹復(fù)合圖像文件格式（如傳真式的服務(wù)等）與以前的JPEG標(biāo)準(zhǔn)小比，JPEG2000具有優(yōu)越的壓縮性能。這是因為它采用了先進的EBCOT編碼技術(shù)。其優(yōu)越性能可以分下面六個方面來說[27,28,38,40]：⑴可以實現(xiàn)漸進式傳輸，這是JPEG2000的重要特征之一。它先傳輸圖像的大體輪廓，然后逐步傳輸其他數(shù)據(jù)，不斷地提高圖像質(zhì)量。這樣圖像就由朦朧到清晰顯示出來，從而充分利用有限的帶寬。而傳統(tǒng)的JPEG只能從上到下逐行顯示，無法做實現(xiàn)漸進式傳輸。⑵同時支持有損、無損兩種壓縮方式。而JPEG只支持有損壓縮。⑶支持感興趣區(qū)域（Regionofinteresting，ROI）進行特別的壓縮編碼。不但可以指定圖像上任意區(qū)域的壓縮質(zhì)量，還可以指定哪個部分先進行解壓處理。這在大大降低圖像尺寸方面起到很大作用。⑷可達(dá)到較高的壓縮比。在具有和傳統(tǒng)JPEG類似質(zhì)量的前提下，其壓縮率要比JPEG高20%-40%左右。⑸在顏色處理上，具有更優(yōu)秀的內(nèi)涵。與JPEG相比，JPEG2000同樣可以用來處理多達(dá)256個通道的信息。而JPEG僅局限于RGB數(shù)據(jù)。也就是說，JPEG2000可以用單一的文件格式來描述另外一種色彩模式，比如CMYK模式。⑹能使基于WEB方式多用途圖像簡單化。由于JPEG2000圖像文件在它從服務(wù)器下載到用戶的WEB頁面時，能平滑地提供一定數(shù)量的分辨率基準(zhǔn)，WEB設(shè)計師們處理圖像的任務(wù)就簡單。例如我們經(jīng)常會看到一些提供圖片欣賞的站點，在一個頁面上用縮略圖來代理較大的圖像。瀏覽者只需點擊該圖像，就可以看到較大分辨率的圖像。不過這樣WEB設(shè)計師們的任務(wù)就在無形中加重了。因為縮略圖與它鏈接的圖像并不是同一個圖像，需要另外制作與存儲。而JPEG2000只需要一個圖像就可以了。用戶可以自由地縮放、平移、剪切該圖像并能得到他們所需要的分辨率與細(xì)節(jié)?！?.4本文研究的內(nèi)容文獻(xiàn)[1]中指出，第一代小波變換都可以通過Euclidean算法得到其等效的提升結(jié)構(gòu)。提升算法為第一代小波變換提供了快速的實現(xiàn)方法。但是在一些情況下，這種優(yōu)勢并不是很明顯。例如，若兩個Laurent多項式的商，仍是一個比較復(fù)雜的Laurent多項式，這樣該提升步驟就較為復(fù)雜，仍然要進行卷積運算。雖比原來稍有簡化但仍然很復(fù)雜。本文就針對第一代小波提升實現(xiàn)算法中存在的這些問題進行研究，提出了一種使得每一步提升都很簡單的提升實現(xiàn)算法。另外，本文還在第二代提升小波變換的基礎(chǔ)上，對變換后的小波系數(shù)如何進行有效的壓縮編碼進行研究。目前比較流行的小波系數(shù)編碼方法有EZW算法、SPIHT算法及被JPEG2000采用的EBCOT算法等。這些算法特別是EBCOT算法，都具有優(yōu)越的性能。但是它們?nèi)匀挥胁蛔阒?。本文針對這些問題進行了分析，并對這些算法進行改進和創(chuàng)新，提出了一種更為有效的小波編碼方案。本文的主要創(chuàng)新點具體如下：1)在傳統(tǒng)的Laurent多項式Euclidean算法的基礎(chǔ)上，通過重新定義Laurent多項式除法，給出了一種改進的Laurent多項式的Euclidean算法，并在該算法的基礎(chǔ)上提出了一種小波變換提升實現(xiàn)的簡化算法。在該提升實現(xiàn)算法中，用簡單的數(shù)乘運算代替了原來小波變換提升實現(xiàn)算法中的卷積運算，使得提升算法中的核心部分——提升及對偶提升步驟的計算更加簡單直接，更加易于軟件和硬件的實現(xiàn)。如果利用該算法對具有線形相位的小波濾波器（如JPEG2000有損壓縮時推薦使用的(9-7)小波濾波器）進行提升實現(xiàn)，就可以使每一步提升都是簡單的單項式，完全擺脫了復(fù)雜的卷積運算。2)研究原始圖像分割后各個子塊的提升小波變換結(jié)果與整個圖像的提升小波變換結(jié)果之間的關(guān)系后發(fā)現(xiàn)，變換后，每個子塊的子帶在整個圖像的相同子帶內(nèi)的空間位置，與該子塊在原始圖像中的空間位置相同。利用這個結(jié)論，可以在編碼端把原始圖像分塊并進行提升小波變換后，進行單獨編碼傳輸；而在解碼端每接收完一個子塊的編碼數(shù)據(jù)并解碼后，按照空間位置關(guān)系，安放到整個圖像的相應(yīng)子帶的相應(yīng)空間位置上。把解碼的數(shù)據(jù)安放好之后，進行提升小波逆變換，就可以恢復(fù)原始圖像。另外，利用該結(jié)論還可以很容易的實現(xiàn)小波變換及其編碼的并行處理和ROI編碼。3)通過引入EBCOT的子帶分塊編碼的思想，對傳統(tǒng)的SPIHT壓縮編碼算法進行改進，提出了一種基于提升小波變換的改進SPIHT算法。該算法不但具有傳統(tǒng)SPIHT算法的優(yōu)點，而且能實現(xiàn)碼流的分辨率可伸縮性和ROI區(qū)域編碼。試驗結(jié)果表明，該算法是綜合性能比較好的一種小波系數(shù)壓縮算法。4)給出了一種有效的基于提升小波變換的圖像壓縮系統(tǒng)。該系統(tǒng)利用分塊理論，把圖像分割成小塊后，單獨進行提升小波變換，對各個圖像塊單獨利用帶有自適應(yīng)二進制算術(shù)編碼器的改進SPIHT算法進行編碼，并在解碼端恢復(fù)后進行重新整合。正文§4.6中分析并給出了該系統(tǒng)的各種優(yōu)越性能，第五章的測試結(jié)果表明該系統(tǒng)在分辨率可伸縮性和ROI區(qū)域編碼情況下的壓縮壓縮效果都比較好。第二章小波變換§2.1連續(xù)小波變換在小波分析中，主要討論的函數(shù)空間為。指上平方可積函數(shù)構(gòu)成的函數(shù)空間，即若，則稱為能量有限的信號。也常稱為能量有限的信號空間。如果，其傅立葉變換為滿足容許性條件（AdmissibleCondition）：(2-1)即有界，則稱為一個基小波或母小波（MotherWavelet）。將母小波經(jīng)過伸縮和平移后，就可以得到一個小波序列：(2-2)其中，，且。稱為伸縮因子，為平移因子。定義下式為關(guān)于基小波的連續(xù)小波變換（或積分小波變換）。其中，表示對的共扼運算。顯然，變換后的函數(shù)是二維的，即小波變換把原來的一維信號變換為二維信號。以便分析信號（或函數(shù)）的時－頻特性。而下面的變換為關(guān)于基小波的逆小波變換。小波逆變換把二維信號重構(gòu)回原來的一維信號。 從小波的容許性條件（2-1）可以知道，母小波是一個振蕩且能量有限的函數(shù)。并且在時域上是快速衰減的。從容許性條件，容易推出(2-3)即。這是因為，若，則當(dāng)時，，即無界。 小波變換的實質(zhì)在于將空間中的任意函數(shù)表示成為其在具有不同伸縮因子和平移因子的之上的投影的疊加。與傅立葉變換（僅將投影到頻率域）不同的是，小波變換將一維時域函數(shù)映射到二維“時間－尺度”域上，因此在小波基上的展開具有多分辨率的特性。通過調(diào)整伸縮因子和平移因子，可以得到具有不同時－頻寬度的小波以匹配原始信號的任意位置，達(dá)到對信號的時－頻局部化分析的目的。§2.2離散小波變換連續(xù)小波變換中的尺度因子和平移因子都是連續(xù)變化的實數(shù)，在應(yīng)用中需要計算連續(xù)積分，在處理數(shù)字信號時很不方便。主要用于理論分析與論證。在實際問題的數(shù)值計算中常采用離散形式，即離散小波變換（DWT）。DWT可以通過離散化CWT中的尺度因子和平移因子得到。通常取把其帶入式（2-2）可以得到這時的小波函數(shù)就是離散小波。相應(yīng)的離散小波變換為特殊的，取，可以得到二進小波（DyadicWavelet）： 在實際應(yīng)用中，為了使小波變換的計算更加有效，通常構(gòu)造的小波函數(shù)都具有正交性，即 從理論上可以證明將連續(xù)小波變換離散成離散小波變換，信號的基本信息并不會丟失，相反由于小波基函數(shù)的正交性，使得小波空間中兩點之間因冗余度造成的關(guān)聯(lián)得以消除；同時，因為正交性，使得計算的誤差更小，使得變換結(jié)果時－頻函數(shù)更能反映信號本身的性質(zhì)?！?.3多分辨分析及Mallat算法多分辨分析（Multi-resolutionAnalysis，MRA）是由S.Mallat引入的，他從空間概念上，形象地說明了小波的多分辨特性，將在此之前所有小波變換理論統(tǒng)一起來。1989年，Mallat在小波變換多分辨分析理論與圖像處理的應(yīng)用研究中受到塔式算法的啟發(fā)，提出了信號的塔式多分辨分析分解與重構(gòu)的快速算法，即著名的Mallat算法。Mallat算法在小波分析中的地位相當(dāng)于快速傅立葉變換（FFT）在經(jīng)典傅立葉分析中的地位。本節(jié)就介紹一維和二維張量積情況下的多分辨分析及相應(yīng)的Mallat算法。至于三維及三維以上情況下的多分辨分析，由于在二維離散的數(shù)字圖像的處理中不涉及，在此不作介紹(可參見文獻(xiàn)[12，P138-144])?！?.3.1一維正交多分辨分析多分辨分析是用小波函數(shù)的二進伸縮和平移表示函數(shù)這一思想的更加抽象復(fù)雜的表現(xiàn)形式，它重點處理整個函數(shù)集，而非側(cè)重處理作為個體的函數(shù)。MRA形成了構(gòu)造正交小波基的一個框架，常用的B-樣條正交小波基和Daubechies緊支撐正交小波基都可看作是該框架下的產(chǎn)物。下面就給出多分辨分析的嚴(yán)格定義：定義2.1稱中的閉子空間序列為一個（二進）多分辨分析，如果滿足下列條件：單調(diào)性：逼近性：伸縮性：平移不變性：Riesz基存在性：存在函數(shù)，使得構(gòu)成的一個Riesz基。即函數(shù)序列線性無關(guān)，且存在常數(shù)和，滿足，使得對任意的，總存在序列使得且，。則稱為尺度函數(shù)，并稱生成的一個多分辨分析。特別的，若構(gòu)成的一個標(biāo)準(zhǔn)正交基，則稱為正交尺度函數(shù)，相應(yīng)的，稱生成的一個正交多分辨分析。MRA本質(zhì)上給出了人類視覺系統(tǒng)對物體認(rèn)識的數(shù)學(xué)描述。當(dāng)人眼觀察某一物體時，如果設(shè)為人眼在尺度下所感知的物體信息（如物體的一個側(cè)面），而當(dāng)尺度增加到時，所攝取的信息量為（如物體的全貌）。尺度的增加可以看作是觀察距離的較少，因而，能更深入的認(rèn)識物體，即有，。在多分辨分析中，稱為逼近空間。一般的，不同的逼近空間對應(yīng)著不同的尺度函數(shù)，從而對應(yīng)不同的多分辨分析。在實際中，比較有用的是一類具有緊支撐特性的尺度函數(shù)。若為尺度函數(shù)生成的中的多分辨分析，則必然存在系數(shù)序列，使得以下尺度關(guān)系，即兩尺度方程成立：（2-4）這是因為，，且構(gòu)成的一個Riesz基，故存在系數(shù)，使得。尺度方程（2-4）在頻域的表達(dá)式為（2-5）其中為系數(shù)序列的傅立葉變換。假設(shè)是數(shù)字濾波器的脈沖響應(yīng)，則該式將離散濾波器和多尺度分析聯(lián)系起來。根據(jù)文獻(xiàn)[12]中的定理2.34，可以知道，若，則是標(biāo)準(zhǔn)（規(guī)范）正交系，等價于恒等式對于幾乎所有的成立。 利用這個定理，可以通過將尺度函數(shù)正交化的方法，得到一個正交尺度函數(shù)。若令(2-6)則，且構(gòu)成的一個標(biāo)準(zhǔn)正交基，而對于任意的，構(gòu)成一個標(biāo)準(zhǔn)正交基。從而生成一個正交多分辨分析。事實上，對任意，由多分辨分析的定義可知，。則存在系數(shù)序列使得用代替，可得。因此，構(gòu)成的一個基。此外，對于任意，有則可以知道，對于任意的，是標(biāo)準(zhǔn)正交的。 但是，通常情況下不是的標(biāo)準(zhǔn)正交基。通過正交多分辨分析，我們可以得到的一個標(biāo)準(zhǔn)正交基。 由于，則存在在中的正交補空間，使得上述空間正交分解過程可對逼近空間遞歸進行下去，可用下圖表示。則，。令，可得到的正交和分解：(2-7)函數(shù)稱為小波，如果。如果構(gòu)成的一個標(biāo)準(zhǔn)正交基，則由可以推出構(gòu)成的標(biāo)準(zhǔn)正交基，從而構(gòu)成的標(biāo)準(zhǔn)正交基。這時稱為小波空間，為正交小波。 定理2.1設(shè)正交尺度函數(shù)生成了正交多分辨分析，是滿足兩尺度方程的濾波器，令(2-8)其中，滿足，則為小波，且它的平移系構(gòu)成的標(biāo)準(zhǔn)正交基，其中是在中的正交補。從而，構(gòu)成的一個標(biāo)準(zhǔn)正交基。 上述定理等價為以下幾點： 1）是標(biāo)準(zhǔn)正交的。 2）對任意。 3）中的每個函數(shù)都可表示為的線性組合。 4）是一個小波，即。 定理2.1是一個非常重要的定理，它給出了一種根據(jù)正交尺度函數(shù)來構(gòu)造正交小波的一般方法。具體推導(dǎo)過程如下：利用式（2-6）由計算利用式（2-5）計算由，計算相應(yīng)的傅立葉變換式根據(jù)小波方程的頻域表示式計算上述構(gòu)造正交小波基的整個過程可總結(jié)為， 根據(jù)上面的過程，得到小波基之后，我們就可以用其來表示中的任意函數(shù)，等式兩邊同時對取內(nèi)積，并注意到是的一個標(biāo)準(zhǔn)正交基，可以得到，則有特別的，對于中的任意子空間，有從而，可以得到中的任意函數(shù)都存在如下多分辨分析表示，其中表示函數(shù)的低頻部分，而表示在不同分辨率下的高頻成分。在式(2-9)兩邊同時與做內(nèi)積，并利用及其二進伸縮和平移的正交特性，可得到類似的有同時對等式（2-9）兩邊與做內(nèi)積，有其中，是由正交尺度函數(shù)的兩尺度方程對應(yīng)的濾波器系數(shù)序列，可看作是低通濾波器；由式給出，可看作是高通濾波器。由此，可以得到一維情況下，離散小波變換的Mallat算法。其卷積表達(dá)形式為其中，表示濾波器的共軛反轉(zhuǎn)；表示與的卷積；表示對卷積的二元下抽樣；表示對序列的二元上抽樣；為二元上、下抽樣算子。小波分解與重構(gòu)的迭代過程如圖2.1所示。相應(yīng)二通道濾波器組表示見圖2.2。a）小波分解過程b）小波重構(gòu)過程圖2.1一維信號小波分解與重構(gòu)的迭代過程示意圖圖2.2一維信號小波分解與重構(gòu)的二通道濾波器組表示（括號中選項表示雙正交濾波器） 由于除了Haar小波外，沒有同時具有對稱性和緊支撐性的正交小波。緊支撐性，意味著小波濾波器的長度是有限長的，以便于計算（如果長度無限，將難以處理）。對稱性，意味著小波濾波器的線性相位，線性相位可以保持原信號的相位不變。緊支撐性和對稱性在信號處理中具有重要的意義。為了同時具有這兩種性質(zhì)，就必須放棄小波的正交性，而采用雙正交小波。下面就來介紹雙正交多分辨分析的概念、雙正交小波基在函數(shù)多分辨表示中的作用及雙正交小波分解與重構(gòu)的濾波器組算法。定義2.2設(shè)函數(shù)，稱是的一個Reisz基，如果它是線性無關(guān)的，且存在常數(shù)和，滿足，使得對任意的，總存在序列滿足：且，。 設(shè)和是的兩個多分辨分析，它們的尺度函數(shù)分別為和，如果下述條件成立：和滿足如下正交性條件：(2-10)這時稱和為對偶尺度函數(shù)。令是在中的補空間，是在中的補空間，使得其中，為直和運算。如果存在中的函數(shù)和序列滿足：使得且是的一個Reisz基，是的一個Reisz基，從而和都構(gòu)成的Reisz基。則稱是的一個雙正交多分辨分析。這時稱和為對偶雙正交小波。 在雙正交多分辨分析的定義中，如果，則由式（2-10）可知，為正交尺度函數(shù)，它生成的一個正交多分辨分析。這說明正交多分辨分析是雙正交多分辨分析的特殊情況。類似正交小波分解和重構(gòu)過程的推導(dǎo)，可以得到雙正交小波變換的Mallat算法如下：選取圖2.2中括號中的濾波器，可以得到雙正交小波分解與重構(gòu)對應(yīng)的二通道濾波器組表示。§2.3.2二維張量積多分辨分析及Mallat算法前面介紹的是一維小波及其變換，為了能夠處理二維函數(shù)或信號（如圖像信號），就必須引入二維小波和二維小波變換及相應(yīng)的快速算法。二維多分辨分析有兩種，一種是可分離的，一種是不可分離的。前一種情況簡單且應(yīng)用廣泛。因此本節(jié)就介紹可由一維多分辨分析的張量積空間構(gòu)造的二維多分辨分析。而不可分離的情況也比較常見，但在圖像處理領(lǐng)域應(yīng)用不多，故這里不作介紹（可參見文獻(xiàn)[11]，P113-118）。用表示平面上平方可積函數(shù)空間，即（2-11）容易證明，平面上有限區(qū)域中的一幅圖像的能量是有限的。如設(shè)是一幅圖像，它的定義域圍成的區(qū)域的面積為，設(shè)最大的亮度值為M，即，則 引入空間的內(nèi)積相應(yīng)的范數(shù)定義為在不發(fā)生混淆的情況下，范數(shù)也常記為。的Fourier變換定義為， 設(shè)和是兩個有限維或可數(shù)無限維線性空間。和的基底分別為，及。定義以形如的元素為基底的空間，為與的張量積空間，表示為如果和都是函數(shù)空間，和分別是和中的自變量，則張量積空間中的元素稱為二維張量積函數(shù)或張量積曲面。 現(xiàn)在，設(shè)和是由尺度函數(shù)和生成的兩個多分辨分析。則可以得到和的張量積空間，由于的基底為，的基底為，所以的基底為。 對于二元函數(shù)，引入記號記則是的基底。這樣就形成中的一個多分辨分析，就是相應(yīng)的尺度函數(shù)。 設(shè)關(guān)于的補空間，關(guān)于的補空間，即 現(xiàn)在，設(shè)生成，生成，即這時（2-12）其中，,同樣，由于的基底為，的基底為，則的基底為。記則的基底為。類似的，記則的基底為，的基底為。 可以看到，與一維只有一個尺度函數(shù)和一個小波函數(shù)不同的是，二維情形有一個尺度函數(shù)和三個小波函數(shù)。 與一維情況類似，由式（2-12），我們有直和分解則對于都有唯一分解其中。 若及都是半正交尺度函數(shù)與半正交小波函數(shù)，則上面的直和分解就可以變?yōu)檎缓头纸獯藭r，即，其中。 設(shè)，則其中對于任何。這樣對于還可以進一步分解為其中。則有。 利用一維情況下的兩尺度方程和小波方程可以得到二維張量積兩尺度關(guān)系為其中現(xiàn)在，設(shè)則由再利用尺度函數(shù)和小波函數(shù)及其二進伸縮和平移的正交性，可以得到二維Mallat算法如下：（1）分解算法：（2）重構(gòu)算法：類似的，利用一維雙正交多分辨分析，可以獲得二維雙正交多分辨分析。只要將相應(yīng)的分解和重構(gòu)濾波器置換，就可以得到二維雙正交多分辨分析的Mallat算法。我們稱序列為的一級二維小波變換。 則對應(yīng)于二維Mallat算法的濾波器組表示如圖2.3所示。二維小波分解（括號中表示雙正交濾波器）二維小波重構(gòu)圖2.3二維二通道Mallat算法的濾波器組表示 有了上面的分析，現(xiàn)在就可以分析二維離散圖像信號的處理方法。設(shè)是一幅輸入圖像，其象素點之間的距離為，其中。我們可以將與尺度下的一個逼近函數(shù)聯(lián)系起來，其中，是兩個對偶尺度函數(shù)。使得為的均勻采樣，即。另外，根據(jù)，有。由于，故從而，是在的一個小鄰域上的加權(quán)平均。因此有 若將看成是一幅二維圖像信號，和分別為行下標(biāo)和列下標(biāo)，則二維小波變換過程可以如下解釋：先利用分析濾波器，對圖像的每一行做小波變換，得到低頻部分和高頻部分；然后對得到的數(shù)據(jù)的每一列用分析濾波器，做小波變換；對的各列做小波變換得到低頻系數(shù)，即；得到高頻系數(shù)，即。對的各列做小波變換得到低頻系數(shù)，即，及高頻系數(shù)，即。一級小波分解后圖像由四部分構(gòu)成：其中，每個子圖像都是原始圖像尺寸大小的。這樣每一級變換得到的低頻信號遞歸的進行分解。同樣重構(gòu)過程也可類似進行。這樣就形成了二維小波變換的塔式結(jié)構(gòu)?！?.4緊支撐雙正交小波基的構(gòu)造 由于除了Haar小波外，沒有同時具有對稱性和緊支撐性的正交小波。而Haar小波不能很好的表示和分析連續(xù)信號或函數(shù)。因而，在數(shù)字圖像處理中，常常采用同時具有對稱性和緊支撐性的雙正交小波。故本節(jié)只介紹具有緊支撐性的雙正交小波基的構(gòu)造方法。正交小波基的構(gòu)造方法可以參見文獻(xiàn)[8,11,12]相關(guān)部分的介紹。設(shè)是對偶的雙正交尺度函數(shù)，是對偶雙正交小波，則有與其相應(yīng)的兩尺度方程和小波方程（2-13）（2-14）在式（2-13）和式（2-14）中的每個方程兩邊同時取積分，可得（2-15）及（2-16）容易推出，式（2-13）和式（2-14）等價的頻域表示形式分別為（2-17）（2-18）對式（2-17）和式（2-18）中的各方程進行反復(fù)迭代，可得各式的無窮積表示，（2-19），（2-20）這說明以上四個式子在中都是收斂的。 另外，濾波器組還要滿足完全重構(gòu)條件（2-21） 由式（2-15）、式（2-16）和式（2-21）容易推出此外，由式（2-15）和式（2-21）可以推出式（2-16）；由式（2-19）和式（2-13）可以推出式（2-20）。因此，綜上可以得到，有限濾波器，使得尺度函數(shù)和對偶小波函數(shù)存在的必要條件為（2-22）及（2-23）式（2-22）被稱為雙正交濾波器的約束條件。 下面的定理給出了對完全重構(gòu)的有限長濾波器給出了生成的一個雙正交基的充分條件。 定理2.2若有限長濾波器滿足式（3-21）,滿足下式其中，時，。并且則無窮積，依次收斂于中的函數(shù)，。滿足雙正交關(guān)系。兩個小波族都是的雙正交Riesz基，其中滿足式（3-13）。且相應(yīng)的尺度函數(shù)和小波函數(shù)也都有緊支集。具體的，如果對于，；對于，，使得的支撐依次為和，則的支撐分別為和。因而，相應(yīng)的小波的支撐分別為和。所以兩個小波的支撐長度相同，都等于。設(shè)和是關(guān)于0對稱的對偶低通濾波器，即滿足（2-24）并且的長度分別為和，則有下面的結(jié)論成立：小波有階消失矩等價于滿足如下關(guān)系（2-25）2）小波有階消失矩等價于滿足如下關(guān)系（2-26）綜上所述可知，構(gòu)造具有階消失矩并關(guān)于0對稱的雙正交小波和的約束條件為式（2-22）、式（2-24）、式（2-25）及式（2-26）下面用例子來說明雙正交小波基的構(gòu)造方法。 例2.1構(gòu)造(5-3)小波濾波器。其被廣泛應(yīng)用于圖像壓縮，而且為JPEG2000中無損圖像壓縮的缺省濾波器。的濾波器長度分別為5和3，即。。并且是關(guān)于0對稱的雙正交小波。則可以得到(5-3)小波濾波器的約束條件為整理并求解該方程組可得到 例2.2構(gòu)造(9-7)小波濾波器。其被JPEG2000用于有損圖像壓縮的缺省濾波器。的濾波器長度分別為9和7，即。。并且是關(guān)于0對稱的雙正交小波。則可以得到(9-7)小波濾波器的約束條件為整理并求解該方程組可得到的值如表2.1所示。表2.1小波與對偶小波都具有4階消失矩的(9-7)小波濾波器系數(shù)01，－12，－23，－34，－40.788485616405580.41809227322162-0.04068941760916-0.0645388826287000.852698679008890.37740285561283-0.11062440441844-0.023849465019560.03782845550726§2.5本章小結(jié)本章主要介紹傳統(tǒng)小波（或第一代小波）變換理論的基本知識。首先介紹了連續(xù)小波變換和離散小波變換的基本原理。接著討論了離散小波變換在一維和二維張量積情況下的多分辨分析及相應(yīng)的Mallat算法。Mallat算法在小波分析中具有非常重要的地位，相當(dāng)于快速傅立葉變換（FFT）在經(jīng)典傅立葉分析中的地位。最后給出了緊支撐雙正交小波基的構(gòu)造方法。本章所介紹的內(nèi)容是為下一章介紹提升小波變換（或第二代小波）理論做必要準(zhǔn)備。第三章提升小波變換的簡化實現(xiàn) 經(jīng)典小波分析是從傅立葉分析的基礎(chǔ)上發(fā)展出來的，因而它在一定程度上受到傅立葉分析的限制。小波分析中的兩個核心的概念——小波分析和多分辨分析都是建立在二進平移和伸縮思想基礎(chǔ)之上的，這種思想直接來源于信號處理領(lǐng)域。我們稱這種經(jīng)典多分辨分析框架構(gòu)造的小波為第一代小波。 1995年Sweldens提出了一種不依賴于傅立葉變換的新的小波構(gòu)造方法——提升格式(liftingscheme)，稱之為第二代小波變換。提升格式保持了第一代小波的特性，同時又克服了其平移和伸縮的不變性，并具有許多優(yōu)點，具體表現(xiàn)在： 1）能夠用于構(gòu)造第一代小波，可根據(jù)需要來設(shè)計小波基。例如，可以先選擇一個具有特殊尺度函數(shù)的一般多分辨分析，然后利用提升技術(shù)來修正該多分辨分析，直到滿足設(shè)計者所希望性質(zhì)。這種方法常用于提升小波的消失矩、構(gòu)造具有插值性質(zhì)的小波等。應(yīng)用提升方法構(gòu)造第一代小波，雖然不能構(gòu)造全新的小波，但是它使我們認(rèn)識到小波的構(gòu)造能夠完全在空間域完成。 2）能夠改進第一代小波變換算法。它提供了一種快速實現(xiàn)方式，與經(jīng)典的Mallat算法相比，運算量減少一半。能夠?qū)崿F(xiàn)小波變換的原位（in-place）計算。換言之，整個計算過程不需要申請輔助存儲空間，可節(jié)省存儲單元。逆小波變換的實現(xiàn)非常簡單、快速直接，而且意義非常明確?？梢院唵蔚耐ㄟ^逆序正變換，同時交換加減符號得到。很容易實現(xiàn)整數(shù)小波變換，可以使小波變換用于信號的無損壓縮。能夠很容易的處理邊界問題。 3）可用于第二代小波的構(gòu)造。這種小波構(gòu)造方法完全擺脫了Fourlier變換，放棄了二進平移和伸縮的條件，但獲得的小波具有第一代小波的所有優(yōu)點，如時頻局部化性質(zhì)和快速變換算法?；诖?，我們可以在非平移不變區(qū)域（如有界區(qū)域或曲面）上構(gòu)造小波基?！?.1小波分解與重構(gòu)的多相位表示 由于正交小波變換是雙正交小波變換的特殊情況，因此，下面僅介紹具有有限脈沖響應(yīng)（FiniteInpulseresponse，F(xiàn)IR）的雙正交小波濾波器的情況。設(shè)、、、是雙正交小波濾波器組，它們對應(yīng)的二通道Mallat算法等價的變換表示如圖3.1所示。圖3.1二通道Mallat算法等價的變換表示 濾波器的多相位表示為其中，包含了的偶系數(shù)，而包含了的奇系數(shù)，即或者 在二通道雙正交小波濾波器組的完全重構(gòu)（PerfectReconstruction,PR）條件下，取，從而有， 定義和的多相位矩陣（polyphasematrix）為從而有，類似的，可以定義和的多相位矩陣，亦即和的對偶多相位矩陣為同樣，因此，小波濾波器的完全重構(gòu)條件可以寫成，（3-1）其中表示矩陣的轉(zhuǎn)置矩陣，為的單位矩陣。根據(jù)上式可以給出小波分解與重構(gòu)的多相位表示，如圖所示。z-1z-1z圖3.2小波分解與重構(gòu)的多相位表示 下面來說明圖3.1和圖3.2在效果上的等價性。設(shè)輸入序列的變換為，則圖3-2中虛線框部分的作用相當(dāng)于對序列進行懶小波變換，即抽取序列的偶序列和奇序列。偶序列和奇序列的變換分別為，，。設(shè)這兩個變換經(jīng)過作用后的低頻部分和高頻部分分別為和，則有計算上式可以得到這與根據(jù)圖2.1所得到的結(jié)果完全相同。這就說明兩圖在效果上是完全等價的。 由于、、、都是有限長的小波濾波器，所以和的行列式和都是Laurent多項式。由式（3-1）可知，及其倒數(shù)都是Laurent多項式，故其必定為關(guān)于的單項式。這里設(shè)。下面的章節(jié)將根據(jù)小波分解和重構(gòu)的多相位表示，通過對多相位矩陣進行因子分解，給出小波變換的提升實現(xiàn)算法?！?.2Laurent多項式的Euclidean算法 考慮一個具有緊支集的有限脈沖響應(yīng)（FiniteInpulseresponse，F(xiàn)IR）濾波器，其中對于有限范圍以外的均為零。有限濾波器的變換是一個Laurent多項式，即(3-2)于是，的次數(shù)為，比濾波器的長度少1。當(dāng)是單項式時，定義其次數(shù)為[1]。 定義3.1兩個Laurent多項式的帶余除法： 對任何兩個Laurent多項式和，其中，，一定存在Laurent多項式（稱為商）和（稱為余數(shù)），使成立，其中，或。稱該過程為兩個Laurent多項式的帶余除法。簡稱帶余除法。 兩個Laurent多項式的商和余數(shù)不是唯一的。例如，對于，，對于以下幾種情況： 1）。 2）。 3）。都滿足，且。 利用帶余除法，可以給出Laurent多項式的Euclidean算法如下： 對于任何兩個Laurent多項式和，其中。設(shè)，從開始進行如下的遞歸運算：其中，“％”表示取余運算。則，且是一個Laurent多項式，其中為使的最小數(shù)，“gcd()”表示取最大公因子（greatestcommondivisor）。 假設(shè)，則存在使得，因此算法在步結(jié)束，其中。若記，其中，“/”表示取“商”運算，則有這等價于(3-3)顯然，同時整除和。如果是一個單項式，則和是互素的。§3.3改進的Laurent多項式Euclidean算法 根據(jù)上面的兩個Laurent多項式的帶余除法的定義，給出了商為單項式的帶余除法的定義，如下： 定義3.2商為單項式的兩個Laurent多項式的帶余除法： 對任何兩個Laurent多項式，，其中，（即），一定存在Laurent單項式(3-4)稱為單項商，其和多項式（稱為余數(shù)），使成立。稱該過程為商為單項式的兩個Laurent多項式的帶余除法。簡稱為，單項商帶余除法。 從上面的定義可以看出，單項商帶余除法的定義少了一個約束條件。這是因為，在要求商為單項式的條件下，就不能保證所求得的余數(shù)的次數(shù)一定比除數(shù)的小。另外，在我們的定義中也可以不要求，為與上面所述的Euclidean算法相一致特意增加了該條件。 由于對于給定的兩個Laurent多項式和，以及都是確定的數(shù)，因此在該定義下，顯然有下面的定理成立。 定理3.1兩個Laurent多項式的單項商和余數(shù)是唯一的。例如，對于上面的例子，，由于，故，，且。 利用單項商帶余除法，我們可以給出Laurent多項式的改進的Euclidean算法如下： 對于任何兩個Laurent多項式和，其中。初始化，令，；計算；計算單項商其中，，和，分別表示和中的最大指數(shù)項及最小指數(shù)項的系數(shù)；計算余數(shù)其中，“％”表示單項商帶余除法定義下的取余運算；5）;6）如果退出循環(huán)。否則，跳轉(zhuǎn)到2)繼續(xù)循環(huán)。和上面的定義一樣，，且是一個Laurent多項式，其中為使的最小數(shù)。假設(shè)，則存在使得，因此算法在步結(jié)束。其中。同樣我們可以得到與式（3-3）相同的結(jié)果，顯然，同時整除和。如果是一個單項式，則和是互素的。比較改進前后的Laurent多項式Euclidean算法，我們可以發(fā)現(xiàn)，雖然前后兩種算法都可以得到式（3-3）相同的結(jié)構(gòu)。但是其中的是完全不同的。前者中為一個Laurent多項式，而后者中所有的都是單項式。使得各個矩陣之間的乘積變得簡單，計算復(fù)雜度大大減少。下面還是用上面的例子，來說明。 例3.1用基于帶余除法的Laurent多項式Euclidean算法進行計算。 計算過程（由于結(jié)果不止一種，這里只取下面一種）1）令，2），，3），，所以，和是互素的，且輾轉(zhuǎn)除法的步數(shù)為。 例3.2用基于單項商帶余除法的Laurent多項式Euclidean算法進行計算。 計算過程，1）令， 2），， 3），， 4)，， 5)，，所以，和是互素的，且輾轉(zhuǎn)除法的步數(shù)為。 下面用，來說明。 例3.3用基于帶余除法的Laurent多項式Euclidean算法進行計算。 計算過程，1）令， 2），， 3），，所以，和是互素的，且輾轉(zhuǎn)除法的步數(shù)為。 例3.4用基于單項商帶余除法的Laurent多項式Euclidean算法進行計算。 計算過程，1）令， 2），， 3），， 4)，， 5)，， 6)，， 7)，， 8)，， 9)，，所以，和是互素的，且輾轉(zhuǎn)除法的步數(shù)為。§3.4多相位矩陣的因子分解 Daubechies和Swedens在其文獻(xiàn)[1]中研究并給出了多相位矩陣因子分解的定理，該定理構(gòu)成了小波變換提升實現(xiàn)的基礎(chǔ)。下面在的行列式等于1的前提下，討論完全重構(gòu)濾波器的提升分解格式。并給出多相位矩陣的因子分解定理。 定義3.3若多相位矩陣的行列式等于1，則相應(yīng)的濾波器對稱之為補。 顯然，當(dāng)構(gòu)成補時，也構(gòu)成補。 定理3.2（提升）設(shè)構(gòu)成補，則任何其他的補都可以表示為其中為Laurent多項式。 證明：直接計算知道的多相位分量對于偶數(shù)部分為，而對于奇數(shù)部分為。做一次提升分解后，新的多相位分解矩陣定義為 此時行列式的值沒有發(fā)生變化，而。類似可以得到對偶多相位分解矩陣的表示為，此時的提升格式得到新的濾波器。類似的，我們也可以通過對偶提升格式來建立分解與重構(gòu)端的提升結(jié)構(gòu)。 定理3.3（對偶提升）設(shè)構(gòu)成補，則任何其他的補都可以表示為其中為Laurent多項式。做一次對偶提升分解后，新的多相位分解矩陣定義為而對應(yīng)于產(chǎn)生新的濾波器滿足。 根據(jù)前面所述的改進的Euclidean算法對多項式向量（3-5）進行分解，可以得到。經(jīng)過處理，我們總能保證為偶數(shù)。當(dāng)為奇數(shù)時，經(jīng)過下面的處理過程可以使得變?yōu)榕紨?shù)。 假設(shè)為奇數(shù)，并令則， 現(xiàn)在，如果令則，由于為單項式，所以仍為單項式。則此時有，（3-6）其中，。給定一個濾波器，通常可以用下面的式子得到與其構(gòu)成補的濾波器。 根據(jù)前面的論述，上面的式子構(gòu)成了一種完全重構(gòu)濾波器多相位矩陣的提升分解。但是，對于一般給定的特殊長度（包括分解和重構(gòu)）的完全重構(gòu)濾波器，上述分解不一定滿足。因此，我們需要根據(jù)定理3.2對該結(jié)果進行提升。存在Laurent多項式使得，則濾波器對的多相位矩陣可以表示為，（3-7）另外，注意到，當(dāng)為偶數(shù)時，利用上式可以得到，（3-8）根據(jù)上面的討論，我們可以給出下面的定理。 定理3.4若的行列式等于1，即，則總存在Laurent多項式和及非零常數(shù)，使得其中，，。 在式（3-8）中，令，，，并結(jié)合式（3-7）可以知道該定理成立。 下面給出提升因子和的計算方法。 首先，對多項式矩陣（3-5）應(yīng)用歐幾里德算法，可得到令，注意到，則由式（3-7）可得，，其中。 若記，則則有，因此有，，綜上，我們可以得到有限濾波器多相位矩陣的提升分解算法：使用歐幾里德算法得到計算最后計算出另外，對多項式矩陣（3-5）應(yīng)用歐幾里德算法，可得到其中，為偶數(shù)。若為奇數(shù)，可以根據(jù)式（3-6）處理，最終可以使得為偶數(shù)。令，則，化簡上面的式子，可以得到，。則根據(jù)式（3-7）可以得到，用該式進行計算，比上述算法少做一次矩陣乘法。根據(jù)二通道小波濾波器的完全重構(gòu)（PerfectReconstruction）條件的多相位表示，（3-9）其中，為的單位矩陣，可以得到，（3-10）由此，我們可給出基于提升的正向小波變換和逆向小波變換的流程圖如圖3.3和圖3.4所示。圖3.3基于提升的正向小波變換流程圖圖3.4基于提升的逆向小波變換流程圖圖3.3和圖3.4中和分別表示輸入序列的偶序列和奇序列的變換，和表示經(jīng)過一級小波變換后得到的低頻部分和高頻部分的變換。§3.5小波變換的提升實現(xiàn)的傳統(tǒng)算法 根據(jù)上一節(jié)的討論，下面給出小波變換的提升實現(xiàn)算法。根據(jù)是否為零分為兩種情況。當(dāng)時，預(yù)測步驟的起始步由奇序列預(yù)測偶序列。時，預(yù)測步驟的起始步由偶序列預(yù)測奇序列。限于篇幅，這里只給出的情況。設(shè)是長度為（這里設(shè)為偶數(shù)）的一個信號，和表示它的偶序列和奇序列。由于和都是單項式，故可以記，若記，分別表示，的變換，且則用序列卷積可表示為，故可以寫出正向小波變換提升實現(xiàn)的簡化算法如下：1）懶小波變換（Lazywavelettransform）2）步提升及對偶提升（liftinganddualliftingsteps）3）比例縮放變換（scaling）最后得到的和分別為小波分解的低頻分量和高頻分量。其中，。 通過對正向小波變換按照相反的步驟操作，同時改變正負(fù)號，即可得到相應(yīng)的逆變換如下。1）比例縮放變換（scaling）2）步提升及對偶提升（liftinganddualliftingsteps）3）逆懶小波變換（InverseLazywavelettransform）另外，參照上面的介紹，時的算法步驟可以類似給出。這里不再列出?！?.6小波變換的提升實現(xiàn)的簡化算法 利用上面給出的改進的Laurent多項式的Euclidean算法，我們提出了一種小波變換的提升實現(xiàn)的簡化算法。該算法與前面的算法類似，只是提升與對偶提升步驟稍有差別，其他過程都基本一致。同樣該算法也按是否為零，分為兩種情況。時的算法過程如下。設(shè)是長度為（這里設(shè)為偶數(shù)）的一個信號，和表示它的偶序列和奇序列。由于和都是單項式，故可以記，，若記，分別表示，的變換，且則用序列卷積可表示為，故可以寫出正向小波變換提升實現(xiàn)的簡化算法如下：1）懶小波變換（Lazywavelet）；2）步提升及對偶提升（liftinganddualliftingsteps）；3）比例縮放變換（scaling）。最后得到的和分別為小波分解的低頻分量和高頻分量。其中，。 通過對正向小波變換按照相反的步驟操作，同時改變正負(fù)號，即可得到相應(yīng)的逆變換。另外，當(dāng)?shù)那闆r與時情況稍有不同，但是可以參照傳統(tǒng)算法時的情況類似給出算法步驟。這里不再列出。§3.7提升算法舉例 下面以幾種常用的小波變換的提升實現(xiàn)為例來說明本文算法與傳統(tǒng)算法的不同。由于傳統(tǒng)的多相位矩陣的分解不唯一，所以小波變換的提升分解也不是唯一的。以下用傳統(tǒng)小波變換提升分解算法實現(xiàn)的例子中只給出一種常用的分解形式。 例3.5用傳統(tǒng)提升小波算法實現(xiàn)(5-3)小波變換的提升。 (5-3)小波濾波器如下：可以求出(5-3)小波濾波器的多相位矩陣在傳統(tǒng)的提升小波算法下存在如下一種因子分解，其中，。由此可以給出(5-3)正向小波變換的提升實現(xiàn)為， 例3.6用本文提升小波算法實現(xiàn)(5-3)小波變換的提升?？梢郧蟪觯蜃臃纸鉃椋浩渲?，。由可以得到，由此可以給出(5-3)正向小波變換的提升實現(xiàn)為，簡單的變更計算次序和加減號就可以給出(5-3)逆向小波變換的提升實現(xiàn)為，然后根據(jù)圖3.3和圖3.4就可以給出相應(yīng)的基于提升的正向及逆向小波變換的流程圖。以下各例都可通過做類似的操作，得到相應(yīng)的流程圖。 例3.7用傳統(tǒng)提升小波算法實現(xiàn)(9-7)小波變換的提升。，這里選用小波與對偶小波都具有4階消失矩的(9-7)小波濾波器，濾波器系數(shù)見表2.1。可以求出，存在以下因子分解：令，則，于是我們可以得到(9-7)正向小波變換的提升實現(xiàn)算法為： 例3.8用本文提升小波算法實現(xiàn)(9-7)小波變換的提升?？梢郧蟪觯蜃臃纸鉃椋海?-11）其中，由可以得到，于是我們可以得到(9-7)正向小波變換的提升實現(xiàn)算法為：(9-7)逆向小波變換的提升實現(xiàn)仿照例3.6中的形式，可以很容易給出。這里不再給出。 例3.9用傳統(tǒng)提升小波算法實現(xiàn)D4小波變換的提升。D4小波濾波器的變換為其中可以求出D4小波濾波器的多相位矩陣在傳統(tǒng)的提升小波算法下有如下一種因子分解，由此，可以給出D4小波變換的傳統(tǒng)提升實現(xiàn)算法為， 例3.10用本文提升小波算法實現(xiàn)D4小波變換的提升。 用改進的Laurent多項式Euclidean算法計算出 由此，可以給出D4小波變換的本文提升實現(xiàn)算法為， 從上面的例子，可以看到，對于具有線性相位的(9-7)和(5-3)小波濾波器，它們的為常數(shù)，而對于對稱性不好的D4小波濾波器而言，為多項式。 從例子可以看出，除了最后一步提升外，其他的提升和對偶提升步驟都是用奇序列中的一項來預(yù)測偶序列中的一項，或用偶序列中的一項來更新奇序列中的一項。計算過程只是用簡單的乘法運算和加減運算得到，計算復(fù)雜度非常低。對于具有線性相位的小波濾波器，所有的提升步驟都是通過簡單單項乘法及加法得到，完全去除了傳統(tǒng)提升運算中的卷積運算，更加有利于軟硬件的實現(xiàn)。 另外，當(dāng)(9-7)和(5-3)這些具有線性相位的濾波器用于處理信號時，采用對稱周期延拓的信號邊界處理方法則不僅可實現(xiàn)小波變換的完全重構(gòu)，同時又不增加變換后的數(shù)據(jù)量。§3.8整數(shù)小波變換 數(shù)字圖像都是用整數(shù)來表示其象素值的，而小波濾波器表示卻具有浮點數(shù)系數(shù)。對數(shù)字圖像進行小波變換處理后數(shù)據(jù)，即得到的小波系數(shù)不再為整數(shù)。由于用二進制來表示浮點數(shù)的精度有限，因而經(jīng)過小波變換后得到的小波系數(shù)重構(gòu)時，就會有能量損失。因此，當(dāng)人們想對數(shù)字圖像進行無損壓縮時，就希望變換后的小波系數(shù)仍為整數(shù)。提升算法可以十分方便的構(gòu)造整數(shù)到整數(shù)的小波變換。將整數(shù)小波變換應(yīng)用于圖像壓縮就可以實現(xiàn)無失真的圖像壓縮。該算法是通過在忽略歸一化因子的情況下，將算子作用于每一個提升步驟中的算子和實現(xiàn)的。而向下取整算子“”是非線性的，因此，整數(shù)小波變換是非線性變換。利用例3.8中結(jié)果，給出(9-7)小波變換基于本文算法的整數(shù)提升形式為 通過上面的討論我們可以知道，從多分辨分析的尺度函數(shù)或直接從濾波器出發(fā)可以構(gòu)造出具有緊支撐性的雙正交小波基；并在傳統(tǒng)小波變換的提升算法的基礎(chǔ)上，給出了一種新的提升算法。該算法在計算復(fù)雜度上較傳統(tǒng)算法略微下降，但在軟硬件實現(xiàn)方面更加簡單。§3.9本章小結(jié)本章介紹了小波變換的提升理論，通過分析傳統(tǒng)小波提升變換的不足，提出了一種小波變換的簡化提升格式。具體就是在傳統(tǒng)的Laurent多項式Euclidean算法的基礎(chǔ)上，通過重新定義Laurent多項式除法，給出了一種改進的Laurent多項式的Euclidean算法，并在該算法的基礎(chǔ)上提出了一種小波變換提升格式實現(xiàn)的簡化算法。在該提升實現(xiàn)算法中，用簡單的數(shù)乘運算代替了原來小波變換提升實現(xiàn)算法中的卷積運算，使得算法中的核心部分——提升及對偶提升步驟的計算更加簡單直接，更加易于硬件實現(xiàn)。本章的最后，給出了傳統(tǒng)提升小波變換算法與本文的簡化提升算法的實例。通過實例對比可以看出，對于一般的小波濾波器，簡化算法中的卷積運算除了最后一步提升或?qū)ε继嵘猓渌嵘蛯ε疾襟E中都沒有卷積運算；而對于具有線形相位的小波濾波器（如常用于圖像有損壓縮的(9-7)濾波器），簡化提升算法的每一提升和對偶提升步驟都是通過簡單的一次加法和一次乘法運算完成，完全去除了復(fù)雜的