A decomposition technique for reconstructing discrete sets from four projections

摘要

The reconstruction of discrete sets from four projections is in general an NP-hard problem. In this paper we study the class of decomposable discrete sets and give an efficient reconstruction algorithm for this class using four projections. It is also shown that an arbitrary discrete set which is Q-convex along the horizontal and vertical directions and consists of several components is decomposable. As a consequence of decomposability we get that in a subclass of hv-convex discrete sets the reconstruction from four projections can also be solved in polynomial time. Possible extensions of our method are also discussed.