用霍夫变换来提取目标边界.doc

《用霍夫变换来提取目标边界.doc》由会员分享，可在线阅读，更多相关《用霍夫变换来提取目标边界.doc（6页珍藏版）》请在三一文库上搜索。

1、第23卷2003年6月计算机应用ComputerApplicati onsVol .23Jun e,2003文章编号:1001- 9081 2003 06Z- 0117- 02用霍夫变换来提取目标边界张会章，张利霞，郭雷（西北工业大学 自动控制系，陕西 西安710072!。文中将就摘 要：霍夫变换因能够快速识别出由点构造的边界模型而应用于图像边界的识别霍夫变换的具体实现过程来介绍图像中一些边界形状的判识，如直线、圆等。关键词：霍夫变换；目标检测中图分类号：TP301 文献标识码:A第23卷2003年6月计算机应用ComputerApplicati onsVol .23Jun e,2003第23

2、卷2003年6月计算机应用ComputerApplicati onsVol .23Jun e,20031简述图像处理的一个重要任务是对图像中的景物进行分析和 理解,得到图像中要找 的东西。然而复杂目标不同于一般刚 体,它难以用固定的参数来描述,只能用一些抽象的语句来描 述。虽然难以设计一个具体算法去识别大量的复杂目标，但 可以根据人的视觉系统建立起一类具体目标的识别方法。人在观察自然景物时一般首先根据颜色、纹理、轮廓等特征把他 看到的景物粗略地分成几 个较大的区域，然后再对感兴趣的 区域进行仔细观察，以获得细节信息。因此作为计算机视觉 系统可以模仿人的这一视觉处理过程。首先粗略提取图像有 意义

3、区域，然后再对各个区域进行处理获取精确目标。线特征的投影不变性，能够帮助我们正确的判断和识别 一些特殊的目标。人造目标具有规律的边缘较多，如直线、圆 都具有描述比较简单的特征，因此，如何从图像中得到这些特 征边界是非常重要的。获取表征图像的关系可以减少物体模 型匹配的搜索空间。霍夫变换是一种可以将图像的特征点映 射至参数空间，从而获取图像特征点关系的方法，例如可以判 断点的共线特征、平行性、相交、圆等。2图像中的区域图像中人造目标显著的 边缘特 征为识别它提供了帮助， 需要相应的算法来有效地 发现这些边界并加以描述，霍夫变 换是一种在图像中检测直线和曲线的有效方法。从图像中检测直线和曲线的重要

4、性源于 现实对象大量有 价值的内容（如 公路、河流、桥梁、铁路）。霍夫变换已经成功地运用于各种图 像:卫片、工业图像以及所有需要定位物体任意形态的图像 中,在许多应用中，通常直线、圆形 是最为重要的特征，它们可以表示 规则对象的存在。霍夫变换（HT）由PVCHough提 出，后来Duda和Hart认为直线可以 用&和p参数来描述。如图1所示p 表示原点到直线的垂直距离 ，B表示 图1直线的参数形式 该垂线与X轴的夹角。它的参数方程为：p= xcos 0 + ysin 0这种方法和用（k , ©（斜率和截距）表示相比具有显 著的 优点，如斜率较大时表示就有困难 。国外的一些研究

5、者把HT 算法扩展到各 种形状的检测中而不只是直线（如圆弧、抛物 线、椭圆）。Wahl和Biland研究一种可以用峰值的分布模式来表示 的方法，然而他们把识别局 限在二维的结构图像中而不是真 实景物的复杂对象上，它利用单一的参数空间和应用不同的 规则来检测边缘特征（如共线、平行、相交）。本文将根据传统 的HT方法，对检测直线、圆形曲线进行研究。在检测这些特 征之前需要一些预处理，首先，利用Canny算法在图像中 提取 边界点，得到边缘点集P，然后根据邻接 性形成链 表，再根据 曲率变化进行分段，从而形成以段为格式的边缘组；得到局部 的HT变换后，再进行整体计算。如果考虑曲线的方向在一 定范围内

