基于改进扫描线逼近的鱼眼图轮廓提取算法的研究

韩迎辉

(常州大学城常州轻工职业技术学院，江苏常州213164)

为了获得超宽视角，鱼眼镜头被大量地应用在群组视频会议［1］、大范围监控系统、智能交系统、虚拟实景技术［2］，全景浏览及球面电影等领域。鱼眼镜头可以克服普通镜头视场小的缺点，但是鱼眼图像具有严重的桶形畸变，在利用鱼眼图像信息之前需要对鱼眼图像进行校正展开。

目前鱼眼图像轮廓提取的算法主要有最小二乘拟合法，面积统计法，区域增长法和扫描线逼近法。最小二乘拟合法［3］提取鱼眼轮廓的计算量大并且不一定精确。面积统计法［4］原理简单但是当有效区域内特别是靠近轮廓有大量黑色像素点存在时计算误差偏大，而且计算量相对较大，因此适用范围也有限。区域增长法［5］计算复杂，耗时长，且不一定能够取得理想结果，更不实用。相比之下，扫描线逼近算法［6-8］的效率最高，效果也比较好，应用广泛，但仍具有抗噪能力差的缺陷，有些轮廓提取效果还可以提升。本文在已有的扫描线逼近算法的基础上提出了一种新的鱼眼轮廓提取算法，该算法有很强的抗噪能力，能够精确定位鱼眼图像的中心和半径，在提高鱼眼轮廓提取精度的同时能够保证不增加运行时间，具有很强的实用价值。

1 传统的扫描线逼近算法

图1是一张鱼眼镜头拍摄的图像，从图中可以看出鱼眼图像具有很严重的桶形畸变，要想利用鱼眼图像的信息(除了艺术欣赏)就要对鱼眼图像进行校正展开。鱼眼图像的特点是中间圆形区域是图像涵盖物景信息的有效区域，四周是黑色的背景部分。在进行鱼眼图像校正之前首先要把鱼眼图像的有效区域提取出来，为后续的鱼眼图像校正做准备。所以说鱼眼图像轮廓的提取效果在鱼眼图像的校正过程中非常重要，常常直接影响图像的校正结果。

图1 鱼眼图像

极限亮度差是指图像中某一行或列的各像素点的最大亮度和最小亮度之间的差值。根据鱼眼图像的特点可知，图像的全部物景信息都包含在圆形有效区域里，有效区域里像素的亮度值比有效区域外的像素要大得多，扫描线逼近算法就是根据这一特点提出的算法。

既然鱼眼图像的有效区域是圆形的，那么这个圆必然存在一外切正方形，扫描线逼近算法首先求出这个外切正方形进而再求出圆形的中心坐标和半径。如图2所示，从鱼眼图像的上下左右四个方位分别建立一条扫描线，从周围向中心扫描逼近。在圆形有效区域外部，大多是黑色像素点，各像素的亮度值很小，所以扫描线对应的极限亮度差很小，但是当扫描线进入有效区域时，由于物景像素点的增多，扫描线的极限亮度差很大。当扫描线贴近圆形轮廓时极限亮度差剧增，如扫描线left2有一个很大的跳跃值存在，我们可以设一个阈值，当差值大于这个阈值时，我们就认定扫描线到达了鱼眼图像的轮廓边上了，这条直线对应的位置就是鱼眼图像圆形轮廓的一条切线。

图2 扫描线逼近算法扫描示意图

算法的具体步骤为:

首先设定一亮度阈值T，从鱼眼图像的四周开始，建立四条扫描线，像中心逼近扫描。鱼眼图像一般为彩色的RGB图像，我们首先根据红R，绿G，蓝B信息得到该像素对应的亮度值，图像像素亮度公式为［7］:

极限亮度差:

其中Imax、Imin分别是扫描中确立的该行或该列的最大和最小亮度值。当Ilim大于设定的阈值T时，则Imax对应的点就是鱼眼图像轮廓上的点，立即停止该方向的扫描。四个方位都扫描完毕时，在理想情况下将得到圆形的外切正方形，那么鱼眼图像的中心坐标和半径分别为:

理想情况下Rx=Ry，但是当鱼眼图像轮廓附近有比较多的黑色像素时，会导致扫描线定位有偏差，那么得到的外切正方形将畸变成长方形，这时我们可以取两者的平均值作为半径。

扫描线逼近算法解决了面积统计法存在的一个问题，即当有效区域内含有像素值比较小的像素点比较多，仍能取得精确的计算结果，但是当大量黑色像素点存在于轮廓边缘时，特别是存在与四条扫描线的切点附近时扫描线逼近算法计算结果也有偏差。

图3 新的扫描方案示意图

2 改进的扫描线逼近算法

2.1 引入扫描步长建立新的扫描方案

