融合区域生长与霍夫变换的内窥图像分割算法

耿春明，方 菲

(北京航空航天大学 机械工程及自动化学院,北京 100191)

引言

图像分割在许多自动图像模式识别和场景分析问题中是一个基本的预备性步骤。为实现复杂背景中运动目标的检测与识别，应首先考虑如何利用图像分割方法分割出有效的检测区域，这一直是人们关注的难点问题。目前常用的分割算法主要有阈值法、区域生长法两大类[1]。这两类方法各有优势，却也有局限性。例如阈值法选取的阈值不精确；区域生长法由于生长准则或目标区域灰度分布不均匀等原因造成欠分割或者过分割等[2-3]。分析这两类分割方法的优缺点，结合本文实际采集图像的特点，提出了一种基于区域生长和霍夫(Hough)变换相结合的分割方法，最终准确地划分出有效检测区域。

1 算法设计和实现

1.1 算法设计

设计的算法主要应用于由内窥镜采集到的不透明容器内部物质的图像。内窥镜放置在容器口处，所以在图像中呈现的是容器内所有物质由上而下的俯视平面图。图像采集是在外界为全黑的环境下进行，保证采集图像时不受到外界光源的影响，采集图像的光源由内窥镜自带的LED白光源提供。该条件下采集的图像具有特点是图像中含有强光干扰与光圈等。观察实验中采集的图像(如图1所示)，强光干扰区域(图1中C区域)即图中高亮度的光线区域，它主要是由内窥镜LED白光源过于集中引起的；光圈(图中B区域)主要是由于光线在容器壁与容器内液体表面这两种不同介质上的折射、反射等不一样造成的，由此可知，光圈外侧是容器壁，光圈内侧是容器内的液体，即光圈内的区域为有效检测区域。为最终检测出目标(如图中的杂质目标A)，应首先分割出有效检测区域。结合这些图像的显著特点以及上述两类分割方法的优缺点，提出了基于区域生长和霍夫变换相结合的分割方法。

图1 实际内窥图像Fig.1 Actual endoscopic images

此算法的基本思想：首先根据强光干扰区域灰度值高于背景区域灰度值的特点，利用基于区域灰度差的区域生长法[4]作为基础分割算法，可将强光干扰区域及光圈区域大致分割出来；由于区域生长法可能造成欠分割或过分割，因此再根据光圈具有规则圆形状的特点，采用霍夫变换检测[5]作为辅助算法更为准确地检测出光圈的位置，从而可弥补区域生长的不足之处，更准确地划分出有效检测区域。

为进一步提高精确性，针对算法中2个基本模块——区域生长和霍夫变换分别做出改进。第一点改进：在选择合适的生长点和生长规则进行区域生长之后运用形态学的膨胀和腐蚀运算处理[6]。这主要是为了填充区域生长后图像物体内部的细小孔洞以及连接临近的物体，可以在不明显改变物体面积和形状的情况下起到平滑其边界的作用[7]。第二点改进:在霍夫变换检测圆之前先做Canny边缘检测[8-9]。通过边缘检测可提取出感兴趣区域(主要是光圈)的边缘，依据此边缘进行Hough变换检测圆，可减少虚假圆检测及漏检圆的情况，更精确地判定出圆的位置，从而提高了有效检测区域的划分准确性。算法的基本流程图如图2所示。

图2 算法流程图Fig.2 Flow chart of algorithm

1.2 算法实现

1.2.1 区域生长和填充

区域生长基本思想[10]是将具有相似性质的像素集合起来构成区域。选择合适的生长点，根据生长准则将生长点周围与其相同或相似的像素合并到生长点所在区域。再将这些新像素当作新生长点继续进行生长，直到所有满足条件的像素都被包括在内，则完成生长。从以上描述可知：预分割的区域(强光干扰和光圈区域)灰度值高于背景区域，故选择图像中灰度值大于最亮区域灰度均值的像素点作为生长点，并且选择基于区域灰度差的生长准则，主要程序流程如图3所示。

图3 区域生长程序流程图Fig.3 Flow chart of region growing

区域生长结束后，为填充图像内部的细小孔洞等，算法改进在其后运用二值形态学处理作为区域填充算法，主要运用膨胀和腐蚀运算处理：先进行膨胀运算，后进行腐蚀运算。图4是区域填充的程序实现过程。

