基于卡尔曼预测的序列图像椭圆检测算法

赵江涛，张东亮，张锁平，齐占辉

（国家海洋技术中心 天津 300112）

图像平面上点、直线以及二次曲线的检测是图像处理、模式识别及机器视觉等领域的重要研究内容。圆形目标是现实生活中极为常见的目标，由于透视投影变换圆在图像坐标系蜕变为椭圆，快速鲁棒的椭圆曲线提取有重要的意义。寻找一种快速、鲁棒、精确的椭圆检测算法一直是相关领域研究热点。目前常用的椭圆检测算法主要有最小二乘拟合法[1]、Hough变换法[2]以及基于椭圆几何特征的算法[3]等。最小二乘拟合方法是椭圆拟合中最为常用的方法，该方法直观、简单、实时性好并且可以达到较高的拟合精度，能够应用于各种复杂的对象模型。目前大多数的椭圆检测算法所针对的是静态图像，对序列图像中动态椭圆目标的实时检测研究较少。在笔者所研究的计算机视觉测量系统中，需要对序列图像中的椭圆目标予以检测及识别，通过分析各帧图像中椭圆目标的中心位置、长短轴等参数对目标的运动参数（位置、速度、姿态）予以估计。实验证明：本方法可以实现序列图像中椭圆目标的快速、鲁棒检测。

1 序列图像中椭圆检测算法

在二维平面上，椭圆和其他二次曲线方的一般形式可以描述为：

当上式中的参数满A2－4B<0时，该方程表示的是椭圆方程。另一种更直观的椭圆表示方式是椭圆几何参数法，假设椭圆的中心为（uc，vc），长轴和短轴分别为（2a 2b），椭圆长轴与坐标系横轴的夹角为θ，可以利用式（2）～（6）将椭圆的一般式转换成几何参数表示形式。

随机抽样一致性算法[4]RANSAC（RANdom SAmple Consensus）是一种鲁棒性的模型估计算法，基于RANSAC的改进的最小二乘椭圆拟合算法[5]能有效剔除错误样本点的影响。对于序列图像中的单帧图像经边缘检测后，边缘二值图像除包含待检测椭圆的边缘信息之外还包含大量的伪边缘及其他干扰信息，分别对边缘拟合之后会得到多个椭圆目标，有必要利用先验知识对拟合得到的椭圆进行筛选。用以下步骤对序列图像中的椭圆目标予以检测，算法流程如图1所示。

1）根据上一帧图像中卡尔曼预测的结果设置本帧图像中椭圆待检测区域，使用Canny算子得到待检测区域的边缘点集；

2）利用边缘特征点的连通性将图像边缘分为不同的轮廓，选取轮廓，若轮廓点的个数大于，则使用基于RANSAC的改进最小二乘法拟合椭圆。否则，重新选取轮廓；

3）计算所拟合椭圆的椭圆率、拟合率以及面积，如果三者都满足阈值条件，则将拟合的椭圆记为本帧图像中的目标椭圆。否则，返回步骤2）重新选择轮廓；

4）返回步骤1）检测下一帧图像中的椭圆目标。

其中，卡尔曼滤波预测的相关内容在本文第二节予以介绍。椭圆率定义为λ=b/a，b为椭圆的短半轴，a为椭圆的长半轴，椭圆率描述了椭圆接近于圆的程度。拟合率定义为p=m/n，其中n为拟合椭圆所用轮廓边界的总点数，m为该边界上的点到拟合椭圆距离小于设定阈值的点集，拟合率描述了拟合椭圆所用轮廓与所得到椭圆之间的拟合程度。椭圆面积S=πab。可以根据先验知识及前期实验设定待检测椭圆的面积、椭圆率以及拟合率的阈值范围。

图1 椭圆检测流程Fig.1 Flow of ellipse detection

2 卡尔曼滤波预测椭圆搜索区域

对整幅图像进行椭圆检测需要较多的时间，如果能够对下一帧图像中椭圆的位置有预先粗略的估计，将椭圆的待检测区域限定在一个较小的范围内，可以减少算法所需要的存储空间和运行时间。另外，在全局范围内搜索椭圆目标使得算法的抗干扰能力也不理想。利用卡尔曼滤波器的预测功能来预测下一帧图像中待检测椭圆目标中心的位置，并设置下一帧图像中椭圆目标的大致搜索范围。通过这种方法大大减小了算法的运算量，保证了系统的实时性及鲁棒性。

