vc2_bit_widths.vc2_filters: VC-2 Filters Implemented as InfiniteArrays

This module provides an implementation of the complete VC-2 wavelet filtering process in terms of InfiniteArrays.

By using SymbolArrays as inputs, algebraic descriptions (using LinExp) of the VC-2 filters may be assembled. From these analyses may be performed to determine, for example, signal ranges and rounding error bounds.

Using VariableArrays as inputs, Python functions may be generated (using pyexp) which efficiently compute individual filter outputs or intermediate values in isolation.

Usage

To create an InfiniteArrays-based description of a VC-2 filter we must first define the filter to be implemented. In particular, we need a set of vc2_data_tables.LiftingFilterParameters describing the wavelets to use. In practice these are easily obtained from vc2_data_tables.LIFTING_FILTERS like so:

>>> from vc2_data_tables import WaveletFilters, LIFTING_FILTERS

>>> wavelet_index = WaveletFilters.haar_with_shift
>>> wavelet_index_ho = WaveletFilters.le_gall_5_3
>>> dwt_depth = 1
>>> dwt_depth_ho = 3

>>> h_filter_params = LIFTING_FILTERS[wavelet_index_ho]
>>> v_filter_params = LIFTING_FILTERS[wavelet_index]

Given this description we can construct a set of symbolic analysis filters using analysis_transform():

>>> from vc2_bit_widths.infinite_arrays import SymbolArray
>>> from vc2_bit_widths.vc2_filters import analysis_transform

>>> input_picture = SymbolArray(2)
>>> output_coeff_arrays, intermediate_analysis_arrays = analysis_transform(
...     h_filter_params,
...     v_filter_params,
...     dwt_depth,
...     dwt_depth_ho,
...     input_picture,
... )

Two dictionaries are returned. The first dictionary, output_coeff_arrays, provides a nested dictionary of the form {level: {orient: array, ...}, ...} containing the InfiniteArrays representing the generated transform coefficients.

The second dictionary, intermediate_analysis_arrays, is of the form {(level, array_name): array, ...} and exposes every intermediate InfiniteArray from the filtering process (see Terminology for a guide to the naming convention used). This dictionary contains a superset of the arrays contained in the first.

Similarly we can use synthesis_transform() to construct an algebraic description of the synthesis filters. This function takes an array for each transform component as input. The make_symbol_coeff_arrays() utility function provides a convenient way to produce the necessary SymbolArrays:

>>> from vc2_bit_widths.vc2_filters import (
...     make_symbol_coeff_arrays,
...     synthesis_transform,
... )

>>> input_coeff_arrays = make_symbol_coeff_arrays(dwt_depth, dwt_depth_ho)
>>> output_picture, intermediate_synthesis_arrays = synthesis_transform(
...     h_filter_params,
...     v_filter_params,
...     dwt_depth,
...     dwt_depth_ho,
...     input_coeff_arrays,
... )

As before, two values are returned. The first, output_picture, is a InfiniteArray representing the final decoded picture. The second, intermediate_synthesis_arrays, again contains all of the intermediate InfiniteArrays (and the output picture).

Warning

The analysis_transform() and synthesis_transform() functions always return almost immediately since InfiniteArrays only compute their values on-demand. For very large transforms, accessing values within these arrays (and triggering their evaluation) can take a non-trivial amount of time and memory.

Omitting arrays

Some of the intermediate arrays returned by analysis_transform() and synthesis_transform() are simple interleavings/subsamplings/renamings of other intermediate arrays. These arrays may be identified using their nop property and skipped to avoid duplicating work when performing filter analysis.

When arrays have been skipped during processing it can still be helpful to show the duplicate entries when results are presented. The add_missing_analysis_values() and add_missing_synthesis_values() functions are provided to perform exactly this task.

For example, lets count up the number of symbols in each filter phase in the example wavelet transforms, skipping duplicate arrays:

>>> def count_symbols(expression):
...     return len(list(expression.symbols()))

>>> analysis_symbol_counts = {
...     (level, array_name, x, y): count_symbols(array[x, y])
...     for (level, array_name), array in intermediate_analysis_arrays.items()
...     for x in range(array.period[0])
...     for y in range(array.period[1])
...     if not array.nop
... }
>>> synthesis_symbol_counts = {
...     (level, array_name, x, y): count_symbols(array[x, y])
...     for (level, array_name), array in intermediate_synthesis_arrays.items()
...     for x in range(array.period[0])
...     for y in range(array.period[1])
...     if not array.nop
... }

