圖像處理中的正交變換探討

劉舜鑫，劉少卿

（工業(yè)和信息化部電子第五研究所，廣東 廣州 510610）

0 引言

圖像處理是指用計算機對圖像進行分析，以達到所需結(jié)果的技術(shù)，又被稱為影像處理。平常所說的圖像處理一般指數(shù)字圖像處理。數(shù)字圖像是指用數(shù)字?jǐn)z像機、掃描儀等設(shè)備經(jīng)過采樣和數(shù)字化得到的一個大的二維數(shù)組，該數(shù)組的元素被稱為像素，其值為一整數(shù)，被稱為灰度值。圖像處理技術(shù)的主要內(nèi)容包括圖像壓縮，增強和復(fù)原，匹配、描述和識別3個部分[1]。

圖像變換是圖像處理技術(shù)的重要工具。為了有效和快速地對圖像進行處理和分析，圖像變換將原定義在圖像空間的圖像以某種形式轉(zhuǎn)換到另外一些空間，并利用這些空間的特有性質(zhì)更方便地進行加工，最后再變換回圖像空間以得到所需的效果。正交變換改變圖像的表示域及表示數(shù)據(jù)，給圖像處理工作帶來了極大的方便。利用這個工具，可以對圖像的頻譜進行各種各樣的處理。

1 正交變換的兩種定義

a）定義1：歐氏空間V上的一個線性變換σ被稱為正交變換，如果它保持向量的長度不變，即對任意ξ∈V，均有

b）定義2：歐氏空間V上的一個線性變換σ被稱為正交變換，如果它保持向量的內(nèi)積不變，即對任意 ξ，η∈V，均有（σ（ξ），σ（η））=（ξ，η）。

正交變換最鄰近的一種概念是線性變換，而保持向量的長度不變與保持向量的內(nèi)積不變分別是正交變換的兩個特征。在σ是線性變換的前提下，可以證明這兩個特征是等價的，所以定義1與定義2所描述的概念的內(nèi)涵是一致的。

常見的正交變換有離散傅里葉變換（DFT）、離散沃什一哈達瑪變換（DWHT）、離散余弦變換（DCT）和斜變換（ST）、 霍特林變換（K-L）等[2]。

1.1 傅立葉變換

傅立葉變換是數(shù)字圖像處理技術(shù)的基礎(chǔ)，其通過時空域和頻率域來回切換圖像，對圖像的信息特征進行分析和提取，簡化了計算工作量，被喻為描述圖像信息的第二種語言，廣泛地應(yīng)用于圖像變換、圖像編碼與壓縮、圖像分割和圖像重建中。因此，深入研究和掌握傅立葉變換及其擴展形式的特性是很有價值的。

1.1.1 傅立葉變換的兩種定義

設(shè)R表示實數(shù)全體，L2（R）表示在R上的勒貝格平方可積的函數(shù)全體。L2（R）中的函數(shù)在通信學(xué)科中又被稱作為能量有限信號。對f（x）∈L2被稱作為f的能量。

本文主要討論L2（R）中函數(shù)的傅立葉變換的定義。這兩種定義都與積分有關(guān)。雖然f（x）∈L1（R），積分（x）exp（-iωx）dx一定收斂，但 F（ω）不一定屬于L1（R）。因此，F(xiàn)（ω）的傅立葉逆變換不一定存在。如果f（x）∈L2（R），則積分（-iωx）dx不一定存在。 但是，若 f（x）∈L2（R），則對任意自然數(shù)N，f（x）在區(qū)間[-N，N]上絕對可積，于是dx有意義，而且函數(shù)序列 {FN（ω）}N是 L2（R）中的柯西序列。由于L2（R）是完備的，因此函數(shù)序列 {FN（ω）}N收斂于L2（R）中惟一的極限函數(shù)。

a）定義1 設(shè)f（x）∈L2（R），則f的傅立葉變換定義為：

在L2（R）中的柯西極限，記為：

為方便起見，通常將上述極限簡記為：

其對應(yīng)的傅立葉逆變換定義為：

b）定義2 設(shè)f（x）∈L2（R），則f的傅立葉變換定義為：

其對應(yīng)的傅立葉逆變換定義為：

（注：按照定義1，傅立葉變換是從L2（R）到L2（R）上的有界可逆線性算子。按照定義2，傅立葉變換是從L2（R）到L2（R）上的酉算子。如果記第一種傅立葉變換為F1[f]（ω），第2種傅立葉變換為 F2[f]（ω），則 F1[f]（ω）=2πF2[f]（ω）。）

