一种新型圆检测方法

1.本发明属于模式识别算法领域，特别是涉及一种新型圆检测方法。

背景技术：

2.随着计算机技术的发展，图像成为表达、传递现实世界场景的载体，图像中的圆形目标的检测是计算机视觉和模式识别中的一个基本问题，圆检测广泛应用于航天器、工业部件测量、虹膜定位、纳米粒子研究、细胞分析、机器人技术、交通标识、棒材自动统计等领域，因此对圆检测方法的研究有着重要的实用价值和意义。
3.最经典的圆检测方法是霍夫变换(ht)，它将圆参数的估计转换为多个三维圆锥空间的交集，其中累加器中的最高峰作为最终确定的圆参数。但是，ht占用内存空间大，耗时高，对噪声敏感，尤其是在存在复杂背景时。与ht不同，随机圆检测(rcd)在每次迭代中随机选择四个边缘点，使用距离标准计算圆参数，然后进行证据收集和验证，虽然rcd提高了计算效率，但它仍然需要多次尝试来生成候选圆，然而对于存在遮挡、噪声或复杂场景的图像，随机采样点来自同一个圆的概率很小。利用了圆的几何特性进行圆参数检测的方法也出现了很多，例如射线、梯度、对称性、相交线、内接三角形等几何特性。然而，正如文献中指出的那样，射线计算了功率峰值直方图时，需要设置多个参数点进行多次计算；梯度计算结合了微分，使梯度比边缘点对噪声更敏感；对称性的利用是基于完整的圆假设，因此不适合遮挡和噪声场景；相交线需要是同一个圆的弦，复杂场景下也会受限；大直径圆多出遮挡较大时，内接三角形方法也很难保证精度和有效性。智能优化算法在圆检测中也得到了较为广泛的应用，如遗传算法、进化算法及深度学习等，这些方法在应用环境中，取得了较好的效果，但还存在一定的局限性，如无法很好检测小半径的圆、真实图像的提取效果表现不佳等问题。

技术实现要素：

