自动化学报
ACTA AUTOMATICA SINICA
1998年 第24卷 第5期  Vol.24  No.5 1998



扩展Hough变换及其在主动
视觉中的应用
汪　威　胡占义　马颂德
摘　要　讨论了Hough变换的直线扩展参数化形式成立的几个充分条件，并提出了利用扩展参数化形式模拟人类视觉系统中视网膜上视锐度空间分布的具体方法，进而将该方法运用于主动视觉中的注视点轨迹控制问题，取得了较为满意的结果.
关键词　扩展Hough变换，直线参数化形式，主动视觉，注视点轨迹控制.
THE EXTENDED HOUGH TRANSFORM AND ITS
APPLICATIONS IN ACTIVE VISION FIELD
WANG WEI　　HU ZHANYI　　MA SONGDE
(National Laboratory of Pattern Recognition,Institute of Automation,
The Chinese Academy of Sciences,Beijing　100080)
Abstract　　In this paper,the extended Hough transform(EHT)is investigated.It is shown that it is impossible to give the necessary conditions of being an EHT.Two sufficient conditions,however,are introduced.In addition,the EHT is used to simulate a human vision system for the study of gaze control,a problem actively pursued in the active vision field currently.
Key words　Extended Hough transform,line parameterization,active vision,focus of attention control.
1　引言
　　Hough变换［1，2，3］自从被提出以来，由于具有受随机噪声影响小，对部分遮挡现象不敏感而且适合于并行处理等优点，因此在计算机视觉与模式识别等领域得到了广泛的应用.随着大规模集成电路技术的飞速发展，Hough变换的硬件实现逐渐成为可能，这种方法也越来越受到人们的重视.
　　Hough变换的参数化形式对其性能有着至关重要的影响［4，5］，为此，针对不同的应用场合文献中已提出多种直线参数化形式［6，7］，而且越来越多的新参数化形式也在不断出现.针对这些参数化形式，文献［8，9］中提出了评价和设计直线参数化形式的若干准则.
　　主动视觉［10，11］是计算机视觉领域一个非常重要的研究方向，它强调视觉过程中观察者和环境的动态交互过程，并研究给定任务情况下对外部可感知世界所刺激的动态行为的发展.注视点轨迹控制则是主动视觉中一个重要研究课题［12］，有效的注视点轨迹控制对主动视觉中许多概念的实现有着极其重要的意义.
　　扩展直线参数化形式［13］是一类范围很广的直线参数化形式，它包含文献中已报道的所有主要的直线参数化形式，并具有更一般的形式，但是其性质与应用尚未得到深入研究.本文基于文献［6］中提出的唯一性、有界性和均匀性准则，提出扩展参数化形式构成直线参数化形式的若干充分条件，探讨它们在主动视觉尤其是在注视点轨迹控制方面的应用.
2　Hough变换的直线扩展参数化形式
2.1　扩展参数化形式
　　Koshimizu等人［13］提出，直线的扩展Hough变换(EHT——Extended Hough Transform)的基本形式为
g(μ,ξ)=x.f1(μ,ξ)+y.f2(μ,ξ),　　(1)
其中μ，ξ是直线的两个参数.并且，只要满足以下三个条件，即可以把(1)式作为EHT的一个参数化形式
　　条件1.f1(μ，ξ),f2(μ，ξ),g(μ，ξ)是关于变量μ、ξ的单值连续函数，且满足f21(μ，ξ)+f22(μ，ξ)≠0.由于f21+f22≠0，方程(1)可被替换为方程(2)，(3).
　　(2)
R(μ，ξ)=x.cosΦ(μ，ξ)+y.sinΦ(μ，ξ).　　(3)
　　条件2.R(μ，ξ)，Φ(μ，ξ)分别关于变量μ，ξ单调递增(或递减)，即满足下面方程(4)
Rμ＞0(或＜0)，　　Φξ＞0(或＜0).   (4)
(这里记下同)
　　条件3.设变量μ，ξ有界，且各自的界限为ξk,ξ0与μL，μ0.此外设B为标准直线参数化形式［2］下参数ρ的范围，则方程(5)必须得到满足
｜Φ(μ，ξK)-Φ(μ，ξ0)｜=π，　　对于μ，　(5a)
R(μ，ξK)-R(μ，ξ0)=0，　　对于μ，　(5b)
R(μL，ξ)-R(μ0，ξ)=B，　　对于ξ.　(5c)
　　事实上，上述3个条件既不是直线参数化形式的充分条件，也不是必要条件.因为作为一个直线参数化形式，它至少应满足唯一性条件［8］，即设(P1，P2)为一直线参数化形式，则任意的一对参数(p1,p2)可以确定唯一的一条直线，且任意一条直线都对应于唯一的一对参数(p1,p2)1).而上述三个条件并不能保证唯一性条件成立.
　　根据唯一性条件和EHT形式，易得
　　结论1.形如方程(3)的直线参数方程，满足唯一性条件的充要条件是：设定义空间内函数Φ(μ，ξ)的等值点集合Ω=｛(μ，ξ)｜Φ(μ，ξ)=c｝2)，则对于(μ1，ξ1),(μ2，ξ2)∈Ω，如果(μ1，ξ1)≠(μ2，ξ2)，有R(μ1，ξ1)≠R(μ2，ξ2).
　　上述结论是很明显的，这是因为对于形如方程(3)的直线参数方程，若给定一对参数(r,φ)(其中r=R(μ，ξ),φ=Φ(μ，ξ))，它和图象空间的直线存在一一对应关系，所以唯一性条件等价于在参数(r,φ)，(μ，ξ)之间建立一一对应关系.而结论1中的条件恰是该一一对应关系成立的充要条件.
　　结论2.条件1，2，3不是构成扩展参数化形式的充分条件，因为可以找到两组参数(μ1，ξ1)≠(μ2，ξ2)，但(Φ(μ1，ξ1),R(μ1，ξ1))=(Φ(μ2，ξ2),R(μ2，ξ2))(如图1所示).
Φ(μ，ξ)=μ+3ξ-1),　　(μ，ξ)∈［0，1］，


