基于未加权区域采样的直线反走样算法

毛 峡 刘运龙 薛雨丽

（北京航空航天大学 电子信息工程学院，北京 100191）

光栅图形显示器由一系列离散像素组成，利用未加入反走样技术的简单直线生成算法（例如Bresenham算法［1］）绘制的非垂直非水平直线会在该类显示器上出现明显锯齿状或阶梯状边缘［2］，在某种场合将会严重影响显示效果.这种用离散量表示连续量引起的失真，称为走样（aliasing）；而用于减少或消除走样的技术，称为反走样（anti-aliasing）［3］.反走样在光栅图形显示［4－12］、共聚焦三维数据表面重建［13］、地图可视化表达［14－15］等领域均有广泛应用.

目前，直线反走样技术主要有两类：区域采样和Wu算法.区域采样又可分为未加权区域采样和加权区域采样，前者在确定显示屏上某一像素灰度值时需要在重叠区域（该像素与代表直线的矩形相互重叠的部分）上对加权函数w（x，y）求积分，此加权函数恒为1；后者计算方法与前者相同，只是所选加权函数w（x，y）不恒为1.Wu算法［7－8］基于距离加权确定像素灰度值，其在二像素宽直线的反走样方面至今仍是经典解决方案［2］.

对于具有多灰度的光栅图形显示器，未加权区域采样和加权区域采样通过控制像素灰度缓慢变化从而很好地实现反走样.至今，以加权和未加权区域采样算法为基础已延伸出多种能有效解决直线走样问题的算法［5－9］.

文献［5］从频域的角度剖析走样现象产生的机理，并将二维圆锥形滤波器应用于直线反走样，虽然该加权区域采样算法能取得很好的反走样效果，但是由于该算法在计算像素与理想直线的距离时需要用到浮点数加法和乘法，并且在确定灰度值时用到了取整运算，这些运算利用FPGA（Field Programmable Gate Array）实现所需周期过多，不利于FPGA硬件的快速实现.

文献［6］给出一种基于加权区域采样的离散化算法，在确定像素灰度值时不再使用运算量很大的积分运算，算法效率相对于传统算法更优，但是该算法在计算当前像素灰度值时仍会用到浮点运算以及类型强制转换运算，不利于FPGA硬件实现.

文献［7］和文献［8］提出了经典Wu直线反走样算法.相比于Bresenham算法，利用 Wu直线反走样算法生成的直线能达到很好的平滑效果，但是Wu算法需要用到较多的浮点数乘法和取整运算，计算比较复杂.

文献［9］分析了屏幕正方形像素和一个像素宽直线条相交的7种情况，并给出相应的重叠区域面积计算方法，该方法用到了不利于FPGA硬件实现的除法运算.

综上所述，为实现反走样，传统区域采样和Wu算法使用大量不利于FPGA硬件实现的运算.本文通过结合Bresenham算法和传统未加权区域采样的思想，提出一种利于FPGA硬件实现的反走样直线生成新算法.

1 直线生成与反走样概述

1.1 直线生成算法

计算机图形学中的直线生成算法（或直线扫描转换算法）通过在光栅图形显示器上寻找与理想直线距离最近的一系列离散像素近似表示直线.

目前生成单像素宽直线的算法主要有3种：数值微分法、中点画线法和Bresenham算法［16］.

1.1.1 数值微分法

数值微分法是最简单、直观的直线生成算法.假设拟生成直线的斜率处于0～1之间（其它情况可通过先转换x和y轴再处理），算法原理为：沿着x轴方向根据直线斜率从起点到终点依次确定与直线距离最近的一组离散像素.

由于该算法中的像素纵坐标y和直线斜率k必须用浮点数表示，且每次循环计算均需对y进行舍入取整，所以该算法不利于FPGA硬件实现.

1.1.2 中点画线法