6、（A0变化，对各个组在这一范围内进行HT变换， 则可以减少计算量；相比较而言对圆的判断就要比直线复杂 止匕 o2.1直线的检测对于一条直线，如果不考虑边缘点之间的关系而来进行 判断的话，通常可采用以下算法：For each （x，y） P doFor 0= 0，2 n ,0 dop= xcos 0+ ysin 0H（ p，）= H（ p，）+1EndEnd该算法表明对于任意的边缘点在其各个方向上都有对应 的p值和其对应，如果简单地把p、看成一个二维平面，那么 对于每一个方格单元（p, 0都有对应的H（ p，0值，H（ p，0 事实上是某方向点的数目。如果没有噪音的干扰，则我们就可 以用H（ p

7、, 0来表示该方向上直线点的多少，显然用H（ p, 0来判断直线是可靠的。这样就可以较容易地确定点的共线情 况，因此，可以用H（ p, 0的值来进行直线的判断。具体的实现过程如下：第23卷2003年6月计算机应用ComputerApplicati onsVol .23Jun e,2003第23卷2003年6月计算机应用ComputerApplicati onsVol .23Jun e,2003收稿日期：2002- 07- 06;修订日期：2003- 03- 28作者简介：张会章（1965-）,男，博士研究生，主要研究方向：图像处理与识别、智能控制；张利霞（1964）,女，讲师，主要研究方向：人

8、工智 能；郭雷（1956-）,男，博士生导师，主要研究方向：图像处理与模式识别、神经元网络.，r 942014 China Academic Journal EIccLrumc Frtihlishing Husc. All rithls reserved.I）llp:wu wA'nkiJict第23卷2003年6月计算机应用ComputerApplicati onsVol .23Jun e,2003第23卷2003年6月计算机应用ComputerApplicati onsVol .23Jun e,20031)用Canny算法对原图进行 边缘提取，设P为得到的边 缘点集合；用Cramer

9、法则解方程组，得:2) 用以上程序计算岀 每个边缘点各个方向上的p,将对 应的H( p, 9加1；3) 根据H( p, 9)的峰值情况,从边缘点中判断满足(p, 9的点进行标注；4) 对于某一 H( p, 9所对应的点可根据x,y值计算该 方向上直线的长度；5) 判断点在该方向上的稠密度；6) 根据稠密度判断该直线是否为真。事实上，如果根据曲 率的变化,把边界分成若干段,每一mm ipya1 = i2ao =从而得到直线的方程。段在区间来进行计算判断,然后再进行拟合，从而可以显著提高计算的效率3.2 圆的拟合圆形轮廓可采用最 小二乘拟 合来获得某 些参数。已知圆 上若干点的坐标为(Xi,yi)

10、 ,i= 1 ,2,N,设圆的方程为：(x- xo)2 +( y - yo) 2 = R2方差定义为：2.2 圆的检测圆可以用如下方程来表示：(x - xo)2 +( y - yo)2 = r2从方程中可以看到一个圆需 要用三个参数来描述,(X0, yo)为 圆心的坐标,r为圆的半 径。那么 用以上算法要建立一个三维的累 加器才能判断共圆的点。由于该SEN卑.(X0 - x) 2 +( yo - yi)2 - R|由于上式带根号不易处理,可以换一种表达方式N2 2E =罩(Xo - Xi)+( yo - y) - Rm其中2Rm = R方程为三维锥面，因此要来判断圆的存在更为困难，对于这样从理

