一种快速精确的反走样直线算法及其嵌入式实现

刘小燕,李秋生,袁新娣

(赣南师范学院 物理与电子信息学院,江西 赣州　341000)



一种快速精确的反走样直线算法及其嵌入式实现

刘小燕,李秋生,袁新娣

(赣南师范学院 物理与电子信息学院,江西 赣州341000)

摘要:针对嵌入式应用中快速绘制反走样直线的问题,分析了各种反走样直线绘制方法的特点,给出了一种快速精确的反走样直线绘制算法,该算法指出了图像边缘像素点的灰度值与边缘点到直线中心的距离、直线的斜率和直线的灰度值的关系．该算法可用于绘制任意宽度、任意灰度的直线,有详细的实现过程,并对算法进行了优化,提高了算法的执行速度．

关键词:反走样;嵌入式系统;直线绘制

反走样是图形学中的重要概念,用以防止“锯齿”现象的出现．走样指的是光栅图形显示器中用离散量表示连续量引起的失真,消除这种失真现象即为反走样[1]．在具有多灰度级的显示器上,可以通过控制灰度级的缓慢变化来缓解此类问题．图1(a)和(b)为两条宽度和灰度都一致的直线.其中图1(a)未进行反走样处理,失真较大;图1(b)为进行了反走样处理,失真较小．由于图形的走样对图形质量有很大的影响,所以反走样技术领域的研究也一直是计算机图形学的研究热点．

反走样方法很多[2-10],一是提高屏幕分辨率,嵌入式设备的分辨率一般较低,不适合此种方法;二是全屏图像处理,先绘制直线,然后对整个图形做平滑处理以消除走样,这种方式费时较长,占用内存较多,不适合在嵌入式系统中应用;三是图元生成时反走样,绘制和反走样同时进行,可大大提高处理速度,非常适合嵌入式应用,常见的算法有Wu直线反走样绘制算法及其改进算法．Wu算法原理:跨骑着直线绘制一对像素,跨骑直线的像素对中,越靠近直线的像素应该越亮,沿着直线长度画这样的像素对,就可以得到一条Wu反走样直线．这些算法在嵌入式应用中有一定的局限性,如不能很好地支持任意线宽、算法效率不高、反走样效果不精确等．

第三类反走样算法的关键问题是直线的边缘像素点灰度值的计算问题[11]．文献[1-2]指出,图像边缘像素点的灰度值Ii与边缘点到直线中心的y轴方向距离di有关[1]

Ii=max(0,min(1.0,0.5*Wy-di+0.5))，

(1)

其中：Wy为y轴方向线宽．

作者认为图像边缘像素点的灰度值除了与边缘点到直线中心的距离有关外,还与直线的斜率和直线的灰度值有关,目前未见文献有相关分析,论文拟对此进行分析．另外,在嵌入式应用中,受硬件限制,内存较为紧张,工作速度较慢,针对这种情况,在反走样算法的实现过程中,论文通过分析,改进算法,尽可能地提高算法的执行速度．

1分析与推导

设直线斜率的绝对值|s|≤1．设G为直线灰度(灰度值范围Gm～GM),di为像素(xi,yi)到直线中心线的距离

(2)

其中：yc为xi处直线中心的y轴坐标．

当斜率的绝对值|s|=1,由图2可知:当di≤(Wy/2-1),该点在直线内部,因此灰度为G,其中Wy为直线在y轴方向上的宽度;当di≥(Wy/2+1),该点在直线外部,灰度为背景灰度;当(Wy/2-1)

若斜率的绝对值|s|=0,由图3可知:当di≤(Wy/2-0.5),该点在线内,灰度为G;当di≥(Wy/2+0.5),该点在线外,灰度为背景灰度;当(Wy/2-0.5)

因此,对于任意斜率s,可近似认为:当di≤(Wy/2-0.5-|s|/2),该点在线内,灰度为G;当di≥(Wy/2+0.5+|s|/2),该点在线外,灰度为背景灰度;当(Wy/2-0.5-|s|/2)

(3)

其中:a、b为常数,当di=Wy/2-0.5-|s|/2时,gi=G;当di=Wy/2+0.5+|s|/2时,gi=Gm.代入式(3),求出a和b,则式(3)可写为

(4)

式(1)仅给出了图像边缘像素点的灰度值与边缘点到直线中心的y轴方向距离di的关系,从式(4)中可以看出,直线边缘点的灰度gi除了与di有关,还与直线斜率绝对值|s|和直线的灰度值G有关系,论文算法更为准确．当斜率的绝对值|s|>1时,将x、y轴互换即可．