图 1　条件1，2，3的不充分性图示

　　试考虑集合Ω=｛(μ,ξ)｜μ+3ξ=2,ξ∈［,),μ∈［0，1］｝，对于(μ1,ξ1)∈Ω，(μ2,ξ2)∈Ω且(μ1,ξ1)≠(μ2,ξ2)有：Φ(μ1,ξ1)=Φ(μ2,ξ2)=,R(μ1,ξ1)=R(μ2,ξ2)=,由结论1知唯一性条件被破坏.因此，条件1，2，3不是扩展参数化形式的充分条件.
　　结论3.条件1，2，3不是构成扩展参数化形式的必要条件.下面的反例(如图2所示)即可充分说明这一点.


图 2　条件1，2，3的不必要性图示

　　容易验证它满足唯一性条件，构成一个扩展参数化形式.但显然并不同时满足条件1，2，3.可见，条件1，2，3不是构成扩展参数化形式的必要条件.
2.2　扩展参数化形式满足唯一性条件的充分条件
　　根据结论1，要使扩展参数化形式满足唯一性条件，必须在参数对(r,φ)，(μ,ξ)之间建立一一对关系.由于只考虑R(μ,ξ)，Φ(μ,ξ)是单值连续函数的情况，所以从几何的角度看，这相当于：若给定一对(r,φ)值(r0,φ0)，则曲线Φ(μ,ξ)=φ0和R(μ,ξ)=r0在定义区域内有且仅有一个交点.一般情况下，曲线Φ(μ,ξ)=φ0和R(μ,ξ)=r0的相交关系十分复杂，很难给出只有一个交点的条件，但就实际应用而言，一般只要考虑以下较为特殊的情况就已经足够了.
　　定理1.若直线的扩展参数化形式R(μ,ξ)=x.cosΦ(μ,ξ)+y.sinΦ(μ,ξ)满足
　　1)函数R(μ,ξ)，Φ(μ,ξ)是关于变量μ、ξ的单值连续函数，其中变量μ∈［μ0，μL］，ξ∈［ξ0，ξK］；
　　2)在整个定义区域上Φξ＞0(或Φξ＜0)；｜Φ(μ,ξk)-Φ(μ,ξ0)｜=π，μ；
　　3)在整个定义区域上Rμ＞0(或Rμ＜0)；min(R(μ0,ξ),R(μL,ξ))=ρ0,max(R(μ0,ξ),R(μL,ξ))=ρL,ξ，其中［ρ0，ρL］为标准直线参数化形式下参数ρ的范围；
且满足下列条件之一，则该参数化形式满足唯一性条件.
　　条件4.Φμ=0,μ,ξ,
　　条件5.Rξ=0,μ,ξ.
　　证明.若函数R(μ,ξ)，Φ(μ,ξ)满足题设条件与条件4，则有
　　由于Φμ=0，所以函数Φ(μ,ξ)实际上仅与变量ξ有关，不妨记作Φ(μ,ξ)=f(ξ).又因为Φξ≠0，故f′(ξ)≠0，只要ξ值不同，f(ξ)的值即Φ(μ,ξ)的值也不相等3)，从而Φ(μ,ξ)等值意味着ξ值相等.因此，结论1中提到的函数Φ(μ,ξ)的等值点集合Ω=｛(μ,ξ)｜Φ(μ,ξ)=c｝实际上是一条平行于μ轴的直线ξ=a,其中a为ξ定义区间内的某一常数.考虑到Rμ≠0，所以当ξ值相等而μ值不相等时，R(μ,ξ)的值不相等，由此得：Φ(μ,ξ)的等值点集合中任意不同两点的R(μ,ξ)值均不相等.再根据结论1可知此时扩展参数化形式满足唯一性条件.
　　类似可证，当函数R(μ,ξ)，Φ(μ,ξ)满足题设条件与条件5时，扩展参数化形式也满足唯一性条件.综合以上结果可知定理成立.证毕.
　　从几何角度看，定理1实际上是把原来较难处理的两条一般曲线相交的问题简化成一条直线与一条曲线相交的特殊问题.条件4中Φμ=0意味着曲线Φ(μ,ξ)=φ0退化成一条与μ轴平行的直线，而条件5中Rξ=0则意味着曲线R(μ,ξ)=r0退化成一条与ξ轴平行的直线.这样，定理1中条件的充分性就很明显了.
　　在文献［6］中指出，优化直线参数化形式除了满足唯一性条件外，还应满足有界性及均匀性条件.所谓有界性，就是说在Hough变换下，一个有界的图象空间应变换成一个有界的参数空间.而所谓均匀性，就是指在标准参数化形式下，当参数θ被选择为量化变量时，变量θ的密度函数为均匀分布；若直线用其它参数化形式表示时，则通过标准参数化形式与该参数化形式之间的对应关系，可以求得该参数化形式下量化变量的密度函数，该密度函数也应为均匀分布.在本文所研究的扩展参数化形式下，满足上述两条要求的条件是
　　推论1(有界性).如果函数R(μ,ξ)，Φ(μ,ξ)满足定理1的条件，则扩展参数化形式满足有界性条件.
　　证明.给定一个图象坐标系(x,y)∈［-N/2，…，N/2，-M/2，…，M/2］，对于定理1中的扩展参数化形式，可直接得Φ(μ,ξ)∈［0，π),｜R(μ,ξ)｜事实上函数R(μ,ξ)，Φ(μ,ξ)是定义在有界闭区域上的连续函数，而且(r,φ)，(μ,ξ)之间存在一一对应关系.所以函数R(μ,ξ)，Φ(μ,ξ)有界也意味着(μ,ξ)对应于有界区域上.
　　推论2(均匀性).若函数R(μ,ξ)，Φ(μ,ξ)满足定理1题设条件，且有Φ(μ,ξ)=aξ+b(其中a,b为两个任意常数)，则扩展参数化形式满足均匀性条件.
　　显而易见，这是因为在标准参数化形式下，如果参数θ的密度函数为均匀分布，由于这里Φ=θ且ξ=(Φ-b)/a，所以ξ的密度函数同样为均匀分布，即均匀性条件得到满足.
3　扩展Hough变换在主动视觉中的应用
3.1　扩展参数化形式与注视点轨迹控制
　　在计算机视觉领域，主动视觉是一个非常重要的研究方向，它突出了视觉过程中观察者和周围环境的动态交互过程，并强调这一过程中观察者的主动性.注视点轨迹控制则是主动视觉中一个重要研究课题.有效的注视点轨迹控制对主动视觉中许多概念的实现有着极其重要的意义.
　　在人类的视觉系统中，视网膜的不同部分对外界刺激的敏感程度其空间分布是不均匀的.从生理结构上看，视网膜上视觉感受器(主要指锥体细胞)的空间分布是越趋向于视野中心(中央窝)密度越高，而从中央窝往边缘则越来越低.相应地，视网膜中心的视锐度最高，逐渐往边缘测试时，视锐度就会急剧下降.视觉系统的这一特点保证了人类在观察外部世界时在注视点附近(即视网膜中最敏感部分)具有最大精度.而在视网膜的边缘只有较粗糙的分辨率.因此，视觉系统在把主要注意力集中于视野中心感兴趣部分的同时，也能保持对其它部分的适度注意.由于人眼能不断改变注视点，所以实际上人眼能以适当的精度观察视野中的任何部分.
　　文献［14］中采用特殊的CCD摄像机结构模拟了人类视觉系统这一特征，并把它应用于计算机视觉系统，取得了一定的成功.但考虑到如果能用软件的方法以合理的代价实现类似的特征，则硬件实现并无很大必要.本节旨在利用前面得到的结果，采用扩展参数化形式来解决这一问题.
　　视网膜上视锐度的空间变化可以用一个径向截线为对数曲线的曲面来模拟.据此定义函数R(μ,ξ)，Φ(μ,ξ)如下：
　(6)
其中a,b,m,n为常数.
　　容易验证R(μ,ξ)，Φ(μ,ξ)满足定理1和推论2的条件，因此可以构成直线的扩展参数化形式4).如图3所示，该扩展参数化形式特点在于：当R(μ,ξ)值较小亦即离图象中心较近时，很小的R(μ,ξ)值变化能引起较大的μ值变化；而当R(μ,ξ)值较大亦即离图象中心较远时，大的R(μ,ξ)值变化只能引起很小的μ值变化.所以，μ参数在小的R(μ,ξ)值处敏感，而在大的R(μ,ξ)值处则受影响较小，这恰恰符合人类视觉系统的特征.
　　通过检测参数空间(μ,ξ)中的峰值，可以对图象中心附近的直线以很高的精度确定其参数，同时也能兼顾图象边缘附近的直线，估计其粗略的参数值，然后再根据这些粗略的参数值适当移动注视点，把边缘附近感兴趣的部分移至观察中心，再以很高的精度确定其参数值.这样，就可用Hough变换的方法来实现主动视觉中的注视点轨迹控制。


