1 引言

快速、准确地检测矩形在实际应用中具有重要的意义,例如汽车的车牌与矩形零件的定位和识别以及复杂背景下的二维码检测等。目前,关于矩形的检测算法大部分采用基于Hough变换检测直线算法以及基于Harris角点检测算法。

利用基于Hough变换检测直线算法检测矩形,通常先检测矩形的4条边再检测矩形,等价于将矩形检测转换为直线检测。直线检测的方法中,基于经典Hough变换检测直线算法应用最为广泛^[1]。Jung和Schramm^[2]提出了基于窗口Hough变换的矩形检测算法,该算法利用环形窗口扫描图像,且对环形窗口内的图像进行Hough变换,通过比较Hough空间的峰值点来判断窗口中心是否为矩形中心,从而检测环形窗口内所包围的矩形,虽然可以检测出方向和大小未知的矩形,但因为检测过程中对窗口内的像素都进行操作,导致计算量大,检测速度较慢。李强兵等^[3]给出了基于Hough变换的矩形检测算法,该算法在Hough变换的空间上对峰值点进行一系列操作,并在组合和提取到的峰值点中检测出满足一定角度和长度条件的直线,最终识别图像中的矩形。王红军等^[4]提出了结合Hough变换和最小二乘拟合的矩形几何提取和校正算法,利用该算法来识别图像中的直线,并且利用4条直线的4个交点得到透视变换矩阵,从而将四边形内的点映射到矩形区域。Zhu等^[5]提出了一种随机Hough变换(RHT)方法,用来检测冷冻电子显微镜图像中的矩形颗粒,如果已知矩形的边,使用2D累积数组来检测矩形的中心和方向,该方法检测快速,并且检测结果很好,但仅限于图像中所有矩形具有相同的尺寸,并且所有尺寸都清楚。目前,基于Hough变换的改进算法主要有RHT以及概率Hough变换(PHT)方法等^[6-7]。但Hough变换需要对每个像素点进行操作,导致基于Hough变换的矩形检测无法解决耗时长的问题且效率较低,在检测速度要求高的环境下应用受限。

基于Harris角点检测的矩形检测方法通常先检测矩形的角点,再根据角点信息来识别矩形,等价于将矩形检测转换为角点检测。张从鹏等^[8]提出了基于Harris角点的矩形检测算法,该算法改进传统的Harris角点检测算法,首先提取矩形中L型角点,然后提取L型角点中满足矩形特性的角点,利用角点信息来检测矩形,该算法与Hough变换方法相比,可以提高检测速度和效率,但是在图像中的角点信息受到严重噪声污染的情况下,检测容易受到干扰,会检测出多余的矩形,从而影响矩形检测的准确率。

目前,针对矩形检测算法存在检测速度慢、准确率低以及精度的问题,本文提出一种快速、高精度的矩形识别算法。通过提取图像中的亚像素轮廓并将轮廓分割为线段,然后利用模糊数学理论对线段的几何和物理特性进行融合计算,最终根据模糊融合计算得到的判决结果来识别并定位矩形。该算法能够快速并且准确地检测出图像中的矩形,具有一定的应用价值。

2 算法原理

2.1 矩形判断的条件

图1中P₁P₂P₃P₄是一个矩形,其中P₁=(x₁,y₁),P₂=(x₂,y₂),P₃=(x₃,y₃),P₄=(x₄,y₄),P₁、P₂、P₃和P₄为矩形的4个顶点,其中(x₁,y₁),(x₂,y₂),(x₃,y₃)和(x₄,y₄)分别为矩形线段的端点坐标。图像坐标系为xOy,原点为O。线段P₁P₂,P₂P₃,P₃P₄,P₄P₁满足以下条件,则可以判定其为一个矩形。

1)斜率条件:k₁=k₂,k₃=k₄。其中k₁为线段P₁P₂的斜率,k₂为P₃P₄斜率,k₃为P₂P₃的斜率,k₄为P₄P₁的斜率。

2)长度条件:l₁=l₂,l₃=l₄。其中P₁P₂=l₁,P₃P₄=l₂,P₂P₃=l₃,P₄P₁=l₄。

3)距离关系:d₁>0,d₂>0。d₁为两线段P₁P₂和P₃P₄之间的垂直距离,d₂为线段P₄P₁和P₂P₃之间的垂直距离。

4)相邻边正交:角度值差为π/2,即arctan k₁-arctan k₃=π/2。

5)位置关系:P₁P₂和P₃P₄对角线交点为O₁,P₂P₃和P₄P₁对角线交点为O₂,其中O₁与O₂点重合,且对角线P₁P₃=P₂P₄,即d₃=d₄。

