Abstract: Image semantics has the characters of vague, complex, and abstractive, therefore only low-level features are not enough for describing image semantics, and rectuire a combination of image-related content in order to improve the accuracy of the image annotation. In this paper, an image annotation method based on mutual K nearest neighbor graph (MKNNU) was proposed, which builds the relationship between the low-level features, annotation words and images by a mutual K nearest neighbor graph. Mutual K nearest neighbor graph is to extract semantic information from paired nodes, which overcomes the limitation of unilateral mining of the traditional K nearest neighbor graph, and effectively improves the image annotation performance. Based on the analysis on the structure of mutual K nearest neighbor graph,Combined with Random Walk with Restart(RWR)，a fast algorithm was proposed without apparent reducing the precision of the image annotation. Experimental results on the Corel image datasets show the effectiveness of the proposed approach in terms of quality of the image annotation.

Key words: Image annotation, Mutual K adjacency graph, Random walk with restart, Fast solution