分割线扫描鱼眼图像有效区域提取算法

程德强，刘 洋，柳 雪，赵 国，张佳琳

（中国矿业大学 信息与电气工程学院，江苏 徐州 221000）

分割线扫描鱼眼图像有效区域提取算法

程德强，刘 洋，柳 雪，赵 国，张佳琳

（中国矿业大学 信息与电气工程学院，江苏 徐州 221000）

对于超大广角鱼眼图像的校正，关键是必须准确地提取出鱼眼图像的有效区域，并且同时确定有效区域的中心和半径。现有的鱼眼镜头校正算法针对高清鱼眼视频监控有一定的不足，因此为满足高清鱼眼视频监控的高分辨率需求，在现有算法的基础上提出一种分割线扫描算法。该算法首先划定一条特定水平分割线，由此寻找最接近边界线的范围区域，减少不必要像素点的检测，然后在此区域内精确寻找有效区域边界线。经实验表明，该算法在不降低提取精度的同时，可以显著降低鱼眼图像有效区域提取的时间复杂度和计算量，将以往算法的200万计算量降低到万量级以下。

鱼眼镜头；轮廓提取；分割线扫描

1 鱼眼图像研究

随着信号处理和图像处理技术的发展，基于鱼眼全景监控摄像头的视觉处理技术得到快速发展，中国已于2013年底发射“嫦娥三号”，搭载的“玉兔号”月球车所配备的就是全景摄像头，拍摄的全景图和展开图如图1所示。另外，鱼眼镜头还广泛应用于全景安全监控、地铁走廊监控等长距离和大场地空间，相较一般的摄像头，其视场角接近于180°甚至超过180°，所以相比普通镜头，鱼眼镜头能够拍摄到更大场景画面，获取到更多的空间信息。为了捕获更多的信息，目前高清鱼眼镜头也得到了广泛应用，它所获得的图像对校正有着更高的要求，图2是1 080p高清鱼眼镜头所拍摄的鱼眼图像，分辨率达到1 920×1 280，单帧图像像素点数目高达250万。当镜头的视场角由几十度提高到180°时，图像将产生严重畸变[1]，所以对校正的时间复杂度和计算量有很大的挑战。

针对鱼眼大广角畸变图像的校正研究，目前也已经相当成熟，鱼眼图像校正的关键在于准确提取出鱼眼图像的有效区域，同时确定出有效区域的中心和半径。本文主要研究针对高清鱼眼镜头的实时视频监控，提出的算法可以在不降低提取精度的同时，显著降低鱼眼图像有效区域提取的时间复杂度和计算量，将以往算法[2-6]的200万计算量降低到万量级以下。

图1 玉兔号拍摄的全景图及校正图

图2 高清鱼眼镜头拍摄的鱼眼图像

2 鱼眼图像校正原理

针对鱼眼图像校正模型的研究，主要有基于经度坐标的校正模型、等距投影校正模型、球面透视投影模型和基于内容的校正模型，但是对于超过180°的超大广角鱼眼镜头，一般目前应用最多的是球面透视投影模型，文献[2]提出一种透视投影模型，空间点到鱼眼图像点的坐标变换不是简单的线性转换，且给出如下流程[2]：第一步，建立空间点P与球面中心圆点的关系，即向量OP；第二步，通过向量OP得到空间点P与球面模型映射点的关系；第三步，通过模型计算得到球面点与投影点的关系。

如图3所示，球面上的点与投影点保持一一映射的关系，这种投影关系可以由m=D（p）来表示；反之，为了逆向得到校正输出点，通过p=D-1（m）即可得到，通过这种映射关系，就可以实现对畸变图像的校正。

图3 鱼眼校正模型

3 鱼眼图像的有效区域提取

3.1 算法原理

根据鱼眼图像的特征，相比较黑色像素部分，有效区域基本占据了整幅鱼眼图像的大部分区域，目前对于鱼眼畸变图像的有效提取主要有4种算法：最小二乘拟合算法[3]、面积统计算法[4]、区域生长算法[5]和逐行逐列扫描线[6]算法。其中最小二乘拟合算法和面积统计算法由于是对整幅鱼眼畸变图像的所有像素点进行扫描判断，因此其时间复杂度和空间复杂度都要比逐行逐列扫描线算法要高，故在实际应用中，应用最广的也是算法最成熟的是逐行逐列扫描线算法。当对高清图像进行处理时，单帧像素点数目高达250万，即使是应用最多的逐行逐列扫描线算法，有效计算量一般也在百万次以上，计算量相当大。为了减少计算量和复杂度，本文提出的算法思路是首先划定一特定水平分割线，由此寻找最接近边界线的范围区域，减少不必要像素点的检测，然后再在此区域内精确寻找有效区域边界线。

3.2 算法具体实现过程

鱼眼图像有效区域的左右边界线的确定流程如图4所示。

图4 有效区域左右边界线提取流程