2算法实现过程

设显示屏分辨率为X×Y,以左下角为原点建立坐标系,显示屏右上角坐标则为(X-1,Y-1)．设要绘制一条直线,起点坐标(X0,Y0),终点坐标(X1,Y1),设X0≤X1,否则将X0和X1互换,线宽为W,灰度为G(设灰度值范围为Gm～GM),反走样绘制过程如下[12-13]:

(1) 计算斜率的绝对值|s|,若|s|≤1,绘制直线以x方向为主,否则以y方向为主,这里只讨论|s|≤1的情况.

(2) 设|s|≤1,计算y轴线宽Wy为

(5)

(3) 在x轴(行)上从X0开始以一个像素为步长移动,到X1结束,对y轴(列)进行填充,计算xi(X0≤xi≤X1)处直线中心的y轴坐标yc为

(6)

(4) 在行坐标xi(X0≤xi≤X1)处填充一列像素,yi由0增加至Y-1,填充像素(xi,yi)的灰度值gi取决于该像素距直线中心的距离di,gi计算公式为式(4),di计算见式(2).

(5) 根据gi的计算结果分3种情况填充像素:① 若gi≤Gm,则不填充(也可用Gm填充,但是这样会增加程序运行时间,且会删除背景图像);② 若gi>G,则取灰度值G进行填充;③ 若Gm

3算法优化

嵌入式应用对直线算法的执行速度比较关切,可在以下两个方面对算法进行优化,提高算法处理的速度:

(1) 非边缘点的处理．对一列像素进行填充时,yi由0增加至Y-1,要计算Y次公式(4),耗费较多时间．而实际情况仅需对直线边缘像素点计算灰度并填充,直线内部直接用灰度G填充,直线外部不做任何计算和处理．常见的做法是先检测直线的边缘,再对直线内部、边缘和外部分别处理,运算量较大．由于嵌入式应用中显示屏分辨率有限,直线宽度一般较小,为了简化运算,可将直线内部像素点和边缘像素点统一处理,直线外部不处理．改进方案为:yi由yc(yc先取整)开始增加,当计算到某个像素点灰度值gi≤Gm(或yi=Y-1)时停止;yi再由yc开始减少,当计算到某个像素点灰度值gi≤Gm(或yi=0),则结束本列像素的填充．仅计算并填充直线内部和直线边缘上的像素点,大大加快了计算速度．

(2) 去浮点优化．上述算法中|s|、wy、yc均为浮点数,式(4)~(6)包含浮点运算的乘法、除法及开方,耗时较多．可根据绘图精度将这些变量乘以适当的倍数(该实验乘以倍数10),以整数运算取代浮点运算．

4结果分析

4.1　算法反走样效果分析

显示屏幕分辨率32×32,绘制一条宽度为4、灰度为200、斜率为1的反走样直线,绘制结果局部放大图如图4所示．其中图4(a)为论文算法的反走样直线绘制结果,图4(b)为采用文献[4]算法的反走样直线绘制结果.从图中可以看出图4(b)直线的“锯齿”较图4(a)明显,论文算法的直观反走样效果更好．嵌入式应用中由于分辨率低,对反走样的精度要求较高,论文算法可绘制各种宽度、灰度和斜率的直线,精度高,在显示屏分辨率较低嵌入式系统中,反走样效果理想．

绘制一条宽度为2、灰度为255、斜率接近0的反走样直线,绘制结果如图5所示．论文浮点运算绘制结果如图5(a)所示,采用文献[1]中算法结果如图5(b)所示,图5(c)为论文反走样直线算法的去浮点优化结果．

从图5(a)、(b)可以看出在直线宽度仅为2个像素、斜率接近0的条件下,论文绘制反走样直线算法的效果较为理想,略优于文献[1],但差别不大．从图5(c)可以看出,浮点优化后,反走样效果比较理想,但是绘图的精度有所降低,直线斜率有误差．由分析得知,若去浮点优化时乘以了倍数N,则斜率误差小于等于(100/N)%．

经典算法反走样效果不够精确,且不能很好地支持任意线宽、任意灰度,算法效率不高．而嵌入式应用中由于分辨率低,对反走样的精度要求较高,从图4、5可以看出,论文算法可绘制各种宽度、灰度和斜率的直线,精度高.在显示屏分辨率较低嵌入式系统中,反走样效果理想,反走样效果优于文献[1]的算法,且直线斜率越大,二者反走样效果差别越大．

