FDDB

本文简要翻译了 FDDB: A benchmark for Face Detection in Unconstrained Settings.

Introduction

人脸检测发展很快，但是很多算法所报道的结果不能复现，因此需要建立一个新的评价标准来评估算法表现。现有数据库存在如下问题：

Sung et al. 的数据库：虽然来源各异，甚至包括从报纸上扫描的图片，但是所有的人脸都是正面垂直照。

Rowley et al. ：与上面的数据库相似，并包括了平面内旋转的人脸 (faces with in-plane rotation)。

Schneiderman et al. ：将上面的两个数据库结合，并增加了人的侧脸图片 (profile face images)，构建了著名的 MIT+CMU 数据库。

上面这些数据库都是灰度图，不能有效评估彩色人脸检测器。之后的一些数据库也包含了彩色图片，但是存在缺点。例如 GENKI 数据库收集了不同姿态的彩色人脸图（左右/上下 $\pm 45^\circ$，正面旋转$\pm20^\circ$），但是每幅图只有一张人脸。类似的 Kodak，UCD 和 VT-AAST 数据库包含了带遮挡的人脸，但是数据集太小，不能作为评判标准。

本工作的贡献是建立了一个新的数据库，解决了上述问题。这个数据库包含：

• 2845 张图片，其中包含了 5171 张人脸；

• 包含了各种遮挡，高难度的姿态，低分辨率以及对焦模糊的人脸；

• 用椭圆来标定人脸区域；

• 同时包括灰度图和彩色图。

当前的评判标准存在的另一个问题是，缺少对程序表现的评价指标。某个算法报道出来的表现，取决于它对“正确检测”的定义。本文设置了一个评判框架，包含下面几个部分：

• 一个程序，对比算法输出和groundtruth的相似度

• 两个严格、精确的方法来评估算法在数据集上的表现。这两种方法是为不同的应用设计的

• 实现上述步骤的源代码

本文按如下结构展开：

Section 2：评价不同人脸检测方法的困难之处；Section 3：概括本数据集的构建过程；Section 4：介绍一种半自动化的方法，用于去除数据集中的重复图片；Section 5：本数据集的标定过程细节；Section 6：介绍本数据集的评判框架。

Comparing face detection approaches

基于可以接受的头部姿态变化程度，人脸检测算法可以被分为如下几类：

• 单一姿态：只能检测标准正面或者侧面像

• 旋转不变：可以接受脸部在画面中的旋转

• 多视角：画面中的头部可以左右上下旋转

• 姿态不变：对人的头部朝向没有任何限制

本文构建的数据库用来评价最普遍的情况，也就是姿态不变。

评价人脸检测算法的第一个挑战是，对程序的预期输出没有达成一致：有些算法输出的是矩形框，有些是任意形状的框，还有些是输出眼睛等脸部特征的位置。另外还有的算法输出了头部的姿态。

本工作限定在对基于区域的输出的评价（evaluation of region-based output）。因此用任意尺寸、形状和朝向的椭圆来标定图像中的人脸。这比之前的矩形框更贴合人脸，并且也易于用参数表示（椭圆公式）。在 Section 5 中介绍标定步骤。

FDDB: Face Detection Data set and Bench-mark

Berg et al. 根据新闻图片和提取它们的新闻标题创建了一个数据库，图片包含了各种姿态、光照、背景。里面的人脸包含各种表情、动作和遮挡，因此很贴近现实中的识别场景。但是这里面的人脸是通过自动化的人脸检测算法标定的，因此并不客观。本数据库采用了该数据库的所有图片，并为里面的所有图片中的人脸做了标定。

Construction of the data set

Berg et al. 的数据库是从 Yahoo 新闻网收集的。很多新闻虽然来源不同，但是用的图片相同，因此数据库里面有很多重复图片，这些图片虽然内容相同，但是可能有微调（剪裁、对比度修正），导致了所谓 near-duplicat images。这种近似的图片会影响到对算法评估的客观性，因此需要去重。

Near-duplicate detection

作者从 Berg et al. 的图-标题对中（根据时间顺序）选出了 3527 张图。如果用朴素的方法去重，需要对比大概 12500000 次（估计是每幅图和剩下的图对比，$3527\times (3527-1)=12436202$）。另一种方法是每次同时展示一组图片，然后人工为这组图片去重，由于图片太多也不现实。

