Core Routines

Low-level routines for observing or influencing the basic algorithms.

The adrt.core module provides low-level routines that make it possible to observe the progress of other iterative algorithms provided in this package, or to intervene in their computation.

Broadly, there are two types of routines provided here: generators which yield snapshots of each phase in the iterative computation; and single-step functions which allow executing a single, specified step.

These routines could be used to implement the basic routines from the adrt module; however the implementations there are more efficient. If you only want the final result of the basic algorithms, you should use the functions from the main adrt module.

However, if you want to observe or modify the progress of the basic algorithms, these routines make this possible. If you want only to observe the individual steps of the iterative computations—but not modify them—then the iterator routines here may be useful. Otherwise, if you want to perform more advanced operations and intervene in and modify the progress of the computations, the single-step routines make that possible.

Generator Routines

The main algorithms implemented in this package are internally iterative. For example, the ADRT merges line segments, doubling their lengths until they span the full size of the input.

The low-level routines here make it possible to observe the progress of these iterations. These are generator functions that will yield snapshots of the iterative computation after each step. Their final snapshots are equivalent to the outputs of the basic algorithms in the adrt module.

adrt.core.adrt_iter(a, /, *, copy=True)

Yield individual steps of the ADRT.

The ADRT implemented in adrt.adrt() is internally an iterative algorithm. Sums along line segments of a given length are approximated by joining sums along line segments of half length in a bottom-up fashion from segments of length two.

This function allows you to observe individual steps of the ADRT. It is a generator which will yield first the initialized array, followed by the outputs of each iteration of the ADRT.

Parameters:

• a (numpy.ndarray of float) – The array for which steps of the ADRT will be computed. This array must have a square shape, with sides a power of two.

• copy (bool, optional) – If True (default), the arrays produced by this generator are independent copies. Otherwise, read-only views are produced and these must not be modified without making a copy first.

Yields:

numpy.ndarray of float – Successive stages of the ADRT computation. First, the unprocessed array computed by adrt_init() followed by snapshots of progress after each ADRT iteration.

Note

If you only want the result of the last step (the full ADRT) and are not interested in the intermediate steps, use the more efficient adrt.adrt().

adrt.core.bdrt_iter(a, /, *, copy=True)

Yield individual steps of the bdrt.

The implementation of adrt.bdrt() is internally an iterative algorithm. This function allows you to observe individual steps of the bdrt. It is a generator which will yield the outputs of each iteration of the bdrt.

Parameters:

• a (numpy.ndarray of float) – The array for which steps of the backprojection will be computed. Array a must have the shape of an ADRT output.

• copy (bool, optional) – If True (default), the arrays produced by this generator are independent copies. Otherwise, read-only views are produced and these must not be modified without making a copy first.

Yields:

numpy.ndarray of float – Successive stages of the bdrt computation, a snapshot of the progress after each bdrt iteration.

Note

If you only want the result of the last step and are not interested in the intermediate steps, use the more efficient adrt.bdrt().

adrt.core.iadrt_fmg_iter(a, /, *, copy=True)

Iteratively improve estimated inverses by the full multigrid method.

Internally computes a recurrence with iadrt_fmg_step() to iteratively refine an estimated inverse for the ADRT output a.

This iterator has infinite length and will continue computing refinements until stopped. For a simple implementation with a basic stopping condition consider adrt.iadrt_fmg().

For another inverse which may perform more reliably for certain inputs consider the iadrt_cg recipe proposed in the Iterative Inverse example.

Parameters:

• a (numpy.ndarray of float) – The array for which inverse estimates will be computed. This array must have the shape of an ADRT output.

• copy (bool, optional) – If True (default), the arrays produced by this generator are independent copies. Otherwise, read-only views are produced and these must not be modified without making a copy first.

Yields:

numpy.ndarray of float – Estimated inverses for a refined by repeated applications of iadrt_fmg_step().

Warning

This is an infinite iterator; a simple for loop over its values will run forever. To limit the computation either implement some desired stopping condition, or consider itertools.islice() to cap the number of elements produced.

Single-Step Routines

These routines allow selecting a particular iteration to run on an input. Internally, the iterative routines select the number of iterations required based on the size of an input using the num_iters() function. Values in this range are then valid as loop counter values to be passed to the step arguments of these functions.

The outputs of these routines allow modifying the progress of the algorithm, either by editing the results of the steps (for example, to mask certain values) or by running the steps multiple times or in a different order.

adrt.core.num_iters(n, /)

Number of adrt iterations needed for an image of size n.

Many of the algorithms in this package are iterative. For an image of size \(n \times n\) (powers of two), the core loop must be run \(\log_2(n)\) times. This function computes the number of iterations necessary and is equivalent to \(\lceil{\log_2(n)}\rceil\), with the special case num_iters(0) == 0.

