In Place Modified Fast Haar Wavelet Transform Biology Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

As the health care is computerized novel techniques and applications are developed, along with them are the MR and CT techniques. To overcome this problem image compression has been introduced in the field of medical. Wavelets are mathematical tools for hierarchically decomposing functions. Wavelet Transform has been proved to be an extremely useful tool for image processing in recent years. The most discrete feature of Haar Transform lies in the fact that it lends itself easily to uncomplicated manual calculations. Modified Fast Haar Wavelet Transform (MFHWT), is one of the algorithms which can lessen the calculation work in Haar Transform (HT) and Fast Haar Transform (FHT). The In-Place MFHWT further reduces the memory consumption and useless movement of intermediary coefficients. The present paper attempts to explain the algorithm for image compression using In-Place MFHWT and shows that it is faster. It includes a number of examples of different images to confirm the usefulness and importance of algorithm's performance.

A lot of hospitals handle their medical image data using computers. The employ of computers and a network makes it attainable to distribute the image data among the staff efficiently. MR and CT produce series of images (image stacks) all along the cross-section of an object. The quantity of data produced by these techniques is enormous and this might be a difficulty when sending the data over a network. Medical image compression performs as a key role as hospitals, move towards film- less imaging and go wholly digital compression. Image compression will let Picture Archiving and Communication Systems (PACS) to decrease the file sizes on their storage necessities while maintaining related diagnostic information because in spite of rapid progress in mass-storage density, processor speeds, and digital communication system performance, requirement for data storage capacity and data-transmission bandwidth continues to exceed than the capabilities of available technologies. The recent growth of data intensive multimedia-based web applications have not only sustained the need for more proficient ways to encode signals and images but have made compression of such signals central to storage and communication technology.

Image compression is an application of data compression on digital images. The image is in actuality a kind of redundant data i.e. it contains the same information from certain perspective of view. By using data compression techniques, it is feasible to remove some of the redundant information contained in images. Image compression is reducing the size in bytes of a graphics file without degrading the quality of the image to an acceptable level. The decrease in file size allows additional images to be stored in a given amount of disk or memory space. It also reduces the time necessary for images to be sent over the Internet or downloaded from Web pages.

The transform coding constitutes an integral component of contemporary image processing applications. Transform coding relies on the premise that pixels in an image exhibit a certain level of correlation with their neighboring pixels. As a result, these correlations can be exploited to predict the value of a pixel from its respective neighbors. A transformation is, therefore, defined to map this spatial (correlated) data into transformed (uncorrelated) coefficients. Clearly, the transformation should utilize the fact that the information content of an individual pixel is relatively small i.e. to a large extent visual contribution of a pixel can be predicted using its neighbors. [7]

2. Image Compression Using Wavelets

2.1 Wavelets and Image Compression

Wavelets are the foundation for representing signals, such as images, in a hierarchy of increasing resolutions. While taking into account more and more resolution layers we get a vivid and detailed look at the images. The decomposition of an image into different frequency bands is obtained by successive low-pass and high-pass filterings of the signal and down-sampling the coefficients following each filtering. Because of their data reduction ability and uniform distribution of compression error cross the entire image, Wavelets are considered as efficient transform coding for compressing image

information. Wavelets offer adaptive spatial frequency resolution (better spatial resolution at high frequencies and better frequency resolution at low frequency), which is helpful in improving image quality.

A wavelet literally means a small wave. It is a type of mathematical function used to divide a given function or continuous-time signal into different frequency components and study every component with a resolution that matches its scale.

2.2 Haar Wavelet

A Haar wavelet is the simplest kind of wavelet. In discrete form, Haar wavelets are related to a mathematical operation called the Haar transform. The Haar transform serves as a prototype for all additional wavelet transforms. Like all wavelet transforms, the Haar transform decomposes a discrete signal into two sub signals of half its length. One sub signal is a running average or trend; the other sub signal is a running difference or fluctuation.

2.3 Mathematical description

Wavelets are generated from one particular function (basis function) known as mother wavelet. Mother Wavelet is a prototype for generating the other window functions.

The mother wavelet is scaled (or dilated) by a factor of a and translated (or shifted) by a factor of b to give

where a and b are two random real numbers. 'a' and 'b' represent the dilations and translations parameters correspondingly in the time axis. The parameter 'a' contracts (t) in the time axis when a < 1 and expands or stretches when a > 1. Hence 'a' is called the dilation (scaling) parameter. For a < 0, the function ψa,b(t) outcome in time reversal with dilation. Mathematically, when't' is replaced in equation by (t - b) it causes a translation or shift in the time axis resulting in the wavelet function. [24]

To know how wavelets work, let us begin with a simple example. Imagine 1D image with a resolution of four pixels, having values [8 6 2 4]. Haar wavelet basis can be used to signify this image by computing a wavelet transform. To do this, first the average of the pixels together, pair wise, is calculated to obtain the new lower resolution image with pixel values [7 3]. Clearly, a quantity of information is lost in this averaging process. To recover original four pixel values from the two averaged values, some detail coefficients needed to be stored. The first detail coefficient is 1. This single number is used to recover the first two pixels of the original four-pixel image. Similarly, the second detail coefficient is -1, since 3 + (-1) = 2 and 3 - (-1) = 4. Thus, the original image is decomposed into a lower resolution (two-pixel) version and a pair of detail coefficients. Repeating this process recursively on the averages gives the full decomposition shown in Table 1:

Table 1. Decomposition to Lower Resolution

4

[8 6 2 4]

2

[7 3]

[1 -1]

1

[5]

[2]

Thus, for the one-dimensional Haar basis, the wavelet transform of the original four-pixel image is given by [5 2 1 - 1]. The way used to compute the wavelet transform by recursively averaging and differencing coefficients is called as filter bank. The image can be reconstructed to any resolution by recursively adding and subtracting the detail coefficients from the lower resolution versions.[23]

The Haar wavelet transform has a number of advantages:

• It is conceptually uncomplicated.

• It is speedy.

• It is memory efficient, for the reason that it can be calculated in place with no temporary array.

• It is exactly reversible with no the edge effects that are a problem with other Wavelet transform.

In generating each of averages for the subsequent level and each set of coefficients, the Haar transform performs an average and difference on a pair of values. Then the algorithm shifts over by two values and calculates another average and difference on the next pair. The high frequency coefficient spectrum should mirror all high frequency changes Human Visual System is less sensitive to high frequency signal and more sensitive to low frequency signal. By taking into account this phenomenon, the threshold value or quantization factor is selected and thresholding/ quantization take place in image compression.

2.4 Fast Haar Wavelet Transform

The major operations in the Haar transform are effortless additions and subtractions the overhead involved in the data movement of intermediate results at each low stage is a chief source of speed degradation. The characteristics of a new in place form of the Haar transform algorithm is that in this movement of Haar coefficients is minimized, resulting in less total operations. The price of this advantage is a different ordering of the Haar coefficients. There is a easy calculation which can be used to arbitrarily access the Haar coefficients given the degree and member number of the coefficient. The major motivation behind the development of this algorithm was to trim down the memory requirements of the transform and the amount of incompetent movement of Haar coefficients. At all stage in the transform the amount of operations involving any particular intermediate value is always two. Both the operations involve the same second intermediate value. After each pair of operations is finished the two intermediate value locations can be used to store the results of the calculations. Only the results of at most two operations would have to be stored at any one time. [4]

2.5 Modified Fast Haar Wavelet Transform

Modified Fast Haar Wavelet Transform (MFHWT), is one of the algorithms which can reduce the calculation work in Haar Transform (HT) and Fast Haar Transform (FHT).

Modified Fast Haar Transform not only allows certain calculation in the process decomposition be ignored without affecting the results, but also still remains in simple type of calculation as for FHT. The MFHT works based on the idea that approximate coefficients can be ignored since it is not involve in the reconstruction work as well as threshold process in multi-resolution wavelet analysis. As FHT, we use 2N data. For Modified Fast Haar Transform, MFHT, it can be done by just taking (w+ x + y + z)/ 4 instead of (x + y)/ 2 for approximation and (w+ x − y − z)/ 4 instead of (x − y)/ 2 for differencing process. 4 nodes have been considered at once time. Notice that the calculation for (w+ x − y − z)/ 4 will yield the detail coefficients in the level of n − 2. [20]

In MFHWT, for data of size 2N, the approximations are calculated as

and detail sub signal at the same level is given as

For the purpose of getting detail coefficients, differencing process (x − y)/ 2 still need to be done. . Figure 1 shows the calculation of the Modified Fast Haar Transform, for N = 4 , given by the data F = [2 4 6 3 1 2 5 9 8 13 15 7 8 9 0 4] T [20]

Figure 1: Modified Fast Haar Transform, MFHT [20]

3. Haar to In-Place MFHWT

Since the Haar Transform is memory efficient, just reversible without the edge effects, it is fast and simple. As such the Haar Transform technique is broadly used these days in wavelet analysis. Fast Haar Transform is one of the algorithms which can decrease the tedious work of calculations.

Fast Haar Transform (FHT) involves addition, subtraction and division by 2, due to which it becomes faster and reduces the calculation work in contrast to HT. For the decomposition of an image, first apply 1D FHT to each row of pixel values of an input image matrix. These transformed rows are themselves an image and then apply the 1D FHT to each column. The resulting values are all detail coefficients except for a only overall average coefficient.

The MFHWT is faster in contrast to FHT and reduces the calculation work. Since the reconstruction procedure in multi-resolution wavelet does not involve approximation coefficients, except for the level 0 and we require storing only half of the original data used in FHT. The coefficients can be disregarded to reduce the memory requirements of the transform and the quantity of inefficient movement of Haar coefficients. So, we get the values of approximation and detail coefficients one level in advance than the FHT and HT.

This fulfills the aim of trying to reduce the memory requirements of the transform and the amount of inefficient movement of Haar coefficients. The main advantage of MFHWT is sparse representation and fast transformation and possibility of implementation of fast algorithms.

