小角度直线反走样的改进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)