Parameters:

n (int) – The integer size of the image array which is to be processed.

Returns:

The number of iterations needed to fully process the image of size n.

Return type:

int

adrt.core.adrt_init(a, /)

Initialize an array for use with adrt_step().

This function processes square arrays with side lengths a power of two. These arrays may also optionally have a batch dimension. This function is intended to be used with adrt.core.adrt_step().

After processing, the resulting array has the shape of an ADRT output, but only the top square of each quadrant is filled in. Other values are zero.

The function adrt.utils.truncate() provides an inverse for this operation.

Parameters:

a (numpy.ndarray) – The array which will be made suitable for further processing with the ADRT. This array must have a square shape with sides a power of two, optionally with a leading batch dimension.

Returns:

The input array duplicated, stacked, flipped, and rotated to make it suitable for further processing with the ADRT. The output array has the shape of an ADRT output.

Return type:

numpy.ndarray

adrt.core.adrt_step(a, /, step)

Compute a single step of the ADRT.

The ADRT implemented in adrt.adrt() is internally an iterative algorithm. Sums along line segments of a given length are approximated by joining sums along line segments of half length in a bottom-up fashion from segments of length two.

This function allows you to run a single step of the ADRT in order to observe the outputs (for example to read off sums of partial line segments) or to modify the values as the computation proceeds (for example, to mask certain values as they grow).

To use this function correctly, use adrt.core.adrt_init() to initialize your input array. The argument a to this function should either be the result of adrt_init() or a previous output of this function.

Parameters:

• a (numpy.ndarray of float) – The array for which the single ADRT step should be computed.

• step (int) – The step to compute. The upper bound on this value should be computed using num_iters(), then step must be between \(0\) and \(\mathtt{num\_iters}-1\), inclusive.

Returns:

The result of the step iteration of the ADRT. The output has the same shape as the input.

Return type:

numpy.ndarray of float

Note

If you only want the result of the last step (the full ADRT) and are not interested in the intermediate steps, use the more efficient adrt.adrt().

adrt.core.bdrt_step(a, /, step)

Compute a single step of the bdrt.

The implementation of adrt.bdrt() is internally an iterative algorithm. This function allows you to run a single step of the bdrt in order to observe the outputs or to modify the values as the computation proceeds.

To use this function correctly, the input a should be the result of an ADRT operation (adrt.adrt()) or a previous output of this function.

Parameters:

• a (numpy.ndarray of float) – The array for which the single bdrt step should be computed. This array must have data type float32 or float64.

• step (int) – The step to compute. The upper bound on this value should be computed using num_iters(), then step must be between \(0\) and \(\mathtt{num\_iters}-1\), inclusive.

Returns:

The result of the step iteration of the bdrt. The output has the same shape as the input.

Return type:

numpy.ndarray of float

Note

If you only want the result of the last step and are not interested in the intermediate steps, use the more efficient adrt.bdrt().

adrt.core.iadrt_fmg_step(a, /)

Compute an estimated inverse by the full multigrid method.

This is an implementation of the “FMG” inverse described by Press [1]. A call to this function on an output of the ADRT produces an estimated inverse which can be iteratively refined by adding corrections for remaining errors.

For easy access to iteratively-improved inverses produced by this method, consider iadrt_fmg_iter() which internally performs the required recurrence.

For another inverse which may perform more reliably for certain inputs consider the iadrt_cg recipe proposed in the Iterative Inverse example.

Parameters:

a (numpy.ndarray of float) – The array for which an estimated inverse is computed. This array must have the shape of an ADRT output.

Returns:

An estimated inverse computed by the full multigrid method for the input a.

Return type:

numpy.ndarray of float

References

[1]

W. Press, “Discrete Radon transform has an exact, fast inverse and generalizes to operations other than sums along lines,” Proceedings of the National Academy of Sciences, 2006. doi:10.1073/pnas.0609228103

Examples

For an input array after_adrt

>>> rng = np.random.default_rng(seed=0)
>>> orig = rng.normal(size=(16, 16))
>>> after_adrt = adrt.adrt(orig)

we can compute an estimated inverse

>>> est_inv = adrt.core.iadrt_fmg_step(after_adrt)

and iteratively refine it by repeating the below

>>> err = after_adrt - adrt.adrt(est_inv)
>>> est_inv += adrt.core.iadrt_fmg_step(err)

Multithreading Status

Most of the core routines in this package can be built with support for OpenMP. The function threading_enabled() queries whether this support is enabled.

adrt.core.threading_enabled()

Indicate whether core routines provide multithreading.

Many of the core routines in this package can optionally be built with internal multithreading support using OpenMP. If this is enabled these functions will internally split their work across multiple threads.

Returns:

True if this module is built with internal threading support, otherwise False.

Return type:

bool