Approximate Nearest Neighbor Fields in Video
This addresses the need for efficient video processing in applications like colorization and denoising, though it is incremental as it builds on existing ANN methods.
The paper tackled the problem of real-time patch matching in videos by introducing RIANN, an algorithm that uses ring intersections in appearance space, achieving up to two orders of magnitude speed improvement over previous methods and enabling real-time operation.
We introduce RIANN (Ring Intersection Approximate Nearest Neighbor search), an algorithm for matching patches of a video to a set of reference patches in real-time. For each query, RIANN finds potential matches by intersecting rings around key points in appearance space. Its search complexity is reversely correlated to the amount of temporal change, making it a good fit for videos, where typically most patches change slowly with time. Experiments show that RIANN is up to two orders of magnitude faster than previous ANN methods, and is the only solution that operates in real-time. We further demonstrate how RIANN can be used for real-time video processing and provide examples for a range of real-time video applications, including colorization, denoising, and several artistic effects.