论文阅读——椭圆检测 2017：A hybrid method for ellipse detection in industrial images
最近要复现论文，找了一篇发表在PR(1区)的一篇论文《A hybrid method for ellipse detection in industrial images》，这个可以理解为设计了一个应用于工业图像的椭圆检测算法。下面对其细节进行分析
目前的椭圆检测由于信号噪声的原因不适用于工业图像。本文提出了一个方法结合了基于边缘和基于HT的优点，能够检测分割多段的椭圆。方法主要分为两步：① 基于边缘链接的方法能够快速精确的提取出主要椭圆。② 对于无法检测出的小椭圆，使用基于HT的思想进行提取。
文章目录
- 1 介绍
- 2基于边缘的方法
- 2.3 候选椭圆弧段聚类
- Step 1: 寻找有高拟合精度的候选椭圆弧段，并将其作为种子弧段
- Step 2：确定每个种子弧段的搜索区域
- Step 3：在每个种子点的搜索区间内，查找其相关的边缘弧段
- Step 4：确定组合的弧段是否在同一个椭圆上
- 2.4 从分组弧中提取椭圆及其验证结果
- Step 1： 将属于同一个弧段的组合聚类在一起
- Step 2：每个组合的相似弧段的移除
- Step 3：生成假设椭圆
- Step 4：假设椭圆的验证
- 3 Hough变换方法
- 3.1 弧段聚类
- 3.2 对每个区域提取假设椭圆
- 3.3 候选椭圆验证
- 总结
1 介绍
工业图像下的椭圆检测有如下几个问题：
- 椭圆尺寸非常小，尺寸可以被估计，因为在使用时候，椭圆大小几乎是一致的。
- 椭圆与其他周围的对比度可能非常低，因为都是涂上了相同的颜色
- 零件表面可能存在许多微小的划痕或小凹坑，可能腐蚀椭圆形边缘，甚至使得不可能获得连续的椭圆曲线。
- 表面可以是强反射的，因此椭圆可能被反射光覆盖。
第一步先使用基于边缘连接的方法提取精确的椭圆，要求准则就是宁肯检测不出来也不能检测出错误的椭圆。第二步是使用HT的方法检测出第一步漏下的椭圆。
2基于边缘的方法
边缘线提取，然后提取椭圆弧段前面博客已经介绍过了，这里不对齐进行细致分析，只写其检测流程。
Canny边缘检测→\rightarrow→无分支的边缘线提取（最少3个像素）→\rightarrow→多边形逼近→\rightarrow→识别Sharp turns和inflection点
2.3 候选椭圆弧段聚类
这个部分主要是介绍如果将属于同一个椭圆的弧段聚类在一起，之前12年的Prasad的算法是将每个椭圆拟合一次进行投票确定，这个方法是作者提出来的，下面对其进行一步步分析。
Step 1: 寻找有高拟合精度的候选椭圆弧段，并将其作为种子弧段
这里选择了一个阈值Therrl\boldsymbol{Th_{errl}}Therrl作为拟合误差的边界，小于这个阈值被认为是高精度的候选种子弧段。对于无法与种子弧段组合的弧段，将会被扔掉。这个结论是作者通过观察得到：几乎每一个有效椭圆都具有一个具有高拟合精度的边缘轮廓。虽然可以进行全面的搜索以确定哪个候选椭圆弧段可以与另一个合并，但是当有许多候选弧段时候，将会浪费巨大的时间，（我设计算法时候也是这样，小弧段很容易造成大量的false ellipse）。
Step 2：确定每个种子弧段的搜索区域
给定一个种子弧段，需要确定其搜索区间。一个弧段只有在其搜索区间，才能被组合，否则将会被排除。如下图(a)所示，每个弧段可以计算出其最小包围盒，每个包围盒得中心点作为其中心，两个弧段的距离就是两个包围盒中心点的距离，即∣PiPj∣|P_iP_j|∣PiPj∣，搜索半径为rmaxr_{max}rmax，这个前面是根据理论椭圆尺寸算出来的大小。下图(b)展示了其搜索区间的定一，再搜索区间内的椭圆才能考虑组合。
Step 3：在每个种子点的搜索区间内，查找其相关的边缘弧段
在搜索区间内找到可以组合在一起的椭圆之后，需要利用几何性质判断其是否满足具体椭圆性质。Prasad提出了5中椭圆弧段的情况。下图只有图(e)可能会组合在一起。
针对这5种情况，Prasad提出了一种方法来判断是否可以被组合在一起。p1,p2p_1,p_2p1,p2是每个弧段首尾相连的中点，p1p2p_1p_2p1p2的延长线与两个弧段相交于p1′,p2′p'_1,p'_2p1′,p2′，那么如果两个弧段如果可以组合，则其满足等式关系：p1′p2′≈p1p1′+p1p2+p2p2′p'_1p'_2\approx p_1p'_1+p_1p_2+p_2p'_2p1′p2′≈p1p1′+p1p2+p2p2′。下图a到图c表示这个公式的原理。
但是这个方法有个缺点，无法准确找到点p1′,p2′p'_1,p'_2p1′,p2′，虽然可以利用近似的方法找到这两个点，但是这个方法的时间消耗是time-consuming的，而且这个公式方法是近似的，对于下图©的问题，明显其不属于同一个椭圆。因此Prasad的方法是有瑕疵的。
那么为了克服这个缺点，作者设置 p1′p2′p'_1p'_2p1′p2′ 为每个弧段边缘的中心点，然后再计算出其与收尾相连对应的交点p1,p2p_1,p_2p1,p2。那么其判断公式为：p1′p2′=p1p1′+p1p2+p2p2′p'_1p'_2= p_1p'_1+p_1p_2+p_2p'_2p1′p2′=p1p1′+p1p2+p2p2′。但对于点p1,p2p_1,p_2p1,p2，需要均在直线段上，而不是直线段外部。上图d到f即可说明这个方法的有效性。
Step 4：确定组合的弧段是否在同一个椭圆上
给定种子弧段之后，在经过查找其相关弧段后，直接进行拟合，如果你和误差小于TherrhTh_{errh}Therrh，则认为这些弧段属于同一个椭圆，否则这个组合将会被抛弃。
2.4 从分组弧中提取椭圆及其验证结果
这个小节主要是去除重复椭圆
Step 1： 将属于同一个弧段的组合聚类在一起
如果两个组合拟合出的椭圆的形状参数的欧式距离小于阈值20，则认为这两个组合近似，需要将这一堆椭圆组合在一起，并移除相似弧段。
Step 2：每个组合的相似弧段的移除
相似弧段的判断思想很简单，假设现在有两个弧段ei,eje_i,e_jei,ej，eje_jej比eie_iei长，那么这两个弧段的相似度为：
sim(ei,ej)=∑k=1nd(ei[k],ej)nsim(e_i,e_j)=\dfrac{\sum_{k=1}^n d(e_i[k],e_j)}{n}sim(ei,ej)=n∑k=1nd(ei[k],ej)
如果d(ei[k],ej)<Thlen3d(e_i[k],e_j)<Th_{len3}d(ei[k],ej)<Thlen3则d(ei[k],ej)=1d(e_i[k],e_j)=1d(ei[k],ej)=1，最后，如果sim(ei,ej)>Thpersim(e_i,e_j)>Th_{per}sim(ei,ej)>Thper，则认为这两个弧段相似。
Step 3：生成假设椭圆
前面的步骤已经生成了一堆没有相似弧段的组合。下一步就是从每个组合中提取椭圆。对这个组合进行你和，得到椭圆EseE_{se}Ese，这个椭圆需要满足如下性质，个人觉得这个应用限制于目标的大小尺寸，算是合作目标的椭圆检测。
- 拟合误差小于Therrh/2Th_{errh}/2Therrh/2
- 半长轴在rminr_{min}rmin和rmaxr_{max}rmax之间
- 短轴和长轴的比值大于ThratTh_{rat}Thrat
由于噪声弧段的存在，这三个性质可能无法同时满足，然后剔除所有可能的弧段组合，从大到小一个个组合，直到出现这个结果，或者所有不满足，这个椭圆扔掉。
Step 4：假设椭圆的验证
这里不想分析太多，就是椭圆验证的一个方法，定义lrl_rlr为组合的所有边缘点个数与椭圆周长的比值，这个值越大，说明参与拟合的像素越多。
作者也说了，为了保证检测的准确性和可靠性，实际图像不是在斜视角上得到的，也就是说这个椭圆很近似为圆，也就是srs_rsr应该接近于1。然后作者定义了一个分数来计算验证得分：
S=0.5×lr+0.5×[(sr−k21−k2−1)exp(k1(sr−k2)1−k2)+1]S = 0.5 \times l_r + 0.5\times \left[\left(\dfrac{s_r-k_2}{1-k_2}-1\right) exp\left(\dfrac{k_1(s_r-k_2)}{1-k_2}\right)+1\right]S=0.5×lr+0.5×[(1−k2sr−k2−1)exp(1−k2k1(sr−k2))+1]
同样这里面包含了各种阈值，分数大于阈值则认为是真实椭圆，否则抛弃。
3 Hough变换方法
由于开发这种方法的动机是提取具有高精度和实时性能的椭圆，因此我们不要求该方法能够在不丢失椭圆的情况下提取图像中呈现的所有椭圆，但是检测到的椭圆必须是真正的正椭圆。
由于椭圆的椭圆弧太短，无法提供足够的信息进行椭圆拟合，因此很多椭圆都是碎片，很难用边缘跟踪方法检测。
这里使用HT的方法实际上是从可能包含椭圆的区域内部提取，而不是从全局图像去提取。
3.1 弧段聚类
弧段聚类这里还没用到HT的思想，主要就是想办法将小弧段聚类在一起，与前面类似，主要也是先根据位置信息类进行聚类。
一个弧段根据其首尾两点和弧段中心点确定出两条直线将区域分割为4块，对于一个点PPP，其如果在区域r1r_1r1中，则称其为内点（inner point），图a-d。对于图e，ac，ab夹角为锐角，那么需要对这个弧段进行更加细致的分割，保证每个子弧段的夹角都大于130°，然后再验证点PPP都是这些子弧段的内点。下图给出了对应的算法流程图。
聚类之后，得到聚类中心，以4rmax4r_{max}4rmax作为半径，得到候选区域。
3.2 对每个区域提取假设椭圆
对每个区域，直接使用基于HT的方法去检测，考虑到时间问题，作者添加了几条准则去除了无效的边缘像素，这些像素分别为：
- 去除非平滑弧段，即只保留平滑弧段
- 如果这个弧段与其他候选弧段没有任何关联，去除
- 使用这个方法只考虑没有被检测出来的区域
3.3 候选椭圆验证
对于椭圆长轴不在[rmin,rmax],sr<=Thrat[r_{min},r_{max}], s_r<=Th_{rat}[rmin,rmax],sr<=Thrat的删除，计算两个值。RinR_{in}Rin即有效像素点个数与总像素点个数，RisR_{is}Ris有效像素点与参与像素点个数的比值，最后使用调和等式得到一个评分，然后设置个参数，这个分数大于阈值则有效，否则无效。
总结
方法有很多借鉴之处，目前只是大概了解一下，许多细节仍然需要去复现才能了解，因此在复现之后我会对其进行更加详细的分析。