High-Order Affinity Extension of Normalized Cut and Its Applications

In the normalized cut (Ncut) process, it is crucial to construct an appropriate affinity matrix. The affinity matrix is generally limited to pairwise similarity relations. However, in practice, it is necessary to use high-order affinities in several computer vision applications such as motion segmentation. In this paper, by using high-order singular value decomposition techniques, we derive a high-order affinity model directly from the Ncut relaxation formula, called high-order normalized cut (HNcut). However, in practice, it cannot directly utilize the high-order affinity matrix because of the computational resources required. To address this issue, we adopt and improve various techniques to make the proposed method more practical such as sampling strategy. Finally, we analyze the upper error bound of our algorithm based on matrix perturbation theory. To demonstrate the performance of our HNcut, we compare it with some existing algorithms for the motion segmentation and face clustering problems.