摘? 要: 介紹了圖像處理" title="圖像處理">圖像處理過程中常用到的兩種算法及其在ADSP2189數字信號處理器" title="數字信號處理器">數字信號處理器上的實現,討論了出現問題的可能原因及解決辦法,在ADSP2189處理器上驗證了各算法。

　　關鍵詞: ADSP2189數字信號處理器? 卷積? DCT

?

　　近幾年來,Analog Devices公司的ADSP系列數字信號處理器以其優異的性能和簡單易學的語言逐漸受到人們的青睞,其中的ADSP218X定點系列更是得到廣泛的應用。ADSP2189片內有192KB的RAM,因此更多地應用于圖像領域。本文就圖像處理壓縮過程中常用到的算法及其在ADSP2189上的實現進行了分析,如何充分利用ADSP系列數字信號處理器特殊的硬件結構和功能強大的指令集實現各種算法是本文討論的重點。然而作為通用定點處理器,處理過程中如何避免可能出現的問題以及如何解決問題也是本文所要討論的。

1 ADSP2189及EZ-KIT簡介

　　ADSP2189是指令執行速度最高可達75MIPS的16位定點數字信號處理器,主要具有以下特點:單周期指令執行,片內的程序控制器不會附加循環和條件指令的執行周期;三總線的體系結構允許在單指令周期" title="指令周期">指令周期中進行雙操作數傳遞;片內192KB的存儲器可被配置成32K×24bit的程序區(PM：Program Memory)和48K×16bit的數據區(DM： Data Memory),而PM中還可同時存放數據。除了具有優異的計算能力外,ADSP2189還具有強大的系統接口:8位的BDMA端口尋址可達4MB,用來提供片內外存儲器的高速存取;16位的IDMA(Internal Direct Memory Access)端口可實現主系統對片內存儲器的高速存取;2048個I/O地址,支持并行的外設;兩個雙緩沖串口,帶自動壓擴。

　　ADSP-2189M EZ-KIT Lite是一塊可用來演示驗證DSP基本算法的仿真板,也是本文所有算法的測試平臺。它主要由以下器件組成:

　　·ADSP-2189M 75 MIPS DSP

　　·AD73322立體聲編譯碼器

　　·RS-232接口

　　·FLASH存儲器

　　EZ-KIT Lite的FLASH存儲器中帶有監控程序,這段程序可完成仿真板與PC機間的串行通信,并允許用戶下載、執行和調試ADSP2189程序。EZ-KIT Lite可與EZ-ICE仿真器相連,通過EZ-ICE仿真器,用戶可以單步執行程序、觀察和改變寄存器和內存值以及完成其它調試工作^[1]。

2 模板運算

　　在圖像處理時,模板運算有著廣泛的應用。例如,在邊沿檢測時,通過將像素矩陣與邊沿檢測矩陣即模板相卷積來實現檢測功能;在圖像平滑時,通過模板運算來濾除噪聲。模板運算的數學涵義就是卷積(或互相關)運算^[2],它是一項非常耗時的運算。以模板為例,每個像素完成一次模板操作要用9個乘法、8個加法和1個除法。對于一幅N×N的圖像,就是9N2個乘法,8N2個加法和N2個除法,算法復雜度為O(N2)。一幅較大的圖像計算量是很大的,所以很多專用的圖像處理系統,用硬件來完成模板運算,這樣可以大大提高速度。在ADSP2189上快速實現模板運算需要充分利用ADSP2189的結構特點和功能強大的指令集。由于ADSP的哈佛結構允許同時訪問程序和數據存儲器,而ADSP的多功能指令(Multifunction Instructions)在執行算術操作的同時還可以并行進行數據傳輸,因此在單周期內可以完成取指、譯碼、讀數、執行和調整寄存器。例如,MR=MR+MX0*MY0(SS)、MX0=DM(I0,M0)、MY0=PM(I4,M4),MX0和MY0分別從數據和程序存儲區以間接尋址方式取得操作數相乘,乘積與結果寄存器中數值相加后放回結果寄存器,數值計算的同時地址指針寄存器I0、I4中的地址自動與調整寄存器中M值進行相加更新。雖然ADSP2189支持除法指令,但為了提高速度,可在程序中將除法改為乘以除數的倒數。另外,在程序中將2維模板運算轉換成1維模板運算,可極大地降低運算量。需要注意的是,由于ADSP2189中CNTR寄存器為14bit,所以在單循環處理中輸入像素個數必須小于16383。模板運算程序的流程如圖1所示。

