10. Encoding of stationary images through latice method with polynomial estimation
In the present article an adaptive method of estimation of image unknown elements for the problem of image encoding is proposed. Polynomial method of estimation with adaptive selection of filter parameters through pseudogradient method is considered. Comparative analysis of the proposed method of encoding with algorithms JPEG and JPEG2000 is given.
Analysis of image encoding methods
At present time a great number of image encoding algorithms has been developed [1,2,3,4] and among them compression algorithms with some loss of compressed image quality are of most interest. In this case normalized root-mean-square deviation(NRMSD) is usually chosen in the capacity of agreement estimate between initial and restored images.
As a rule, the methods with losses utilize one or another transformation of initial signal with the purpose of statistical redundancy reduction. Thus, the wide-spread JPEG algorithm expands image signal into cosine harmonics of the Fourier series . The above-mentioned transformation is analyzed in a great number of works [1,3] in which the drawbacks of such an approach are shown. Appearance of false contours in a restored image at high speed of encoding and independent encoding of 8x8 pixel blocks can be referred to the main drawbacks and this leads to compression coefficient reduction. Besides, Fourier transform coefficients are the averaged characteristic of signal in time and do not represent its non-stationary properties.
The wavelet transform is free of these drawbacks  and it found its application in a new standard of image compression – JPEG2000. The basics of the method is in expanding of a signal into basis functions localized both in space and in time. This enables to take into account non-stationarity of the signal in the coefficients of the wavelet transform. Besides, scaling ability of the basis functions enables to analyze image signal with various degree of detail and this finds its application in multiple-scale analysis(MSA) [1,5]. Lattice approach to image encoding
Sometimes it is convenient to carry out analysis of image in time domain through lattice methods . In this case it is proposed to carry out image estimation from incomplete observables which, for instance, are distant from each other at one sample vertically and horizontally and forming low-frequency component. Estimation errors are found as differences between initial image and the result of estimation from incomplete data. At such an approach there is a possibility to choose any interpolating filters, including inseparable ones, for estimation error variance minimization.
The procedure of estimation of unknown elements can be recurrently repeated for low-frequency components, which leads to image energy localization in a small number of estimation (errors) coefficients.
Due to such an approach patterns of repeating bytes, which can be effectively encoded through lossless compression methods, will be formed. Pseudogradient estimation of interpolating filter parameters
In general case interpolating filter can be represented in the form of polynomial estimate from the nearest to the estimated element observables:
The parameters in (1) have to be chosen in such a way that .
One of the methods of determination of the parameters , minimizing the functional is the procedure of recurrent gradient estimation  having the following form:
where - approximation to the minimum point of due after ; - gradient of the functional ; ‑ positive numerical sequence having an effect on step length of the procedure (2); - initial approximation.
The implementation of the considered method is complicated in terms of computing expenses because at every step it is necessary to recalculate. Significantly less calculations are required for pseudogradient (PG) algorithms . A certain random direction is defined which satisfies the condition of pseudogradientness:
where «» – the sign of scalar product of the vectors, i.e. makes on average a sharp angle with the true gradient .
In cases when the functional gradient is expressed through mathematical expectation of a certain random value it is possible to take the realizations of this value as the pseudogradient. In this case the pseudogradient for the functional is written in the form:.
The procedure of estimation takes the form:
(4) Comparative analysis of the proposed method efficiency
In the analyzed encoding algorithm four-level decomposition of image was applied. The estimation of image elements from incomplete observables , where - decomposition step, .
The developed transformation was compared with Haar wavelet transform and algorithms of JPEG and JPEG2000.
Images of 128x128 samples each and with 256 shades of grey were used as input data (fig. 1). The results of encoding are presented in Table 1.
Table 1. The results of encoding of test image encoding
The analysis of test image encoding results shows the gain of the proposed method for both test images. At that computational complexity of the proposed algorithm is at a small disadvantage with the algorithms of JPEG and JPEG2000. The further development of work is directed to determination of the found parameters from quantized errors of encoding which enables to essentially increase the compression coefficient.
1. Теория и практика вейвлет-преобразования. Воробьев В.И., Грибунин В.Г., ВУС, 1999. С. 1-204.
2. Сармин А. Метод Хаффмана и родственные методы http://www.arctest.narod.ru\ descript\huffmans.htm.
3. Зелов С. Стандарт JPEG-кодирование неподвижных изображений Компьютер Пресс №5, 1997 с. 82-84.
4. Д.С. Ватолин. Алгоритмы сжатия изображений www.useic.ru\~dv\ fractal\index.htm.
5. Добеши И. Десять лекций по вейвлетам. – Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001, 464 стр.
6. Уидроу Б., Стирнз С. Адаптивная обработка сигналов: Пер. с англ. – М.: Радио и связь, 1989. – 440 с.: ил.
7. Прикладная теория случайных процессов и полей / Васильев К.К., П 75 Драган Я.П., Казаков В.А. и др.; Под ред. Васильева К.К., Омельченко В.А. Ульяновск: УлГТУ, 1995. 256 с.