基于gröbner基的多通道iir圖像的反卷積問題的求解【開題報告+文獻(xiàn)綜述+畢業(yè)論文】

1、<p><b>　　畢業(yè)論文開題報告</b></p><p><b>　　數(shù)學(xué)與應(yīng)用數(shù)學(xué)</b></p><p>　　基于Gröbner基的多通道IIR圖像的反卷積問題的求解</p><p><b>　　選題的背景與意義</b></p><p>　　在科學(xué)研

2、究和工程應(yīng)用的很多問題都要涉及到卷積的概念。用儀器來觀測記錄某個物理現(xiàn)象時，所得到的數(shù)據(jù)不僅反映物理現(xiàn)象本身，同時也反映儀器的特性。而儀器的非理性特性會使得到的數(shù)據(jù)降質(zhì)。這在數(shù)學(xué)上可以用卷積來描述，出于這種失真情況，，我們把觀測數(shù)據(jù)還原成真實(shí)數(shù)據(jù)，就是所謂的反卷積問題。根據(jù)采集觀測數(shù)據(jù)的儀器的個數(shù)，可以把反卷積問題分為單通道反卷積和多通道反卷積。單通道反卷積理論已經(jīng)十分成熟，然而，單通道反卷積問題一般來說具有病態(tài)性。多通道濾波可以有效避

3、免該問題，因此多通道濾波的應(yīng)用日漸廣泛。目前在國際上提供了一種在反卷積可逆情況下計算反卷積的有效的算法。然而，鑒于很多卷積是不可逆的，因此如何找出不可逆卷積的反卷積就有了它的意義。運(yùn)用Grobner基理論可以解決這一問題。</p><p>　　二、研究的基本內(nèi)容與擬解決的主要問題：</p><p><b>　　基本內(nèi)容:</b></p><p>

4、;　　在處理圖像過程中，利用儀器（相機(jī)或傳感器等）獲得的信號（圖像信號，視頻信號等）通過儀器的特性和真實(shí)信號疊加作用得到的是觀測信號。這其中的過程在數(shù)學(xué)上可以看成是卷積的過程。本課題要研究的內(nèi)容就是處理一些圖像，把被降質(zhì)的觀測信號還原成真實(shí)信號。這就需要構(gòu)造濾波器使各種卷積問題都能得到它的反卷積，從而來使信號精確或近似的還原。</p><p><b>　　主要問題：</b></p>

5、;<p>　　找到“z域”中構(gòu)造低通濾波器的方法。</p><p>　　利用Groebner基理論求解多通道IIR圖像的反卷積問題。</p><p>　　三、研究的方法與技術(shù)路線：</p><p>　　學(xué)習(xí)數(shù)字圖像相關(guān)方面的知識，了解濾波器，反濾波的相關(guān)內(nèi)容。研究“z域”中構(gòu)造低通濾波器組的方法，結(jié)合Grobner基理論，研究低通近似逆濾波器組的求解問

6、題。</p><p>　　四、研究的總體安排與進(jìn)度：</p><p>　　2011年1月之前：學(xué)習(xí)基礎(chǔ)理論（多通道濾波、Groebner基）；</p><p>　　2011年2月：研究“z域”中構(gòu)造低通濾波器的方法；</p><p>　　2011年3月：結(jié)合Groebner基理論，研究低通近似逆濾波器組的求解問題；</p>&l

7、t;p>　　2011年4月：解決一些細(xì)節(jié)問題，并撰寫論文，準(zhǔn)備答辯。</p><p><b>　　五、主要參考文獻(xiàn)：</b></p><p>　　[1] 章毓晉. 圖像工程（上冊）——圖像處理. 清華大學(xué)出版社，2006.3.</p><p>　　[2] 章毓晉. 圖像工程（中冊）——圖像處理. 清華大學(xué)出版社，2006.3.</p

8、><p>　　[3] 章毓晉. 圖像工程（下冊）——圖像理解. 清華大學(xué)出版社，2007.2.</p><p>　　[4] Zhou Jianping and Minh N. Do. Multidimensional multichannel FIR deconvolution using Grobner bases. Ieee Transactions on Image Proces

9、sing, 15(10):2998–3007, October 2006.</p><p>　　[5] G.Harikumar and Y.Bresler. "FIR perfect signal reconstrustion from multiple convolutions:Minimum deconvover orders",IEEE Trans.Image Process.,v

10、ol.46,no.1,pp.215-218,Jan.1998.</p><p>　　[6] H.Park,T.Kalker,and M.Vetterli,"Gröbner bases and multidimensional FIR multirate systems",Multidimen.Syst.Signal Process.,vol.8,pp.11-30,1997.</

11、p><p><b>　　畢業(yè)論文文獻(xiàn)綜述</b></p><p><b>　　數(shù)學(xué)與應(yīng)用數(shù)學(xué)</b></p><p><b>　　圖像處理技術(shù)</b></p><p>　　人們75%的信息從圖像里獲得。在現(xiàn)實(shí)生活中，人們都喜歡用相機(jī)拍攝下旅途中優(yōu)美的景色，用DV記錄下生活中某些感人

12、的細(xì)節(jié)。各種各樣的儀器的出現(xiàn)，使得我們能夠把自然界和生活中的景象事物，用圖像信號，視頻信號或者音頻信號保存下來。數(shù)碼相機(jī)等數(shù)字產(chǎn)品的出現(xiàn)，使得圖像信號等能轉(zhuǎn)化為數(shù)字信號。地球數(shù)字化帶來的任務(wù)，一方面要求處理對象的數(shù)字性，一方面也要求處理的直觀性。因此也給我?guī)砹嗽S多研究課題和方向如：圖像的處理技術(shù)，圖像的自我識別，圖像的安全技術(shù)等等。本課題主要是要研究數(shù)字圖像處理技術(shù)，并應(yīng)用它來處理一些圖像。</p><p>　

