🔢 mathematics

A Discrete Radon Transform Based on the Area of Cube-Plane Intersection

This paper presents a computationally efficient, analytically exact discrete Radon transform for voxelized data in arbitrary dimensions by deriving a closed-form expression for the intersection area between a hyperplane and an axis-aligned cube, with a regularized variant proposed to enhance numerical stability.

Original authors: Robert Beinert, Jonas Bresch, Michael Quellmalz

Published 2026-03-17

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Robert Beinert, Jonas Bresch, Michael Quellmalz

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, complex 3D sculpture made of millions of tiny Lego bricks (voxels). You want to understand its shape, compare it to other sculptures, or even reconstruct it from scratch, but you can't just look at it from the outside. You need to "slice" it mentally from every possible angle to see what's inside.

This is the job of the Radon Transform. In the real world, this is how CT scans work: they take X-rays from many angles to build a 3D picture of your insides. In math and computer science, it's a tool used to analyze shapes, move data around efficiently, and even recognize objects.

However, there's a problem. When computers try to do this "slicing" on digital Lego models, they usually have to guess. They might just look at the center of a brick and say, "Okay, the slice goes through here," or they might throw a million random darts at the model to estimate the area (a method called Monte Carlo). These guesses are either too sloppy (missing details) or too slow (taking forever to calculate).

The "Magic Formula" Solution
The authors of this paper, Robert, Jonas, and Michael, decided to stop guessing. They asked a simple question: "If I have a perfect cube (a single Lego brick) and I slice it with a flat sheet of glass at any angle, exactly how much surface area does that slice create?"

They derived a closed-form mathematical formula (a precise recipe) to answer this.

The Analogy: Imagine you are a master chef. Instead of guessing how much of a block of cheese a knife will cut through, you have a magic calculator that tells you the exact surface area of the cut, no matter how weirdly you angle the knife.
The Result: They found that this area isn't a messy, random number. It follows a smooth, predictable pattern (a piecewise polynomial). It's like a staircase that changes its steps depending on where you cut, but the steps are perfectly calculated.

Why is this a big deal?

It's Exact: Because they have the exact formula, they don't need to guess or approximate. If you have a digital image made of cubes, they can calculate the "slice" perfectly.
It's Fast: Their method is like taking a direct highway to the answer. The old way (Monte Carlo) is like driving through every single side street to get there. The paper shows their method is hundreds of times faster, especially in higher dimensions (like 4D or 5D data).
It's Stable: Sometimes, when you slice a cube right on the edge, the math gets shaky. They created a "regularized" version (a safety buffer) that smooths out these wobbles, making the computer less likely to crash or give a weird error.

What did they do with this superpower?
They put their new tool to work in three cool ways:

3D Shape Matching (The "Fingerprint" Test): They used their tool to look at 3D models of chairs, beds, and toilets. By slicing them up mathematically, they could create a unique "fingerprint" for each object. Even if a chair was rotated or squished, their method could still recognize it as a chair. It was much better at this than previous methods.
The "Sliced" Water Balloon (Wasserstein Barycenters): Imagine you have two different shapes made of water (like a sphere and a cube). You want to find the "average" shape between them. This is hard to calculate. Their method slices both shapes, averages the slices, and then rebuilds the average shape. It's like blending two smoothies by mixing their ingredients perfectly rather than just dumping them in a blender.
Classifying Objects: They tested this on a dataset of 3D objects (ModelNet10). Their method correctly identified objects with high accuracy, proving that knowing the exact geometry of a slice helps computers "see" better.

The Bottom Line
Before this paper, computers were like people trying to measure a complex cake by poking it with a stick and guessing the volume. These authors gave them a laser cutter and a precise blueprint. They turned a messy, slow, guessing game into a fast, exact, and reliable calculation. This helps computers understand 3D data much better, whether it's for medical imaging, recognizing objects, or solving complex geometric puzzles.

1. Problem Statement

The Radon transform is a fundamental tool in tomographic imaging, optimal transport, and geometric analysis, linking functions to their integrals over hyperplanes. While continuous formulations are well-understood, numerical computation requires accurate discretization, particularly for voxelized data (images composed of discrete cubes/voxels).

Existing discrete Radon transform (DRT) methods suffer from several limitations:

Approximation Errors: Many methods rely on projecting voxel centers to a line/plane and binning, which ignores the actual geometry of the voxel intersection.
Artifacts: Fourier-based approaches often introduce artifacts when applied to voxelized data due to interpolation issues.
Computational Cost: High-quality approximations using Monte Carlo integration are computationally expensive, especially in higher dimensions ( $d > 3$ ).
Lack of Unified Formulas: Explicit, closed-form expressions for the intersection area of a hyperplane and an axis-aligned hypercube in arbitrary dimensions were missing in a unified, numerically evaluable form.

2. Methodology

The authors propose a novel Discrete Radon Transform (DRT) that is analytically exact for voxelized data. The core methodology involves three main components:

A. Closed-Form Expression for Cube-Plane Intersection

