Date: 2020/11/02

Coder: CW

Foreword:

通常情况下，anchor的大小是根据经验而人工预设的，这种做法在差异较大的数据集之间可能不能达到平衡的表现。比如有两个数据集，它们的 gt box 的大小差异较大，在其中一个数据集anchor能比较好地匹配 gt box，但同样的这批anchor在另一个数据集中的匹配情况可能就比较尴尬了。那么，有没有一种自适应的方法，让anchor能够根据数据集 gt box 的大小来自动生成相应的尺寸呢？

结论先行——有滴！

想一想，如何做到自适应？在一个数据集里，有那么多的物体，对应各种大小的 gt box，它们的尺寸可能相差悬殊，因此我们可以让这些 gt box “抱团”，将尺寸较为接近的 gt box归为一类，这样就能得到不同的“团”，每个团中的 gt box 尺寸都处于相同水平，都是好哥们儿！

抱了团不能没有团长，群龙无首如何行走江湖！那么谁来做团长呢？既然都是好哥们儿，选谁做团长变得高人一等难免伤感情，于是可以对每个团中所有 gt box 的尺寸取均值作为每个团 gt box 尺寸的代表，这个尺寸就是团长的尺寸，那团长呢？团长当然就是我们的主角——anchor了！

以上做法实质上是在无标签（这里的标签并非指以上谈到的数据集的 gt）的情况下进行分类，也就是所谓的“聚类”，聚类出来的各个质心就对应anchor（实质上是聚类anchor的宽和高，坐标位置无关紧要）。大名鼎鼎的 YOLO 就是使用聚类算法来生成anchor的，算法的基本过程如上所述，本文内容是将这个过程落实到代码实现中进行解析，从而将算法思想转化到代码实现中，希望能让诸位客官有更深刻的理解。

---

先开个好头：变量初始化

n_anchors代表我们打算设置9个anchor，也就是将数据集的gt box分为9个团，每个anchor分别作为对应的团长。另外说明下，这里gt box的宽、高进行了归一化缩放到了[0,1]范围，因此最终聚类得出的anchor宽、高也是在这个范围内，需要乘以输入图像的宽、高才能对应到输入图像上，这也是以下strides和grid_sizes两个变量存在的原因。

在聚类算法前，我们需要先初始化聚类中心，也叫“质心”，常规的做法是随机初始化，这种做法有可能会影响最终的聚类效果；另外一种做法是在K-Means++算法中使用的方法，它的思想是在初始化的时候让各质心之间彼此相距较远。这里，设置一个标识位plus用于指定使用哪种初始化方法。

最终，当算法执行超过规定的最大迭代次数或者loss已经收敛到指定的水平，就可以结束了。

初始化设置

---

Pipeline

首先，初始化规定数量的质心，在这里，就是我们的anchor。另外说明下，此处省略了从标签文件解析出gt box坐标的过程，boxes中就是各个gt box，里面有它们对应的宽、高信息。

pipeline(i)

接着就是迭代执行K-Means聚类算法，直至达到一定迭代次数或loss收敛，每次迭代都会得出新的质心，也就是说每次迭代后我们的anchor宽、高都会更新。

pipeline(ii)

最终输出聚类结果。上一节谈到过，聚类出来的anchor宽、高是[0,1]区间内的值，因此这里需要乘上输入图像大小（等于特征图尺寸乘上对应的步长）完成转换。

pipeline(iii)

---

K-Means++初始化

了解了算法整个pipeline，现在我们来对每个核心部分进行剖析。先来看看如何完成质心的初始化，在这里，就是如何初始化anchor的宽、高。随机初始化的方法在上一节pipeline中已“走光”，无需多言，这里主要来看看K-Means++的初始化方法。

先随机从gt box里挑选一个作为质心。

K-Means++初始化(i)

然后，依次迭代，每次选出一个新的质心，直至规定数量的质心都被选出。

每次挑选质心时，我们需要计算各gt box到当前已有的哪个质心最近，并记录下这个最短距离。这里的距离使用1-IoU表示，这样，gt box与质心的IoU越大，它到质心的距离就越短。

K-Means++初始化(ii)

接着，为每个gt box设置对应的概率区间，代表它们各自被选为下一个质心的概率。概率区间通过累加各gt box到最近质心的距离来构建，由此可知，距离越短则对应的概率区间越窄，对应gt box被选为质心的概率也就越小，也就是说距离当前已有质心越远的gt box越有可能被选为下一个质心，这就是K-Means++初始化的精髓所在。

K-Means++初始化(iii)

最后，产生随机数看落入哪个区间就挑出对应的gt box作为下一个质心即可。

K-Means++初始化(iv)

---

K-Means聚类

质心的初始化完成了，我们就可以开始真正地进行聚类了。

new_centroids就是本次迭代需要计算出的新质心，初始化它们的宽、高都是0，groups就是各质心对应的“团”，优雅点称作“簇”。

K-Means(i)

然后计算出各gt box到哪个质心最近，同时记录下对应的距离。

K-Means(ii)

一次迭代的loss是所有gt box到其最近质心的距离总和，这样，当loss收敛时就代表各个簇都已经相对稳定不再变动了，也就可以没必要再进行迭代了。

计算出gt box距离最近的质心后，将其划分到质心对应的簇，同时将其宽、高累加到新的质心上。

K-Means(iii)

为何前面要将gt box的宽、高累加到所在簇的新质心上？因为新的质心（在这里就是我们的anchor）的宽、高是所在簇中所有gt box的宽、高的均值。

K-Means(iv)

---

End

使用聚类算法来生成anchor相比于人工预设来说“较为科学”，一定程度上有了自适应的feel，如今许多anchor-base机制下的模型也会使用到它，感兴趣的朋友们可以将其收纳进自己的百宝箱里，作为一个备用手段（当预设anchor效果不理想时）。