Factorization of the translation kernel for fast rigid image alignment

Aaditya Rangan, Marina Spivak, Joakim Andén, Alex Barnett

Research output: Contribution to journalArticlepeer-review


An important component of many image alignment methods is the calculation of inner products (correlations) between an image of n × n pixels and another image translated by some shift and rotated by some angle. For robust alignment of an image pair, the number of considered shifts and angles is typically high, thus the inner product calculation becomes a bottleneck. Existing methods, based on fast Fourier transforms (FFTs), compute all such inner products with computational complexity O(n3 log n) per image pair, which is reduced to O(Nn2) if only N distinct shifts are needed. We propose to use a factorization of the translation kernel (FTK), an optimal interpolation method which represents images in a Fourier-Bessel basis and uses a rank-H approximation of the translation kernel via an operator singular value decomposition (SVD). Its complexity is O(Hn(n + N)) per image pair. We prove that H = O((W + log(1/∈))2), where 2W is the magnitude of the maximum desired shift in pixels and ∈ is the desired accuracy. For fixed W this leads to an acceleration when N is large, such as when sub-pixel shift grids are considered. Finally, we present numerical results in an electron cryomicroscopy application showing speedup factors of 3-10 with respect to the state of the art.

Original languageEnglish (US)
Article number024001
JournalInverse Problems
Issue number2
StatePublished - 2020


  • Fourier-Bessel basis
  • Interpolation
  • Rigid image alignment
  • Single-particle electron cryomicroscopy
  • Singular value decomposition

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Mathematical Physics
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'Factorization of the translation kernel for fast rigid image alignment'. Together they form a unique fingerprint.

Cite this