算法评价

我们如何衡量一个目标检测算法的优劣？

由于目标检测并不是一个单纯的分类或者回归问题，一个合理的评价指标应该综合考虑多个方面。直观来说，我们认为一个好的目标检测算法应该满足以下条件：

1. 找到了图像中出现的全部物体，没有遗漏，即高的召回率。

2. 给出的每一个框中都真正包含物体，即高的准确率

3. 对框中物体分类准确

4. 框的位置准确

近年来，学术界较为流行的指标包括 mAP（mean Average Precesion）、AR（Average Recall）等。 在本节中，我们先铺垫一些基本概念，再介绍两种评价指标的具体算法。

一些基本概念

交并比 IoU

交并比（Intersection over Union, IoU）是衡量两个区域之间重合度的一个指标，定义为两区域交集与并集的面积比，如下图所示。

任意两个区域的 IoU 介于 0 和 1 之间，重合度越高 IoU 越大。当两个区域完全没有交集时，IoU = 0，当二者完全重合时，IoU = 1 。

在目标检测中，我们常用检测框与真值框的交并比衡量检测结果的准确性。如果一个检测框与一个真值框的交并比超过一定的阈值（通常设置为 0.5），就认为这个检测结果是有效的，这个检测结果就是一个 True Positive，否则就是 False Positive。

TP、FP、FN

在目标检测中，我们会将检测结果与真值进行比较，并将比较结果分为 True Positive、False Positive、False Negative 三种类别。

这里 True、False 指的是检测器的结果是否正确，Positive 、Negative 指的是检测器是否将某个区域检测为物体，因此三者的具体含义如下：

1. True Positive (TP)：检测器认为这个区域包含某个类别的物体，这个区域也确实包含这个类别的物体，即图中存在某个同类且交并比大于阈值的真值框。

2. False Positive (FP)：检测器认为这个区域包含某个类别的物体，但这个区域并不包含这个类别的物体，即图中所有同类真值框与该检测框的交并比都小于阈值。

3. False Negative (FN)：这个区域包含某种类别的物体，但检测器没有检测出来，或者给出了检测框但是类别预测错了。

不难得出，TP+FP=检测框的总数，TP+FN=真值框的总数。 在目标检测中，我们通常不考虑 True Negative，即实际为背景，检测结果也为背景（既没有产生任何检测框）的区域。

从上面的定义可以看出，检测结果正确性的评判不仅依赖位置的准确性，也依赖类别的准确性。 因此，主流的评价方法多采用“按类别计算评价，再取平均”的做法，即对于特定类别 c，将所有属于此类的真值框和预测框拿出来，计算某种评价指标。 再按照所有类别取平均值。

$\text{AvgM} = \frac{1}{C}\sum_{c=1}^{C} \text{Measure}(\{\text{pred}\}_c, \{\text{gt}\}_c)$

准确率与召回率

准确率（Precision）的定义为：