步骤1：首先在鱼眼图像的水平中间线上进行边界点的扫描，如图5所示。P1P2所在直线为水平分割线，其位置是鱼眼图像高度的1/2，先如向右箭头方向扫描。

图5 分割线扫描算法

步骤2：由式（1）计算出当前点的像素亮度值

将该点像素亮度值I与下一点的像素亮度值Incxt进行比较，由式（2）判断其差值是否满足条件

式中：T为预设阈值，如果当前点满足上述条件，则将该点设为临时边界点，在图5中标为P1点；如果不满足上述条件，则继续下一点的比较。同理，如向左箭头方向扫描，计算该点像素亮度值是否满足式（2），如果满足条件，则将该点设为临时右边界点，图中标为P2点；如果不满足上述条件，则继续下一点的比较。其中P1和P2点并不一定恰好是鱼眼图像有效区域的边缘，这是由于鱼眼图像中可能存在的黑色像素导致的，如果鱼眼图像中边缘有黑色物体，单纯地由水平分割线上的点的关系无法实现准确的有效区域边缘识别，所以进行如下计算。

步骤3：以P1点为起点，作P1P2线的垂线段，此垂线段的高度为鱼眼图像高度的1/2，如图2所示的鱼眼图像，鱼眼图像的有效区域基本位于整幅鱼眼图像的中间位置，因此为减少不必要的计算量，垂线段的高度为鱼眼图像的1/2即可达到提取目标，这也通过实验证实了其可行性，然后向鱼眼图像边缘方向移动，由式（1）计算此垂线段上的每个点的像素亮度值，并由式（3）求得最大亮度值与最小亮度值之差，即极限亮度值之差

式中：Δ为极限亮度值之差。再由式（4）判断极限亮度值之差是否满足条件

式中：Δnext为下一个扫描线段的极限亮度值之差。

如果满足上述条件，则将下一点所在的纵向直线设为鱼眼图像有效区域的左边界线；如果不满足上述条件，则继续下一点所在垂线上的极限亮度值之差的比较。

步骤4：与步骤3原理相同，以P2点为起点，作P1P2线的垂线段，此垂线段的高度为鱼眼图像高度的1/2，并向鱼眼图像边缘方向移动，计算此垂线上所有点的极限亮度值之差是否满足式（4），如果满足此条件，则将下一点所在的纵向直线设为鱼眼图像有效区域的右边界线；如果不满足，则继续下一点所在垂线上的极限亮度值之差的比较。

鱼眼图像有效区域的上下边界线的提取流程如图6所示。

步骤5：确定出鱼眼图像有效区域的左右边界线之后，以P1P2的中点作P1P2的垂线Q1Q2，从此垂线交于鱼眼图像的上边缘点开始向内移动，如图5所示，由式（1）计算当前点的像素亮度值，并判断是否与下一点的亮度值之差满足式（2），如果满足此条件，则将下一点设为临时上边界点，在图中标为Q1点；如果不满足上述条件，则继续下一点像素亮度值的比较。同理，从此垂线交于鱼眼图像的下边缘点开始向内移动，由式（1）计算当前点的像素亮度值与前一点的亮度值之差是否满足式（2），如果满足此条件，则将下一点设为临时下边界点，在图中标为Q2点；如果不满足上述条件，则继续下一点像素亮度值的比较。其中Q1和Q2点并不一定恰好是鱼眼图像有效区域的边缘，这与P1和P2点也不恰好是边缘点的原因一样，这都是由鱼眼图像中可能存在的黑色像素导致的。

图6 有效区域上下边界线提取过程

步骤6：同样为了减小鱼眼图像有效区域中的黑色像素带来的检测误差，对上下边界线的确定进行如下处理，以临时上边界点Q1为起点，作Q1Q2的垂线段，此垂线段的长度为鱼眼图像宽度的1/2，并向鱼眼图像的边缘移动，由式（3）求得此垂线段上的最大亮度值与最小亮度值之差，即极限亮度值之差，然后判断极限亮度值之差是否满足式（4），如果满足此条件，则将下一点所在的水平直线设为鱼眼图像有效区域的上边界线；如果不满足此条件，则继续下一点所在垂线上的极限亮度值之差的比较。

步骤7：同步骤6原理相同，以临时下边界点Q2为起点，作Q1Q2的垂线段，此垂线段的长度为鱼眼图像宽度的1/2，并向鱼眼图像的边缘移动，判断极限亮度值之差是否满足式（4），如果满足此条件，则将下一点所在的水平直线设为鱼眼图像有效区域的下边界线；如果不满足上述条件，则继续下一点所在垂线上的极限亮度值之差的比较。

3.3 有效区域中心与半径的确定

如果鱼眼图像有效区域为标准圆形，其圆心坐标和半径即可简单表示为

4 算法分析与实验结果

4.1 算法复杂度比较分析

假设图像的分辨率为W×H，鱼眼图像的有效区域半径为R，先分析面积统计法、经典扫描线法和改进扫描线法的计算复杂度。

