Abstract: The appearance gap between sketches and photo-realistic images is a fundamental challenge in sketch based image retrieval (SBIR) systems. The existence of noisy edges on photo-realistic images is a key factor in the enlargement of the appearance gap and significantly degrades retrieval performance. To bridge the gap, we propose a framework consisting of a new line segment-based descriptor named histogram of line relationship (HLR) and a new noise impact reduction algorithm known as object boundary selection. HLR treats sketches and extracted edges of photo-realistic images as a series of piece- wise line segments and captures the relationship between them. Based on the HLR, the object boundary selection algorithm aims to reduce the impact of noisy edges by selecting the shaping edges that best correspond to the object boundaries. Multiple hypotheses are generated for descriptors by hypothetical edge selection. The selection algorithm is formulated to find the best combination of hypotheses to maximize the retrieval score; a fast method is also proposed. To reduce the distraction of false matches in the scoring process, two constraints on spatial and coherent aspects are introduced. We tested the HLR descriptor and the proposed framework on public datasets and a new image dataset of three million images, which we recently collected for SBIR evaluation purposes.

Keywords: Photo-realistic images; histogram of line relationship (HLR); Large-scale sketch retrieval; line segment-based descriptor.