图像放大算法
1?引言
基于ARM體系的微處理器，特別是Intel XScale架構(gòu)的微處理器，比如PXA255和最新的PXA270，以其高性能、低功耗等優(yōu)點(diǎn)，已在嵌入式系統(tǒng)領(lǐng)域中得到廣泛的應(yīng)用。而目前PDA的屏幕越來越大，從QVGA的320×240分辨率漸漸提高到VGA的640×480分辨率。但是由于ARM處理器性能有限，一些多媒體和游戲程序只能在QVGA的分辨率下達(dá)到比較流暢的速度，但是在VGA的分辨率之下由于要渲染的像素升至4倍，幀速往往就下降到原來的1/4，速度慢得讓人無法忍受，所以非常有必要采用一些特殊的方法來提高程序運(yùn)行的速度。
本文提出一種能有效提高多媒體和游戲程序在VGA分辨率下執(zhí)行速度的方法，就是先讓程序渲染出QVGA分辨率的圖像，然后再放大一倍，以只比QVGA分辨率渲染多一點(diǎn)點(diǎn)處理時間，達(dá)到VGA分辨率的效果。這樣就需要一種快速且失真比較小的圖像放大算法來達(dá)到非常快的處理時間和比較好的效果。本文詳細(xì)分析了現(xiàn)有的多種圖像放大算法，提出了適用于嵌入式系統(tǒng)的快速優(yōu)質(zhì)圖像放大算法，并針對XScale架構(gòu)進(jìn)行大量的優(yōu)化來提高速度，最后通過實(shí)例說明最終的執(zhí)行效果。其中實(shí)例研究的軟件平臺為Arm Linux 2.4.19，硬件平臺為基于Intel PXA255 的Sitsang開發(fā)板和基于PXA270 的Mainstone開發(fā)板。
2?圖像放大算法
2.1?最鄰近法（Nearest Neighbour）
以圖像處理領(lǐng)域為例，理想圖像是均勻分布在二維平面直角坐標(biāo)系中的，任意給出一對坐標(biāo)，就應(yīng)該能得到一個對應(yīng)顏色值，然而實(shí)際上只能用離散的點(diǎn)陣信息來近似表現(xiàn)圖像。
現(xiàn)在假設(shè)給定一對坐標(biāo)(3.1,5.3)，想要得到這個坐標(biāo)對應(yīng)的顏色（假設(shè)是灰度圖），那么最簡單的方法是用四舍五入來得到距離該點(diǎn)最近的像素，即像素(3,5)的值來代替，這就是最鄰近法。最鄰近法顯然是速度最快的一種方法，但也是效果最差的一種，如果用這個方法進(jìn)行圖像放大，那么在放大比例較大的情況下就會出現(xiàn)非常明顯的“馬賽克”現(xiàn)象。
2.2?雙線性插值法（Bi-linear Interpolation）
對于上面的例子，更好的辦法是把像素(3,5)和像素(4,6)的顏色值按照一定的比例混合。原始坐標(biāo)離哪個像素近，哪個像素的比例就大些，即混合的比例與離像素的距離成反比。
如圖一所示，如果要求出點(diǎn)P處的顏色值，首先讓p00和p01混合求出P0處的顏色值：（其中h0+h1=1，v0+v1=1）
P0 = p00×h0 + p01×h1???????????????????????????????????????????????????????????????????????????????? （1）
然后再讓p10和p11混合求出P1處的顏色值：
P1 = p10×h0 + p11×h1???????????????????????????????????????????????????????????????????????????????? （2）
最后讓P0和P1混和求出P處的顏色值
P?? =? P0 ×v0 + P1 ×v1???????????????????????????????????????????????????????????????????????????? （3）
采用雙線性插值法之后顏色的過渡比較平滑,效果也比最鄰近法要好得多。
2.3??????? 雙立方插值法（Bi-cubic Interpolation）
但是雙線性插值只采用了2×2＝4個點(diǎn)進(jìn)行計算，就是說顏色值在圖一所示的正方形內(nèi)是線形變化的，而一般相鄰正方形的這個線性斜率是不同的，這樣在正方形的邊緣部分顏色就不是漸變，而會有個突變，而人眼對于這種突變往往十分敏感，當(dāng)放大倍數(shù)比較大時就會看到明顯的馬賽克，這時可以采用效果更好的雙立方插值。
雙立方插值采用的B樣條曲線插值，在每個維度上對于連續(xù)的4個點(diǎn)進(jìn)行插值，這樣在所有的點(diǎn)之間的斜率都是連續(xù)的，不會存在突變。如果是兩維的情況在相鄰的正方形之間的斜率也都是連續(xù)的，人眼就不會看到明顯的馬賽克了。
先來看一維的情況，這里采用了B樣條插值，在4個點(diǎn)之間利用3次曲線進(jìn)行擬合：
??雖然雙立方插值可以得到最佳畫質(zhì)，但是它的計算復(fù)雜度實(shí)在太大了，即使采用了整數(shù)優(yōu)化和查表法，也將耗去大量的CPU資源。
而在放大至原來2倍的情況下，雙立方插值和雙線性插值畫質(zhì)相近，這時雙線性插值就有明顯的速度優(yōu)勢，所以更加適合嵌入式環(huán)境。
2.4??????? 其他圖像放大算法
對于游戲程序來說，又有一些專門的放大算法，可以達(dá)到更加好的放大效果。比如：2xSaI，Supersai，Egale，Scale2x，hq2x，lq2x等。這些算法都是專門放大圖像到原來大小兩倍的算法，由于固定了放大倍率，所以都經(jīng)過特殊的優(yōu)化，效果往往比雙線性插值和雙立方插值要好。如圖二所示，hq2x對于簡單線條和輪廓比較清晰的圖像就有非常好的效果：
hq2x采用了模式匹配的思想，原始圖像的每個點(diǎn)放大后都擴(kuò)展成4個點(diǎn)，在hq2x里面就是參考了這個點(diǎn)周圍的八個點(diǎn)，就是說一共用9個點(diǎn)的顏色值來確定放大后4個點(diǎn)的顏色值。首先比較當(dāng)前點(diǎn)和周圍八個點(diǎn)的顏色值的差別，根據(jù)差別的大小分成顏色相近和顏色差別較大兩種類別，因為周圍共有八個點(diǎn)，這樣共有256種可能的排列組合。
對于每種組合，每種情況，都要確定如何根據(jù)原先的9個點(diǎn)的顏色值混合成放大后4個點(diǎn)的顏色值，可以事先做好這256種可能組合的混色表，每項都存放了每種情況應(yīng)該如何混色，放大時只要根據(jù)當(dāng)前的情況查詢一下混色表，就知道應(yīng)該如何混色生成放大后4個點(diǎn)的顏色值了。
這些算法對于線條輪廓比較清晰的卡通游戲會有非常好的放大效果，所以通常都使用在游戲模擬器中，比如任天堂模擬器，Gameboy Advanced模擬器等等。但是如果是一般的多媒體程序，比如視頻的播放，由于模式比較復(fù)雜，難于統(tǒng)計出合適的混色表，放大效果并不是很好，僅僅和雙線性插值差不多，又由于算法復(fù)雜度太高，并且只能用于放大一倍的情況，所以使用的不是很多。
3?XScale架構(gòu)下程序的優(yōu)化
對比這些放大算法，由于雙線性插值算法的通用性比較強(qiáng)，復(fù)雜度又低，所以最后采用雙線性插值作為放大算法，下面對雙線性插值算法進(jìn)行優(yōu)化：
3.1?定點(diǎn)數(shù)優(yōu)化
把雙線性插值算法的（1）、（2）、（3）式合起來就是：
P = (p00*h0+p01*h1)*v0 + (p10*h0+p11*h1)*v1?????????????????????????????????????????? （7）
其中h0+h1=1，v0+v1=1，這個公式中共有6次浮點(diǎn)乘法，RGB需要分開算，這樣一個像素點(diǎn)需要18次浮點(diǎn)乘法，這還不包括生成浮點(diǎn)坐標(biāo)的時間。
由于XScale架構(gòu)沒有浮點(diǎn)運(yùn)算單元（FPU），所有的浮點(diǎn)運(yùn)算都由軟件模擬實(shí)現(xiàn)，所以這段程序在XScale架構(gòu)中運(yùn)行得非常慢，需要進(jìn)行大量的優(yōu)化來提高程序的性能。
首先把浮點(diǎn)運(yùn)算改成定點(diǎn)運(yùn)算，采用Q16.16的定點(diǎn)數(shù)。即：
定點(diǎn)數(shù) = (int)(浮點(diǎn)數(shù)*65536.0+0.5)，
把v0，v1，h0，h1轉(zhuǎn)成定點(diǎn)數(shù)為：V0，V1，H0，H1。式（7）就變?yōu)?#xff1a;
P = (((p00*H0+p01*H1)>>16)*V0 + ((p10*H0+ p11*H1)>>16)*V1) >>16????? （8）
此外，V0，V1，H0，H1也不需要每次都計算坐標(biāo)然后轉(zhuǎn)換成16位定點(diǎn)數(shù)，可以一開始計算好后使用增量法，在相應(yīng)的循環(huán)中遞增等量值，這樣也可以減少每次計算的時間。
3.2??????? 查表法優(yōu)化
在式（8）中還是有6次定點(diǎn)乘法，在XScale架構(gòu)下乘法的操作需要花費(fèi)1-5個時鐘周期，而且乘法流水線是偽流水線，只有上一條乘法語句執(zhí)行完了，下一條乘法語句才能進(jìn)入流水線。
同時對這行代碼編譯后的匯編代碼進(jìn)行分析，發(fā)現(xiàn)數(shù)據(jù)先后關(guān)聯(lián)性非常大，如果存在關(guān)聯(lián)性，乘法流水線和主流水線就不能并行工作，必須等待乘法運(yùn)算結(jié)束了主流水線才能繼續(xù)工作。所以即使采取了重排序等手工匯編優(yōu)化手段，這段代碼的實(shí)際性能也并不是很高，所以最后采用查表法作更進(jìn)一步的優(yōu)化。
對于兩個顏色a，b和相應(yīng)的歸一化距離v構(gòu)建表：
LinearTable[a][b][v]=(a*v + b*(255-v))>>8????????????????????????????????????????????????? （9）
其中a，b為6位（由于使用的是RGB565，采用最高的6位），v使用8位的精度（經(jīng)實(shí)踐，8位的精度已經(jīng)足夠了），這樣一個表所占內(nèi)存為：6×6×8＝1MB
對于多媒體程序來說多耗1M的內(nèi)存是完全可以接受的。這樣，一次雙線性插值的開銷減少到3次查表：
P0 = LinearTable [p00][p01][H0];
P1 = LinearTable [p10][p11][H0];???????????????????????????????????????????????????????????? （10）
P?? = LinearTable [P0][P1][V0];
3.3?對于放大一倍情況的優(yōu)化
特別的對于放大一倍的情況，算法簡化了很多，式（7）變?yōu)?#xff1a;
P =? (p00 +p01 + p10 + p11)>>2??????????????????????????????????????????????????????????? （11）
這樣算法中只有加法和位移，計算復(fù)雜度小了很多。
但是對于一個象素的計算要分別計算RGB三個分量，這時可以采用重新排列數(shù)據(jù)結(jié)構(gòu)的方法來提高速度。
原來是16bit的RGB565：?? 0x0000 0000 0000 0000 RRRR RGGG GGGB BBBB
現(xiàn)在分開存放：?????????? 0x0000 0GGG GGG0 0000 RRRR R000 000B BBBB
這樣一次就能同時處理RGB三種顏色，相當(dāng)于提高速度3倍。
3.4?基于XScale架構(gòu)的優(yōu)化
在XScale架構(gòu)中使用了很多PC上所使用的先進(jìn)技術(shù)來提高程序的速度，下面對雙線性插值算法進(jìn)行進(jìn)一步的優(yōu)化。
現(xiàn)在計算的瓶頸就是內(nèi)存訪問了，由于圖像數(shù)據(jù)比較大，遠(yuǎn)大于XScale的32K數(shù)據(jù)緩存，所以幾乎每次都要從SDRAM中取數(shù)據(jù)，在主頻為624MHz的PXA270中首先需要3個總線周期CAS延遲，然后可以連續(xù)取到8個32bit數(shù)據(jù)，正好構(gòu)成cache的一行，這樣一共11個總線周期（66個內(nèi)核周期）僅可取到8個32bit數(shù)據(jù)，RGB565的象素點(diǎn)都是16bit的，所以平均66個周期可以取到16個數(shù)據(jù)。
在式（11）中的4個數(shù)據(jù)平均需要約16個時鐘周期才能全部取到，但是整個式子的計算只要5個時鐘周期就可以完成，這樣CPU的大部分時間都處于等待數(shù)據(jù)的狀態(tài)，顯然如何提高內(nèi)存讀寫效率成了提高程序運(yùn)行速度的關(guān)鍵。
首先可以采用PLD命令預(yù)取數(shù)據(jù)，在計算當(dāng)前像素點(diǎn)前就用PLD命令預(yù)取下一次要計算的像素點(diǎn)，然后在計算當(dāng)前點(diǎn)的同時CPU就會把下一次要計算的像素點(diǎn)的數(shù)據(jù)預(yù)取到數(shù)據(jù)緩存中，這樣，到了下一次計算時可以直接從數(shù)據(jù)緩存中取數(shù)據(jù)，這樣可以保證CPU的流水線效率最大。
然后再針對XScale的流水線進(jìn)行指令重排序。把a(bǔ)rm-linux-gcc編譯出來的代碼反匯編，對匯編代碼進(jìn)行分析，刪除、合并部分冗余代碼，并將ldr指令前后不相關(guān)的指令進(jìn)行略微的重排序來防止流水線的停頓。這樣可以更進(jìn)一步提高程序的性能。
最后還可以利用PXA270 所特有的Wireless MMX指令集來優(yōu)化，可以同時處理64bit的數(shù)據(jù)，這樣還能再提高一倍的速度。
4?性能測試
下面對各種放大算法放大一幀圖像（從QVGA放大成VGA）所花的時間進(jìn)行比較：
假設(shè)程序渲染QVGA分辨率的圖像需要30ms的時間，這樣程序跑在QVGA分辨率下可以達(dá)到33.3幀的速度，畫面非常流暢。而渲染VGA分辨率的時間是QVGA的4倍，需要120ms，這樣速度僅有8.3幀了，這時畫面很不流暢。
從圖三可以看出優(yōu)化前的雙線性插值法速度是相當(dāng)慢的，即使程序只執(zhí)行放大算法，一秒也只能渲染12幀圖像，加上渲染QVGA的圖像所需的30ms，程序的速度和直接渲染VGA分辨率差不多，而畫質(zhì)肯定不如直接渲染的，這樣采用放大算法就完全沒有意義了。而經(jīng)過上述一系列優(yōu)化之后，雙線性插值只需17.3ms就能完成一幀圖像的放大，這樣渲染QVGA分辨率的圖像加上放大只需47.3ms，可以達(dá)到比較流暢的21.1幀的速度。即使是效果最差、速度最快的最鄰近法也需要14.4ms，而采用雙線性插值可以用稍多一點(diǎn)的放大時間來達(dá)到好得多的圖像效果。
hq2x算法非常耗時，需要131.5ms來放大，雖然可以達(dá)到非常好的放大效果，但由于速度問題而不能應(yīng)用到實(shí)際程序中。
5?總結(jié)
經(jīng)過對各種圖像放大算法的研究和分析，并且結(jié)合實(shí)際應(yīng)用程序的編寫和測試，最終找到一種適合嵌入式系統(tǒng)，特別是適合XScale架構(gòu)的快速優(yōu)質(zhì)的圖像放大算法。經(jīng)過大量代碼優(yōu)化之后，使其放大速度接近直接數(shù)據(jù)拷貝，并在實(shí)際應(yīng)用程序中達(dá)到很好的效果。
總結(jié)
- 上一篇： 改进飞碟游戏
- 下一篇： 什么是AAC音频格式 AAC-LC 和