二维图像序列直线的提取及跟踪匹配研究

简宏伟,陈 震

摘 要:在基于直线光流场的三维重建研究中首先要对连续多帧单目图像序列进行处理,主要是二维图像直线的提取、跟踪及匹配。在此利用改进的Hough变换对图像进行直线提取,利用Hough变换的点线对偶性,即可将对图像序列中的特征直线的跟踪与匹配问题转化为在参数空间(ρ,θ)中对特征点运动轨迹的参数估计,可以采用卡尔曼滤波器对运动目标进行初步跟踪,预测其大致位置,再通过建立模板与图像的匹配相关系数判定搜索到的特征点的精确坐标。实验结果表明,该方法取得了较好的实验结果。

关键词:边界算子;Hough变换;卡尔曼滤波器;模板

中图分类号:TN919文献标识码:A

文章编号:1004-373X(2009)20-066-03

Extraction and Tracking Match of 2-D Image Array Straight Line

JIAN Hongwei,CHEN Zhen

(College of Automation,Nanchang Hangkong University,Nanchang,330063,China)

Abstract:During the study of reconstructing 3D based on straight line optical flow,a sequence of monocular images should be processed first.Using improved Hough transform to extract lines,and a tracking characteristic lines method which is based on Hough transform is presented.Rather than tracking lines in image space directly,the method makes use of duality theory in Hough transform in order to transform line-tracking in image space into point-tracking in Hough space.The first step designing is adopting Kalman filter to preliminary track the motion target,then accurate characteristic point location is searched by using build-up modeling board and image matching correlation modulus.Experiment result using composed image array shows that the presented method provides a good estimation of the characteristic lines tracking.

Keywords:boundary operator;Hough transform;Kalman filter;modeling board

点和线是计算机视觉中最常用到的视觉特征,通常图像特征抽象的层次越高,越有利于图像的处理与分析,为了更好地进行三维重建,非常有必要提高图像特征的抽象层次,即将点级别提高到线级别。在计算机视觉和图像处理领域,直线特征相比于点特征提供了更多场景结构信息[1],并能够很稳健地检测和跟踪感兴趣的直线特征。

1 Hough变换提取直线的改进方法

1972年Duda和Hart提出利用Hough变换提取直线,Hough变换法提取直线是一种变换域提取直线的方法[2],利用线-点的对偶性,把直线上点的坐标变换到通过该点的直线的系数域[3],利用了共线和直线相交的关系[4],使直线的提取问题转化为计数问题[5]。Hough变换在直线提取方法中拥有众多优点的同时也存在着一些缺点,如需要较大的存储空间和较长的计算时间[6,7]。针对这一缺点,这里采取一种Hough变换提取直线的改进方法。

由几何原理可知,平面上任意两点可以确定一条直线的参数(ρ,θ),则可令直线上的两点坐标为(x1,y1)和(x2,y2),那么:

ρ=x2cos θ+y2sin θ

θ=-tan-1[(x2-x1)/(y2-y1)](1)

对于每一个非零点,在其较小的邻域中,计算其他非零点与该点所确定的直线参数并在相应参数区间投票表决,统计出投票数最多的参数区间,以该参数作为直线参数[8],然后根据此参数在全图范围内搜索直线上的其他点,提高算法的鲁棒性。

改进算法的具体实现步骤如下:

(1) 在图像中顺序搜索,直到检测到图像中的一个非零点P,将该点作为一个参考点;

(2) 选取以P点为起始点的一个M×M区域Ap。在Ap中搜索其他的非零点,并根据式(1)计算每个非零点pi与P点所属直线的参数对(ρi,θi);

(3) 令ρ的偏差范围为Δρ,θ的偏差范围为Δθ。在Ap内进行投票表决,统计落入每个(ρ+Δρ,θ+Δθ)参数区间的参数对的个数ni;

(4) 找出Ap中最多的得票数的参数区间nmax,并对所有落入该区间的(ρi,θi)取均值,以减少量化误差的影响,得到(,),以此作为在Ap内通过P点的直线的参数;

(5) 令T1为Ap内直线长度阈值,若nmax>T1,则转到步骤(6),搜索属于该直线的其他点;否则认为过P点的直线不存在,将P点灰度清为零,转到步骤(1),重新开始搜索;

(6) 将搜索范围扩展至全图,对检测到的每个非零点,令=,若-<Δρ,则认为属于该直线,将其投票数进行累加,并将该点的灰度置为0;