图 1. 矩形示意图

Fig. 1. Rectangular diagram

下载图片 查看所有图片

2.2 模糊融合的原理

在所提算法中,4条线段是否可以组合成矩形,是由一系列与矩形的几何特性有关的判断条件决定的,每个判断条件提供线段是否为矩形边的支持程度,这种支持程度有较大的不确定性,所以设置固定的阈值来判定线段是否为矩形边是不合理的。Zadeh教授提出了模糊集合理论^[9],在这个理论中提供了一种处理不严密信息的方法,并且通过模糊计算融合来判断信息,故实验引入模糊集合理论来解决判定是否为矩形的问题^[10]。

定义1:利用模糊逻辑来解释不确定性的隶属度函数,并将由隶属度函数生成的集合视为模糊集合。

定义2:对于论域U上的模糊集合A由隶属度程度μ_A(u)来表征,映射μ_A:U→[0,1],u→μ_A(u)叫作A的隶属度函数。任意u∈U,μ_A(u)∈[0,1]叫作u关于A的隶属度程度。对于μ_A(u)=1的所有u都是模糊集合A的元素,对于μ_A(u)=0的所有u都不是模糊集合A的元素,而μ_A(u)值介于0和1之间的所有u均是模糊集合A的部分元素。

实验使用定义来判决矩形的隶属度程度,并以此判断任意4条线段是否能够组合成矩形,其中每一个判决器得到的结果是线段为矩形边的隶属度程度。为了综合考虑每个判决器的计算结果,采用模糊数学的方法融合计算每个判决结果。采用的判决条件如下。

1)斜率条件,平行直线的斜率相等。因为直线的斜率有可能不存在,所以直线的斜率使用角度α=arctan [(y₅-y₀)/(x₅-x₀)]来表示,其中(x₀,y₀)和(x₅,y₅)分别为线段的端点坐标。隶属度函数可表示为

u1(w1)=-w1/b+1,0≤w1≤b0,else,(1)

式中:b表示角度差的阈值;w₁表示任意两条直线l_i和l_j的斜率反正切值差的绝对值,即w₁=|α_i-α_j|,i、j表示不同的编号。图2为斜率相似的隶属度函数曲线。

图 2. 斜率相似的函数图像

Fig. 2. Function image of similar slope

下载图片 查看所有图片

2)长度条件,P₁P₂=l₁,P₃P₄=l₂,P₂P₃=l₃,P₄P₁=l₄,l₁=l₂,l₃=l₄,隶属度函数可表示为

u2(w2)=-w2/c+1,0≤w2≤c0,else,(2)

式中:c表示长度差的阈值;w₂表示任意两条直线l_i和l_j的长度差值的绝对值,即w₂=|l_i-l_j|。图3为长度相似的隶属度函数曲线。

图 3. 长度相似的函数图像

Fig. 3. Function image of similar length

下载图片 查看所有图片

3)相邻边正交,角度差为π/2,即arctan k₁-arctan k₃=π/2,k₁=(y₂-y₁)/(x₂-x₁)、k₃=(y₃-y₂)/(x₃-x₂)。隶属度函数可表示为

u3(w3)=2w3/π,0≤x≤π/20,else,(3)

式中:w₃表示任意两条直线l_i和l_j的角度差的绝对值,即w₃=|arctan k_i-arctan k_j|。图4为正交性的隶属度函数曲线。

图 4. 正交性的函数图像

Fig. 4. Function image of orthogonality

下载图片 查看所有图片

4)矩形的中心位置重合,P₁P₂和P₃P₄的对角线交点为O₁,P₂P₃和P₄P₁的对角线交点为O₂。当O₁和O₂点重合时,则满足矩形的中心不变性。隶属度函数可表示为

u4(w4)=1,0≤w4≤mw4/(m-n)+n/(n-m),m<w4≤n0,else,(4)

式中:m和n分别表示中心点距离矩形长和宽的阈值,其中n>m;w₄表示两对角线交点之间的距离,即w₄=O₁O₂。图5为中心位置关系的隶属度函数曲线。

图 5. 中心位置关系的函数图像

Fig. 5. Function image of center position relationship

下载图片 查看所有图片

每个判决条件的计算结果是一个有关线段是否为矩形边的隶属度函数。分别计算(1)~(4)式,可以得到对应情况下线段为矩形边的支持程度,并且利用融合策略公式^[7],其表达式为

S=∑a=14{ua(wa)-[1-ua(wa)]},(5)

