Messy data structure of SIWPD

[zengfung]

Some functions on the Shift-Invariant Wavelet Packet Decomposition (SIWPD) have been implemented, but the tree structure and the best basis algorithm are quite different from the usual implementations in the standard, stationary, and the autocorrelation wavelet transforms. The latter transforms all involve binary trees (for 1D signals) and quadtrees (for 2D signals).

For SIWPD however, each level of decomposition also comes with a corresponding shifted decomposition, ie. in the case of 1D signals, each node will decompose into 2 nodes for approximate and detail coefficients of the original node, plus 2 more nodes for the approximate and detail coefficients of the right circularly shifted version (via circshift) of the node.

The current implementation is quite messy. Here's an example of the difference in tree structures between the SIWPD and the other transforms:

# 1D tree for dwt, swt, and acwt transforms for signals of length 4
3-element BitVector:
 1
 1
 1

# full tree for siwpd for the same signal
7-element Vector{BitVector}:
 [1]
 [1, 1]
 [1, 1]
 [1, 1, 1, 1]
 [1, 1, 1, 1]
 [1, 1, 1, 1]
 [1, 1, 1, 1]

Hence, the issues that need to be resolved are:

• What data structure is best for representing the full tree for SIWPD?
• Can we find a data structure for SIWPD trees that is similar to the BitVectors used for the standard, stationary, and autocorrelation wavelet transforms' binary and quadtrees?
• Plot(s) to visualize the best basis of SIWPD of a signal.

[zengfung]

Current plan is to create a new data structure for this purpose.

ShifftInvariantWaveletTransformObject struct contains:

• Dictionary of index to nodes
• Original signal length
• Max transform level
• Wavelet used
• Minimum cost
• Nodes indices for minimum cost aka best tree [eg: [(0,0,0), (1,0,0), (1,1,0),...]]

ShiftInvariantWaveletTransformNode struct contains

• Array of values
• [Bool] Current node is shifted transform
• Depth of current node
• Index of current node relative to depth [eg: (2,4) => 4]
• Cost of current node

Will probably be memory intensive, but this method seems to be focused more heavily on analysis side anyway, so I'll prioritize functionality and analysis capability over performance and memory consumption for now.

[zengfung]

https://github.com/UCD4IDS/WaveletsExt.jl/pull/51#issuecomment-1146748678

SIWPD and best basis search with new data structure runs smoothly now. Signal reconstruction and documentation fixes are in progress.

[zengfung]

https://github.com/UCD4IDS/WaveletsExt.jl/pull/51#issuecomment-1148265638

Signal reconstruction and documentation fixes complete.

[zengfung]

Decomposition process for SIWT is quite slow, will look out for further improvements.