4.本发明解决了传统圆检测算法中由于遮挡、噪声和复杂场景等带来的不稳定问题，本发明提供了一种新型圆检测方法。本发明通过初次圆参数邻域密度聚类把属于同一个圆的多数圆弧聚为一类，生成虚拟连通区域，然后对虚拟连通区域进行圆参数的二次计算和聚类，实现更为精准的获取每个圆的圆参数计算，最后对圆参数进行验证，得到了真实的圆参数数据。通过实验验证本发明算法抗干扰性好、准确率高、鲁棒性强等特点。
5.为解决上述技术问题，本发明采用的技术方案为：一种新型圆检测方法，按照以下步骤进行：
6.步骤1)角点检测及腐蚀
7.先采用harris角点检测方法对角点位置进行检测，并对角点位置进行腐蚀，使得原始图像中的交点和有折线的位置完全断开；
8.步骤2)连通区域标记
9.将角点位置腐蚀后，为了准确检测图像中的圆，对腐蚀后的图像按如下步骤进行
连通区域标记：
10.2.1用imageedge表示二值图像，用imagelabel表示标记矩阵，lvalue表示标记变量，初始值设为lvalue＝2，到二值图像imageedge上为1的第一个点，将该位置标记为imagelabel(i,j)＝lvalue，之后，搜索该像素点的8邻域内所有像素值为1的像素点坐标，并将像素点的坐标信息保存入堆栈空间；
11.2.2取出步骤2.1中堆栈空间的一个位置点，并将标记矩阵imagelabel的该位置点置为lvalue，同时搜索该位置点的8邻域内所有像素值为1像素点坐标，并相应坐标信息保存入堆栈空间；
12.2.3重复步骤2.2，直至取出所有的堆栈中存储的点坐标信息，完成一次8邻域连通区域的标记；
13.2.4寻二值图像中下一个像素值为1的像素点，并更新标记变量lvalue＝lvalue+1，将标记矩阵imagelabel的该位置点置为lvalue，之后，继续搜索该像素点的8邻域内所有像素值为1的像素点，并将像素点的坐标信息保存入堆栈空间，转入步骤2.2，直至二值图像imageedge中所有为1的像素点均被遍历，完成连通区域的标记，得到标记矩阵imagelabel；
14.2.5统计标记矩阵imagelabel中的每个连通区域的大小，设定连通区域的提取阈值，阈值一般设为20，低于阈值的连通区域删除，删除后得到新的标记矩阵记为fimagelabel；
15.步骤3)连通区域圆参数计算
16.为了准确的检测复杂背景下的圆，根据已经得到的连通区域的标记结果，进行圆参数的具体计算，具体步骤如下：
17.3.1提取标记图像fimagelabel中的一块连通域ci；
18.3.2在连通区域ci上随机取一点然后在与点距离大于等于1/3长度位置的同一连通区域上随机取第二个点最后在与两个点的距离都大于等于1/3长度位置的同一连通区域上随机取上第三个点
19.3.3根据连通区域的圆参数的定义，可计算得三个点确定的圆的圆参数(x,y,r)，为了减小计算量，避免三个点在近似的一条直线上可能出现超大值的问题，算法要求(x,y,r)需满足公式(9)，同时将连通区域的标记号加入满足式子(9)圆参数(x,y,r)数据中，得到(x,y,r,ci)并存储，其中ci是连通区域的标记号，w是图像宽度，h是图像高度，每块连通区域得到圆参数的总数一般连通区域大小的3倍。
[0020][0021]
3.4取出标记图像fimagelabel的下一块连通区域c
i+1
，转到步骤3.2，继续计算新的连通区域的圆参数，直至遍历了所有连通区域，完成所有连通区域的圆参数计算。
[0022]
步骤4)计算圆参数数据的密度分布
[0023]
根据圆参数的密度定义，计算圆参数数据的密度分布，具体步骤如下：
[0024]
4.1根据圆参数的x、y、z三个坐标轴的最大值maxx、maxy、maxz与最小值minx、miny、minz，以间隔g将圆参数数据划分为多个密度立方块；
[0025]
4.2依据公式(7)求取每个密度立方块的密度值，
[0026][0027]
其中，nj为立方块j内的数据d
i,j
的个数，g为立方块的边长；
[0028]
4.3建立有效密度块存储空间，根据有效密度块公式(8)计算每一个密度立方块的有效性，有效的置1，无效的清零；
[0029][0030]
其中，d
th
为密度阈值，按公式(8)将大于等于阈值d
th
的密度块edj称为有效密度块，并置1，小于阈值d
th
的密度块edj称为无效密度块，并清零；
[0031]
步骤5)邻域聚密度类法
[0032]
得到了有效密度块后，圆参数的数据量减小了很多，为了进一步确定这些圆参数数据所属的圆，利用邻域聚类法进行计算，具体步骤如下：
[0033]
5.1邻域定义：三维空间3
×3×
3的邻域中共有27个元素，中心核心元素周围共有26个元素相邻；
[0034]
5.2初始化邻域聚类簇数k＝2，初始化未访问样本集合γ＝ed，簇划分c＝φ；
[0035]
5.3在有效密度块ed上的随机选择一个有效密度块a1，初始化当前簇样本集合c
k-1
＝{a1},更新未访问样本集合γ＝γ-{a1}，搜索该有效密度块a1的邻域内所有的有效密度块，并保存a1所有邻域内的有效密度块的位置信息；
[0036]
5.4取出保存的一个有效密度块ai，同时搜索该有效密度块ai的邻域内所有的有效密度块，并相应有效密度块的位置信息一并保存，更新当前簇样本集合c
k-1
＝{a1,ai}和未访问样本集合γ＝γ-{a1,ai}；
[0037]
5.5重复步骤5.4，直至取出所有的存储空间中的有效密度块，当前邻域的有效密度块聚类簇c
k-1
生成完毕；
[0038]
5.6若γ＝φ，则算法结束，否则更新簇划分c＝{c1,c2,
…
,c
k-1
}，更新k＝k+1，转入步骤5.3；
[0039]
5.7完成有效密度块聚类后，根据有效密度块的聚类编号，将相应的密度块内的数据给一相同聚类编号，即完成了圆参数数据的聚类操作；
[0040]
步骤6)优化密度聚类结果
[0041]
当前每个有效的圆参数数据均有其分类标记号，统计类标记号相同的圆参数数据占总数据量的百分比dpi，设定阈值dp
th
，则按公式(10)优化分类数据，优化后，基本去除了有效密度块的噪声点，留下了集中在一起的圆参数数据，再对保留的圆参数数据进行重新标记分类号；
[0042][0043]
步骤7)虚拟连通区域的生成
[0044]
为了进一步准确的得到被检测圆的圆心和半径参数，将属于同一聚类结果的数据所在的圆弧标记为了同一连通区域，此连通区域并非真实的连通关系，因此将这种非真实的连通关系的连通区域定义为虚拟连通区域，虚拟连通区域的生成方法如公式(11)，其中
cirvcaj表示邻居聚类结果的第j类数据生成的虚拟连通区域，ca
ji
邻居聚类结果的第j类数据中的第i个圆弧；
[0045]
cirvcaj＝uca
ji
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(11)
[0046]
步骤8)虚拟连通区域的圆参数计算及聚类
[0047]
通过步骤7)得到了虚拟连通区域标记结果，属于同一圆的圆弧标记为了同一类数据，此时，把属于同一个圆的圆弧看成了一个连通区域，也即得到一个虚拟连通区域；按照上述步骤3)中方法二次计算圆参数数据，步骤4)的方法计算圆参数数据的密度分布后，再按步骤5)方法进行邻域密度聚类计算，得到的了最终的聚类结果；
[0048]
步骤9)各个圆圆参数的确定
[0049]
每一个聚类区域都是有若干个圆参数点组成，选取哪一个点作为该圆的圆参数，也是决定了圆检测的精准度，从理论上说，越接近实际圆参数的位置，数据密度越大，而在越远离实际圆参数的位置，数据密度越稀疏，为此，数据的核心点位置应该到其他圆参数点的距离和最小，用公式(12)计算点pi到所有聚类点的距离和，其中n为当前聚类区域的圆参数点数，然后取spi最小值对应的圆参数点作为该聚类区域的圆参数，也即得到了当前聚类区域对应的圆的圆参数；
[0050][0051]
步骤10)圆参数的验证
[0052]
为了保证圆参数数据的正确性，对计算获得的圆参数进行验证，由于当前求得圆参数均是以像素为单位的，因此统计第i个圆中参与计算的虚拟连通区域的像素点数spni，然后，再以第i个圆的圆参数画圆，统计该圆圆周轨迹上对应圆边缘信息的像素点数cpni，按公式(13)确定圆的真假，真圆的圆参数保留，否则删除，得到最终的检测结果；
[0053][0054]
本发明的优点及其积极效果是：本发明方法主要用于复杂场景下的圆参数检测，旨在尝试解决传统圆检测算法中由于遮挡、噪声和复杂场景等带来的不稳定问题。本发明方法通过初次圆参数邻域密度聚类把属于同一个圆的多数圆弧聚为一类，生成虚拟连通区域，然后对虚拟连通区域进行圆参数的二次计算和聚类，实现更为精准的获取每个圆的圆参数计算，最后对圆参数进行验证，得到了真实圆的圆参数。实验结果表明该算法抗干扰性好、准确率高、鲁棒性强等特点。
附图说明
[0055]
图1为二值图像及其连通区域标记结果。其中(a)为二值图像，(b)为连通区域标记结果。
[0056]
图2为角点检测及腐蚀结果。其中(a)为原始二值图像，(b)为角点检测结果，(c)为角点腐蚀后结果。
[0057]
图3为连通区域标记结果。
[0058]
图4为圆参数计算结果。
[0059]
图5为圆参数密度块划分结果。
[0060]
图6为有效密度块标记结果。
[0061]
图7为有效密度块中圆参数数据。
[0062]
图8为三维邻域示意图。其中(a)为26邻域示意图，(b)为18邻域示意图，(c)为6邻域示意图。
[0063]
图9为有效密度块优化结果。
[0064]
图10为连通区域圆参数数据聚类结果。
[0065]
图11为虚拟连通区域标记结果。
[0066]
图12为二次圆参数计算后虚拟连通区域圆参数数据显示结果。
[0067]
图13为二次圆参数计算后虚拟连通区域圆参数聚类结果。
[0068]
图14为本发明实施例圆检测结果。
具体实施方式
[0069]
为使本发明的目的、特征和优点能够更为明显易懂，下面对本发明的具体实施方式做详细的说明。
[0070]
为了更好的理解本发明的圆检测方法，再进行描述之前，先对连通区域的圆参数以及圆参数密度进行定义。
[0071]
连通区域的圆参数定义
[0072]
图1是二值图像及其连通区域标记结果，标记结果中每一个连通区域用一种灰度表示，并用c1、c2、..对连通区域标号，其中用c表示圆周上任意一段标记区域。以图像的左下角为坐标原点，水平向右为x轴正方向，垂直向上为y轴正方向，建立图像坐标系，则图像上的点p
1c
(x
1c
,y
1c
)、p
2c
(x
2c
,y
2c
)、p
3c
(x
3c
,y
3c
)是属于连通区域c的间隔大于g
l
三个任意点，其中g
l
是连通区域最大长度的1/3。
[0073]
由图1可知，复杂背景下随机取点计算圆参数，会得到很多无效圆参数数据，因此，本发明中基于某一连通区域，在距离大于等于g
l
的条件下，随机提取了p
1c
、p
2c
、p
3c
三个点，将此连通区域中三点确定的圆参数定义为连通区域的圆参数，用公式(1)、(2)、(3)表示。
[0074][0075][0076][0077]
其中a＝(x
1c
+x
3c
)/2、b＝(y
1c
+y
3c
)/2、c＝(x
1c
+x
2c
)/2、d＝(y
1c
+y
2c
)/2、k
12
＝(y
1c-y
2c
)/(x
1c-x
2c
)、k
13
＝(y
1c-y
3c
)/(x
1c-x
3c
)，明显，当k
12
＝k
13
时，三点在同一条直线上，不能得到有效的圆参数，舍弃此种情况的计算结果。
[0078]
圆参数密度的定义
[0079]
假设圆参数样本集是d＝(d1,d2,
…
,dm)，则圆参数密度描述定义如下：
[0080]
1)建立坐标系：对于di∈d，di是一个三维数据(x,y,r)，建立三维坐标系(x,y,z)，即将圆参数数据(x,y,r)，映射到了三维坐标下(x,y,z)。
[0081]
2)密度块的划分：为了表征圆参数数据分布的疏密程度，分别取x、y、z三个方向的
最大值maxx、maxy、maxz与最小值minx、miny、minz，设间隔距离为g，分别用公式(4)、(5)、(6)画平面，则建立多个边长为g的立方块。
[0082]
x＝kg,k为整数，且
[0083]
y＝mg,m为整数，且
[0084]
z＝ng,n为整数，且
[0085]
3)密度块内的密度计算：对于任意di∈d，必定落于某一立方块j内，记为d
i,j
，设立方块j内的数据d
i,j
的个数为nj，则立方块j的密度定义为公式(7)
[0086][0087]
4)有效密度块：设定密度阈值d
th
，按公式(8)将大于等于阈值d
th
的密度块edj称为有效密度块，并置1，小于阈值d
th
的密度块edj称为无效密度块，并清零。
[0088][0089]
上面对先对连通区域的圆参数以及圆参数密度进行了定义，在此定义的基础上，下面再对本发明的基于邻域聚类的圆检测方法进行具体的介绍，具体步骤如下：
[0090]
步骤1)角点检测及腐蚀
[0091]
对于真实图像需要进行边缘检测，为了避免边缘检测算法优劣的影响，本实施例中采用复杂的合成图像来说明算法，如图2(a)，待检测圆的圆弧会与背景或是其他待检测圆的圆弧有多处相交，如果直接计算圆参数，不仅计算量大，而且很难保证准确性，为了更准确检测圆，本发明在做计算之前采用harris角点检测方法对角点位置进行检测，检测结果见图3(b)，并对角点位置进行腐蚀，使得原始图像中的交点和有折线的位置完全断开，这些连通区域的分割结果如图3(c)。
[0092]
步骤2)连通区域标记
[0093]
将角点位置腐蚀后，得到了图2(c)的结果，为了准确检测图像中的圆，首先对腐蚀后的图像按如下步骤进行连通区域标记。
[0094]
2.1)用imageedge表示图2(c)中的二值图像，用imagelabel表示标记矩阵，lvalue表示标记变量，初始值设为lvalue＝2，到二值图像imageedge上为1的第一个点，将该位置标记为imagelabel(i,j)＝lvalue，之后，搜索该像素点的8邻域内所有像素值为1的像素点坐标，并将像素点的坐标信息保存入堆栈空间；
[0095]
2.2)取出2.1)中堆栈空间的一个位置点，并将标记矩阵imagelabel的该位置点置为lvalue，同时搜索该位置点的8邻域内所有像素值为1像素点坐标，并相应坐标信息保存入堆栈空间；
[0096]
2.3)重复步骤2.2)，直至取出所有的堆栈中存储的点坐标信息，完成一次8邻域连通区域的标记；
[0097]
2.4)寻二值图像中下一个像素值为1的像素点，并更新标记变量lvalue＝
lvalue+1，将标记矩阵imagelabel的该位置点置为lvalue，之后，继续搜索该像素点的8邻域内所有像素值为1的像素点，并将像素点的坐标信息保存入堆栈空间，转入步骤2.2)，直至二值图像imageedge中所有为1的像素点均被遍历，完成连通区域的标记，得到标记矩阵imagelabel；
[0098]
2.5)统计标记矩阵imagelabel中的每个连通区域的大小，设定连通区域的提取阈值，阈值一般设为20，低于阈值的连通区域删除，删除后得到新的标记矩阵记为fimagelabel。
[0099]
为了更好的表示连通区域标记结果，将标记矩阵中每种不同数值用不同灰度表示，可得到灰度标记图像如图3。
[0100]
步骤3)连通区域圆参数计算
[0101]
为了准确的检测复杂背景下的圆，前文中定义了连通区域圆参数的计算方法，图3中已经得到了连通区域的标记结果，则圆参数的具体计算步骤如下：
[0102]
3.1)提取标记图像fimagelabel中的一块连通域ci；
[0103]
3.2)在连通区域ci上随机取一点然后在与点距离大于等于1/3长度位置的同一连通区域上随机取第二个点最后在与两个点的距离都大于等于1/3长度位置的同一连通区域上随机取上第三个点
[0104]
3.3)根据连通区域的圆参数的定义，可计算得三个点确定的圆的圆参数(x,y,r)，为了减小计算量，避免三个点在近似的一条直线上可能出现超大值的问题，算法要求(x,y,r)需满足公式(9)，同时将连通区域的标记号加入满足式子(9)圆参数(x,y,r)数据中，得到(x,y,r,ci)并存储，其中ci是连通区域的标记号，w是图像宽度，h是图像高度，每块连通区域得到圆参数的总数一般连通区域大小的3倍。
[0105][0106]
3.4)取出标记图像fimagelabel的下一块连通区域c
i+1
，转到步骤3.2)，继续计算新的连通区域的圆参数，直至遍历了所有连通区域，完成所有连通区域的圆参数计算，计算结果如图4。
[0107]
步骤4)计算圆参数数据的密度分布
[0108]
根据前文中圆参数的密度定义，计算圆参数数据的密度分布。
[0109]
4.1)根据圆参数的x、y、z三个坐标轴的最大值maxx、maxy、maxz与最小值minx、miny、minz，以间隔g将圆参数数据划分为多个密度立方块，结果如图5。
[0110]
4.2)依据公式(7)求取每个密度立方块的密度值。
[0111]
4.3)建立有效密度块存储空间，根据有效密度块公式(8)计算每一个密度立方块的有效性，有效的置1，无效的清零，有效密度块标记结果如图6。
[0112]
步骤5)邻域聚密度类法
[0113]
得到了有效密度块后，从图7可以看出，圆参数的数据量减小了很多，为了进一步确定这些圆参数数据所属的圆，本发明提出了邻域聚类法，具体步骤如下：
[0114]
5.1)邻域定义：三维空间3
×3×
3的邻域中共有27个元素，如图8(a)中心核心元素周围共有26个红元素相邻，根据中心元素与相邻元素的关系，三维空间中一般采用如图8
(a)、8(b)、8(c)所示的26邻域、18邻域及6邻域等邻域情况，本实施例采用图8(a)的26邻域。
[0115]
5.2)初始化邻域聚类簇数k＝2，初始化未访问样本集合γ＝ed，簇划分c＝φ。
[0116]
5.3)在有效密度块ed上的随机选择一个有效密度块a1，初始化当前簇样本集合c
k-1
＝{a1},更新未访问样本集合γ＝γ-{a1}，搜索该有效密度块a1的邻域内所有的有效密度块，并保存a1所有邻域内的有效密度块的位置信息；
[0117]
5.4)取出保存的一个有效密度块ai，同时搜索该有效密度块ai的邻域内所有的有效密度块，并相应有效密度块的位置信息一并保存，更新当前簇样本集合c
k-1
＝{a1,ai}和未访问样本集合γ＝γ-{a1,ai}；
[0118]
5.5)重复步骤5.4)，直至取出所有的存储空间中的有效密度块，当前邻域的有效密度块聚类簇c
k-1
生成完毕；
[0119]
5.6)若γ＝φ，则算法结束，否则更新簇划分c＝{c1,c2,
…
,c
k-1
}，更新k＝k+1，转入步骤3)。
[0120]
5.7)完成有效密度块聚类后，根据有效密度块的聚类编号，将相应的密度块内的数据给一相同聚类编号，即完成了圆参数数据的聚类操作，聚类结果如图9。
[0121]
步骤6)优化密度聚类结果
[0122]
由图6有效密度块标记结果来看，是有部分独立的密度块存在，我们认为这种有效密度块是噪声点，这种噪声点对分类结果有一定的干扰作用，因此对分类结果进一步优化。当前每个有效的圆参数数据均有其分类标记号，统计类标记号相同的圆参数数据占总数据量的百分比dpi，设定阈值dp
th
，则按公式(10)优化分类数据。优化后，基本去除了有效密度块的噪声点，留下了集中在一起的圆参数数据，再对保留的圆参数数据进行重新标记分类号，有效密度块优化结果及相应数据如图10。
[0123][0124]
步骤7)虚拟连通区域的生成
[0125]
优化邻域聚类计算完成后，将所有的圆参数数据根据密度和邻域关系分成了不同类，由图10可知，被聚为同一类的圆参数数据，基本来自于同一个圆的一个或多个圆弧，这也说明邻域聚类法可以很好的实现圆检测，由于多个独立圆弧得到的圆参数数据的收敛性一般劣于多个圆弧同时参与计算得到的圆参数的精度，为了进一步准确的得到被检测圆的圆心和半径参数，文中将属于同一聚类结果的数据所在的圆弧标记为了同一连通区域，此连通区域并非真实的连通关系，因此本发明中将这种非真实的连通关系的连通区域定义为虚拟连通区域，虚拟连通区域的生成方法如公式(11)，其中cirvcaj表示邻居聚类结果的第j类数据生成的虚拟连通区域，ca
ji
邻居聚类结果的第j类数据中的第i个圆弧。最终生成的连通区域如图11。
[0126]
cirvcaj＝uca
ji
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(11)
[0127]
步骤8)虚拟连通区域的圆参数计算及聚类
[0128]
由上述步骤得7)到了虚拟连通区域标记结果，属于同一圆的圆弧标记为了同一类数据，此时，把属于同一个圆的圆弧看成了如前文所属的一个连通区域，也即得到一个虚拟连通区域。一般情况，虚拟连通区域由一个或多个连通区域组成，此时，按前文方法计算得到的圆参数的准确性更高，而且数据的集中性更为密集，更容易准确的获取圆的圆参数。为
此，按步骤3)方法二次计算圆参数数据，计算结果显示图如图12所示，与图4对比可以看出，二次计算的圆参数数据，一是更为密集了，二是离散的圆参数数据量明显少了很多，这也再次说明，通过第一次聚类后，基本把圆弧的边缘连通区域保留了下来，而与圆弧差别较大的边缘连通区域则被删除。再按步骤5)方法进行邻域密度聚类计算，得到的了最终的聚类结果如图13，从聚类结果可以看出圆参数数据集中于30个互不关联的区域，这30个区域实际代表图2(a)中的30个大小不同的圆。
[0129]
步骤9)各个圆圆参数的确定
[0130]
如图7(b)所示，每一个聚类区域都是有若干个圆参数点组成，选取哪一个点作为该圆的圆参数，也是决定了圆检测的精准度，从理论上说，越接近实际圆参数的位置，数据密度越大，而在越远离实际圆参数的位置，数据密度越稀疏，为此，数据的核心点位置应该到其他圆参数点的距离和最小，可用公式(12)计算点pi到所有聚类点的距离和，其中n为当前聚类区域的圆参数点数，然后取spi最小值对应的圆参数点作为该聚类区域的圆参数，也即得到了当前聚类区域对应的圆的圆参数。
[0131][0132]
步骤10)圆参数的验证
[0133]
为了保证圆参数数据的正确性，对计算获得的圆参数进行验证。由于当前求得圆参数均是以像素为单位的，因此统计第i个圆中参与计算的虚拟连通区域的像素点数spni。然后，再以第i个圆的圆参数画圆，统计该圆圆周轨迹上对应圆边缘信息的像素点数cpni，按公式(13)确定圆的真假，真圆的圆参数保留，否则删除，得到最终的检测结果。圆检测结果见图14，其中红部分表示圆检测结果，由结果可知已经完全把图像中包含的圆全部准确检测出来，并且包含了部分圆心在图像之外的情况。
[0134][0135]
本发明的主要贡献有(1)提出了一种连通标记区域的圆参数计算法方法。(2)提出了一种邻域密度聚类算法，为圆参数的检测提供了这一种新方法。(3)依据邻域密度聚类算法，实现了多种场景下的圆检测，由实验结果可知，文中算法对复杂场景、遮挡、噪声等都有较好的适应性。
[0136]
上面对本发明的实施例作了详细说明，但是本发明并不限于上述实施例，在本领域普通技术人员所具备的知识范围内，还可以在不脱离本发明宗旨的前提下做出各种变化。