?

?

　　以3×3模板為例,通過在Visual DSP環境下設置PROFILE選項,可以得到以下結論:對于一個100×100的數組,完成模板運算共需要96445個指令周期;對于一個640×480的數組,共需要3052205個指令周期,遠遠低于直接計算。

3 DCT變換

　　許多圖像壓縮算法采用DCT(Discrete Cosine Transform,即離散余弦變換)來消除像素間冗余,例如JPEG 、H.261以及MPEG。采用DCT是因為它具有以下優點:DCT不同于DFT(Discrete Fourier Transform,即離散傅立葉變換),它屬于實域運算;DCT變換矩陣的基向量很接近于托波列茲矩陣的特征向量,所得變換系數具有弱相關性,可以單獨處理各系數而不損失壓縮效率。

　　一維DCT表達式如下:

???

　　二維DCT表達式如下:

　　由上面的表達式可以看出DCT屬于可分離變換,所以二維DCT通常不采用直接計算的方式,而是對原始圖像數據的行和列分別做一維DCT,即將圖像數據的各行做一維DCT,然后將結果矩陣各列再做一次一維DCT。以8×8的圖像塊為例,進行行列一維DCT需要1024次乘法和896次加法,難以滿足實時要求。因此人們研究了許多DCT的快速算法" title="快速算法">快速算法,如何選取一種適合ADSP結構的算法是提高運算速度的關鍵。計算DCT的快速算法大體上可以歸納為三類^[3～6]:(1)間接計算法。利用FFT和Walsh-Hadamard變換計算DCT,這類算法包含許多多余的過程,降低了運算速度;(2)直接矩陣分解法。利用稀疏矩陣直接分解,使計算速度優于其它算法,僅需較少的乘法和加法,但需對余弦系數進行求反和除法,因而數值不穩定;(3)遞歸算法。Kashef提出的遞歸算法^[4]需要計算N階三角矩陣,而Hou^[5]提出的算法不僅具有規則的遞歸結構,并且具有穩定的數值特性,適合于在DSP上實現,因為它通過少量的乘加運算就可實現DCT,并且對DSP的片內存儲區占用少。這一算法的基本思想類似于Cooley- Tukey FFT算法,它用兩個相同的低階DCT來構成一個高階DCT。以8點一維DCT為例,其信號流程圖如圖2所示。

?

?

　　由圖2可以看出,利用這種方法計算8×8的DCT僅僅需要計算192次乘法和464次加法,計算量遠遠小于標準算法。由于算法的遞歸性以及對各行各列做同樣的處理,所以將分解計算過程以子程序方式調用可以大大降低對存儲區的要求。另外,如果采用“同址計算”的方式,即把運算結果放回到參加運算的輸入數據的原存儲地址,還可以節省存儲空間。以8×8的數據塊" title="數據塊">數據塊為例,應用這種算法的程序流程圖如圖3所示。

?

?

　　在Visual DSP++2.0環境下編譯執行,可以得到8×8數據塊快速算法和標準算法的指令周期數和執行時間,如表1所示。

?

?

　　很明顯,采用快速算法將大大減少處理時間,因此對于實時圖像處理選取合適的算法很重要。

　　在圖像編碼中,DCT本身并不減少數據。真正的數據量減少出現在將DCT的結果也就是DCT系數進行量化,量化后大部分系數接近于零,最后把經之字形掃描的系數進行熵編碼,就達到了壓縮效果。之字形掃描在ADSP2189上實現起來簡單方便,因為對于8×8的數據塊進行之字形掃描僅需要四個地址調整變量。而ADSP2189的數據內存和程序內存各有4個用于產生地址的指針寄存器,每個指針寄存器都可以被四個調整寄存器調整進行更新,即被I0～I3和M0～M3以任何組合進行調整,因此定義M0～M3分別為1、-7、7和8,就可以方便地進行之字掃描。在這個過程中,間接尋址和其它數值計算并行進行,因此不會增加指令執行時間和代碼大小。所以在ADSP2189上實現JPEG編碼,可以在量化的同時進行之字掃描,無需額外開銷。