2.1 卡尔曼预测器

卡尔曼预测器[6]实质上是一种递归预测算法，根据误差无偏最小方差原则预测目标下一时刻的运动状态。卡尔曼滤波可以划分为两个过程：时间更新和测量更新。时间更新方程用于向前预测下一时刻状态X （k）-及计算预测协方差P（k）-。测量更新方程用于估计当前时刻状态的最优值X（k），计算卡尔曼增益Kg（k）并更新最优值的协方差P（k）。在卡尔曼滤波器初始化后，通过图2中卡尔曼滤波的5个基本方程就可以保证算法自回归的运行下去。在利用卡尔曼滤波的预测功能时系统所输入的是k-1时刻系统状态的测量值Z（k-1），输出的是k时刻系统的预测值X（k）-。在没有控制输入的情况下Kalman滤波的递归运算过程如图2所示。

图2 卡尔曼滤波预测流程Fig.2 Flow of Kalman filter prediction

2.2 椭圆检测区域预测算法实现

考虑运动速度、加速度对椭圆中心位置预测的影响，使用三阶向量卡尔曼预测器对下一帧图像中的椭圆中心位置进行预测。为保证算法的实时性，设计了两个卡尔曼预测器分别跟踪椭圆中心在图像坐标系横轴和纵轴方向，将一个二维预测降为两个一维预测[7]，提高了算法的运行速率。假设目标物体运动的轨迹投影在一定时间间隔T内的加速度是常量，则：

上式中，yk-1、vk-1、ak-1分别表示 t=k-1时刻椭圆中心在图像坐标系纵轴方向上的位置、速度及加速度，T为两帧图像间的时间间隔。用示t=k时刻单个预测器的状态向量，则椭圆中心运动状态的系统方程可以写为：

系统量测方程为

上式中，C=[1 0 0]为量测矩阵，Z（k）为 t=k时刻所测量得到的椭圆中心在图像坐标系中纵轴方向的坐标，V（k）为测量噪声，其协方差矩阵为R。将基于卡尔曼滤波的椭圆中心位置预测算法描述为：

1）初始化卡尔曼滤波器，设置卡尔曼预测器的噪声方差Q和R，并给定状态初始值X（0）和对应协方差矩阵初始值 P（0）；

2）由时间更新方程并根据k-1时刻的最优估计值X（k-1）预测k时刻系统状态X（k）-，同时更新k时刻状态预测值的协方差 P（k）-，并将预测值 X（k）-作为系统的输出；

3）根据测量更新方程可以计算得到k时刻的卡尔曼增益Kg（k），输入k时刻的状态测量值Z（k）并结合k时刻状态预测值X（k）-可以得到 k时刻的最优估计值X（k）。计算k时刻最优估计值的协方差P（k），并返回步骤2）使算法自回归的运行下去。

假设由第k-1帧图像预测的第k帧图像中椭圆的中心坐标为（uc，vc），在 k-1帧计算的椭圆的长轴为 r，则将第 k帧图像中椭圆的待检测区域设置为以（uc，vc）为中心，以2（r-Tr）为边长的矩形区域[8]。图3中实线框为由卡尔曼滤波预测的下一帧图像中椭圆的待检测区域。其中，阈值可以根据目标椭圆运动情况进行调整，对于运动变化较快的目标可以适当增大，此时椭圆检测范围增大Tr，稳定性提高。由卡尔曼滤波的性质可知，滤波器初始化后的前几次预测并不可靠，此时应适当增大Tr保证算法的稳定性，经过若干帧跟踪之后，以较小的Tr即可保证待检测椭圆位于预测的检测区域内。

图3 卡尔曼预测椭圆区域Fig.3 Ellipse location prediction with kalman predictor

3 实验与分析

3.1 仿真实验

利用MATLAB生成含有噪声的标准椭圆边界点并添加部分错误点，分别利用最小二乘法和改进的方法拟合椭圆，两者检测结果如图4所示。由图可以看出由于样本点中含有一定比例的不属于待拟合椭圆边界的点集，最小二乘法所拟合椭圆并不准确，而基于RANSAC方法能排除这些错误点的干扰，准确的拟合出目标椭圆。

3.2 实际图像检测结果

图4 椭圆拟合结果Fig.4 Result of ellipse fitting

