A Rank-Order Distance based Clustering Algorithm for Face Tagging
【论文阅读】A Rank-Order Distance based Clustering Algorithm for Face Tagging
原文链接:2011_CVPR_A Rank-Order Distance based Clustering Algorithm for Face Tagging
Rank-Order distance, which measures the dissimilarity between two faces using their neighboring information in the dataset. The Rank-Order distance is motivated by an observation that faces of the same person usually share their top neigh- bors. |
|
由于人脸的复杂场景,比如光照、姿态、表情等因素,绝对距离的度量方式可能会造成相同人的不同照片相似度很低,而不同人的照片反而相似度很高,所以单纯的L1或L2距离已不再适用。
由于大部分家庭照片都拍摄于不同的环境,对于人脸聚类会有一些要求和挑战:
1、相册中的人脸通常会在高维空间形成几个脸部簇,并具有不同的密度,大小和形状。这种非均匀分布使得绝对距离(例如,两个人脸识别特征之间的L1或L2距离)容易失败。如下图所示,男孩的群集比女孩的群集更稀疏。如果我们在这个例子中使用绝对距离,那么这个在中间男孩的脸更接近女孩群。
2、人脸检测通常会返回一些背景中不感兴趣或不喜欢的人脸。通常,我们不想标记这些面孔。聚类算法应该能够处理这些噪声和异常值。
3、算法的运行时间应该满足快速用户交互的要求。
由于复杂的人脸分布,同一人的所有人脸通常由几个子集群组成。由于这些子聚类相对比较紧密,因此可以通过简单的阈值法以Rank-Order距离来强健地识别它们。然而,由于光照,姿态,表达等变化的干扰,子簇之间的连接通常较弱且稀疏。为了解决这个问题,我们提出了一种基于排序距离的聚类算法,以迭代方式合并子簇凝聚的方式。聚类算法结合了聚类级别的秩距离和聚类级别的距离。在每个迭代步骤中,合并任意两个具有较小Rank-Order距离和较小归一化距离的人脸聚类。以这种方式,来自同一个人的不同子集群被有效连接。
Rank-order distance来度量两个人脸的相似度。这个距离是基于一个有趣的观察:同一个人的两张脸有许多共享的top邻居,但是来自不同人的人脸的邻居通常差异很大。
Rank-Order Distance
算法流程
该算法的时间复杂度是O(N2)O(N2),其中DRDR和DNDN对应的两个阈值是固定参数,而K近邻是可以选择的参数,该参数大小直接影响最后聚类的簇数目。