论文阅读——椭圆检测 2016 Robust ellipse detection with Gaussian mixture models

        这篇文章是16年发表的椭圆检测文章，论文题目为：《Robust ellipse detection with Gaussian mixture models》，发表在《Pattern Recognition》（2区SCI）上。这里最为新颖的地方就是使用高斯混合模型GMM算法进行椭圆检测。下面我就对这篇文章进行分析。

〇 摘要部分

        高斯混合之间的欧式距离已经被证明在进行点集配准上是鲁棒的。作者采用这个思想用于匹配一系列形状（椭圆）。使用退火策略执行优化，并且多次重复寻找来检测感兴趣中的多个实例1。

一 介绍

        介绍这部分第一段只是泛泛介绍想基于配准的算法的思想，没有阅读过这篇文章的肯定读的一头雾水，所以直接先看创新点是啥。相关研究这里也不说了，同类文章大同小异，具体的可以参考前面介绍的椭圆检测文章。这里只想了解是如何将GMM应用在椭圆检测上。创新点部分一共有三点，如下所示：

• 扩展了基于L2${\mathcal{L}}_2$用于估计一系列曲线参数的框架。

• 提出了一种用于密度函数的多维模型，以便包含其他可用的信息，而且具有很少的计算。

• 作者提出了一个检测多个椭圆的方法。这个方法用于在2D点云和图片中中进行椭圆检测。

二 使用L2${\mathcal{L}}_2$的椭圆检测

        高斯混合模型用于表示观测点（定义为f$f$）和椭圆模型（定义为gθ$g_{\theta }$）之间的形状，其中θ$\theta$就是椭圆的参数(γ,a,b,xo,yo)$(\gamma ,a,b,x_o,y_o)$，γ$\gamma$是椭圆旋转角，a,b$a,b$是椭圆半短轴和半长轴，xo,yo$x_o,y_o$就是椭圆中心点。椭圆的参数可以通过最小化两个密度函数f$f$和gθ$g_{\theta }$之间的欧式距离来估计。接下来介绍如何对这两个密度函数进行建模，为了方便理解，我会对公式进行详细的推导与分析。

2.1 对椭圆gθ$g_{\theta }$进行建模

        参数为θ$\theta$的椭圆上的一点u(j)$u^{(j)}$可以由吐下等式表示。其中τj∈[0,2π]${\tau }_j\in [0,2\pi ]$。

        模型gθ$g_{\theta }$使用均匀分布的N=20$N=20$个点u(j)$u^{(j)}$来定义一个非等方向（non-isotropic）的GMM。

        其中N(x;μj,Σj)$\mathcal{N}(x;{\mu }_j,{\mathrm{\Sigma }}_j)$正态密度函数，x∈R2$x\in R^2$是一个随机变量。其中μj${\mu }_j$定义为两个连续定点的均值u(j),u(j+1)$u^{(j)},u^{(j+1)}$。协方差矩阵Σj=QTjΛjQj${\mathrm{\Sigma }}_j=Q_j^T{\mathrm{\Lambda }}_j{Q}_j$，其中Qj$Q_j$是一个旋转矩阵Qj=[n⃗ 1j,n⃗ 2j]$Q_j=[{\overrightarrow{n}}_{1j},{\overrightarrow{n}}_{2j}]$，n⃗ 2j${\overrightarrow{n}}_{2j}$与u(j),u(j+1)$u^{(j)},u^{(j+1)}$方向相同，是一个单位向量，n⃗ 1j${\overrightarrow{n}}_{1j}$就是n⃗ 2j${\overrightarrow{n}}_{2j}$对应的正交单位向量。Λj${\mathrm{\Lambda }}_j$的定义方式如下式，其中htj=||u(j)−u(j+1)||$h_{tj}=||u^{(j)}-u^{(j+1)}||$，参数h$h$控制轮廓发现方向的模糊性，这个参数由用户设定（也就是需要调参的参数）。权重参数wj$w_j$与htjh$h_{tj}h$成正比，且权重的和为1，利用这个条件可以计算出wj$w_j$实际计算方法，wj=htjh∑Ni=1htih$w_j={\displaystyle \frac{h_{tj}h}{\sum _{i=1}^N{h}_{ti}h}}$。

        下图是不同的采样点个数N$N$和不同的模糊阈值h$h$对概率的影响，个人认为，边缘点有时候会受到误差影响，有一定的便宜，这个两个参数就是控制这个参数的接受程度吧。N$N$过小就形成不了一个严格的山脊，就像图（e）一样，也就是保证椭圆上的区域概率要高。最后选择，N=20，h=1$N=20，h=1$。

2.2 对观测点f$f$进行建模

        GMM模型f$f$对观测点进行建模，依赖可使用的信息和观测点的结构。例如，假设，我们得到一组观测点{v(i)}i=1,...,n$\{v^{(i)}{\}}_{i=1,...,n}$。在这种情况下，没有关于这些点是如何相连的信息。因此，我们使用各向同性协方差矩阵来定义GMM，每个高斯的均值就是其本身。下式就是对应的GMM公式。

        我们可以使用边缘点{v(i)}i=1,...,n$\{v^{(i)}{\}}_{i=1,...,n}$作为观测点。除此之外，每个观测点的梯度信息是已知的，是可以用于前面说的GMM模型的。具体的模型定义如下所示。像素梯度信息根据上一小节就可以用于计算Σi${\mathrm{\Sigma }}_i$，因为每个边缘点之间的距离很近，因此原来的htj$h_{tj}$在这里就是ht=1$h_t=1$。权重wi$w_i$的计算方式同之前的介绍。

