文章编号:1006-0871(2006)04-0053-04广义霍夫变换的改进叶州海, 陈福民(同济大学电子与信息工程学院,上海 200092)摘 要:提出基于广义霍夫变换(Generalized H ough Transfor m ation ,GHT )的改进算法.与传统方法比较,新方法将参考点设在形状边界上,可以减少内存的需要,并且用于寻找峰值的速度也大大提高.理论上,改进后的算法对内存的需要是一个基于形状描述复杂度的函数,越是精确和高级的形状和特征描述,意味着节省的内存空间越大.最后,将改进的GHT 应用于物体形状识别,取得一些实验性效果.关键词:广义霍夫变换;形状识别;内存空间节省中图分类号:TP306.1 文献标志码:AGeneralized Hough transfor mation i m prove mentYE Zhouha,i CHEN Fu m i n(Schoo l o f E lectron ic&Info .Eng .,T ong jiU n i v .,Shangha i 200092,Ch i na)Abst ract :An i m prove m ent ofG enera lizedH ough T ransfor m a ti o n(GH T)is proposed .Co m pared w ith the trad itionalm ethod ,the ne w one can reduce the storage requ ire m ent by setti n g reference points on shape edge .M eanw hile ,the speed o f search for peak is acce lerated conspicuously .Theo retica ll y ,the storage require m en t is a functi o n based on t h e co m plex ity of the shape descri p ti o n i n the ne w m et h od .And the m ore accurate and higher level the shape is described,the s m aller the storage space is needed .I n the end ,the i m proved a l g orith m is pu t i n to the ob ject recogn iti o n ,and obta i n s so m e experi m ental resu lts .K ey w ords :genera lized H ough transfor m ati o n(GHT );object recogn ition ;storage space reduction收稿日期:2006-02-27;修回日期:2006-03-29作者简介:叶州海(1980-),男,江苏泰兴人.硕士研究生,研究方向为网络多媒体技术和图像处理,(E-m ail)t h reel eafzerg @ci ti z .net0 引 言霍夫变换(HT )是一种用于区域边界形状描述的方法,经典HT 常被用于直线段、圆和椭圆的检测.HT 的优点是:(1)对噪音的抗干扰性;(2)能够处理多个形状.广义霍夫变换(Genera lized H ough Transfor m ation ,GHT)可以推广至检测任意形状.其基本思想是将图像的空间域变换到参数空间,用大多数边界点满足某种参数形式来描述图像中的曲线.实现方法是寻找在参数空间由参数累加器形成的峰值.由于HT 是根据局部度量来计算全面描述参数,因而具有很强的容错性和鲁棒性.然而,传统GHT 有几个较大的缺陷:(1)计算量大,每个边缘点映射成参数空间的一个曲线,是一到多的映射;(2)占用内存大;(3)提取的参数受参数空间的量化间隔制约.本文通过将参考点设立在边界点上以减少GHT 对内存的需求.当然,改进后的方法会对GHT 的鲁棒性有一定影响,可以通过设多个参考点来加强鲁棒性,而且增加的R 关系表带来的额外内存空间相对于采用该算法所节省的内存空间而言微不足道.最后本文将此改进方法用于物体形状检测,对图像进行边缘检测处理(Canny Detector),并估计其算法性能.1 广义霍夫变换设X r =(x r ,y r )T是任意形状区域内的参考点(如区域的形心),X =(x,y )T是边界B 上任意一点,记X r 和X 之间的差矢量r =X r -Xr 与x 轴夹角为U ,点X r 至边界点X 的距离为r .计算边界点x 处的边界取向H ,见图1.图1 边界点x 处边界取向H 的计算显然r 和U 是取向H 的函数,将H 角可能的取值范围分成离散的m 种可能状态(i $H ,i =1,2,3,,,m ),记作H k =k $H其中$H 是角度增量,定义H k 的方向参数r H k ={r |x r =x +r (H k )#cos (U (H )), y r =y +r (H k )#sin (U (H))} 对全部边界点确定的参考点位置建立关系查找表R.如果一个区域边界上的大部分点(x,y )都具有参数r H k ,那么就把r H k 作为这条边界曲线的形状特征.表1 R 关系表i H i 半径集合{r H i},r =(r ,U )1$H r 11,r 12,,,r 1n 122$H r 21,r 22,,,r 2n 2,,,k k $H r k 1,r k 2,,,r k nk,,,mm $Hr m 1,r m 2,,,r m nm任意形状区域边界的HT 归纳如下: 步骤1 制作关系表;步骤2 对参考点位置可能取值的计数器阵列A (x r ,y r )清零;步骤3 对所有边界点x =(x ,y ),计算(1)梯度方向H(2)x r =x +r (H k )#cos (U (H))y r =y +r (H k )#sin (U (H ))(3)相应的A (x,y )加1,即A (x r ,y r )+1→A (x r ,y r )步骤4 对区域边界上的每点执行步骤(3),找出{A (x r ,y r )}中的最大值,r*={r H k |A (x r ,y r )=m ax 1[i [mA (x r ,y r )}2 改进算法的思想运用GHT 进行形状平移检测时,计数器数组大小约为N @N (图像大小N @N ).所以,对于一个256@256位图,H T 需要216字节的内存用作计数器数组,因此内存代价非常大.如果不是随意选取参考点,而把选择范围限制在形状边界点上,很显然,将会有一个或更多的边界点恰巧成为形状的参考点.因此,可以认为边界像素坐标便是潜在的参考点位置.因为边界点像素只是图形全部像素的一小部分,所以HT 需要的累加器(只需分配给边界像素)内存变得相当小.以上是如何提高GHT 算法空间效率的关键.用R 关系表描述一个形状的原形,参考点的选择可以是任意的,但必须位于形状的边界点上.当然,关系表的索引项依然是H .在形状检测过程中,每个像素p j (j =1,,,n e )都附带计数器.由像素p j 得到的约束关系(r k ,U k )(k =1,,,n ),经计算得出的坐标正是另一个边界点的坐标,则此像素对应的计数器加1.当k 遍历在R 关系表中与取向H 所有的(r ,U )后,在累加器中出现高于所设定的阀值峰值则说明检测出预设形状.3 改进后的算法构造R 关系表这一环节与GHT 相似,以下是形状检测步骤:(1)遍历被边界检测器检测过的边界图并标志出所有边界点,将其坐标与边界方向H 放入数组中,并在数组中为每个元素增加一个计数器(相对于传统方法,此累加器的大小已经大大减少).(2)对于每一个边界点对应的H 查找它在R 关系表中的(r ,U ),根据此计算x r =x +r (H )cos (U (H ))y r =y +r (H )sin (U (H ))这是相对参考点的候选位置.(3)对于每个计算出的候选位置,决定候选像素点x r 是否为边界点(因为现在参考点一定是边界点),是则该边界点对应计数器加1.(4)当所有的边界点通过R关系表都映射至霍夫空间,在一维累加器中寻找峰值,由于原来的HT在一个两维的累加器数组寻找最大值,因此,搜索时间缩短.在选择参考点上可以采取这样的策略:它们平均地分布在形状模型的边界上.4改进后算法的初步评估当然有时候会出现因为闭合边界未被检测出来而使边界像素点丢失的情况.所以为了增强这种方法的健壮性,可以在边界上多选取几个参考点.可以选择创建以各个参考点独立的R关系表,或者将其合并成一个R关系表.以上这两种选择取决于采取何种边缘检测方法.参考点r的冗余度将稍微减少改进后算法对空间上的节省.下面计算改进方法节省的空间:如果在数据库中有S个预设形状,平均有B个形状边界像素点.进一步假设参考点的冗余度为r (对于每个形状都设r个参考点),则广义霍夫变换需要内存空间为N2+S#B,改进后需要空间n e+S #B(r-1),n e指图像的所有边界点个数,显然改进后的方法对空间需求大大降低.5使用高级形状特征语义直到目前,改进的算法都是使用原始边界信息进行形状原型描述和形状检测.虽然可以显著节省内存,但计算速度却会因为边界像素点和参考点个数而大受影响.如果使用高级形状特征语义来获得更清晰简洁的形状信息,那么就能提高该改进算法的实用性和高效性.在形状原型描述中,可以选择一个或多个目标形状的结构特征作为参考特征量,并将所有的形状特征量作为查找表的索引(连同H).可以在形状检测时从场景中抽取一些高级形状特征加入到查找表中,则查找表中相应的每一条记录可用来计算出可能的参考特征位置.该参考特征位置专门用于在整张包含场景特征信息的表中进行搜寻工作.在考虑了每个场景特征后,再次搜索整个表就可以检测出峰值.新算法描述如下:(1)从预设形状中抽取形状特征语义,然后以一定的标准比如一种特征的可视性、显著度、大小等从所抽取的特征语义中选取参考特征.(2)把这N项的特征并作一个集合作为新构造查找表的一个索引项;把抽取特征与参考特征的关系作为新查找表的一条记录.(3)对于给定的图像,使用同样的特征提取过程抽取有用的和可行的特征.把每个候选特征标号f i的特征信息存储在一个数组A(f i)(特征1,特征2,,,特征N)的元素中.再设一个A(f i)的计数器记录每个抽取出的特征f i.(4)对于每个候选特征f i,用关联集合决定其相应的在新查找表里的记录(记录有所抽取的特征与参考特征的关系).这些记录可以用于计算可能的参考特征位置.运用简单的过程可以确定出参考特征值是否位于预设的数值范围内.如果计算出的位置出现在某个图片特征f i范围内,那么相应A(f i)累加器则加1.(5)在考虑所有抽取出的场景特征f i后,从一维累加器里寻找出峰值.如果找到峰值,则意味着已找到目标形状.总而言之,从一张图片中抽取的特征数量要远远少于边界数.因此,同标准GH T相比,用于查找表的查找记录和用于存储抽取的形状特征也大为减少.显然,用于更新累加器的计算时间和寻找峰值的时间也大为减少.6改进后的算法实验测试结果提供一些实验性结果说明改进后算法的优点.图中实景是由DH-VRT-CG200图像采集卡采集的.形状原型是一个2D小熊模型图(见图2).图3显示小熊图形被许多复杂的形状所包围.图4是图3经过Canny Detector处理后的边界图,其中边界像素点个数为2551个.图5为经过改进算法计算后的累加器峰值图.结果表明改进方法的计算速度比标准GHT快3%~5%.接下来运用高级形状特征语义作为新构造的查找表的索引项.如前所述,可以从形状原型中抽取特征语义作为参考特征,但这里简化,仅用两个参考点显示其概念(见图6).在实验中,从形状原型抽取直线段作为高级特征语义,其中把直线段的长度和方向作为新查找表的索引项.在提取图片直线段时,采用多边形曲线近似算法.图7是一张实景图,表示小熊被许多形状包围.图8是图7经过Canny D etector 处理后的边界图.图9为经过新算法计算后的累加器峰值图.结果表明,虽然边界像素点增加为8304个,但计算速度却比标准GHT快60%~70%.图2原型图3实景(1)图4边界(1)5累加器峰值(1)图6带参考点图7实景(2)图8边界(2)图9累加器峰值(2)7结束语提出一个改进的基于GHT的算法用于检测二维图形的形状.此方法的关键在于将参考点的选择放在物体边界上.从结果得出该方法与传统方法相比可大大减少所需内存空间的结论.但是,如何能有效运用更加高级的特征语义作为构造查找表的索引项,从而能更大地节省空间和计算时间,有待进一步研究.参考文献:[1]郑南宁.计算机视觉与模式识别[M].北京:国防工业出版社,1998.[2]LI U Tyng-Luh.A generalized s hape-axis m odel f or p lanar s hap es[C]//Pattern Recogn iti on,2000Proc15th InternationalC onferen ce,2000,3:487-491.[3]CHAU C hun-Pong,SI U W an-Ch.i G eneralized dua-l poi n tH ough tran sfor m for ob j ect recogn i ti on[C]//I m age Processi ng,1999P roc In ternati on-alC on f eren ce,1999,1:560-564.[4]TEZ M OL A,SAR I-SARRAF H,M I TR A S,e t al.Cus t o m iz ed H ough trans f or m for robust seg m en tati on of cervical vertebrae fro m X-ray i m ages[C]//I m age Anal ys i s and Interpretation,2002Proc Fifth I EEE Sou t hw est Sy m posi um,2002:224-228.[5]QI J i n,S H I Zhongchao,Z HAO Xuy i ng,et al.A novel fi ngerpri n t m atch i ng m ethod b ased on the H ough transfor m w ithout quan tizati on of theH ough s pace[C]//I m age and Graphics,2004P roc Th ird In ternati onal Con ference,2004:262-265.[6]TOU J S,BEN-A M ARA N E,AM I R IH.Generali zed H ough transfor m for arab i c op tical character recogn iti on[C]//Docum en tAn al ysis and R ec-ogn ition,2003P roc Seven t h I n tern ati ona lConference,2003:1242-1246.(编辑廖粤新) (上接第52页)参考文献:[1]SHAPI RO J M.Em bedded i m age cod i ng u si ng zero trees ofw avel et coeffi cients[J].I EEE T rans on S i gnal Processi ng,1993,41(12):3445-3462.[2]SAI D A,PEARL M AN W A.A new,f ast,and effi cient i m age codec b ased on set partiti on ing i n h ierarc h ical trees[J].IEEE Tran s on C i rcu i tsand Syste m s forV i deo T echnology,1996,6(6):243-250.[3]SAI D A,PEARL M AN W A.An i m agem u lt-i res ol u ti on representation for l ossless and lossy comp ress i on[J].IEEE T ran s on I m age Process i ng,1996,5(9):1303-1310.[4]ANTON I N IM,BARLAUD M,M ATH IEU P,et al.I mage cod i ng using wavelet transfor m[J].I EEE T rans on I m age Process i ng,1992,1(4):205-220.(编辑廖粤新)。