图4 区域填充程序流程图Fig.4 Flow chart of area filling

1.2.2 改进的Hough变换

Hough变换(circle Hough transform, CHT)及相应改进算法[11]是常用的检测圆算法之一，在本文的主要任务是精确定位有效检测区域的位置。它的主要计算方法[12]是图像中所有点做三维空间参数转换，通过求三维累加阵列的峰值，获得所需的圆参数。这种变换消耗大量时间和存储资源[13]，为此算法做出改进。首先利用边缘检测提取出感兴趣区域的边缘，只对边缘点做三维变换。Canny算子能较好平衡噪声抑制和边缘检测[14]，是对定位乘积与信噪比的最优化算法[15]，故选择Canny边缘检测提取图像边缘。通过设计合理的高通滤波器对图像进行滤波，可提取出二维信号的高频成分即边缘信息。算法中进行高斯滤波，利用一阶偏导的有限差分计算梯度幅值和方向，通过对梯度幅值进行非极大值抑制来确定该点是否为边缘点，最后采用双阈值法检测和连接边缘。其次通过降低参数空间的维数来减少开销。实验中的图像半径r大约在180像素～260像素之间变化，因此累加该范围内对应边缘点的变换点即可。算法软件实现流程如下：

第1步，按Canny边缘检测法搜索出边缘点。

首先根据高斯核公式(1)生成二维高斯滤波系数k，用该系数对图像进行滤波处理，滤波后的图像数据保存在*lpNewDIBBits。

(1)

式中：(x,y)表示图像中当前像素点的坐标位置；σ表示高斯函数的标准偏差，本文选取0.4。

其次根据(2)式～(5)式计算x、y向偏导数、梯度幅值及梯度方向P[i,j]、Q[i,j]、M[i,j]及θ[i,j]：

P[i,j]= (f[i,j+1]-f[i,j]+f[i+1,j+

1]-f[i+1,j])/2

(2)

Q[i,j]= (f[i,j]-f[i+1,j]+f[i,j+1]-

f[i+1,j+1])/2

(3)

(4)

θ[i,j]=arctan(Q[i,j]/P[i,j])

(5)

其中f[i,j] 表示像素点[i,j]的灰度值。

接着进行非极大值抑制。循环遍历所有梯度幅值点，判断这些点的灰度值在其8邻域内是否为局部最大。若是则保留该值不变；反之则可排除该点在边缘上，置其值为0。

最后按双阈值法连接边缘。先按高阈值ThrHigh寻找边缘，以找到的点为中心寻找邻域内满足低阈值ThrLow的点，形成闭合轮廓。按经验公式选取高、低阈值，即：

ThrHigh=nHist[0.79×nEdgeNum]

(6)

ThrLow=0.5×ThrHigh

(7)

式中：nEdgeNum表示边缘点总个数；nHist[i]表示灰度值从低到高有序数组。

第二步，只对边缘点进行Hough变换，并只累加半径范围在180像素～260像素内的变换点即可。

首先设置角度、半径步长step_angle、step_r和半径变化范围r_min～r_max，按(8)式、(9)式计算半径、旋转一周角度变换次数size_r、size_angle；按图像大小建立变换后参数空间hough_space[Height*Width][size_r]，初始条件下所有元素均置0。

size_r=(r_max-r_min)/step_r

(8)

size_angle=2π/step_angle

(9)

其次循环遍历所有像素点，判断当前点(i,j)是否是边缘点。如果是，则按(10)式、(11)式对(i,j)做Hough变换，其中r在0～size_r、k在0～size_angle间循环变化，(temp_a,temp_b)是变换后的点。

temp_a=i-(r_min+r×step_r)×

cos(step_angle×(k+1))

(10)

temp_b=j-(r_min+r×step_r)×

sin(step_angle×(k+1))

(11)

判断(temp_a,temp_b)是否超出图像的范围，没超出则将(temp_a,temp_b,r)相应的累加器hough_space加1，即

hough_space[temps_a×Width+

temp_b][r]+=1

(12)

最后搜索hough_space数组中超过阈值的聚焦点，其中阈值取hough_space中最大值的0.7倍。在找到的所有聚焦点中求出半径最小的圆，此圆内即为有效检测区域。