网络搜索领域研究的一个课题是找出 near-duplicate images。然而在网络搜索中，放缩的重要性要大于在图片库中找出所有的近似图片。因此也不能直接使用这种手段。Zhang et al. 提出了一种基于 stochastic attribute relational graphe (ARG) （随机属性关系图）匹配的计算密集型算法。这些 ARGs 通过检测图片中的几个 interest points 来表示整幅图的构成部分和每部分之间的关系。为了计算两幅图的 ARGs 的匹配分数，采用了一种图变换的生成模型。这种方法在寻找近似图片方面能够达到很高的召回率：

$$
recall=\frac{relevant\ documents\cap retrieved\ documents}{relevant\ documents}
$$

（recall 也就是 true positive rate，能够最大程度地检测出和当前图相关的图保证不会遗漏，但是可能检测到很多和当前图不相关的图，汪精卫：宁可错杀1000不放过一个）因此很适合用在这里。为限制误检率，采用 Algorithm 1 的算法，循环地交替聚类和人工检查。Algorithm 1 的 3-5 步采用 spectral graph-clustering 方法进行聚类。然后，人工检查每个非单一样本的小聚类，如果这个小聚类中所有的图片都是一个来源，那么就用其中的一幅图片代替整个类。

在聚类步骤，作者根据 collection 中的所有图片创建了 fully-connected undirected graph G，其中 ARG-匹配得分作为每两幅图之间连线的权重。 根据 spectral graph-clustering approach，作者计 graph G 的 (unnormalized) Laplacian $L_G$ 。

$$
L_G = diag(\mathrm(d))-W_G
$$

其中 d 是 set of degrees of all nodes in G，$W_G$ 是 G 的 adjacency matrix。图 G 到 $L_G$ 的前几个特征向量张成的子空间的投影，可以为每对节点（一个节点代表一张图片）提供一个很有效的距离测度。作者在这个投影空间中用 mean-shift clustering with a narrow kernel，得到图片的聚类。

利用该算法，7 次迭代，人工发现了 103 个聚类，消灭了 682 张重复图片。

人脸区域标定

预标定：在 2845 （3527 张原有的图减 682 张重复的图）张图片中，画出每个人脸的矩形框。长或宽小于 20 像素的人脸被排除，得到了 5171 个人脸标定。有些地区不太好确认是否标定为人脸，原因包括低分辨率，遮挡，头部角度等。作者采用多人标定，取平均值的手法。对于下面这些情况，标定者需要将其排除人脸：两只眼睛同时被遮挡、无法估计（定性地 qualitatively）位置、尺寸或者朝向。Appendix A 中描述了标定流程。

Elliptical Face Regions

作者表示人的头部可以用两个椭球近似，进而认为用椭圆标定人脸比用矩形更准确，所以采用椭圆标定。采用的椭圆参数有：中心坐标、长轴/段轴的长度、以及方向。由于现实中人脸在 2 维的投影不是规则的椭圆，所以用椭圆标定人脸很有挑战。为了使标定一致，人工按照下面的流程进行标定：

• 椭圆的长轴两个端点分别是人脸的下巴和椭球（用来近似人头的那个）最上端的点，椭圆不包括耳朵部分

• 对非正面的人脸，椭圆的至少一个横向端点与该侧耳朵与人脸的边界重合

• 细节见 Appendix A。

接下来需要设计一个一致且合理的评估标准。

Evaluation

首先要做出几点假设：

• 每个检测结果都与它毗邻的图像区域对应

• 任何用于重叠区域融合或者相似检测去除的后处理步骤都已经完成

• 每个检测结果唯一对应一张人脸，不能出现对应多张或者一半人脸的情况。换句话说，一个检测框不能同时检测两个人脸，两个检测框不能组合起来检测一张人脸，如果一个程序用多个检测框检测到了人脸上不相连的区域，那么这里面只能有一个代表正确检测，其余的都为错误检测。

为了表达检测结果 $d_i$ 和标定 $l_j$ 之间的吻合度，采用 intersection over union 的算法：

$$
S(d_i, l_j) = \frac{area(d_i) \cap area(l_j)}{area(d_i)\cup area(l_j)}
$$

其中标定 $l_j$ 采用上文的椭圆。

