vc2_bit_widths.infinite_arrays: Infinite arrays

InfiniteArray and its subclasses provide a way to define and analyse VC-2 filters.

Tutorial

In the worked example below we’ll see how a simple LeGall (5, 3) synthesis filter can be described using InfiniteArrays. We’ll use this description to enumerate all of the resulting filter phases and generate algebraic expressions for them.

Building a VC-2 filter

A horizontal-only LeGall (5, 3) synthesis transform takes as input two arrays of transform coefficients (a low-pass band, L, and high-pass band, H) and produces a single output array. Lets start by defining the two input arrays:

>>> from vc2_bit_widths.infinite_arrays import SymbolArray

>>> L = SymbolArray(2, "L")
>>> H = SymbolArray(2, "H")

The SymbolArray class defines an infinite array of LinExps containing a single symbol of the form LinExp((prefix, x, y)). Like all InfiniteArray subclasses, we can access entries in our arrays using the usual Python subscript syntax:

>>> L[3, 4]
LinExp(('L', 3, 4))
>>> H[7, -5]
LinExp(('H', 7, -5))

Notice that the coordinate system extends to positive and negative infinity.

Next we’ll create an InterleavedArray which contains a horizontal interleaving of the two inputs:

>>> from vc2_bit_widths.infinite_arrays import InterleavedArray

>>> interleaved = InterleavedArray(L, H, 0)

The new interleaved array can be accessed just as before:

>>> interleaved[0, 0]
LinExp(('L', 0, 0))
>>> interleaved[1, 0]
LinExp(('H', 0, 0))
>>> interleaved[2, 1]
LinExp(('L', 1, 1))
>>> interleaved[3, 1]
LinExp(('H', 1, 1))

Next we’ll apply the two lifting stages which implement the LeGall (5, 3) transform using a LiftedArray:

>>> from vc2_bit_widths.infinite_arrays import LiftedArray

>>> from vc2_data_tables import LIFTING_FILTERS, WaveletFilters
>>> wavelet = LIFTING_FILTERS[WaveletFilters.le_gall_5_3]
>>> stage_0, stage_1 = wavelet.stages

>>> lifted_once = LiftedArray(interleaved, stage_0, 0)
>>> lifted_twice = LiftedArray(lifted_once, stage_1, 0)

Finally we’ll use a RightShiftedArray to apply the final bit shift operation to the result:

>>> from vc2_bit_widths.infinite_arrays import RightShiftedArray

>>> output = RightShiftedArray(lifted_twice, wavelet.filter_bit_shift)

This final array now, in effect, contains a complete algebraic description of how each entry is computed in terms of our two input arrays, L and H:

>>> output[0, 0]
LinExp({('L', 0, 0): Fraction(1, 2), ('H', -1, 0): Fraction(-1, 8), ('H', 0, 0): Fraction(-1, 8), AAError(id=1): Fraction(-1, 4), AAError(id=2): Fraction(1, 2)})

Notice that the expression above refers to transform coefficients with negative coordinates (e.g. ('H', -1, 0)). This is because the infinite dimensions of InfiniteArrays allows LiftedArray to ignore VC-2’s filter edge effect behaviour. This makes it easier to analyse filter behaviours without having to carefully avoid edge effected behaviour.

Filter phases

The InfiniteArray subclasses automatically keep track of the period of each array (see Terminology) in the InfiniteArray.period property:

>>> L.period
(1, 1)
>>> H.period
(1, 1)

>>> output.period
(2, 1)

This makes it easy to automatically obtain an example of each filter phase in our output:

>>> all_output_filter_phases = [
...     output[x, y]
...     for x in range(output.period[0])
...     for y in range(output.period[1])
... ]

Detecting no-operations

When performing a computationally expensive analysis on a set of filters described by InfiniteArrays it can be helpful to skip arrays which just consist of interleavings and other non-transformative views of other arrays. For this purpose, the InfiniteArray.nop property indicates if a given array implements a no-operation (nop) and therefore may be skipped.

From the example above:

