With deep convolutional features, cross-region matching (CRM) has recently shown superior performance on image retrieval. It evaluates image similarity by comparing image regions at different locations and scales, and is therefore more robust to geometric variance of objects. This paper firstly scrutinizes CRM based image retrieval to provide a rigorous probabilistic interpretation by following the probability ranking principle. In addition to manifesting the assumptions implicitly taken by CRM, our interpretation highlights a fundamental issue hindering the performance of CRM—when comparing two image regions, CRM ignores modeling the distribution of the visual concept class associated with an image region, making the similarity comparison less precise. Taking advantage of the unprecedented representation capability of deep convolutional features, this paper proposes one approach to tackle that issue. It treats locally clustered image regions as a pseudo-labeled class sharing the same visual concept, and utilizes them to model the distribution of the visual concept class associated with an image region. Both non-parametric and parametric methods are developed for this purpose, with careful probabilistic justification. Extensive experimental study on multiple benchmark datasets demonstrates the superior performance of the proposed pseudo-label approach to CRM and other comparable methods, with the maximum improvement of more than 10 percentage points over CRM.