假设拟生成直线的斜率处于0～1之间，若直线在x方向增1，则在y方向的增量只能在0～1之间.中点画线法的思想为：将当前列（设横坐标为x0）与直线距离最近的两个像素（x0，y0），（x0，y0＋1）的中点坐标（x0，y0＋0.5）代入函数F（x，y）（F（x，y）＝0为直线方程）；若F（x0，y0＋0.5）≥0，认为当前列属于直线的点为（x0，y0）；若F（x0，y0＋0.5）＜0，则认为当前列属于直线的点为（x0，y0＋1）.

经过简单换算后，中点画线法只包含整数加减及比较运算，因此该算法利于FPGA硬件实现.

1.1.3 Bresenham算法

Bresenham 算法［1，17－18］被公认为最有效的直线生成算法.假设拟生成直线的斜率处于0～1之间，该算法基本思想是：直线每走一步，横坐标x改变一个像素单位，纵坐标y根据误差项e的符号决定是否改变.

Bresenham算法同样可改写为只包含整数加减及比较运算的形式，因此该算法利于FPGA硬件实现.

1.2 区域采样直线反走样算法

区域采样直线反走样算法的提出基于两点假设：第一，将像素看成有一定面积的规则区域（本文将像素看成互不相交的正方形）；第二，拟生成直线段并非无宽度理想线段，而是一个宽度至少为一个像素单位的线条.如图1所示，正方形代表一个像素，内部实心圆点为像素中心，矩形代表拟生成的单像素宽线条，虚线为矩形中轴线.

图1 代表直线的矩形和代表像素的正方形

区域采样算法可分为未加权区域采样与加权区域采样两类.由于加权区域采样所用到的加权函数w（x，y）不恒为1，因此需要花费大量计算用于确定在重叠区域上对w（x，y）所求的积分，而未加权区域采样则只需计算重叠区域的面积，因此，未加权区域采样的运算量往往少于加权区域采样.然而，未加权区域采样在计算重叠面积时仍需大量浮点数乘法，在确定像素灰度值时需用到舍入运算，这些运算使该算法复杂度过高，不利于FPGA硬件实现.

1.3 Wu直线反走样算法

Wu直线反走样算法［7－8］是计算机图形学反走样技术领域较早使用的一种经典算法，适用于生成二像素宽的反走样直线.Wu算法实际上是一种基于距离加权的反走样算法，其基本思想为：沿长轴方向前进一个像素单位，在短轴方向有两个像素距离理想直线最近，灰度值由它们与直线的距离确定，距离越近灰度值越大，两个像素灰度值之和等于像素颜色的最大灰度.

由于Wu直线反走样算法能满足通常需求且算法本身计算不复杂，因此该算法在很多场合得到广泛应用.

2 新的直线反走样算法

鉴于传统未加权区域采样直线反走样算法不利于FPGA硬件实现，本文将Bresenham算法与未加权区域采样思想相结合，提出一种利于FPGA硬件实现的直线反走样算法，该算法可用于快速生成三像素宽的反走样直线段.

2.1 算法的基本原理

本文算法的应用前提是光栅图形显示器支持多级灰度显示，例如64级和256级.

算法的基本原理是将与矩形区域有重叠的像素均分为M个子像元，M等于灰度级数，通过统计被覆盖子像元的数量确定像素灰度值.例如，若某像素被覆盖子像元数量为N，则该像素灰度值为N－1，特殊地，若N＝0，则像素灰度值为0.

2.2 算法的实现

2.2.1 非端点部分的处理

图1的实线矩形框代表拟生成的直线段，虚线为矩形的中轴线，介绍本文算法的具体实现时只讨论直线斜率处于0～1之间的情况，其余斜率情况可通过将x和y轴互换处理.本文算法流程如图2所示.

图2 本文算法流程图

假设光栅图形显示器支持256级多灰度显示，结合图1与图2将本文算法主要步骤叙述如下：

1）判断当前列是否被矩形区域覆盖.