Further reduction in memory requirement can be done by using In-Place MFHWT. Instead of placing the intermediate results in another array, during the application of MFHWT algorithm, we can use the original array by merely replacing the coefficients by the newer ones.

Thus in the light of the above discussion it may be concluded that reasonably accurate numerical results can be obtained by using the In-Place MFHWT.

.

4. In-Place Modified Fast Haar Wavelet Technique

In- Place Modified Fast Haar wavelet Technique is formed by combing the two techniques that is In-Place Algorithm and Modified Fast Haar Wavelet Transform. With Modified Fast Haar wavelet Technique, the memory utilization during the compression process can be reduced. Further Reduction in memory utilization can be decreased with In - Place Algorithm.

In In-Place Algorithm for MFHWT the storage of intermediate coefficients is shown in the figure 2.

Figure 2: Storage of intermediate coefficients

So, in this technique there is no requirement of another array to store the results. The intermediate and final results are stored in the original array by overwriting the original coefficients.

Figure 3 shows the calculation of the In-Place Modified Fast Haar Transform, for N = 4 , given by the data F = [2 4 6 3 1 2 5 9 8 13 15 7 8 9 0 4] T

Figure 3: Calculation of 1-D array using In-Place MFHWT

5. Results and Discussion

In the case of lossy compression, the reconstructed image is only an approximation to the original. Although many performance parameters exist for quantifying image quality, it is most frequently expressed in terms of mean squared error (MSE) and peak signal to noise ratio (PSNR), which is defined as follows.

Mean Square Error (MSE):

Peak Signal to noise ratio PSNR:

where HW is the size of the images, Y(i,j) and X(i,j) are the matrix elements of the decompressed and original images at (i,j) pixel. The larger PSNR values correspond to good image quality.

In order to estimate the performance of image compression systems, compression ratio metric is frequently employed. In our results, compression ratio (CR) is computed as the ratio of non-zero entries in the original image to the non-zero entries in the transformed image.

Compression Ratio CR:

CR = n1/n2

where n1 and n2 denote the number of non zero entries in original image and transformed image, respectively.

For comparing the speed of compressing an image with HT, FHT and In Place MFHWT, time elapsed parameter has been taken. The time of processing can be measured using the matlab command tic- toc. The tic and toc functions work together to measure elapsed time. Tic saves the current time that toc uses later to measure the elapsed time and displays the time in seconds.

Energy retained throughout the compression process is given by the density parameter. Density is calculated as number of non- zero elements in compressed image.

Image compression experiments using HT, FHT and In Place MFHWT are conducted on natural images: Strawbery.jpg, Lady.tif, Large.jpg, Khush.jpg and Book.jpg pictures which are used frequently in the image compression literature.

The results shown here are calculated using software matlab.

Figure 4: Application of Haar Wavelet on Strawbery.jpg image

Figure 5: Application of Fast Haar Wavelet on Strawbery.jpg image

Figure 6: Application of In-Place Modified Fast Haar Wavelet on Strawbery.jpg image

Figure 7: Application of Haar Wavelet on Lady.tif image

Figure 8: Application of Fast Haar Wavelet on Lady.tif image

Figure 9: Application of In-Place Modified Fast Haar Wavelet on Lady.tif

Table 2, 3 and 4 shows the results of application of HT, FHT and In- Place MFHWT. It can be seen that the time taken by In-Place MFHWT is least while compressing.

Thus In- Place MFHWT provides a faster compressing technique.

Table 2. Results using Haar Wavelet

IMAGE

HAAR WAVELET

RMSE

PSNR

(db)

CR

DENSITY (%age)

TIME

(Sec)

Strawbery.jpg

0.00282

50.9713

1.022

97.7595

3.328

Lady.tif

0.05265

25.5713

1.025

97.5277

0.766

Large.jpg

0.00755

42.4296

1.442

69.3377

80.86

Khush.jpg

0.07840

22.1136

0.993

100.606

0.125

Book.jpg

0.00247

52.1416

1.132

88.3273

3.313

Table 3. Results using FHT

IMAGE

FHT

RMSE

PSNR

(db)

CR

DENSITY (%age)

TIME

(Sec)

Strawbery.jpg

0.00282

50.9713

1.035

96.5414

0.969

Lady.tif

0.05265

25.5713

1.035

96.5843

0.969

Large.jpg

0.00755

42.4296

1.487

67.2189

15.87

Khush.jpg

0.07840

22.1136

0.996

100.372

0.047

Book.jpg

0.00247

52.1416

1.169

85.5099

0.969

Table 4. Results using In-Place MFHWT

IMAGE

In Place MFHWT

RMSE

PSNR

(db)

CR

DENSITY (%age)

TIME

(Sec)

Strawbery.jpg

0.00282

50.9713

1.035

96.5716

0.687

Lady.tif

0.05265

25.5713

1.035

96.5881

0.64

Large.jpg

0.00755

42.4296

1.487

67.233

10.46

Khush.jpg

0.07840

22.1136

0.996

100.372

0.032

Book.jpg

0.00247

52.1416

1.169

85.526

0.687

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.