  We present a novel convex relaxation and a corresponding inference algorithm
for the non-binary discrete tomography problem, that is, reconstructing
discrete-valued images from few linear measurements. In contrast to state of
the art approaches that split the problem into a continuous reconstruction
problem for the linear measurement constraints and a discrete labeling problem
to enforce discrete-valued reconstructions, we propose a joint formulation that
addresses both problems simultaneously, resulting in a tighter convex
relaxation. For this purpose a constrained graphical model is set up and
evaluated using a novel relaxation optimized by dual decomposition. We evaluate
our approach experimentally and show superior solutions both mathematically
(tighter relaxation) and experimentally in comparison to previously proposed
relaxations.
