# Approximate Nearest Neighbor Fields in Video

arXiv: https://arxiv.org/abs/1508.07953 · HTML: https://mlsanity.com/paper/1508.07953/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Aug 2015.

## Built on by (most cited first, 6 of 6)

- [Video Colorization with Pre-trained Text-to-Image Diffusion Models](https://mlsanity.com/paper/2306.01732/) (2023)
- [Exemplar-based Video Colorization with Long-term Spatiotemporal Dependency](https://mlsanity.com/paper/2303.15081/) (2023)
- [Temporal Consistent Automatic Video Colorization via Semantic Correspondence](https://mlsanity.com/paper/2305.07904/) (2023)
- [Efficient High-Resolution Template Matching with Vector Quantized Nearest Neighbour Fields](https://mlsanity.com/paper/2306.15010/) (2023)
- [Computer-aided Colorization State-of-the-science: A Survey](https://mlsanity.com/paper/2410.02288/) (2024)
- [GPU-accelerated Multi-relational Parallel Graph Retrieval for Web-scale Recommendations](https://mlsanity.com/paper/2502.11490/) (2025)

## Abstract (arXiv)

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.