13、　《圖像工程》介紹到數(shù)字圖像處理的發(fā)展概況：1、二十世紀(jì)二十年代：圖像遠(yuǎn)距離傳輸。2、二十世紀(jì)五十年代：數(shù)字計算機(jī)發(fā)展到一定水平，數(shù)字圖像處理技術(shù)引起巨大關(guān)注。3、二十世紀(jì)六十年代末：數(shù)字圖像處理較完整的理論體系形成，成為一門新興的學(xué)科。4、二十世紀(jì)八十年代以來：數(shù)字圖像處理想更高級的方向發(fā)展：智能化，普及化，體成本，實(shí)時性。</p><p>　　這里我主要想運(yùn)用數(shù)學(xué)知識結(jié)合圖像處理技術(shù)來處理一些圖像，這就首先要

14、用到卷積的概念。卷積概念被廣泛運(yùn)用于科學(xué)研究和工程應(yīng)用的很多問題，特別在圖像信號處理工程中。用儀器來觀測記錄某個物理現(xiàn)象時，所得到的數(shù)據(jù)不僅反映物理現(xiàn)象本身，同時也反映儀器的特性。而儀器的非理性特性會使得到的數(shù)據(jù)降質(zhì)。這在數(shù)學(xué)上可以用卷積來描述，出于這種失真情況，，我們需要把觀測數(shù)據(jù)還原成真實(shí)數(shù)據(jù)，就是所謂的反卷積問題。根據(jù)采集觀測數(shù)據(jù)的儀器的個數(shù)，可以把反卷積問題分為單通道反卷積和多通道反卷積。單通道反卷積理論已經(jīng)十分成熟，然而，單通

15、道反卷積問題一般來說具有病態(tài)性，因?yàn)閱蝹€函數(shù)的系統(tǒng)函數(shù)的極點(diǎn)掩蓋了部分真實(shí)信號，使其無法還原。這就需要構(gòu)造出一類濾波器，過濾掉那些失真信號使其近似的還原成真實(shí)信號。多通道濾波可以有效避免該問題，再加上在過去十年，由于傳感器和計算元件成本的下降，使得多通道卷積構(gòu)造變的可行和普遍，多通道濾波日漸發(fā)展。</p><p>　　Harikumai和Bresler研究卷積和反卷積濾波器都是FIR的多通道1-D和2-D的精確反

16、卷積問題。他們得出，在沒有疊加噪音的影響下，復(fù)原信號和原始信號是相同的。</p><p>　　這些精確反卷積法比傳統(tǒng)的最小二乘法有更高的計算效率。他們提出了一種基于線性代數(shù)理論來計算反卷積濾波器組的方法，但這種方法需要對濾波器的前導(dǎo)支撐進(jìn)行預(yù)估，而這在大部分實(shí)際應(yīng)用中難于做到。而且，盡管他們提出了一些對1-D和2-D濾波器的預(yù)估算法，但這些預(yù)估濾波器都很大，尤其是當(dāng)卷積濾波器組的支撐數(shù)不同的時候。</p&g

17、t;<p>　　代數(shù)幾何理論的Gröbner基方法是處理多元多項式系統(tǒng)的很有用的工具，并被廣泛應(yīng)用在多維信號處理過程中。Rajagopal和Potter利用Gröbner基方法來求解逆濾波器組則可以完全解決上述線性代數(shù)方法的兩大弊端。然而，他們考慮的只是多項式形式和隨機(jī)的濾波器組，相對的，Jianping Zhou和Minh N.Do更進(jìn)一步，考慮的是一般的FIR濾波器。</p><

18、p>　　為了應(yīng)用代數(shù)幾何，需要把FIR形式轉(zhuǎn)化成多項式形式。一個直接的方法是用一個足夠高次的單項式去乘以FIR濾波器。然而這一方法仍然需要預(yù)先信息或者要計算反卷積濾波器的轉(zhuǎn)換矩陣。</p><p>　　Park提供了一種算法把FIR問題轉(zhuǎn)化成多項式問題，參見[4]。可惜的是，這種方法包含了復(fù)雜的轉(zhuǎn)換矩陣，計算工程量也比較大。</p><p>　　因此，Jianping Zhou和Mi

19、nh N.Do提供了一種用代數(shù)幾何理論來解決一般的多維多通道FIR反卷積問題的新方法。主要貢獻(xiàn)在于他們把反卷積問題通過引入一個新的變量簡單的轉(zhuǎn)化成了多項式問題。然后，他們提出了FIR反卷積濾波器的存在條件并提出一個基于Gröbner基的簡單的算法來計算反卷積濾波器。不同于上述方法的是他們的方法不需要關(guān)于濾波的任何預(yù)先信息，并且能得到一組較好的反卷積濾波器。</p><p>　　然而，考慮到FIR可逆條件

20、的嚴(yán)格性，很多卷積濾波組是FIR不可逆的,又因?yàn)镮IR濾波器在很多方面比FIR濾波器更好,所以在本文中研究的是IIR濾波器組和它的逆濾波器組。</p><p><b>　　主要參考文獻(xiàn)：</b></p><p>　　[1] 章毓晉. 圖像工程（上冊）——圖像處理. 清華大學(xué)出版社，2006.3.</p><p>　　[2] 章毓晉. 圖像工程（

