|
Abstract:
We introduce a new type of wavelet-like representation, dubbed CAMP (Compression- Alignment-Modified Prediction). The hallmarks of CAMP are:
(1) Universal: the methodology works at all spatial dimensions, and for all dilation (i.e., decimation) processes.
(2) Simple: The algorithm is simple, and requires the user to merely select 2-3 low-pass filters and 0-1 full-pass ones (the simplest variant of the algorithm, thus, requires 2 low filters, and the most sophisticated variant requires 3 low-pass filters and one full-pass). One of these filters is 1D and should be interpolatory. There is no further restriction on the selection of the filters. (But, as must be expected, the performance of the representation hinges on certain properties of those filters.)
(3) Fast: Much like standard wavelet constructions, the decomposition and reconstruction are done by a fast algorithm with linear complexity.
(4) Rigorous: Much like in standard wavelet constructions, the representation is associated with performance grade, which is related to the function space characterizations ordered by the representation.
(5) Extremely local: In sharp contrast with mainstream wavelet representations and/or pyramidal representations, the CAMP representation is extremely local. In fact,
the number of operations R that is required for computing one cycle of decomposition- reconstruction satisfies a
bound R ≤ CNR0/Λ, with R0
the tap (= number of non-zero coefficients) in one
of the low-pass filters, with Λ
the determinant of the dilation process (i.e., Λ = 2n for
dyadic decimation in n dimensions), with N the size
of the dataset, and with C ≈ 3 a small constant that
is independent of the type of decimation used, as
well as of the spatial dimension.
We capture the performance of the new representation in the two standard ways: (i) in the ability to provide Jackson-type estimates for functions of a given smoothness, and (ii) in the (more demanding) ability to characterize completely the smoothness class of the function in terms of the detail coefficients of the representation. The performance analysis is accomplished by recasting the representation in terms of a framelet, and explicitly finding a formula for the dual framelet. That dual framelet is used only for the analysis of performance: the reconstruction algorithm based on it will have a catastrophic complexity.
As an illustration of the extreme locality property, we compare the tensor-product biorthogonal 7/9 to one of our CAMP representations that has similar performance. In 3D, the above-mentioned 7/9 uses a total of 8 filters with an average of 512 taps. Our CAMP uses (implicitly, since the high-pass filters are never constructed) a total of 9 filters, with an average size of 18 taps per filter. In 4D, the 7/9 involves 4096 taps per filter. Our CAMP involves a mere 41 coeffecients per filter.
The specific details of this CAMP representation and its reconstruction algorithm indicates that the principles for effecient encoding of the representation should be quite different from those that are employed in wavelet representations.
This is a joint work with Youngmi Hur, a graduate student at UW-Madison.
[LECTURE SLIDES]
|
