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

　　關(guān)鍵詞: ADSP2189數(shù)字信號(hào)處理器? 卷積? DCT

?

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

1 ADSP2189及EZ-KIT簡介

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

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

　　·ADSP-2189M 75 MIPS DSP

　　·AD73322立體聲編譯碼器

　　·RS-232接口

　　·FLASH存儲(chǔ)器

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

2 模板運(yùn)算

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

?

?

　　以3×3模板為例,通過在Visual DSP環(huán)境下設(shè)置PROFILE選項(xiàng),可以得到以下結(jié)論:對(duì)于一個(gè)100×100的數(shù)組,完成模板運(yùn)算共需要96445個(gè)指令周期;對(duì)于一個(gè)640×480的數(shù)組,共需要3052205個(gè)指令周期,遠(yuǎn)遠(yuǎn)低于直接計(jì)算。

3 DCT變換

　　許多圖像壓縮算法采用DCT(Discrete Cosine Transform,即離散余弦變換)來消除像素間冗余,例如JPEG 、H.261以及MPEG。采用DCT是因?yàn)樗哂幸韵聝?yōu)點(diǎn):DCT不同于DFT(Discrete Fourier Transform,即離散傅立葉變換),它屬于實(shí)域運(yùn)算;DCT變換矩陣的基向量很接近于托波列茲矩陣的特征向量,所得變換系數(shù)具有弱相關(guān)性,可以單獨(dú)處理各系數(shù)而不損失壓縮效率。

　　一維DCT表達(dá)式如下:

???

　　二維DCT表達(dá)式如下:

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

?

?

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

?

?

　　在Visual DSP++2.0環(huán)境下編譯執(zhí)行,可以得到8×8數(shù)據(jù)塊快速算法和標(biāo)準(zhǔn)算法的指令周期數(shù)和執(zhí)行時(shí)間,如表1所示。

?

?

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

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

4 常見問題和解決方法

　　在ADSP218X上實(shí)現(xiàn)各種處理時(shí),算法本身或者某型號(hào)的處理器會(huì)出現(xiàn)各種各樣的問題,常見原因主要有:

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

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

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

　　(4)延時(shí)問題 當(dāng)DSP需要對(duì)每個(gè)輸入信號(hào)進(jìn)行順序處理時(shí),輸入信號(hào)頻率就對(duì)處理器的執(zhí)行速度提出了要求。通常的處理延時(shí)主要由DSP的速度和所執(zhí)行算法的復(fù)雜程度來決定,也與外圍邏輯及存儲(chǔ)器件的時(shí)間特性有關(guān)。所以要想提高系統(tǒng)的實(shí)時(shí)性,必須選用高速的器件,并盡量簡化處理算法。

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

?

參考文獻(xiàn)

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

2 章毓晉.圖像處理與分析.北京:清華大學(xué)出版社,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