为了便于人工标定，作者首先用程序对人脸的位置进行了估计。方法是：首先用皮肤分类器对图片的像素进行分类，分类器的输入是像素点的 hue 和 saturation 值（HSV: hue 色调，saturation 饱和度，value 亮度）。然后，皮肤连通区域包围的孔洞用 MATLAB 的 flood fill 算法进行填充。最终，基于连通区域的矩，计算得到其外接椭圆的各项参数，最后人工将调整这些参数。

Matching detections and annotations

将检测结果和标注进行一一对应。最后剩下的问题是如何将一组标注和一组检测结果进行对应。对于好的检测结果，这个问题很好解决。但是对于大量 false positives (误检) 或者多个重叠的检测，这个问题就变得微妙和有技巧性了。下面我们将这个匹配标定框和检测结果的问题，规范化为在二分图中寻找最大比重的匹配。

（匹配方式比较复杂，临时我没搞懂Lecture 10.pdf Maximum Weight Matching in Bipartite Graphs）

Evaluation metrics

假设 $d_i$ 和 $v_i$ 代表第 i 个检测结果和它对应的标定。作者提出了下面两种测度，用来衡量该检测的得分。

• 离散得分(DS Discrete score)：$y_i = \delta_{S(d_i, v_i)>0.5}$

• 连续得分(CS Continuous score): $y_i = S(d_i, v_i)$

这里再回顾一下评估物体检测算法的 ROC 曲线的画法：

1. 根据 annotation 为所有 detection 的矩形框打上标签，如果一个 detection 的框与 annotation 框的 IoU 大于 0.5，那么它的标签就是 1，反之为 0，也就是文中的离散得分定为 1。

2. 将所有图片中的所有检测框放在一起，按照 confidence score 从高往低排列（注意 detection score 和 confidence score 的区别，confidence score 是检测器输出的物体置信度得分，而 detection score 是根据预测的物体位置与实际标定的位置算出的得分）。

3. 对于没有检测到的标定框（也就是没有 detection 框能够覆盖这个 annotation），将其标为正样本（detection score = 1），但是给它的 confidence score 定为负无穷。也排在检测框的序列后面。

4. 从高往低调整 confidence score 的 threshold，例如当 threshold=1 时，没有 confidence score 能在 1 之上，故 True positive rate (TPR 或 recall) 为 0，同时，False positive rate (FPR) 为0。在 ROC 曲线上描出坐标原点这个点；假设 threshold=0.98 时，有 2 个 检测框的 confidence score 在 threshold 之上，其中一个与 annotation 的 IoU 大于 0.5（故标签为1，是正确的检测，属于 True Positive），另一个与 annotation 的 IoU 小于 0.5（故标签为0，是错误的检测，属于 False Positive）。那么，TPR 为 1 除以正确检测的总数（计数时包括那些排在检测框之后的未被检测到的 annotation），FPR 为 1 除以错误检测的总数（在 FDDB 中，并没有采用 FPR，而是直接采用 FP，也就是 False Positive 的个数）。这样，又在 ROC 曲线上描出了新的一个点；继续降低 threshold，描出更多的点，直到 threshold 降到负无穷+1（比负无穷稍大一点），将所有检测框都置为正检测。此时仍然有些 annotation 由于得分为负无穷，无法归为正检测，这样，其 FPR 为 1（若横轴为 FP，则此时其值为所有检测框中的负样本数），而 TPR 为该检测器能力的极限。

以上是传统的 ROC 曲线画法，其 detection score 要么是 1 要么是 0，完全取决于 detection 与 annotation 的 IoU 是否大于 0.5，因此这种做法比较粗糙。FDDB 给出了一种新的评估标准，detection score 不再是非0即1，而是直接采用 IoU 值，计算 TPR 时，将所有 threshold 之上的检测框的 detection score 加起来，除以正样本总数，例如某个 detection 与 annotation 的 IoU 为 0.9，那么它就相当于之前的评判标准的 0.9 幅 True Positive。

数据格式

每个 annotation 文件的内容都是如下格式：

第 i 幅图的名称
该幅图中人脸 annotation 的个数
face f1
face f2
...
第 i+1 幅图的名称

每个人脸的椭圆标定都用 6 个元素的元组来表示。$(r_a, r_b, \theta, c_x, c_y, 1)$ 前两者为椭圆的半长轴和半短轴，中间 $\theta$ 为长轴与水平方向的夹角，接下来两个元素为椭圆中心的坐标，最后一个为得分，由于是标定的groud truth，故得分为 1。对于 detection，得分为检测框对应的 confidence score。

