Abstract
In 1900, Hilbert declared that high order polynomial equations could not be solved by sums and compositions of continuous functions of less than three variables. This statement was proven wrong by the superposition theorem, demonstrated by Arnol’d and Kolmogorov in 1957, which allows for writing all multivariate functions as sums and compositions of univariate functions. Amongst recent computable forms of the theorem, Igelnik and Parikh’s approach, known as the Kolmogorov Spline Network (KSN), offers several alternatives for the univariate functions as well as their construction. A novel approach is presented for the embedding of authentication data (black and white logo, translucent or opaque image) in images. This approach offers similar functionalities than watermarking approaches, but relies on a totally different theory: the mark is not embedded in the 2D image space, but it is rather applied to an equivalent univariate representation of the transformed image. Using the progressive transmission scheme previously proposed (Leni, 2011), the pixels are re-arranged without any neighborhood consideration. Taking advantage of this naturally encrypted representation, it is proposed to embed the watermark in these univariate functions. The watermarked image can be accessed at any intermediate resolution, and fully recovered (by removing the embedded mark) without loss using a secret key. Moreover, the key can be different for every resolution, and both the watermark and the image can be globally restored in case of data losses during the transmission. These contributions lie in proposing a robust embedding of authentication data (represented by a watermark) into an image using the 1D space of univariate functions based on the Kolmogorov superposition theorem. Lastly, using a key, the watermark can be removed to restore the original image.
TopIntroduction
Igelnik and Parikh’s approach, known as Kolmogorov Spline Network (KSN), approximates the univariate functions as well as offers flexibility on several parameters of the algorithm (i.e., univariate function constructions, number of layers, tile size, and etc.).
In the KSN, a multivariate function 
is approximated by
(1)In this formulation, the number of layers
(
) is variable. Similarly to the number of neurones constituting the hidden layer of a feed-forward neural network, increasing 
improves the accuracy and an optimal value corresponding to the decomposed function has to be determined. A function 
is associated for each layer 
along each dimension
. The functions 
are mapping functions from 
to
(similar to hash functions), and are used to evaluate the argument of the outer functions
according to the coordinates 
.
The algorithm for the creation of a KSN is divided into two parts: a construction step, in which the univariate functions are interpolated by cubic splines, and a second stage, in which the spline parameters and the weights of the layers 
are optimized to ensure the convergence of the approximation to the function
. To construct the functions 
and
, a tilage over the space 
is generated. By definition, the tiles are disjoint; therefore, in order to cover the entire space, several tilage layers are created. The inner and outer univariate functions are associated with each tilage layer, and the superposition of these layers constitutes what is called a network. One network contains several various parameters, such as the spline parameters and the layer weights that are further optimized to improve the reconstruction accuracy. Consequently, using Igelnik and Parikh’s approximation scheme, images can be represented as a superposition of layers, i.e., a superposition of images with a fixed (and low) resolution.