4 常見問題和解決方法

　　在ADSP218X上實現各種處理時,算法本身或者某型號的處理器會出現各種各樣的問題,常見原因主要有:

　　(1)內存問題 對于ADSP218X系列處理器來講,其主要區別就在于內部存儲區大小的不同。但由于受內部總線的限制,無論程序存儲區還是數據存儲區每次只能處理16K,因此在編譯程序的過程中,應預先估算一下占用內存的情況,以避免運行錯誤,尤其是C語言源程序在使用默認的LDF(Linker Description File)文件時很容易發生超出內存范圍的情況。在Visual DSP編譯環境下可利用MAP文件查看存儲區的分配。由于DSP采用數據區與程序區分離的哈佛結構,所以可利用這一特點將較大的數據塊放在不同的區域,充分利用片內資源。其次是采用原址運算,即輸出變量和輸入變量占用同樣的存儲區,從而節省空間,或者通過LDF文件使用內存重疊區。

　　(2)溢出問題 在ADSP2189中通常采用1.15數據格式,而它屬于定點DSP,動態范圍有限,兩個1.15格式的數相乘后,結果字長變成了2.30格式,在多次相乘累加后,32位的MAC(乘加器)有可能溢出。如果用舍位方法使結果仍然保持為預定的位數,則會引入誤差。多次舍位可能造成嚴重的誤差積累。因此在存放運算結果的字長一定的情況下,需要防止計算結果特別是中間結果的溢出。如果這個溢出能夠預期的話,可以預先確定運算的標度,即預先確定應空出的高位位數(稱為預定標度)。預定標度防止了數據溢出,但是以丟失精度為代價的,同時這樣又增加了運算量。為了保證結果不溢出,預先空出來的位數不僅與待處理數據有關,還與處理數據的函數和該函數的實現過程有關。在實際圖像處理應用中,要從精度和溢出兩方面綜合考慮,選擇一個最佳的定標方案,在保證不產生溢出的情況下盡量降低誤差。另外還有一種輸入溢出,此時輸入值被截取為可表示數據的最大或最小值,從而使得輸入失真。解決方法同樣是對輸入值進行預定標處理。

　　(3)量化效應 對于定點的處理器ADSP2189,量化效應對某些算法有較大影響。例如在數字濾波器的設計當中,傳輸函數的系數必須用固定長度的二進制表示,這樣的量化處理就會引起量化誤差,使得濾波器實際系數偏離原來設計系數,造成極零點位置偏離理論設計位置,從而使濾波性能變差。嚴重時極點移到單位圓上,破壞了濾波器的穩定性。因此在DSP上進行濾波處理時,應合理選擇算法和運算字長。

　　(4)延時問題 當DSP需要對每個輸入信號進行順序處理時,輸入信號頻率就對處理器的執行速度提出了要求。通常的處理延時主要由DSP的速度和所執行算法的復雜程度來決定,也與外圍邏輯及存儲器件的時間特性有關。所以要想提高系統的實時性,必須選用高速的器件,并盡量簡化處理算法。

　　從以上討論可以看出,即使是很常用的算法,在DSP上的實現過程與在PC機上的實現過程也會有很大不同,如何針對不同的芯片選取合適的算法,充分利用各芯片所支持指令集是保證高速處理圖像的關鍵。

?

參考文獻

1 ADSP-2189M EZ-KIT Lite Users Guide.pdf Analog Devices, 2001

2 章毓晉.圖像處理與分析.北京:清華大學出版社,1999

3 Z.Wang.Fast Algorithms for the DiscreteW-Transform and?for the Discrete Fourier Transform. IEEE Trans on ASSP?Aug 1984；32(4)：803～816

4 Kashef B G.Discrete Computation of High-order DCT Coefficients From Low-order DCT Coefficients.SPIE 28th Annu Int Tech Symp， San Diego， CA， Aug， 1984

5 H.S.Hou.A Fast Recursive Algorithm for Computing the?Discrete Cosine Transform. IEEE Trans on ASSP.1987；35(10)：1455～1461

6 W.A.Chen. A Fast Computational Algorithm for the Discrete Cosine Transform.IEEE Trans Communication.? Sept1977；25(9)：1004～1011