A random walk on image patches

DOI10.1137/110839370MaRDI QIDQ2912290zbMATH OpenOpenAlexWikidataFDO

Authors Kye M. Taylor, François G. Meyer

Publication date 14 September 2012

Published in SIAM Journal on Imaging Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1107.0414

zbMATH Keywords

diffusion mapsgraph LaplacianLaplacian eigenmapscommute timeimage patches

Mathematics Subject Classification ID

Applications of graph theory (05C90) Image analysis in multivariate analysis (62H35) Random walks on graphs (05C81)

Abstract: In this paper we address the problem of understanding the success of algorithms that organize patches according to graph-based metrics. Algorithms that analyze patches extracted from images or time series have led to state-of-the art techniques for classification, denoising, and the study of nonlinear dynamics. The main contribution of this work is to provide a theoretical explanation for the above experimental observations. Our approach relies on a detailed analysis of the commute time metric on prototypical graph models that epitomize the geometry observed in general patch graphs. We prove that a parametrization of the graph based on commute times shrinks the mutual distances between patches that correspond to rapid local changes in the signal, while the distances between patches that correspond to slow local changes expand. In effect, our results explain why the parametrization of the set of patches based on the eigenfunctions of the Laplacian can concentrate patches that correspond to rapid local changes, which would otherwise be shattered in the space of patches. While our results are based on a large sample analysis, numerical experimentations on synthetic and real data indicate that the results hold for datasets that are very small in practice.

Recommendations

• Perturbation of the eigenvectors of the graph Laplacian: application to image denoising
• How to explore the patch space
• Graph simplification and matching using commute times
• Machine Learning: ECML 2004
• How to compare noisy patches? patch similarity beyond Gaussian noise

Cited in

(5)

• How to explore the patch space
• Perturbation of the eigenvectors of the graph Laplacian: application to image denoising
• scientific article; zbMATH DE number 1552495 (Why is no real title available?)
• Random walk approach to image enhancement.
• scientific article; zbMATH DE number 3988353 (Why is no real title available?)

This page was built for publication: A random walk on image patches

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2912290)