由于拟生成直线的起点坐标（x0，y0）和终点坐标（x1，y1）已知，因此只需判断当前列的横坐标X是否处于x0～x1的范围内即可.若X处于x0～x1之间，说明当前列存在被矩形区域覆盖的现象，执行步骤2）操作；否则，直接结束该直线的生成操作.

2）确定当前列可能有灰度值的3个像素.

由图1可知，单像素宽的直线段在当前列最多与3个相邻像素存在重叠区域，其中处于中间位置的像素距离虚线最近，而该像素坐标可通过对虚线应用Bresenham算法快速地进行确定.假设中间像素的坐标为（Xmid，Ymid），则另外两个像素的坐标分别为（Xmid，Ymid＋1）和（Xmid，Ymid－1）.

3）均匀分割步骤2）中确定的3个像素.

根据算法原理，将3个像素各自均匀分割成数量等同于灰度级数的子像元.由于假设光栅显示器的灰度级数为256，因此可将像素均匀分割为16×16子像元，图3给出像素的分割示意图.

图3 像素均匀分割结果示意图

4）确定当前列距离矩形两边最近的两组子像元.

根据Bresenham算法可快速确定这两组子像元，其中每组包含16个子像元.这两组子像元给出矩形区域在当前列覆盖的边界情况.图4给出当前列矩形两边经过Bresenham算法确定的两组子像元.

图4 当前列确定的两组子像元

5）统计3个像素被矩形区域覆盖的子像元数量.

根据步骤4）确定的两组子像元，依次统计当前列（共包含16个子列）每一个子列分别属于3个像素的子像元数量，最后将16个子列的统计结果进行累加，从而得到3个像素被矩形区域覆盖的子像元数量.

6）确定像素灰度值.

3个像素的灰度值分别等于各自被矩形区域覆盖的子像元数量减1，例如，假设像素（x，y）共有N个子像元被矩形区域覆盖，则该像素的灰度值应为N－1，特殊地，若N＝0，则灰度值为0.接着，将记录当前列的横坐标X增1，继续执行步骤1）操作.

2.2.2 端点部分的处理

在确定直线端点（起点和终点）所在列像素灰度值时不能直接采用上述方法，而需进一步分析.

图5给出直线起始端点的放大图，在直线斜率不为0时，矩形两边的起点（P1和P5）横坐标不相等（斜率为0时，两横坐标相等）.这时，利用Bresenham算法确定两组子像元并统计图中像素被覆盖子像元的数量将会存在一定困难.

考虑到图中三角形A区域（由P1，P2和P3确定）与三角形B区域（由P3，P4和P5确定）面积相等，因此有

式中，NA与NB分别表示区域A与B覆盖的子像元数量.

此外，还有

式中，C为由P2，P3，P5，P8，P7和P6确定的多边形区域.

根据式（2）可知，确定图中像素的灰度值只需统计B＋C区域的子像元数量，由于B＋C区域两条边界的起点（P2和P4）横坐标相同，此时以P2，P4为起点利用Bresenham算法确定图5中的像元所在列的两组子像元后，即可方便地统计出该列各个像元中被矩形区域覆盖子像元的数量，从而确定该列像元的灰度值，可见以P2，P4作为矩形两长边的等效起点可简化统计被覆盖子像元的步骤.利用类似方法可简化直线段终点所在列像素灰度值确定的工作，这里不再详细说明.

图5 直线起始端点放大示意图

3 实验结果与分析

本文分别从仿真速度与运算次数统计、反走样效果两个方面将传统未加权区域采样算法、Wu算法以及本文算法进行对比.

3.1 仿真速度与运算次数统计

为验证本文算法仿真速度，在Pentium（R）2.80GHz双核、内存3GB的计算机，用 MATLAB 7.11.0编程完成传统未加权区域反走样算法、Wu算法以及本文提出的反走样算法，利用这3种算法分别计算3条拟生成直线所有像素的坐标和灰度值.表1给出3条直线的起点和终点坐标，表2给出3种算法分别生成3条直线所需时间.

表1 3条直线的起点和终点坐标

表2 3种算法生成3条直线所需时间对比