图 3　R(μ,ξ)关于变量μ取值曲线
觉中的注视点轨迹控制.
3.2　实验结果
　　为证实上面所提出的扩展参数化形式的有效性，做了以下实验
　　　考虑一个区域为［-192…192，-144…144］的图象空间，其对应标准直线参数化形式下参数ρ的取值范围是［-244，244］.设变量μ和ξ取值范围分别为μ∈［0，100］，ξ∈［0，180).根据公式(6)，定义函数R(μ,ξ)，Φ(μ,ξ)5)如下(R(μ,ξ)的取值如图3所示)：
Φ(μ,ξ)=π.ξ/180，　　　μ∈［0，100］，ξ∈［0，180)

　　图4(a)为原始图象，在图象空间内有八条直线，其中四条靠近图象中心，另四条分布在图象边缘附近.
　　用上述直线扩展参数化形式对图4(a)进行变换后，得到的相应参数空间(μ,ξ)如图4(c)所示.经观察可知，图象边缘附近的四条直线在参数空间内对应于两对紧密相邻的峰值，而靠近图象中心的四条直线则对应于四个被明显分开的峰值.
　　虽然在分布很密的峰值处参数的分辨率比较低，但是根据这些峰值所对应的参数值，仍可以估计出它们所对应的直线在图象空间中的大致范围，以作为下一步注视点轨迹控制的依据.
　　根据所估计出的参数值，图4(b)表示当把注视点移至原来图象边缘四条直线附近时的情形.用上述直线扩展参数化形式对图4(b)进行变换后，得到的相应参数空间(μ,ξ)如图4(d)所示.很明显，在改变注视点后，原来参数空间内紧密相邻的两对峰值现在已经被清楚地分隔开来，而原来四个被明显分开的峰值现在则变成为两对紧密相邻的峰值.