技术特征：

1.一种新型圆检测方法，其特征在于：按照以下步骤进行：步骤1)角点检测及腐蚀先采用harris角点检测方法对角点位置进行检测，并对角点位置进行腐蚀，使得原始图像中的交点和有折线的位置完全断开；步骤2)连通区域标记将角点位置腐蚀后，为了准确检测图像中的圆，对腐蚀后的图像按如下步骤进行连通区域标记：2.1用imageedge表示二值图像，用imagelabel表示标记矩阵，lvalue表示标记变量，初始值设为lvalue＝2，到二值图像imageedge上像素值为1的第一个点，将该位置标记为imagelabel(i,j)＝lvalue，之后，搜索该像素点的8邻域内所有像素值为1的像素点坐标，并将像素点的坐标信息保存入堆栈空间；2.2取出步骤2.1中堆栈空间的一个位置点，并将标记矩阵imagelabel的该位置点置为lvalue，同时搜索该位置点的8邻域内所有像素值为1像素点坐标，并相应坐标信息保存入堆栈空间；2.3重复步骤2.2，直至取出所有的堆栈中存储的点坐标信息，完成一次8邻域连通区域的标记；2.4寻二值图像中下一个像素值为1的像素点，并更新标记变量lvalue＝lvalue+1，将标记矩阵imagelabel的该位置点置为lvalue，之后，继续搜索该像素点的8邻域内所有像素值为1的像素点，并将像素点的坐标信息保存入堆栈空间，转入步骤2.2，直至二值图像imageedge中所有为1的像素点均被遍历，完成连通区域的标记，得到标记矩阵imagelabel；2.5统计标记矩阵imagelabel中的每个连通区域的大小，设定连通区域的提取阈值，阈值一般设为20，低于阈值的连通区域删除，删除后得到新的标记矩阵记为fimagelabel；步骤3)连通区域圆参数计算为了准确的检测复杂背景下的圆，根据已经得到的连通区域的标记结果，进行圆参数的具体计算，具体步骤如下：3.1提取标记图像fimagelabel中的一块连通域c
i
；3.2在连通区域c
i
上随机取一点然后在与点距离大于等于1/3长度位置的同一连通区域上随机取第二个点最后在与两个点的距离都大于等于1/3长度位置的同一连通区域上随机取上第三个点3.3根据连通区域的圆参数的定义，可计算得三个点确定的圆的圆参数(x,y,r)，为了减小计算量，避免三个点在近似的一条直线上可能出现超大值的问题，算法要求(x,y,r)需满足公式(9)，同时将连通区域的标记号加入满足式子(9)圆参数(x,y,r)数据中，得到(x,y,r,c
i
)并存储，其中c
i
是连通区域的标记号，w是图像宽度，h是图像高度，每块连通区域得到圆参数的总数一般连通区域大小的3倍。3.4取出标记图像fimagelabel的下一块连通区域c
i+1
，转到步骤3.2，继续计算新的连通区域的圆参数，直至遍历了所有连通区域，完成所有连通区域的圆参数计算。
步骤4)计算圆参数数据的密度分布根据圆参数的密度定义，计算圆参数数据的密度分布，具体步骤如下：4.1根据圆参数的x、y、z三个坐标轴的最大值maxx、maxy、maxz与最小值minx、miny、minz，以间隔g将圆参数数据划分为多个密度立方块；4.2依据公式(7)求取每个密度立方块的密度值，其中，n
j
为立方块j内的数据d
i,j
的个数，g为立方块的边长；4.3建立有效密度块存储空间，根据有效密度块公式(8)计算每一个密度立方块的有效性，有效的置1，无效的清零；其中，d
th
为密度阈值，按公式(8)将大于等于阈值d
th
的密度块ed
j
称为有效密度块，并置1，小于阈值d
th
的密度块ed
j
称为无效密度块，并清零；步骤5)邻域聚密度类法得到了有效密度块后，圆参数的数据量减小了很多，为了进一步确定这些圆参数数据所属的圆，利用邻域聚类法进行计算，具体步骤如下：5.1邻域定义：三维空间3
×3×
3的邻域中共有27个元素，中心核心元素周围共有26个元素相邻；5.2初始化邻域聚类簇数k＝2，初始化未访问样本集合γ＝ed，簇划分c＝φ；5.3在有效密度块ed上的随机选择一个有效密度块a1，初始化当前簇样本集合c
k-1
＝{a1},更新未访问样本集合γ＝γ-{a1}，搜索该有效密度块a1的邻域内所有的有效密度块，并保存a1所有邻域内的有效密度块的位置信息；5.4取出保存的一个有效密度块a
i
，同时搜索该有效密度块a
i
的邻域内所有的有效密度块，并相应有效密度块的位置信息一并保存，更新当前簇样本集合c
k-1
＝{a1,a
i
}和未访问样本集合γ＝γ-{a1,a
i
}；5.5重复步骤5.4，直至取出所有的存储空间中的有效密度块，当前邻域的有效密度块聚类簇c
k-1
生成完毕；5.6若γ＝φ，则算法结束，否则更新簇划分c＝{c1,c2,
…
,c
k-1
}，更新k＝k+1，转入步骤5.3；5.7完成有效密度块聚类后，根据有效密度块的聚类编号，将相应的密度块内的数据给一相同聚类编号，即完成了圆参数数据的聚类操作；步骤6)优化密度聚类结果当前每个有效的圆参数数据均有其分类标记号，统计类标记号相同的圆参数数据占总数据量的百分比dp
i
，设定阈值dp
th
，则按公式(10)优化分类数据，优化后，基本去除了有效密度块的噪声点，留下了集中在一起的圆参数数据，再对保留的圆参数数据进行重新标记分类号；
步骤7)虚拟连通区域的生成为了进一步准确的得到被检测圆的圆心和半径参数，将属于同一聚类结果的数据所在的圆弧标记为了同一连通区域，此连通区域并非真实的连通关系，因此将这种非真实的连通关系的连通区域定义为虚拟连通区域，虚拟连通区域的生成方法如公式(11)，其中cirvca
j
表示邻居聚类结果的第j类数据生成的虚拟连通区域，ca
ji
邻居聚类结果的第j类数据中的第i个圆弧；cirvca
j
＝uca
ji
ꢀꢀꢀ
(11)步骤8)虚拟连通区域的圆参数计算及聚类通过步骤7)得到了虚拟连通区域标记结果，属于同一圆的圆弧标记为了同一类数据，此时，把属于同一个圆的圆弧看成了一个连通区域，也即得到一个虚拟连通区域；按照上述步骤3)中方法二次计算圆参数数据，步骤4)的方法计算圆参数数据的密度分布后，再按步骤5)方法进行邻域密度聚类计算，得到的了最终的聚类结果；步骤9)各个圆圆参数的确定每一个聚类区域都是有若干个圆参数点组成，选取哪一个点作为该圆的圆参数，也是决定了圆检测的精准度，从理论上说，越接近实际圆参数的位置，数据密度越大，而在越远离实际圆参数的位置，数据密度越稀疏，为此，数据的核心点位置应该到其他圆参数点的距离和最小，用公式(12)计算点p
i
到所有聚类点的距离和，其中n为当前聚类区域的圆参数点数，然后取sp
i
最小值对应的圆参数点作为该聚类区域的圆参数，也即得到了当前聚类区域对应的圆的圆参数；步骤10)圆参数的验证为了保证圆参数数据的正确性，对计算获得的圆参数进行验证，由于当前求得圆参数均是以像素为单位的，因此统计第i个圆中参与计算的虚拟连通区域的像素点数spn
i
，然后，再以第i个圆的圆参数画圆，统计该圆圆周轨迹上对应圆边缘信息的像素点数cpn
i
，按公式(13)确定圆的真假，真圆的圆参数保留，否则删除，得到最终的检测结果；

技术总结

本发明是一种新型圆检测方法，属于模式识别算法领域，旨在尝试解决传统圆检测算法中由于遮挡、噪声和复杂场景等带来的不稳定问题；本发明方法通过初次圆参数邻域密度聚类把属于同一个圆的多数圆弧聚为一类，生成虚拟连通区域，然后对虚拟连通区域进行圆参数的二次计算和聚类，实现更为精准的获取每个圆的圆参数计算，最后对圆参数进行验证，得到了真实的圆参数数据；实验结果表明该算法抗干扰性好、准确率高、鲁棒性强等特点。鲁棒性强等特点。鲁棒性强等特点。