来融合计算(1)~(4)式得到的结果,就可最终判定线段是否为矩形边。式中:u_a(w_a)表示第a个判别式判决线段为矩形边的隶属度值。当S>0时,4条线段可以组合成矩形。当S≤0时,4条线段无法组合成矩形。

3 矩形检测的实施方法

3.1 基本思想

如果直接采用算法对整幅图像进行处理,会因组合线段数量过多,导致运算量过大,耗时较长,所以所提算法将以(x₀,y₀)为原点的环形区域分割为I个感兴趣区域,并分别对每个感兴趣区域进行矩形检测,其中I为图像中封闭轮廓的个数。首先提取子图像的亚像素轮廓^[11-12],将亚像素轮廓分割为线段^[13],然后利用模糊数学的方法将直线信息融合为矩形。环形区域的选择如图6所示,其中(x,y)为图像中轮廓区域的中心,轮廓的最短边为D_min,最大轮廓的对角线长度为D_max。

图 6. 环形区域的选择

Fig. 6. Selection of ring regions

下载图片 查看所有图片

3.2 矩形检测算法的步骤及流程图

矩形检测算法的检测步骤如下。

step 1:提取目标图像的亚像素轮廓,计算图像中每个轮廓所有连续点的算术平均值和图像中封闭轮廓的中心^[14-15],以确定环形区域的位置。

step 2:将环形区域分割为I个感兴趣区域。

step 3:提取感兴趣区域的亚像素轮廓^[11-12]。由于提取的亚像素轮廓可能出现断线的现象,所以首先对提取到的亚像素轮廓进行共线连接^[10],然后将轮廓分割为多条线段^[13],并在数组A₁中保存线段的坐标(x_z,y_z),z=1,2,3,…,Z。

step 4:提取线段中相互平行的线段。

1)利用A₁中所有线段坐标来计算任意两条线段的斜率和长度的隶属度函数的隶属度值u₁和u₂。利用α_i、α_j和w₁来计算u₁和u₂。若w₁∈[0,b],u₁=-w₁/b+1,反之,u₁=0。在数组A₂中保存线段的斜率反正切值的均值β=(α_i+α_j)/2。

2)计算两条线段l_i和l_j的中点坐标(x_z0,y_z0)和(x'_z0,y'_z0)以及两中点之间的距离d。

3)计算两条线段l_i和l_j的长度,即w₂=|l_i-l_j|,其中w₂为两线段长度差的绝对值。若w₂∈[0,c],u₂=-w₂/c+1,反之u₂=0。

4)利用(6)式以及附加判据d>0来计算S₁=[u₁-(1-u₁)]+[u₂-(1-u₂)]。若S₁>0,且d>0的线段l_i和l_j为矩形的一对平行边,由此在数组A₃中保存矩形的边长L=(l_i+l_j)/2。

step 5:为了提取平行线对中相互垂直的平行线对,通过步骤1)~3)来计算平行线对的u₃和u₄。步骤如下。

1)分别扫描数组A₂和A₃中的β和L值,计算任意β_i与β_j差值的绝对值,即θ=|β_i-β_j|。若θ∈[0,π/2],u₃=2θ/π,反之u₃=0。同理,比较L_i和L_j值的大小。

2)分别求得两对平行线对的对角线交点O₁与O₂之间的距离w₄,及两对角线的长度为d₃和d₄。若w₄∈[0,m],u₄=1。若w₄∈(m,n],u₄=d₁/(m-n)+n/(n-m)。否则,u₄=0。

3)利用(6)式融合计算S₂=[u₃-(1-u₃)]+[u₄-(1-u₄)]。若S₂>0,d₃=d₄,则两对平行边互相垂直,可以判定这两对平行边为矩形的4条边,此时环形区域的中心即为矩形的中心坐标,长度为L_i和L_j中的最大值,宽度是L_i和L_j中的最小值。否则,两对平行边不是矩形的4条边。

step 6:循环执行I次step 3~5的操作,最终检测图像中所有矩形的中心坐标、长度、宽度以及倾角。

4 算法测试及结果分析

使用所提算法分别对合成图像和利用机械手动平台上由工业相机采集的实际矩形零件图像进行测试。

4.1 合成图像的测试结果

合成图像如图7(a)和图7(b)所示,使用所提算法对合成图像1和图像2进行测试,测试结果如图7(c)和图7(d)所示,检测结果的对比如表1所示。从图7和表1可以看到,利用所提算法检测图7(a)和图7(b)的合成图像,检测的准确率为100%,且最大耗费时长小于95 ms。图像测试的过程中,采用的参数b=π/4,c=5,m=2,n=3。

