Butok Alexander Petrovich

Introduction

    Last decade in the world has arisen and the new scientific direction connected with so-called wavelet - the Word "wavelet", being French transfer "ondelette" was issued, means the small waves following one after another. It is possible to tell without exaggeration, that wavelets have made revolution in the field of the theory and practice of processing of non-stationary signals. Now wavelets are widely applied to pattern recognition; at processing and synthesis of various signals, for example speech, medical; for studying of properties of turbulent fields and in many other things cases. Especially big development was received by application practice wavelets for the decision of problems of compression and processing of the images which are non-stationary by the nature. In this area application wavelet - has allowed to reach simultaneous decrease in complexity and increase of efficiency of coders. Now already there are in working out international standards on compression of motionless images and video - JPEG2000 and MPEG-4. A kernel of these standards will be wavelet. Now researches in area wavelets are conducted in many directions. In spite of the fact that the theory wavelet - already basically is developed, exact definition, that such wavlet, it is possible to name what functions wavelet, it is how much known, does not exist. Usually under wavelet functions, shifts and which stretchings form basis of many important spaces are understood. These functions are compact both in time, and in frequency area.

Urgency

Widespread applications of multimedia (the schedule, audio, video) make every day more and more high demands to hardware base of the computer. Neither escalating of clock frequency of the processor, nor increase in volume of a hard disk, improvement of throughput of data links not in a status to save situation. The only thing by the decision of this problem is working out of effective algorithms of a compression of multimedia data.

The purpose and work problems

The purpose: Working out of the codec for compression of multimedia data.
For object in view achievement in work such problems as are solved: working out of algorithm and a writing of the program which will carry out a compression of multimedia data with use demanded wavelet the filter;

Scientific novelty and practical value

The given work is not absolutely new in the subject domain. Aim working out of the codec for compression multimedia data the help wavelet transformations has arisen for a long time and there is a considerable quantity of researches and workings out of other experts in this area. However in the given work the idea of the integrated analysis of the whole complex of the signs counted in a course wavelet of analysis wavelet transformis offered.

Algorithms of compression - Wavelet

The most important theoretical results in a digital compression have been received still in the late seventies. In particular, it has been established, that any image comprises a surplus information which is not perceived by a human eye. This redundancy is caused by strong correlation communications between image elements - from pixel to pixel within some site of a shot it is possible to consider changes insignificant. So, before algorithm of a compression there is a problem of detection and a surplus information filtration. How it to solve? The most widespread till today's time methods the compression applied in standards JPEG and MPEG, are based on signal Fure-transformation - it is represented in the form of a set of harmonious fluctuations with various frequencies and amplitudes. It is important to note, as JPEG, and MPEG before processing the image, divide it into blocks. Very often it leads to quality decrease - the image turns out strongly digitize,the block structure is accurately visible. In the late eighties - the beginning of 90th years the new standard named a Wavelet-compression (in the Russian-speaking literature the term wavelet is used) has been developed. In a literal translation from English the word "wavelet" is meant by "a small wave". The name it speaks the form of schedules of the functions used in the vejvlet-analysis. Ideologically concepts "vejvlet-analysis" and "Fure-analysis" are equivalent. Both in that, and in other case the real signal is replaced with a set of functions (as a rule, in transformation Fourier it is used the system of sine and cosines.