21、中冊）——圖像處理. 清華大學(xué)出版社，2006.3.</p><p>　　[3] 章毓晉. 圖像工程（下冊）——圖像理解. 清華大學(xué)出版社，2007.2.</p><p>　　[4] Zhou Jianping and Minh N. Do. Multidimensional multichannel FIR deconvolution using Grobner bases. Iee

22、e Transactions on Image Processing, 15(10):2998–3007, October 2006.</p><p>　　[5] G.Harikumar and Y.Bresler. "Exact image deconvolution from multiple FIR blurs",IEEE Trans.Image Process.,vol.8,no.6,

23、pp.846-862,Jun,1999.</p><p>　　[6] G.Harikumar and Y.Bresler. "FIR perfect signal reconstrustion from multiple convolutions:Minimum deconvover orders",IEEE Trans.Image Process.,vol.46,no.1,pp.215-2

24、18,Jan.1998.</p><p>　　[7] H.Park,T.Kalker,and M.Vetterli,"Gröbner bases and multidimensional FIR multirate systems",Multidimen.Syst.Signal Process.,vol.8,pp.11-30,1997.</p><p>&l

25、t;b>　　本科畢業(yè)設(shè)計</b></p><p><b>　?。?0 屆）</b></p><p>　　基于Gröbner基的多通道IIR圖像的反卷積問題的求解</p><p><b>　　摘　要</b></p><p>　　【摘要】本文旨在運(yùn)用Gröbner

26、基理論提出一種求解反卷積問題的新方法。根據(jù)卷積濾波器組的性質(zhì)，反卷積濾波可能是FIR也可能是IIR的。在這之前的求解反卷積問題的算法，僅僅對某些存在FIR反卷積的濾波器適用。本文對其做了擴(kuò)展，提出的新算法適用于任意的濾波器組。利用代數(shù)幾何的Gröbner基理論，本文提出了濾波器可逆性的判定定理，并提供了一種有效的求解反卷積的算法。該方法的求解過程僅僅依賴原濾波器組本身，而不需要估計預(yù)先輸出信號，同時該方法也能夠找到比較簡單的逆

27、濾波器組。模擬結(jié)果顯示，用該方法得到的復(fù)原圖像效果良好。 </p><p>　　【關(guān)鍵詞】反卷積；Gröbner基；根理想；多通道圖像處理；IIR。</p><p><b>　　Abstract</b></p><p>　　【ABSTRACT】This paper aims at providing a new method base