11、论上，上式同样可以得到一个最好的拟合，使得近似值与实际值的均方距离最小，如果定义一个三维问题可以通过某种约束使其变成一个二维问题,然 后再来解决。事实上，我们的目的是 在图像中检 测圆形区域, 如果根据区域的特征，将(X0,y°)和r限制在一定的范围内进 行计算，显然可以缩小计 算量。如果对于一个封闭 区域,还可Ri =(Xo -x)2 + ( yo -yi)以采用先计算岀可能圆的半 径，然后对边缘上的所有点进行 判断,从而快速的识别岀圆形边缘 。具体的实现过程：NE =R - Rm) 2根据最小二乘求偏导数，则有:1) 对图像进行边缘提取；2) 根据边缘点进行区域分割，建立区域边缘

12、点链表；3) 对区域的边界点求其质心的位置( X0,y0);4) 求其边缘点到质心的距离；5) 判断该边缘是否构成圆形边界。6) 同样可以采用以上相似的方法进行改进。另外，也可以采用几条弦的垂直平分线交叉点来得到圆心 。N1Rm = 1 XRi =i= 1通过进一步推导可G11G21其中：G12G22G113边缘线的拟合在一些精确计算中，有时需要给岀边缘的精确描述,因此要对提取的边界进行拟合，从而得到边缘线的精确方程。3.1直线的拟合已知M个点，它们的坐标分别为(X ,y)( i = 1,2,m),这些点可以构成一条直线。设所求的直线方程为：y = a0 + a1 x根据最小二乘直线拟合方法，

13、建立目标函 数如下：m2F( a0, a1)=严(a0 + a1 xi)-yi为了使所有节 点上函数偏 差的平方 和最小，由多元函数极值求法可知，a。、1应满足方程组a0cumal EkcLranic PubN寺习(Xo - Xi)2 +( yo- yi)2N i = 1xoyox2-得：C1=C2Ni= 1_8_ N LSXj XykNG21G12 =8£Xiyi-瓷NNNN4. . 2 _ _4 . . 2 _ 一C1=-尺 i=XijSx-卞NN+ 4 ”y2Xi + 4 fx：i = 1i = 1C2 =NNNNt£y2j罗-瓷fx2J>NN234Xxiyi+

14、 yfyi由此可以计算出xo和yo,再确定最佳的拟 合半径以上我们研究了边缘点的检测和如何得到边缘点方程的精确算法。无论是精确的还是粗略的描述都可为我们识别具体的目标而提供决策支持。在一些精密的机械加工中需要精 确的方程描述,在识别目标时可能只需要粗略的描述。因此 本文的一些研究成果可为我们研究边缘特征提供支持。mg rluusc All ririis reserved, tiltp/wwwcfikiLik 1第23卷2003年6月计算机应用ComputerApplicati onsVol .23Jun e,2003文章编号:1001- 9081 2003 06Z- 0119- 02排列问题的

15、有序化杨文显1 ,杨仲青2(1 .上海应用技术学院计算机科学与信息工程系，上海200233; 2.南京大学 物理系，江苏 南京210093摘 要：在引入混合进制数的基础上，对排列状态进行编码，从而使无序的排列状态有序化，为排列问题，路径搜索等问题提供了崭新的方法。关键词：程序设计；算法；排列中图分类号：TP301.6 文献标识码:A第23卷2003年6月计算机应用ComputerApplicati onsVol .23Jun e,2003第23卷2003年6月计算机应用ComputerApplicati onsVol .23Jun e,20031问题的提出排列是计算机算法中经常遇到的一类问题

16、。N个元素可 以组成N!种不同的排列状态,它们的集台构成了 N个元素 的全排列。一般地说,N !种排列状态之间是无序的,每一种 排列状态没有前趋，也没有后继。本文将排列问题有序化，并将每一种排列状态编码为 0N! - 1之间的一个整数，称为排列序数。排列序数的引 入，给排列问题的算法带来了一种新的思路。2混合进制数考察N位非负整数X :X = dNdN -1 d2d 1该数自右向左各数字所在位置分别称为数位1、数位2数位N。规定，数位i(i=1,2,N)上采用i进制计数。该数位上 可选i个不同的数字:0,1 ,2,，1- 1,di以Mi= i为模向相邻 高位(i + 1 位)进位，即逢i进1”

17、。按照进位计数制 计数法则，数位i上的权R可由下式获 得：Ri = Ri-1 * Mi -1其中R-1,Mi-1分别为相邻低位(i- 1)位上的权和 模。令R! = 1,则有：R2=R1* M1=1 X1 = 1 !R3=R2* M 2=1! X 2 = 2!R4=R3* M 3=2! X 3 = 3!MRi = Ri-1 *Mi-1 =( i - 2) ! * i - 1)=( i - 1) !NN于是 X =dNdN-1d2d1=口i*Ri=y；di*( n- 1) !注意到如下事实：数位1上采用“1进制” ,d1可选1个数 字,该数字为0。因此，d1的存在不影响X的取值,它的出现 仅仅是