Gif-animation (20 shots x 0,1 sec

The requirements shown to transformations

Let's consider properties which are important at coding of images.

• Scale and orientation. For effective representation of the image the important role is played by scale. In images there are objects of the most various sizes. Therefore, transformation should allow to analyze the image simultaneously (and it is independent) on various scales. For a two-dimensional signal some spectral area corresponds to certain scale and orientation. Orientation of basic functions defines ability of transformation correctly to analyze the focused structures typical for images. As an example contours and lines can serve. Thus, for the decision of a problem of the analysis it is desirable to have transformation which would divide an entrance signal into local frequency areas.
• Spatial localisation. Except frequency localisation, basic functions should be local and in space. Necessity for spatial localisation. Transformations arises when the information on a site of details of the image is the major. This locality, however, should not be "absolute", block, as at DWT as it conducts to loss of property of locality in frequency area. Most often applied approach at the analysis consists in the following: the signal digitize, then is carried out DFT. As a result at first the signal is displayed on basis of an individual impulse which has no frequency locality, and then on basis of sinusoids with the even and odd phases, not having spatial locality. Certainly, signal representation in frequency area is exclusively important for its analysis. However it does not mean, that the choice of functions of an impulse and a sinusoid for the decision of this problem is the best. In 1946 D.Gabor has offered a class of linear transformations which provide locality both in frequency, and in time area. The basis of an individual impulse and basis of a sinusoid can be considered as two extreme cases of these transformations. wavelets are one more example of the functions well localised in spatial and frequency areas.
• Orthogonality. Transformation should be not obligatory orthogonal. So, orthogonality usually is not considered in a context of substrip coding though wavelet as a rule, is orthogonal. Orthogonality of functions simplifies many calculations. Besides "strongly not orthogonal transformation can be unacceptable for coding.
• Fast algorithms of calculation. It, probably, the most important property. As the impossibility of practical realisation of transformation in real time brings to nothing all its positive properties.

Application wavelet – transformations for image compression

Last decade in the world considerable interest to compression of images is observed. It is caused by prompt development of computer facilities, graphic monitors, colour printers, and also the digital technics of communication. The image is represented in a digital form enough considerable quantity of bats. So, the colour picture in the size 512х512 demands for the storage of 768 Kb. If to transfer video sequence of such pictures with speed of 25 shots in a second, demanded speed will make 188.7 Mbit / with.

Distinguish compression of images lost-free and with losses. The first is characterised by insignificant factors of compression (from 3 to 5 times) and application in TV, medicine, air photography and other applications finds. At compression of the image with admissible losses the compression factor can reach hundreds times. Popularity wavelet - transform (WT) in many respects speaks that it can successfully be used for image compression as lost-free, and with losses. So, the factor of compression of video signal in family ADV6xx video codecs varies from 3 to 350 and more times.

It is some reasons of successful application.

1. It is known, that wavelet - well approximates transformation Karuner - forfractal signals which images concern also.
2. Dispersions of factors of substrips orthonormal wavelet transform are distributed in a wide range of values. Let dispersions are coded simple entropic by the coder. Then cost of coding of all image is the sum of coding of substrips. Various entropy of substrips will be led by coding costs considerably smaller, than at direct coding of the image.
3. As a result of this redistribution of dispersions factors wavelet - have essentially nongaussian statistics and, thus, smaller entropy, than gaussian a signal of the same dispersion.
4. At last, factors wavelet - have regular spatially-frequency dependences which with success are used in a number of algorithms of coding.

Let's consider the basic problems arising at compression of the image with the help wavelet - transform and possible ways of their decision.

Base wavelet - the image coder

wavelet - the image coder is arranged the same as also any other coder with transformation. We name such coder base. It consists of three basic parts: decorrelate transformation, procedure of quantization and entropy coding. Now all over the world researches on improvement all three component of the base coder are carried out.

1.1 Choice wavelets for image compression

The choice of optimum basis wavelets for image coding is difficult and hardly solved problem. A number of criteria of construction "good" wavelets among which the most important are is known: smoothness, accuracy of approximation, size of a range of definition, frequency selectivity of the filter. Nevertheless, the best combination of these properties is unknown.

The elementary kind wavelet - basis for images is divisible the basis received by compression and a stretching one-dimensional wavelets. Use divisible transformations reduces a problem of search of effective basis to an one-dimensional case, and almost all known coders for today use it. However inseparable bases can be more effective, than divisible.

Prototypes of basic functions for divisible transformations are functions ф () ф(), ф() (), () ф () and () (). On each step of transformation one is carried out two splittings on frequency, instead of. We will assume, we have the image in the size N х N. At first each of N lines of the image shares on low-frequency and high-frequency half. It turns out two images in the sizes N? N / 2. Further, each column shares similarly. As a result it turns out four images in the sizes N / 2? N / 2: low-frequency across and verticals, high-frequency across and verticals, low-frequency across both high-frequency on a vertical and high-frequency across and low-frequency on a vertical.

It is known, that for coding of images well approach spline wavelets. The experiments spent by a number of researchers, show importance of smoothness of basic functions for compression. Practically so the great value has number of the zero moments wavelets which is closely connected with smoothness. Despite it, some researchers consider, that importance of smoothness for applications of digital processing of signals remains an open question. Most widely in practice use the bases having from one to two continuous derivatives. The smoothness increase does not lead to increase in efficiency of coding.

D.Villasenor has regularly tested all biorthogonal blocks of filters of the minimum order with length of filters <=36. In addition to the criteria set forth above sensitivity of approximation with the low permission to function shifts f (x) was considered also. The best filter found in these experiments, it has appeared spline the filter 7/9. This filter is most often used in wavelet - images. In particular, in family ADV6xx video codecs these filters are applied.

It is necessary to make one remark concerning these results. D.Villasenor compared the peak relation a signal/noise received at use of various filters in the simple scheme of coding. The algorithm of placing the bit applied by it, well works with orthogonal bases. In a case biorthogonal filters other, more effective algorithm should be applied. Owing to this reason some worthy biorthogonal filters have been bypassed by it.

For biorthogonal transformations the square of an error in the field of transformation is not equal to an error square in the restored image. As a result the problem of minimisation of an error becomes much more difficult, than in an orthogonal case. It is possible to reduce an error in the field of the image by application of the scheme of the weighed distribution of bats. Then variety of filters by the efficiency becomes equal to the filter 7/9. One of such bases - interpolating wavelet Deslauri - Dubuk an order 4 which advantage is that filter factors - rational numbers, multiple degrees 2. wevelet 4 zero moments and two continuous derivatives have both these.

The family of promising filters has been developed by I.Balasingamom and T.Ramstadom. Working out procedure consisted in a combination of classical methods of working out of filters with ideas of the theory wavelets. The turned out filters considerably surpass popular filters 7/9.

1.2. Transformation realisation on image borders

For effective compression it is necessary to process image borders carefully. An alternative method is designing of the boundary filters keeping orthogonality of transformation near to border. A number of articles of E.Kovachevich is devoted a problem of designing of boundary filters. At application lifting border schemes are considered automatically.

1.3. Quantization

In the majority wavelet - scalar quantization is applied. There are two basic strategy of performance of scalar quantization. If distribution of factors in each strip is in advance known, use quantizers Lloyd - with the limited entropy for each substrip will be optimum. Generally we do not possess similar knowledge, but we can transfer the parametrical description of factors by a parcel to the decoder of additional bats. It is a priori known, that factors of high-frequency strips have generalised gaussian distribution with zero expectation.

In practice it is usually applied much more simple uniform quantizer with a "dead" zone. Quantization intervals have the size ^, except the central interval (near zero), whose size usually gets out 2 ^. To the factor which has got to some interval, value centrode this interval is put in conformity. In a case asymptotically high speeds of coding uniform quantization is optimum. Though in practical operating modes quantizers with a "dead" zone suboptimal , they work almost as well, as quantizers> Lloj-yes-maksa being much easier in execution. Besides, they robust to changes of distribution of factors in a substrip. Their additional advantage is that they can be enclosed each other for reception of the enclosed bit stream.

1.4. entropic coding

Suboptimum entropic coding of factors can be carried out by means of algorithm of arithmetic coding. The coder needs to estimate distribution quantize factors. This estimation turns out by approximation of distribution of factors gaussian or mechanical in density and calculations of parametres of distribution. The estimation of parametres can be made also and in the course of work, "on the move". Such approach has that advantage, that the coder considers local changes of statistics of the image. Effective adaptive procedures estimation are known.

As the image is not casual gaussian process, transformation factors though and not correlated, possess certain structure. entropic the coder can use this structure, carrying out some prediction. In a number of works it is noticed, that prediction application leads to efficiency slight increase.

In practice frequently instead of the arithmetic coder use coder Haffmana. The reason of it consists in smaller required volume of calculations, and also that algorithms of arithmetic coding are patented. So, only firm IBM possesses more than 90 patents of various variations of this coder. Owing to it in video codecs ADV6xx coder Haffmana is applied.

1.5. The measures of distortion weighed taking into account perception by the person

root-mean-square error not always will well be co-ordinated with visually observable error. We will consider, for example, two images which are completely identical, except small area. Though visually the difference between these images is well appreciable, root-mean-square error will be approximately identical. The account of system of human sight in the compression scheme is a difficult problem. The set of researches has been spent, but owing to difficulties with the mathematical description of system of sight of the person of a suitable measure has not been found. It is known, that in a human eye operation of multiscale representation of images is carried out. The eye is more sensitive to distortions in low-frequency area. From here there is a possibility of improvement of visual quality of the reconstructed image by weighing root-mean-square error of substrips according to sensitivity of an eye in various frequency ranges. Weight for most often used filter 7/9 have been calculated by A.Vatsonom.

New ideas in the field of compression of the images, connected with wavelet - transformation

Base wavelet - the coder uses the general principles of the coder with transformation, that is is based on effects decorrelation and energy redistributions. The mathematical theory wavelet - transform allows to create absolutely new and effective methods of compression.

Coding with transformation is based that the energy most part concentrates in small quantity of factors which quantize according to their value. This paradigm, being enough powerful, is based on several assumptions which are not always true. In particular, it is supposed, that the image is generated gaussian by a source that mismatches the validity. S.Mallat and F.Falzon have shown, how this discrepancy leads to incorrect results at coding with low speeds.

Traditional coding with transformation can be improved by introduction of operators of a choice. Instead of quantization of factors transformant in in advance certain order wavelet allows to choose the necessary elements for coding. It becomes possible mainly thanks to that the basis wavelets is compact in frequency and spatial areas.

Generally speaking, development of ideas of coding with transformation consists in removal of restriction on linear approximation of the image as the operator of a choice is nonlinear. In R.Devora, S.Mallata and F.Falzona's works it is shown, that the problem of coding of the image can be effectively solved within the limits of the theory of nonlinear approximation. From here there is also a number of distinctions in algorithms of work traditional and wavelet - coders. In case of linear approximation the image is represented the fixed number of basic vectors Karunen-Loiv. Further, any number of small factors transform is equated to zero. The idea of nonlinear approximation consists in approximation of the image by an adaptive choice of basic functions. The information on the chosen basic functions is stored in a binary map of values and transferred to the decoder, as the additional information.

For reception greater it is necessary for compactness of energy to adapt transformation to what - concrete, instead of for the whole class of images. In a case if the source is described by a mix of various distributions, transformation Karunen - is not more effective.

Trellised quantization of factors is much closer inherently to vector quantization, than to coding with transformation.

Development of ideas of coding with transformation consists basically in introduction of some operator of a choice. The information on a choice should be transferred the decoder, as the additional information. It can be in a kind null tree or in the form of the generalised classes of energy. The method "the return estimation distributions", the offered K.Ramchandranom, is based on other approach. It is considered, that the additional information is superfluous and can be received the decoder directly from data. Use of the given method leads to good indicators of coding.

Visual comparison of the restored images shows, that the best results give the methods using null tree for coding of factors. In particular, in these images contours are is better expressed and is absent smear small details.

Modern directions of researches

Researches in the field of compression of images are conducted in different directions. So, there was a new interpretation wavelet - transformations - lifting the scheme which has been not based on transformation Fourier. With use of this scheme there was a possibility of designing of new inseparable bases wavelets which can potentially lead to increase of efficiency of coders. An interesting direction of researches is studying of nonlinear analogues wavelet - transformations by which the lifting philosophy does possible. Active researches are spent to areas of the coders based on classification and estimation on the past.

One of the most interesting directions is working out of coders of the image steady against errors, arising in communication channels. The idea of joint optimisation of coders of a source and the channel, and also an optimum combination of separately optimised coders is thus used.

Modern wavelet - coders are based on the assumption, that the image is generated by a source with fluctuating a dispersion. Each coder realises the certain mechanism for display of a local dispersion wavelet - and quantize in their optimum or suboptimum image according to a dispersion. Coders differ from each other strategy of quantization of factors and how there is an estimation and transfer of value of a dispersion to the decoder.

The coders based on algorithm null tree, assume presence of two statuses at a dispersion: zero or not. The additional information on a site of significant factors is transferred to the decoder. This process leads to nonlinear approximation of the image. Sets of zero factors are expressed in terms of trees wavelets (Lewis and Noules,Shapiro, etc.) or combinations of these trees Said and Perelman). Zero are transferred to the decoder as the additional information, as well as quantize data. The coders based on null tree, consider interstrip dependences wavelet - factors.