4.2 实际矩形零件图像的测试结果

由工业相机采集得到实际矩形零件图像。系统配置:面阵工业相机,型号为A3600MG18,620万像素,GigE接口;镜头为JHHF0420-5M。实验室的光源条件为环形光源。算法运行环境及硬件:MATLAB R2015b,i7-4790 CPU,8.00 GB内存,64位操作系统。

使用由千兆网工业相机采集的三组实际矩形零件图像来验证所提算法的检测准确度、速度以及精度,结果如图8~10所示。分别使用文献[ 2]和所提算法对矩形零件1和2进行测试,结果如图8和图9所示,检测结果对比如表2所示;使用文献[ 8]和所提算法对矩形零件3进行测试,结果如图10所示。检测矩形的中心坐标为(122.463,126.233),长为195.380 pixel,宽为100.253 pixel,倾角为8.025°。实际矩形图像的中心坐标为(122.000,126.000),长为195.000 pixel,宽为100 pixel,倾角为8°。采用的参数b=π/4,c=6,m=1,n=2。采集大小为3072 pixel×2048 pixel的80幅实际矩形图像,对其进行分析,可以得到所提算法的平均耗时为229.75 ms,正确次数为80次,准确率为100%。

图 7. 合成图像及矩形检测的结果。(a)合成图像1;(b)合成图像2;(c)合成图像1的检测结果;(d)合成图像2的检测结果

Fig. 7. Results of composite image and rectangle detection. (a) Composite image 1; (b) composite image 2; (c) detection result of composite image 1; (d) detection result of composite image 2

下载图片 查看所有图片

图 8. 不同算法对矩形零件1的检测结果。(a)矩形零件1;(b)文献[ 2];(c)所提算法

Fig. 8. Detection results of rectangular part 1 by different algorithms. (a) Rectangular part 1; (b) Ref. [2]; (c) proposed algorithm

下载图片 查看所有图片

图 9. 不同算法对矩形零件2的检测结果。(a)矩形零件2;(b)文献[ 2];(c)所提算法

Fig. 9. Detection results of rectangular part 2 by different algorithms. (a) Rectangular part 2; (b) Ref. [2]; (c) proposed algorithm

下载图片 查看所有图片

图 10. 不同算法对矩形零件3的检测结果。(a)矩形零件3;(b)文献[ 8];(c)所提算法

Fig. 10. Detection results of rectangular part 3 by different algorithms. (a) Rectangular part 3; (b) Ref. [8]; (c) proposed algorithm

下载图片 查看所有图片

4.3 算法性能比较

通过分析检测结果可知,所提算法的检测速度是Hough矩形检测算法的7.4倍;由于采用亚像素轮廓算法,矩形图像中心位置的最大定位误差为(0.507 pixel,0.272 pixel),测得矩形长度的平均误差为1.034 pixel,宽度的平均误差为1.310 pixel,倾角的平均误差为0.304°,利用文献[ 2]算法得到的长度、宽度以及倾角误差分别为6.142 pixel、7.922 pixel和1.179°。从图10可以看到,在这种情况下Hough算法出现误检的现象,所提算法的精度以及准确率均优于文献[ 8]。文献[ 8]受到角点信息检测不准确的干扰,导致检测出多余矩形。所提算法未涉及角点信息的提取,所以相对于文献[ 8],误检的次数减少。分析可知所提算法的时间复杂度为o(n),文献[ 8]的时间复杂度为o(n²),所以所提算法的执行速度较快。

所提算法通过调整b,c,m,n值可以快速、准确地识别矩形。即使是复杂的矩形图形或零件,也可以准确地检测矩形的中心位置并取得很好的精度,但缺点是检测过程中的c、m、n值受到零件尺寸的影响,不同批次的检测零件的尺寸波动较大,需及时调整取值。所提算法对于检测精度、速度和准确率要求高的场合有较高的适应性。

5 结论

为了实现快速而准确地识别、定位矩形,提出一种快速、高精度的矩形检测算法。实验结果表明:该矩形检测算法能够高效、高精度和高准确率地实现矩形的识别和定位。实验结果显示所提算法的检测速度为Hough矩形检测算法的7.4倍,最大中心定位误差为(0.507 pixel,0.272 pixel)、长度的平均误差为1.034 pixel,宽度的平均误差1.310 pixel,倾角的平均误差为0.304°,准确率、精度以及速度相对文献[ 2]和文献[ 8]有所提高,也减少误检情况的发生。所提算法能够满足高精度、高效和高准确率的矩形图元检测,具有一定的工业应用价值。