Bresenham（共4篇）
Bresenham 篇1
1 直线Bresenham算法
设直线从起点(x1,y1)到终点(x2,y2)。直线可表示为方程y=mx+b,|m|≤1,其中
沿线路径的像素位置由以单位x间距的取样来决定,从给定线段的左端点(x1,y1)开始,逐步处理每个后继列(x位置),并在扫描线y值最接近线段的像素上绘出一点。图1显示了这个过程的第k步,用d1和
d2来标识两个候选像素与线段数学路径的垂直偏移。
那么,两个候选像素与线段数学路径的垂直偏移分别为:
其中:xk+1=xk+1,yk+1=yk+1
这两个分离点的差分为:
如果d1
2 中点Bresenham算法
将直线方程转换为:
该直线方程将平面分为三个区域:
对于直线上的点,F(x,y)=0;
对于直线上方的点,F(x,y)>0;
对于直线下方的点,F(x,y)<0。
假设|m|≤1,在第k步,点P(xi,yi),下一个像素可能取的点为Pu(xi+1,yi+1),Pd(xi+1,yi),由可以求出Pu,Pd的中心点M的坐标为(xi+1,yi+0.5)。
判别式:,则有
当d<0,误差项的递推
当d≥0,误差项的递推
初始值的计算:
0≤k≤1时Bresenham算法的步骤为:
1)输入直线的两端点p0(x0,y0)和p1(x1,y1);
2)计算初始值x、y,d=0.5-k,x=x0、y=y0;
3)绘制点(x,y)。判断d的符号;若d<0,则(x,y)更新为(x+1,y+1),d更新为d+1-k。
否则(x,y)更新为(x+1,y),d更新为d-k。
4)当直线没有画完时,重复步骤3。否则结束。
3 改进中点Bresenham算法
用2d△x代替d:
1)输入直线的两端点P0(x0,y0)和P1(x1,y1);
2)计算初始值x、y,d=△x-2△y,x=x0、y=y0;
3)绘制点(x,y),判断d的符号;若d<0,则(x,y)更新为(x+1,y+1),d更新为d+2△x-2△y;
否则(x,y)更新为(x+1,y),d更新为d-2△y。
4)当直线没有画完时,重复步骤3。否则结束。
4 结束语
中点Bresenham算法是直线Bresenham的改进,改进的算法不必计算直线的斜率,不用做除法,不用浮点数,只用整数,而且改进的算法运算速度很快,并且适于用硬件实现。
摘要：直线Bresenham算法的基本原理是采取对整型参量的符号进行检测,整型参量的值正比于两像素与实际线段之间的偏移。直线的中点Bresenham算法是依据下一个点可能出现的两个点的中间点处在直线的位置来判断下一个点的取舍。
关键词：Bresenham算法,斜率,误差项
参考文献
[1]孙正兴,周良.计算机图形学基础教程[M].北京:清华大学出版社,2004.
[2]潘云鹤,董金祥.计算机图形学—原理、方法及应用[M].北京:高等教育出版社,2003.
[3]陈传波,陆枫.计算机图形学基础[M].北京:电子工业出版社,2002.
[4]孙家广.计算机图形学[M].3版.北京:清华大学出版社,1999.
[5]唐泽圣.计算机图形学基础[M].北京:清华大学出版社,1995.
[6]Hearn D,Baker M P.Computer Graphics(C Version)[M].Prentice Hall,1997.
Bresenham 篇2
直线是生成各种图形的基本元素,直线生成算法是其它各类图形算法的基础,因此直线的生成算法已得到了人们的广泛研究,并已出现许多有效的算法,其中最著名的是Bresenham算法。该算法的优点在于不需要进行小数和取整运算,只需要使用整数加法和乘法来计算待生成的像素点。Bresenham算法的缺点在于效率不高,没有充分利用像素之间的相关性,一次计算只能生成一个像素点[1,2]。
提高直线生成效率可以从两方面考虑:减少生成每个像素点所必需的计算量或一次计算可以生成多个像素点以减少循环次数。Wu和Rokne对Bresenham算法进行了改进,提出了双步直线生成算法,该算法一次预测两个而不是一个像素,从而提高了直线生成算法的效率[1]。双步直线生成算法的效率提高有限,某些情况下与Bresenham算法效率基本一样。文献[3,4,5,6,7,8]对Bresenham算法进行了一定程度的改进,但改进幅度不大,主要表现在:改进算法往往引入了浮点运算甚至除法或取整运算,这恰恰破坏了Bresenham算法不进行小数和取整运算的特点。这些改进算法一次计算虽然可以画多个像素点,但运算更加复杂。
本文在对Bresenham算法、双步算法和现有改进算法进行深入研究后,充分认识到经典的Bresenham算法基本思想的重要性,又考虑到Bresenham算法本身的缺陷,提出了一种改进算法,克服了上述直线生成算法的弱点。新算法既保持Bresenham算法只需要使用整数加法和乘法运算,不需要进行小数和取整运算的优点,又可以通过一次计算生成两个像素行,因此执行效率明显高于其它直线生成算法,并且算法实现简单、运算量少。
1 算法原理
本文的算法和程序只对斜率在[0,1]之间的直线进行讨论,并设直线的起点为(x0,y0),终点为(x1,y1),且x1≥x0、y1≥y0,对于一般的情况可以利用变换求得。下面首先提出并证明两个结论,再在这两个结论的基础上介绍改进算法。
结论1 用Bresenham算法生成的直线在除起始和终止两像素行外,其它各像素行点亮的像素点个数m满足:
Q≤m≤Q+1
式中Q=[dx/dy](“/”表示除法、“[]”表示下取整)、dx=x1-x0、dy=y1-y0。
例如一条从(0,0)到(45,10)的线段,其Q=[dx/dy]=4,则该直线除起始和终止两像素行外,其它各像素行点亮的个数为4或5个。
证明:Bresenham算法利用当前被选中的像素来选择下一个像素点,如图1,P点已被选中,则直线的下一个像素点应该在E和NE中选择。
Bresenham算法考察E和NE的中点M,设F(x,y)为待生成直线,若F(M)>0,则M在直线下方,应选点NE,若F(M)≤0,则M不在直线下方,应选点E,Bresenham算法定义判定变量d=F(xp+1,yp+1/2),根据像素点的d值来选择:若d>0,则在下一个像素行点亮,即选点NE,若d≤0,则在原像素行再点亮一个像素点,即选点E。在选择像素点的同时计算下一个像素点的d值为下一个像素点的选择作好准备,选点NE时d=d+2(dy-dx),选点E时d=d+2dy。
现假设某像素行有m个像素点(m=1,2,…),各像素点的判定变量d值设为d1～dm,上一像素行最后一像素点的d值设为d0,下一像素行第一像素点的d值设为di,如图2所示。
若上一像素行不止一个像素点,由Bresenham算法:
且d0≤0、d1>0、dm≤0、di>0
将①②代入③则:
di=dm+2dy=d1+2(m-1)dy-2dx+2dy
=d0+2dy+2(m-1)dy+2(dy-dx)
=d0+2(m+1)dy-2dx
即d0+2(m+1)dy-2dx>0,而d0≤0,所以2(m+1)dy-2dx>0,可得m>dx/dy-1,又m为正整数,所以m≥Q。
而dm=d1+2(m-1)dy-2dx≤0且d1>0,则2(m-1)dy-2dx<0,所以m<dx/dy+1,又m为正整数,所以m≤Q+1。
则Q≤m≤Q+1。
若上一像素行只有一个像素点,则根据双步直线算法该直线斜率不小于1/2(此时Q=1或2),并且直线的各像素行包含像素点个数不超过2,很容易验证结论1成立。
综合以上推导,得证。
由结论1可知,除起始和终止两像素行外,其它各像素行点亮Q或Q+1个像素点,若某像素行第一个像素点d值为d1,只要确定本像素行第一个像素点之后第Q个像素点对应的判定变量值(设为dq)的符号就可以知道该像素行应点亮几个像素点。而dq=d1+2Qdy-2dx,若dq≤0则点亮Q+1个像素点,同时把dq加上2dy得到下一像素行第一个像素点的d值,否则点亮Q个像素点,此时dq即为下一像素行第一个像素点的d值。这样只需要计算一次d即可画出一个像素行的全部像素点,效率较高。
下面介珊渭扑鉗值,若直接用Q=[dx/dy]来求,会破坏Bresenham算法只需要使用整数加法和乘法、不需要进行小数和取整运算的优点。为了提高效率又不做取整运算,本文提出了一种用一条直线的第一像素行的像素点个数来求Q的算法。考察直线第一像素行的像素点个数与Q的关系可以得到结论2。
结论2 若用Bresenham算法生成的直线的第一个像素行(即y=y0的像素行)有n个像素点,则2n-2≤dx/dy<2n。
证明:若第一个像素行有n个像素点,则该直线第n个像素点d≤0而第n+1个像素点d>0,即
式中d0=2dy-dx为d的初值,即直线第二个像素点对应的d值,则
可得2n-2≤dx/dy<2n,得证。
由结论2,Q为2n-1或2n-2,再根据结论1,则直线除起始和终止两像素行外,其它各像素行点亮的像素点个数m有三种可能的取值:2n、2n-1或2n-2。
在生成一条直线时,只要在这三种情况中作出选择就可以一次性生成一个像素行。而这种选择也很简单。设一个像素行的第一个像素点判定变量为d0,考察该点之后第2n-2个像素点的判定变量d=d0+(4n-4)*dy-2dx,若d>0,则该行有2n-2个像素点,若d≤0,则需要进一步判断,若d>-2dy,则该行有2n-1个像素点,否则有2n个像素点,这样通过一或两次比较就可以确定一个像素行的像素点数目,一次预测一个像素行,从而提高直线生成效率。在点亮像素点的同时,根据该行像素点的个数m对d予以增量:d=d0+2m*dy-2dx,为下一像素行的计算作好准备。
为进一步提高算法效率,可以利用线段本身的对称性[9,10],用改进算法产生起点一侧的半条线段,至于终点一侧的半条线段,可以看成以终点为起点线段的生成。起点一侧的线段生在x或y方向每前进一个坐标单位,终点一侧的线段生成就在x或y方向后退一个坐标单位。
2 算法实现
从以上的描述可以实现优于Bresenham的直线生成算法,其C语言程序如下。程序中函数drapoi(x,y)用来画点(x,y),函数daw(int x,int y,int m)表示点亮(x,y)、(x+1,y)、(x+2,y)、……(x+m-1,y),共m个像素点。cre为像素行第一个像素点的d值到该点后面第2n-2个像素点的d值的增量。由于结论1对直线的第一和最后一行不成立,所以用Bresenham算法生成直线的第一行和最后一行,用改进算法生成其它各行。当同时由起点和终点向中点生成直线时,中点处的像素点可能出现重复点亮等错误,相应的处理程序省略。
程序一次可以预测一个像素行,再利用直线的对称性生成两个像素行,其效率比Bresenham算法明显提高,而且不需要取整和小数运算。
该算法已在计算机上得到了实现,经验证其执行效率明显优于传统的Bresenham算法。仍然以从(0,0)到(45,10)的线段生成为例,Bresenham算法每次计算生成一个像素点,共需要循环45次,执行加法和比较各45次;双步算法共需要循环23次,执行23次加法和33次比较;而本文提出的新算法只需要循环5次,执行加法和比较各10次。新算法的计算量和循环次数都较少。
表1是新算法与Bresenham算法分别编程实现后的效率比较,程序在Intel PentiumⅢ 866MHz,256MB内存的计算机上用VC++6.0运行,设直线的起点都是(0,0),表中所列时间为坐标计算时间,不包括像素点点亮时间,为消除Windows多任务系统带来的影响,数据为反复执行一百次后的算术平均值。
由算法原理,若直线只有一个像素行,新算法等同于Bresenham算法。从表1中第一列数据可见若直线斜率为1,新算法与Bresenham算法效率一样。其它情况下改进算法效率都优于Bresenham算法和双步算法。表1中从左向右三条直线斜率依次为1、0.1、0.01;除开始、最后两像素行外其它各行包含像素点个数依次为:1、10、100。新算法的效果从左向右越来越明显,可见待生成线段的斜率值越小,像素行包含的像素点越多,节省的计算量越大。
3 结 论
本文提出了一种基于Bresenham算法的直线生成算法。新算法利用直线的第一像素行的像素点数目来计算其余各像素行的像素点数目,一次可以预测一个像素行,再利用直线的对称性一次生成两个像素行,从而有效地提高了直线生成效率。
摘要：直线是图形的基本元素,其生成算法具有重要意义。在经典的Bresenham直线生成算法的基础上进行改进,提出一种新的多点生成算法。该算法利用直线的第一像素行的像素点数目来计算其余各像素行的像素点数目,一次可以预测一个像素行,再利用直线的对称性一次生成两个像素行。新算法既保持Bresenham算法不使用取整和小数运算的优点,又减少了计算量和循环次数,从而大幅提高了直线生成效率。
关键词：计算机图形学,Bresenham算法,偏差量
参考文献
[1]James D Foley.计算机图形学导论.北京:机械工业出版社,2004:48-56.
[2]Mel Slater.计算机图形学与虚拟环境.北京:机械工业出版社,2004:270-272.
[3]Asiful Haque,Mohammad Saifur Rahman,Mehedi Bakht.Drawing lines byuniform packing[J].Computers&Graphics,2006,30(2):207-212.
[4]Ramon Molla,Roberto Vivo.The stair algorithm[J].Journal of Graph-ics Tools,2002,6(2):17-25.
[5]Riemersma T.Image scaling with Bresenham[J].Dr.Dobb's Journal,2002,27(5):21-26.
[6]Felsner,Liotta,Wismath.Straight-line drawings on restricted integergrids in two and three dimensions[J].Journal of Graph Algorithmsand Applications,2003,7(4).
[7]Boyer V.Auto-adaptive step straight-line algorithm[J].ComputerGraphics and Applications,2000,20(5):67-69.
[8]郑宏珍.改进的Bresenham直线生成算法[J].中国图像图形学报,1999,4(7):606-608.
[9]林笠.基于Bresenham算法的四步画直线算法[J].暨南大学学报:自然科学版,2003,24(5):19-22.
Bresenham 篇3
在拍摄时成像设备和被拍摄景物之间发生相对运动而造成图像模糊称为运动模糊。在我们国家, 许多城市的道路上都安装有“天眼”设备, 高速公路的收费站也设有摄像头, 这些摄像设备能够拍摄下所有经过车辆包括车牌号码、车型等信息的图像。但图像形成时由于车辆大多数处于运动的状态而产生了模糊的现象, 这就是运动模糊。图像模糊给识别车辆信息造成了麻烦, 所以我们要利用一些方法对图像进行恢复, 以获取需要的信息。
在图像的拍摄形成、存储、传输和输出显示过程中, 受到噪声或相对运动的影响, 会发生不同程度的变质、失真和退化。根据模糊图像提供的信息, 运用某些先验知识, 建立数学模型, 从而将退化图像以最大的保真度恢复原来的图像, 便是图像恢复的目标和任务[1]。
目前已经有许多运动模糊图像复原的算法, 如维纳滤波法、L-R算法, 但这些算法都要求有足够的退化知识, 知道点扩散函数才能对模糊图像进行恢复。对于实际拍摄所得的模糊图像, 在恢复之前就必须先求出相应的点扩散函数PSF (Point Spread Function) [2], 才能用上述的恢复算法进行图像复原。
匀速直线运动模糊图像的点扩散函数由模糊运动的方向与运动长度来确定, 所以求出图像运动的方向以及运动了多长的距离是恢复过程中重要的步骤。
一些学者[3]提出了应用倒频谱分析法估算PSF参数的方法, 但这种方法在模糊长度范围为5至55像素时估算误差较小, 当模糊长度超过这个范围时, 误差值会急剧增加。有研究人员[4]提出对模糊图像进行两次傅立叶变换, 对处理后的图像利用灰度统计方法检测倾斜角以判断运动方向的方法, 但没有给出实现的具体算法。而且在文献给出的两次傅立叶变换后的图像中, 所提及的这种计算方法核心的部分—亮线并不明显, 给图像灰度统计带来不少难度。
本文提出一种结合计算机图形学中Bresenham算法对图像的频谱图进行灰度求和进而确定运动模糊方向的算法。
1 运动模糊的原理及分析
数字图像在计算机上是以位图的形式存在的, 位图是一个矩形点阵, 矩形点阵中每个元素称为像素, 它是数字图像中的基本单位。一幅M×N大小的图像, 是由M×N个明暗不等的像素组成。在数字图像中各个象素的明暗程度是由灰度值来表示的。若将白色的灰度值定义为255, 黑色的灰度值定义为0, 则由黑到白的明暗度可以均匀地划分为256个等级, 每个等级表示一种唯一的灰度。
图像的运动模糊是在成像设备快门开启至关闭这一曝光过程中被摄物和成像系统相对运动造成的。我们以匀速直线运动模糊为例来进行讨论。因为匀速直线运动模糊图像具有一般性和代表性, 变速的、非直线的运动在成像瞬间可以视为匀速直线运动。
所以从物理现象上看, 运动模糊图像实际上就是同一景物图像经过一系列距离延迟后再叠加, 最终形成的图像。而我们所处理的数字图像由若干个像素来构成, 所以图像运动实际上是组成这幅图像的所有像素进行移动。
一幅图像可以定义为一个二维函数f (x, y) , 其中x和y是空间坐标, 而f在任意一对 (x, y) 处的幅度称为该点处图像的灰度或亮度。在线性平移空间不变运动模糊系统中, 用f (x, y) 表示输入的原始图像, g (x, y) 表示输出的模糊图像, 则两者的关系可以用下面的方程来表示:
其中h (x, y) 为退化函数的空间表示, n (x, y) 表示加性噪声。为了将问题简化, 暂时不考虑噪音的影响, 则 (1) 方程简化为:
由于空间域的卷积等同于频域的乘积, 所以 (2) 中各项经过傅立叶变换后, 可以用等价的频域表示来表达:
假设在成像设备的快门开启到关闭这段曝光时间T内图像运动距离为L, 则:
观察式中的这是一个形式类似于sin (x) /x的函数, 也就是sinc (x) 。由于当x=nπ (n=1, 2, 3……) 时, sinc (x) =0。所以对于sinc (π× (u×cosθ+v×sinθ) ×L) 而言, 当u和v取适当的值, 就会使得sinc (π× (u×cosθ+v×sinθ) ×L) 等于0, 函数H (u, v) 就会出现零点。据此我们可以推测H (u, v) 的频谱有一系列的平行暗条纹, 这些暗条纹的位置与sinc (π× (u×cosθ+v×sinθ) ×L) 的零点存在对应关系。
由于有×, 则有:
若H (u, v) 在某一对确定的 (u, v) 处值为零, 那G (u, v) 在对应于该组 (u, v) 处也为零。也就是说G (u, v) 和H (u, v) 有相同的零点, G (u, v) 的频谱也会有一系列与sinc (π× (u×cosθ+v×sinθ) ×L) 的零点对应的暗条纹。
但是模糊图像经傅立叶变换后的频谱图并没有什么直观的规律可循, 这是由于傅立叶频谱的范围为[0, 106], 甚至更高。当频谱显示在线性缩放至8比特的监视器上时, 高值部分占优, 导致频谱中低亮度值的可视细节丢失。于是进一步对频谱作对数变换, 将其动态范围大幅度降低, 使可视细节增加, 方便观察。
模糊图像经过对数变换后, 可以清楚地看到其傅氏频谱图中条纹的存在, 但条纹的走向规律还不是十分一目了然, 仍旧不便于观察研究。所以为了简化频谱的视觉分析, 将原点的变换值由图像左上角的位置移动到频率矩形的中心位置。
这样条纹的走向更加清晰并且有规律可循了。将不同模糊方向的频谱进行比较分析, 发现频谱图中条纹的方向与模糊图像的运动方向总是垂直的。只要能判断出条纹方向的角度, 就可以计算出运动的角度。频谱图中条纹有着对称性, 过图像中心的条纹宽度最大, 其它条纹均匀对称分布在其两边。但如此多的条纹不便于确定角度, 根据傅立叶变换的互异性[5], 再对经过位移处理后的频谱图做傅立叶变换。
沿水平方向成30度角运动的模糊图像频谱图经过对数变换、位移处理、二次傅立叶变换的频谱图如图1所示。
从图1 (c) 中可以观察到在图像的运动方向上, 其对应的频谱有一条明显的亮线, 检测这条亮线与水平方向的夹角便可以直接得出运动的方向了。若要对图4中的亮线测试角度, 可以采取灰度求和的方法。以图像中心作为直线其中一个端点, 在与水平方向0°至180°范围内计算每个角度对应直线的灰度值, 哪个角度对应的直线灰度值最大, 该直线必定就是那条亮线, 角度便可以确定了。
2 Bresenham直线生成算法
要计算某条直线的灰度, 实际上是求那条直线上所有点的灰度和。要快速确定哪些像素点落在同一条直线上, 可以使用计算机图形学中的Bresenham算法[6,7]。此算法因由J.E.Bresenham提出而得名。因为在图形显示设备上显示直线, 要由计算机计算出直线上要显示的各点坐标并逐个显示这些点。但由于显示设备所采用的设备坐标系是整数坐标系, 直线上的各点, 其坐标却未必正好位于设备坐标系的整数位置上, 这就需要选择距该直线最近的像素点逼近显示该直线。
所谓“两点确定一条直线”, 要在显示设备上生成一条直线, 首先必须知道直线的两个端点A (xa, ya) 和B (xb, yb) , 设xB≠xA, yB≠yA。接着便要确定AB之间直线上各个点的坐标。用Bresenham算法确定直线AB上的各点相应坐标, 即把直线AB上的点在图形显示器上画出来的步骤如下:
1) 计算点A与点B之间的坐标差值, 有Δx=xB-xA, Δy=yB-yA;记录Δx、Δy的正负, 如果Δx>0, 则sx=1, 如果Δx<0, 则sx=-1;如果Δy>0, 则sy=1, 如果Δy<0, 则sy=-1;
2) 对Δx, Δy分别取绝对值, 得Δx’=|Δx|, Δy’=|Δy|, 比较Δx’与Δy’的大小, 如果Δx’>=Δy’则执行步骤3) , 否则执行步骤4) ;
3) 计算偏差判别式的初始值d=2×Δy’-Δx’, 确定直线其中一个端点A为当前处理的点, 令x=x A, y=y A, 重复以下步骤, 直至循环次数i>Δx’;
(1) 根据x, y的值画出当前点;
(2) 分别计算更新x、y和d的值, 如果d>=0, 那么x=x+s x, y=y+s y, d=d-2× (Δx’-Δy’) , 否则x=x+sx, d=d+2×Δy’, y的值不变;
(3) 循环次数i递增。
4) 计算偏差判别式的初始值d=2×Δx’-Δy’, 确定直线其中一个端点A为当前处理的点, 令x=x A, y=y A, 重复以下步骤, 直至循环次数i>Δy’;
(1) 根据x, y的值画出当前点;
(2) 分别计算更新x、y和d的值, 如果d>=0, 那么x=x+sx, y=y+sy, d=d-2× (Δy’-Δx’) , 否则y=y+sy, d=d+2×Δx’, x的值不变;
(3) 循环次数i递增;
Bresenham直线算法是一个递推算法, 根据当前已知点的坐标推算出下一个点的坐标。在每一步的推算中, 都不需要对点坐标x、y的值进行浮点数和四舍五入运算, 算法程序运行速度快, 利于在硬件上实现。
3 算法的实现
可以总结出确定模糊运动方向的算法步骤:
1) 对模糊图像做傅立叶变换, 将原点的变换值移动到频率矩形的中心;
2) 频谱图做对数变换;
3) 对频谱图再次做傅立叶变换;
4) 计算频谱图中亮线与水平方向的夹角度数。
若要计算图1 (c) 中的亮线倾斜角度, 可以图像中心作为直线其中一个端点, 同时也作为图像坐标平面的原点, 在与水平方向0°至180°范围内计算每个角度对应直线的灰度值, 要计算某条直线的灰度值, 实际上是求那条直线上所有点的灰度值之和。具体计算时可以以1°为单位递增逐个角度检验。若对角度精度要求比较高, 可以在确定了大概的角度后, 再以0.1°为单位递增角度值做更精确检测。将每一个角度的正切值计算出来后便可得到对应直线的斜率, 有了斜率利用Bresenham算法可以快速确定某一角度值对应的那条直线上的像素点, 哪个角度对应的直线灰度值最大, 该直线必定就是那条亮线, 该直线对应角度即为运动模糊方向。
当模糊运动方向为120°时, 用本文提出的算法检测频谱图所得的数据如图2所示。
在Matlab 6.5的实验环境下, 先对标准图像库中的图像cameraman.tif用imfi lter函数处理, 生成不同运动方向的模糊图像, 然后用结合Bresenham算法的角度估算方法分别判断各模糊图像的运动角度, 实验结果如表1所示:
实验证明, 本文提出的运动模糊角度判别方法比较准确地判断出了图像运动的方向, 误差不超过1°。
4 结束语
本文提出了一种结合计算机图形学中Bresenham算法对图像的频谱图进行灰度求和进而确定运动模糊方向的算法。Bresenham直线算法用于快速生成一条直线, 将Bresenham算法应用于判断图像运动方向的方法目的在于快速计算出某一条直线灰度值的和。
经过实验验证, 本文提出的运动模糊角度判别方法比较准确地判断出了图像运动的方向。但这个算法能够判断的运动方向只是局限在0°至180°的范围内, 也就是无法区分运动模糊的真实方向是θ=θ’还是θ=θ’+180°。若当运动模糊的真实方向是θ=θ’+180°, 而采用θ=θ’作为参数进行图像恢复, 所恢复的图像幅值不变, 只是各像素位移发生变化[8]。
将本文提出算法的判断估算范围从0°至180°扩大到0°至360°是今后研究的方向。
摘要：图像复原是一个以改善图像质量为目的, 利用退化现象的某种先验知识尝试重建或恢复退化图像的学科领域。运动模糊图像的恢复就属于图像复原这个领域。在恢复模糊图像时, 很多时候都是不知道退化模型或者退化信息的, 这让恢复过程难以实现或得到的恢复效果不理想。对于模糊运动方向未知的匀速直线运动模糊图像, 本文提出一种结合计算机图形学中Bresenham直线生成算法的运动角度估计方法。实验结果表明, 这种方法判别模糊运动角度简单可行, 判断比较准确, 速度较快。
关键词：运动模糊,模糊角度判别,Bresenham算法
参考文献
[1]潘琪.运动模糊仿真图像的正确生成[D].广州:暨南大学.2005.
[2]洪汉玉, 陈以超.复杂背景运动模糊图像的盲复原算法研究[J].计算机与数字工程, 2006, 34 (12) :7-11.
[3]谢伟, 秦前清.基于倒频谱的运动模糊图像PSF参数估计[J].武汉大学学报 (信息科学版) , 2008, 33 (2) :128-131.
[4]刘微.运动模糊图像恢复算法的研究与实现[D].北京:中国科学院.2006.
[5]罗纳德.N.布雷斯韦尔著.殷勤业, 张建国译.傅立叶变换及其应用[M]西安:西安交通大学出版社, 2005:24-26.
[6]魏海涛.计算机图形学 (第2版) [M].北京:电子工业出版社, 2007:2-8.
[7]金延赞.计算机图形学[M].浙江:浙江大学出版社, 2003:134-140.
Bresenham 篇4
直线光栅化是计算机图形学中的基本操作,许多复杂图形的边缘均可以由有限数目的直线来近似,直线光栅化的速度在一定意义上决定了显示芯片系统的性能。
Bresenham画线法采用增量技术,只需计算加法和整数操作,运算速度快,易于硬件实现。
本文介绍的简单直线绘制硬件加速引擎采用Bresenham画线法,并将二维平面八等分后,将任意方向的直线光栅化操作,统一为简单的实现过程。该实现简化了硬件实现结构,提高了硬件加速性能。
1 Bresenham算法
为叙述清楚,规定:如果直线斜率绝对值大于1则称该直线位于Xb象限,否则位于Xa象限(X指根据x,y正负所划分的4个象限)。二维平面划分,如错误,未找到引用源。
Bresenham算法流程(以1a象限内起点(x1,y1),终点(x2,y2)直线为例):
(1)画点(x1,y1),dx=x2-x1,dy=y2-y1,误差初值p1=2dy-dx,i=1。
(2)xi+1=xi+1,if(pi>0)yi+1=yi+1;esle yi+1=yi。
(3)画点(xi+1,yi+1)。
(4)if(pi>0)pi+1=pi+2dy-dx;elsepi+1=pi+2dy。
(5)i=i+1。
(6)if(i<dx+1)转2else toend。
可以看到Bresenham算法不计算斜率,只用整数,只做加减法。
2 加速引擎框图
直线光栅化加速引擎的工作机理简述如下:首先,直线预处理模块根据对称性,将任意直线映射到1a象限内的参考直线;其次,直线光栅化模块按照Bresenham算法对参考直线进行绘制;最后,直线后处理模块根据对称性,将参考直线映射为原始直线。
图2为ISE8.1 XST综合出的加速引擎框图,表1为接口信息。左上模块为直线预处理模块;右上模块为直线后处理模块;左下模块为直线光栅化模块;右下模块为完成信号生成模块。
2.1 直线预处理模块
该模块将平面各方向原始直线经过平移、对称操作转换为1a象限参考直线。对应关系总结如表2所示:
原始直线转换为参考直线的Verilog代码(仅以第三象限为例说明):
AREA3a:
begin
rxend <= XBEG-XEND;
ryend <= YBEG-YEND;
end
AREA3b:
begin
rxend <= YBEG-YEND;
ryend <= XBEG-XEND;
end
其中XBEG,YBEG,XEND,YEND分别是原始直线的起点、终点坐标;rxend,yend是对应的参考直线的终点坐标,起点坐标固定为原点。
2.2 直线光栅化模块
该模块对1a象限参考直线进行光栅化操作。其状态数据通道图如图3(矩形框表示状态,圆角矩形表示数据通道所作操作)所示。start为操作开始信号,高有效;p为误差值,其正负来决定下一个点的位置;x,y为当前像素点的坐标;当光栅化过程完成后,使用ready信号,进入idle状态,等待下一次操作开始。
2.3 直线后处理模块
该模块根据原始直线所在象限将直线绘制模块输出的参考直线的点转换为原始直线的对应点。这样参考直线绘制完成后,原始直线也在同一时间绘制完成。其转换总结如表3所示。
2.4 完成信号生成模块
上述三个模块操作完成后各有一个完成信号输出。该模块根据三个完成信号产生整体模块的完成信号输出。
3 实验结果
该硬件加速引擎经过Synplicity Verilog Compiler, version 3.1.0综合后得出如下时序和资源报告。如表4,表5所示。
为验证该引擎工作在100MHz下没有时序错误及输出信号正确。本文在modelsim下进行后仿真得出如图4波形(以绘制起点(1,1)终点(4,4)直线为例)。可以看到复位后ready有效,当接收到start信号后一个周期ready无效,表明该引擎处于忙状态;当最后一个点绘制完成后一个周期,ready信号有效,表明该引擎处于空闲状态,可进行新的绘制操作。其中en信号为当前输出数据有效信号,高电平时候表示输出数据有效。
为测试硬件加速引擎的正确性,给定给定八个方向(代表任意方向)直线进行绘制。将绘制的直线输出输出到.ppm格式的图形文件中。绘制结果如图5所示。可以看到该引擎可正确绘制给定的任意方向的直线。
4 结束语
直线光栅化的速度对显示加速芯片的性能有很大影响,如何快速绘制直线是设计显示芯片时重要的考虑因素。本文基于Bresenham算法,通过将二维平面八等分,任意直线的光栅化过程统一到一个特定区域。该加速引擎硬件结构简单,光栅化速度可以达到100MHz以上,配置灵活且耗费资源少。
摘要：直线光栅化在图形绘制过程中占有很大比例,直线光栅化的速度也在很大程度上影响着显示芯片的加速性能。文中基于Bresenham算法,实现了单像素直线的光栅化。将二维平面八等分后,任意直线的光栅化根据对称性映射到一个固定区域进行,简化了硬件结构,提高了加速性能。基于FPGA平台(Xilinx的Virtex2pXC2VP30),该光栅化系统稳定运行在100MHz。
关键词：Bresenham,FPGA,对称性,直线光栅化
参考文献
[1]BresenhamJ E.Alinear algorithmfor incremental digital display of circular arcs[J].Communications of ACM,1977,20(2):100-106.
[2]Donald Hearn,MPauline Baker.Computer Graphics[M].C Version,2nd Ed.NewYork:Prentice Hall,1997:84-94.
【Bresenham】推荐阅读：