Abstract

We introduce RIANN (Ring Intersection ApproximateNearest Neighbor search), an algorithm for matchingpatches of a video to a set of reference patches in real-time.For each query, RIANN finds potential matches by intersect-ing rings around key points in appearance space. Its searchcomplexity is reversely correlated to the amount of tempo-ral 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 canbe used for real-time video processing and provide exam-ples for a range of real-time video applications, including colorization, denoising, and several artistic effects.