(7) 全图搜索完毕,若直线的投票数大于设定阈值T2,则认为直线存在,否则认为直线不存在;

(8) 将P点灰度清零,返回步骤(1),重新搜索,直到图像中不再有非零点时结束。

2 二维图像序列直线的跟踪及匹配

由Hough变换提取直线的过程可以看到,图像平面中的直线和Hough空间中对应的点具备点线对偶性。这样就可以利用Hough变换的点线对偶性原理,将对图像平面中特征直线的跟踪问题转化为对Hough空间中特征点的跟踪问题[9]。

1960年,Kalman提出了离散系统Kalman滤波[10],后来他把这一滤波方法推广到连续时间系统中去。卡尔曼滤波器是常用预测、跟踪工具。卡尔曼滤波算法为最优化的自回归数据处理,它可以根据过去时刻积累的信息,预测当前时刻目标的粗略位置,为精确定位目标提供依据。

在此针对Hough空间特征点的跟踪估计,可设一个特征点的运动轨迹由三次多项式来描述,定义状态向量为下列一个六维向量X=[p,,],其中点P在Hough空间位置坐标为P=(ρ,θ)T,状态方程为:

X(k|k-1)=FX(k-1|k-1)+W(k|k-1)

式中:X(k|k-1)是利用上一状态预测的结果:

F=I2I2T12I2T

02I2I2T

0202I2

式中:I2为2×2单位矩阵;02为2×2零矩阵;T为相邻两帧的时间间隔;X(k-1|k-1)是上一状态最优的结果,因为没有状态的控制量,所以U(k|k-1)为0。

而在Hough空间中仅能观测到特征点的坐标位置,所以,观测方程可以表达为:

Z(k)=HX(k)+V(k)

式中,H=[I2,02,02]是一个2×6维的矩阵。

因为状态方程和观测方程都是线性的,可以直接应用标准的Kalman滤波器来实现对Hough空间特征点的跟踪。

Kalman滤波器跟踪Hough空间特征点的实现步骤:

(1) 利用系统的状态模型预测下一状态的系统。在Hough空间中预测运动目标特征点的状态向量。

X(k|k-1)=FX(k-1|k-1)(2)

(2) 特征点状态向量协方差矩阵P(k)的预测和Kalman增益矩阵Kg(k)的计算。

P(k|k-1)=FP(k-1|k-1)FT+Q(3)

Kg(k)=P(k|k-1)HT/[HP(k|k-1)HT+R](4)

式(3)中:P(k|k-1)是X(k|k-1)对应的协方差,P(k-1|k-1)是X(k-1|k-1)对应的协方差;式(2),式(3)是对系统的预测。

(3) 由Hough空间特征点的观测值(ρ,θ)和预测值来更新运动目标特征点的状态向量方程,从而可以得到现在状态的最优化估算值X(k|k)。

X(k|k)=X(k|k-1)+Kg(k)[Z(k)-

HX(k|k-1)]

(4) 由上面三个步骤已经得到最优的估算值X(k|k),但是为了要令Kalman滤波器不断地运行下去,直到系统过程结束,就要更新X(k|k)的协方差P(k|k)。

P(k|k)=[I-Kg(k)H]P(k|k-1)

式中:I为单位矩阵。当系统进入(k+1)状态时,P(k|k)就是式(3)中的P(k-1|k-1)。

依据上述四个步骤,当测量误差协方差阵和状态噪声协方差阵不够准确时,滤波结果存在较大误差,甚至有时滤波器会发散或振荡,所以由Kalman滤波器跟踪预测到运动特征点的位置为粗略位置,为了得到点的精确坐标,可以以该点位置为中心,采取匹配相关算法搜索跟踪结果。

匹配相关算法是以设某一匹配模板为模板图像中以特征点为中心的一个M×N的小区域M(i,j),定义模板与当前图像帧在点(m,n)处的归一化相关系数为:

R(m,n)=C(m,n)C1(m,n)×C2(m,n)(5)

式(5)中:C(m,n)为模板与图像相关系数;C1(m,n)为模板M(i,j)的自相关系数;C2(m,n)为当前图像帧在以像素点(m,n)处为中心的M×N范围内的自相关系数。

其中R(m,n)的取值范围为[0,1],最优搜索匹配位置就是使归一化相关系数R(m,n)最大的那个位置,即是当前图像帧中该特征点的最优跟踪测量位置点。

