This paper proposes a novel clustering algorithm for face clustering which is derived from normalized cut (Ncut) by modifying the objective function. In the proposed method, called penalized Ncut (PNcut), prior knowledge is incorporated in traditional Ncut to improve clustering performance. PNcut assumes a small amount of clustering constraints: cannot link constraint and must link constraint. The constraints are included as penalty terms to PNcut and the penalty terms in PNcut are formulate-able in a trace of matrix. It enables minimize PNcut problem to be solved easily using generalized eigenvalue problem. In the face clustering task, we incorporate two constraints: 1. faces detected from same image should not be in same cluster, 2. we can synthesis a new face by flip left to right a original face and the original face and the synthesized face should be in same cluster. We will report on experiments on ORL database of faces that having variance pose and facial expression. And the experimental results show that proposed PNcut outperforms Ncut.
본 논문에서는 얼굴 클러스터링을 위해 normalized cut(Ncut) 알고리즘을 기반으로한 새로운 클러스터링 알고리즘을 제안한다. 제안하고자 하는 알고리즘인 패널티가 추가된 Ncut(PNcut)의 목적은 데이터 쌍에 대한 제약조건이 추가적인 기반지식으로 존재할 때 이를 적용함으로써 클러스터링 성능을 향상시키는 것이다. PNcut에서는 데이터에 대해 두 가지 제약조건: cannot link 제약조건(CL)과 must link 제약조건(ML)을 가정하고 두 가지 제약조건을 Ncut의 목적함수에 패널티 항으로 삽입하여 효과적으로 기반 지식을 적용하였다. 또한 삽입된 CL과 ML 패널티 항은 행렬의 trace 형태로 변환이 가능함을 보여 PNcut을 푸는 문제를 일반화된 고유치 문제로 바꾸어 쉽게 풀 수 있음을 보였다. 얼굴 클러스터링에 있어 PNcut을 적용하기 위해 두가지의 제약조건: 1. 같은 사진에서 검출된 얼굴은 다른 사람의 얼굴일 가능성이 크다, 2. 검출된 얼굴을 좌우반전 등을 통해 새로운 얼굴을 합성할 수 있으며 원래의 얼굴과 합성된 얼굴은 같은 사람이다. 를 각각 CL과 ML로 정의하였다. ORL 얼굴 데이터베이스에 대해 실험한 결과 PNcut은 Ncut보다 좋은 성능을 보였다.
