小角度直線反走樣的改進(jìn)Wu算法

李 鉑，周建江，夏偉杰，吳連慧

(南京航空航天大學(xué) 電子信息工程學(xué)院，江蘇 南京 210016)

1 引 言

隨著科技的進(jìn)步及軍事的需求，新一代機(jī)載座艙圖形顯示系統(tǒng)需快速美觀地生成動態(tài)飛行參數(shù)、圖形供飛行員掌控，為了緩解飛行員的視覺壓力、減少誤操作，提高圖形的顯示質(zhì)量很有必要。

本文致力于研究可用于機(jī)載座艙圖形顯示系統(tǒng)的直線反走樣算法，系統(tǒng)最初選用Wu算法[1]來完成直線的反走樣，該算法通過調(diào)整直線路徑上的像素亮度，平滑了整條直線，相比于未反走樣的直線，視覺效果要好很多，原理也相對簡單，但小角度直線的顯示效果不夠理想，存在明顯的“麻花”現(xiàn)象，動態(tài)效果更是如“游動的魚”，易造成飛行員的誤判。

目前基于Wu反走樣的改進(jìn)算法有很多[2-8]，但基本未對小角度直線的“麻花”現(xiàn)象給予特殊處理，顯示效果不夠理想。本文從“麻花”現(xiàn)象原因出發(fā)，分析了兩種常用的改進(jìn)算法，通過Matlab旋轉(zhuǎn)字符仿真效果的比較，提出一種新的直線反走樣算法，小角度直線顯示效果遠(yuǎn)優(yōu)于Wu算法，且對大角度直線和圓弧的反走樣依舊適用。同時結(jié)合中點(diǎn)畫線法后，算法繪制時間也大大縮短，故可用于機(jī)載座艙顯示系統(tǒng)，以提高圖形的顯示質(zhì)量，緩解飛行員的視覺疲勞。

2 Wu算法

光柵顯示器上顯示直線，實(shí)質(zhì)是將一條理想直線數(shù)字化為一組離散的整數(shù)位置。經(jīng)典的Bresenham算法用距理想直線最近的點(diǎn)來近似，可以快速有效地生成單線寬直線，但顯示時能明顯看出直線的階梯效應(yīng)，這種用離散量表示連續(xù)量引起的失真稱為“走樣”，用于減緩或消除圖形走樣的技術(shù)就是“反走樣”[9]。

Wu算法在單線寬直線反走樣方面至今仍是經(jīng)典解決方案，其算法思路非常簡單，設(shè)直線兩個端點(diǎn)為(x1，y1)和(x2，y2)，則|x1-x2|和|y1-y2|中差值較大的數(shù)軸為主軸(長軸)，較小的為從軸(短軸)。直線沿著主軸方向每前進(jìn)一個像素單位，在從軸方向與理想直線距離最近的兩個像素均被點(diǎn)亮，兩者的亮度和等于待繪制顏色的亮度值，根據(jù)像素點(diǎn)在從軸方向上與理想直線的距離來分配，距理想直線遠(yuǎn)的亮度低，距理想直線近的亮度高[1，10]，算法原理如圖1所示。

圖1 Wu反走樣算法原理圖Fig.1 Schematic of Wu anti-aliasing algorithm

圖2是Matlab中Wu反走樣前后直線的仿真效果圖，可以看出Wu反走樣后的直線階梯效應(yīng)已有明顯改善，視覺效果也更加柔和，達(dá)到了減緩圖形走樣的目的。

圖2 Wu反走樣前后直線效果對比Fig.2 Comparison between Bresenham and Wu algorithm

3 小角度直線存在的問題及常用改進(jìn)算法

3.1 小角度直線存在的問題

Wu反走樣后的直線，當(dāng)其與主軸間夾角小于5°時，會出現(xiàn)一定的“麻花”現(xiàn)象，如圖3(a)所示，可明顯看出直線明暗交接處虛化變寬，如擰成的麻花。

圖3 Wu反走樣后的小角度直線及其局部放大圖Fig.3 Small-angle line and its details under Wu algorithm

為了更好地分析現(xiàn)象原因，對圖3(a)局部放大，由圖3(b)可明顯看出，亮度較高的兩段(X1和X2)間的過渡段(T)亮度較低，亮度變化比較明顯，缺乏連續(xù)性。在直線角度較大時，由于過渡段較短，人眼不易觀察到這種變化，而當(dāng)直線角度較小時，T段和X1、X2段均被拉長，觀察者可以清楚地看到整個亮度變化的過程，因此視覺上出現(xiàn)“麻花”現(xiàn)象。