1.1.2 快速傅立葉變換及其效率評價

快速傅立葉變換（ FFT：Fast Fourier Transform）是離散傅立葉變換（DFT：Discrete Fourier transform）的快速算法，它是根據(jù)離散傅立葉變換的奇、偶、虛、實等特性，對離散傅立葉變換的算法進行改進而獲得的。它對傅立葉變換的理論并沒有新的發(fā)現(xiàn)，但是，對于在計算機系統(tǒng)或者說數(shù)字系統(tǒng)中應(yīng)用離散傅立葉變換，可以說是提高了一大步。

設(shè)Xn為N項的復(fù)數(shù)序列，由DFT變換，任一Xi的計算都需要N次復(fù)數(shù)乘法和N-1次復(fù)數(shù)加法，而一次復(fù)數(shù)乘法等于四次實數(shù)乘法和兩次實數(shù)加法，一次復(fù)數(shù)加法等于兩次實數(shù)加法，即使把一次復(fù)數(shù)乘法和一次復(fù)數(shù)加法定義成一次“運算”（四次實數(shù)乘法和四次實數(shù)加法），那么求出項N復(fù)數(shù)序列的Xi，即N點DFT變換大約就需要N2次運算。當(dāng)N=1024點甚至更多的時候，需要N2=1048576次運算。在 F FT中，利用ωn的周期性和對稱性，把一個N項序列（設(shè)N為偶數(shù)），分為兩個N/2項的子序列，每個N/2點DFT變換需要（N/2）2次運算，再用N次運算把兩個N/2點的DFT變換組合成一個N點的DFT變換。這樣變換以后，總的運算次數(shù)就變成N+2*（N/2）2=N+N2/2。繼續(xù)上面的例子，N=1024時，總的運算次數(shù)就變成了525312次，節(jié)省了大約50%的運算量。而如果我們將這種“一分為二”的思想不斷地進行下去，直到分成兩兩一組的DFT運算單元，那么N點的DFT變換就只需要N*log2N次的運算，N=1024點時，運算量僅有10240次，是先前的直接算法的1%，點數(shù)越多，運算量的節(jié)約就越大，這就是 F FT的優(yōu)越性[3]。

2 離散余弦變換

2.1 問題的起源

離散余弦變換是N.Ahmed等人在1974年提出的正交變換方法。它常被認(rèn)為是對語音和圖像信號進行變換的最佳方法。由于近年來數(shù)字信號處理芯片的發(fā)展，加上專用集成電路設(shè)計上的優(yōu)勢，這就牢固地確立離散余弦變換在目前圖像編碼中的重要地位，成為H.261、JPEG、MPEG等國際上公用的編碼標(biāo)準(zhǔn)的重要環(huán)節(jié)。在視頻壓縮中，最常用的變換方法是DCT，DCT被認(rèn)為是性能接近K-L變換的最佳變換，該變換編碼的主要特點有：

1）在變換域里的視頻圖像要比空間域里簡單；

2）視頻圖像的相關(guān)性明顯地下降，信號的能量主要集中在少數(shù)幾個變換系數(shù)上，采用量化和熵編碼可有效地壓縮其數(shù)據(jù)；

3）具有較強的抗干擾能力，傳輸過程中的誤碼對圖像質(zhì)量的影響遠(yuǎn)小于預(yù)測編碼。

2.2 離散余弦變換的基本概念

DCT利用傅立葉變換的性質(zhì)，采用圖像邊界褶翻將圖像變換為偶函數(shù)形式，然后對圖像進行二維傅立葉變換，變換后僅包含余弦項，所以稱之為離散余弦變換。

2.3 離散余弦變換算法

DCT算法需要的計算量依賴于矩陣的大小，隨著N的增大，需要的計算處理時間將迅速地延長。實際上不可能在整個圖像上執(zhí)行DCT，如果N=256，對256×256樣值進行DCT變換所需要的計算量之大，達到了使計算無法實時實現(xiàn)的程度。實際上，DCT的實現(xiàn)是將圖像分割成許多8×8的小塊，對各個小塊進行DCT計算。雖然塊尺寸增大會得到更好的壓縮，但研究表明，像素之間的相關(guān)性很快趨于減弱，離預(yù)測點15個或20個像素位以外的像素對預(yù)測器來說用處不大。這意味著64×64的DCT塊比起將它分成16×16這4個子塊不會有更好的壓縮。在JPEG和MPEG方案中選用8×8的子塊，64個數(shù)據(jù)稱為一個數(shù)據(jù)單元，按順序進入編碼器。