In frequency-adaptive coders orthogonal adaptive transformations - a method wavelet - packages are applied. Local fluctuations of correlation communications use spatially coders.

Others wavelet consider intrastrip dependences between wavelet - factors (sometimes simultaneously and interstrip). The coders based on trellised quantization, divide factors into groups according to their energy. For each factor they estimate and (or) transfer the information on group and value quantize in conformity with a nominal dispersion of group of factor. Other new class of coders transfers insignificant quantity of the information on a dispersion. It shows, that, probably, the information on a dispersion has the big redundancy, than was considered earlier.

The conclusion

Intensity of the researches conducted in given area is that, that for detailed illumination of all extensive circle of the questions, concerning the given subject, the edition comparable on scales with BSE would be required.

Advantage wavelets in comparison with JPEG?

First, vejvlet-algorithms work with the whole image, instead of with its part. Secondly, with their help it is easy to analyze faltering signals and signals with sharp splashes as vejvlet-algorithms use essentially other mathematical apparatus. Thirdly, even at 100 multiple vejvlet-compression of the image its quality does not change almost.

The basic idea of vejvlet-transformation consists in representation of some stochastic function (in our case - an investigated signal) as superpositions of certain basic nonharmonic functions - wavelets.

That wavelets well approximated an initial signal, they are exposed to scaling (to compression or a stretching) and to shift (displacement).

