패널티가 추가된 Ncut에 기반한 얼굴 클러스터링

Abstract

본 논문에서는 얼굴 클러스터링을 위해 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보다 좋은 성능을 보였다.