Semantic segmentation, by which an image is decomposed into regions with their respective semantic labels, is often the first step towards image understanding. Existing research on this regard is mainly performed under two conditions: the fully-supervised setting that relies on a set of images with pixel-level labels and the weakly-supervised one that uses only image-level labels. In both cases, the labeling task is time-consuming and laborious, and thus training data are always limited. In practice, there are voluminous on-line images, which unfortunately often have only incomplete image-level labels (tags) but would otherwise be potentially useful for a learning-based algorithm. Only limited efforts have been attempted on using such coarsely and incompletely labelled data for semantic segmentation. This paper proposes a new approach to semantic segmentation of a set of partially-labelled images, using a formulation considering information from multiple visual similar images. Experiments on several popular datasets, with comparison with existing methods, demonstrate evident performance improvement of the proposed approach.