5/3提升小波在DM642上的實(shí)現(xiàn)與優(yōu)化

提升小波變換不僅具有傳統(tǒng)小波多分辨率的優(yōu)點(diǎn)，而且簡化了運(yùn)算，便于硬件實(shí)現(xiàn)，因此在數(shù)字圖像編碼中得到廣泛應(yīng)用。在新的圖像壓縮標(biāo)準(zhǔn)JPEG2000中，采用9/7、5/3提升小波變換作為編碼算法，其中5/3小波變換是一種可逆的整數(shù)變換，可以實(shí)現(xiàn)無損或有損的圖像壓縮。在通用的DSP芯片上實(shí)現(xiàn)該算法具有很好的可擴(kuò)展性、可升級(jí)性與易維護(hù)性。用這種方式靈活性強(qiáng)，完全能滿足各種處理需求。
1 提升算法
提升算法[1]是由Sweldens等在Mallat算法的基礎(chǔ)上提出的，也稱為第二代小波變換。與Mallat算法相比，提升算法不依賴傅立葉變換，降低了計(jì)算量和復(fù)雜度，運(yùn)行效率相應(yīng)提高。由于具有整數(shù)變換及耗費(fèi)存儲(chǔ)單元少的特點(diǎn)，提升算法很適合于在定點(diǎn)DSP上實(shí)現(xiàn)。
小波提升算法的基本思想是通過基本小波逐步構(gòu)建出一個(gè)具有更加良好性質(zhì)的新小波。其實(shí)現(xiàn)步驟為分解(split)、預(yù)測(cè)(predict)和更新(update)。
首先按照對(duì)原信號(hào)進(jìn)行對(duì)稱延拓得到新的x(n)。
分解是將數(shù)據(jù)分為偶數(shù)序列x(2n)和奇數(shù)序列x(2n+1)二個(gè)部分；
預(yù)測(cè)是用分解的偶數(shù)序列預(yù)測(cè)奇數(shù)序列，得到的預(yù)測(cè)誤差為變換的高頻分量：H(n)=x(2n+1)-{[x(2n)+x(2n+2)]>>1}
更新是由預(yù)測(cè)誤差更新偶數(shù)序列，得到變換的低頻分量： L(n)=x(2n)+{[H(n)+H(n-1)+2]>>2}
計(jì)算過程如圖1所示。

2 基于DM642的優(yōu)化策略
2.1 DM642的兩級(jí)CACHE結(jié)構(gòu)
DM642是一款專門面向多媒體處理領(lǐng)域應(yīng)用的處理器，是構(gòu)建多媒體通信系統(tǒng)的良好平臺(tái)。它采用C64xDSP內(nèi)核，片內(nèi)RAM采用兩級(jí)CACHE結(jié)構(gòu)[4][5]，分為L1P、L1D和L2。L1只能作為CACHE被CPU訪問，均為16KB，訪問周期與CPU周期一致，其中L1P為直接映射，L1D為兩路成組相關(guān)；L2可以由程序配置為CACHE和SRAM。
2.2 改進(jìn)的算法結(jié)構(gòu)
傳統(tǒng)的小波變換都是對(duì)整幅圖像作變換，先對(duì)每一行作變換，然后再對(duì)每一列作變換。用這種方式在DSP上實(shí)現(xiàn)該算法時(shí)效率比較低。因?yàn)镈SP的L1D很小，只有16KB，不能緩存整幅圖像，因此原始圖像數(shù)據(jù)通常保存在速度較低的外部存儲(chǔ)器上。這樣CPU從L1D每讀取一行數(shù)據(jù)時(shí)必然會(huì)產(chǎn)生缺失，大量缺失會(huì)嚴(yán)重阻塞CPU的運(yùn)行，延長程序的執(zhí)行時(shí)間。為了減少缺失的發(fā)生，必須將傳統(tǒng)的變換進(jìn)行改進(jìn)。將原來對(duì)整幅圖像的變換改為分塊的變換，即每次從圖像中取出一個(gè)塊，先后完成行、列變換后再按照一定的規(guī)則保存到系數(shù)緩存中，如圖2所示。

在這種方法中，SDRAM中的一個(gè)數(shù)據(jù)塊首先傳輸?shù)絃2中，然后取到L1D中進(jìn)行水平方向的提升，再對(duì)該塊進(jìn)行垂直方向的提升。這樣，由于垂直提升所需的數(shù)據(jù)都在L1D中，避免了此處數(shù)據(jù)緩存缺失的產(chǎn)生，使總的缺失數(shù)大大降低。
2.3 數(shù)據(jù)傳輸
(1)SDRAM與L2間的數(shù)據(jù)傳輸
由于EDMA[6][7]數(shù)據(jù)傳輸與CPU運(yùn)行相互獨(dú)立，因此在L2中開辟兩塊緩存：EDMA在CPU處理InBuffA的同時(shí)將下一塊數(shù)據(jù)傳輸?shù)絀nBuffB，解決了CPU讀取低速設(shè)備SDRAM引起的時(shí)延，如圖3所示。