(a)原始于象


(b)改变注视点后的图象


(c)图案象（a）对应参数空间的三维图示


(d)图象（b）对应参数空间的三维图示
图4　直线的扩展参数化形式和注视点移动的实验结果
4　结论
　　从上面的实验可以看出，本文给出的直线扩展参数化形式，可以在付出合理代价的前提下用软件模拟人类视觉系统中视网膜上视锐度的空间变化特性，并能有效地实现主动视觉中的注视点轨迹控制.由于Hough变换原来所固有的优点并没有受到影响，因此该方法有很大的实用价值.
国家863高技术发展计划及国家自然科学基金资助项目.
　1)(p1,p2)是(P1，P2)的一对给定数值.例如在标准直线参数方程ρ=x.cosθ+y.sinθ中，参数对为(ρ，θ)，对应于直线2=x.cos45°+y.sin45°的参数值为(2，45°).
　2)由于本文所讨论的扩展参数化形式对函数Φ(μ，ξ)只要求｜Φ(μ，ξk)-Φ(μ，ξ0)｜=π，在整个定义区域上Φ(μ，ξ)的取值可能超出一个长度为π的区间.这里约定Φ(μ，ξ)=c实际隐含Φ(μ，ξ)=c+kπ,k∈Z，其中Z代表整数集合.
　3)这里用到了中值定理：对ξ1≠ξ2,∵f′()≠0 ∴f(ξ1)-f(ξ2)=f′().(ξ1-ξ2)≠0，其中∈(ξ1，ξ2).
　4)这里Rμ在μ=b/2处等于0并不与定理1矛盾.事实上，Rμ可以在有限个孤立μ值点处等于0，而定理1仍然成立，这只需把证明中使用中值定理的步骤略作修改即可：不失一般性，不妨假设有ξ1＜ξ0＜ξ2，f′(ξ)＞0，ξ∈［ξ1,ξ0)∪(ξ0,ξ2］,f′(ξ0)=0,则f(ξ2)-f(ξ1)=(f(ξ2)-f(ξ0))+(f(ξ0)-f(ξ1))=f′(2).(ξ2-ξ0)+f′(1).(ξ0-ξ1)＞0，其中1∈(ξ1,ξ0),2∈(ξ0,ξ2).
　　5)这里把方程(6)中常数值n取为19是基于以下考虑：由于在计算机内实现直线扩展参数化形式时参数空间(μ,ξ)是离散的，我们希望在R(μ,ξ)精度最高处(即μ=50处)R(μ,ξ)改变一个象素大小时μ也相应跨过一个累加单元(否则在各参数单元计数过程中，很可能出现连续函数峰值对应的单元上的计数值被分散到其邻近的单元，从而峰值不再那么突出)，再加上μ=100时R(μ,ξ)≈240这条约束，即可解出常数m和n.
作者简介：汪　威　1972年生于湖北省.1994年毕业于浙江大学计算机系，获工程学士学位，1997年于中国科学院自动化所获硕士学位.主要研究方向为图象处理、计算机视觉、模式识别.
　　　　　胡占义　1961年生于山西省繁峙县.1985年毕业于北方工业大学自动化系，1988年和1993年先后于比利时Liege大学获计算机科学硕士和博士学位.现为中国科学院自动化所模式识别国家重点实验室研究员.主要研究方向为图象处理，计算机视觉，模式识别.
　　　　　马颂德　1946年生于上海.1968年毕业于清华大学自动化系，1983年获巴黎第六大学博士学位，1986年获巴黎第六大学Science d'Etat博士学位.1983年至1984年为University of Maryland的客座研究员，1984年至1986年为法国INRIA的Robot Vision Group的客座研究员，现为中国科学院自动化所所长.主要研究领域为计算机视觉、神经计算和基于传感器的机器人控制.
作者单位：(中国科学院自动化所模式识别国家重点实验室　北京　100080)
参考文献
　1　Hough P V C.A method and means for recognizing complex patterns,U.S.Patent 3,069,654,1962
　2　Duda R D,Hart P E.Use of the Hough transform to detect lines and curves in pictures.CACM，1972,15(1):11-15
　3　Ballard D H.Generalizing the Hough transform to detect arbitrary shapes.Pattern Recognition,1981,13(2):111-122
　4　Maitre H. Contribution to the prediction of performances of the Hough transform.IEEE T-PAMI,1986,8(5):669-674
　5　Hu Z,Destine J.Performance comparison of line Parameterizations.In:Proceedings,11th International Conference on Pattern Recognition,1992,3:335-338
　6　Biland H P.The recognition of three-dimensional polyhedral scene by analysis of Hough space structures［Ph.D.thesis］.ETH,Zrich:Swiss Federal Institute of Technology Zurich,1987
　7　Risse T.Hough transform for line recognition:complexity of evidence accumulation and cluster detection.CVGIP,1989,46:327-345
　8　Hu Z,Ma S D.Three conditions of a good line parameterization.Patter Recognition Letters,1995,16:385-388
　9　Hu Z,Ma S D.Uniform line parameterization.Pattern Recognition Letters,1996，17：503—507
　10　Aloimonos J,Weiss I,Bandyopadhyay A.Active vision.Inter.J.of Computer Vision,1988,1(4):333-356
　11　Ballard D H,Brown C M.Principles of animate vision.CVGIP:Image understanding,1992,52(51):3-21
　12　Swain M J,Stricker M A.Promisig directions in active vision,edited.Inter.J.of Computer Vision,1993,11(2):109-126
　13　Koshimizu H,Numada M,Murakami K.Askant vision architecture using warp model of Hough transform——for realizing dynamic & central/peripheral camera vision.Trans.IEICE.1994,E77-D(11):1206-1212
　14　Debusschere I,Bronckaers E,Claeys C,Kreider G,Van der Speigel J,Bellutti P,Soncini G,Dario P,Fantini F,Sandini G.A 2D retinal CCD sensor for fast 2D shape recognition and tracking.In:Proceedings,5th International Solid-State Sensor and Transducers,Montreux,1989
收稿日期　1997-01-27