>>> L.nop
False
>>> H.nop
False

>>> interleaved.nop
True

>>> lifted_once.nop
False
>>> lifted_twice.nop
False

>>> output.nop
False

Here we can see that the interleaving stage is identified as having no material effect on the values it contains.

Relative array stepping

InfiniteArrays provide a InfiniteArray.relative_step_size_to() method for calculating the scaling relationships between arrays. This can be useful for finding array values which don’t use inputs with negative coordinates (i.e. would not be affected by edge-effect behaviour in a real VC-2 filter).

For example, consider the top-left pixel of the filter output from before:

>>> output[0, 0]
LinExp({('L', 0, 0): Fraction(1, 2), ('H', -1, 0): Fraction(-1, 8), ('H', 0, 0): Fraction(-1, 8), AAError(id=1): Fraction(-1, 4), AAError(id=2): Fraction(1, 2)})

This uses the input ('H', -1, 0) which has negative coordinates. Thanks to the period property we know that any array value with an even-numbered X coordinate implements the same filter phase as [0, 0].

We could start trying every even-numbered X coordinate until we find an entry without a negative H coordinate, but this would be fairly inefficient. Instead lets use relative_step_size_to() to work out how many steps we must move in output to move all our H coordinates right by one step.

>>> output.relative_step_size_to(H)
(Fraction(1, 2), Fraction(1, 1))

This tells us that for every step we move in the X-dimension of output, we move half a step in that direction in H. Therefore, we must pick a coordinate at least two steps to the right in output to avoid the -1 coordinate in H. Moving to [2, 0] also gives an even numbered X coordinate so we know that we’re going to see the same filter phase and so we get:

>>> output[2, 0]
LinExp({('L', 1, 0): Fraction(1, 2), ('H', 0, 0): Fraction(-1, 8), ('H', 1, 0): Fraction(-1, 8), AAError(id=3): Fraction(-1, 4), AAError(id=6): Fraction(1, 2)})

Which implements the same filter phase as output[0, 0] but without any negative coordinates.

Caching

All of the subclasses of InfiniteArray which perform a non-trivial operation internally cache array values when they’re accessed.

The most obvious benefit of this behaviour is to impart a substantial performance improvement for larger filter designs.

A secondary benefit applies to InfiniteArrays containing LinExps. By caching the results of operations which introduce affine arithmetic error symbols (AAError), these errors can correctly combine or cancel when that result is reused. As a result, while caching is not essential for correctness, it can materially improve the tightness of the bounds produced.

In some instances, this basic caching behaviour may not go far enough. For example, the contents of output[0, 0] and output[2, 0] are extremely similar, consisting of essentially the same coefficients, just translated to the right:

>>> output[0, 0]
LinExp({('L', 0, 0): Fraction(1, 2), ('H', -1, 0): Fraction(-1, 8), ('H', 0, 0): Fraction(-1, 8), AAError(id=1): Fraction(-1, 4), AAError(id=2): Fraction(1, 2)})
>>> output[2, 0]
LinExp({('L', 1, 0): Fraction(1, 2), ('H', 0, 0): Fraction(-1, 8), ('H', 1, 0): Fraction(-1, 8), AAError(id=3): Fraction(-1, 4), AAError(id=6): Fraction(1, 2)})

In principle, the cached result of output[0, 0] could be re-used (and the coefficients suitably translated) to save the computational cost of evaluating output[2, 0] from scratch. For extremely large transforms, this optimisation can result in substantial savings in runtime and RAM. For use in such scenarios the SymbolicPeriodicCachingArray array type is provided:

>>> from vc2_bit_widths.infinite_arrays import SymbolicPeriodicCachingArray

>>> output_cached = SymbolicPeriodicCachingArray(output, L, H)

The constructor takes the array to be cached along with all SymbolArrays used its definition. The new array may be accessed as usual but with more aggressive caching taking place internally:

>>> output_cached[0, 0]
LinExp({('L', 0, 0): Fraction(1, 2), ('H', -1, 0): Fraction(-1, 8), ('H', 0, 0): Fraction(-1, 8), AAError(id=1): Fraction(-1, 4), AAError(id=2): Fraction(1, 2)})
>>> output_cached[2, 0]
LinExp({('L', 1, 0): Fraction(1, 2), ('H', 0, 0): Fraction(-1, 8), ('H', 1, 0): Fraction(-1, 8), AAError(id=1): Fraction(-1, 4), AAError(id=2): Fraction(1, 2)})

Warning

Note that in the cached version of the array, the AAError terms are not unique between output_cached[0, 0] and output_cached[2, 0], though they should be. This is a result of the caching mechanism having no way to know how error terms should change between entries in the array. As a result, SymbolicPeriodicCachingArray must not be used when the affine error terms in its output are expected to be significant.

Note

SymbolicPeriodicCachingArray only works with InfiniteArrays defined in terms of SymbolArrays.

API

InfiniteArray (base class)

class InfiniteArray(ndim, cache)

An abstract base class describing an immutable infinite N-dimensional array of symbolic values.

Subclasses should implement get() to return the value at a given position in an array.

Instances of this type may be indexed like an N-dimensional array.

The ‘cache’ argument controls whether array values are cached or not. It is recommended that this argument be set to ‘True’ for expensive to compute functions or functions which introduce new error terms (to ensure error terms are re-used)

get(keys)

Called by __getitem__() with a tuple of array indices.

The array of keys is guaranteed to be a tuple with ndim entries.

Values returned by this method will be memoized (cached) by __getitem__(). Consequently, this method will only be called the first time a particular array index is requested. Subsequent accesses will return the cached value.

clear_cache()

Clear the cache (if enabled).

property ndim

The number of dimensions in the array.

property period

Return the period of this array (see Terminology).

Returns

period(int, …)

The period of the array in each dimension.

property nop

True if this InfiniteArray is a no-operation (nop), i.e. it just views values in other arrays. False if some computation is performed.

relative_step_size_to(other)

For a step along a dimension in this array, compute the equivalent step size in the provided array.

Parameters

otherInfiniteArray

An array to compare the step size with. Must have been used (maybe indirectly) to define this array.

Returns

relative_step_size(fractions.Fraction, …) or None

The relative step sizes for each dimension, or None if the provided array was not used in the computation of this array.

Base value type arrays

class SymbolArray(ndim, prefix='v')

An infinite array of LinExp symbols.

Symbols will be identified by tuples like (prefix, n) for a one dimensional array, (prefix, n, n) for a two-dimensional array, (prefix, n, n, n) for a three-dimensional array and so-on.

Example usage:

>>> a = SymbolArray(3, "foo")
>>> a[1, 2, 3]
LinExp(('foo', 1, 2, 3))
>>> a[100, -5, 0]
LinExp(('foo', 100, -5, 0))

Parameters

ndimint

The number of dimensions in the array.

prefixobject

A prefix to be used as the first element of every symbol tuple.

class VariableArray(ndim, exp)

An infinite array of subscripted PyExp expressions.

Example usage:

>>> from vc2_bit_widths.pyexp import Argument

>>> arg = Argument("arg")
>>> a = VariableArray(2, arg)
>>> a[1, 2]
Subscript(Argument('arg'), Constant((1, 2)))
>>> a[-10, 3]
Subscript(Argument('arg'), Constant((-10, 3)))

Parameters

ndimint

The number of dimensions in the array.

expPyExp

The expression to be subscripted in each array element.

Computation arrays

class LiftedArray(input_array, stage, filter_dimension)

Apply a one-dimensional lifting filter step to an array, as described in the VC-2 specification (15.4.4).

Parameters

input_arrayInfiniteArray

The input array whose entries will be filtered by the specified lifting stage.

stagevc2_data_tables.LiftingStage

A description of the lifting stage.

interleave_dimension: int

The dimension along which the filter will act.

class LeftShiftedArray(input_array, shift_bits=1)

Apply a left bit shift to every value in an input array.

Parameters

