Fast ANN for High‐Quality Collaborative Filtering

Tsai, Yun‐Ta; Steinberger, Markus; Pająk, Dawid; Pulli, Kari

Fast ANN for High‐Quality Collaborative Filtering

Date

2016

Authors

Tsai, Yun‐Ta
Steinberger, Markus
Pająk, Dawid
Pulli, Kari

Publisher

Abstract

Collaborative filtering collects similar patches, jointly filters them and scatters the output back to input patches; each pixel gets a contribution from each patch that overlaps with it, allowing signal reconstruction from highly corrupted data. Exploiting self‐similarity, however, requires finding matching image patches, which is an expensive operation. We propose a GPU‐friendly approximated‐nearest‐neighbour(ANN) algorithm that produces high‐quality results for any type of collaborative filter. We evaluate our ANN search against state‐of‐the‐art ANN algorithms in several application domains. Our method is orders of magnitudes faster, yet provides similar or higher quality results than the previous work.Collaborative filtering is a powerful, yet computationally demanding denoising approach. (a) Relying on self‐similarity in the input data, collaborative filtering requires the search for patches which are similar to a reference patch (red). Filtering the patches, either by averaging the pixels or modifying the coefficients after a wavelet or Other transformation, removes unwanted noise, and each output pixel is collaboratively filtered using all the denoised image patches that overlap the pixel. Our method accelerates the process of searching for similar patches and facilitates high‐quality collaborative filtering even on mobile devices. Application examples for collaborative filtering include (left: our output; right: noisy input) (b) denoising an image burst, (c) filtering the samples for global illumination and (d) geometry reconstruction.

        @article{10.1111:cgf.12715
,
journal = {Computer Graphics Forum},
title = {{Fast ANN for High‐Quality Collaborative Filtering
}},
author = {Tsai, Yun‐Ta and 
Steinberger, Markus and 
Pająk, Dawid and 
Pulli, Kari
},
year = {2016
},
publisher = {Copyright © 2016 The Eurographics Association and John Wiley & Sons Ltd.
},
DOI = {10.1111/cgf.12715
}
}

URI

https://doi.org/10.1111/cgf.12715

Collections

35-Issue 1

Full item page