由表2可知，本文算法在软件平台上生成直线的效率约比传统未加权区域采样算法快2倍，与经典Wu算法效率相差不大.但是Wu算法在确定像素灰度值时需用到大量浮点数乘法、四舍五入以及浮点数加减法，这些运算对于FPGA硬件来说较复杂，执行效率不高.本文算法将传统未加权区域采样算法中的浮点运算转换为整数加减法运算，确保算法易于FPGA硬件实现.表3为3种算法分别生成直线1所需执行的各种运算次数统计表.

表3 3种算法生成直线1所需运算次数统计

可见，本文算法主要运算由整数加减法完成，利于FPGA硬件实现，能达到FPGA硬件加速目的.

3.2 反走样效果

为验证本文算法的反走样效果，利用MATLAB 7.11.0软件仿真平台完成基于Bresenham算法以及3种反走样算法生成直线1与直线2的任务.图6的4个子图分别是对应算法仿真结果放大8倍后的效果图，图7的两个子图分别给出Wu算法与本文算法仿真结果放大16倍后的效果图.

图6 4种算法仿真结果图

图7 Wu算法与本文算法仿真效果图对比

对比并分析图6与图7的各个子图，可得如下4个分析结果：

1）由于Bresenham算法没有加入反走样思想，因此由该算法所得直线（图6a）边缘存在明显锯齿状或阶梯状，而由另外3种反走样算法生成所得直线（图6b、图6c和图6d）明显比图6a的平滑；

2）Wu算法生成的反走样直线（图6c）平滑效果较好，但是直线整体灰度偏低，这是由于Wu算法用于生成二像素宽直线，在短轴方向距离直线最近的两个像素点灰度之和仅为像素颜色的最大灰度，从而造成直线整体灰度降低；

3）对比图6的后3个子图可知，由本文算法（图6d）与传统非加权区域采样算法（图6b）分别生成的直线平滑度相差不大，这两种算法生成的直线整体灰度比Wu算法直线高，使得直线看起来更清晰；

4）对比图7的两个子图可知，由于Wu算法基于距离加权计算像素灰度值，所以沿着直线方向，Wu算法所得直线某些相邻像素灰度值相差较大，远处观看时由该算法生成的直线会出现“断断续续”的现象，而基于面积加权的本文算法相邻像素灰度值差异则较小.

综上所述，相比于Wu算法，本文算法的反走样效果更佳.

4 结 束 语

通过结合Bresenham算法以及未加权区域采样的思想，本文提出一种符合FPGA硬件实现特点的反走样直线生成新算法.本文算法可用于在支持多灰度的光栅图形显示器上生成三像素宽的反走样直线.本文算法摒弃传统算法使用大量不利于FPGA硬件实现的浮点运算，而主要采用整数加减法实现，因此易于FPGA硬件实现.仿真结果表明：本文算法不但反走样效果比Wu算法更好，而且仿真效率远高于传统未加权区域采样算法.

（References）

［1］Bresenham J E.Algorithms for computer control of a digital plotter［J］.IBM Systems Journal，1965，4（1）：25－30

［2］李震霄，何援军.任意宽度直线的绘制与反走样［J］.武汉大学学报，2006，39（4）：130－133

Li Zhenxiao，He Yuanjun.Arbitrary width line generation and anti-aliasing［J］.Journal of Wuhan University，2006，39（4）：130－133（in Chinese）

［3］孙家广，杨长贵.计算机图形学［M］.北京：清华大学出版社，1998 Sun Jiaguang，Yang Changgui.Computer graphics［M］.Beijing：Tsinghua University Press，1998（in Chinese）

［4］牛连强，张丹，陶峰.直线的光栅转换算法与快速反走样绘制技术［J］.沈阳工业大学学报，2012，34（1）：73－78

Niu Lianqiang，Zhang Dan，Tao Feng.Raster-conversion algorithm and fast anti-aliased drawing technique for line［J］.Journal of Shenyang University of Technology，2012，34（1）：73－78（in Chinese）

