  Efficiently computing attention maps for videos is challenging due to the
motion of objects between frames. While a standard non-local search is
high-quality for a window surrounding each query point, the window's small size
cannot accommodate motion. Methods for long-range motion use an auxiliary
network to predict the most similar key coordinates as offsets from each query
location. However, accurately predicting this flow field of offsets remains
challenging, even for large-scale networks. Small spatial inaccuracies
significantly impact the attention module's quality. This paper proposes a
search strategy that combines the quality of a non-local search with the range
of predicted offsets. The method, named Shifted Non-Local Search, executes a
small grid search surrounding the predicted offsets to correct small spatial
errors. Our method's in-place computation consumes 10 times less memory and is
over 3 times faster than previous work. Experimentally, correcting the small
spatial errors improves the video frame alignment quality by over 3 dB PSNR.
Our search upgrades existing space-time attention modules, which improves video
denoising results by 0.30 dB PSNR for a 7.5% increase in overall runtime. We
integrate our space-time attention module into a UNet-like architecture to
achieve state-of-the-art results on video denoising.