28、d on Gröbner bases to generate deconvolution filters from any convolution filter bank. The result deconvolution filters may be FIR or IIR according to the convolution filter bank`s property. Previous work only can p

29、rocess few filter banks that have FIR deconvolution filters. Our new method is extended to adapt for all kind of filter banks. Using Gröbner bases and algebraic geometry theory , a criterion theorem on the invertibi

30、lity of filter</p><p>　　【KEYWORDS】Gröbner bases；radical ideal；multichannel image processing;infinite impulse response(IIR)。</p><p><b>　　目　錄</b></p><p><b>　　摘　

31、要VII</b></p><p>　　AbstractVII</p><p><b>　　目　錄VIII</b></p><p><b>　　1緒論9</b></p><p><b>　　1.1引言9</b></p><p>　

32、　1.2研究背景9</p><p><b>　　2預(yù)備知識11</b></p><p><b>　　2.1圖像11</b></p><p>　　2.2圖像處理發(fā)展概況11</p><p><b>　　2.3卷積12</b></p><p&

33、gt;　　2.3.1卷積定義12</p><p>　　2.4Z變換和反卷積12</p><p>　　2.4.1Z變換12</p><p>　　2.4.2反卷積描述13</p><p>　　2.5濾波器13</p><p>　　2.5.1濾波器定義13</p><p>　　

34、2.5.2FIR和IIR濾波器14</p><p>　　2.6Gröbner基理論14</p><p>　　2.6.1Gröbner基14</p><p>　　2.6.2根理想15</p><p>　　2.6.3Buchberger算法15</p><p>　　3反卷積問題的求

35、解16</p><p>　　3.1具體求解16</p><p><b>　　3.2算法18</b></p><p><b>　　4模擬實(shí)驗(yàn)19</b></p><p><b>　　5結(jié)論21</b></p><p>　　參考文獻(xiàn)（宋體，

36、加粗，小二號字，居中）22</p><p>　　致謝（宋體，加粗，小二號字，居中）錯誤!未定義書簽。</p><p>　　附錄（宋體，加粗，小二號字，居左）錯誤!未定義書簽。</p><p><b>　　緒論</b></p><p><b>　　引言</b></p><p&

37、gt;　　在科學(xué)研究和實(shí)際工程應(yīng)用中，很多問題都會涉及到卷積的概念。用一個儀器來觀測和記錄一個物理現(xiàn)象和過程時，所得到的觀測和記錄不僅僅反映物理現(xiàn)象和過程，還反映儀器的特性。儀器系統(tǒng)的非理想特性會使得到的觀測和記錄降質(zhì)。這種機(jī)制在數(shù)學(xué)上可以用卷積來描述。正是因?yàn)檫@種在觀測過程中出現(xiàn)的降質(zhì)的情況，我們需要從觀測數(shù)據(jù)和儀器的特性出發(fā)，來還原真實(shí)數(shù)據(jù)，這就是反卷積問題。傳統(tǒng)的單通道反卷積問題已經(jīng)被廣泛的研究，然而，在一般情況下，單通道反卷積問

38、題往往是病態(tài)的，原因在于單個儀器的系統(tǒng)函數(shù)的極點(diǎn)會掩蓋部分真實(shí)信號，使其無法被還原。多通道濾波可以有效避免這問題，因此越來越多的人開始關(guān)注多通道反卷積問題，再加之最近幾年傳感器和計算元件成本的下降，也為多通道濾波的發(fā)展提供了有力條件。多通道反卷積的主要目的是要把原始信號從多通道的輸出信號中復(fù)原出來。根據(jù)卷積濾波器是否已知，反卷積問題可以分成兩種：常規(guī)的和盲目的。這里，我們關(guān)注常規(guī)的反卷積問題，也就是卷積濾波器是已知或已被計算出了的。&l

39、t;/p><p><b>　　研究背景</b></p><p>　　Harikumai和Bresler研究卷積和反卷積濾波器都是FIR的多通道1-D和2-D的精確反卷積問題。他們得出，在沒有疊加噪音的影響下，復(fù)原信號和原始信號是相同的。具體參見參考文獻(xiàn)[1]，[2]。</p><p>　　這些精確反卷積法比傳統(tǒng)的最小二乘法有更高的計算效率。他們提出

40、了一種基于線性代數(shù)理論來計算反卷積濾波器組的方法，但這種方法需要對濾波器的前導(dǎo)支撐進(jìn)行預(yù)估，而這在大部分實(shí)際應(yīng)用中難于做到。而且，盡管他們提出了一些對1-D和2-D濾波器的預(yù)估算法，但這些預(yù)估濾波器都很大，尤其是當(dāng)卷積濾波器組的支撐數(shù)不同的時候。</p><p>　　代數(shù)幾何理論的Gröbner基方法是處理多元多項式系統(tǒng)的很有用的工具，并被廣泛應(yīng)用在多維信號處理過程中。Rajagopal和Potter利

41、用Gröbner基方法來求解逆濾波器組則可以完全解決上述線性代數(shù)方法的兩大弊端。然而，他們考慮的只是多項式形式和隨機(jī)的濾波器組，相對的，Jianping Zhou和Minh N.Do更進(jìn)一步，考慮的是一般的FIR濾波器。</p><p>　　為了應(yīng)用代數(shù)幾何，需要把FIR形式轉(zhuǎn)化成多項式形式。一個直接的方法是用一個足夠高次的單項式去乘以FIR濾波器，具體參見參考文獻(xiàn)[3]。</p><

42、;p>　　然而這一方法仍然需要預(yù)先信息或者要計算反卷積濾波器的轉(zhuǎn)換矩陣。</p><p>　　Park提供了一種算法把FIR問題轉(zhuǎn)化成多項式問題，參見[4]?？上У氖?，這種方法包含了復(fù)雜的轉(zhuǎn)換矩陣，計算工程量也比較大。</p><p>　　因此，Jianping Zhou和Minh N.Do提供了一種用代數(shù)幾何理論來解決一般的多維多通道FIR反卷積問題的新方法。主要貢獻(xiàn)在于他們把反卷

43、積問題通過引入一個新的變量簡單的轉(zhuǎn)化成了多項式問題。然后，他們提出了FIR反卷積濾波器的存在條件并提出一個基于Gröbner基的簡單的算法來計算反卷積濾波器。不同于上述方法的是他們的方法不需要關(guān)于濾波的任何預(yù)先信息，并且能得到一組較好的反卷積濾波器。</p><p>　　然而，考慮到FIR可逆條件的嚴(yán)格性，很多卷積濾波組是FIR不可逆的,又因?yàn)镮IR濾波器在很多方面比FIR濾波器更好,所以在本文中研究的

44、是IIR濾波器組和它的逆濾波器組。</p><p>　　IIR濾波器經(jīng)過z變換后是有理函數(shù)。雖然代數(shù)幾何和Gröbner基是直接應(yīng)用在多項式系統(tǒng)中的，但經(jīng)過簡單的轉(zhuǎn)化也可以運(yùn)用到有理函數(shù)系統(tǒng)中。具體參見參考文獻(xiàn)[5]</p><p>　　本文主要包括兩個工作：第一，給出了判定卷積濾波器組是否可逆的判定定理，第二，提供了一種計算反卷積濾波器組的新算法。</p><

45、;p>　　用根理想可以很容易的判定一個濾波器組是多項式，F(xiàn)IR或IIR可逆的。再運(yùn)用Buchberge算法，我們就可以算出相應(yīng)的反卷積。提供的算法適用于所有種類的卷積濾波器組并能得到包含更少項的反卷積。而且，通過這種算法得到的反卷積復(fù)原效果良好。</p><p><b>　　預(yù)備知識</b></p><p><b>　　圖像</b><

46、/p><p>　　圖像是用各種觀測系統(tǒng)以不同形式和手段觀測客觀世界而獲得的，可以直接或間接的作用于人眼并進(jìn)而產(chǎn)生視知覺的實(shí)體。</p><p><b>　　圖像的表示</b></p><p>　　一副圖像一般可以用一個2-D函數(shù)來表示，這里x和y表示2-D空間XY中一個坐標(biāo)點(diǎn)的位置，而f則表示圖像在點(diǎn)（x,y）的某種性質(zhì)F的值。日常所見的圖像多是連

47、續(xù)的。而我們討論的是離散化的圖像，也就是數(shù)字圖像。</p><p>　　一副圖像可分解為許多個單位，每個基本單位叫做圖像元素，簡稱像素。要表示圖像就需要表示其各個像素，對像素也可用f(x,y)來表示。比較直觀的，一副圖像可表示為一個2-D的的矩陣（其中每個元素表示一個像素，M和N為別為圖像的行數(shù)和列數(shù)）：</p><p><b>　　。</b></p>

48、<p><b>　　圖像處理發(fā)展概況</b></p><p>　　圖像處理是指將圖像信號轉(zhuǎn)換成數(shù)字信號并利用計算機(jī)對其進(jìn)行處理的過程。圖像處理最早出現(xiàn)于20世紀(jì)50年代，當(dāng)時的電子計算機(jī)已經(jīng)發(fā)展到一定水平，人們開始利用計算機(jī)來處理圖形和圖像信息。數(shù)字圖像處理作為一門學(xué)科大約形成于20世紀(jì)60年代初期。早期的圖像處理的目的是改善圖像的質(zhì)量，它以人為對象，以改善人的視覺效果為目的。圖像

49、處理中，輸入的是質(zhì)量低的圖像，輸出的是改善質(zhì)量后的圖像，常用的圖像處理方法有圖像增強(qiáng)、復(fù)原、編碼、壓縮等。首次獲得實(shí)際成功應(yīng)用的是美國噴氣推進(jìn)實(shí)驗(yàn)室（JPL）。他們對航天探測器徘徊者7號在1964年發(fā)回的幾千張月球照片使用了圖像處理技術(shù)，如幾何校正、灰度變換、去除噪聲等方法進(jìn)行處理，并考慮了太陽位置和月球環(huán)境的影響，由計算機(jī)成功地繪制出月球表面地圖，獲得了巨大的成功。隨后又對探測飛船發(fā)回的近十萬張照片進(jìn)行更為復(fù)雜的圖像處理，以致獲得了月

50、球的地形圖、彩色圖及全景鑲嵌圖，獲得了非凡的成果，為人類登月創(chuàng)舉奠定了堅實(shí)的基礎(chǔ)，也推動了數(shù)字圖像處理這門學(xué)科的誕生。在以后的宇航空間技術(shù)，如對火星、土星等星球的探測研究中，數(shù)字圖像處理技術(shù)都發(fā)揮了巨大的作用。 數(shù)字圖像處理取得的另一個巨大成</p><p><b>　　卷積</b></p><p>　　研究和工程的許多問題都要涉及到卷積的概念。用一個儀器來觀測和記錄

51、一個物理現(xiàn)象和過程時，所得到的觀測和記錄不僅僅反映物理現(xiàn)象和過程，還反映儀器的特性。儀器系統(tǒng)的非理想特性會使得到的觀測和記錄降質(zhì)。這種機(jī)制在數(shù)學(xué)上可以用卷積來描述。</p><p><b>　　卷積定義</b></p><p>　　函數(shù)f與g的卷積記作，它是其中一個函數(shù)翻轉(zhuǎn)平移后與另一個函數(shù)的乘積的積分，是一個對平移量的函數(shù)。定義為：,積分區(qū)間取決于f與g的定義域。&

52、lt;/p><p>　　對于定義在離散域的函數(shù)，卷積的定義為：。</p><p>　　由卷積得到的函數(shù)一般比和要光滑。在圖像處理中兩組幅分辨率不同的圖卷積之后得到的互相平滑的圖像可以方便處理 。</p><p><b>　　Z變換和反卷積</b></p><p><b>　　Z變換</b></p&

53、gt;<p>　　Z變換（Z-transformation）， 是對離散序列進(jìn)行的一種數(shù)學(xué)變換。常用以求線性時不變差分方程的解。它在離散時間系統(tǒng)中的地位，如同拉普拉斯變換在連續(xù)時間系統(tǒng)中的地位。這一方法 ( 即離散時間信號的Z變換)已成為分析線性時不變離散時間系統(tǒng)問題的重要工具。在數(shù)字信號處理、計算機(jī)控制系統(tǒng)等領(lǐng)域有廣泛的應(yīng)用。</p><p>　　為了運(yùn)用Gröbner基理論，數(shù)字信號必

54、須先轉(zhuǎn)化成多項式或有理函數(shù)方程。z變換是最好的選擇。和一般的z變換的定義不同，以下的的定義是適用于Gröbner基理論的。在下述定義中中黑體表示向量，集合和矩陣。Z，Z+，和C表示整數(shù)集，非負(fù)整數(shù)和復(fù)數(shù)。</p><p>　　定義1：設(shè)是一個在上的m維向量，是在上的m維向量， 那么我們約定：。</p><p>　　定義2：對于一個m維數(shù)字信號x(k),k,可以表示成</p&

55、gt;<p>　　我們用大寫字母用來表示相應(yīng)數(shù)字信號的z變換，為了簡便也省略掉自變量z，如系統(tǒng)函數(shù)h(k)，可以表示為H（z）或H。</p><p><b>　　反卷積描述</b></p><p>　　假設(shè){H1,…，Hn}是卷積濾波器，{G1，…，Gn}是反卷積濾波器，那么反卷積問題可以表示為 </p><p>　　其中 是第

56、i個濾波器的輸出信號，X（z）是原始信號。因此，在精確和沒有噪音的環(huán)境下，復(fù)原的信號必須和原始信號X相等。所以，精確的反卷積問題就是尋找一組，使得</p><p><b>　?。?）</b></p><p><b>　　成立。</b></p><p><b>　　濾波器</b></p>

57、<p><b>　　濾波器定義</b></p><p>　　濾波器，顧名思義，是對波進(jìn)行過濾的器件?！安ā笔且粋€非常廣泛的物理概念，在電子技術(shù)領(lǐng)域，“波”被狹義地局限于特指描述各種物理量的取值隨時間起伏變化的過程。該過程通過各類傳感器的作用，被轉(zhuǎn)換為電壓或電流的時間函數(shù)，稱之為各種物理量的時間波形，或者稱之為信號。因?yàn)樽宰兞繒r間‘是連續(xù)取值的，所以稱之為連續(xù)時間信號，又習(xí)慣地稱之為

58、模擬信號(Analog Signal)。隨著數(shù)字式電子計算機(jī)(一般簡稱計算機(jī))技術(shù)的產(chǎn)生和飛速發(fā)展，為了便于計算機(jī)對信號進(jìn)行處理，產(chǎn)生了在抽樣定理指導(dǎo)下將連續(xù)時間信號變換成離散時間信號的完整的理論和方法。也就是說，可以只用原模擬信號在一系列離散時間坐標(biāo)點(diǎn)上的樣本值表達(dá)原始信號而不丟失任何信息，波、波形、信號這些概念既然表達(dá)的是客觀世界中各種物理量的變化，自然就是現(xiàn)代社會賴以生存的各種信息的載體。信息需要傳播，靠的就是波形信號的傳遞。信號

59、在它的產(chǎn)生、轉(zhuǎn)換、傳輸?shù)拿恳粋€環(huán)節(jié)都可能由于環(huán)境和干擾的存在而畸變，有時，甚至是在相當(dāng)多的情況下，這種畸變還很嚴(yán)重，以致于信號及其所攜帶的信息被深深地埋在噪聲當(dāng)中了。濾波，本質(zhì)上是從被噪聲畸變和污染了的信號中提取原始信號所攜帶的信息的過</p><p>　　FIR和IIR濾波器</p><p>　　無限脈沖響應(yīng)濾波器是數(shù)位濾波器的一種，簡稱IIR數(shù)位濾波器(infinite impulse

60、 response filter)。由于無限脈沖響應(yīng)濾波器中存在反饋回路，因此對于脈沖輸入信號的響應(yīng)是無限延續(xù)的。有限脈沖響應(yīng)濾波器是數(shù)字濾波器的一種，簡稱FIR數(shù)字濾波器（finite impulse response filter）。這類濾波器對于脈沖輸入信號的響應(yīng)最終趨向于0，因此是有限的，而得名。它是相對于無限脈沖響應(yīng)濾波器(IIR)而言。有限脈沖響應(yīng)濾波器（FIR filter）的優(yōu)點(diǎn)：</p><p>

61、;　　1.脈沖響應(yīng)（impulse response）為有限長：造成當(dāng)輸入數(shù)位訊號為有限長的時候，輸出數(shù)位訊號也為有限長。</p><p>　　2.比無限脈沖響應(yīng)濾波器（IIR filter）較容易最佳化（optimize）。</p><p>　　3.線性相位（linear phase）：造成h(n)\,是偶對稱（even）或奇對稱（odd）且有限長。</p><p&g

62、t;　　4.一定是穩(wěn)定的（stable）：因?yàn)閆轉(zhuǎn)換（Z transform）后所有的極點(diǎn)（pole）都在單位圓內(nèi)。</p><p>　　有限脈沖響應(yīng)濾波器（FIR filter）的缺點(diǎn)：</p><p>　　設(shè)計方式較無限脈沖響應(yīng)濾波器（IIR filter）不容易。</p><p>　　無限脈沖響應(yīng)濾波器(IIR filter)的優(yōu)點(diǎn)：</p>&

63、lt;p>　　較容易設(shè)計以及實(shí)現(xiàn)。</p><p>　　無限脈沖響應(yīng)濾波器(IIR filter)的缺點(diǎn)：</p><p>　　1.脈沖響應(yīng)(impulse response)為無限長：造成當(dāng)輸入數(shù)位訊號為有限長的時候，輸出數(shù)位訊號會變成無限長。</p><p>　　2.比有限脈沖響應(yīng)濾波器(FIR filter)較不易最佳化(optimize)。</p

64、><p>　　3.不一定是穩(wěn)定的(stable)：因?yàn)閆轉(zhuǎn)換(Z transform)后所有的極點(diǎn)(pole)不一定都在單位圓內(nèi)。</p><p>　　Gröbner基理論</p><p><b>　　Gröbner基</b></p><p>　　Gröbner基理論的本質(zhì)是從多變元多項式環(huán)中任

65、一理想的一組生成元出發(fā)，刻化和計算出一組具有“好的”性質(zhì)的生成元，而具有“好的”性質(zhì)的生成元，可幫助我們研究理想的結(jié)構(gòu)和進(jìn)行某些理想運(yùn)算。</p><p>　　定義： 設(shè)I是環(huán)A中任意給定的一個非零理想，是I中非零多項式的有限集合。我們稱G是理想I的Gröbner基，當(dāng)且僅當(dāng)對I中的每個非零多項式f，存在i,,使得。</p><p><b>　　根理想</b>

66、;</p><p>　　定義3：由多項式組{H1,…,Hn}生成的多項式理想I可以寫為</p><p>　　定義4：令I(lǐng)是一個理想。理想I的根記為,定義為=。</p><p>　　容易得出，也是一個理想。特別的，若，則稱I為根理想。</p><p>　　代數(shù)幾何里的一個基本問題就是判斷理想成員問題，即對于任意一個給定的多項式f,判定它是否屬于

67、理想I，也就是是否存在一組多項式{G1，…，Gn}，使得。這可以運(yùn)用Gröbner基來解決。一個理想有多個Gröbner基，但只有一個即約Gröbner基。Buchberger算法能用來計算生成Gröbner基相應(yīng)的轉(zhuǎn)化矩陣 。例如，給定一個多項式組，存在一組Gröbner基和一個的轉(zhuǎn)換矩陣，使得</p><p><b>　　。</b><

68、;/p><p>　　Buchberger算法</p><p>　　Buchberger算法：</p><p>　　用途：求解理想的Gröbner基</p><p><b>　　輸入：</b></p><p>　　輸出：，一個Gröbner基，使得。</p><p

69、><b>　　初始：</b></p><p><b>　　WHILE DO</b></p><p><b>　　任意選擇</b></p><p><b>　　IF THEN</b></p><p>　　證明：在次簡單證明Buchberger算法的

70、正確性。如果算法有限步停止，則輸出的有限集合G必然滿足如下性質(zhì)：（1）；（2）對任意，則。因此由 定理：設(shè)I是的理想，是I的有限子集合，則G是I的Gröbner基，當(dāng)且僅當(dāng) 成立。知，G是Gröbner基。所以只要證明Buchberger算法有限步停止。設(shè)算法中第i步的集合G是，其中是添加了一個不能被約化的元素，因此有 由Hilbert基本定理，存在使得。因此Buchberger算法在t步就停止了。這就證明了Buc

71、hberger算法的正確性。</p><p><b>　　反卷積問題的求解</b></p><p><b>　　具體求解</b></p><p>　　為了更好的討論，我們先討論卷積濾波器是多項式的情況，先給出以下定義。</p><p>　　定義5：設(shè){H1,…,Hn}是一個多項式卷積濾波器組，{G1

72、,…,Gn}是相應(yīng)的滿足上述方程（1）的反卷積濾波器組。</p><p>　　如果所有的G1,…,Gn是可多項式，那么卷積濾波器組是多項式可逆的；</p><p>　　如果所有的G1,…,Gn是FIR的，那么卷積濾波器組是FIR可逆的；</p><p>　　如果所有的G1,…,Gn是IIR的，那么這卷積濾波器組是IIR可逆的。</p><p>

73、;　　明顯的，一個卷積{H1,…,Hn}一定能找到一個IIR的反卷積濾波器組。因此，我們可以說任何濾波器組都是IIR可逆的。但是，這一簡單的反卷積濾波器組只是簡單的N個單通道逆的組合，不能解決單通道反卷積的病態(tài)問題。所以，我們應(yīng)該找到一個穩(wěn)定的反卷積濾波器組。因?yàn)樗蠪IR濾波器都是穩(wěn)定的，所以很多人討論FIR的可逆性。但可惜的是，很多濾波器組不是FIR可逆的。而且，在某種等效性要求下，IIR濾波器通常比FIR濾波器更簡單，所以IIR反

74、卷積濾波器值得進(jìn)一步研究。</p><p>　　假設(shè)濾波器集合{H1,…,Hn}有IIR反卷積濾波器組,那么它們滿足。所以存在一個多項式F和整數(shù)m，使得 （2）</p><p>　　根據(jù)定義3，4，易知F屬于I=<H1,…,Hn>的根理想,所以我們一旦得到了I的根理想中的某個元素以及其對應(yīng)的多項式轉(zhuǎn)化矩陣，就能找到一個IIR反卷積濾波器組。也就是說是反卷積濾波器組。而且，如

75、果=1，則該反卷積濾波器組是多項式的，如果是一個單項式，則該反卷積濾波器組是FIR的。因此，我們就得到了濾波器組可逆性的判定定理。</p><p>　　定理 1 ：一個多項式濾波器組</p><p>　?。?）多項式可逆當(dāng)且僅當(dāng)它的根理想是<1>;</p><p>　　（2）FIR可逆當(dāng)且僅當(dāng)它的根理想包含一個單項式；</p><p&

76、gt;　?。?）總是IIR可逆的。</p><p>　　Hermann,Mines,Gianni等提供了計算根式理想的算法，參見[6],[7]-[9]。但用他們的算法很難去算出它的轉(zhuǎn)化多項式，因?yàn)檎麛?shù)m是未知的.下面提出的定理2能容易的解決這個問題。</p><p>　　定理 2 : F當(dāng)且僅當(dāng)常數(shù)多項式1屬于理想<H1,…,Hn,1-wF>(其中w是一個新的變量）。</

77、p><p><b>　　定理證明：充分性：</b></p><p><b>　　.</b></p><p><b>　　,</b></p><p>　　則 必存在一組,使得</p><p><b>　?。?）</b></p>

78、<p>　　令 ，則（1）變成：</p><p><b>　　，</b></p><p>　　即 ，根據(jù)根理想定義，F(xiàn)。</p><p><b>　　必要性: F</b></p><p>　　則 (2)</p><p>　　把（2）兩邊除以,得到&l

79、t;/p><p><b>　?。?）</b></p><p>　　現(xiàn)考慮零點(diǎn)集，則欲使上式有意義，則還應(yīng)滿足：</p><p>　　引入新的變量w，則零點(diǎn)集滿足上述要求。</p><p>　　此時（3）式等價于多項式1屬于理想<H1,…,Hn,1-wF>.。定理證畢。</p><p>　　

80、由這一定理，利用Buchberger算法計算<H1,…,Hn,1-wF>的即約Gröbner基同時能得到轉(zhuǎn)換矩陣 ,滿足:</p><p>　　令w=1/F,那么 ,集合就是反卷積濾波器組。這樣就避免了m的計算。</p><p>　　一般情況下當(dāng)濾波器是有理函數(shù)時，對其乘以一個多項式能使之變成多項式。然后用上面的方法就可以去找到反卷積濾波器。</p>&

81、lt;p><b>　　算法</b></p><p>　　把整個計算過程總結(jié)如下。</p><p>　　輸入：卷積濾波器組{H1,…,Hn}</p><p>　　輸出：反卷積濾波器組G={G1，…，Gn}</p><p>　　第一步：將H1,…,Hn分別乘以一個多項式H使之變成多項式。</p><

82、p>　　第二步：計算出I=<H1,…,Hn>的根理想,也就是。</p><p>　　第三步：從中找一個多項式F（比如次數(shù)最低的）</p><p>　　第四步：算出理想<H1,…,Hn,1-wF>的即約Gröbner基和</p><p><b>　　它的轉(zhuǎn)換矩陣 </b></p><p

83、>　　第五步：令w=1/F 就能得到</p><p>　　第六步：輸出G，G就是反卷積濾波器組。</p><p><b>　　模擬實(shí)驗(yàn)</b></p><p>　　本實(shí)驗(yàn)中,我們?nèi)V波器組如下：</p><p><b>　　,</b></p><p><b>

84、　　， </b></p><p><b>　　,</b></p><p>　　根據(jù)算法得到的逆濾波器組的z-變換為：</p><p><b>　　=6</b></p><p><b>　　;</b></p><p><b>　　.&

85、lt;/b></p><p>　　模擬的原圖為圖a。圖b,圖c,圖d,分別為經(jīng)濾波器H1，H2，H3濾波后且加入高斯噪音的結(jié)果，圖e為經(jīng)反濾波器組反卷積得到的結(jié)果。從圖像效果看，復(fù)原效果良好。</p><p>　　圖1 帶有噪音的模擬實(shí)驗(yàn)</p><p><b>　　5.結(jié)論</b></p><p>　　本文主要解

86、決了那些FIR不可逆的卷積濾波器的多通道圖像復(fù)原問題。通過z變換，數(shù)字信號被轉(zhuǎn)化為有理函數(shù)。這樣，多通道反卷積問題可以轉(zhuǎn)化到有理函數(shù)系統(tǒng)里解決了。再運(yùn)用Gröbner基理論和根理想，可以比較簡單的判定卷積濾波器的可逆性。本文提出的新算法不需要濾波器的預(yù)先響應(yīng)信號，而且能找到較小的反卷積濾波器組。而模擬實(shí)驗(yàn)的結(jié)果顯示，用這種方法得到的反卷積對圖像還原的質(zhì)量是很好的。</p><p>　　但因?yàn)镮IR濾波器

87、的穩(wěn)定性，一些病態(tài)的濾波器可能在存在噪音的環(huán)境中不能得到反卷積濾波器，所以IIR濾波器還需要在未來被更多的研究。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　G.Harikumar and Y.Bresler. "Exact image deconvolution from multiple FIR blurs",IEEE T

88、rans.Image Process.,vol.8,no.6,pp.846-862,Jun,1999.</p><p>　　G.Harikumar and Y.Bresler. "FIR perfect signal reconstrustion from multiple convolutions:Minimum deconvover orders",IEEE Trans.Image Pro

89、cess.,vol.46,no.1,pp.215-218,Jan.1998.</p><p>　　C.Caroenlarpnopparut and N.K.Bose,"Multidimensional FIR filter bank design using Gröbner bases",IEEE Trans.Circuits Syst.,vol.46,no.12,pp.1475-1

90、486,Dec.1999.</p><p>　　H.Park,T.Kalker,and M.Vetterli,"Gröbner bases and multidimensional FIR multirate systems",Multidimen.Syst.Signal Process.,vol.8,pp.11-30,1997.</p><p>　　Davi

91、d A.Cox,John Little,and Donal O`Shea.Ideals,Varieties,and Algorithms:An Introduction to Computational Algebraic Geometry and Commutative Algebra,3/e(Undergraduate Texts in Mathematics).Springer-Verlag New York,Inc.,Secau