We can then fill in all of the missing entries and present the results to the user:

>>> from vc2_bit_widths.vc2_filters import (
...     add_missing_analysis_values,
...     add_missing_synthesis_values,
... )

>>> full_analysis_symbol_counts = add_missing_analysis_values(
...     h_filter_params,
...     v_filter_params,
...     dwt_depth,
...     dwt_depth_ho,
...     analysis_symbol_counts,
... )
>>> full_synthesis_symbol_counts = add_missing_synthesis_values(
...     h_filter_params,
...     v_filter_params,
...     dwt_depth,
...     dwt_depth_ho,
...     synthesis_symbol_counts,
... )

>>> for (level, array_name, x, y), symbol_count in full_analysis_symbol_counts.items():
...     print("{} {} {} {}: {} symbols".format(
...         level, array_name, x, y, symbol_count
...     ))
4 Input 0 0: 1 symbols
4 DC 0 0: 1 symbols
4 DC' 0 0: 1 symbols
4 DC' 1 0: 4 symbols
<...snip...>
1 DC'' 0 0: 340 symbols
1 DC'' 1 0: 245 symbols
1 L 0 0: 340 symbols
1 H 0 0: 245 symbols

>>> for (level, array_name, x, y), symbol_count in full_synthesis_symbol_counts.items():
...     print("{} {} {} {}: {} symbols".format(
...         level, array_name, x, y, symbol_count
...     ))
1 L 0 0: 1 symbols
1 H 0 0: 1 symbols
1 DC'' 0 0: 1 symbols
1 DC'' 1 0: 1 symbols
<...snip...>
4 Output 14 0: 34 symbols
4 Output 14 1: 38 symbols
4 Output 15 0: 42 symbols
4 Output 15 1: 48 symbols

API

Transforms

analysis_transform(h_filter_params, v_filter_params, dwt_depth, dwt_depth_ho, array)

Perform a multi-level VC-2 analysis Discrete Wavelet Transform (DWT) on a InfiniteArray in a manner which is the complement of the ‘idwt’ pseudocode function described in (15.4.1) in the VC-2 standard.

Parameters

h_filter_params, v_filter_paramsvc2_data_tables.LiftingFilterParameters

Horizontal and vertical filter parameters for the corresponding synthesis trhansform (e.g. from vc2_data_tables.LIFTING_FILTERS). These filter parameters will be transformed into analysis lifting stages internally.

dwt_depth, dwt_depth_ho: int

Transform depths for 2D and horizontal-only transforms.

arrayInfiniteArray

The array representing the picture to be analysed.

Returns

coeff_arrays{level: {orientation: InfiniteArray, …}, …}

The output transform coefficient values. These nested dictionaries are indexed the same way as ‘coeff_data’ in the idwt pseudocode function in (15.4.1) in the VC-2 specification.

intermediate_arrays{(level, array_name): InfiniteArray, …}

All intermediate (and output) value arrays, named according to the convention described in Terminology.

This value is returned as an OrderedDict giving the arrays in their order of creation; a sensible order for display purposes.

synthesis_transform(h_filter_params, v_filter_params, dwt_depth, dwt_depth_ho, coeff_arrays)

Perform a multi-level VC-2 synthesis Inverse Discrete Wavelet Transform (IDWT) on a InfiniteArray in a manner equivalent to the ‘idwt’ pseudocode function in (15.4.1) of the VC-2 standard.

Parameters

h_filter_params, v_filter_paramsvc2_data_tables.LiftingFilterParameters

Horizontal and vertical filter synthesis filter parameters (e.g. from vc2_data_tables.LIFTING_FILTERS).

dwt_depth, dwt_depth_ho: int

Transform depths for 2D and horizontal-only transforms.

coeff_arrays{level: {orientation: InfiniteArray, …}, …}

The transform coefficient arrays to be used for synthesis. These nested dictionaries are indexed the same way as ‘coeff_data’ in the idwt pseudocode function in (15.4.1) in the VC-2 specification. See make_symbol_coeff_arrays() and make_variable_coeff_arrays().

