直线生成算法

直线生成算法（精选6篇）

直线生成算法 篇1

0 引 言

直线是生成各种图形的基本元素,直线生成算法是其它各类图形算法的基础,因此直线的生成算法已得到了人们的广泛研究,并已出现许多有效的算法,其中最著名的是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算法:

$\{\begin{array}{l}d{}_1=d{}_0+2dy①\\ d{}_m=d{}_1+2(m-1)dy-2dx②\\ d{}_i=d{}_m+2dy③\end{array}$

且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,即

$\{\begin{array}{l}d{}_0+(n-2)2dy\le 0\\ d{}_0+(n-1)2dy>0\end{array}$

式中d0=2dy-dx为d的初值,即直线第二个像素点对应的d值,则

$\{\begin{array}{l}2dy-dx+(n-2)2dy\le 0\\ 2dy-dx+(n-1)2dy>0\end{array}$

可得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.

[10]韩玫瑰.基于并行填充模式的直线生成算法[J].济南大学学报:自然科学版,2004,18(3):212-214.

直线生成算法 篇2

关键词：计算机图形学,Bresenham算法,直线生成算法

1 概述

直线是生成各种图形的基本元素, 直线生成算法是其它各类图形算法的基础。目前对于直线的生成算法已得到了深入研究, 并已出现许多有效的算法, 其中最著名的是Bresenham算法。在分析了传统的Bresenham算法的基本思想和优点之后, 探讨了该算法本身的缺陷, 并在考虑直线本身特性的基础上提出了一种新的直线算法。

由于直线具有关于y=x的对称性。k大于1时直线的像素点坐标可以通过k小于1的直线坐标推出。遇到k小于零的情况, 也可以利用直线的对称性解决, 所以本文中后续的讨论只涉及k小于1且大于零的情况。

2 经典的Bresenham算法

在计算机屏幕上绘制直线时, 直线上的点的坐标并不总是恰好位于像素点, 所以其实是利用靠近理想点的像素点来近似地表示图像。当直线上某个点的理想坐标位于两个像素点之间时, 只能用靠近该点的那个像素点来近似地表示。所以各种直线绘制算法的核心是, 如何有效地选择直线两侧的像素点作为近似点。

Bresenham算法速度很快, 并适于用硬件实现.。该算法主要思想是:按直线从起点到终点的顺序计算直线与各垂直网格线的交点与网格线之间的距离d, 借助于一个由d得到的决策变量Dk, 来判断网格中哪个像素点距离交点最近, 从而确定下一个该点亮的像素点。以某线段为例 (如图1) , 设其左端坐标值为 (x1, y1) , 右端坐标值为 (x2, y2) , 则斜率k= (y2-y1) / (x2-x1) , 直线方程为y=kx+b。

根据图1所示, 可以列出如下的方程:

d1= (yk+1) -y=yk+1- (k (xk+1) +b)

d2=y-yk= (k (xk+1) +b) -yk

d1-d2=2yk-2k (xk+1) -2b+1

将k= (y2-y1) / (x2-x1) 表示为k=△y/△x, 代入上式, 可以整理得到:△x (d1-d2) =2△x·yk-2△y·xk+c

令Dk=△x (d1-d2) , 把dk作为第K步 (第K个点) 的决策参数。因为△x>0, 所以可以通过dk判断出d1和d2的大小, 从而确定究竟该取 (xk+1, yk) , 还是 (xk+1, yk+1) 。

显然, 当Dk>0时, d1>d2, 应取像素 (xk+1, yk) , 即右方像素。反之, 应当取 (xk+1, yk+1) , 即右上方像素。当Dk=0时, 可以约定取 (xk+1, yk+1) 。

Dk+1=2△x·yk+1-2△y·xk+1+c

则Dk+1-Dk=2△x· (yk+1-yk) -2△y· (xk+1-xk)

因为xk+1=xk+1, 所以得到:

Dk+1=Dk+2△x· (yk+1-yk) -2△y

如果取的是右方像素 (Dk>0) , 则:

Dk+1=Dk-2△y

如果的是右上方像素 (Dk≤0) , 则:

Dk+1=Dk+2△x-2△y

采用以上这两个递归式, 可以从线段的坐标端点开始, 循环地进行决策参数的计算, 判断出所有要点亮的像素坐标。

由以上分析结果可以看出, 使用Bresenham算法时不必计算直线的斜率, 因此不做除法;不涉及浮点运算, 只用整数;只做整数加减法和乘2运算, 而乘2运算可以用硬件移位实现;采用递归计算, 效率较高。

3 改进的Bresenham算法

尽管上述这种算法已经能够很快地生成直线, 但是还可以进一步地改进。虽然只用计算简单的加减和乘法, 但是毕竟每个点都需要计算一个决策变量才能够确定, 而事实上, 在直线的两个端点确定之后, 斜率就确定了, 同时像素点之间的距离是均匀的, 所以像素点的选择其实是遵循一定的规律的。如图2所示, 除首位点之外, 线段的中部的像素点的排列有这样一种规律:在x轴方向上每前进三步, 就会在y轴方向前进一步。这里x轴上的三步就可以看成是像素位置变化的步长。所以对于首末点的特殊情况进行单独处理后, 线段中部的生成就无需对每个点进行Dk的计算, 而是可以直接按照步长来推算出应该点亮的像素点。这样一来, 可以省去大量的计算。进一步提高直线生成效率。

为了便于描述, 我们在这里做出如下定义:

定义1:当线段在x轴方向延伸较长 (k小于1) 时, 称x轴为主轴, 称y轴为副轴, 反之亦然。

定义2:在副轴方向前进一个坐标单位, 在主轴方向前进的坐标单位数 (线段的两个端点除外) 称为步长, 记作h。在0

但是如果计算出的步长并不总是整数, 这样的情况下就不能按照以上所说的方法简单地判断了。例如图3所示的一条k=3/4的直线, 其步长为4/3, 约等于1.3, 取点的变化情况与图2相比要复杂, 不能采用上述的方法总结其变化规律。但是随着直线的延伸, 像素点与理想点间距离的变化仍然是呈现周期性的。从起点开始, 主轴方向每前进四个网格便构成一个变化周期。

重新观察图2中的直线, 从起点开始, x轴方向每前进3步就构成一个周期。所以我们这里可以定义一个更具一般性的算法, 即以Bresenham算法为基础, 利用直线上理想点与像素点间误差值的周期性变化生成直线的算法。

定义:直线的斜率总可以表示成k=N/M (0

如图3所示, 该直线的变化步长为4, 每个步长之内都包括5个点, 第一个步长之内的第一个点是起点, 直接确定而不必多做处理。接着从第二个点开始应用经典的Bresenham算法, 连续计算出4个点的决策变量Dk, 但计算过程中需要给每个点添加一个标记 (可用0, 1作为标记的值。) , 表明该点相对于前一点来说是右方像素点, 还是右上方像素点, 以作为后续周期中取值的依据。从第二周期T1开始, 就可以反复利用记录好的这四个标记来确定像素点的位置 (五个点中的第一个点为前一周期的最后一个点, 仍可看作是起点) , 直到线段终点。

因此, 对于步长是M的直线, 在起点确定好之后, 就可以利用Bresenham算法思想计算后续M个点的坐标和标记, 此后, 在到达终点之前, 就可以只用标记值来判断下一点的坐标了。

4 结论

改进后的算法节省了大量的加减和乘法运算, 具体分析如下:设某直线的长度约为n·M (nεZ+) , 采用传统的Bresenham算法时, 必须要计算n·M次Dk+1=Dk-2△y (Dk>0) 或Dk+1=Dk+2△x-2△y (Dk≤0) , 如果采用本文提出的改进的Bresenham算法, 只需要计算M次Dk+1。所节省的乘法运算次数在 (n-1) M到2 (n-1) M之间, 节省的加法次数在0到 (n-1) M之间, 节省的减法次数在 (n-1) M到2 (n-1) M之间。

显然, 直线越长, 所节省的计算量就越大, 算法的优越性也就越能体现出来。

参考文献

[1]孙岩, 唐棣.并行的Bresenham直线生成算法[J].计算机工程与应用, 2002, 21.

[2]郑宏珍等.改进的Bresenham直线生成算法[J].中国图象图形学报, 1999, 7.

[3]苗兰芳等.自适应多步位移码直线绘制算法[J].软件学报, 2002.Vol.13 (4) .

[4]袁超.直线Bresenham生成改进算法研究[J].四川理工学院学报 (自然科学版) , 2006, 4.

直线拟合椭圆误差控制算法 篇3

对于没有非圆曲线插补功能的机床而言, 加工椭圆等非圆曲线时, 较多采用宏程序编程, 用直线拟合时, 常采用等间距法和等弦长法, 但不易控制轮廓精度。若用等误差法编程, 一般算法是:在已知节点建立允差圆, 根据允差圆与曲线关系, 求出拟合直线斜率, 再求出拟合直线与曲线交点。这种算法复杂, 且有不易求解的缺点。本文提出了一种新算法, 原理简单, 适合用宏程序编程。

2 原理及计算方法

如图1, 直线L1拟合椭圆时, 起点 (X1, Y1) , 另一交点 (X2, Y2) , 误差即是椭圆上某点到直线的最大距离。设拟合误差控制在一个定值D内, 做拟合直线的平行线L2, 两直线距离为D, 若直线L2与椭圆相切或相离, 则拟合误差未超差, 若直线L2与椭圆相交, 则拟合误差大于D。

设椭圆方程为:x2/a2+y2/b2=1, 直线方程为y=Kx+C

直线L1方程:y=Kx+C1, 直线L2方程:y=Kx+C2

(上半部椭圆用“+”号, 下半部椭圆中间用“-”号) 将已知点 (x1, y1) 代入直线L1方程得:C1=y1-Kx1

此方程只有两个解时:直线L2与椭圆相交;此方程只有一个解时:直线L2与椭圆相切;此方程没有解时:直线L2与椭圆相离。

要使椭圆上的点到拟合直线最大距离小于等于拟合允许最大误差D, 则只允许直线L2与椭圆相切或相离。

据韦达定理:方程Ax2+Bx+C=0

要使其只有一个解或无解则:B2-4AC≤0

编程时可以根据条件判断拟合误差是否超出给定最大误差D, 满足条件则未超差, 否则超差。

3 编程实例

(1) 用常规等间距法编程的精加工程序

此程序没有考虑拟合误差大小, 加工精度无法保证。

(2) 若编程时考虑拟合误差, 并使用本文算法, 假设取最大拟合误差为D=0.005的精加工程序

4 结 语

利用这种算法, 每走一段直线都会判断拟合误差大小, 当拟合误差符合要求时才进行拟合, Z坐标间距初始值一定 (例题为0.4) , 当不满足精度要求时, 则间距会变化, 每次变化0.05 (第一次0.4, 第二次0.35, 以此类推) , 直至求出最合适间距。本编程方法克服了等间距直线拟合精度不能保证的缺点, 原理简单, 适合宏程序编程。

摘要：主要介绍对于有轮廓度要求的椭圆, 数控编程时要如何控制拟合误差, 文中提出了一种纯代数算法——直线拟合椭圆时误差控制算法, 适合在宏程序中自动算出节点, 并可控制拟合误差在一定值内。

关键词：宏程序,直线拟合,韦达定理

参考文献

一种改进的直线检测算法 篇4

直线段、曲线段和角点是组成物体的最基本的几何特征, 它们是对目标物体进行高层研究的基础, 从图像中准确识别这些特征是计算机视觉领域的重要研究内容之一, 对智能交通、数字地图的更新和城市交通状况监测具有重要意义[1,2,3]。

经典的直线检测算法由霍夫变换 (Hough Transform) 来实现。Hough变换是由Paul Hough提出的, 其最初是用来检测图像中的直线的一种方法[4]。由于Hough变换是通过在两个笛卡尔坐标系之间的变换来进行直线检测的, 所以当直线的斜率趋向于无穷大时, 用该方法来检测直线就带来了一定的困难。

基于相位编组检测直线是另一种检测直线的方法, 相位编组是由Brian Burn J[5]在1986年提出的, 由P.Kahn做了全面的改进。该算法涉及到两个概念, 即边缘支持区和梯度相位。边缘支持区是由梯度方向相同的相邻像素点组成。在像素的邻域范围内, 其灰度变化最大的方向即为梯度相位。相位编组检测直线的原理即是基于梯度方向一致性。该算法将提取直线简化为链接和分组两个过程, 同时该方法还可以计算出直线的宽度、长度等。Hough变换实质上也涉及到了边缘的相位问题, 但是在Hough中, 只有幅值大的边缘才能被检测出来, 而相位编组算法则在提取直线的过程中不受对比度、局部宽度等的影响。

基于主成分分析 (Principal components analysis, PCA) 或基于协方差矩阵最小特征根检测直线的方法是近几年提出的一种新的检测直线的方法。该方法利用了直线的连续性, 它以边界上的一点和包含该点的一段连续边界为对象来研究, 首先构造协方差矩阵, 并计算最小特征根, 如果其最小特征根小于预先设定的阈值, 则表示此段边界为直线[6]。2004年, Guru提出了基于最小特征根检测直线的方法[7], 该方法由于计算简单、高效, 因此得到了广泛的应用。但是由于此方法在检测过程中, 使用传统的局部窗口进行检测, 因此会出现将平滑曲线误判为直线的问题, 且对噪声也较敏感。2006年, Yun-Seok Lee等人对该方法进行了改进[8], 该方法通过将边缘图像的像素点分为行像素图和列像素图, 从而避免了局部窗口产生噪声的影响, 且在时间上也有了大大的提高, 但是当两直线相交形成的角度比较大时, 用此方法就会出现严重的漏检情况, 且还会把部分光滑曲线检测为直线。引入链码算法可以较好的解决此问题, 但是由于链码算法易受噪声的影响, 且加入链码后, 检测直线所有的时间较长。

从目前的研究现状来看, 现有的上述算法对直线的检测存在困难, 据此, 本文提出了一种直线检测改进算法, 对边缘检测的图像进行线段拆分, 基于协方差矩阵特征根初步检测出直线、圆、曲线, 并基于各个像素点的方向变化而将初步检测出的曲线进行进一步检测获得其含有的直线部分, 通过结合初步检测的直线和曲线中检测的直线部分实现直线检测。

1 算法模型

1.1 线段拆分

自然场景中的线段端点通常有两种情况: (1) 两向交点:线段与另一条曲线或直线的交点; (2) 多向交点:线段与其它两条或两条以上曲线或直线的交点。根据线与线相交的仿射不变性, 自然场景映射为数字图像后, 端点将仍然存在, 并且大部分两向交点会映射成为角点, 多向交点会映射成为交叉点。基于此, 连续边缘终点、交叉点和角点必然是最有可能构成线段端点的特征。

因此, 从线段入手, 通过对线段分解及每条线段的方向变化来对物体的特征识别进行研究, 其中包括对物体的直线段, 平滑曲线识别。为了提取准确的直线, 本文采用能够连接局部弱边缘的Canny算子对源图像进行边缘检测, 设其边缘图像为E, E中边缘具有单像素宽度, 对边缘图像E进行线段拆分, 其具体过程如下所示。

考察E (x, y) 中某边缘像素P的3×3邻域, 像素点序号如图1 (a) 所示。设x (i) , i=1, …, 9表示P的3×3邻域内的像素值 (0或1) , 定义:a=[x (1) , x (2) , x (3) , x (6) , x (9) , x (8) , x (7) , x (4) ], b =[x (2) , x (3) , x (6) , x (9) , x (8) , x (7) , x (4) , x (1) ], 如果其满足 :

则为交叉点, 如图1 (b) 所示, 对经过Canny边缘检测之后的图像E, 依据式 (1) , 对E进行交叉点检测 , 如果某边缘像素满足式 (1) 中条件, 则将该像素赋值为0。重复检测, 直到E中不存在交叉点。其具体实例如图2所示, 其中2 (a) 是源图像, 图2 (b) 是Canny边缘检测的图像, 其交叉点和端点如图2 (c) 所示, 其中十字交叉点表示线段的端点, 圆圈表示三叉交点, 其中不同的颜色代表了各个不同的拆分出来的线段。依据上述规则, 检测E中的交叉点, 如果某边缘像素满足式 (1) 中条件, 则将该像素赋值为0。重复检测, 直到E中不存在交叉点, 此时定义不含交叉点的边缘图像为Ed:

其中, mi表示组成线段Ci的像素点数, 其中, (xij, yij) 表示第i条线段上第j个像素点的坐标, Ci上每个点的值为1。其对Canny边缘检测之后的图像进行边缘拆分, 其线段拆分之后的结果如图2 (d) 所示。

1.2 基于协方差矩阵特征根的线段形状初步检测

经过边缘分解, Ed中包含若干条独立且连续的线段Ci, 其形状可能是曲线、圆或直线。根据微分几何定理, 以弧长表示C2类平面曲线Ci:r=r (s) , 则Ci在一点pj=r (s0) 的邻近结构利用泰勒公式展开后 , 结合伏雷内公式, 可得:

式 (3) 中, α, β为平面曲线基本向量, κ为曲率, ε1, ε2为微小量, Δs为局部曲线弧长, 取r (s0) 为直角坐标系原点 , 以α, β为坐标系基向量 , 在r (s0) 点邻近 , 曲线的近似方程为 :

即曲线在一点的邻近结构有三种可能:二次抛物线, 三次抛物线和直线。对于数字图像而言, 局部范围内很难区分三次抛物线和直线, 因此可忽略三次抛物线的情况, 即在数字图像中, 考虑曲线在一点的邻近结构只有二次抛物线和直线这两种可能。

对Ci={pj= (xij, yij) , j=1, …, mi}, i=1, …, n, 取pj= (xij, yij) 左右4相邻点组成局部支持集Cij={pj|i-4≤j≤i+4}。根据协方差矩阵检测直线的原理[7,8], 定义向量x1=[xi (j-4) , …, xij, …, xi (j+4) ], x2=[yi (j-4) , …, yij, …, yi (j+4) ], 如果设输入矩阵为X={x1, x2}, xi∈Rn, (i=1, 2) , 则有协方差矩阵 :

其中, 式 (5) 中:

对CX进行特征根分解, 可得p特征向量和两个特征值λ1, λ2 (λ1>λ2) :

其中, 特征向量p1代表数据X主方向, p2⊥p1, 两个特征值λ1, λ2分别代表数据X在方向p1和p2上的方差。从微分几何的观点, 可认为p1, p2是平面曲线Ci在点pj= (xij, yij) 的伏雷内标架 , p1=α, p2=β。

(1) 基于协方差矩阵最小特征根λ2检测直线

由文献[8]可知:如果由Cij={pj|i-4≤j≤i+4}定义的CX计算所得的最小特征值λ2=0, 则Cij上的点满足直线方程, 且最小特征根的值越接近于0, 表示像素点的共线性越好。因此, 当λ2为0时, 检测为直线。

(2) 基于协方差矩阵两特征根比值λ1/λ2检测圆和曲线

由文献[9]可知, 如果支持集中的边界像素点共圆, 则其两特征根满足关系式λ1=λ2。因此 , 当两特征根λ1/λ2的比值等于1时, 检测为圆。协方差矩阵的两个特征值λ1/λ2的比值大小反映了线段的弯曲程度, 比值越小, 即其值越接近1, 其弯曲越大, 等于1时表示的是圆;反之, 比值越大弯曲越小, 当λ2为0时, 比值为+∞, 表示的是直线。

1.3 曲线中直线部分的进一步检测

对于前述初步检测出的直线、圆、曲线, 其中曲线还可能含有直线部分, 对此, 可利用曲线中的方向变化检测出曲线中的直线部分, 从而细分出曲线中的直线部分, 并结合前述初步检测的直线实现直线检测。设待检测的连续边缘为Ci (1≤i≤n) , 统计曲线上各像素点的方向值dir, 得到局部直线方向直方图, 设定如果某一方向值dir出现的次数大于预设阈值Tdis, 则对这些像素点进行最小二乘直线拟合 , 求解最小化问题:

求得式 (13) 的参数ka和ba后, 再考虑Ci上其他点到拟合直线的距离误差值:

如果dis (i) <Tdis (Tdis为预设阈值) , 则认定该像素点i属于直线部分, 统计所有满足条件的像素点的坐标构成新的直线集合Ldir, 记为检测出的直线部分。

2 实验结果与分析

为了验证本文算法对直线识别的有效性, 我们选取了三类图像进行试验, 并分别将直线检测的结果与三种经典算法:Hough变换直线检测、相位编组、最小特征根算法[8]进行对比, 其中三类图像分别为人工合成图像、含有曲线的建筑物图像、含有圆的道路指标图像。

2.1 人工合成图像

图3 (a) 为源图, 图3 (b) 是Canny边缘检测的图像, 图3 (c) 是Hough变换直线检测结果, 图3 (d) 是相位编组检测结果, 图3 (e) 是最小特征根检测结果, 图3 (f) 是本文算法检测结果。对比图3 (c) - (f) 与边缘检测得到的图3 (b) 中右上角的圆、椭圆、矩形检测结果可以发现, 本文算法直线检测效果最好, 成功去除了圆和椭圆, Hough变换和相位编组检测结果均不能去除圆和椭圆, 最小特征根直线检测仅去除了椭圆的一部分。

(a) 源图; (b) Canny边缘检测图; (c) Hough变换结果; (d) 相位编组结果; (e) 最小特征根结果; (f) 本文算法结果

2.2含有曲线的建筑物图像

图4为含有曲线的建筑物图像检测结果, 通过图4 (c) - (f) 与边缘检测得到的图4 (b) 比较, 可以发现:本文算法检测效果最好, 较成功地去除了右下角草坪的大圆弧, Hough变换和相位编组均将弧当作部分直线, 最小特征根法在去除弧的效果上也没有本文算法理想。

2.3 道路指标图像

图5为道路指标图像检测结果, 通过图5 (c) - (f) 与边缘检测得到的图5 (b) 比较, 可以发现, 本文算法在检测过程中能成功的去除圆, 且对于检测出的直线, 本文算法能较好的将检测出的各个直线段断开, 方便了后续各个直线段的拟合。

3 结论

提出了一种直线检测的改进算法, 该算法包括线段拆分、初步检测和曲线的进一步直线部分细分 , 相比传统的直线检测算法 , 本算法可以在较准确检测直线的同时, 有效地去除边缘图像中的曲线和圆。

摘要：提出了一种直线检测的改进算法, 对获得的边缘检测图像进行交叉点检测并将交叉点断开, 使图像分割成若干条不交叉的线段以实现线段拆分, 基于协方差矩阵特征根初步检测出线段所属的直线、圆、曲线类型, 并对初步检测出的曲线基于各个像素点的方向变化而进一步检测其含有的直线部分, 通过结合初步检测的直线和曲线中检测的直线部分实现直线检测。实验结果表明, 相比传统的直线检测算法, 本算法引入线段拆分和曲线中进一步细分直线部分, 可以在较准确检测直线的同时, 有效地去除边缘图像中的曲线和圆。

关键词：机器视觉,直线检测,线段拆分,协方差矩阵

参考文献

[1]Li Q F, Shi J F, Li C.Fast Line Detection Method for Railroad Switch Machine Monitoring System[C]//International Conference on Image Analysis and Signal Processing, 2009:61-64.

[2]Ding Weili, Wang Wenfeng, Zhang Xuguang et al..Extracting straight lines from building image based on orientation image[J].Acta Optica Sinica, 2010, 30 (10) :2904-2910.

[3]Chen G, Li L, Ma J W, A Gradient BYY.Harmony Learning Algorithm for Straight Line Detection[J].Lecture Notes in Computer Science, 2008, 5263:618-626.

[4]Hough P V C.Method and Means for Recognizing Complex Patterns[P].US Patent, No 3069654, 1962, 2.

[5]Brian, Burns J, Hanson A R et al..Extracting Straight Lines[J].IEEE Transactions on Pattern Analysis and Machine Intelligent, 1986, 8 (4) :425-455.

[6]Kuang Ping, Zhu Qingxin, Chen Xudong.Line Detection Algorithm Based on the Smallest Eigenvalue Analysis[J].Journal of Electronic Measurement and Instrument, 2007, 21 (3) :33-38.

[7]Guru D S, Shekar B H, Nagabhushan P.A Simple and Robust Line Detection Algorithm Based on Small Eigenvalue Analysis[J].Pattern Recognition Letters, 2004, 25 (1) :1-13.

[8]Lee Y S, Koo H S, Jeong C S.A Straight Line Detection using Principal Component Analysis[J].Pattern Recognition Letters, 2006, 27 (4) :1744-1754.

直线生成算法 篇5

图像的运动模糊是曝光时间内成像系统和物体之间的相对位移引起的, 这种图像视觉质量上的退化有时会因为模糊所带来的信息缺失对后期处理带来严重的不便。但运动模糊图像在日常生活中又是普遍存在的, 如在行驶中的车上拍摄的照片, 以及运动中的航天器获取的遥感图片等, 所以如何将运动模糊图像进行恢复具有重要的意义。早在上世纪六七十年代, 运动模糊图像的恢复开始快速发展起来, 至今已经有很多较为成熟的算法被提出。为了研究的一般性, 本文以匀速直线运动模糊图像为研究对象, 将点扩散函数估计方法与Lucy-Richardson滤波相结合, 完成模糊图片恢复全过程。

若f (x, y) 为原始图像, 经过成像系统H退化之后再在噪声n (x, y) 的作用下最终产生退化图像g (x, y) 。则图像退化过程用下式表示, 一般情况下n (x, y) 为一种统计性质下的噪声信息。

对图像进行恢复的关键是建立点扩散函数H, 主要任务是要找点扩散函数的两个参数:运动模糊方向和长度。

1点扩散函数的参数估计

1.1运动方向估计

将图像进行傅里叶变换, 从空间域变换到频率域, 利用傅里叶变换后的特性, 并结合Radon变换, 可以较准确地估计出模糊图像运动方向。为了更好地观察傅里叶频谱图, 一般都将图像频谱原点移到中心。

如图1为方向45°, 长度为20PX的运动模糊图像, 图2为其中心化后的傅里叶变换频谱图。可以明显看出, 图2具有条纹特性, 且条纹具有明显的方向特性, 条纹相对原点是对称的, 且方向相同, 猜想这个方向即为运动方向。若能检测出这些条纹的方向, 就能估计出运动模糊的方向。

为验证此猜想是否成立, 利用Radon变换来检测傅里叶变换频谱图的条纹方向是否为45°。Radon变换实际上是计算图像矩阵在某一特定方向的积分。对于二值图像而言, 如果在某个方向上的积分 (即点个数) 很大, 那么说明在该方向上有着较强的线性, 可以认为存在线段。对于运动模糊图像的傅里叶变换频谱图, 可以利用Radon变换的特性来检查其条纹方向, 只需将图像进行一组连续角度 (一般0°～180°) 的Radon变换, 找出幅值最大的变换角度, 即为条纹方向。

将图2进行0°～180°的Radon变换, 估计出的条纹方向为46°, 与真实值45°只有1°的误差, 可见此方法有着一定的精确性, 且由于此方法的计算量小, 所以具有实际参考价值。为了验证此方法的精确性, 做了多次模拟实验, 实验中每次的模糊长度L是20个PX, 实验结果如表1, 绝对误差最多不超过4°, 可见此方法是较精确的。

1.2运动长度估计

微分自相关方法就是在上面将图像水平旋转的基础上进行的, 将二维问题降次为一维, 证明见参考文献[2]。先将图像进行微分运算 (水平) , 再计算自相关图像, 最后将各列相加, 得到一条鉴别曲线, 在这条鉴别曲线上会出现一对共轭低峰 (图像方向向下的极小值点) 。理论证明, 这对低峰之间的距离就是运动模糊长度像素值的两倍。

同样, 以前面的cameraman图像为例, 将水平移动20个像素点的运动模糊图像进行上述步骤的处理, 得到的鉴别曲线如图3。从图中可以明显看到其共轭的一对低峰, 将中间部分进行放大, 由共轭低峰点的坐标值, 可以得出此运动模糊图像的尺度为 (277-237) /2=20, 即运动长度为20个像素点, 估计的长度与实际情况是一样的。

至此, 将以上所提的两种估计方法结合起来, 点扩散函数参数都得到了估计, 在此基础上就可以恢复对具体模糊图像的实验了。

2实际处理技巧

上文中的模糊图像是用Matlab模拟出的, 而实际上, 从现实生活获取照片的过程中, 成像系统的成像空间是固定的, 较之于真实图像所得到的模糊图像会有边缘截断, 边界的卷积关系被破坏, 将不再是一个完全卷积的关系, 傅里叶变换后中心会出现十字条纹的亮线, 如图4, 这会影响到用Radon变换检测直线方向。在实际的应用中, 可以对傅里叶变换图像进行截取, 避开中间的十字条纹, 观察傅里叶变换图, 根据实际情况, 选择方向条纹较明显的部分。

本例中选择左上角部分, 截取部分图像后再进行Radon变换, 最后确定运动方向。为了增加精度, 采用二值化处理 (阈值设为0.5) , 进行Radon变换后, 中间的十字条纹被明显避开了, 此图的运动模糊方向为50°, 见图5。

3实验过程及结果

基于上面所述的点扩散函数参数估计方法, 本文采用Lucy-Richardson滤波进行图像恢复。Lucy-Richardson是一种迭代的方法, 目前应用较为广泛。该方法按照泊松统计的标准输出与给定点扩散函数卷积之后最大概率成为输入模糊图像的图像。

在此继续以cameraman图像作为实验的对象。用Matlab模拟的运动方向为52°, 长度为25PX的运动模糊图像图6进行恢复操作。利用上面点扩散函数参数估计方法估计出模糊方向53°, 误差为1°。对模糊尺度的鉴别, 根据之前所提及的方法, 将模糊图像进行53°的旋转, 再估计出运动模糊的长度为 (197-147) /2=25, 即25个像素点。最后用Lucy-Richardson滤波进行图像恢复, 图7为迭代50次后的恢复图像。

上面讨论的都是用Matlab模拟出来的运动模糊图像的恢复, 接下来将对现实中的模糊图像做恢复实验, 考察实际价值。现实中所拍摄的照片都为彩色的图像, 所需存储空间较大, 为了提高运算的速度将原图灰度变换后进行恢复实验。图8为灰度图像, 图9为按上述方法进行图像恢复之后的图 (迭代到80次) , 图像已经比较清晰了, 文字、图片等都能得到清晰的辨识, 恢复效果较好。

4结语

直线生成算法 篇6

直线特征是图像中物体的基本形状特征之一, 大部分人造目标如房屋, 公路, 桥梁, 机场都具有明显的直线特征。在图像分析与理解过程中, 直线特征是一种常用的中层符号, 可以简洁高效地对目标形状进行描述, 有利于高层次的图像处理。由于直线在图像分析中的重要地位, 其提取算法也是人们研究的重点, 目前主要的直线提取算法可以分为两类。第一类是先通过边缘检测, 阈值分割等方法提取边缘, 再对边缘进行直线拟合。代表算法是Hough变换法, 其原理是将图像平面中的点按照待求曲线的函数关系映射到参数空间, 然后找到最大聚集点, 完成从直线到点的变换。第二类直线提取方法是直接进行直线区域搜索, 寻找直线支持区, 然后对直线支持区进行直线拟合, 代表算法是相位编组法。利用图像灰度的相位信息, 将相邻方向相同的点编为一个直线支持区, 然后对直线支持区进行灰度平面拟合, 使灰度平面与相应的平均灰度平面相交, 其交线即为所求直线。

本文提出的基于Harris算法的直线提取方法是上述两类直线提取方法的相结合的方法, 通过对边缘进行直线搜索, 根据Harris原理进行判断, 筛选直线上的点。

2 算法描述

2.1 图像预处理

在实际卫星图像中, 通常会包括其他很多干扰物体, 如建筑、湖泊等等, 在对机场类直线目标进行提取之前, 对图像进行分割, 滤波等预处理手段, 可以有效提高系统的运算效率, 减少干扰, 提高目标识别度。本文才用Harris角点检测原理进行直线提取, 针对图像边缘进行直线检测, 能提高检测精度, 同时提升检测速度。

本文算法的图像预处理包括对原始图像采用多重迭代法进行图像分割, 利用LOG算子对图像进行边缘检测。

2.2 Harris角点检测原理

Harris角点检测方法是由C.Harris和M.Stephens提出的, 其原理是将图像窗口w沿任意方向做微小移动, 其窗口的灰度值变化会有3 种情况:

(1) 灰度值不随窗口w的移动而变化, 表明此处为平坦区域。

(2) 窗口w沿任意方向移动都会引起灰度值的剧烈变化, 表明此处为角点。

(3) 窗口w沿特定方向移动, 灰度值不发生变化, 沿其他方向移动, 灰度值剧烈变化, 表明此处为边缘。

窗口w移动时, 其灰度变化量可以定义为:

对于微小移动量, O (x2, y2) 可以忽略不计, 则式 (1) 可以写成:

其中

根据每个像素点的R值可以判断其是否为角点, 如图1 所示。

2.3 Harris原理检测直线

图像边缘是单像素的连通域, 将图像窗口沿边缘移动, 当边缘是直线时, 图像窗口的灰度值在窗口沿直线方向移动时不会发生变化, 沿其他方向移动时灰度值会发生剧烈变化, 通过图像窗口灰度值的变化情况, 可以确定边缘像素点是否在直线上。

根据式 (4) 中的灰度值变化量的定义, 可以得到

3 实验结果

在原Harris算法中求解时, 采用的是prewitt算子, 即[-1, 0, 1], 无法计算单位矩阵的横向微分, 本文采用简单的[-1, 1] 模板进行横向微分的计算, 得到的结果更加准确。

本文选用的图片为机场的卫星图像, 在Matlab2013a环境下进行仿真, 得到的结果如图2 所示。

图2中 (a) 图为一机场卫星图像作为原始图像, 经过阈值分割和LOG算子提取边缘后得到如图 (b) 的边缘图像, 其中包含了机场跑道信息, 图 (c) 则是在边缘图像中做Harris检测提取出的直线段, 图 (d) 是Hough变换法得到的直线特征提取图。可以看出, 本文算法可以很好的提取出目标的直线特征, 更具有针对性。

同时, 本文将该算法与Hough变换算法在计算时间上做了比较, 其结果如表1 所示。

可以看出, 本文算法在运算速度上优于Hough变换算法。

4 结论

本文提出的基于Harris算法的直线提取方法能够有效得提取图像中的直线特征, 同时与Hough变换相比, 本文算法是基于图像目标边缘信息, 更具有针对性, 并具有更快的运行速度。本文算法依赖于图像边缘提取的效果, 同时微分算子的选择会影响到直线的检测结果, 具有一定的局限性。本文提出的算法是根据Harris算法得到的, 目前已有多种Harris算法的改进措施, 其中的部分改进方法可以应用到本文算法的改进中, 进一步提升本文算法性能。

摘要：根据Harris算法的原理, 结合直线边缘的特征, 提出一种新的直线提取方法。图像灰度窗口在直线边缘上移动时, 只有沿直线方向移动, 窗口灰度才不会发生变化, 沿其他方向移动, 窗口灰度会产生较大变化。结合Harris算法原理, 推导了直线边缘的提取原理和方法, 并通过仿真实验, 证明该方法能有效的提取直线特征, 相比于Hough变换法具有更快的运行速度。

关键词：图像分割,边缘检测,Harris算法,Hough变换,直线提取

参考文献

[1]李建飞, 文志强, 卢水乐, 等.基于直线检测的遥感影像道路提取方法[J].科学技术与工程, 2015 (3) :124-130.

[2]康文静, 丁雪梅, 崔继文, 等.基于改进Hough变换的直线图形快速提取算法[J].光电工程, 2007, 34 (3) :105-108.

[3]周俊, 王仁礼, 吴云东.基于边缘检测的编组法直线提取[J].测绘学院学报, 2004, 21 (3) :181-183.

[4]陈宁宁.几种图像阈值分割算法的买现与比较[J].电脑知识与技术, 2011, 07 (13) :3109-3111.