4.2　算法复杂度分析

在X轴上以一个像素为步长移动,设X轴上的步数为N,Y轴方向的转换宽度为M．对于X轴的每一步长,需要按照浮点数计算M次灰度值,需要O(M)复杂度的浮点加减运算,而X轴上的步数为N,则总的绘制直线复杂度为O(M×N)次浮点加减运算．

4.3　算法效率分析

嵌入式应用多用于实时控制,对算法的执行速度较敏感.论文算法主要在边缘点的处理和去浮点优化两个方面对算法进行优化,提高算法处理的速度．系统主频为60 MHz,表1为绘制图4直线时各算法执行速度对比.从表中可以看出,虽然论文算法在优化前运行时间高于文献[4]算法,但是进行非边缘点优化处理后程序运行时间仅为优化前的约4%,进行去浮点算法优化后程序运行时间为优化前的约35%,若同时进行这两种优化则程序运行时间仅为优化前的不到2%,算法运行速度提高显著．

表1　各算法绘制图4直线所需运行时间对比

5结束语

论文详细分析了反走样直线绘制算法的原理,得到一种快速精确的反走样直线绘制算法,给出其在嵌入式系统的详细实现过程,并对结果进行了分析．经验证,该反走样直线绘制算法高效、精确,具有一定参考价值．

参考文献：

[1]李震霄,何援军. 任意宽度直线的绘制与反走样[J]. 武汉大学学报：工学版, 2006，39(4):130-133.

[2]骆朝亮. 一种支持多线宽直线反走样算法[J]. 计算机技术与发展, 2010,20(4):102-105.

[3]舒若,张焕春. 一种基于Bresenham算法的直线快速反走样技术[J]. 机械制造与研究, 2002(5):15-17.

[4]Donald H. 计算机图形学[M].3 版,蔡士杰译.北京:电子工业出版社, 2010.

[5]彭群生,金小刚.计算机图形学应用基础[M].1版.北京:科学出版社, 2009.

[6]张波,张焕春.罗盘刻度线反走样快速绘制算法的改进研究[J]. 计算机辅助设计与图形学学报, 2003,15(1):71-75.

[7]张诗诗，徐尔.远约束多目标优化的一种新的下降算法[J].信阳师范学院学报：自然科学版，2014，27(4)：499-520.

[8]杭后俊,付勇. 一种基于加权区域采样的直线反走样生成算法[J]. 计算机技术与发展, 2009,19(6):138-142.

[9]韩丽,唐棣. 一个快速有效的直线反走样算法[J]. 小型微型计算机系统, 2005,26(3):509-511.

[10]王宇平. 光栅显示图形中直线反走样算法的改进[J]. 哈尔滨理工大学学报, 2008,13(3):51-54.

[11]宋莹,陈科.基于图像分块的边缘检测算法[J]. 计算机工程, 2010,36(14):196-197.

[12]Wu X. An efficient anti-aliasing technique [J]. Computer Graphics,1991,25(4):143-152.

[13]Hoberock J, Lu V, Jia Y T. Stream compaction for deferred shading[C]//Proc of the High Performance Graphics’09. New York, USA:ACM Press, 2009:173-180.

(责任编辑朱夜明)

A rapid and precise anti-aliasing line drawing algorithm and its

implementation in embedded system

LIU Xiao-yan,LI Qiu-sheng,YUAN Xin-di

(School of Physics and Electronic Information, Gannan Teachers’ College, Ganzhou 341000, China)

Abstract:By analyzing the characteristics of various anti-aliasing line drawing algorithm, an algorithm for drawing anti-aliased straight lines in embedded systems was presented, which pointed out that the gray level of the pixels on line edge has relations with the distance between the pixels on line edge and on line center, the slope and the gray level of straight line. The algorithm could be used to draw line of any width and of any gray level. A detailed implementation process was offered in the paper, and the algorithm was optimized to improve the execution speed.

Key words:anti-aliasing; embedded system; line drawing

作者简介：曹启龙(1983-),男,山东省泰安市人,宜宾学院讲师,博士.

基金项目:教育部全国大学生创新创业训练计划项目(201210641106);四川省教育厅科研基金资助项目(13ZA0198,13ZB0211)

收稿日期：2014-07-05

doi:10.3969/j.issn.1000-2162.2015.02.007

中图分类号：TP391

文献标志码:A

文章编号:1000-2162(2015)02-0032-05