Returns

arrayInfiniteArray

The final output array (i.e. decoded picture).

intermediate_arrays{(level, array_name): InfiniteArray, …}

All intermediate (and output) value arrays, named according to the convention described in Terminology.

This value is returned as an OrderedDict giving the arrays in their order of creation; a sensible order for display purposes.

Coefficient array creation utilities

make_symbol_coeff_arrays(dwt_depth, dwt_depth_ho, prefix='coeff')

Create a set of SymbolArrays representing transform coefficient values, as expected by synthesis_transform().

Returns

coeff_arrays{level: {orientation: SymbolArray, …}, …}

The transform coefficient values. These dictionaries are indexed the same way as ‘coeff_data’ in the idwt pseudocode function in (15.4.1) in the VC-2 specification.

The symbols will have the naming convention ((prefix, level, orient), x, y) where:

• prefix is given by the ‘prefix’ argument

• level is an integer giving the level number

• orient is the transform orientation (one of “L”, “H”, “LL”, “LH”, “HL” or “HH”).

• x and y are the coordinate of the coefficient within that subband.

make_variable_coeff_arrays(dwt_depth, dwt_depth_ho, exp=Argument('coeffs'))

Create a set of SymbolArrays representing transform coefficient values, as expected by synthesis_transform().

Returns

coeff_arrays{level: {orientation: VariableArray, …}, …}

The transform coefficient values. These dictionaries are indexed the same way as ‘coeff_data’ in the idwt pseudocode function in (15.4.1) in the VC-2 specification.

The expressions within the VariableArrays will be indexed as follows:

>>> from vc2_bit_widths.pyexp import Argument

>>> coeffs_arg = Argument("coeffs_arg")
>>> coeff_arrays = make_variable_coeff_arrays(3, 0, coeffs_arg)
>>> coeff_arrays[2]["LH"][3, 4] == coeffs_arg[2]["LH"][3, 4]
True

Omitted value insertion

add_missing_analysis_values(h_filter_params, v_filter_params, dwt_depth, dwt_depth_ho, analysis_values)

Fill in results for omitted (duplicate) filter arrays and phases.

Parameters

h_filter_params, v_filter_paramsvc2_data_tables.LiftingFilterParameters

dwt_depth, dwt_depth_ho: int

The filter parameters.

analysis_values{(level, array_name, x, y): value, …}

A dictionary of values associated with individual intermediate analysis filter phases with entries omitted where arrays are just interleavings/subsamplings/renamings.

Returns

full_analysis_values{(level, array_name, x, y): value, …}

A new dictionary of values with missing filters and phases filled in.

add_missing_synthesis_values(h_filter_params, v_filter_params, dwt_depth, dwt_depth_ho, synthesis_values, fill_in_equivalent_phases=True)

Fill in results for omitted (duplicate) filter arrays and phases.

Parameters

h_filter_params, v_filter_paramsvc2_data_tables.LiftingFilterParameters

dwt_depth, dwt_depth_ho: int

The filter parameters.

synthesis_values{(level, array_name, x, y): value, …}

A dictionary of values associated with individual intermediate synthesis filter phases with entries omitted where arrays are just interleavings/subsamplings/renamings.

fill_in_equivalent_phasesbool

When two InfiniteArrays with different periods are interleaved, the interleaved signal’s period will include repetitions of some phases of one of the input arrays. For example, consider the following arrays:

 a = ... a0 a1 a0 a1 ...    (Period = 2)
 b = ... b0 b0 b0 b0 ...    (Period = 1)

ab = ... a0 b0 a1 b0 ...    (Period = 4)

In this example, the interleaved array has a period of 4 with two phases coming from a and two from b. Since b has a period of one, however, one of the phases of ab contains a repeat of one of the phases of ‘b’.

Since in a de-duplicated set of filters and phases, duplicate phases appearing in interleaved arrays are not present, some other value must be used when filling in these phases. If the ‘fill_in_equivalent_phases’ argument is True (the default), the value from an equivalent phase will be copied in. If False, None will be used instead.

Where the dictionary being filled in contains results generic to the phase being used (and not the specific filter coordinates), the default value of ‘True’ will give the desired results.

Returns

full_synthesis_values{(level, array_name, x, y): value, …}

A new dictionary of values with missing filters and phases filled in.