18、为了形式上的完 整性。称数X= dN dN- 1 -d2d1为N位混合进制数，它的最小取 值为000= 0,最大取值为1000- 1 = N! - 1( N位 g 。n位混合进 制数的全体 组成非负整数的一个子集z'n = 0,1, - ,N! - 1。3 P函数以N = 4为例,将元素e1, e2, e3, e4的原始排列e1e2e3e4 称为正序”排列，其中每一个元素的下标都小于它右侧元素 的下标。排列e4e1e3e2不是正序排列，e3右侧的元素e2的下标小 于e3的下标，我们记该位上 逆序”元素个数为1,元素e4的 右侧有3个元素的下标小于4,该位上逆序元 素个数为3。记 下每个

19、元素位置上的 逆序元素个数，得到与该排列对应的一 组数:30 1 0,称此数为该排列的 中间码”。每一个排列 都有 与之对应的唯一的中间 码。中间码的末位恒为0。中间码每一位数字 的取值有确定的范围，从末位起依次 为00,01,02,03 。显然,每个中间码是 N位混合 进制数的一个表述。称中间码所代表的值为该排列的排列 序数”。每一个排列均有一个唯一的“排列序数”,它的取值范围 是0N! - 1。将N个元素的N !种排列定义为集合An。至此，已经 建立了如下的映射P：An探Z'n。同样地，存在它的逆映射第23卷2003年6月计算机应用ComputerApplicati onsVol

20、.23Jun e,2003第23卷2003年6月计算机应用ComputerApplicati onsVol .23Jun e,2003:计算机控制技术收稿日期:2002- 03- 15;修订日期：2002- 06- 09作者简介：杨文显(1947-),男，上海人，副教授，主要研究方向第23卷2003年6月计算机应用ComputerApplicati onsVol .23Jun e,2003第23卷2003年6月计算机应用ComputerApplicati onsVol .23Jun e,2003参考文献1 Davis LS. Hierarchical generalized Hough Tra

21、nsforms and Line - segment Based generalied Hough Transforms J . Pattern Recognition, 1982,15 4) :277- 285.2 Amir I . Algorithm for Finding the center of Circular Fiducials A. ComputerVision, Graphics, and Image Procesing C . 1990, 49. 398 -406.3 Li HW, Lavin MA . Fast Hough Transform :A Hierarchica

22、l ApproachA . ComputerVision, Graphics, and Image ProcessingC . 1986,36 . 139- 161.4 Mansouri AR ,MalowanyAS, LevineMD. Line Detection in Digital PiG tures:A Hypothess Prediction/ Verification Paradgm A . Computerv- sion,Graphicsprocesig C| . 1987,40. 95- 114.5 Zlotnick A ,Carnine J°D. Finding RoadSeedsin Aerial Images CVGIP:第23卷2003年6月计算机应用ComputerApplicati onsVol .23Jun e,2003Image Understanding J . 1993,57(2 : 243- 260.9爭4加 14 China AcademicurneiI Itkclrunic Puhishing Housc. A11 rights reserved, http:' v 讣 wxnki.ncL