从上节可知，扫描线逼近算法是逐行逐列进行扫描的，当鱼眼图像有效区域比较小，而黑色背景比较大时，扫描到鱼眼轮廓边缘需要很长时间，扫描效率低下，针对此，本文建立新的扫描方案，引入扫描步长λ，即前后两次扫描跳跃的行或列值。如图3所示，以左方向扫描为例，扫描线lefti和lefti+1是前后两次扫描，但是第lefti+1次扫描的列值比lefti次扫描大λ。当lefti扫描线未进入鱼眼图像有效区域时，则以步长λ进入下一次扫描，记为lefti+1。当lefti+1进入有效区域时，则下一次扫描以步长为1逐列退回扫描，记为lefti+2，就这样一直退回扫描到鱼眼轮廓边界为止。

2.2 扫描阈值的选取

扫描线逼近算法用的是固定阈值，阈值的选取对算法的结果有一定的影响，特别是对于扫描线逼近算法来说，阈值选取过小，会把噪点当做边缘，造成计算半径过大，阈值选取过大有可能错过边缘点，使半径偏小。本论文针对固定阈值的缺陷，根据不同的鱼眼图像采用自动阈值。

一般来说鱼眼图像四周或多或少都存在亮度很低的黑色区域，本文称为背景部分。一般数码相机噪声点的灰度大部分小于30，因此鱼眼图像背景区域绝大部分亮度值也小于30［9］，本文就以30为参考值对阈值进行如下方法设置:首先设定一较小的整数值M，数值在10以下均可。然后取图像四周最外层的M行M列的像素值，按式(1)计算亮度，然后计算亮度平均值记为Tm，则阈值T为:

其中N为一正整数，本文取为20。本文这样设置阈值T的目的是防止鱼眼图像黑色区域的亮度过大，而固定阈值30太小不适用于某些鱼眼图像。而且这样设定阈值还能在一能程度上抑制噪声点对扫描算法的干扰。

2.3 局部二值化去除噪声原理

扫描线逼近算法对噪声的干扰比较敏感，比如背景部分的椒盐噪声点，或者亮度较高像素点。容易想到的一个解决方案就是在轮廓提取之前对鱼眼图像进行滤波去噪处理，如中值滤波，均值滤波，高斯滤波等，其中中值滤波处理对椒盐噪声的处理效果最好［10］。但是对鱼眼图像进行滤波处理必定会影响鱼眼图像轮廓的提取速度，而且在鱼眼图像轮廓提取阶段对鱼眼图像有效区域内的像素信息进行滤波也是不必要的，因此不宜采用滤波处理。

在扫描线逼近算法中，当扫描线扫描到噪声点时，亮度差超过了设定的阈值，算法误认为扫描到了轮廓边界，针对此我们可以在对取得最大亮度的那个点进行定位然后判断此点是否噪声点，如何区分此点是噪声点还是正常点是本节研究的重点。

鱼眼图像有效区域里的图像像素亮度值比黑色背景部分要大很多，因此可以通过二值化将有效区域和背景部分分割出来，但是由于有效区域里也会含有像素亮度值比较小的点，因此不可能将二者完全分离出来。但是相邻像素之间是存在一定关联性的，可以根据它来区分二值化后黑色像素点是属于有效区域的还是背景部分，区域增长法就是利用这个原理来提取鱼眼图像的轮廓的。

根据相邻像素之间的关系可以对黑色像素点这样进行判别，如图4所示，点q在圆O外，U(q)是q的任意一个邻域(矩形邻域亦可)。在U(q)中，属于圆O的区域为in，面积记为Si;不属于圆O的区域为 out，面积记为So。由此可得:Hi的面积小于U(q)面积的1/2，即Si/(Si+So)＜0.5;反之，如果点q在圆O内，就有Si/(Si+So)＞0.5。

图4 像素点邻域特性

一般来说，二值化过后的邻域内黑色像素点比邻域内白色像素点要多时，可以认为该黑色的像素点是属于背景部分的，否则认为是有效区域的。本文也将利用取得最大亮度差的点的邻域特性来判断该点是不是噪声点。邻域可选用圆形邻域或者矩形邻域，如图5所示。噪声点的特性就是与周围点像素值差别太大，而针对本文，取得最大亮度差的那个点如果是噪声点的话，像素值必定比邻域内其他的点大。因此可以对取得极限亮度差的点某个邻域内的所有点用上小节的阈值进行局部二值化，然后计算邻域内白色像素点所占的比例(记为S)的大小，若大于某一阈值(记为Ts)如0.5，可断定此点不是噪声点，否则就是噪声点，应该继续进行扫描。

图5 像素点的两种邻域

2.4 算法流程图

本文提出的新的鱼眼图像轮廓提取算法的流程图如图6所示。

算法的具体步骤如下:

(1)按式(5)计算亮度阈值T。

(2)以左侧扫描为例，以步长λ进行扫描，若极限亮度差小于T则继续以步长λ扫描。