2 实例仿真分析

该分割算法主要针对由内窥镜采集到的不透明容器内的液体图像，图像的大小为480像素×640像素，灰度级为256。实验的硬件环境为，CPU：Intel( R) Core(TM)i3 3.07 GHz；内存：1.80 GB；采集图像设备：USB接口的内窥镜，分辨率为30万像素。实验中算法在Windows XP、Microsoft Visual C++6.0平台上实现。

首先，区域生长法可大致分割出强光干扰区域及光圈区域，在区域生长后使用形态学处理来填充图像生长引起的细小孔洞以及连接临近的物体。为了验证这个方法对实际图像的分割效果是否有效，对由内窥镜采集的不透明容器内液体的图像进行实验，图5为一组仿真结果。

观察图5(a)源图像和图5(b)区域生长图像可知，按照上文所述方法选择的生长点和生长准则进行区域生长后，能够大致提取出亮度较高的强光干扰区域和光圈区域，即区域生长可以大致提取出干扰区域。此外，对比图5(b)区域生长图像与图5(c)区域生长后进行区域填充的图像，经过形态学处理的区域填充后可以将由区域生长造成图像中的一些孔洞填补，也可以连接相距很近的一些区域，即改进后具有区域填充的区域生长法能够使图像生长得更加完整。

其次，在利用区域生长大致分割出干扰区域的基础上，进一步采用Hough变换圆检测算法精确地分割出有效检测区域。为了验证这个算法的分割效果优于单独基于区域生长的分割效果，在VC++6.0环境下实现了区域生长与Hough变换检测相结合的算法，将实验结果与上文中只基于区域生长法的实验结果进行对比，仿真结果如图6所示。

图5 仿真结果Fig.5 Simulation results

图6 仿真结果Fig.6 Simulation results

从实验结果可以看出，区域生长与Hough变换检测相结合的分割算法在分割效果上要优于单独基于区域生长的分割算法。对比图6(b)只基于区域生长的分割图像和图6(c)区域生长与Hough变换检测结合的分割图像可以看出，图6(b)在图像中心位置附近有强光干扰未分割出，此外图像也没有准确地分割出有效检测区域，也就是说单独基于区域生长分割出的图像不仅会产生漏检边缘，不能完全分割出强光干扰，而且也不能确定哪些区域是需要检测区域、哪些区域是不需要检测区域；然而观察图6(c)，在图像中心位置附近的强光干扰几乎被全部分割出，并且确定了有效检测区域(圆内区域，将不关心的区域赋为全黑区域)，即区域生长法与Hough变换检测相结合可以有效地抑制漏检边缘或虚假边缘的产生，同时也划分出有效检测区域，能取得对感兴趣区域的良好分割效果。

结合上述的实例，另外再利用内窥镜采集90组不透明容器内的液体图像进行实验。将此90组均有强光圈干扰这个特点的内窥图像依照文中提出的算法进行处理，处理结果显示，有88组内窥图像能够精确的分割强光干扰，且划分出有效检测区域；仅有2组图像分割出的强光干扰及划分出的有效检测区域不够准确。据此统计，针对有强光圈干扰的内窥图像，此算法能较精确地分割出强光干扰且划分出有效检测区域的概率约可达到97.8%。由此可知：本文算法对带有强光圈干扰的内窥图像能取得良好的有效区域分割效果。

3 结束语

区域生长是传统的图像分割方法，Hough变换是传统的检测圆算法。区域分割能够检测特征的相似性与均匀性，而Hough变换能够检测出比较规则的圆。文中提出的基于这两种方法的图像有效检测区域的分割算法，结合了两者的特点，首先通过区域生长法大致分割出比较规则的光圈所组成的圆，再通过Hough变换准确地划分出有效检测区域。因此，避免了单独使用区域生长进行图像分割时，造成的漏检边缘或分割出虚假边缘的错误；也避免了单独使用Hough变换检测圆时，造成的误检虚假圆或由于光圈不明显而不能准确检测到圆的错误。从上述的实例分析以及采用此算法对90组内窥图像进行实验得到的实验结果和数据可知，结合这两种算法作为分割方法，对含有强光圈的内窥图像具有很好的分割效果，分割出的有效检测区域位置更精确。