2.3 密度函数的简化表示

        两个密度函数的目标函数可以化简为如下所示。

        ||f||2$||f|{|}^2$项没有涉及到未知参数θ$\theta$就不需要进行计算了。其他项的计算应用到了如下的等式。函数的内积就是这两个函数的乘积在其定义域上的积分，下面这个公式是作者参考的那篇文章的引用（等我手头工作完事，就详细去证明这个等式）。

        之后就可以得到目标函数的两个项的表达形式。这里面的未知参数只有θ$\theta$。

三 椭圆检测算法

        我们首先展示了一个算法从观测数据中拟合数据。与作者参考的算法相似，在模拟退火框架中进行优化来避免局部解，并限制起始猜测点对优化结果的影响。然后作者有提出了一种用于从观测数据中检测出多个椭圆的策略2。

3.1 退火算法用于椭圆检测

        在计算L2${\mathcal{L}}_2$时唯一自由的参数是GMM中的f$f$和gθ$g_{\theta }$。该参数在所提出的估计框架中起着两个重要的作用。首先，它影响形状的描述。它控制曲线在法线方向上的模糊性，其次它影响了代价函数的凸性。使用基于梯度的优化算法（GOA）来执行优化3，这个算法依赖于起始猜测点θ(0)${\theta }^{(0)}$和正交带h$h$的选择。

        h$h$的选择越大，损失函数就越平滑。因此，未来使我们的方法对初始点θ(0)${\theta }^{(0)}$不明娜，我们使用了一个模拟退火算法框架，其中正交带h$h$是随着几何速率的降低而降低（由参数β$\beta$控制）的温度。h$h$从hmax$h_{max}$开始到小于hmin$h_{min}$停止。模拟退火的使用有助于收敛到全局解。

        这个小节说白了，就是使用模糊退火算法进行优化求解，最终得到目标椭圆参数θ$\theta$。

3.2 多个椭圆的检测

        这个小节的目标是从观测点中检测出一组椭圆。作者提出了一个迭代算法来处理这个问题。

• 全局估计： 这步估计使用上一小节的方法估计出一个参数θ^$\hat{\theta }$。

• 观测模型f$f$的更新： 一旦匹配出一个椭圆，那么所有与这个椭圆相关的观测点都会被移除。剩下的观测点被用于检测其他的椭圆。更新集Sf$S_f$应该具有如下的性质，其中Hellipse=1N∑Ni=1gθ^(μj)$H_{ellipse}={\displaystyle \frac{1}{N}}\sum _{i=1}^N{g}_{\hat{\theta }}({\mu }_j)$，t1=0.3$t_1=0.3$。

        关于Hellipse$H_{ellipse}$的理解，可以参考下图的介绍。参与构成一个椭圆的观测点在GMM上具有较大的概率，也就是下图中凸起的部分，这个凸起部分的平均值代表整体概率，其他观测点在这个模型上不应该具有较大的概率。这样我们可以得到一堆其他观测点，这些观测点肯定不在这个得到的椭圆上，然后重复检测，重复利用这个想法，直到剩下10%的点结束。

四 GMM模型的维数增广

        之前的模型直接采用的每个图像的像素点，所以每个GMM模型都是2维的，作者又利用了梯度角的信息，将GMM模型增光到3维，更新了均值与协方差矩阵的定义，其他的计算方法都不变，目的就是提高检测精度。思想方法都很容易理解。

五 实验部分

        作者将自己的方法与一些拟合算法进行了对比，验证了其在噪声较高的地方具有高鲁棒性。但是，我觉得这个问题在椭圆检测领域是不重要的，根据提供的测试图可以看出来，参与拟合的数据都有一些错误值，这些值肯定不属于椭圆。作者提供的这个算法可以理解为一种剔除错误值的算法，所以肯定会比那些没有剔除错误值的方法要好。但是，实际中，椭圆拟合主要就是弧段组合，很少会出现这种有异常值的点，每个点都是通过Canny检测出来的，会有1~3个像素的失真，但像测试图这种我个人认为出现的情况太少了。

        从下面的这个仿真图测试来看，其效果不是十分理想，很多看起来很容易检测出来的椭圆没有检测出来。个人认为，观测点找到之后最好进行一次直接拟合，不要进行优化求解，毕竟优化求解不一定能很好的找到好的拟合解。效果不好，不代表这个方法不好，作者是新的尝试，是一种大胆的创新，作者已经证明了其可行性，在未来的工作中如果解决这些问题，一定会比边缘链接的要容易处理，效果更好。

        下图是检测一个图片多个椭圆的过程，其方法是有效的，而且大部分是交给算法进行自动识别，很符合机器学习的思想，结果看起来也十分有趣。

六 个人总结

        这个文章创新性很好，尽管结果差强人意，但是这个想法非常值得我们去借鉴。但是，从这个算法，仍然有很多地方需要分析研究。

• 简单场景，这个算法会十分实用，而且对于手写的方法一定会有良好的匹配效果，匹配的思想绝对是优于边缘链接的。真实场景的Canny边缘图相当复杂，这个算法的耗时是否增加的非常严重。

• 基于边缘的方法如果边缘被分割的十分严重，效果肯定不好。但这个方法存在大量的错误检测，而且观测点正确，缺拟合出了错误的结果，这后期也要深度研究。

• 观测点的组合，我觉得会有效的提高检测精度。

        总而言之，这个算法非常值得我们去阅读，如果我们想采用机器学习的思想去进行椭圆检测，不建议直接去与基于边缘的去对比。个人建议，制作一个手绘椭圆数据集，与本文和UpWrite算法去对比。这样绝对会是很好的创新。