Result of vejvlet-transformation - a usual file of numerical factors. Such form of representation of the information on the image is very convenient, as numerical data it is easy to process.

After that there comes very important stage - threshold transformation. It is necessary to reject the factors which value is close to zero. It is necessary to remember, that thus there is an irreversible loss of the information, after all the rejected factors participate in image formation. Therefore the chosen threshold value of factors strongly influences quality of the image - the task of too high threshold will cause quality falling.

So, the compression occurs in two stages - on the first compression with loss information (vejvlet-transformation), on the second - usual archiving of data is carried out.

For image restoration it is necessary to repeat all actions upside-down. At first values of factors, and then on them are restored, applying return vejvlet-transformation, receive the image (signal).

As practical application wavelet - transform modern approaches to compression of images are considered. wavelet - transformation has laid down in a basis of international standard MPEG-4, the standard on compression of prints of fingers of FBI, firm Analog Devices video codecs. Now working out of standard JPEG-2000 where wavelet - transform it is probable is conducted, also will find of itself application.

The vejvlet-analysis has found wide application in set of applications - in medicine, in biology, in oil and gas branch, in telecommunications. FBI actively uses wavelets for optimisation of algorithms of storage of dactyloscopic databases, and NASA develops technology of application of the vejvlet-analysis to problems of development of a space.

