Digital imagery has had an enormous impact on industrial, scientific and computer applications. It is no surprise that image coding has been a subject of great commercial interest in today’s world. Uncompressed digital images require considerable storage capacity and transmission bandwidth. Efficient image compression solutions are becoming more critical with the recent growth of data intensive, multimedia-based web applications.
An image is a positive function on a plane. The value of this function at each point specifies the luminance or brightness of the picture at that point. Digital images are sample versions of such functions, where the value of the function is specified only at discrete locations on the image plane, known as pixels. During transmission of these pixels the pixel data must be compressed to match the bit rate of the network.
In order to be useful, a compression algorithm has a corresponding decompression algorithm that, given the compressed file, reproduces the original file. There have been many types of compression algorithms developed.
These algorithms fall into two broad types, loss less algorithms and lossy algorithms. A lossless algorithm reproduces the original exactly. A lossy algorithm, as its name implies, loses some data. Data loss may be unacceptable in many applications. For example, text compression must be lossless because a very small difference can result in statements with totally different meanings. There are also many situations where loss may be either
Unnoticeable or acceptable. In image compression, for example, the exact reconstructed value of each sample of the image is not necessary. Depending on the quality required of the reconstructed image, varying amounts of loss of information can be accepted.
Various research works were carried out on both lossy and non-lossy image compression. The JPEG committee released a new image-coding standard, JPEG 2000 that serves the enhancement to the existing JPEG system. The JPEG 2000 implements a new way of compressing images based on the wavelet transforms in contrast to the transformations used in JPEG standard.
A majority of today’s Internet bandwidth is estimated to be used for images and video transmission. Recent multimedia applications for handheld and portable devices place a limit on the available wireless bandwidth. The bandwidth is limited even with new connection standards. JPEG image compression that is in widespread use today took several years for it to be perfected. Wavelet based techniques such as JPEG2000 for image compression has a lot more to offer than conventional methods in terms of compression ratio. Currently wavelet implementations are still under development lifecycle and are being perfected. Flexible energy-efficient implementations that can handle multimedia functions such as image processing, coding and decoding are critical, especially in hand-held portable multimedia wireless devices.
Computer data compression is, of course, a powerful, enabling technology that plays a vital role in the information age. Among the various types of data commonly transferred over networks, image and video data comprises the bulk of the bit traffic. For example, current estimates indicate that image data take up over 40% of the volume on the Internet The growth in demand for image and video data, with delivery limitation has kept compression technology at a premium. Among the several compression standards available, the JPEG image compression standard is in wide spread use today. JPEG uses the Discrete Cosine Transform (DCT) as the transform, applied to 8-by-8 blocks of image data. The newer standard JPEG2000 is based on the Wavelet Transform (WT). Wavelet Transform offers multi-resolution image analysis, which appears to be well matched to the low level characteristic of human vision. The DCT is essentially unique but WT has many possible realizations. Wavelets provide a more suitable way for representing images. This is because it can represent information at a variety of scales, with local contrast changes, as well as larger scale structures and thus is a better fit for image data. An enhancement to image compression coding is recently proposed [1] using Embedded Zero-tree coding which exploit the multiresolutional properties of the wavelet transform to give a computationally simple algorithm with outstanding performance.
1.2 STATEMENT OF PROBLEM
For progressive transmission, image browsing, multimedia applications, and compatible transcoding, in a digital hierarchy of multiple bit rates, the problem of obtaining the best image quality and accomplishing it in an embedded fashion i.e. all the encoded bits making compatible to the target bit rate is a bottleneck task for today’s engineer. As images are of huge data set and encoding it for a lower bit rate results in loss of data, which intern results in very low image quality under retrievation. Coming to the transmission over a noisy channel this problem becomes more effective due to narrow bandwidth effect. Various algorithms were proposed for encoding and compressing the image data before transmission. These algorithms show high-end results under high bandwidth systems but show poor result under low data rate systems.
The problem of transmission of images over a low bit rate bandwidth can be overcome if the image data bits are such encoded and compressed that the data bit rate is made compatible to the provided low bit rate.
Embedded zero tree wavelet algorithm is a proposed image compression algorithm which encode the bit in the bit stream in the order of importance which embed the bit stream in hierarchical fashion.
1.3 OBJECTIVE OF THE STUDY
Data compression is the process of converting data files into smaller files for efficiency of storage and transmission. As one of the enabling technologies of the multimedia revolution, data compression is a key to rapid progress being made in information technology. It would not be practical to put images, audio, and video alone on websites without compression.
Data compression treats information in digital form, that is, as binary numbers represented by bytes of data with very large data sets. Fox example, a single small 4. × 4. Size color picture, scanned at 300 dots per inch (dpi) with 24 bits/pixel of true color, is produce a file containing more than 4 megabytes of data. At least three floppy disks are required to store such a picture. This picture requires more than one minute for transmission by a typical transmission line (64k bit/second ISDN). That is why large image files remain a major bottleneck in a distributed environment. Although increasing the bandwidth is a possible solution, the relatively high cost makes this less attractive. Therefore, compression is a necessary and essential method for creating image files with manageable and information can be accepted.
This project work aims towards the realization of an enhanced embedded image-coding algorithm for low bit rate data transmission.
1.4 REVIEW OF LITERATURE
The problem for image compression is more important in many applications, particularly for progressive transmission, image browsing [2], multimedia applications, and compatible Transcoding in a digital hierarchy of multiple bit rates.
The embedded zero-tree wavelet coding for image processing [1] uses universal coding for its implementation. Various works shows the implementation of various algorithms for the compression of transformed image data. A technique that is closer in spirit to the zero trees in the end-of-block (EOB) symbol used in JPEG [7], which is also a terminating symbol indicating that all remaining DCT coefficients in the block are quantized to zero. Targeting toward JPEG 2000 [8], [9] Standard the Embedded Zero-Tree wavelet coding [1], [8] uses the wavelet [5], [6] coefficient for encoding. Wavelets use the multiresolution analysis [6] for decomposing the image into sub-band [4] as detail and approximate coefficients. In Subband coding systems [4], the coefficients from a given subband are usually grouped together for the purposes of designing Quantizer and coders.
Literature search shows that very few works on generation of an accurate bit stream that claims higher PSNR performance at rates between 0.25 and 1 bit/pixel were made. Z. Xiong, K. Ramchandran and M. Orchad [3] uses a tree coding where the said value is zero if its energy is less than perceptually based threshold.
An approach to the low bit rate image transform coding is presented by S.Mallat and F.Falzon [2]. The overview to lossy wavelet image compression for JPEG 2000 [9] and Wavelet transformation with Embedded zero-tree coding were presented by Bryan E. Usevitch [8]. Colm Mulcahy presented the application of embedded coding on an isolated tile image for image compression in his paper [10] using Haar wavelet. The paper gives an approach towards embedded coding using Haar wavelet transform for real image.
1.5 SCOPE OF STUDY
The wavelet based coding has improved significantly since the introduction of JPEG standard. Typical JPEG image coder requires an extensive training for both quantization (both scalar and vector) and generation of nonadaptive entropy codes for encoding.
The embedded coding scheme implemented uses universal coding schemes that have been used for loss less data compression. In this scheme the data bits are encoded a source using no prior knowledge of the source.
The Embedded zero tree wavelet coding uses the multi resolution properties of wavelet transform to give a computationally simple algorithm for low bit rate data transmission over the network. Due to the simplification in the computational effort the system improves the decoding rate and overall improves the operation speed of the image processing system. The Embedded zero tree wavelet coding can be used for multiple bit rate application ranging from a lower rate to higher rate, this gives an advantage of using on single encoding and decoding system for multiple bit rate application.
1.6 METHODOLOGY
''Data compression'', a fundamental topic of computer science, is the process of encoding data so that it takes less storage space or less transmission time than it would if it were not compressed. This is possible because most real-world data is very redundant or not most concisely represented in its human-interpretable form. Various methods were proposed for data compression in which the Commonly used Data compression techniques are;
1.6.1. Lossless Data Compression
''Lossless data compression'' refers to data compression algorithms which allow the original data to be reconstructed ''exactly'' from the compressed data. Contrast with lossy data compression. Lossless data compression is used in software compression tools such as the highly popular Zip format, used by PKZIP and WinZip, and the UNIX programs bzip2, gzip and compress. Image file formats, such as PNG, use only lossless compression, while others like TIF and MNG may use either Lossless or lossy methods.
Lossless compression methods may be categorized according to the type of data they are designed to compress. The three main types of targets for compression algorithms are text, images, and sound.
Most lossless compression programs use two different kinds of algorithm: One which generates a ''statistical model'' for the input data, and another which maps the input data to bit strings using this model in such a way that "probable" (e.g. frequently encountered) data is produce shorter output than "improbable" data.
1.6.2. Lossy data compression
‘‘Lossy data compression'' method is one where compressing a file and then decompressing it retrieves a file that may well be different to the original, but is "close enough" to be useful in many ways. This method is used on Internet and especially in streaming media and telephony applications.
The advantage of lossy methods over Lossless data compression/lossless methods is that in some cases a lossy method can produce a much smaller compressed file than any known Lossless method, while still meeting the requirements of the application.
Lossy methods are most often used for compressing sound or images. In these cases, the retrieved file can be quite different to the original at the bit level while being indistinguishable to the human ear or eye for most practical purposes.
1.6.3 METHODS OF DATA COMPRESSION
1) STATISTICAL ENCODING METHODS
a) COMMA CODING
The Comma code is a non-optimal code, which often leads to more efficient decoder circuits. The Comma code, is a prefix-free, and derives its name from the fact that it contains a terminating symbol, e.g. 0, at the end of each codeword.
The Comma encoding procedure first sorts the unique patterns in decreasing order of probability of occurrence, and encodes the first pattern (i.e., the most probable pattern) with a 0, the second with a 10, the Third with a 110, and so on. The procedure encodes each pattern by adding a 1 to the beginning of the previous codeword.
b) RUN-LENGTH CODING
Comma encoding considers the large number of repetitions of patterns in the data sequence without directly making use of the fact that there are many contiguous, identical patterns. Run-length encoding exploits this property of the data sequences.
Table. 1 Distribution of runs in data set.
Run-length coding is a data compression technique that replaces a sequence of identical symbols with a Copy of the repeating symbol and the length of the sequence. Run-length coding assigns a fixed code word for every observation, which result in lower compression rate. The counting of repeated occurrence of data bits makes the system comparatively slower.
c) ARITHMETIC CODING
In arithmetic coding a source ensemble is represented by an interval between 0 and 1 on the real number line. Each symbol of the ensemble narrows this interval. As the interval becomes smaller, the number of bits needed to specify it grows. The method begins with an unordered list of source messages and their probabilities. The number line is partitioned into subintervals based on cumulative probabilities.
Several difficulties become evident when implementation of arithmetic coding is attempted. The first is that the decoder needs some way of knowing when to stop. Two solutions to this problem have been suggested. One is that the encoder transmits the size of the ensemble as part of the description of the model. Another is that a special symbol be included in the model for the purpose of signaling end of message. Both these solutions increases the data bits to be transmitted and requires high computation to predict these data bits under reconstruction as the track of bit stream has to be maintain and the starting and ending point is to be found.
d) HUFFMAN CODING
The Huffman code is found to be more optimal since it results in the shortest average codeword length among all encoding techniques that assign a unique binary codeword to each pattern. In addition, Huffman codes possess the prefix-free property, i.e., no codeword is the prefix of a longer codeword.
The first step in the encoding process is to identify the unique patterns in the test set. A codeword is then developed for each unique pattern using the Huffman code construction method. The obtained Huffman tree is then used to construct code words for the patterns of a data set. These code words are assigned to the data bits for compression. The rate of compression achieved is considerably high compared to other encoding techniques due to its variable length property. Typical image coder generally consist of this encoding process, however this method require extensive training of non adaptive entropy codes and has to maintain a codebook for encoding and decoding. System following Huffman coding generally shares the codebook under transmission and reception. These parameters make the coding system non efficient. An enhance coding proposed by Shapiro [1] over come these excessive codebook maintenance.
e) EMBEDDED CODING
The original or “heritage” wavelet coders were based on the same basic ideas found in sub-band coding. The era of modern lossy wavelet coding began in 1993 when Jerry Shapiro introduced EZW coding [1]. EZW coding exploits the multiresolution nature of wavelet decomposition to give completely a new way of doing image coding. The resulting algorithm had improved performance at low bit rates relative to the existing JPEG standard as well as having other nice feature such as completely embedded bit representation. EZW marked the beginning of modern wavelet coding since improved wavelet coders proposed subsequent to EZW are based on fundamental concepts from EZW coding.
The EZW algorithm contains the following features
* A discrete wavelet transforms which provides a compact multiresolution representation of the image.
* Zero tree coding, which provides a compact multiresolution representation of significance maps, which are binary maps indicating the positions of the significant coefficients. Zero trees allow the successful prediction of insignificant coefficients across scales to be efficiently represented as a part of exponentially growing trees.
* Successive approximations, which provides a compact multiprecision representation of the significant coefficients and facilitates the embedding algorithm.
* A prioritization protocol whereby the ordering of importance is determined in order by the precision, magnitude, scale, and spatial location of the wavelet coefficients. In particular, the larger coefficients are deemed more important than smaller coefficients regardless of their scale.
1.7 LIMITATION OF STUDY
Although EZW shows much enhancement to the existing image coding system, this system has got few limitations. EZW performs poorly when errors are introduced into the coded data. This is because the embedded nature of the coding causes errors to propagate from the point that they are introduced to the end of the data. This is not a problem in low noisy environment but does pose a problem in the modern wireless world where error rates in data communication can be quite high. Another concern is that the original EZW data structure is not very flexible. For example, some applications may want to be selectively decoding an image to increase resolution only in certain portions of the image. Such selective spatial decoding requires modifications to the original Embedded Zero-tree Wavelet algorithm.
CHAPTER 2
EMBEDDED ZEROTREE WAVELET CODING
2.1 TRANSFORM CODING
Digital image is represented as a two-dimensional array of coefficients, each coefficient representing the brightness level in that point. Differentiation can be made between coefficients as more important ones, and lesser important ones. Most natural images have smooth color variations, with the fine details being represented as sharp edges in between the smooth variations. Technically, the smooth variations in color can be termed as low frequency variations, and the sharp variations as high frequency variations.
The low frequency components (smooth variations) constitute the base of an image, and the high frequency components (the edges which give the details) add upon them to refine the image, thereby giving a detailed image. Hence, the smooth variations are more important than the details. Separating the smooth variations and details of the image can be performed in many ways. One way is the decomposition of the image using the discrete wavelet transform. Digital image compression is based on the ideas of sub-band decomposition or discrete wavelet transforms.
Wavelets, which refer to a set of basis functions, are defined recursively from a set of scaling coefficients and scaling functions. The DWT is defined using these scaling functions and can be used to analyze digital images with superior performance than classical short-time Fourier-based techniques, such as the DCT, FFT. The basic difference between wavelet-based and Fourier-based techniques is that short-time Fourier-based techniques use a fixed analysis window, while wavelet-based techniques can be considered using a short window at high spatial frequency data and a long window at low spatial frequency data. This makes DWT more accurate in analyzing image signals at different spatial frequency, and thus can represent more precisely both smooth and dynamic regions in image.
2.2 WAVELET TRANSFORM
The fundamental idea behind wavelets is to analyze the signal at different scales or resolutions, which is called multiresolution. Wavelets are a class of functions used to localize a given signal in both space and scaling domains. A family of wavelets can be constructed from a mother wavelet. Compared to Windowed Fourier analysis, a mother wavelet is stretched or compressed to change the size of the window. In this way, big wavelets give an approximate image of the signal, while smaller and smaller wavelets zoom in on details. Therefore, wavelets automatically adapt to both the high frequency and the low-frequency components of a signal by different sizes of windows. Any small change in the wavelet representation produces a correspondingly small change in the original signal, which means local mistakes are not influence the entire transform. The wavelet transform is suited for nonstationary signals, such as very brief signals and signals with interesting components at different scales.
Wavelets are functions generated from one single function ψ, which is called mother wavelet, by dilations and translations
Where ψ must satisfy ∫ ψ (x) dx = 0.
The basic idea of wavelet transform is to represent any arbitrary function f as a decomposition of the wavelet basis or write f as an integral over a and b of ψa,b .
Let with m, n € integers, and a0>1,b0>0 fixed. Then the wavelet decomposition is
In image compression, the sampled data are discrete in time. It is required to have discrete representation of time and frequency, which is called the discrete wavelet transform (DWT).
Wavelet Transform (WT) was used to analyze non-stationary signals, i.e., whose frequency response varies in time. Although the time and frequency resolution problems are results of a physical phenomenon and exist regardless of the transform used, it is possible to analyze any signal by using an alternative approach called the multi resolution analysis (MRA). MRA analyzes the signal at different frequencies with different resolutions. MRA are basically designed to give good time resolution and poor frequency resolution at high frequencies and good frequency resolution and poor time resolution at low frequencies. This approach is useful especially when the signal considered has high frequency components for short durations and low frequency components for long durations. Which are basically used in practical applications.
2.3 THE CONTINUOUS WAVELET TRANSFORM
A continuous wavelet transform is given as:
---------- (1)
Where * denotes complex conjugation. From this equation it can be seen how a function f (t) is decomposed into a set of basis functions, Ψ s, τ (t) called the wavelets. The variables s and t , scale and translation, are the new dimensions after the wavelet transform. For completeness sake (2) gives the inverse wavelet transform. --------- (2)
The wavelets are generated from a single basic wavelet (t), the so-called mother wavelet, by scaling and translation:
---------- (3)
In (3) s is the scale factor is the translation factor and the factor s-1/2 is for energy normalization across the different scales. It is important to note that in (1), (2) and (3) the wavelet basis functions are not specified. This is a difference between the wavelet transform and the Fourier transform, or other transforms. The theory of wavelet transforms deals with the general properties of the wavelets and wavelet transforms only. It defines a framework within one can design wavelets to taste and wishes.
2.4 DISCRETE WAVELETS
The wavelet transform has three properties that make it difficult to use directly in the form of (1). The first is the redundancy of the CWT. In (1) the wavelet transform is calculated by continuously shifting a continuously scalable function over a signal and calculating the correlation between the two. It is seen that these scaled functions is nowhere near an orthogonal basis and the obtained wavelet coefficients is therefore be highly redundant. For most practical applications this redundancy is removed.
Even without the redundancy of the CWT one still have an infinite number of wavelets in the wavelet transform and would like to see this number reduced to a more manageable count. This is the second problem.
The third problem is that for most functions the wavelet transforms have no analytical solutions and they can be calculated only numerically or by an optical analog computer. Fast algorithms are needed to be able to exploit the power of the wavelet transform and it is in fact the existence of these fast algorithms that have put wavelet transforms where they are today.
Let us start with the removal of redundancy.
As mentioned before the CWT maps a one-dimensional signal to a two-dimensional time-scale joint representation that is highly redundant. The time-bandwidth product of the CWT is the square of that of the signal and for most applications, which seek a signal description with as few components as possible, this is not efficient. To overcome this problem discrete wavelets have been introduced.
Discrete wavelets are not continuously scalable and translatable but can only be scaled and translated in discrete steps. This is achieved by modifying the wavelet
Representation (3) to create
---------- (4)
Although it is called a discrete wavelet, it normally is a (piecewise) continuous function. In (4) j and k are integers and s0 > 1 is a fixed dilation step. The translation factor Ï„0 depends on the dilation step. The effect of discretizing the wavelet is that the time-scale space is now sampled at discrete intervals. It is usually chosen s0 = 2 so that the sampling of the frequency axis corresponds to dyadic sampling. This is a very natural choice for computers, the human ear and music for instance. For the translation factor the value is usually chosen Ï„0 = 1 so that a dyadic sampling of the time axis is obtained.
When discrete wavelets are used to transform a continuous signal the result is be a series of wavelet coefficients, and it is referred to as the wavelet series decomposition. An important issue in such a decomposition scheme is of course the question of reconstruction. It is all very well to sample the timescale joint representation on a dyadic grid, but if it is not be possible to reconstruct the signal it is not be of great use. As it turns out, it is indeed possible to reconstruct a signal from its wavelet series decomposition. It is proven that the necessary and sufficient condition for stable reconstruction is that the energy of the wavelet coefficients must lie between two positive bounds, i.e.
------- (5)
Where || f ||2 is the energy of f(t), A > 0, B <>j, k (t) with j, k € Z is referred to as a frame with frame bounds A and B. When A = B the frame is tight and the discrete wavelets behave exactly like an orthonormal basis. When A≠B exact reconstruction is still possible at the expense of a dual frame. In a dual frame discrete wavelet transform the decomposition wavelet is different from the reconstruction wavelet.
The last step that has to taken is making the discrete wavelets orthonormal. This can be done only with discrete wavelets. The discrete wavelets can be made orthogonal to their own dilations and translations by special choices of the mother wavelet, which means:
--------- (6)
An arbitrary signal can be reconstructed by summing the orthogonal wavelet basis functions, weighted by the wavelet transform coefficient:
--------- (7)
Equation (7) shows the inverse wavelet transform for discrete wavelets, which is not yet seen. Orthogonal is not essential in the representation of signals. The wavelets need not be orthogonal and in some applications the redundancy can help to reduce the sensitivity to noise or improve the shift invariance of the transform. This is a disadvantage of discrete wavelets: the resulting wavelet transform is no longer shift invariant, which means that the wavelet transforms of a signal and of a time-shifted version of the same signal are not simply shifted versions of each other.
In many practical applications the signal of interest is sampled. In order to use the results one have achieved so far with a discrete signal that have to make our wavelet transform discrete too. Remember that our discrete wavelets are not time-discrete, only the translation- and the scale step are discrete. Simply implementing the wavelet filter bank as a digital filter bank intuitively seems to do the job. But intuitively is not good enough.
Stated that the scaling function could be expressed in wavelets from minus infinity up to a certain scale j. If added a wavelet spectrum to the scaling function spectrum that is get a new scaling function, with a spectrum twice as wide as the first. The effect of this addition is that one can express the first scaling function in terms of the second, because all the information that is need to do this is contained in the second scaling function. It can express this formally in the so-called multiresolution formulation or two-scale relation
----------- (8)
The two-scale relation states that the scaling function at a certain scale can be expressed in terms of translated scaling functions at the next smaller scale. Do not get confused here: smaller scale means more detail. The first scaling function replaced a set of wavelets and therefore one can also express the wavelets in this set in terms of translated scaling functions at the next scale. More specifically it can be written for the wavelet at level j. Which is the two-scale relation between the scaling function and the wavelet.
--------- (9)
A signal f (t) could be expressed in terms of dilated and translated wavelets up to a scale j-1, this leads to the result that f (t) can also be expressed in terms of dilated and translated scaling functions at a scale j:
--------- (10)
To be consistent in the notation discrete scaling functions are to be considered, since only discrete dilations and translations are allowed. If in this equation one step up a scale to j-1, it had to add wavelets in order to keep the same level of detail. It can then express the signal f (t) as
-------- (11)
If the scaling function φ j, k (t) and the wavelets ψ j, k (t) are orthonormal or a tight frame, then the coefficients λ j-1(k) and γ j-1(k) are found by taking the inner products
----------- (12)
If φ j ,k (t) and ψ j ,k (t) are replaced in the inner products by suitably scaled and translated versions of manipulate a bit, keeping in mind that the inner product can also be written as an integration,
--------- (13)
--------- (14)
These two equations state that the wavelet- and scaling function coefficients on a certain scale can be found by calculating a weighted sum of the scaling function coefficients from the previous scale. Now recall from the section on the scaling function that the scaling function coefficients came from a low pass filter and recall from the section on sub band coding how it is iterated a filter bank by repeatedly splitting the low-pass spectrum into a low-pass and a high-pass part. The filter bank iteration started with the signal spectrum, so if the signal spectrum is the output of a low-pass filter at the previous (imaginary) scale, then the sampled signal can be considered as the scaling function coefficients from the previous (imaginary) scale. In other words, the sampled signal f(k) is simply equal to (k) at the largest scale.
As known from signal processing theory a discrete weighted sum are the same as a digital filter and since the coefficients λ j (k) come from the low-pass part of the splitted signal spectrum, the weighting factors h (k) must form a low-pass filter. And since the coefficients γ j (k) come from the high-pass part of the splitted signal spectrum, the weighting factors g (k) must form a high-pass filter.
This means that they form one stage of an iterated digital filter bank and from now on the coefficients h (k) is referred as the scaling filter and the coefficients g(k) as the wavelet filter.
It is now certain that implementing the wavelet transform as an iterated digital filter bank is possible and from now on one can speak of the discrete wavelet transform or DWT. Our intuition turned out to be correct. Because of this one are rewarded with a useful bonus property of (13) and (14), the sub sampling property. One last look at these two equations one see that the scaling and wavelet filters have a step-size of 2 in the variable k. The effect of this is that only every other λ j(k) is used in the convolution, with the result that the output data rate is equal to the input data rate. Although this is not a new idea, it has always been exploited in sub band coding schemes, it is kind of nice to see it pop up here as part of the deal.
The sub sampling property also solves our problem, which had come up at the end of the section on the scaling function, of how to choose the width of the scaling function spectrum. Because, every time the iterate the filter bank the number of samples for the next stage is halved so that in the end one are left with just one sample (in the extreme case). It is be clear that this is where the iteration definitely has to stop and this determines the width of the spectrum of the scaling function.
Normally the iteration is stop at the point where the number of samples has become smaller than the length of the scaling filter or the wavelet filter, whichever is the longest, so the length of the longest filter determines the width of the spectrum of the scaling function.
2.5 WAVELET FILTER
With the redundancy removed, one still have two hurdles to take before, the wavelet transform in a practical form. Continuing by trying to reduce the number of wavelets needed in the wavelet transform and save the problem of the difficult analytical solutions for the end.
Even with discrete wavelets it still needs an infinite number of scalings and translations to calculate the wavelet transform. The easiest way to tackle this problem is simply not to use an infinite number of discrete wavelets. Of course this poses the question of the quality of the transform. Is it possible to reduce the number of wavelets to analyze a signal and still have a useful result.
The translations of the wavelets are of course limited by the duration of the signal under investigation so that have an upper boundary for the wavelets.
From (18) it is observed that wavelet has a band-pass like spectrum. From Fourier theory the compression in time is equivalent to stretching the spectrum and shifting it upwards:
This means that a time compression of the wavelet by a factor of 2 is stretch the frequency spectrum of the wavelet by a factor of 2 and also shift all frequency components up by a factor of 2. Using this insight one can cover the finite spectrum of our signal with the spectra of dilated wavelets in the same way as that one covered our signal in the time domain with translated wavelets. To get a good coverage of the signal spectrum the stretched wavelet spectra should touch each other, as if they were standing hand in hand. This can be arranged by correctly designing the wavelets.
Fig 2.1 Touching Wavelet Spectra resulting from scaling of mother wavelet in the time domain
Summarizing, if one wavelet can be seen as a band-pass filter, then a series of dilated wavelets can be seen as a band-pass filter bank. If one look at the ratio between the center frequency of a wavelet spectrum and the width of this spectrum it is seen that it is the same for all wavelets. This ratio is normally referred to as the fidelity factor Q of a filter and in the case of wavelets one speaks therefore of a constant-Q filter bank
.
2.6 SCALING FUNCTION
The scaling function was introduced by Mallat. It is sometimes referred to as the averaging filter Because of the low-pass nature of the scaling function spectrum.
If the scaling function is considered as being just a signal with a low-pass spectrum, then it can be decompose in wavelet components and expressed as (7):
---------- (15)
Since the scaling function (t) is selected in such a way that its spectrum neatly fitted in the space left open by the wavelets, the expression (15) uses an infinite number of wavelets up to a certain scale j as shown in figure 2.2. This means to analyze a signal using the combination of scaling function and wavelets, the scaling function by itself takes care of the spectrum otherwise covered by all the wavelets up to scale j, while the rest is done by the wavelets. In this way limited the number of wavelets from an infinite number to a finite number are obtained.
Fig 2.2 An infinite set of wavelets replaced by one scaling Function
By introducing the scaling function that have circumvented the problem of the infinite number of wavelets and set a lower bound for the wavelets. Of course when using a scaling function instead of wavelets, information is lost. That is to say, from a signal representation point of view one do not loose any information, since it is still be possible to reconstruct the original signal, but from a wavelet analysis point of view possible valuable scale information is discarded. The width of the scaling function spectrum is therefore an important parameter in the wavelet transform design. The shorter its spectrum the more wavelet coefficients you is have and the more scale information. But, as always, there is be practical limitations on the number of wavelet coefficients you can handle. Later on, in the discrete wavelet transform this problem is more or less automatically solved. The low-pass spectrum of the scaling function allows us to state some sort of admissibility condition similar to (19)
∫ φ (t) dt =1 -------- (16)
Which shows that the 0th moment of the scaling function cannot vanish.
Summarizing once more, if one wavelet can be seen as a band-pass filter and a scaling function is a low pass filter, then a series of dilated wavelets together with a scaling function can be seen as a filter bank.
2.7 SUB-BAND ANALYSIS
A time-scale representation of a digital signal is obtained using digital filtering
Techniques. Recall that the CWT is a correlation between a wavelet at different scales and the signal with the scale (or the frequency) being used as a measure of similarity. The continuous wavelet transform was computed by changing the scale of the analysis window, shifting the window in time, multiplying by the signal, and integrating over all times. In the discrete case, filters of different cutoff frequencies are used to analyze the signal at different scales. The signal is passed through a series of high pass filters to analyze the high frequencies, and it is passed through a series of low pass filters to analyze the low frequencies.
The resolution of the signal, which is a measure of the amount of detail information in the signal, is changed by the filtering operations, and the scale is changed by up sampling and down sampling (sub sampling) operations. Sub sampling a signal corresponds to reducing the sampling rate, or removing some of the samples of the signal. For example, sub sampling by two refers to dropping every other sample of the signal. Sub sampling by a factor n reduces the number of samples in the signal n times.
Up sampling a signal corresponds to increasing the sampling rate of a signal by adding new samples to the signal. For example, up sampling by two refers to adding a new sample, usually a zero or an interpolated value, between every two samples of the signal. Up sampling a signal by a factor of n increases the number of samples in the signal by a factor of n.
Although it is not the only possible choice, DWT coefficients are usually sampled from the CWT on a dyadic grid, i.e., s0 = 2 and ∏ 0 = 1, yielding s=2j and ∏ =k*2j . Since the signal is a discrete time function, the terms function and sequence is be used interchangeably in the following discussion. This sequence is be denoted by x[n], where n is an integer.
The procedure starts with passing this signal (sequence) through a half band digital low pass filter with impulse response h [n]. Filtering a signal corresponds to the mathematical operation of convolution of the signal with the impulse response of the filter. The convolution operation in discrete time is defined as follows:
A half band low pass filter removes all frequencies that are above half of the highest frequency in the signal. For example, if a signal has a maximum of 1000 Hz component, then half band low pass filtering removes all the frequencies above 500 Hz.
The unit of frequency is of particular importance at this time. In discrete signals, frequency is expressed in terms of radians. Accordingly, the sampling frequency of the signal is equal to 2∏ radians in terms of radial frequency. Therefore, the highest frequency component that exists in a signal is be ∏ radians, if the signal is sampled at Nyquist’s rate (which is twice the maximum frequency that exists in the signal); that is, the Nyquist’s rate corresponds to ∏ rad/s in the discrete frequency domain. Therefore using Hz is not appropriate for discrete signals. However, Hz is used whenever it is needed to clarify a discussion, since it is very common to think of frequency in terms of Hz. It should always be remembered that the unit of frequency for discrete time signals is radians.
After passing the signal through a half band low pass filter, half of the samples can be eliminated according to the Nyquist’s rule, since the signal now has a highest frequency of ∏/2 radians instead of ∏ radians. Simply discarding every other sample is sub sample the signal by two, and the signal is then have half the number of points. The scale of the signal is now doubled. Note that the low pass filtering removes the high frequency information, but leaves the scale unchanged. Only the sub sampling process changes the scale. Resolution, on the other hand, is related to the amount of information in the signal, and therefore, it is affected by the filtering operations. Half band low pass filtering removes half of the frequencies, which can be interpreted as losing half of the information. Therefore, the resolution is halved after the filtering operation. Note, however, the sub sampling operation after filtering does not affect the resolution, since removing half of the spectral components from the signal makes half the number of samples redundant anyway. Half the samples can be discarded without any loss of information. In summary, the low pass filtering halves the resolution, but leaves the scale unchanged. The signal is then sub sampled by 2 since half of the number of samples is redundant. This doubles the scale.
This procedure can mathematically be expressed as
Having said that, now looking at how the DWT is actually computed: The DWT analyzes the signal at different frequency bands with different resolutions by decomposing the signal into coarse approximation and detail information. DWT employs two sets of functions, called scaling functions and wavelet functions, which are associated with low pass and high pass filters, respectively. The decomposition of the signal into different frequency bands is simply obtained by successive high pass and low pass filtering of the time domain signal. The original signal x[n] is first passed through a half band high pass filter g[n] and a low pass filter h[n]. After the filtering, half of the samples can be eliminated according to the Nyquist’s rule, since the signal now has a highest frequency of ∏ /2 radians instead of ∏. The signal can therefore be sub sampled by 2, simply by discarding every other sample. This constitutes one level of decomposition and can mathematically be expressed as follows:
Where yhigh [k] and ylow [k] are the outputs of the high pass and low pass filters, respectively, after sub sampling by 2. This decomposition halves the time resolution since only half the number of samples now characterizes the entire signal. However, this operation doubles the frequency resolution, since the frequency band of the signal now spans only half the previous frequency band, effectively reducing the uncertainty in the frequency by half. The above procedure, which is also known as the sub band coding, can be repeated for further decomposition. At every level, the filtering and sub sampling is result in half the number of samples (and hence half the time resolution) and half the frequency band spanned (and hence double the frequency resolution). Figure 2.3 illustrates this procedure, where x [n] is the original signal to be decomposed, and h[n] and g[n] are low pass and high pass filters, respectively. The bandwidth of the signal at every level is marked on the figure as "f".
The dominant pass can thus be implemented as;
* Dominant pass
initialize_fifo();
while (fifo_not_empty)
{
get_coded_coefficient_from_fifo();
if coefficient was coded as P, N or Z then
{
code_next_scan_coefficient();
put_coded_coefficient_in_fifo();
if coefficient was coded as P or N then
{
add abs(coefficient) to subordinate list;
set coefficient position to zero;
}
}
}
After the dominant pass follows the subordinate pass:
/*
* Subordinate pass
*/
subordinate_threshold = current_threshold/2;
for all elements on subordinate list do
{
if (coefficient > subordinate_threshold)
{
output a one;
coefficient = coefficient-subordinate_threshold;
}
else output a zero;
}
If the threshold used is a power of two, then the subordinate pass reduces to a few logical operations and can be made very fast.
CHAPTER 3
SYSTEM ANALYSIS
3.1 THE HARDWARE REQUIREMENTS
1. 128MB RAM (min) 256MB RAM (optimal)
2. Pentium III/IV machines with 300 MHz or Higher
3. 40 GB Hard Disk
4. Monitor
5. Keyboard
6. Mouse
7. CD Drive
3.2 THE SOFTWARE REQUIREMENTS
1. MAT LAB 6.5
2. Java Virtual Machine
3. Rational Rose
3.3 INTRODUCTION TO SYSTEM ANALYSIS
The development of standards by the International Organization for Standardization (ISO) for audio, image, and video, for both transmission and storage, has led to worldwide activity in developing hardware and software systems and products applicable to a number of diverse disciplines. With the continual expansion of multimedia and Internet applications, the needs and requirements of the technologies used grew and evolved. JPEG 2000 standard was intended to create a new image coding system for different types of still images (bilevel, gray level, color, multicomponent), with different characteristics (natural images, scientific, medical, remote sensing, text, rendered graphics, etc.) allowing different imaging models (client/server, real-time transmission, image library archival, limited buffer and bandwidth resources, etc.) preferably within a unified system. This coding system provide low bit-rate operation with rate distortion and subjective image quality performance superior to existing standards, without sacrificing performance at other points in the rate-distortion spectrum, and at the same time incorporating many interesting features. It has proved a valuable tool during all these years, but it cannot fulfill the advanced requirements of today. Today’s digital imagery is extremely demanding, not only from the quality point of view, but also from the image size aspect. Current image size covers orders of magnitude, ranging from web logos of size of less than 100Kbits to high quality scanned images of approximate size of 40 Gbits. The JPEG 2000 international standard represents advances in image compression technology here the image coding system is optimized not only for efficiency, but also for scalability and interoperability in network and mobile environments. The markets and applications better served by the JPEG 2000 standard are Internet, color facsimile, printing, scanning (consumer and prepress), digital photography, remote sensing, mobile, medical imagery, digital libraries/archives, and E-commerce.
The state of wavelet-based coding has improved significantly since the introduction of the original JPEG standard. A notable breakthrough was the introduction of embedded zero-tree wavelet (EZW) coding . The EZW algorithm was able to exploit the multiresolutional properties of the wavelet transform to give a computationally simple algorithm with outstanding performance.
Improvements and enhancements to the EZW algorithm have resulted in modern wavelet coders which have improved performance relative to block transform coders. As a result, wavelet-based coding has been adopted as the underlying method to implement the JPEG 2000 standard.
The original wavelet coders were based on the same basic ideas found in subband coding. EZW coding exploited the multiresolution nature of the wavelet decomposition to give a completely new way of doing image coding. The resulting algorithm had improved performance at low bit rates relative to the existing JPEG standard, as well as having other nice features such as a completely embedded bit representation. EZW marked the beginning of modern wavelet coding since improved wavelet coders proposed subsequent to EZW are based on fundamental concepts from EZW coding.
CHAPTER 4
SYSTEM DESIGN
4.1 DESIGN CONSIDERATION
The Embedded zero-wavelet tree coding is fundamentally been classified into 6 major parts;
1) Preprocessing of the source image.
2) Transformation of the processed image using wavelet transforms.
3) Encoding the transformed data for compression.
4) Decoding the compressed encoded data.
5) Performing the inverse transformation on the decoded data to retrieve back the original data back.
6) Processing the retrieved data to obtain the original image back.
The design unit implements the Embedded zero-tree wavelet coding system for data compression. The coding system reads the multiresolution component of the image obtain from the transformation module and pass the data to the decoder unit to retrive the image back. Figure below shows the implemented embedded zero tree wavelet coding system for image processing.
4.2.1 PREPROCESSING UNIT
Before the processing of image data the image are preprocessed to improve the rate of operation for the coding system. Under preprocessing tiling on the original image is carried out. The term “tiling” refers to the partition of the original (source) image into rectangular nonoverlapping blocks (tiles), which are compressed independently, as though they were entirely distinct images. All operations, including component mixing, wavelet transform, quantization and entropy coding are performed independently on the image tiles. The tile component as shown in Fig 4.2 is the basic unit of the original or reconstructed image. Tiling reduces memory requirements, and since they are also reconstructed independently, they can be used for decoding specific parts of the image instead of the whole image. All tiles have exactly the same dimensions, except maybe those at the boundary of the image. Arbitrary tile sizes are allowed, up to and including the entire image (i.e., the whole image is regarded as one tile).
| |||||
Original image
Fig 4.2 Tiling of original image
4.2.2 TRANSFORMATION UNIT
This unit Transforms the input image from time domain to frequency domain and decomposes the original image into its fundamental components. The transformation is performed using Debuchie wavelet transform. Wavelet transform is a very useful tool for signal analysis and image processing, especially in multi-resolution representation. One-dimensional discrete wavelet transform (1-D DWT) decomposes an input sequence into two components (the average component and the detail component) by calculations with a low-pass filter and a high-pass filter. Two-dimensional discrete wavelet transform (2-D DWT) decomposes an input image into four sub-bands, one average component (LL) and three detail components (LH, HL, HH) as shown in Fig 4.3.
Fig 4.3 The result of 2-D DWT decomposition
The wavelet transform uses filter banks shown in Fig 4.5 for the decomposition of preprocessed original image into 3 details and 1 approximate coefficient. 2-D DWT is achieved by two ordered 1-D DWT operations (row and column). Initially the row operation is carried out to obtain 1 D decomposition. Then it is transformed by the column operation and the final resulted 2-D DWT is obtained.
Fig 4.4 Filter Bank Implementation of Wavelet sub-band decomposition
The filtering is carried out by convolving the input image with the filter coefficients passed. Each decomposing stage consists of a pair of high pass and a low pass filter. These filters isolate the highly varying and low varying components from the given image. Fig 4.5 (a) shows the original image used for decomposition into fundamental subbands using filter bands as shown in Fig 4.4. Fig 4.5 (d) shows the 3 level decomposition of the original image. The approximate coefficient obtained at each level were further decomposed to 3 detailed and 1 approximate coefficient for n levels
4.2.3 EZW ENCODING
The Embedded ZeroTree Wavelet(EZW) encoder encodes the decomposed image by recognizing the priority of decomposed image pixel. The encoder module calculates a initial threshold for coding given by T0 = 2^(log2xmax). The encoding process is performed using 2 passes namely dominant pass and subordinate pass. The dominant pass scan the coefficient using the threshold and assigned each coefficient with a symbol. Basically there 4 isolated symbols for coding, they are positive significant(TS), negative significant(NS), isolated zero(IZ) and zerotree root(ZR). A PS symbol is assigned when the current coefficient is above the threshold. The coefficient is coded as NS if the coefficient is below the negative of the threshold value. An isolated zero is assigned to a coefficient if 1 or more descending coefficients are above the threshold. A zerotree is assigned if the coefficient and all the relative descending coefficients are below the threshold. Any coefficient which are been coded as zerotree is be isolated and result in zero value under decoding.
The other pass made at the encoding unit is the subordinate pass where the coefficients are encoded as 0 or 1 depending on the current threshold. These passes are repeated for n cycles reducing the current threshold by 2 until the required data bit rate is reached.
4.2.4 EZW DECODING
The decoding unit reconstructs the values by identifying the symbols as positive, negative, zerotree and isolated zerotree. The reconstructed values are taken as threshold for positive coded coefficients and negative of threshold for negative coded coefficients. The zerotree coefficients and the isolated zerotree coefficients are assigned with 0 value.
4.2.5 INVERSE TRANSFORMATION
Inverse transformation is the process of retriving back the image data from the obtained image values. The image data trasnformed and decomposeed under encoding side is rearranged from higher level decomposition to lower level with the highest decomposed level been arranged at the top. From the highest level of decomposition
4.3.2 QUANTIZATION UNIT
Quantization refers to the process of approximating the continuous set of values in the image data with a finite (preferably small) set of values. The input to a quantizer is the original data, and the output is always one among a finite number of levels. The quantizer is a function whose set of output values are discrete, and usually finite. Obviously, this is a process of approximation, and a good quantizer is one which represents the original signal with minimum loss or distortion.
The input-output characteristics of quantization process is shown in Fig 4.10. Inverse quantization formulates the reverse of quantization. In quantization process each block of Transformed coefficients is subjected to a process of quantization, wherein grayscale and color information are discarded. Each transformed coefficient is divided by its corresponding element in a scaled quantization matrix, and the resulting numerical value is rounded. The default quantization matrices for luminance and chrominance are specified in the JPEG standard, and were designed in accordance with a model of human perception. The scale factor of the quantization matrix directly affects the amount of image compression, and the lossy quality of JPEG compression arises as a direct result of this quantization process.
Fig 4.10 Quantization relationship wrt. a given input
In quantization, each input symbol is treated separately in producing the output. A quantizer can be specified by its input partitions and output levels (also called reproduction points). If the input range is divided into levels of equal spacing, then the quantizer is termed as a Uniform Quantizer, and if not, it is termed as a Non-Uniform Quantizer. A uniform quantizer can be easily specified by its lower bound and the step size. Also, implementing a uniform quantizer is easier than a non-uniform quantizer. For example in Fig 4.11 if the input falls between n*r and (n+1)*r, the quantizer outputs the symbol n.
Fig 4.11 A uniform quantizer
Just the same way a quantizer partitions its input and outputs discrete levels, a Dequantizer is one which receives the output levels of a quantizer and converts them into normal data, by translating each level into a 'reproduction point' in the actual range of data. It can be seen from literature, that the optimum quantizer (encoder) and optimum dequantizer (decoder) must satisfy the following conditions.
- Given the output levels or partitions of the encoder, the best decoder is one that puts the reproduction points x' on the centers of mass of the partitions. This is known as centroid condition.
- Given the reproduction points of the decoder, the best encoder is one that puts the partition boundaries exactly in the middle of the reproduction points, i.e. each x is translated to its nearest reproduction point. This is known as nearest neighbour condition.
· The quantization error (x - x') is used as a measure of the optimality of the quantizer and dequantizer.
The Quantizer Quantizes the data at a specific step level ∆ given by
The Quantizer Quantizes the data at a specific step level ∆ given by
(Step size) ∆ = R/ (2b -1)
where R is the range of the image matrix (I)
(Range) R = max (I)-min (I). ‘b’ indicate the number of bit outputted for every step. The quantization carried out on thresholding operation. For every value of the image element fed to the quantizer an equivalent binary sequence is passed as output which is passed to the encoder module for further processing.
4.3.3 ENTROPY ENCODER
After the data has been quantized into a finite set of values, it can be encoded using an Entropy Coder to give additional compression. By entropy, it means the amount of information present in the data, and an entropy coder encodes the given set of symbols with the minimum number of bits required to represent them. Various algorithms were proposed for the coding of image among which huffman coding is found to be more efficient than others.
Huffman encoding is designed to work best on images that have a lot of repetition. The general concept is to assign the most used bytes fewer bits, and the least used bytes more bits. First, the most used bytes in the image are assigned a variable length binary code. The more often the byte is used the shorter the control code. The less often a byte occurs the longer the control code.
4.3.4 HUFFMAN DECODER
The decoder unit decodes the encoded data bit stream from the encoder module. The decoder unit performs the reverse operation to the encoder process. This unit shares the same code word used under encoding from the code book.
The Huffman decoder block carries out decoding reading the unique code bits passed in place of the data bit. The data bits are received in serial format and compared with the unique word. Equivalent data bits are passed out whenever there is a matching of the unique word. For decoding of ‘m’ block of data bits a minimum of 2m-1 iterations are performed which make the system much slower in operation.
4.3.5 DEQUANTIZER
The dequantizer unit dequantizer the decoded data bits. The dequantization operation is carried in the reverse manner to the quantization. The dequantizer takes the same step sizes as in quantization from the quantization table. The reconstructed data are not exactly recovered to the original image which makes the system a lossy compression system.
4.3.6 INVERSE TRANSFORMATION
The inverse Transforamtion is carried out in a similar fashion to the one explained
Under the embedded coding.
4.4 USE CASE DIAGRAM
A use case provides a description of how the system is be used. To create a use case, the analyst must first identify the different types of people that use the system or product. These actors usually represent roles that people or devices play as the system operates. An actor is usually anything that communicates with the system or product that is external to the system itself.
A use case diagram is a diagram which shows a set of use cases and actors and the associations between these actors and use cases. Infact a use case diagram shows the interaction of the things that are outside the system with things that are inside the system. A use case is represented using an ellipse and the actors are represented using dummy sticks.
IMPLEMENTATION
5.1 GENERAL IMPLEMENTATION
1.Top: The first user interface module for interfacing userdata to the implemented design.
Function UICONTROL id used to create user interface control.
CALLBACK: Predefined operator used to call the function for simulation and return the
result.
2.Gui1: Gui1 is 2nd user interface file for reading input and passing to processing unit for
further process
3.Read1: Function used for reading input image from the work space.
Uigetfile(user interface get file)
4.Gui: The next user interface function used to create interface for processing wavelets and embedding coding and to view and analyze the results.
5.Process2: Implements JPEG2000 coding system.
6. User definrd function used for implementing wavelet decomposition. This function reads the input file, number of scales and the wavelet type for wavelet decomposition. This function returns 2 parameters coefficient matrix & bookkeeping matrix.
7. wavefilter: This function defines all the filter coefficients for performing filtering, convolution operation in filter banks.
8.symextend: This function extend the image matrix symmetrically in both directions based on the extension value passed. The extension to the image matrix is performed to overcome the border effect obtained due to convolution operation.
9.symconv: This function takes the image data and the type of convolution to be carried out from the top module. In this function the image data get convolved with the filter coefficients in 1-D either in rows or in columns based on the passed type. This function also down sample the obtained convolved matrix and returns the down sampled convolved matrix back.
10.wave2gray: This function is used for displaying the obtained scaled image in appropriate scaled order.
11. waveback: The obtained decomposed image is passed to this function to reconstruct the image back. This function calls wavefilter function to obtained the filter coefficients and perform the convolution operation. The convolution operation is carried out using the function symconvup.
12. Symconvup: This function reads the image matrix and the filter coefficient with the type of convolution, and performs a 1-D convolution operation. This function uses conv function to convolve the data. The convolved data is then upsampled by a factor of 2 and returned back.
13. process1: This function implements the embedded zerotree wavelet coding algorithm for the compression of image data. The function calls sampletest1 function which realizes the EZW coding.
14.wvcall: This function is used to file out the whole image into an (8x8) subblock set. These subblocks are then passed to the wavelet transformation unit for transformation.
15.wvback: This function rejoins the file blocks to retrieve back the original image of original dimension.
16. Dominant pass: This function read the coefficient data and performs the scanning on these data using morse scanning. The function list out the dominant coefficients in the given matrix.
17.Analysis: This function read the time and error values from the processing module and plot the time comparison and error comparison for the 2 processing units.
18.go,go1: These functions read the obtained results from the process1 and process2 and display the original and final images for the EZW process and wavelet process respectively.
19.scale: This function read the scaled value for the 2 process and display the scaled image in multiscale format.
20.Upsam: This function upsamples the data by a factor of 2.
21. haffman: This function calls the probability matrix and carryout haffman coding to generate the code book used for compression. This function use the reduced and make code function to generate code book.
22.mapping: This function is used to create the morton scan order for scanning. The scan is continue until the last level.
23.subordinate pass: This function scans on the sublist created during the dominant pass to findout the zerotree.
24.checkchildren: This function id used for decoding the compressed data. This function returns the descend value and 1 for all zerotree elements. This function self repeat until the size of scaled data.
25.checkancestor: This function checks for the descends from the zerotree root.
26.checkdescendents: This function returns the results after decoding the coefficients of significance. The significant coefficients are taken from significant descend matrix.
CHAPTER 6
INTERPRETATION OF RESULTS
INPUT CONSIDERATIONS:
This project implements EZW and JPEG2000 coding for image compression. The implemented algorithm is tested for various types of inputs. The inputs considered for testing are of different dimensions (256x256, 128x128, 110x110) with both gray scale as well as color images. The images considered are with varying pixel intensity.
CONCLUSION
This project implements an enhanced image coding system for image compression compared to the existing JPEG 2000 system. It is observed that EZW is able to achieve its good performance with a relatively simple algorithm. EZW does not require complicated bit allocation procedures like subband coding does, it does not require training or codebook storage like vector quantization does, and it does not require prior knowledge of the image source like JPEG does (to optimize quantization tables). EZW also has the desirable property, resulting from its successive approximation quantization.
One desirable consequence of an embedded bit stream is that it is very easy to generate coded outputs with the exact desired size. Truncation of the coded output stream does not produce visual artifacts since the truncation only eliminates the least significant refinement bits of coefficients rather than eliminating entire coefficients as is done in subband coding.
From the obtained results it is concluded that embedded zerotree wavelet coding takes comparatively less(about 60%) time then the JPEG coding system. The coding also shows less percentage of error in retrieved image compare to the existing JPEG coding system. It is observed that image coded with embedded zerotree wavelet coding shows clearer image than other coding system.
FUTURE SCOPE
This project implements the coding algorithm on less noisy images. The work can be further extending for different kind of images having different properties. The project realizes EZW coding algorithm that can be further applied for image coding systems where embedded coding is used.
REFERENCES
1. J.Shapiro, “Embedded image coding using zerotrees of wavelet coefficients,” IEEE Trans. Signal Processing, vol. 41, pp.3445-3462, Dec 1993.
2. S.Mallat and F. Falzon, “Analysis of low bit rate image transform coding,” IEEE Trans. Signal Processing, vol. 46, pp. 1027-1042, Apr. 1998.
3. Z. Xiong, K . Ramchandran, and M. Orchad, “Space-frequency quantization for wavelet image coding,” IEEE Trans. Signal Processing, vol. 6, pp. 677-693, May 1997.
4. E. H. Adelson, E. Simoncelli, and R. Hingorani, “Orthogonal pyramid transforms for image coding,” Proc. SPIE, vol. 845, Cambridge, MA, Oct. 1987, pp. 50-58.
5. R. A. DeVore, B. Jawerth, and B. J. Lucier, ”Image compression through wavelet transform coding,” IEEE Trans. Informat. Theory, vol. 38, pp. 719-746, Mar. 1992.
6. S. Mallat, “A theory for multiresolution signal decomposition: The wavelet representation,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 37, pp.2091-2110, Dec.1990.
7. G. K. Wallace, “ The JPEG Still Picture Compression Standard,” Commun. ACM, vol. 34, pp. 30-44, Apr. 1991.
8. Bryan E. Usevitch, “A Tutorial on “Modern Lossy Wavelet Image Compression: Foundations of JPEG 2000”, IEEE signal processing magzine, 1053-5888,sep-2001.
9. Athanassios Skodras, Charilaos Christopoulos, and Touradj Ebrahimi, “The JPEG 2000 Still Image Compression Standard” IEEE signal processing magzine, 1053-5888,sep-2001.
10. Colm Mulcahy “Image Compression using the Haar wavelet transform”, spelman science and Math Journal.
ANNEXURE
1. DWT DISCRETE WAVELET TRANSFORM
2. DCT DISCRETE COSINE TRANSFORM
3. FFT FAST FOURIER TRANSFORM
4. CWT CONTINUOUS WAVELET TRANSFORM
5. MRA MULTI RESOLUTION ANALYSIS
6. EZW EMBEDDED ZEROTREE WAVELET
7. JPEG JOINT PHOTOGRAPH EXPERT GROUP
8. PSNR PEAK SIGNAL TO NOISE RATIO
9. WT WAVELET TRANSFORM
10. LL LOW LOW COMPONENTS
11. LH LOW HIGH COMPONENTS
12. HL HIGH LOW COMPONENTS
13. HH HIGH HIGH COMPONENTS
14. ZR ZEROTREE ROOT
15. IZ ISOLATED ZERO
16. TS POSIRIVE SIGNIFICANT
NS NEGATIVE SIGNIFICANT
2 comments:
Hello Sir I am PG student and my project is on videowatermarking ,it includes embedding a binary logo in a uncoded video frames using dwt and pca.Pls help me out with this
recently I have mailed about the videowateramrking project pls. send me code on mail amita.waghmare6@gmail.com
Post a Comment