Reconstruction of Convex Bodies from Brightness Functions

R. J. Gardner, Peyman MilanfarDiscret. Comput. Geom 2003 · DOI

Introduction

In the realm of geometric tomography, the challenge of reconstructing an object from its projections is a classic problem with deep theoretical roots. While the uniqueness of such reconstructions for origin-symmetric convex bodies was established by Aleksandrov in 1937, the proof was non-constructive. This research bridges the gap between theory and application by introducing the first convergent algorithms for 3D reconstruction based on brightness functions—the volumes of an object's orthogonal projections.

The Problem: Learning from Shadows

The core question in this field is whether the volumes of an object's projections onto various planes are sufficient to determine its shape. Aleksandrov's theorem guarantees that for origin-symmetric convex bodies, the brightness function uniquely identifies the body. However, translating this mathematical certainty into a practical tool requires a method to handle finite, potentially noisy measurements and produce a tangible geometric representation.

Methodology: A Two-Phase Pipeline

The authors propose a robust framework that decomposes the reconstruction into two distinct phases:

Phase I: Inverting the Cosine Transform

The brightness function is linked to the object's surface area measure through a cosine transform. To invert this relationship, three algorithmic variants are proposed:

  • BrightLSQ: Utilizes constrained linear least-squares, offering stability in the presence of noisy data.
  • BrightLP: Employs linear programming for faster computation when data is exact.
  • BrightNFacets: A nonlinear approach tailored for scenarios where the number of facets in the target polytope is known.

Phase II: Geometric Polytope Reconstruction

Once the surface area measures (normals and areas) are estimated, the MinkData algorithm is applied. Based on Minkowski’s existence theorem, this step solves a concave optimization problem to determine the vertices and faces of the approximating polytope by maximizing volume under facet area constraints.

The authors also demonstrate that for rational convex polytopes of fixed dimension, this process can be executed in oracle-polynomial time, ensuring theoretical efficiency.

Experimental Results

The algorithms were validated using synthetic "ground truth" shapes to assess convergence and accuracy:

  • Octahedron Recovery: A regular octahedron was successfully reconstructed from 21 measurement directions in under three minutes on legacy hardware.
  • Ellipsoid Approximation: For smooth bodies like ellipsoids, the algorithms produced a 72-faceted polyhedral approximation using 50 random directions, achieving a brightness match within 2% of the original.
  • Performance Bottlenecks: The study identified Phase II as the primary computational bottleneck, largely due to the intensive volume calculations required during the optimization of the polytope.

Key Insights and Limitations

A critical insight of this work is the role of origin symmetry as a necessary constraint for uniqueness; without it, the problem becomes ill-posed. While the least-squares approach provides robustness against real-world sensor noise, the current implementation faces challenges in scaling to high-dimensional spaces or very high facet counts due to the nonlinearity of Phase II.

Conclusion

By transforming a 1937 existence theorem into a suite of convergent algorithms, this research provides a foundational toolkit for geometric tomography. Future work aims to optimize volume computation and explore methods for handling non-symmetric bodies through "Blaschke bodies," potentially expanding the reach of these reconstruction techniques to a broader class of geometric objects.

Summary updated

BibTeX
@article{gardner2003reconstruction,
  author = {R. J. Gardner and Peyman Milanfar},
  title = {{Reconstruction of Convex Bodies from Brightness Functions}},
  journal = {Discret. Comput. Geom.},
  year = {2003},
  doi = {10.1007/s00454-002-0759-2},
}
Figure