题目：一种快速有效的椭圆检测
绪论
对于几何形状的数学模型通常被描述为模式识别。
这种在有噪声的杂乱的图像中探测参数形状的企图导致了直线，圆形算法的成功。它们都基于accumulations/voting程序（霍夫变换Hough–based methods），差值interpolation，圆弧 curve fitting 等。
相似的，椭圆检测超越了过去（？），虽然椭圆检测有更多参数复杂的圆弧（由于大量的参数），因为椭圆在自然界和项目中的常见，椭圆检测是许多计算机视觉应用的起点。举例来说，椭圆检测可以用于车轮检测，信号检测和分类，工业应用的目标分割，细胞显微图像的自动分割，瞳孔追踪等。随着强大的移动技术的出现和新一代智能手机的普及，这些设备上运行的新应用程序的需求大幅增加。尽管有其局限性，移动设备现在已经足够强大以支持复杂数据的板载处理，包括声音及图像。因此，科学界最近对在手机上处理图像/声音产生了极大的兴趣，经常称为embedded or mobile vision。可能应用于试试目标/人物跟踪，基于内容的无标记物体识别框架式场景检索，面部识别，盲人协助行动等。因此，尽管技术和多核处理器的进步将允许更快的计算，但保持快速的椭圆检测具有允许日益复杂的计算机视觉应用的优点。
因此，在本文中，我们提出了一种用于实时图像中快速椭圆检测的新解决方案。我们通过在弧级而不是像素级工作，并依靠创新的选择策略，非常快速和非常可靠地选择属于同一椭圆的弧。然后估计椭圆中心，利用平行和弦的中点的特性，并且剩余的参数被估计在分解的参数空间中积累投票。 效率（每幅图像10毫秒左右）和精度之间的良好折衷使得这种方法成为移动设备上实现的合适候选者。
本文的其余部分描述了椭圆检测的最新技术（第2节），主要集中在快速算法上。 第3节详细描述了所提出的方法，其结果超越了所有现有的快速方法。第4节分析了新颖性和不同参数的影响，并与其他可能的方法进行比较。 为了证明这一性能，第5节报告了几个关于合成和真实图像的实验，包括用移动设备捕获的数据集。 评估效率和有效性。 第6节总结了该论文的贡献。
2.相关工作
一般都用HF方法，评估需要一组边缘点。使用多组连接的边缘像素即弧可以实现更好的表征，其可以通过链接短直线，分割边缘轮廓或验证连接的边缘像素而生成。 使用椭圆拟合方法在缩减的弧集上获得椭圆参数，根据弧的相对位置和曲率约束或椭圆拟合误差对弧进行分组。
文献中大部分的作品都具有很高的检测精度。 但是，这些结果主要在几张合成图像上得到验证，除了超过10张真实图像外，很少有这些结果。 声称快速或实时的方法的执行时间也是在少量图像上计算的，并且可能会在不同种类的图像上显着增加。 在本文中，我们提出了一种新的方法（可以发现椭圆检测的初步工作，其结果是比其他最先进的方法快得多，同时获得相似甚至更好的检测性能，我们还提供了两个带注释的数据集 （可在线获取）真实图像，我们测试了快速和有效的方法以进行公平评估。
3.方法描述
我们提出了一种新颖的快速椭圆检测算法，用于在真实世界图像上实时执行性能。 它首先选择属于相同椭圆的弧的组合，然后通过Hough变换在分解的参数空间中估计其参数。 首先让我们描述一下总体程序，如图1所述。
作为第一步，从边缘掩模中提取弧，并根据它们的凸性将其分为四类。 我们根据它们的梯度相位和相同方向类中的8个连接的边缘像素对两个主方向上的边缘像素进行分类以形成弧。 他们的质量也得到了改善，消除短或直弧。 然后根据它们的凸面对弧进行分类，并以稳健和有效的方式进行计算。 通过组合这两个分类，可以将每个弧分配给象限，类似于如fig2(c)所示的笛卡尔平面中的最终配置。该方法适用于检测可见椭圆，定义为在至少三个象限中边界部分可见。 因此，我们搜索三个弧的组合，称为三元组，每个属于不同的象限。 为了避免组合爆炸，我们只选择由圆弧组成的三元组，其满足三个基于凸性，相互位置和相同的成对估计中心的标准。选定的三元组形成候选椭圆，并且已经知道其中心，我们估计剩余的三个参数在分解的霍夫空间中，需要三个1D累加器。 然后根据估计与实际边缘像素的适合度对候选椭圆进行验证。 由于椭圆可以由不同的三元组支持，因此可以生成具有稍微不同的参数的多个检测。 我们使用参数空间中的快速聚类过程处理多个检测。
以下小节将详细描述算法的不同阶段。
3.1 弧提取
在这个阶段，我们从输入图像中提取弧，首先通过检测边缘点，然后将它们分组在弧中，最后根据边缘方向和凸面对弧进行分类。
3.1.1 边缘检测（用canny函数即可）
与大多数一样，所提出的方法也开始分析边缘点，其中每个边缘点ei=（xi，yi，θi）由其位置xi，yi和梯度θi的相位来定义。 为了获得一组边缘点，我们在输入图像上应用边缘检测器。我们选择带自动阈值1的Canny边缘检测器，因为它具有良好的检测性能，良好的定位和最小的响应。 在检测到的边缘点中，梯度相位θi通过Sobel算子获得（已经在Canny算法中计算）。
3.1.2 圆弧检测
把所有边缘点用函数D分类为ei→（+，-），我们丢弃位于分类边界上的边缘点，丢弃位于分类边界上的边缘点，即水平或垂直梯度方向。 通过链接相同方向等级的连接的边缘点形成弧αk：
公式
3.1.2 圆弧凸面分类
这里的ak代表圆弧（点的集合），要对ak进行分类，ak→（+，-），具有向上凸面的为+，向下凸面的为-（外国人凹凸与中国人相反），如Fig2(b)所示。总之，对于所有属于ak的点eik都在BBk中，被分为两个区域，圆弧下方称为Uk，圆弧上分称为Ok（Fig3），然后用算法1计算。
我们通过比较区域Uk和Ok来找到凸面：
公式
如果区域Uk与Ok的面积相等，意味着获得了一个无意义的圆弧，丢弃它。
算法1
算法解释：
D(α)为+时，如图三所示求取圆弧α的C(α)；当D(α)为-时，交换U，O区域再进行计算
定义函数 getconvexity（输入是数组Point α[]）
第一段循环实现了area_o=0+∑|α[i].y-left.y|（像素的单位是1所以没有问题）
area_BB是最小外界矩形的点的个数
因此area_U=area_BB-area_O
比较结果，判断函数的输出为何。
公式
由之前的结果可以将圆弧分成四类（四个区间）
3.2 椭圆检测
我们定义候选的椭圆εi为一个三维数，即一系列三个圆弧τabc=（αa，αb，αc）满足一套标准，因此可能属于同一个椭圆。 然后在HT框架中计算每个εi的参数。
3.2.1 圆弧选择策略
令Nα=图像中圆弧的数量，T0是所有可能的三圆弧组合组成的集合。这个数字可能非常高，大多数三元组由不属于同一个椭圆的圆弧组成：大量的计算将浪费在估计错误检测的参数上。这个策略的目标是生成一个三元组的子集，这个子集中弧线是同一个椭圆的边界。
我们定义一对弧为pab=（αa，αb）。因此，三元组也可以定义为两对共享一个弧：τabc ={（pab，pdc）|αb=αd}。选择策略首先选择哪些弧满足（i）凸性和（ii）相互位置的约束。 然后它在相同的椭圆边界上工作。 最后，它发现候选圆弧是由两对组成的三元组，（iii）意味着相同的中心。
对凸性的第一个约束确保每对在后续象限中由弧组成（按逆时针顺序）：
第二个限制是，丢弃形状不一样的圆弧对。如Fig5，有如下公式：
其中L和R分别是第3.1.2节中定义的弧的最左边和最右边的极值，不等式≳和≲用第4.2节中研究的公差Thpos定义。 子集T2⊆T2仅包含其对与第一和第二约束相关的三元组：
第三个约束：验证三个弧αa，αb，αc是否在同一个椭圆的边界，相等的，验证由圆弧对pab，pdc获得的椭圆中心Cab，Cdc是否在一定阈值内（Thcenters）
公式见上图（9）
于是T3⊆T2满足上述三个条件，获得了候选椭圆。
第一个和第二个约束可以快速计算，并且仍然具有很强的区分性。 第三个计算更复杂，但是在更窄的集合上计算，并且极大地提高了候选椭圆的质量。 有关选择策略的更多细节，请参见第5.6节。
3.2.2 中心估计
我们通过一个众所周知的椭圆几何性质估计给定弧对的椭圆中心：平行弦的中点是共线的，如图Fig.6(a)。
因此，连接两组不同平行弦的中点的两条线的交点就是椭圆中心。
为了找到椭圆中心，我们需要生成两组彼此不平行的平行弦。 为了清楚起见，我们参照Fig.6(b)说明了对pan的处理过程。我们生成两组Ns弦，分别平行于线L a M b和R b M a（M是3.1.2节定义的弧的中点），倾斜r1ab，r2ab。在第4.2节中研究了参数Ns对整体性能的影响。
伪代码如下图：
给出一对弧pab，计算中点C如图Fig.6(b)，公式如下：
现在我们可以得到Cab，Cdc和两对弧pab，pdc，如果满足阈值条件。
3.2.3 参数估计
论文原文
椭圆的参数仅有3.2.2节获得的满足选择策略的三元数组得出。因此，通过定义，两对弧的直线l1，l2应该相交于椭圆中心。然而在有噪声的图像中很少实现，为了更好的评估参数，我们考虑椭圆的中心（xc，yc）为一组7个点的坐标的中值，包括两个中心Cab，Cdc，他们的平均值，和其他四个估计直线的交点{l1ab∩l1dc，l1ab∩l2dc，l2ab∩l1dc，l2ab∩l2dc
}如图8中的灰点所示。
为了找到剩余的参数，参数空间按照[15]中的半轴比N=B/A和方向ρ进行分解。 在推导[15,16,37]之后，N和ρ的值被计算为
对于表1中的参数q 1，q 2，q 3，q 4的每个组合累计一次投票。将q 1，q 3的值设置为平行和弦的斜率， q 2，q 4的值与由Theil-Sen估计器（算法2）计算的所有线的斜率相比较。 N和ρ的值是两个1D累加器中的最高峰值。
给定值N和ρ，长轴A的值为:
A的值在1D累加器中估计，考虑三个弧段αa，αb，αc中的每个边缘点ei（xi，yi），并取最高峰值。 那么最后一个参数的值是短轴B。
B=A×N
3.3 后期处理
选择策略为检测椭圆定义了三个必要但不充分的条件。 候选椭圆然后必须被验证以消除错误的检测。 此外，在同一个椭圆的边界上可能会找到多个三元组，从而生成需要合并的同一个椭圆的多个检测。 由于候选椭圆的数量远小于弧的数量，所以合并多个检测比在早期阶段找到位于相同椭圆的边界上的所有弧更有效。
3.3.1 验证
一个有质量的测量被分配给每个候选椭圆εi。 回想一下，我们可以根据椭圆方程得到εi的边界点（xi，yi）：
我们可以定义点集 B={(xi,yi):|f(xi,yi,εi)-1<0.1|}，点集B包含接近边界的点。 分数δ∈[0,1]总结了构成εi的三个弧的点与估计的椭圆的边界吻合的程度：
如果分数δ大于阈值（Thscore），考虑候选椭圆有效，否则将丢弃它。
3.3.2 聚类
通过采用[38]中描述的方法的变体将相同椭圆的多个有效检测聚类，该方法允许评估两个椭圆εi，εj的相似性; 通过分别比较椭圆中心（26），轴（27）和（28）和旋转（29）之间的距离：
定义了一个衡量两个椭圆的函数，见上图（20）
所有有效的椭圆按降序进行排序，并通过函数Δ逐一与每个簇的中心进行比较。
我们将最高分数的椭圆视为给定聚类的中心。 如果当前的椭圆不能被分配（即不等于）任何集群，它将成为新集群的中心。 参数根据[38]设置。
网友评论