另外，DCT有快速算法，二維快速余弦變換（2D-FCT）是把8×8塊不斷地分成更小的無交疊子塊，直接對數(shù)據(jù)塊作運算操作。

在進行DCT之前，二維空間圖像亮度數(shù)據(jù)通常較高，為了降低傳輸位率，應(yīng)先進行向下的電平移位。設(shè)原樣值的采樣精度為P位，是無符號整數(shù)，輸入之前把[0，2P-1]范圍的無符號整數(shù)變成[-2P-1，2P-1-1]范圍的有符號整數(shù)，以此作為DCT的輸入。在解碼時，再把經(jīng)DCT反變換得到的一系列8×8樣值子塊的數(shù)值范圍，由[-2P-1，2P-1-1]變回到[0，2P-1]范圍，獲得重建圖像[4]。

3 兩種變換結(jié)果的比對

3.1 傅立葉變換的實驗結(jié)果

a）實驗1

用隨機生成的一個8×8矩陣作為時域離散信號輸入，結(jié)果如圖1所示（左圖為時域信號，右圖為頻域信號）。

隨機產(chǎn)生的DFT輸入信號（8×8矩陣）：

圖1 傅立葉變換的時、頻域信號對比圖

DFT輸出信號（Fx）：

如圖1所示，經(jīng)傅立葉變換以后，頻域信號主要集中在0～5之間即傅立葉變換后圖像大部分能量集中在中間。

b）實驗2

用C++程序?qū)D像（如圖2所示）進行傅立葉變換，從頻譜圖中更直觀地進行觀察、分析。

圖3所示的亮點表示低頻信號，利用傅立葉變換這個工具，可以對圖像的頻譜進行各種各樣的處理，如濾波、降噪和增強等。

圖2 原始圖像

圖3 DFT變換后的頻譜

如圖4所示，經(jīng)離散余弦變換以后，頻信號主要集中在0～0.5之間即離散余弦變換后圖像大部分能量集中在左上角。

3.2 離散余弦變換的實驗結(jié)果

隨機產(chǎn)生的DCT輸入信號（8×8矩陣）：

DCT輸出信號（Fx）：

圖4 離散余弦變換的時、頻域信號對比圖

圖5所示的亮點表示低頻信號，從圖中可以看到圖像的低頻能量都集中在左上角區(qū)域，而向著右下角方向，頻率越來越高。與圖3的離散傅立葉變換頻譜圖進行比較可以發(fā)現(xiàn)，高低頻的能量集中在不同的區(qū)域，這主要是因為離散傅立葉變換的變換核是復(fù)數(shù)，而離散余弦變換的變換核實際上是取其實部的原因。

3.3 兩種變換結(jié)果的比較

為了更加直觀、清楚地對比兩種變換后頻域的變化情況，現(xiàn)以一個隨機矩陣作為輸入信號，并同時對其進行DFT與DCT變換，實驗結(jié)果如圖6所示。

隨機產(chǎn)生的輸入信號（4×4矩陣）：

DFT輸出信號（Fx1）：

DCT輸出信號（Fx2）：

如圖6所示，可以很明顯地看出離散余弦變換的信號相對集中，即是對圖像做離散余弦變換以后，大部分的能量集中在左上角[5]。

4 結(jié)束語

離散余弦變換實際上是傅立葉變換的實數(shù)部分，但是它比傅立葉變換有更強的信息集中能力。對于大多數(shù)自然的圖像，離散余弦變換能將大多數(shù)的信息放到較小的系數(shù)上去，因此就更能提高編碼的效率。同時，由于利用DCT的能量壓縮特性，僅使用一部分DCT系數(shù)就可以重建信號，所以與傅立葉變換相比較，其失真比較小。

[1]燕衛(wèi).正交變換在圖像處理技術(shù)上的應(yīng)用[J].福州電視大學(xué)學(xué)報，2002，8（2）：12-16.

[2]候維民，劉松濤.關(guān)于正交變換兩種定義方式的探討[J].高等數(shù)學(xué)研究學(xué)報，2005，8（1）：44-45.

[3]王曉東，王榮芝.傅立葉變換在圖像處理中的應(yīng)用[J].牡丹江師范學(xué)報，2004，5（6）：16-19.

[4]魯業(yè)頻，李鳳亭，朱仁義，等.基于DCT編碼的新進展[J].中國圖象圖形學(xué)報，2004，9（1）：1-9.

[5]劉維.精通Matlab與C/C++混合程序設(shè)計[M].北京：北京航空航天大學(xué)出版社，2008.