On the computational complexity of super-resolution imaging in discrete tomography

27^th January 2021, 14:00 Online MT CSACTOO365Team
Andreas Alpers
University of Liverpool

Abstract

Super-resolution imaging aims at improving the resolution of
an image by enhancing it with other images or data that might have been
acquired using different imaging techniques or modalities. Motivated by
applications in plasma physics, we consider the task of doubling the
resolution of tomographic grayscale images of binary objects by fusion
with double-resolution tomographic data that has been acquired from two
viewing angles. We show that this task is polynomial-time solvable if
the gray levels have been reliably determined. The task becomes NP-hard
if the gray levels of some pixels come with an error of +-1 or larger.
The NP-hardness persists for any larger resolution enhancement factor.
This means that noise does not only affect the quality of a
reconstructed image but, less expectedly, also the algorithmic
tractability of the inverse problem itself. (This is joint work with
Peter Gritzmann, TU Munich.)

Additional Materials

• https://epubs.siam.org/doi/10.1137/17M1115629