In countries of Western Europe and the USA wavelets confidently supersede JPEG-technologies. In Russia only ISS - one of few companies offering software products, using vejvlet-ideology.

Meanwhile, in many areas it is possible to expect essentially best results at the expense of use wavelets. We will list some of them. The problems connected with a prediction. It is a prediction of a price of securities in the market, a prediction of earthquakes, weather forecast.

wavelets are successfully applied in the quantum physics, at studying of a structure of atom, in the laser technics. Clearing of noisenoisy signals. So, scientists Stenford with success have applied wavelets to improvement of sounding of old phonograph records. The problems connected with detection of a signal against a hindrance, its recognition, classifications. By employees of Research laboratory of Naval Forces of the USA wavelets were applied to detection of submarines, for an estimation of the destructions made by bombardments, and for many other things the important military-applied problems.

---

The literature

1. Воробьев В.И., Грибунин В.Г. "Теория и практика вейвлет преобразования" ВУС, 1999. С.1 -204.
2. Петухов А.П. Введение в теорию базисов всплесков. Учебное пособие. СПб.: СПбГТУ, 1999., 132 с.
3. Л. В. Новиков. Основы вейвлет-анализа сигналов. Учебное пособие. СПб.: Изд-во ООО "МОДУС+", 1999. 152 с.
4. http://data.ufn.ru//ufn01/ufn01_5/Russian/r015a.pdf статья «Вейвлеты и их использование» И.М. Дремин, О.В. Иванов, В.А. Нечитайло – Успехи физических наук, том 171, №5, 2001. 37p. Полезное пособие тем, кто собирается применять дискретное вейвлет-преобразование в практических расчетах.
5. http://www.basegroup.ru/filtration/intro-to-wavelets.htm – статья Киселева Андрея «Основы теории вейвлет-преобразования».
6. http://www.masters.donntu.ru/2005/kita/stoyanovsky/index.htm
7. Дьяконов В.П. "Вейвлеты. От теории к практике". - М.: СОЛОН-Р, - 2002. 448с
8. http://entropyware.info/articles.html

Copyright © Alexander Butok DonNtU 2008