图6 鱼眼轮廓提取流程图

(3)否则暂停扫描，定位取得极限亮度差的像素点。

(4)按照3.3节所描述的方式对该像素点进行局部二值化，计算比例S，若S小于设定的阈值Ts说明此点是噪声点，应继续以步长λ前进扫描。

(5)若S大于设定的阈值Ts，说明扫描到了轮廓的边界点，立即停止前进扫描，以步长1也就是逐列退回向左进行扫描，直到扫描到轮廓边界为止。

值得注意的是，逐列退回扫描时要一直后退直扫描到轮廓边界外的那一列，才能断定已经扫描到了轮廓边界，这一点未在流程图中体现出来，务必要注意。

3 实验结果与分析

本节将给出本文提出的改进的扫描线逼近算法与原算法性能的对比，本文算法的测试环境为:Windows XP sp3 Intel(R)Pentinum(R)Dual CPU 1.46 GHz，1 GB内存，MATLAB 7.4。共选用8幅鱼眼图像进行测试，数据如表1和表2所示，其中圆心坐标和半径是算法计算得到的，误差是与的标准值相比得到的，而标准值则是手工测量获得的。图1的鱼眼图像(对应图像序号为3)的轮廓提取结果对比如图7所示。

图7 鱼眼图像轮廓提取对比图

从图7可以看出改进算法提取的轮廓比原算法更精确，图7(a)出现的偏差是由图像右边的白色噪点引起的，右侧的扫描线扫到此行时由于噪声点的存在使极限亮度差大于设定的阈值，认为扫描到了边界。

表1 扫描线逼近法实验结果数据

表2 本文提出的改进扫描线逼近法实验结果数据

相比的扫描线逼近算法，本文提出的改进的扫描线逼近算法取得了很好的效果。由于本文引入局部二值化的去噪思想，使得含噪声图像(对应序号为3)的提取效果改善很多。详细的对比情况如图8所示，圆圈代表本文提出的改进算法的圆心坐标误差，十字代表原扫描线逼近算法，显而易见本文提出的算法提取的圆心坐标误差更小。参照表1和表2的数据，本文提出的改进算法的半径平均误差为0.91，而原扫描线逼近算法的半径平均误差为1.09，可见本文提出的算法效果更好。

图8 改进前后扫描线逼近算法提取圆心坐标误差

表2中算法运行时间包括扫描步长为5和1的结果，结合表1中原算法运行时间，绘制时间曲线如图9。当步长为5时算法运行时间最小，而且大部分小于原算法的运行时间。当改进算法不引入步长扫描时，即步长为1时算法的运行时间较长，因此说明本文引入的步长扫描能够有效地改进算法的运行时间。

图9 改进前后扫描线逼近算法的运行时间对比曲线

4 结论

本文针对扫描线逼近算法在提取鱼眼图像轮廓时具有抗噪能力差的缺点，提出改进的扫描线算法，提取的改进算法由于引进新的阈值计算方法和局部二值化去噪思想能够很好地抑制噪声，有效改善鱼眼图像轮廓的提取效果，而新的扫描方案，即按步长λ扫描的方案能够缩短算法的运行时间，提高了计算效率。因此本文提取的算法具有更精确的效果，更短的运行时间，具有很强的实时性和实用价值。

［1］Yang R G，Brownt M S，Sealest W B.Geometrically Correct Imagery for Teleconferencing，Orlando，ACM Multimedia’99，1999(1):179-186.

［2］Xiong Y，Turkowski K.Creating Image-Based VR Using a Self-Calibrating Fisheye Lens［C］//IEEE Computer Society Conference on Computer Vision and Pattern Recognition(CVPR’97)，San Juan，Puerto Rico，1997，6:237-243.

［3］吴方，王霞.鱼眼镜头图像变形校正算法研究［J］.计算机科学，2009，36(4B):109-111.

［4］Szeliski R.Video Mosaics for Virtual Environment［J］.IEEE Computer Graphics and Applications，1996，16(2):22-30.

［5］杨丹，游磊，张小洪，等.基于区域生长的鱼眼图像轮廓提取算法［J］.计算机工程，2010，36(8):217-218.

［6］王大宇，崔汉国，陈军.鱼眼图像轮廓提取及校正研究［J］.计算机工与设计，2007，28(6):2878-2879.

［7］崔汉国，陈军，王大宇.基于鱼眼图像的虚拟漫游研究［J］.系统仿真学报，2007，9(5):1504-1506.

［8］Li S G，Nakano M，Chiba N.Acquisition of Spherical Image by Fish-Eye Conversion Lens［J］.IEEE Computer Society，2004:235-236.

［9］肖诗勤，杨关良.一种改进的鱼眼图像轮廓提取算法［J］.计算机与数字工程，2010，38(1):147-150.

［10］贾永红.数字图像处理［M］.武汉:武汉大学出版社，2003:77-78.