小角度直線反走樣的改進Wu算法

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

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

1 引 言

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

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

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

2 Wu算法

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

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

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

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

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

3 小角度直線存在的問題及常用改進算法

3.1 小角度直線存在的問題

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

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

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

3.2 直線展寬

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

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

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

3.3 小角度校正函數

相比于3.2節僅僅基于現象表面的方法，校正函數是從現象的本質出發，通過弱化明暗兩段間的分界，達到改善或減輕麻花現象的目的。

3.3.1 算法原理

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

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

3.3.2 算法實現

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

(1)

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

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

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

4 改進Wu算法

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

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

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

因此本文基于亮度漸變的思想，結合Wu算法像素對互補的特點，提出了一種易實現，且顯示效果又好的小角度直線反走樣算法。

4.1 算法思想

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

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

圖7 改進算法原理圖Fig.7 Schematic of improved algorithm

(2)

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

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

4.2 算法仿真

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

圖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實現

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

圖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.

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

5 結 論

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

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

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

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

[3] Jones T R，Ferry R N. Antialiasing with line samples [C]//RenderingTechniques2000ProceedingsoftheEurographicsWorkshop，2000：197-205.

[4] 汪麗娜. 飛機座艙顯示系統儀表畫面的反走樣技術的研究[D]. 長春：吉林大學，2007.

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

[5] 馬培華. 直線反走樣生成和裁剪的算法改進研究[D]. 南寧：廣西大學，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] 賈銀亮，張煥春，經亞枝. 基于FPGA的直線反走樣算法研究[J]. 計算機技術與發展，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]. 南京航空航天大學學報，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. 計算機圖形學 [M]. 3版.北京：電子工業出版社，2005：70-79.

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

[10] 杜晨輝. 提高飛機座艙顯示系統羅盤畫面顯示質量的研究[D]. 南京：南京航空航天大學，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]. 計算機工程與應用，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亮度調節中的人眼感受非線性校正[J]. 鄭州大學學報：工學版，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] 姜丹丹，李成貴. 全羅盤畫面中的刻度線反走樣技術[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)