Graph-based dimensionality reduction for KNN-based image annotation

KNN-based image annotation method is proved to be very successful. However, it suffers from two issues: (1) high computational cost; (2) the difficulty of finding semantically similar images. In this paper, we propose a graph-based dimensionality reduction method to solve the two problems by adapting the locality sensitive discriminant analysis method [1] to multi-label setting. We first determine relevant and irrelevant images based on label information and construct relevant and irrelevant graphs by focusing on the visually similar relevant and irrelevant images. A linear feature transformation matrix is derived by considering the two graphs. The transformation can map the images to a low-dimensional subspace in which neighborhood relevant images are pulled closer while irrelevant images are pushed away. Thus the new feature after dimensionality reduction is quite fit for KNN-based image annotation. Experiments on the Corel dataset also demonstrate the effectiveness of our dimensionality reduction method for KNN-based image annotation.