3 实验与结果

实验对象为合成立方实体运动图像序列。利用计算机辅助设计软件Swift 3D生成立方实体模型。将该模型以给定的、很小的旋转和平移量在3D空间运动,获取其连续图像序列,如图1所示。分别为连续运动图像序列的第一帧及其直线检测图像,利用该文的方法检测连续图像中的特征直线及其匹配。

图1 合成立方体及其直线检测图像

对图像序列的连续三帧图像进行滤波,并采用Canny算子进行边缘检测,采用Hough变换提取直线的改进方法对图像进行直线提取,将直线的方程表示成法线式,得到各条直线的Hough空间坐标ρ和θ,将各条直线连续三帧的Hough空间坐标映射到Hough空间上。将获取的Hough空间图像采用卡尔曼滤波算法,估计Hough空间中特征点运动的轨迹参数,得到预测点的粗略位置,存储各位置坐标,利用匹配模板在以预测点为中心的小区域搜索,按式(5)计算出各个位置的归一化相关系数R(m,n),记录R(m,n)为最大值的点,即为这两帧中匹配的特征点,也就是相应连续图像平面中匹配的直线。该次实验中共匹配到如表1所示的1~11条直线参数坐标。

表1 合成立文体的直线提取及跟踪匹配结果

直线编号第一帧(ρ,θ)第二帧(ρ,θ)第三帧(ρ,θ)

1-100.355 9-1.57-100.355 9-1.57-100.355 9-1.57

2-138.491 1-1.134 5-137.487 5-1.134 5-136.484 0-1.134 5

341.145 9-1.134 544.156 6-1.11747.167 3-1.099 6

4189.672 60.017 5187.665 50.017 5183.651 20

5169.601 40.261 8173.615 70.209 4176.626 30.157 1

675.266 90.261 888.313 20.331 698.348 80.366 5

7222.791.134 5223.793 61.117224.797 21.117

823.081 9-0.261 823.081 9-0.331 625.089 0-0.384

944.156 61.11744.156 61.134 546.163 71.117

10-58.206 4-0.541 1-72.256 2-0.645 8-81.288 3-0.715 6

11115.409 3-0.279 3129.459 1-0.226 9145.516 0-0.157 1

4 结 语

在此利用Hough变换提取直线的改进方法,提高了Hough变换提取直线的精度,并且利用Hough变换的点线对偶性,将对图像序列中的特征直线的匹配转化为在参数空间(ρ,θ)中对特征点运动轨迹的参数估计,设计采用卡尔曼滤波器对运动目标进行初步预测估计,通过建立模板与图像的匹配相关系数,便可搜索判定参数空间特征点的精确坐标,即图像空间中匹配的直线。

实验结果表明该方法取得了较好的直线提取和匹配效果,可应用于基于直线运动的三维物体运动和结构重建的研究中。

参考文献

[1]马颂德,张正友.计算机视觉计算理论与算法基础[M].北京:科学出版社,1998.

[2]陈海峰.数字图像中基本几何形状检测算法的研究与应用[D].杭州:浙江大学,2007.

[3]许强,陈震.图像序列直线提取和匹配时Hough变换的应用研究[J].南昌航空工业学院学报:自然科学版,2007,21(1):43-47.

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

[5]Mieghem J A V,Avi-Itzhak H I,Melen R D.Straight Line Extraction Using Iterative Total Least Squares Methods[J].Journal of Visual Communication and Image Representation,1995,6(1):59-68.

[6]杨顺辽.基于Hough变换提取直线的改进方法研究[J].电脑与信息技术,2006,14(5):29-31.

[7]杨顺辽.弗里曼链码法在图像处理中的应用[J].中国水运:理论版,2006,4(1):23-25.

[8]JeongHun Jang,KiSang Hong.Fast Line Segment Grouping Method for Finding Globally more Favorable Line Segments[J].Pattern Recognition,2002,35:2 235-2 247.

[9]陈震,高满屯,杨声云.基于Hough变换的直线跟踪方法[J].计算机应用,2003,23(10):30-32.

[10]Kalman R E.A New Approach to Linear filtering and Prediction Theory[J].Transactions of the ASME-Journal of Basic Engineering,1960(82):35-45.

[11]董梁.基于哈夫变换的图像边缘连接[J].现代电子技术,2008,31(18):149-150,156.