input_arrayInfiniteArray

The array to have its values left-shifted.

shift_bits: int

Number of bits to shift by.

class RightShiftedArray(input_array, shift_bits=1)

Apply a right bit shift to every value in an input array.

The right-shift operation is based on the description in the VC-2 specification (15.4.3). Specifically, \(2^{\text{shiftbits}-1}\) is added to the input values prior to the right-shift operation (which is used to implement rounding behaviour in integer arithmetic).

Parameters

input_arrayInfiniteArray

The array to have its values right-sifted

shift_bits: int

Number of bits to shift by

Sampling arrays

class SubsampledArray(input_array, steps, offsets)

A subsampled view of another InfiniteArray.

Parameters

input_arrayInfiniteArray

The array to be subsampled.

steps, offsets: (int, …)

Tuples giving the step size and start offset for each dimension.

When this array is indexed, the index into the input array is computed as:

input_array_index[n] = (index[n] * step[n]) + offset[n]

class InterleavedArray(array_even, array_odd, interleave_dimension)

An array view which interleaves two InfiniteArrays together into a single array.

Parameters

array_even, array_oddInfiniteArray

The two arrays to be interleaved. ‘array_even’ will be used for even-indexed values in the specified dimension and ‘array_odd’ for odd.

interleave_dimension: int

The dimension along which the two arrays will be interleaved.

Caching arrays

class SymbolicPeriodicCachingArray(array, *symbol_arrays)

A caching view of a InfiniteArray of LinExp values.

This view will request at most one value from each filter phase of the input array and compute all other values by altering the indices in the previously computed values.

For example, normally, when accessing values within a InfiniteArray, values are computed from scratch on-demand:

>>> s = SymbolArray(2, "s")
>>> stage = <some filter stage>
>>> la = LiftedArray(s, stage, 0)
>>> la[0, 0]  # la[0, 0] worked out from scratch
LinExp(...)
>>> la[0, 1]  # la[0, 1] worked out from scratch
LinExp(...)
>>> la[0, 2]  # la[0, 2] worked out from scratch
LinExp(...)
>>> la[0, 3]  # la[0, 3] worked out from scratch
LinExp(...)

By contrast, when values are accessed in a SymbolicPeriodicCachingArray, only the first access to each filter phase is computed from scratch. All other values are found by changing the symbol indices in the cached array value:

>>> cached_la = SymbolicPeriodicCachingArray(la, s)
>>> cached_la[0, 0]  # la[0, 0] worked out from scratch
LinExp(...)
>>> cached_la[0, 1]  # la[0, 1] worked out from scratch
LinExp(...)
>>> cached_la[0, 2]  # Cached value of la[0, 0] reused and mutated
LinExp(...)
>>> cached_la[0, 3]  # Cached value of la[0, 1] reused and mutated
LinExp(...)

Parameters

arrayInfiniteArray

The array whose values are to be cached. These array values must consist only of symbols from SymbolArrays passed as arguments, AAError terms and constants.

Warning

Error terms may be repeated as returned from this array where they would usually be unique. If this is a problem, you should not use this caching view.

For example:

>>> s = SymbolArray(2, "s")
>>> sa = RightShiftedArray(s, 1)

>>> # Unique AAError terms (without caching)
>>> sa[0, 0]
LinExp({('s', 0, 0): Fraction(1, 2), AAError(id=1): Fraction(1, 2)})
>>> sa[0, 1]
LinExp({('s', 0, 1): Fraction(1, 2), AAError(id=2): Fraction(1, 2)})

>>> # Non-unique AAError terms after caching
>>> ca = SymbolicPeriodicCachingArray(sa, s)
>>> ca[0, 0]
LinExp({('s', 0, 0): Fraction(1, 2), AAError(id=1): Fraction(1, 2)})
>>> ca[0, 1]
LinExp({('s', 0, 1): Fraction(1, 2), AAError(id=1): Fraction(1, 2)})

symbol_arraysSymbolArray

The symbol arrays which the ‘array’ argument is constructed from.