5/3提升小波在DM642上的實現(xiàn)與優(yōu)化
1 提升算法
提升算法[1]是由Sweldens等在Mallat算法的基礎(chǔ)上提出的,也稱為第二代小波變換。與Mallat算法相比,提升算法不依賴傅立葉變換,降低了計算量和復雜度,運行效率相應提高。由于具有整數(shù)變換及耗費存儲單元少的特點,提升算法很適合于在定點DSP上實現(xiàn)。
小波提升算法的基本思想是通過基本小波逐步構(gòu)建出一個具有更加良好性質(zhì)的新小波。其實現(xiàn)步驟為分解(split)、預測(predict)和更新(update)。
首先按照對原信號進行對稱延拓得到新的x(n)。
分解是將數(shù)據(jù)分為偶數(shù)序列x(2n)和奇數(shù)序列x(2n+1)二個部分;
預測是用分解的偶數(shù)序列預測奇數(shù)序列,得到的預測誤差為變換的高頻分量:H(n)=x(2n+1)-{[x(2n)+x(2n+2)]>>1}
更新是由預測誤差更新偶數(shù)序列,得到變換的低頻分量: L(n)=x(2n)+{[H(n)+H(n-1)+2]>>2}
計算過程如圖1所示。
2 基于DM642的優(yōu)化策略
2.1 DM642的兩級CACHE結(jié)構(gòu)
DM642是一款專門面向多媒體處理領(lǐng)域應用的處理器,是構(gòu)建多媒體通信系統(tǒng)的良好平臺。它采用C64xDSP內(nèi)核,片內(nèi)RAM采用兩級CACHE結(jié)構(gòu)[4][5],分為L1P、L1D和L2。L1只能作為CACHE被CPU訪問,均為16KB,訪問周期與CPU周期一致,其中L1P為直接映射,L1D為兩路成組相關(guān);L2可以由程序配置為CACHE和SRAM。
2.2 改進的算法結(jié)構(gòu)
傳統(tǒng)的小波變換都是對整幅圖像作變換,先對每一行作變換,然后再對每一列作變換。用這種方式在DSP上實現(xiàn)該算法時效率比較低。因為DSP的L1D很小,只有16KB,不能緩存整幅圖像,因此原始圖像數(shù)據(jù)通常保存在速度較低的外部存儲器上。這樣CPU從L1D每讀取一行數(shù)據(jù)時必然會產(chǎn)生缺失,大量缺失會嚴重阻塞CPU的運行,延長程序的執(zhí)行時間。為了減少缺失的發(fā)生,必須將傳統(tǒng)的變換進行改進。將原來對整幅圖像的變換改為分塊的變換,即每次從圖像中取出一個塊,先后完成行、列變換后再按照一定的規(guī)則保存到系數(shù)緩存中,如圖2所示。
在這種方法中,SDRAM中的一個數(shù)據(jù)塊首先傳輸?shù)絃2中,然后取到L1D中進行水平方向的提升,再對該塊進行垂直方向的提升。這樣,由于垂直提升所需的數(shù)據(jù)都在L1D中,避免了此處數(shù)據(jù)緩存缺失的產(chǎn)生,使總的缺失數(shù)大大降低。
2.3 數(shù)據(jù)傳輸
(1)SDRAM與L2間的數(shù)據(jù)傳輸
由于EDMA[6][7]數(shù)據(jù)傳輸與CPU運行相互獨立,因此在L2中開辟兩塊緩存:EDMA在CPU處理InBuffA的同時將下一塊數(shù)據(jù)傳輸?shù)絀nBuffB,解決了CPU讀取低速設(shè)備SDRAM引起的時延,如圖3所示。
(2)L2與L1D間的數(shù)據(jù)傳輸
CPU首先訪問第一級CACHE中的程序和數(shù)據(jù),如果沒有命中則訪問第二級CACHE(如果配置L2的一部分為CACHE),若還沒有命中就要訪問外部存儲空間。在這個過程中,CPU一直處于阻塞狀態(tài),直至讀取的數(shù)據(jù)有效。所以,在對L2中的數(shù)據(jù)塊進行水平提升時,CPU讀取每一行都會產(chǎn)生缺失。針對這種情況,TMS320C64x系列DSP為L1D提供了一種高速緩存缺失處理的流水處理機制。若連續(xù)多次未命中,CPU等待時間就會重疊,總體上減少了平均缺失造成的CPU阻塞時間。
因此,在CPU對數(shù)據(jù)進行水平提升前,利用缺失流水技術(shù),將當前數(shù)據(jù)塊全部讀取到L1D中,隨后再對該數(shù)據(jù)塊進行水平提升,則不會再發(fā)生缺失,并可提高運算速度。
2.4 L1P與L1D性能優(yōu)化
L1D是兩路成組相關(guān),每組8KB,總?cè)萘?6KB。CPU一次處理的數(shù)據(jù)不應超過8KB,并且所有的原始數(shù)據(jù)都連續(xù)存儲在同一CACHE組中;程序的中間過程數(shù)據(jù)保留在預分配的另一個CACHE組中。
數(shù)據(jù)讀取到L1D之后,首先由8位擴展成16位,然后對這些數(shù)據(jù)進行水平提升,只要這些數(shù)據(jù)能保留在L1D中,隨后進行的垂直提升就可以完全避免缺失。因此,數(shù)據(jù)塊的大小是由中間過程數(shù)據(jù)決定的,所有中間過程數(shù)據(jù)加起來不能超過8KB,選取數(shù)據(jù)塊是32×32。
當多個函數(shù)映射到L1P的同一個CACHE行時就會引起沖突缺失,所以必須合理放置這些函數(shù)。由于實現(xiàn)提升的全部函數(shù)加起來不超過16KB,因此,如果能將這些函數(shù)安排在一個連續(xù)的存儲空間內(nèi),就可以完全避免由沖突引起的L1P缺失??梢栽赾md[8]文件的SECTIONS中添加一個GROUP,然后將頻繁調(diào)用的函數(shù)放到GROUP中:
SECTIONS
{
GROUP > ISRAM
{
.text:_horz
.text:_vert
.text:_IMG_pix_pand
…
}…}
2.5 程序優(yōu)化
由前面的分析可知,對圖像進行提升小波變換時,需要對其四個邊界進行延拓。延拓方式采用圖1所示的對稱延拓,其中左邊與上邊需要多延拓一個點。而對圖像中的一個塊進行提升變換時,其延拓的應該是與該塊相鄰的四個塊數(shù)據(jù)的邊界數(shù)據(jù),如圖4所示。
邊界延拓主要是用于計算高頻系數(shù)。分析發(fā)現(xiàn),水平提升時,當前數(shù)據(jù)塊每一行的最后一個高頻系數(shù)與下一個塊在該行的第一個高頻系數(shù)相同。所以只要把當前塊的這些系數(shù)保存起來,在對下一塊進行水平提升時第一個高頻系數(shù)就不需要再進行計算,因此也就不需要再對其左邊界進行延拓了。垂直方向的提升也是同樣的道理。在程序中添加兩個數(shù)組,分別用于存放當前塊的每一行與每一列的最后一個高頻系數(shù)。采用這種方法就可以降低程序的復雜度,提高執(zhí)行效率,減少缺失的發(fā)生。
像素擴展函數(shù)pix_pand[9]是采用TI的IMGLIB算法庫。水平提升與垂直提升函數(shù)均由作者用線性匯編語言編寫,充分利用64x系列DSP的半字處理指令,采用半字打包技術(shù),最大限度地提高程序的執(zhí)行效率。
水平提升時,將每行的數(shù)據(jù)重新排序,變成如圖5所示的結(jié)構(gòu)。
使用C64x的ADD2、SHR2和SUB2等半字處理指令,將如下的兩個運算并行執(zhí)行:
H(1)=B-[(A+C)>>1]
H(2)=D-[(C+E)>>1]
垂直提升時則可以安排多列的計算并行執(zhí)行,如圖6所示。
H1(1)=B1-[(A1+C1)>>1]
H2(1)=B2-[(A2+C2)>>1]
3 仿真結(jié)果
表1列出了CPU讀取L1D時產(chǎn)生的缺失數(shù)。其中,水平方向的缺失不可避免。由于要對數(shù)據(jù)塊的右側(cè)和底部進行邊界延拓,所以在水平方向的缺失數(shù)比傳統(tǒng)方法略高;而在垂直方向上,該算法完全避免了缺失的發(fā)生。
表2列出了幾種方法的計算性能。由于本文采用了多種優(yōu)化技術(shù),運算速度提高了4~10倍。
本文介紹了5/3提升小波變換及其在DM642上的實現(xiàn)。為了提高其性能提出了多項優(yōu)化技術(shù),試驗證明這些方法十分有效。
參考文獻
[1] RABBANI M,JOSHI R.An overview of the JPEG2000 still image compression standard.Signal Processing:Image Com-munication,2002;(17)1:3-48.
[2] CHO J K,HWANG M C,KIM J S et al.Fast DSP implementation of JPEG2000.Proc of IEEE TENCON,2004(A): 231-234,Thailand,Nov.21-24,2004.
[3] CHO J K,HWANG M C,KIM J S et al.Fast Implementation of Wavelet Lifting for JPEG2000 on a Fixed-Point. Proc.of 2004 International Technical Conference on Circuits Systems,Computers and Communications,Sendai/Matsusima,2004,7.
[4] Texas Instruments Incorporated. SPRU656A-TMS320C6000 DSP Cache User′s Guide,2003.
[5] Texas Instruments Incorporated.SPRU610B- TMS320C64x DSP Two-Level Internal Memory Reference Guide,2004.
[6] Texas Instruments Incorporated.SPRU234B-TMS320C6000 DSP Enhanced Direct Memory Access(EDMA) Controller Reference Guide,2005.
[7] Texas Instruments Incorporated.SPRU401J-TMS320C6000 Chip Support Library API Reference Guide,2004.
[8] Texas Instruments Incorporated.SPRU186O-TMS320C6000 Assembly Language Tools v 6.0.0 Alpha User′s Guide,2005.
[9] Texas Instruments Incorporated.SPRU023B-TMS320C64x Image/Video Processing Library Programmer′s Reference,2003.