Introduction
The Radon transform is a fundamental mathematical tool used to reconstruct internal structures from external measurements. It serves as the backbone for technologies such as Computed Tomography (CT) in medicine and seismic imaging in geophysics. By calculating line integrals across an image, the transform maps spatial data into a "sinogram" space. However, traditional discrete implementations of the Radon transform are computationally intensive, typically requiring $O(N^3)$ operations for an $N \times N$ image. This cubic scaling significantly limits the feasibility of high-resolution, real-time processing.
The Approximate Discrete Radon Transform (ADRT)
The Approximate Discrete Radon Transform (ADRT) offers a more efficient alternative. By utilizing a "divide and conquer" approach similar to the Fast Fourier Transform (FFT), the ADRT reduces the computational complexity to $O(N^2 \log N)$. While the theory for ADRT has been established since the late 1990s, the scientific community has lacked a high-performance, open-source, and easy-to-use implementation. Researchers often had to develop custom, private codebases, which hindered reproducibility and slowed the adoption of ADRT in fields like machine learning and large-scale scientific computing.
Implementation of the adrt Package
The adrt package addresses this gap by providing a production-ready Python implementation. To ensure high performance while maintaining ease of use, the package employs a hybrid architecture:
- C++ Core: The performance-critical algorithms are implemented in C++, allowing for low-level optimizations and efficient memory management.
- Parallelization: The implementation supports multi-core CPU threading via OpenMP, enabling significant speedups on modern hardware.
- Python Interface: The package exposes a seamless interface for Python users, operating directly on NumPy arrays. This integration makes it compatible with the broader scientific Python ecosystem.
- Functional Scope: Beyond the forward ADRT, the package includes essential utilities for image reconstruction, such as back-projection and multiple inversion methods (including a single-quadrant inverse and a full multigrid inverse).
Performance Evaluation
The primary claim of the adrt package is its adherence to the theoretical $O(N^2 \log N)$ complexity. To verify this, the authors conducted extensive benchmarks using synthetic images of varying sizes, ranging from $2^2 \times 2^2$ up to $2^{14} \times 2^{14}$ pixels.
As shown in the figure above, the measured execution time on an Intel Xeon Platinum 8268 processor closely follows the predicted $O(N^2 \log_2 N)$ trendline. This efficiency is transformative for high-resolution data; for a $1024 \times 1024$ image, the reduction in operations compared to an $O(N^3)$ algorithm is substantial. Furthermore, the ADRT maintains high accuracy, approximating the continuous Radon transform with an error of $O(N^{-1} \log N)$, which is sufficient for most scientific applications.
Conclusion and Future Work
The adrt package provides the first general-purpose, open-source implementation of the ADRT for the Python ecosystem. By making this efficient transform accessible, the authors provide a "testbed" for researchers to explore the properties of the transform and its applications in iterative reconstruction.
While the current implementation is highly optimized for CPUs, future work could involve GPU acceleration using CUDA or OpenCL to further enhance performance for real-time imaging tasks. Additionally, while the package provides core routines, more complex iterative solvers are currently provided as documentation examples, suggesting a path for future built-in feature expansion.
Summary updated