(2)L2與L1D間的數(shù)據(jù)傳輸
CPU首先訪問第一級(jí)CACHE中的程序和數(shù)據(jù)，如果沒有命中則訪問第二級(jí)CACHE（如果配置L2的一部分為CACHE)，若還沒有命中就要訪問外部存儲(chǔ)空間。在這個(gè)過程中，CPU一直處于阻塞狀態(tài)，直至讀取的數(shù)據(jù)有效。所以，在對(duì)L2中的數(shù)據(jù)塊進(jìn)行水平提升時(shí)，CPU讀取每一行都會(huì)產(chǎn)生缺失。針對(duì)這種情況，TMS320C64x系列DSP為L1D提供了一種高速緩存缺失處理的流水處理機(jī)制。若連續(xù)多次未命中，CPU等待時(shí)間就會(huì)重疊，總體上減少了平均缺失造成的CPU阻塞時(shí)間。
因此，在CPU對(duì)數(shù)據(jù)進(jìn)行水平提升前，利用缺失流水技術(shù)，將當(dāng)前數(shù)據(jù)塊全部讀取到L1D中，隨后再對(duì)該數(shù)據(jù)塊進(jìn)行水平提升，則不會(huì)再發(fā)生缺失，并可提高運(yùn)算速度。
2.4 L1P與L1D性能優(yōu)化
L1D是兩路成組相關(guān)，每組8KB，總?cè)萘?6KB。CPU一次處理的數(shù)據(jù)不應(yīng)超過8KB，并且所有的原始數(shù)據(jù)都連續(xù)存儲(chǔ)在同一CACHE組中；程序的中間過程數(shù)據(jù)保留在預(yù)分配的另一個(gè)CACHE組中。
數(shù)據(jù)讀取到L1D之后，首先由8位擴(kuò)展成16位，然后對(duì)這些數(shù)據(jù)進(jìn)行水平提升，只要這些數(shù)據(jù)能保留在L1D中，隨后進(jìn)行的垂直提升就可以完全避免缺失。因此，數(shù)據(jù)塊的大小是由中間過程數(shù)據(jù)決定的，所有中間過程數(shù)據(jù)加起來不能超過8KB，選取數(shù)據(jù)塊是32×32。
當(dāng)多個(gè)函數(shù)映射到L1P的同一個(gè)CACHE行時(shí)就會(huì)引起沖突缺失，所以必須合理放置這些函數(shù)。由于實(shí)現(xiàn)提升的全部函數(shù)加起來不超過16KB，因此，如果能將這些函數(shù)安排在一個(gè)連續(xù)的存儲(chǔ)空間內(nèi)，就可以完全避免由沖突引起的L1P缺失。可以在cmd[8]文件的SECTIONS中添加一個(gè)GROUP，然后將頻繁調(diào)用的函數(shù)放到GROUP中：
SECTIONS
{
GROUP > ISRAM
{
.text：_horz
.text：_vert
.text：_IMG_pix_pand
…
}…}
2.5 程序優(yōu)化
由前面的分析可知,對(duì)圖像進(jìn)行提升小波變換時(shí),需要對(duì)其四個(gè)邊界進(jìn)行延拓。延拓方式采用圖1所示的對(duì)稱延拓，其中左邊與上邊需要多延拓一個(gè)點(diǎn)。而對(duì)圖像中的一個(gè)塊進(jìn)行提升變換時(shí)，其延拓的應(yīng)該是與該塊相鄰的四個(gè)塊數(shù)據(jù)的邊界數(shù)據(jù)，如圖4所示。

邊界延拓主要是用于計(jì)算高頻系數(shù)。分析發(fā)現(xiàn)，水平提升時(shí)，當(dāng)前數(shù)據(jù)塊每一行的最后一個(gè)高頻系數(shù)與下一個(gè)塊在該行的第一個(gè)高頻系數(shù)相同。所以只要把當(dāng)前塊的這些系數(shù)保存起來，在對(duì)下一塊進(jìn)行水平提升時(shí)第一個(gè)高頻系數(shù)就不需要再進(jìn)行計(jì)算，因此也就不需要再對(duì)其左邊界進(jìn)行延拓了。垂直方向的提升也是同樣的道理。在程序中添加兩個(gè)數(shù)組，分別用于存放當(dāng)前塊的每一行與每一列的最后一個(gè)高頻系數(shù)。采用這種方法就可以降低程序的復(fù)雜度，提高執(zhí)行效率，減少缺失的發(fā)生。
像素?cái)U(kuò)展函數(shù)pix_pand[9]是采用TI的IMGLIB算法庫。水平提升與垂直提升函數(shù)均由作者用線性匯編語言編寫，充分利用64x系列DSP的半字處理指令，采用半字打包技術(shù)，最大限度地提高程序的執(zhí)行效率。
水平提升時(shí)，將每行的數(shù)據(jù)重新排序，變成如圖5所示的結(jié)構(gòu)。

使用C64x的ADD2、SHR2和SUB2等半字處理指令，將如下的兩個(gè)運(yùn)算并行執(zhí)行：
H(1)=B-[(A+C)>>1]
H(2)=D-[(C+E)>>1]
垂直提升時(shí)則可以安排多列的計(jì)算并行執(zhí)行，如圖6所示。
H1(1)=B1-[(A1+C1)>>1]
H2(1)=B2-[(A2+C2)>>1]

3 仿真結(jié)果
表1列出了CPU讀取L1D時(shí)產(chǎn)生的缺失數(shù)。其中，水平方向的缺失不可避免。由于要對(duì)數(shù)據(jù)塊的右側(cè)和底部進(jìn)行邊界延拓，所以在水平方向的缺失數(shù)比傳統(tǒng)方法略高；而在垂直方向上，該算法完全避免了缺失的發(fā)生。

表2列出了幾種方法的計(jì)算性能。由于本文采用了多種優(yōu)化技術(shù)，運(yùn)算速度提高了4～10倍。
本文介紹了5/3提升小波變換及其在DM642上的實(shí)現(xiàn)。為了提高其性能提出了多項(xiàng)優(yōu)化技術(shù)，試驗(yàn)證明這些方法十分有效。