3.2 直線展寬

一般的，為了減輕麻花現(xiàn)象，最簡單、也最易實(shí)現(xiàn)的方法是物理展寬直線，在像素對中間加一個最大亮度的像素點(diǎn)，這樣在不改變邊緣的情況下，視覺上兩側(cè)鋸齒淡化，直線連續(xù)性增加，減緩了走樣[8，11]。如圖4(b)所示，加寬后的Wu反走樣直線視覺效果更加平滑，麻花現(xiàn)象有所減弱。

需要注意的是，增加一個最大亮度的像素點(diǎn)即可，增加兩個或兩個以上會顯得直線過寬、過亮，反而影響顯示效果。

圖4 加寬前后直線效果對比圖Fig.4 Comparison of widening effect

3.3 小角度校正函數(shù)

相比于3.2節(jié)僅僅基于現(xiàn)象表面的方法，校正函數(shù)是從現(xiàn)象的本質(zhì)出發(fā)，通過弱化明暗兩段間的分界，達(dá)到改善或減輕麻花現(xiàn)象的目的。

3.3.1 算法原理

從人的視覺原理來講，人的眼睛感到亮度增加一級時，光強(qiáng)約增加一倍[12]。也就是說，以純色圖像為例，若每個像素用8位二進(jìn)制來表示，該圖像最亮的地方編碼值是255，那么次一級亮的地方則為128，依次類推，整幅圖像的亮度共有9個分區(qū)，對應(yīng)的編碼值分別是0～1，1～2，……，64～128，128～255。在最亮的分區(qū)(編碼值128～255)表達(dá)的亮度細(xì)節(jié)過于豐富，超過了人眼的識別能力(人眼僅能識別高于最大亮度1%的亮度變化[12])，而在較暗的分區(qū)中，表達(dá)的亮度細(xì)節(jié)則過少，人眼可捕捉到亮度的明顯變化。

添加校正函數(shù)是通過一種變換使較暗的分區(qū)占有的量級多一些，較亮分區(qū)占的少些，以更好地表達(dá)一幅圖像的亮度細(xì)節(jié)，一般采用指數(shù)函數(shù)來完成。

3.3.2 算法實(shí)現(xiàn)

將所有的亮度值歸一化，原始亮度值與校正后的亮度值符合式(1)：

(1)

其中：G0表示歸一化的原始亮度值，Gr表示校正后的亮度值，γ是校正系數(shù)，一般γ取1.8～2.2比較符合人眼的視覺特性。綜合算法復(fù)雜度和校正效果，本文取γ=2.0。

對圖3(a)中的小角度直線進(jìn)行校正，前后效果對比如圖5所示，可以看出校正后直線麻花現(xiàn)象有了一定程度的改善，肉眼觀察效果好。

圖5 校正前后直線效果對比Fig.5 Comparison of correction effect

4 改進(jìn)Wu算法

本文涉及的機(jī)載座艙圖形顯示系統(tǒng)，除了圖形，還會顯示飛行參數(shù)，其中有些參數(shù)會隨儀表盤轉(zhuǎn)動，因此算法驗(yàn)證階段常會對字符進(jìn)行旋轉(zhuǎn)。以直立字符N為例，將其旋轉(zhuǎn)85.5°，Matlab仿真結(jié)果如圖6(a)所示，可看到相比于直立字符而言，旋轉(zhuǎn)后字符無明顯走樣，基本無失真。

圖6 旋轉(zhuǎn)后的字符及其局部放大圖Fig.6 Rotated character and its partial enlarged view

對旋轉(zhuǎn)后字符局部放大，如圖6(b)所示，可以看到N的豎線旋轉(zhuǎn)后每個x坐標(biāo)均有4個亮度不一的像素點(diǎn)與之對應(yīng)。對比小角度直線的仿真圖，可以得出直線從軸方向像素點(diǎn)的亮度漸變能很好的消除“麻花”現(xiàn)象。

因此本文基于亮度漸變的思想，結(jié)合Wu算法像素對互補(bǔ)的特點(diǎn)，提出了一種易實(shí)現(xiàn)，且顯示效果又好的小角度直線反走樣算法。

4.1 算法思想

