Proceedings Article | 28 January 2009
KEYWORDS: Reconstruction algorithms, Wavelets, Superposition, Image compression, Neural networks, Signal processing, Image processing, Stochastic processes, Image quality, Algorithms
This paper deals with the decomposition of multivariate functions into sums and compositions of monovariate
functions. The global purpose of this work is to find a suitable strategy to express complex multivariate functions
using simpler functions that can be analyzed using well know techniques, instead of developing complex Ndimensional
tools. More precisely, most of signal processing techniques are applied in 1D or 2D and cannot easily
be extended to higher dimensions. We recall that such a decomposition exists in the Kolmogorov's superposition
theorem. According to this theorem, any multivariate function can be decomposed into two types of univariate
functions, that are called inner and external functions. Inner functions are associated to each dimension and
linearly combined to construct a hash-function that associates every point of a multidimensional space to a
value of the real interval [0, 1]. Every inner function is the argument for one external function. The external
functions associate real values in [0, 1] to the image by the multivariate function of the corresponding point of
the multidimensional space.
Sprecher, in Ref. 1, has proved that internal functions can be used to construct space filling curves, i.e. there
exists a curve that sweeps the multidimensional space and uniquely matches corresponding values into [0, 1]. Our
goal is to obtain both a new decomposition algorithm for multivariate functions (at least bi-dimensional) and
adaptive space filling curves. Two strategies can be applied. Either we construct fixed internal functions to obtain
space filling curves, which allows us to construct an external function such that their sums and compositions
exactly correspond to the multivariate function; or the internal function is constructed by the algorithm and is
adapted to the multivariate function, providing different space filling curves for different multivariate functions.
We present two of the most recent constructive algorithms of monovariate functions. The first method is
due to Sprecher (Ref. 2 and Ref. 3). We provide additional explanations to the existing algorithm and present
several decomposition results for gray level images. We point out the main drawback of this method: all the
function parameters are fixed, so the univariate functions cannot be modified; precisely, the inner function
cannot be modified and so the space filling curve. The number of layers depends on the dimension of the
decomposed function. The second algorithm, proposed by Igelnik in Ref. 4, increases the parameters flexibility,
but only approximates the monovariate functions: the number of layers is variable, a neural networks optimizes
the monovariate functions and the weights associated to each layer to ensure convergence to the decomposed
multivariate function.
We have implemented both Sprecher's and Igelnik's algorithms and present the results of the decompositions
of gray level images. There are artifacts in the reconstructed images, which leads us to apply the algorithm on
wavelet decomposition images. We detail the reconstruction quality and the quantity of information contained
in Igelnik's network.