在序列图像动态椭圆目标检测实验中，对自由下落并反弹的球体的投影图像进行椭圆检测。所录制视频图像分辨率为320*240，帧频为20 frame/s，并设置待检测区域阈值Tr=30。图5为从该段序列图像中所截取的几帧图像，图像中的方形区域为通过卡尔曼滤波器所预测的椭圆待检测区域。各帧图像中所预测的方形区域边长最大不超过50像素，待检测区域的面积仅仅是全局图像面积的1/30，大大减小了下一帧图像中椭圆的搜索区域。在不同的实验状况下，可以根据目标运动的剧烈情况设置不同的Tr来保证椭圆目标位于待检测区域内。图5中的椭圆为按本文方法所拟合的椭圆曲线与原二值边缘图像叠加的结果。

图6为横向和纵向的卡尔曼预测结果及误差，从图6（a）和图6（c）可以看出经过几次迭代之后，卡尔曼滤波器在两个方向上都可以准确预测出下一帧图像中椭圆中心的实际位置。图6（b）和图6（d）也表明滤波器可以较为准确的预测出下一帧图像中椭圆目标的中心位置，最大预测误差在20个像素之内。通过卡尔曼滤波预测可以较为准确的预测下一帧图像中椭圆目标的待检测区域。

4 结 论

为实现对序列图像中的动态椭圆实时检测，结合RANSAC算法和最小二乘法设计了鲁棒性的椭圆检测流程，能有效剔除椭圆拟合过程中干扰边缘和噪声点的影响。序列图像中椭圆目标的检测对系统的运算速度要求较高，采用卡尔曼滤波预测能够充分的利用历史信息，缩小下一帧图像中对待检测椭圆目标的搜索区域，提高了系统的运算速度和稳定性。此外，当在某一帧图像中未能检测出椭圆目标时可以根据预测结果继续对下一帧图像中的椭圆进行检测，提高了系统的可靠性。目前已成功将该算法应用于所开发的水下目标运动参数视觉测量系统中，取得了令人满意的效果。

[1]邹益民，汪渤.一种基于最小二乘的不完整椭圆拟合算法[J].仪器仪表学报，2006，27（7）:809-810.ZOU Yi-min，WAN Bo.Fragmental ellipse fitting based on least square algorithm[J].Chinese Journal of Scientific Instrument，2006，27（7）:809-810.

[2]袁立，叶露，贾建禄.基于Hough变换的椭圆检测算法[J].中国光学与应用光学，2010，3（4）:380-382.YUAN Li，YE Lu，JIA Jian-lu.Ellipse detection algorithm based on hough transform[J].Chinese Journal of Optics and Applied Optics，2010，3（4）:380-382.

[3]于海滨，刘济林.基于中心提取的RHT在椭圆检测中的应用[J].计算机辅助设计与图形学学报，2007，19（9）:1108-1112.YU Hai-bin，LIU Ji-lin.Ellipse detection by the RHT based on center extraction[J].Hournal of Computer-Aided Desigh&Computer Graphics，2007，19（9）:1108-1112.

[4]Fischler M A，Bolles R C.Random sample consensus:a paradigm for model fitting with applications to image analysis and automated cartography[J].Graphics and Image Processing，1981，24（6）:381-383.

[5]闫蓓，王斌，李媛.基于最小二乘法的椭圆拟合改进算法[J].北京航空航天大学学报，2008，34（3）:295-298.YAN Pei，WANG Bin，LI Yuan.Optimal ellipse fitting method based on least-square principle[J].Journal of Beijing University of Aeronautics and Astronautics，2008，34 （3）:295-298.

[6]郝利云，吴玲达.基于卡尔曼预测器的数据预取方法[J].计算机仿真，2012，29（10）:10-12.HAO Li-yun，WU Ling-da.Kalman predictor based data perfecting method[J].Computer Simulation，2012，29（10）:10-12.

[7] 姚红阁，耿军雪. 基于卡尔曼预测的视频目标实时跟踪[J].西安工业大学学报，2007，27（2）:174.YAO Hong-ge，GENG Jun-xue. A real-time tracking for videotarget based on kalman prediction[J]. Journal of Xi’an TechnoloficalUniversity，2007，27（2）:174.

[8] 王忠立，高文. 基于最小二乘预测的动态快速椭圆检测[J].信息与控制，2003，32（7）:732.WANG Zhong-li，GAO Wen. Dynamic fast ellipse detectionbased on location prediction with least square[J]. Informationand Control，2003，32（7）:732.