On the complexity of probabilistic image retrieval

Probabilistic image retrieval approaches can lead to significant gains over standard retrieval techniques. However, this occurs at the cost of a significant increase in computational complexity. In fact, closed-form solutions for probabilistic retrieval are currently available only for simple representations such as the Gaussian and the histogram. We analyze the case of mixture densities and exploit the asymptotic equivalence between likelihood and Kullback-Leibler divergence to derive solutions for these models. In particular, (1) we show that the divergence can be computed exactly for vector quantizers and, (2) has an approximate solution for Gaussian mixtures that introduces no significant degradation of the resulting similarity judgments. In both cases, the new solutions have closed-form and computational complexity equivalent to that of standard retrieval approaches, but significantly better retrieval performance.