Abstract
Gaussian Mixture Models have become one of the major tools in modern statistical image processing, and allowed performance breakthroughs in patch-based image denoising and restoration problems. Nevertheless, their adoption level was kept relatively low because of the computational cost associated to learning such models on large image databases. This work provides a flflexible and generic tool for dealing with such models without the computational penalty or parameter tuning diffificulties associated to a na¨ıve implementation of GMM-based image restoration tasks. It does so by organising the data manifold in a hirerachical multiscale structure (the Covariance Tree) that can be queried at various scale levels around any point in feature-space. We start by explaining how to construct a Covariance Tree from a subset of the input data, how to enrich its statistics from a larger set in a streaming process, and how to query it effificiently, at any scale. We then demonstrate its usefulness on several applications, including nonlocal image fifiltering, data-driven denoising, reconstruction from random samples and surface modeling from unorganized 3D points sets.