92、cus,NJ,USA,2007</p><p>　　T.Becker and V.Weispfenning.Gröbner Bases. Springer-Verlag New York-Berlin-Heidelberg,1993.</p><p>　　Hermamn.Der frage der endlich vielen schritte in der theorie de

93、r polynomideale. Math.Annalen,pp.736-788,1926.</p><p>　　P.Gianni,B.Trager,and G. Zacharias. Gröbner bases and primary decomposition of polynomial ideals. Journal of Symbolic Computation,pp.149-167,1988.

94、</p><p>　　D.Eisenbud,C.Huneke,and W.Vasconcelos. Direct methods for primary decomposition. Invent.Math.,pp.207-235,1992.</p><p>　　Zhou Jianping and Minh N.Do. Multidimensional multichannel FIR d

95、econvolution using Gröbner bases. IEEE Transsactions on Image Processing,pp.2998-3007,Oct.2006.</p><p>　　R.Rajagopal and L.C.Potter,"Multi-channel multi-variate equalizer computation",Multidi

96、men.Signal Syst.,vol.14,pp.105-108,Jan.2003.</p><p>　　E.Fornasini and M.E.Valcher. Multidimensional systems with finite support behaviors:Signal structure,generation,and detection. SIAM J.Control Optim, 700C

97、779,Mar.1998.</p><p>　　R.Froberg,Introduction to Gröbner Bases. New York:Wiley,1997.</p><p>　　B.Buchberger,H.van Hulzen,ED.,"A note on the complexity of constructing Gröbner bases