Edge-aware image smoothing using commute time distances

Most edge-aware smoothing methods are based on the Euclidean distance to measure the similarity between adjacent pixels. This paper exploits the properties of the commute time to extend the notion of 'similarity' in this context. The intuition is that since the commute time reflects the effect of all possible weighted paths between nodes (pixels), it can account for the global distribution of image features. The commute time is characterized by eigenvectors of a large Laplacian matrix, which is very costly even with sophisticated eigen-solver. To this end, we further employ a multiscale algorithm for approximating the eigenvector computation efficiently. It is analogous to the classical Nystrom's method for low rank matrix approximation. However, we do not depend on long-range connections between nodes, allowing one to include spatial coordinates in defining feature space. Extensive experimental validation demonstrates the benefits of using the commute time in a range of image processing applications, such as edge-aware image smoothing, texture filtering, and local edit propagation.