雙正交小波變換提升格式的簡(jiǎn)化算法

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