Clustering Millions of Faces by Identity 论文阅读

这里只记录我在读此篇论文时认为重要的章节部分。

一、论文背景和贡献

1，论文背景

1）在2013年波士顿马拉松爆炸案发生后，有成千上万的图像和视频需要在短时间内分析调查，从而缩小调查范围。

2）人脸聚类也试图解决以下问题：给定大量未标记的人脸图像，将它们聚为这些数据中的单个标识。这种情况出现在从社交媒体到执法等许多不同的应用场景中。

2，论文贡献

一种改进的聚类算法，改进了Rank-Order Clustering提出的方法。贡献点如下：

   1，利用近似最近邻方法的可扩展性，获得更好的聚类精度；
   2，基于深度网络的大规模人脸识别的大规模人脸聚类实验；
   3，提出的人脸聚类方法对视频的适用性做了初步调查；
   4，定义了每个聚类质量度量。

二、聚类算法

1，人脸聚类流程

2，获取人脸特征

获取人脸特征步骤：
1，用dlib进行68个特征点的提取
2，用dlib进行人脸对齐（face align）
3，构建卷积神经网络提取人脸特征
4，最终输出320维的人脸feature

3，Rank-Order Clustering 改进前的算法

是一种层级聚类

基于排序距离的聚类算法（人脸与其他人脸的相似度的排序）

3.1 层级聚类

1，将所有数据点本身作为簇；
2，然后找出距离最近（相似度最高）的两个簇，且其距离小于给定的threshhold，则将它们合为一个；
3，不断重复以上步骤直到不能再合并（大于threshhold）。

4，特点是不需要指定聚类数量K。

3.2 Rank-Order Distance

First step: a set of unlabeled face images

Second step: nearest neighbor lists are computed for each image

Third step: 

3.3 Rank-Order Distance Measure

fa(i)表示a的列表中第i张脸,Ob(fa(i))则表示脸fa(i)在b的列表中的序号位置。

3.4 Approximate Rank-Order Clustering 改进后的聚类算法

Rank-Order Clustering方法存在一个明显的问题，因为它需要计算数据集中的每个样本的最近邻样本列表，如果直接计算，时间成本为O(n2)。

Approximate Rank-Order Clustering改进点：
   1.使用opencv FLANN库的随机k-d tree算法求出每个人脸图片的k个最近邻图片排序。

   2.不计算每一个人脸的所有最近邻列表，而是计算每一个人脸的k个最近邻列表。

改进点 1 使用opencv FLANN库的k-d tree算法求出每个人脸图片的近邻图片排序：

这步用于前面的Second step: nearest neighbor lists are computed for each image

1，k-d tree是k-dimensional树的简称，利用k-d tree搜索，利用特殊的结构存储数据，能减少大部分的数据搜索，从而减少距离计算的次数。
2，对于中等规模的数据集，时间复杂度能降到O(nlogn)。

3，但是要注意，kd树更适合于数据样本数目远大于空间维数的k近邻搜索，当空间维数接近于样本数目时，它的效率会迅速下降，接近于线性扫描。

改进点2 计算每一个人脸的k个最近邻列表：

其中Ib(x,k)是一个指示函数，如果Ob(fa(i))输入b的k近邻中，则为值为0，否则为1。忽略了距离排序顺序，只关注在k近邻中还是不在。

举例：If k= 4, dm(a,b) = (0+1+0+1) = 2

簇距离归一化公式：

3.5 聚类步骤：

为数据集中的每一张脸提取深度特征；
2) 为数据集中的每个人脸计算一组k最近邻列表；
3) 计算每个人脸与其他人脸的簇距离，用前面的归一化公式；
4) 合并距离低于阈值的所有人脸对。

三、算法评估

请参考博文 人脸聚类Fscore评估

四、实验结果

五、总结

基于rank-order cluster论文，利用FLANN库的随机 k-d tree算法计算每个人脸的rank-order，并从计算每个人脸的rank-order distance改进为只计算前k个近邻人脸的距离。从而提高了准确率，减少了算法的时间复杂度。


介绍了一种评估人脸聚类算法Fscore的计算方法。