detection 的形状既可以为矩形，也可以为椭圆形。若为矩形，其格式为 $(x, y, w, h, s)$ 分别代表矩形的左上角坐标，宽度，高度以及得分，其中得分 $s\in \{-\inf, +\inf\}$。

detection 若为椭圆形，其格式为 $(r_a, r_b, \theta, c_x, c_y, s)$。分别代表：半长、半短轴长度，长轴与横坐标轴的夹角，椭圆中心点坐标，confidence score。

代码

下面的代码可以在图像中同时画出 annotation 和 detection。

import matplotlib.pyplot as plt
import matplotlib.image as mpimg
from matplotlib.patches import Ellipse
import numpy as np
import os

 # 用于读取 detection 和 annotation
 # 返回字典列表，列表中每个元素为一个字典，包含的键有：图像名称，该图中脸的个数，脸的坐标
def getRes_det(fdet):
    detFile = open(fdet,'r')
    det = detFile.readlines()
    detFile.close()
    res = []
    for idx in range(len(det)):
        if '/' in det[idx]:
            im_res = {}
            im_res['name'] = det[idx].strip()
            num = int(det[idx+1])
            im_res['num'] = num
            coord = []
            for i in range(idx+2,idx+2+num):
                coord_str = det[i].split()
                coord_float = [float(i) for i in coord_str]
                coord.append(coord_float)
            im_res['coord'] = np.array(coord)
            res.append(im_res)
    return res


 # 在 res 中的每个元素中增加时间 键
def getRes_time(res, ftime):
    timeFile = open(ftime,'r')
    tm = timeFile.readlines()
    timeFile.close()
    for i in range(len(res)):
        res[i]['time'] = float(tm[i])
    return res

 # 画出 detection 和 annotation
def showRes(res, ann, thresh=0.5, class_name='face'):
    dets = res['coord']
    inds = np.where(dets[:,-1]>=thresh)[0]
    im_name = os.path.join('..','originalPics',res['name']+'.jpg')
    im = mpimg.imread(im_name)
    fig, ax = plt.subplots(figsize=(6,6))
    ax.imshow(im, aspect='equal')
    for i in inds:
        bbox = dets[i, :4]
        score = dets[i, -1]
        ax.add_patch(
            plt.Rectangle((bbox[0], bbox[1]),
                          bbox[2],
                          bbox[3], fill=False,
                          edgecolor='red', linewidth=3.5)
            )
        ax.text(bbox[0], bbox[1] - 2,
                '{:s} {:.3f}'.format(class_name, score),
                bbox=dict(facecolor='blue', alpha=0.5),
                fontsize=14, color='white')                
    ax.set_title(('{} detections with '
                  'p({} | box) >= {:.1f}').format(class_name, class_name,thresh),
                  fontsize=14)
    dets_ann = ann['coord']
    for i in range(len(dets_ann)):
        ellipse_ann = dets_ann[i, :5] #(r_vertical, r_horizontal, theta, c_x, c_y)
        ellipse = Ellipse(xy=(ellipse_ann[3], ellipse_ann[4]), 
                          width=ellipse_ann[0]*2, 
                          height=ellipse_ann[1]*2, 
                          angle=np.degrees(ellipse_ann[2]), 
                          edgecolor='r', fc='None', lw=2)
        ax.add_patch(ellipse)
    plt.axis('off')
    plt.tight_layout()
    plt.draw()
    plt.show()
    
det_name = [] # detection file name
time_name = [] # detection time
ann_name = [] # annotation file name
for i in range(10):
    det_name.append('FDDB-det-fold-{:0>2}.txt'.format(i+1))
    time_name.append('FDDB-time-fold-{:0>2}.txt'.format(i+1))
    ann_name.append('../FDDB-folds/FDDB-fold-{:0>2}-ellipseList.txt'.format(i+1))

res = []
ann = []
for i in range(10):
    res_det = getRes_det(det_name[i])
    res_time = getRes_time(res_det, time_name[i])
    res.extend(res_time)
    ann_det = getRes_det(ann_name[i])
    ann.extend(ann_det)
 # 显示第 1000 幅图的效果
temp = res[1000]
temp_ann = ann[1000]
showRes(temp, temp_ann)