［5］沈强，张波，陈淑珍，等.计算机图形学反走样技术及实现［J］.武汉大学学报，1997，43（1）：113－118

Shen Qiang，Zhang Bo，Chen Shuzhen，et al.Antialiasing technique and applications in computer graphics［J］.Journal of Wuhan University，1997，43（1）：113－118（in Chinese）

［6］杭后俊，付 勇.一种基于加权区域采样的直线反走样生成算法［J］.计算机技术与发展，2009，19（6）：138－141

Hang Houjun，Fu Yong.One antialiasing algorithm based on weighting region sampling［J］.Computer Technology and Development，2009，19（6）：138－141（in Chinese）

［7］Wu Xiaolin，Rokne J G.Double-step incremental generation of lines and circles［J］.Computer Vision，Graphics and Image Processing，1987，37（3）：331－344

［8］Wu X.An efficient anti-aliasing technique ［J］.Computer Graphics，1991，25（4）：143－152

［9］孔令德.基于面积加权反走样算法的研究［J］.工程图学学报，2009，4：49－54

Kong Lingde.Research on area-weighted antialiasing algorithm［J］.Journal of Engineering Graphics，2009，4：49－54（in Chinese）

［10］娄剑涛，王秀和.基于对称的反走样直线生成算法［J］.计算机工程与应用，2011，47（1）：173－175

Lou Jiantao，Wang Xiuhe.Anti-aliasing line drawing algorithm based on symmetry［J］.Computer Engineering and Applications，2011，47（1）：173－175（in Chinese）

［11］袁一鸣，段凤阳，李赞平.罗盘仪表绘制中快速反走样算法的研究［J］.舰船电子工程，2011，31（9）：60－62

Yuan Yiming，Duan Fengyang，Li Zanping.Research on fast anti-aliasing algorithm in compass display［J］.Ship Electronic Engineering，2011，31（9）：60－62（in Chinese）

［12］张鹏，王良.嵌入式图像系统的改进Bresenham反走样算法的应用［J］.电子设计工程，2011，19（4）：117－119 Zhang Peng，Wang Liang.Application of improved Bresenham anti-aliasing algorithm based on embedded image system［J］.Electronic Design Engineering，2011，19（4）：117－119（in Chinese）

［13］薛斌党，姜志国，周孝宽.共聚焦三维数据表面重建的一种反走样方法［J］.北京航空航天大学学报，2005，31（10）：1054－1057

Xue Bindang，Jiang Zhiguo，Zhou Xiaokuan.Anti-aliasing technique for surface reconstruction of confocal data［J］.Journal of Beijing University of Aeronautics and Astronautics，2005，31（10）：1054－1057（in Chinese）

［14］梅洋，李霖，贺彪.基于边界反走样算法的地图可视化研究［J］.武汉大学学报，2008，33（7）：759－761

Mei Yang，Li Lin，He Biao.Cartographic visualization based on boundary anti-aliasing［J］.Journal of Wuhan University，2008，33（7）：759－761（in Chinese）

［15］邓术军，郭建星.一种适合于地图出版符号的反走样算法研究［J］.武汉大学学报，2005，30（12）：1120－1123

Deng Shujun，Guo Jianxing.An anti-aliasing algorithm suitable to map publishing symbol［J］.Journal of Wuhan University，2005，30（12）：1120－1123（in Chinese）

［16］Foley J D.计算机图形学导论［M］.北京：机械工业出版社，2004

Foley J D.Introduction to computer graphics［M］.Beijing：China Machine Press，2004（in Chinese）

［17］Li Xiang，Shao Xiaoyan.Fast line drawing algorithm by circular subtraction based on Bresenham［J］.Proceeding of SPIE，2012，83490L：1－6

［18］Norbert Spie，Michael Zapf，Nicole V Ruiter.Evaluation of the Bresenham algorithm for image reconstruction with ultrasound computer tomography［J］.Proceeding of SPIE，2011，796803：1－9