[1] Guo Suoli, Xin Dong, Liu Yanfei. Survey of modern image segmentation method[J]. Journal of Sichuan Ordnance, 2012,33(7):93-96.

郭锁利，辛栋，刘延飞.近代图像分割方法综述[J].四川兵工学报，2012，33(7):93-96.

[2] Zhang Ling, Guo Leimin, He Wei,et al. An image segmentation algorithm based on maximal variance between-class and region growing[J]. Information and Electronic Engineering, 2005,3(2):91-93,96.

张玲，郭磊民，何伟,等.一种基于最大类间方差和区域生长的图像分割法[J].信息与电子工程，2005，3(2):91-93,96.

[3] Luo Wencun. A new image segmentation approach by integration of thresholding and region growing[J]. Modern Computer, 2001,115:43-46.

罗文村.基于阈值法与区域生长法综合集成的图像分割法[J].现代计算机,2001,115:43-46.

[4] Yu Dianhong. Image detecting and processing technology[M]. Xi’an: Xi’an University of Electronic Science and Technology Press, 2006:155-159.

于殿泓.图像检测与处理技术[M].西安：西安电子科技大学出版社，2006:155-159.

[5] Ye Fudong. An graphic detection algorithm based on Hough transform[J]. Journal of Hubei Vocational College of Ecological Engineering, 2011,9(3):45-49.

叶富东.基于霍夫变换的图形检测算法[J].湖北生态工程职业技术学院学报，2011，9(3):45-49.

[6] Yu Zhaohui, Pang Yechi, Yu Tao. The engineering application and digital image processing of visual C++[M]. Beijing: China Railway Publishing House, 2012:335-353.

俞朝晖，庞也驰，于涛.Visual C++数字图像处理与工程应用实践[M].北京：中国铁道出版社，2012:335-353.

[7] He Dong，Yang Fengbo，Lin Suzhen,et al. Colour transfer for grayscale images based on morphology transformation and FFCM cluster[J]. Journal of Applied Optics, 2012, 33(2):300-304.

贺栋，杨风暴，蔺素珍,等.基于形态学变换和FFCM聚类的灰度图像颜色迁移算法[J].应用光学,2012, 33(2):300-304.

[8] Miao Yu, Wang Yanchun, Guo Naizhu,et al. Region growth algorithm based on edge detection ending condition[J]. Journal of Changchun University of Science and Technology, 2009,32(4):680-682,556.

苗语，王艳春，郭乃珠,等.基于边缘检测终止条件的区域生长算法[J].长春理工大学学报，2009，32(4):680-682,556.

[9] Trucco E，Verri A. Introductory techniques for 3-D computer vision [M]. Englewood Cliffs:Pretice Hall, 1998:71-79.

[10] Tao Tangfei, Han Chongzhao, Dai Xuefeng, et al. An infrared image segmentation method based on edge detection and region growing[J]. Opto-Electronic Engineering, 2004,31(10):50-52,68.

陶唐飞，韩崇昭，代雪峰，等.综合边缘检测和区域生长的红外图像分割方法[J].光电工程，2004，31(10):50-52,68.

[11] Illingworth J，Kittler J. A survey of the Hough transform[J]. Computer Vision Graphics and Image Process,1988,44(1): 87-116.

[12] Wang Xuewei,Wang Shili，Li Ke. Characteristic of ship target IR image[J]. Journal of Applied Optics, 2012, 33(5):837-840.

王学伟，王世立，李珂.船舰目标红外图像特性研究[J].应用光学,2012,33(5):837-840.

[13] Zhao Xiaochuan, He Hao, Miu Yuancheng. Digital image processing of MATLAB[M]. Beijing: China Machine Press, 2013:97-101.

赵小川，何灏，缪远诚.MATLAB数字图像处理实战[M].北京：机械工业出版社，2013:97-101.

[14] Jia Yonghong. Digital image processing[M]. Wuhan: Wuhan University Press, 2003：133-145.

贾永红.数字图像处理[M].武汉：武汉大学出版社，2003：133-145.

[15] Chen Yanyan, Wang Yuanqing. Quantitative comparison of common edge detection algorithms[J]. Computer Engineering, 2008, 34(17): 202-204.

陈彦燕，王元庆.常用边缘检测算法的定量比较[J].计算机工程,2008,34(17): 202-204.