為了體現(xiàn)亮度漸變的過程，直線每向主軸方向前進(jìn)一個像素，則沿從軸方向在理想直線兩側(cè)各繪制兩個像素點(diǎn)，如圖7所示，Am和Cm組成像素對P1，Bm和Dm組成像素對P2，像素對內(nèi)亮度互補(bǔ)，每個像素點(diǎn)均以繪制顏色的亮度值乘以某個權(quán)作為實(shí)際亮度值，該權(quán)值的兩倍等于2減去像素點(diǎn)在從軸方向上與理想直線間的距離。

若待繪制直線的顏色亮度值為G，背景顏色為GB(x，y)，相鄰像素間距為1，位于(x，y)的像素點(diǎn)距理想直線的距離為d(d∈[0，2])，則(x，y)處像素點(diǎn)的亮度值Gx，y如式(2)所示。

圖7 改進(jìn)算法原理圖Fig.7 Schematic of improved algorithm

(2)

與Wu算法相同，新算法也是針對單色的反走樣，在處理彩色直線時，需對其RGB分量單獨(dú)處理。

由算法原理可知，該算法的計(jì)算量是Wu算法的兩倍，故在實(shí)際運(yùn)用中結(jié)合中點(diǎn)畫線法[4，13]，首先計(jì)算出直線中點(diǎn)的位置，然后從直線兩端向中心繪制，對稱畫出所需直線，以達(dá)到既提高顯示效果，又不增加處理時間的目的。

4.2 算法仿真

在Matlab中對新算法進(jìn)行性能仿真，圖8給出了新算法與前文提到的多種算法的仿真效果對比圖，可明顯看出新算法的顯示效果最優(yōu)，最接近理想直線，利于長時間觀察。而且雖然新算法處理后的直線略有變寬，但仍滿足系統(tǒng)對顯示線條的寬度要求，故可用于機(jī)載座艙顯示系統(tǒng)。

圖8 不同算法下小角度直線效果對比Fig.8 Same small-angle line under different algorithms

圖9 不同算法下小角度直線屏幕顯示效果對比圖.(a)Wu反走樣直線;(b)校正后的Wu反走樣直線;(c)加寬的Wu反走樣直線; (d)新算法反走樣后的直線.Fig.9 Display comparison of small-angle lines under different algorithms.(a) Wu anti-aliased line;(b)Corrected Wu anti-aliased line;(c)Widened Wu anti-aliased line; (d)line under new algorithm.

4.3 FPGA實(shí)現(xiàn)

新算法由于復(fù)雜度低、計(jì)算簡單，適合于硬件實(shí)現(xiàn)。在Xilinx公司的Virtex-5系列芯片XC5VFX70T上實(shí)現(xiàn)新算法和前文提到的多種算法，并在屏幕上顯示，如圖9所示。直線傾斜角為2.217°，可以看到新算法視覺效果遠(yuǎn)好于其他算法，“麻花”現(xiàn)象已基本消除。本文系統(tǒng)輸出分辨率為1 600×1 200，幀速率為60 Hz，時鐘頻率為200 MHz，用新算法繪制一條長度為400個像素點(diǎn)的小角度直線耗時16 μs，結(jié)合中點(diǎn)畫線法后只需8.2 μs，與Wu算法的8 μs相差甚少，且顯示效果有了質(zhì)的飛躍，故可用于對顯示效果要求較高的機(jī)載座艙顯示系統(tǒng)中。

圖10 大角度直線和圓弧顯示效果對比.(a)(b)Wu反走樣后; (c)(d)新算法反走樣后.Fig.10 Display comparison of large-angle line and circular arc.(a)(b) under Wu algorithm; (c)(d) under new algorithm.

實(shí)現(xiàn)過程中，除了驗(yàn)證多個小角度直線的生成效果，還對大角度直線和圓弧也試用了本算法，效果也很理想，大角度直線的邊緣鋸齒基本消除，圓弧在小角度部分的虛化現(xiàn)象也得到了很好的緩解，如圖10所示。

5 結(jié) 論

基于Wu反走樣算法的思想，提出了一種原理簡潔、易于硬件實(shí)現(xiàn)、且顯示效果遠(yuǎn)優(yōu)于Wu算法的小角度直線反走樣算法。該算法不僅可用于小角度直線，對大角度直線和圓弧的反走樣依舊適用，而且結(jié)合中點(diǎn)畫線法后，繪制時間大大縮短。在200 MHz的系統(tǒng)時鐘下，繪制長度為400個像素點(diǎn)的小角度直線僅需8.2 μs，與Wu算法所需時間基本一致，故可用于對實(shí)時性和顯示效果要求均較高的機(jī)載座艙顯示系統(tǒng)，以緩解飛行員的視覺疲勞。后續(xù)研究中希望結(jié)合迭代算法[6]、多段并行畫線法[9]等高效算法的思想，對本算法進(jìn)行優(yōu)化，進(jìn)一步縮短處理時間。