根据面积统计法的算法原理，进行一次完整的分割过程，需要对整幅图像的每个像素处理，实际的计算量为

经典逐行逐列扫描线算法由于扫描到边界时就不再继续扫描，计算量相比面积统计法，减少了中心区域的计算，其计算量为

文献[8]对经典扫描线算法的改进，去除了经典算法4条扫描线重复扫描区域，但是此改进算法需要对像素点操作的次数为

而改进的分割线扫描线算法，以当前扫描线为边界代替鱼眼图像的边界，计算量相比经典逐行逐列扫描线算法更少，根据分割线扫描算法的原理，临时分界点的确定过程中，只是对单个像素进行计算，其计算量仅为相对较小的整数φ，水平扫描线宽度为W/2，竖直扫描线高度为H/2，并且两条扫描线在由临时分界点确定最终分界线过程中，只经过一段相对较短的距离，所以此过程的计算量为W/2×ζ+H/2×η，因此总的计算量为

式中：ζ，η和φ为一相对较小的整数。

从式（7）～（10）可明显得出，在高分辨率和高频率视频监控前提下，以上各算法计算量N1＞N2＞N3≫N4，在对1 080p图像进行处理时可以将原算法的200万计算量降低到万量级以下，通过仿真实验计算得到有效区域提取的算法时间对比如表1所示。

表1 不同算法有效区域提取时间对比

4.2 仿真结果

本文的仿真实验是在VS2008界面下，基于OpenCV实现的，针对本实验室所拍摄的鱼眼图像进行有效提取的实验室结果如图7所示，其中心坐标为（928.6，540.7），半径为540.26像素。

图7 鱼眼图像轮廓提取结果

5 结束语

本文针对高分辨率和高频率的高清鱼眼视频监控，为了能够得到更好地实时校正监控效果，提出一种分割线扫描提取有效区域算法，相比较面积统计法和扫描线法，以及改进的扫描线法，分割线扫描算法能大幅度减少鱼眼图像有效区域的提取时间，最后对本实验室所获取的高清鱼眼图像进行有效区域提取，并给出中心坐标和半径，为后续实现鱼眼图像的校正打下重要基础。

[1]于景良，王德福，倪志刚，等.全景电视摄像技术的研究[J].电视技术，1993，17（11）：2-5.

[2]英向华，胡占义.一种基于球面投影约束的鱼眼镜头校正方法[J].计算机学报，2003，26（12）：1702-1708.

[3]NOMURA Y，SAGARA M，HIROSHI N.Simple calibration algo⁃rithm for high-distortion-lens camera[J].IEEE Trans.Pattern Analysis and Machine Intelligence，1992，14（11）：1095-1099.

[4] SZELISKI R.Video mosaics for virtual environment[J].IEEE Com⁃ puter Graphics and Applications，1996，16（2）：22-30.

[5] 杨丹，游磊，张小洪，等．基于区域生长的鱼眼图像轮廓提取算法[J].计算机工程，2010，36（8）：217-218．

[6] 王大宇，崔汉国，陈军.鱼眼图像轮廓提取及校正研究[J].计算机工程与设计，2007，28（6）：2878-2879．

[7]常丹华，赵丹，杨峰明，等.提取鱼眼图像轮廓的算法改进及图像校正[J].激光与红外，2012，42（4）：448-451.

[8] 江芳，袁纵横.鱼眼图像轮廓提取方法的对比[J].计算机系统应用，2011，20（4）：214-218.

Algorithm for Dividing Line Scan Fisheye Image Region Extraction

CHENG Deqiang，LIU Yang，LIU Xue，ZHAO Guo，ZHANG Jialin
（School of Information and Electrical Engineering，China University of Mining&Technology，Jiangsu Xuzhou 221000，China）

For correcting the ultra wide angle of fish-eye image，the key is accurately extracting the effective coverage of fish-eye image，and determining the center and radius of effective coverage.In view of video surveillance of high definition fish-eye，the existing correction algorithms of fish-eye lens have some insufficient.In order to satisfy the high definitionof fish-eye video surveillance，the cut line scanning algorithm basing on existing algorithms is proposed in the paper.Aiming at reducing unnecessary detections of pixel points，a specific level cut line must be determined to find the range and region which most closing boundary line.Then the boundary line of effective coverage can be precisely found in the region.The experimental results show that the algorithm can significantly reduce the time complexity and computational complexity when the algorithm extracts efficient coverage of fish-eye image，meanwhile maintain the original extraction precision，and reduce the computational complexity from 2 000 000 to 10 000 or below.

fisheye lens；contour extraction；line scan

TN919.81 文献标志码：A DOI：10.16280/j.videoe.2015.06.001

【本文献信息】程德强，刘洋，柳雪，等.分割线扫描鱼眼图像有效区域提取算法[J].电视技术，2015，39（6）.

国家自然科学基金委员会与神华集团有限责任公司联合资助项目（U1261105）

时 雯

2014-06-05