The authors derive a closed-form, piecewise polynomial expression for the Radon transform of an axis-aligned hypercube in arbitrary dimension $d$ .

Theorem 1: Provides the formula for $A^a_\theta(t)$ , representing the $(d-1)$ -dimensional surface area of the intersection between a hypercube $(-a, a]^d$ and a hyperplane $H_\theta(t)$ .
Mathematical Structure: The result is a piecewise polynomial of degree $d-1$ that is $(d-2)$ -times differentiable. It is expressed as a summation over the $2^\ell$ vertices of the cube (where $\ell$ is the number of non-zero components in the direction vector $\theta$ ), utilizing the positive part function $(x)_+$ .
Derivation: The proof utilizes the Fourier Slice Theorem and the Fourier convolution theorem, relating the Radon transform of the indicator function of a cube to the convolution of 1D indicator functions (splines).

B. Regularized Variant (Cube-Slab Intersection)

To improve numerical stability, the authors introduce a regularized variant. Instead of calculating the exact $(d-1)$ -dimensional area of the intersection with a hyperplane (which can be sensitive to floating-point errors), they compute the $d$ -dimensional volume of the intersection between the cube and a thin slab (an $\epsilon$ -neighborhood of the hyperplane).

Corollary 6: Provides a closed-form formula for the volume of the intersection between a cube and a slab $S_\theta(t_1, t_2)$ .
As the slab width $2\epsilon \to 0$ , this volume converges to the exact hyperplane intersection area.

C. Discrete Radon Transform for Voxelized Data

The proposed DRT treats a voxelized image as a sum of weighted indicator functions of cubes.

By linearity, the Radon transform of the image is the sum of the Radon transforms of individual voxels.
Using the derived closed-form formulas (both the exact area and the regularized volume), the method sums the contributions of all voxels intersecting a specific hyperplane.
This approach avoids the "center-projection" approximation and is significantly faster than Monte Carlo sampling.

3. Key Contributions

Explicit Closed-Form Formula: The derivation of a piecewise polynomial expression for the Radon transform of a hypercube in $\mathbb{R}^d$ (Theorem 1), valid for arbitrary directions and offsets.
Regularized Variant: A stable formula for the volume of a cube-slab intersection (Corollary 6), serving as a numerically robust alternative to the exact area calculation.
Voxel-Aware DRT: A computationally efficient algorithm for the discrete Radon transform that utilizes the exact geometric intersection properties of voxels, outperforming simple binning and Monte Carlo methods.
Application Framework: Demonstration of the method in 3D shape matching, classification, and sliced Wasserstein barycenter computation.

4. Results and Experiments

A. Shape Matching and Classification (ModelNet10)

The authors tested the DRT on the ModelNet10 dataset (10 classes of 3D objects).

Radon Shape Matching (Trace Transform): Using feature extractors based on the Radon transform, the method achieved a 71% accuracy on a 3-class subset (bathtubs, chairs, dressers) and 36% on the full 10-class dataset. This outperformed previous attempts to reproduce similar methods due to the more accurate voxel handling.
Normalized Radon CDT (NR-CDT): Applying the affine-invariant Normalized Radon Cumulative Distribution Transform yielded superior results:
- 93% accuracy on the 3-class subset.
- 47% accuracy on the full 10-class dataset (significantly better than random guessing and the standard shape matching approach).
- Affine Invariance: When tested on affinely transformed objects (scaling, shearing, rotation), the mNR-CDT achieved 99% accuracy, confirming its theoretical invariance properties, whereas standard shape matching dropped to 42%.

B. Sliced Wasserstein Approximation and Barycenters

The method was applied to approximate empirical measures using mixtures of uniform measures on cubes (histograms) and computing Sliced Wasserstein Barycenters.

Clustering: The algorithm successfully clustered empirical data points into optimal histograms using the Sliced Wasserstein distance.
Barycenters: Computed barycenters between rotated hemispheres and spheres, visualizing the geometric interpolation effectively.

C. Computational Efficiency vs. Monte Carlo

A critical comparison was made between the proposed exact formula and Monte Carlo integration in 4 dimensions ( $d=4$ ).

Speed: Evaluating the exact formula for 128 angles and 128 radii took < 1 second.
Monte Carlo: Achieving comparable accuracy (<1% error) for just one angle and 128 radii took ~5 seconds using $2^{24}$ samples.
Conclusion: The proposed method is orders of magnitude faster and more accurate than Monte Carlo integration for high-dimensional Radon transforms.

5. Significance

Theoretical Advancement: The paper fills a gap in geometric analysis by providing a unified, explicit formula for cube-hyperplane intersections in arbitrary dimensions, extending classical results by Sommerfeld and Pólya.
Practical Impact: The proposed DRT offers a computationally efficient and analytically exact alternative for processing voxelized data. This is crucial for applications in medical imaging, 3D object recognition, and optimal transport where high-dimensional data and voxel fidelity are required.
Stability and Speed: The regularized slab approach provides a robust solution for numerical implementation, while the closed-form nature eliminates the stochastic noise and high computational cost associated with Monte Carlo methods, making high-dimensional Radon analysis feasible.