Automatic image annotation aims at assigning a set of textual labels to an image that describes its semantics. In real-world datasets with large vocabularies, each image is usually annotated with only a subset of all possible relevant labels. This leads to the problem of learning with missing labels. Moreover, several existing approaches for image annotation aim at producing a set which contains as many relevant labels as possible for a given image. However, such a set is usually unnecessary and contains redundant labels. This leads to the task of diverse image annotation, which aims at predicting labels that are collectively representative as well as diverse. In this paper, we study a new task called diverse image annotation with missing labels (DIAML), which is a fusion of these two practical aspects of the conventional image annotation task; i.e., diverse image annotation, and image annotation with missing labels. For this, we also propose a new k-nearest neighbours (kNN)based algorithm, called per-label k-nearest neighbours (or PL-kNN), that addresses both these challenges simultaneously. For a given image, rather than identifying its neighbours in the feature-space as done in the conventional kNN algorithm, PL-kNN first creates diverse partitions of the (training)samples based on label information, and then predicts the confidence for each label using a fixed number of nearest neighbours from the corresponding partition. The label-specific partitioning and neighbourhood selection steps inherently address the issue of missing labels as well. Extensive experiments on benchmark datasets show that though conceptually simple, the proposed method consistently outperforms state-of-the-art methods that address either of these two (sub-)tasks, thus establishing a strong baseline for the new DIAML task. © 2019 Elsevier Ltd