[Papers][CV][Face Clustering] Face Clustering 동향 분석

11 minute read

Face Clustering 동향 분석

이번 포스팅은 Face Clustering에 대한 내용을 다뤄보려 합니다.

하나의 논문을 깊게 다루기보다는 몇 개 논문의 핵심 아이디어를 살펴보고, 그 흐름이 어떤 식으로 발전하고 있는지에 대해 알아보려 합니다.

본 포스팅에서 다루는 논문은 아래와 같습니다.

Linkage Based Face Clustering via Graph Convolution Network, https://paperswithcode.com/paper/linkage-based-face-clustering-via-graph (Code Available)
Video Face Clustering with Unknown Number of Clusters, https://paperswithcode.com/paper/video-face-clustering-with-unknown-number-of-clusters (Code Available)
FaceMap: Towards Unsupervised Face Clustering via Map Equation, https://paperswithcode.com/paper/facemap-towards-unsupervised-face-clustering (Code Available)
Self-Supervised Video-centralised Transformer for Video Face Clustering, https://arxiv.org/pdf/2203.13166.pdf (Code Unavailable)

Face Clustering

먼저 Face clustering이 무엇인지 간단히 알아보겠습니다.

Face Detection: 이미지에서 face의 위치를 찾는 task
Face recognition: 이미지에서 face를 찾고, 미리 결정된 class에 따라 분류하는 task
Face clustering: 여러 face 이미지들을 미리 결정된 class 없이 identity에 따라 clustering하는 task

즉 Face clustering은 여러 얼굴 이미지들이 있을 때, 각 이미지들로부터 feature를 추출하고 이 feature 간의 유사성을 기반으로 각 이미지를 clustering합니다. 여기서 생성되는 하나의 cluster는 하나의 identity(사람)에 해당합니다.

Face Clustering을 위해서 여러 방법론들이 연구되어 왔고, 이는 크게 supervised learning과 unsupervised learning으로 나눌 수 있습니다. 이번 포스팅에서는 크게 supervised learning에 해당하는 GCN과 Ball Clustering을 사용한 방법, 그리고 unsupervised learning에 해당하는 Map Equation을 사용한 방법에 대해 알아봅니다.

Linkage Based Face Clustering via Graph Convolution Network

첫번째로 소개할 논문은 GCN을 사용한 2019년 4월 발표된 논문입니다.

본 논문에서는 face image의 feature map 상에서 두 feature가 하나의 identity에 해당한다면, 두 node(face) 사이 edge가 존재한다는 것에 기반을 둡니다.

기존의 face clustering 방법들(K-Means, Spectral Clustering, DBSCAN 등)은 다양하고 불균형한 face image를 clustering하는 데 충분한 성능을 보이지 못 했습니다. 이에 대한 가장 큰 이유는 기존의 방법들은 데이터 분포에 제약 사항이 존재하기 때문입니다. 제약 사항으로는 cluster가 convex shape이어야 한다거나, cluster 내의 instance 수가 비슷해야 한다거나, density가 비슷해야 한다는 등의 사항들이 있습니다.

본 논문에서 제안하는 GCN based face clustering은 데이터 분포에 제약 사항을 두지 않음으로써 훨씬 뛰어난 성능을 보였다고 주장합니다.

또한 기존의 방법들이 heuristic 적으로 데이터의 분포를 제한했다면, GCN은 데이터의 분포를 ‘학습’합니다.

본 논문에서 제안하는 face clustering 과정은 다음과 같습니다.

Clustering problem을 link prediction problem으로 치환
각 instance마다 다른 모든 instance들이 아닌, 주변 instance 들에 대해서만 link prediction을 수행
- 이 과정에서 생성된 그래프를 IPS(Instance Pivot Subgraph)라고 합니다.
GCN을 이용해 IPS들을 연결

논문에서는 IPS를 생성하기 위해 ARO(Approximate Rank-Order Clustering) 알고리즘을 사용하며, ARO는 instance 주변 k개의 이웃 노드(kNN)와의 연결성 만을 고려하여 시간 복잡도를 크게 줄인 알고리즘입니다. 여기서 kNN은 확률에 기반한 ANN(Approximate NN)으로 대체되어 그 복잡도를 더욱 줄일 수 있다고 합니다.

생성된 IPS들은 (spatial-based) GCN의 input으로 들어가 최종적인 link prediction이 수행됩니다.

Construction of Instance Pivot Subgraph

IPS가 어떻게 만들어지는지 알아보겠습니다.

Step 1. Node discovery

Pivot instance p에 대하여 h-hop 노드까지를 IPS로 구성합니다. i-th hop에 해당하는 이웃 노드들의 집합을 k_i라 하면, h=3인 경우 집합 V_p는 {k1, k2, k3}로 표현됩니다. 즉, V_p에 자기 자신(p)은 포함되지 않습니다.