[1] Wu X. Efficient anti-aliasing technique [J] .ComputerGraphics，1991，25(4)：143-152.

[2] 楊蕾，趙慕奇，馮晨，等. 飛機(jī)座艙顯示系統(tǒng)的反走樣技術(shù)研究[J]. 液晶與顯示，2006，21(6)：686-691.

Yang L，Zhao M Q，F(xiàn)eng C，etal. Anti-aliasing in aircraft cockpit display system [J].ChineseJournalofLiquidCrystalsandDisplays，2006，21(6)：686-691. (in Chinese)

[3] Jones T R，F(xiàn)erry R N. Antialiasing with line samples [C]//RenderingTechniques2000ProceedingsoftheEurographicsWorkshop，2000：197-205.

[4] 汪麗娜. 飛機(jī)座艙顯示系統(tǒng)儀表畫面的反走樣技術(shù)的研究[D]. 長春：吉林大學(xué)，2007.

Wang L N.Research on antialiasing technology for instrument picture of aircraft cockpit display system [D]. Changchun：Jilin University，2007. (in Chinese)

[5] 馬培華. 直線反走樣生成和裁剪的算法改進(jìn)研究[D]. 南寧：廣西大學(xué)，2012.

Ma P H.The study of improved algorithm on generating and clipping line with anti-aliasing [D]. Nanning：Guangxi University，2012. (in Chinese)

[6] 賈銀亮，張煥春，經(jīng)亞枝. 基于FPGA的直線反走樣算法研究[J]. 計(jì)算機(jī)技術(shù)與發(fā)展，2011，21(2)：26-29.

Jia Y L，Zhang H C，Jing Y Z. Research of line antialiasing based on FPGA [J].ComputerTechnologyandDevelopment，2011，21(2)：26-29. (in Chinese)

[7] Wong K H，Ouyang X，Lmi C W. Rendering anti-aliased line segments [C].ComputerGraphicsInternational2005，2005：198-205.

[8] 江修，張煥春，經(jīng)亞枝. 三像素寬反走樣直線的繪制算法研究[J]. 南京航空航天大學(xué)學(xué)報(bào)，2003，35(2)：148-151.

Jiang X，Zhang H C，Jing Y Z. Study on algorithms for three pixel thick straight line with antialiasing [J].TransactionsofNanjingUniversityofAeronauticsandAstronautics，2003，35(2):148-151. (in Chinese)

[9] Hearn D，Baker M P. 計(jì)算機(jī)圖形學(xué) [M]. 3版.北京：電子工業(yè)出版社，2005：70-79.

Hearn D，Baker M P.ComputerGraphics[M].3rd ed. Beijing：Publishing House of Electronics Industry，2005：70-77. (in Chinese)

[10] 杜晨輝. 提高飛機(jī)座艙顯示系統(tǒng)羅盤畫面顯示質(zhì)量的研究[D]. 南京：南京航空航天大學(xué)，2002.

Du C H.The research on improving the compass display quality of aircraft cockpit display system [D]. Nanjing：Nanjing University of Aeronautics and Astronautics，2002. (in Chinese)

[11] 駱朝亮，謝忠. 一種快速的多線寬直線反走樣算法[J]. 計(jì)算機(jī)工程與應(yīng)用，2011，47(21)：188-190.

Luo C L，Xie Z. Rapid algorithm for anti-aliasing of arbitrary width line drawing [J].ComputerEngineeringandApplications，2011，47(21)：188-190. (in Chinese)

[12] 琚新剛，勾占鋒，孫華. LED亮度調(diào)節(jié)中的人眼感受非線性校正[J]. 鄭州大學(xué)學(xué)報(bào)：工學(xué)版，2012，33(5)：138-140.

Ju X G，Gou Z F，Sun H. Nonlinear correction for human eye feeling to LED brightness control [J].JournalofZhengzhouUniversity：EngineeringScience，2012，33(5)：138-140. (in Chinese)

[13] 姜丹丹，李成貴. 全羅盤畫面中的刻度線反走樣技術(shù)[J]. 液晶與顯示，2009，24(7)：130-134.

Jiang D D，Li C G. Research and implementation of anti-aliasing technology on compass screen-scale [J].ChineseJournalofLiquidCrystalsandDisplays，2009，24(7)：130-134. (in Chinese)