In many cases, when working with noisy images we need to compress the image as well as filter it from noise.
Abstract
In many cases, when working with noisy images we need to compress the image as well as filter it from noise. The idea behind this project is the implementation of an algorithm that achieves both goals at the same time. The algorithm implemented in this project is an adaptive one, meaning that its method of operation changes during the processing of the image. The processed image is divided into several parts (blocks) and for each part the best algorithm among a given set of algorithms (schemes) is chosen.
In the first part of the project we deal with images without noise and we implement a compression algorithm (with no filtering), using scalar quantizers and DPCM-based schemes. In the second part, the case of a noisy image is treated and a solution of simultaneous filtering and compression is presented, using DPCM-based schemes.
The project was implemented in the MATLAB environment.
Introduction
In many applications, the problem of planning a system, which operates on images, the statistical description of which is unknown, is encountered in this case it is quite clear that if a fixed, non-adaptive algorithm is used, it would work well for images with certain values’ distribution, but not for images with other distributions. This is where the idea of creating an adaptive algorithm, which fits itself to the image in order to improve the system performance, comes from. The algorithm tries to learn the image and chooses the best performing scheme from the given set of schemes (different schemes will be the best for different images).
The images in this project are considered as individual images.
Another aspect of choosing the schemes for the project is the lack of future memory and the final memory of the past in encoding and decoding of the image. Therefore, the chosen schemes are scalar quantizer schemes (lack of memory to the past), and DPCM-based schemes (see the explanation which follows).
Another issue we mention here is the way of choosing images – the images that were chosen for checking the algorithm, are gray scale ones, they are relatively small, and therefore the long delay of the algorithm will be prevented. In addition, the algorithm (which has to work for every picture) has been checked on a number of images in order not to reach perfect results only for images of a certain type.
Algorithm Overview
We will start with the algorithm pertaining to the noise-free environment. We suppose that every pixel in the image is presented by ‘B’ bits, and we want to compress the image so that every pixel will be transmitted in the channel presented by ‘R’ bits per pixel (compression ratio of B/R).
In order to compress, as the first step we will scan the image to the one-dimensional vector. There are many kinds of scans, but for the simplicity of the project we will use the row stack scanning.
The scanned vector will pass through encoder, which will perform a local action for every pixel on a vector (by using the pixel itself and number of pixels before it) and will create a scalar of ‘R’ bits, which will present this pixel. This scalar will be transmitted in the channel to the decoder’s side.
At the decoder’s side, the reverse action on the received scalar will be performed: this scalar will pass through decoder that will bring us back to the one-dimensional vector with the members that are presented by ‘B’ bits. For this vector we will perform reverse scanning and obtain the restored image.
The system compressing transmitting and decoding the image
Now, when we have the original and the restored pictures, we can define the algorithm performance according to the sum of errors between the pixels of two images. This error can be defined, for example by the criteria of square difference (square error) or absolute difference. In this project we will use the criteria of square error.
Algorithm overview in the noisy environment
The principle underlying the operation of the algorithm here is similar to the one in the noise-free environment. The main difference is that the noise with a known statistical description is added to the original image (in this project the noise consists of independent and identically distributed components, so that it could be described by one matrix of passing probabilities in X*X size, when X = 2B is the size of the image alphabet), and in addition to compressing during the encoding, the algorithm performs filtering of noise during decoding.
The main problem of the adaptive algorithm mentioned, is that the performance of schemes from the set, that we compete with, is unknown. Since we do not have the original noise-free image, we have to estimate the performance of every scheme in the set according to the original noise-free image (the estimation will be performed based on the observed noisy sequence and the probability matrix of the noise).
The system compressing transmitting and decoding the image with filtering
Description of the scalar quantizer
Scalar quntization is an example of a number presented by ‘B’ bits by another number presented by ‘R’ when B > R. In other words, we map 2B levels of values that we have at the input to the quantizer to 2R levels in the exit from it atits output.
Reverse quantization description
At the input to the reverse quantization module we have a number presented by ‘R’ bits (2R levels) and that number will be transformed to the number presented by ‘B’ bits at the exit.
The scalar quantization system
While X is the pixel’s value at the entrance, Y – pixel’s value after quantization – the transmitted value, Xr – restored pixel’s value.
DPCM (differential pulse coded modulation) description
In contrast to the scalar quantizer, which compresses the image by encoding every pixel separately, the DPCM algorithm uses the built-in dependence which exists between neighboring pixels in the image. The idea is to predict the discussed pixel from those pixels, to calculate the prediction error and to transmit only this error after its quantization. For this matter we have to save at the encoder the values of the pixels, which have been treated earlier (as well as in decoder as will be seen later), while for the prevention of the dragged error from early treated pixels, the saved values are not of the original pixels, but of their restored values exactly like we got from the decoder.
Therefore, the encoder includes the decoder.
Although, the prediction action can be general, in this project we use linear predictors only. This kind of predictor in case of DPCM (like we have in our project) is one-dimensional and easy to be defined by a vector of weights whose dimension is as the number of pixels, taking part in prediction. Every pixel is multiplied by the suitable weight and the sum of results is subtracted from the discussed pixel for receiving the prediction error.
Even though in our project the DPCM – based algorithm deals with one-dimensional vectors, we have to remember that this vector is the result of scanning the image that, of-course, is two-dimensional. We would like to use the property of a potential place locality, therefore we will predict every pixel based on the neighboring pixels that we have. We will, therefore, predict every pixel based on the pixel on its left and on three pixels above it (they are all pixels from the discussed pixel’s neighborhood that the encoder already has).
Of-course, there are exceptions in such cases when we do not have all four mentioned pixels, since the pixels from the first row or the first and the last columns are meant. In those cases we will calculate the predictor on basis of those pixels we have:
- In case of the pixels from the first row (beginning with the second one and on) the predictor will be the last pixel received in the encoder
- In case of the pixels from the first column (beginning with the second one and forward) the predictor will be calculated on the basis of two pixels above the discussed pixel
- In case of the pixels from the last column (beginning with the second one and on) the predictor will be calculated on basis of three pixels: one from the discussed pixel’s left and two above it
- The exceptional case is the one of the first pixel in the image when we have to perform scalar quantization only in order to predict it (DPCM with 0 memory to the past it is actually the scalar quantizer)
iDPCM (the inverse DPCM) description
At the input to the iDPCM module we get the prediction error for the discussed pixel. This error will go through inverse quantization, and for getting the restored value of the pixel we will add the predictor of this pixel to this error.
As it was mentioned earlier, our predictor is linear, therefore we will just add the sum of restored pixels’ values multiplied by weights (exactly according to the same weights vector that we used for DPCM) to this error.
A DPCM system
While X is the pixel’s value at the entrance, Xp – predicted pixel’s value, E –prediction error before quantization, Y – prediction error after quantization – the transmitted value, Er – reconstructed prediction error, Xr – restored pixel’s value.
Results
For the noisy-free environment
We performed our adaptive algorithm running for the set of scalar quantizers schemes, and for the set of DPCM – based schemes for the number of representing images. We will measure the prediction error by distortion (that will be defined by general error for the pixel in an image for the criteria of square error – we will divide general error on number of pixels and perform square root operation on the result).
We will define eta = 0.000001 for all the experiments.
We have performed several runnings for the quantizer and DPCM systems in various parameters combinations.
On the following figures you can see some images, while first one is original, the second one is the output of the scalar quantization system, and the third one is the output of the DPCM – based system.
For the noisy-free environment.
We performed our adaptive algorithm running for the set of scalar quantizers schemes, and for the set of DPCM – based schemes for the number of representing images. We will measure the prediction error by distortion (that will be defined by general error for the pixel in an image for the criteria of square error – we will divide general error on number of pixels and perform square root operation on the result).
We will define eta = 0.000001 for all the experiments.
We have performed several runnings for the quantizer and DPCM systems in various parameters combinations.
On the following figures you can see some images, while first one is original, the second one is the output of the scalar quantization system, and the third one is the output of the DPCM – based system.
- Lena – The original image
Lena – Restored by quantizer Lena – Restored by DPCM
Lyn – The original image
Lyn – Restored by quantizer Lyn – Restored by DPCM
For the noisy environment
We ran the algorithm only twice in the noisy environment, because the algorithm, which was implemented in MATLAB environment, is too complicated and its running time is too long. The algorithm was checked on two small images: ‘test’ and ‘test2’.
These are the results:
test: the left image – the original image;
The middle image is the noisy-corrupted image;
The right image is the restored image
test2: the left image – the original image;
The middle image is the noisy-corrupted image;
The right image is the restored image
From these results we can see that the algorithm filters most of the noise from the noisy image.
Audio signals processing in noise-free environment by DPCM
It is possible to run our algorithm on audio signals exactly in the same way as it was done on images after scanning them to the one-dimensional vector. All stages of the algorithm are the same beginning from the scanning (scanning does not exist).
The algorithm was checked on three representative audio signals:
- Speech signal (speech)
- Music signal (music)
- Sound (siren)
In order to use the same DPCM environment we constructed for the images on the audio signals we transform the audio samples values to the range 0 – 255 and we quantize them to 8 bits per sample.
It can be seen from the graphical results or by listening to the original and the restored signals that our algorithm restores the compressed audio signals.
If we use the square error criteria to quantify the algorithm’s distortion we get the following results on the scale of 0 – 255:
- Speech signal (speech) – 3.53
- Music signal (music) – 3.84
- Sound (siren) – 4.28
As we can see the DPCM algorithm achieves smaller distortions in this case than for images.
The results are the following:
speech: the original image speech: the restored image
music: the original image music: the restored image
siren: the original image siren: the restored image
Acknowledgement
We would like to thank Tsachy Weissman for supervising this project. Our acknowledgement goes also to the VISL laboratory staff and the Ollendorff Minverva Center for their support.