Step 2. Node feature normalization

V_p에 해당하는 노드 중 하나를 q라고 하고 q의 feature를 x_q라고 하겠습니다.

두번째 단계에서는 V_p 의 모든 노드들의 feature에 p의 feature x_p를 빼서 normalize합니다. 그리고 normalize를 완료한 각 노드의 feature 집합을 F_p라고 합니다. 여기서 F_p는 pivot node와 neighbor node 간의 차이를 인코딩하고 있다고 할 수 있습니다.

Step 3. Adding edges among nodes

V_p 내의 모든 원소에 대해, 가장 가까운 u개의 이웃 노드(uNN)를 정의합니다. 이때 이웃 노드를 정의하는 범위는 V_p 안에서 하는 것이 아니라 전체 instance에 대해 수행합니다.

V_p에 속하는 임의의 원소 q에 대해 uNN에 속하는 노드 r이 V_p에 속한다면, (q, r)을 연결하는 edge를 추가합니다.

이 과정을 V_p 내의 모든 원소에 대해 반복하여 생성된 그래프를 IPS G_p(V_p, E_p)라고 합니다. IPS의 구조적 형태는 인접 행렬 형태인 A_p(size = |V_p|x|V_p|)로 표현되고, feature는 위에서 구한 F_p로 표현됩니다.

즉, 하나의 IPS는 A matrix와 F matrix로 표현됩니다.

Graph Convolutions on IPS

이제 생성된 IPS를 GCN의 input으로 넣어줍니다. 이제부터 F는 X라고 표기합니다.

Graph convolution layer의 연산은 아래와 같은 수식으로 표현할 수 있습니다.

Calculate G

G는 A로 부터 구합니다. 이때 A로부터 G를 구하는 방법에는 크게 3가지 방법을 사용할 수 있습니다.

Mean Aggregation
Weighted Aggregation
Attention Aggregation

각각에 대한 설명은 생략하겠습니다. 다만 아래로 갈수록 모델 성능이 높아지긴 하는데, 추론 시간 증가에 비해 그 상승폭이 크지 않아서 논문에서는 Mean Aggregation을 사용했습니다.

Multiply G and X

G와 X를 행렬곱합니다. 행렬곱한 결과는 IPS에 대한 취합된 정보들을 인코딩하고 있는 것으로 해석할 수 있습니다.

Concat X and GX

다음으로 X와 GX를 feature dimension으로 concat합니다.

Multiply W(Linear layer)

이때의 W는 learnable parameter입니다.

apply relu activation(σ)

계산된 행렬은 relu activation을 통과합니다.

GCN 학습 시 back propagation에서는 1-hop neighbor들에 대한 오차값만 사용합니다. 이는 1-hop neighbors 만을 사용할 때 positive sample과 negative sample의 수의 균형이 가장 잘 맞기 때문이라고 합니다. 여기서 positive sample이란 실제로 pivot과 동일한 identity의 node들이고, negative sample은 다른 identity의 node들입니다.

아래 그림을 보면 2개의 graph convolution layer를 사용할 때 iteration에 따라 positive node들과 negative node들이 잘 분류되는 것을 확인할 수 있습니다.

Link Merging

GCN을 거치고 나면, 각 IPS의 각 edge에 대한 가중치을 얻게 됩니다. 이 가중치가 높을수록 edge가 연결하는 두 sample이 동일한 identity를 가질 확률이 높은 것입니다.

최종 clustering된 graph를 만들기 위해 가장 쉬운 방법은 threshold를 설정하여 threshold 이하의 edge들은 끊어버리는 것이지만, 이는 threshold 값에 큰 영향을 받습니다.

본 논문에서는 이보다 더 진보된 방식인 pseudo label propagation을 사용했습니다. 해당 기법은 iteration을 반복하면서 매 iteration마다 특정 threshold 이하의 edge는 연결을 끊되, 특정 size 이상의 cluster의 경우 연결을 끊지 않는 것입니다.

Iteration이 증가할수록 threshold 값 또한 증가하고, 특정 size 이상의 cluster가 더 이상 없으면 iteration을 종료합니다.

Evaluation

본 논문에서는 metric으로 NMI(normalized mutual information)와 BCubed F-measure를 사용했습니다.

NMI

H는 impurity, I는 mutual information을 나타냅니다.

Bcubed F-measure

L이 ground truth label, C가 cluster label이라고 할 때, 두 sample의 pairwise correctness score는 아래와 같습니다.

그리고 Precision과 Recall은 아래와 같이 구할 수 있습니다.

최종 F-measure는 P와 R의 조화평균입니다.

결과적으로 Bcubed F-measure는 각 sample에 대한 precision과 recall 값의 조화평균입니다.