\text{Precision} = \frac{\text{TP}}{\text{TP}+\text{FP}} = \frac{\text{TP}}{\text{# det boxes}}

即检测器给出的所有检测框中，有多少比例是正确的。

召回率（Recall）的定义为：

\text{Recall} = \frac{\text{TP}}{\text{TP}+\text{FN}} = \frac{\text{TP}}{\text{# gt boxes}}

即所有真值框中，检测器检测出了多少比例。

在检测器性能恒定的情况下，召回率和准确率之间会有一定的制约。通过简单的阈值调整可以提高一方，但通常会降低另一方。

一个好的检测器应该同时具有高准确率与高召回率，且可以在较高的 IoU 阈值下达到这个目标，即具有较高的位置精度。

Average Precision

Average Precision (AP) 是近年来学术界最常用的检测器评价指标之一，其定义为 precision-recall 曲线下的面积，即 precision 值关于 recall 的平均值。

通常，AP 是针对每个类别分别计算的。 对于每一个类别 $c$，取所有类别为 $c$ 的真值框 $\{\text{gt}\}_c$ 和检测框 $\{\text{pred}\}_c$ ，根据算法计算二者的 AP 值，再将所有类别的 AP 值求平均。

$$\text{mAP} = \frac{1}{C}\sum_{c=1}^{C} \text{AP}(\{\text{pred}\}_c, \{\text{gt}\}_c)$$

因为这个额外的平均值操作，AP 也称为 mAP （mean Average Precision）

在 COCO 数据集的评价标准中，我们还需要对 IoU 取平均。我们知道，计算 precesion 和 recall 需要对预测框进行 TP、FP、TN 的判定，而预测框的判定依赖一个预先设置好的 I o U 阈值。在 Pascal VOC 数据集的评测方法中，这个阈值固定设置为 0.5，而在 COCO 数据集的评测方法中，我们需要计算从 0.5 到 0.95，每 0.05 步长的所有 IoU 阈值下，mAP 的值，再对其进行平均。也就是说，我们需要针对不同的类别和不同的 IoU 值，计算出一系列 AP 值，再对所有的 AP 值求平均。

针对给定的 IoU 阈值和类别，我们可以通过下面的算法计算出对应的 AP 值。

首先我们根据给定的类别，挑出整个数据集中所有该类别的真值框和检测框，并将检测框按照置信度从高到底排序。

考虑置信度最高的检测框，如果存在某个与之交并比大于阈值的检测框，则将这个检测框标记为 TP，否则标记为 FP，并将这个真值框标记为“已匹配”，表示已经有一个检测框与之匹配了，不能再用来匹配其他真值框了。

如果匹配结果是 TP，则当前的 precision 值为 $P_1 = 1$ ，recall 值为 R_1 = \frac{1}{\text{# gt boxes}} 。 如果匹配结果为 FP，则有 $P_1 = R_1 = 0$。

接下来，按照置信度从高到底逐一匹配其余的检测框： 如果第 $i$ 个检测框与某个之前未被匹配过的真值框交并比大于阈值，则标记为 TP；如果与所有真值框交并比小于阈值，或者交并比大于阈值的真值框已经被前 $i-1$ 个真值框匹配过，则标记为 FP。

每匹配一个检测框之后，我们都需要计算当前状态下的 Precision 值 $P_i$ 和 Recall 值 $R_i$ 。当全部检测框都匹配完成，或者检测框数量的达到一个提前设定的限制时（比如每张图上限 500 个）时，匹配过程结束。

然后，我们就可以将全部的 $P_i$ 和 $R_i$ 绘制在 Precision/Recall 坐标系中。 通常情况下，这个曲线会展现出下图的形式，即随着 recall 的增加，precision 有升有降。

显然，$R_i$ 是 $i$ 的增函数，由于 recall 的分母是真值框的总数，是个常数，而随着检测框的增加，分子要么在匹配的情况下增加，要么在不匹配的情况下不变。 而 $P_i$ 随 $i$ 的增减是不确定的，在匹配的情况下，分子分母分母会同时增加 1，准确率不变或上升，而当不匹配的情况下，分子不变，分母增加 1，准确率下降。因而曲线会出现升降交替的形状。

接下来，我们对得到的 precesion-recall 进行插值，插值的公式为：

$$\tilde{P_i} = \max_{j \ge i}{P_j}$$

直观上讲，就是使用曲线右侧较大的 precision 值填补那些 precision 下降产生的“低洼区域”。 插值之后，precision-recall 曲线更为平滑，而且变成了一个单调递减的函数。

如果我们将 precision 看作是 recall 的连续函数，插值公式也可以表述为：

$$\tilde{p}(r) = \max_{j | R_j \ge r}{P_j}$$

最后，我们计算插值之后的曲线下的面积，得到当前类别和 IoU 阈值下的 AP 值。

遍历全部类别和 IoU 阈值，计算出全部条件下的 AP 值后取平均，即为最终的 mAP 值。

11 点 AP

早期的 Pascal VOC 竞赛还使用过一种称为 11 点（11-point）AP 的评价算法。 11 点算法使用 recall 等于 0, 0.1, 0.2, ..., 1.0 这 11 个点的（插值后的） precision 值的平均值，作为单条 precision-recall 曲线的 AP 值，即

$$AP_{11} = \frac{1}{11}(\tilde{p}(0)+\tilde{p}(0.1)+...+\tilde{p}(1))$$

而不是使用整条曲线下的面积。在其余方面，11 点 AP 的计算方法与上述 mAP 相同。

Average Recall

Average Recall (AR) 是论文提出的一种衡量指标， 起初用于衡量 Region Proposal 的质量，后被 COCO 数据集选取为衡量检测结果的指标之一。

AR 定义为检测器在不同交并比阈值下召回率的平均值，即 AR 名字中的 Average 就是针对不同交并比而言的。 与 mAP 等指标相同，AR 也是针对每个类别单独计算，再按类别求平均值。

给定某个类别和一个特定的交并比阈值，我们将所有这个类别的检测框与所有这个类别的真值框进行匹配，依照设定的交并比阈值将检测框归类为 TP 和 FP，并计算出对应的召回率：

\text{Recall}_{\text{IoU, class}} = \frac{\# \text{TP}_{\text{IoU, class}}}{\# \text{pred_box}_{\text{class}}}

针对不同的类别与交并比阈值重复计算召回率，再取平均值，就得到最终的 AR 值。 通常， AR 会在 0.5, 0.55, ..., 0.95 这几个交并比阈值上进行计算。

AR 指标并没有考虑准确率方面的要求。只要任意增加检测框的数量，就可以提高 AR 值，但大量低质量检测框（即 FP）的出现却降低了检测结果的质量，导致 AR 指标失效。

为解决这个为题，COCO 数据集还要求在计算 AR 的时候限制每张图上检测框的最大数量。 具体而言，COCO 要求在每张图上至多给出 1、10、100 个检测框的条件下分别计算 AR，分别得到 ARmax=1、ARmax=10、ARmax=100 三个指标。 这相当于在准确率上给予了一定的限制。

mmdetection 中的实现的评价方法

mmdetection 在 mmdet.core.evaluataion 模块中支持了 mAP 和一个不区分类别的的 AR 的计算，而针对 COCO 数据集的各种 AR 评价指标则依赖 pycocotools 工具包。

mAP 的具体实现为 eval_map 函数，该函数输入一系列检测框与真值框，并根据其他一些参数计算出对应的 mAP 值。该函数的实现逻辑大致如下：

1. 遍历全部真值类别，通过 get_cls_results 函数取出对应类别的检测框与真值框，用于计算这个类别的 AP。

2. 通过 tpfp_fn 函数，将检测框与真值框进行匹配，并将检测框分为 TP 或 FP，或在一些额外规则下忽略某个检测框（既不算 TP、也不算 FP）。

3. 将所有的检测框按置信度排序，并根据匹配得到的 TP 或 FP 值，计算出所有检测框的 $P_i$ 和 $R_i$ 值，即前 $i$ 个检测框对应的 precision 和 recall 值。
4. 使用 average_precision 函数计算曲线下的面积，或计算 11 点 AP 值。

5. 将所有类别的 AP 值取平均得到 mAP。

AR 的具体实现为 eval_recalls 函数，该函数可以根据一系列检测框与真值框，在不同的 IoU 阈值和检测框数量上限要求下计算 recall 并平均得到 AR 值。该函数的实现逻辑大致如下：

1. 在每张图的上，将检测框按置信度从大到小排序，根据要求的检测框数量上限（如果达不到上限就取全部检测框），取出 prop_num 个检测框，并使用 bbox_overlaps 函数计算出这些检测框与该图像上所有真值框之间的 IoU 值，结果是一个矩阵，存储在 iou 变量中。

2. 在 _recall 函数中，使用贪心算法，针对每个真值框找出与其 IoU 最大的检测框，且每个检测框只能被一个真值框匹配。再根据不同的 IoU 阈值判断满足要求的 TP 的个数并计算 Recall，再平均得到 AR 值。

参考资料与图片来源

1. https://en.wikipedia.org/wiki/Evaluation_measures_%28information_retrieval%29#Mean_average_precision

2. https://www.zhihu.com/question/53405779/answer/993913699

3. https://innerpeace-wu.github.io/2018/03/22/Metrics-Average-Precision/