IPS construction 시에 설정할 수 있는 hyperparameter로 h (number of hops), k_i (number of picked nearest neighbors in each hop), u (number of linked nearest neighbors u for picking edges)가 있습니다.

본 논문에서는 이에 대한 실험을 진행했고, 아래와 같은 관찰 결과를 얻었습니다.

h가 3 이상일 때부터는 성능 증가가 거의 없다.
k1이 증가하면 recall 값이 증가하고, k2가 증가하면 precision 값이 증가한다.
- k가 증가하면 성능은 증가하지만, 추론 시간 또한 증가한다.
u는 모델 성능에 큰 영향을 주지 않는다.

결과적으로 본 논문에서는 h=2, k1=80, k2=5, u=5를 선택했습니다.

아래는 GCN-based face clustering과 다른 기법들을 비교한 성능 평가표입니다.

Contributions

GCN을 사용해 face clustering을 link prediction task로 치환
데이터 분포에 대한 제약을 두지 않음으로써 성능 향상(singleton cluster 감소)
Multi-view data, Multi-modal data의 활용 가능성
SOTA 성능 달성

Codes

학습데이터: face feature file(binary data), label(plain text), knn file(selective)
https://github.com/yl-1993/learn-to-cluster
https://github.com/Zhongdao/gcn_clustering

Video Face Clustering with Unknown Number of Clusters (BCL)

다음으로 소개할 논문은 같은 해인 2019년 8월 발표된 Ball Cluster Learning(BCL)을 사용한 face clustering 논문입니다.

BCL이란, embedding space의 각 cluster를 동일한 크기의 ball로 정교화하는 과정입니다. 그 과정에서 모든 sample들은 하나의 ball 안에 위치하게 되고, 각 ball들은 overlap되지 않습니다.

본 논문의 최종 목표는 아래와 같습니다.

정해진 cluster의 개수 없이, video 내의 모든 인물(잠깐 등장한 인물을 모두 포함해서)을 동일한 크기의 ball에 할당하는 것

각 ball의 크기(반지름)는 학습 과정에서 결정되고, 반지름의 크기에 따라 알고리즘의 종료 시점이 결정됩니다. 또한 BCL의 장점은 batch size와 number of clusters에 linear한 시간 복잡도를 가진다는 것입니다.

Constraints

Constraint는 similar case와 dissimilar case로 나뉩니다. 여기서 Similar하다는 것은 두 sample x_i와 x_j가 같은 label을 가진다는 것을 말합니다. k번째 set of similar samples(즉, cluster)를 C_k라고 하겠습니다.

Similar case

먼저 용어부터 정리하겠습니다.

µ_k는 cluster C_k의 중심 좌표입니다.
f_i는 x_i의 l2 normalized embedding으로, CNN module을 통해 face image를 feature representation x_i 로 변환한 후에 한 번 더 embedding한 값에 해당합니다. (이로부터 약 2.5%의 성능 향상을 이뤘다고 합니다)
d²은 euclidean distance입니다.

이때 C_k에 속하는 모든 sample x_i는 아래 식을 만족해야 합니다.

원의 방정식(x² + y² = r²)을 떠올려보면 b = r²에 해당함을 어렵지 않게 알 수 있습니다. 이때 b는 learnable parameter입니다.

따라서 C_k에 속하는 두 sample x_i, x_j는 아래식을 만족해야 합니다.

이로부터 2r을 두 sample의 similar constraint로 사용할 수 있음을 알 수 있습니다.

Dissimilar case

위로부터, dissimilar sample 사이 거리는 2r을 넘어야 하는 것을 알 수 있습니다. 그리고 따라서, C_k에 속하는 sample f_i와 또 다른 cluster C_v 의 중심좌표 µ_v 사이의 거리는 3r을 넘어야 합니다. r² = b 이기 때문에 이는 아래와 같이 b에 관해 나타낼 수 있습니다.

그리고 논문에서는 γ = 9b + ε 로 나타내어 최종적으로 두 sample의 dissimilar constraint를 아래와 같이 정리합니다.

Problem Formulation

위에서 구한 constraint들을 만족하는 b를 구하기 위해 loss function을 아래와 같이 정의합니다.

여기서 L_sim은 similar samples에 대한 loss이고, L_dis는 dissimilar samples에 대한 loss입니다.

Clustering Algorithm

본 논문에서는 Clustering algorithm으로 HAC(Hierarchical Aggolmerative Clustering) method를 사용합니다.

HAC에서 각 sample들은 자기 자신만을 포함하는 cluster에서 시작하여, iteration을 진행하면서 유사한 cluster들끼리 merge됩니다. 여기서 유사하다의 기준은 아래 수식을 만족하는 cluster입니다.

그리고 앞에서 설정한 similar constraint에 따라, τ = (2r)² = 4b 입니다.

위 수식을 만족하는 cluster가 없으면 HAC 알고리즘은 종료됩니다.