Wavelet Based Compression Question

The following link uses "wcompress" function for wavelet-based compression:

http://www.mathworks.com/help/wavelet/ref/wcompress.html

I tried the following commands, which are already an example in the previous link

[cr,bpp] = wcompress('c',X,'mask.wtc','spiht','maxloop',12);

Xc = wcompress('u','mask.wtc');
whos X
whos Xc

The results are:

 Name        Size              Bytes  Class     

X         256x256            524288  double  

 Name        Size              Bytes  Class     

Xc        256x256            524288  double

How the two images X(original) and Xc(compressed) have the same number of bytes?

Thanks

Answer 1

[Walter Roberson]

Xc is not the compressed image, the compressed image is stored in the file you named mask.wtc . Xc is the decompressed version of mask.wtc . The 'u' as the first parameter of wcompress() means "uncompress".

[Hana Elenany]

But if you looked at the images displayed, you will see that Xc is displayed as the compressed image. Anyway, I have considered mask.wtc as the compressed one and used the first attached file to read the image, transform it to binary for transmission over a channel, and finally decompresses it. It is working successfully. I want now to simulate the effect of channel noise on the compressed compression, so I have created the second attached file. When I runned it, the following error appeared: Undefined function or variable "TabCODE".

Error in modify_wtcfile (line 86) fwrite(fid,TabCODE,'ubit1');

Error in wtcmngr (line 121) methodCOMP = modify_wtcfile('load',filename);

Error in wtcmngr (line 94) [WTC_Struct,methodCOMP] = wtcmngr('load',New_filename);

Error in wcompress (line 459) X_decoded = wtcmngr('read',inputFile,stepFLAG);

Error in wcomp (line 17) m=wcompress('u','mask.wtc'); %decompress the image

Could you plz help me?

[Walter Roberson]

The documentation is misleading. Where it says "Compressed image" in the image titles, it should be something like "Reconstructed Compressed Image"

[Walter Roberson]

TabCODE appears to be internal to the Wavelet Toolbox, which I do not have. It might be a bug in the toolbox; I cannot look at it to evaluate the cause.

[Hana Elenany]

Thanks. How can I find the size (in bytes) of a compressed image to compare it to the original size of the image? Shall I use "whos" function applied on the image arrays? Shall I use "iminfo" on the images after using imwrite? Is there a difference between reading the size of an image stored on windows than on matlab? I need explanation plz because the results are different

[Walter Roberson]

dinfo = dir('mask.wtc');
filesize = dinfo(1).bytes;

This will return the size as stored on disk, the size of the file.

The Xc image array is the reconstructed image based upon the mask.wtc file, and will occupy as much memory after reconstruction as the original image took.

[Hana Elenany]

Thanks. This works successfully for mask.wtc. How can I generalize it to find the size of any file stored on the disk? When I replace mask.wtc with X or Xc, an error appears:??? Index exceeds matrix dimensions.

[Walter Roberson]

X and Xc are not files stored on disk. And you need to pass a string that is a file name.

[Hana Elenany]

How to compute the size of the original image as stored on disk? I need to know this to compare it to the compressed image size

[Walter Roberson]

If you are looking at example 3 of the link you indicated, then the load X from the file mask.mat . You could use dir() to find the size of mask.mat but remember that there is overhead to represent the image inside a .mat file, to store information about its data type, size, name, and so on; there may also be additional variables stored in the .mat. The .mat might also use its own compression. The size of the .mat is probably not what you should be looking for.

You should be looking at the size to represent X in memory, which you can find using whos.

stats = whos('X');
stats(1).bytes

Note: looking at the size in memory only works if what is in memory is the same information that is stored on disk. This is not always the case. In particular, for audio files, even the ones that are not compressed on disk (and most audio is compressed), the audio reading routines automatically convert the stored information into the range -1 <= x < 1 because that is the most commonly used audio form. The audio might only have, for example, 12 bits of information per sample, but the audio read routines would normally expand that to 64 bits. The primary audio read routine has a 'native' option to return what is actually stored on disk.

I know you are not using audio at this time, but it is important to understand the principle, that when you are calculating compression ratios, the sizes you should be working with are based upon how much disk space would be required to "pack" the actual information as tightly as possible without using compression. For example if you were working with data that was certain to be integers in the range 0 to 63, then that is only 6 bits of information. You would not need one uint8 (8 bits) per sample to store the information on disk: you could pack four 6-bit samples (24 bits of information) into 3 uint8 (24 bits of disk) using

   11111122|22223333|33444444

[Hana Elenany]

Thanks. I tried the dir function, in most cases it is working. A final question plz: I want to convert the compressed image to a stream of ones and zeros for transmission over a channel. I use the dec2bin function in matlab. The dynamic range of the image before transmission is 0-255, thus each pixel is represented in 8 bits. If the dynamic range of the compressed image is 0-238, it will be also represented using 8 bits, thus having the same size. Could you plz help me understanding this confusion. Of course I need the size of the compressed binary image to be less than the original image.

[Walter Roberson]

If the dynamic range is 0-238 then you can use mathematical operations to pack about 107 values for every 100 bytes. Research "arithmetic coding".

[Hana Elenany]

I have built an m file (the first attached m file) which performs arithmetic coding and decoding successfully. The size in bytes after arithmetic coding is less than the original size of the image. The problem now is that when I tried to change the value of only one bit after coding (the second attached file)to simulate the effect of noise, I could not reconstruct the image, could you plz help me?

[Walter Roberson]

Compression is the process of removing redundancy. If you remove all discernible redundancy then a single bit change would result in reconstructing different data. If you are using variable number of bits per symbol (such as for Huffman or arithmetic encoding) then a single bit change means that you might not be able to recover the same size of data even.

Protecting against errors involves adding error detection and recovery. There are theorems that show that if your error detection is as efficient as possible and your compression is as efficient as possible, then you should compress first and apply error correction coding techniques to the result.

[Hana Elenany]

This means that an error detection and correction technique must correct all errors, I think this is not logic. I read papers on transmitting compressed images over wireless channels, and the bit error rate is calculated under different values of channel S/N. The error for large values of S/N may be absolutely zero, but of course for other lower values of S/N, there will be a value for BER, may be small but not exactly zero.

[Walter Roberson]

Error detection and correction have a maximum amount of correction that they can apply, and can usually detect roughly 1.5 to 2 times as many errors as they can fix. If there are more errors than can be detected then the transmitted data accidentally looks like it is valid, at least at that level.

Wireless TCP can request retransmission of data if it detects an error at any level.

Wireless UDP cannot request retransmission, but since by definition UDP packets can be lost or discarded or arrive out of order, protocols that rely upon UDP are designed to discard the entire packet if it has more errors then can be corrected, with the application designed to not expect to receive all of the data.

If you are working on an application such as transmission from space probes then they layer on some heavy error detection and correction and they transmit holding bits at a steady value for a multiple of many bit times so that short bursts are ignored. (Multiple bits can be transmitted simultaneously on different low-frequency channels to achieve a higher data rate.) Space probes also are often (but not always) designed to store images until they have received acknowledgement that the image has been received successfully. The techniques are designed to lower the probability of incorrect reception, but the techniques are sometimes not designed to eliminate the possibility, since doing so might unduly slow down everything -- if you have a massive solar flare that lasts 5 days then it probably doesn't matter if you hold a bit for 1 millisecond or 100 seconds. Some noise conditions just cannot be recovered from. Breaking the antenna or turning off the equipment is equivalent to a huge sustained noise as far as theory goes.

[Hana Elenany]

If the transmitted data contains 10 bits in error, and the correction technique could correct 9 of them. The retained 1 bit in error will not enable me to reconstruct the compressed image successfully (as in the second attached file). What is the solution plz??

[Walter Roberson]

Solutions:

1. Request retransmission of the data packet that the unrecoverable error is detected in
2. design your application to be able to do something useful even if a block of data is bad, such as starting each block with a position and letting any pixels not filled be black
3. design your error correction with more redundancy
4. Or do not use a variable-length encoder, so every block of data decodes to something of fixed length that you can then put into the image (even though it might not be right)

[Hana Elenany]

This means that applying any of the above solutions will lead to BER=0, and this is not the case in the papers I read. The curve usually plotted is a relation between S/N on one axis, and the BER on the other axis. All these papers apply image compression with error detection and correction technique for wireless transmission.

[Walter Roberson]

Suppose you need 20 boards to build a house, and suppose you buy 50 boards "just in case" something goes wrong. Now suppose you accidentally break 15 of those 50 boards: no problem, that's why you bought extra, you still have 35 left and only need 20. Now suppose you accidentally break 20 of the 50: again, no problem. Suppose you accidentally break 25: again, you still have 25 and that's enough. Accidentally break 30 of the 50 boards? Wow, that's a lot of accidental damage (maybe a Safe fell out of window on to them!) but you still have the 20 you need. But if you accidentally broke 31 of the 50, you only have 19 whole boards left.

What you are demanding is that I tell you some way to build the house anyhow with only 19 boards.

But wait, maybe 40 of the 50 boards broke! So you think I should be able to tell you how to build the 20-board house with only 10 boards.

Maybe all of the 50 boards broke, so you think I should be able to tell you how to build the 20-board house with no boards.

http://www.extremetech.com/computing/138424-increasing-wireless-network-speed-by-1000-by-replacing-packets-with-algebra

"A team of researchers from MIT, Caltech, Harvard, and other universities in Europe, have devised a way of boosting the performance of wireless networks by up to 10 times [...]

In wired networks, packet loss is incredibly rare, but in wireless networks it’s one of the biggest issues affecting throughput. According to Technology Review, MIT’s WiFi networks generally lose 2% of packets — while on a fast train, packet loss is nearer 5%.

A single dropped packet causes a spike in latency — the receiver has to communicate to the sender that the packet was missing, and can’t do anything until a replacement packet has been received. If there is significant packet loss, this results in a lot of latency, a lot of re-sent data, and ultimately a low-bandwidth connection. This is why wireless adapters (WiFi, LTE, Bluetooth, etc.) negotiate the max speed of the link, as some environments (fast trains, houses with thick walls) are simply too lossy to sustain high throughput."

Thus even MIT researchers think that pocket loss (which can arise due to too much noise to recover a packet) is a major issue that generally requires retransmission. The technique described in the article does not sound like anything new: it is an obvious derivative of the idea of creating multiple "shares" of a "secret", with at least t out of k of the shares needed to reconstruct the "secret"; see https://en.wikipedia.org/wiki/Secret_sharing. The idea for the MIT technique not being to hide the data, but rather the point that if you have a block of data you can construct k packets out of which you only need to receive n in order to reconstruct the data. Just another error correcting code applied across multiple packets.

If you ever get seriously interested in compression and error coding, I highly recommend this book by Bell, Cleary, and Witten. I seem to find copies available for download, but I would have doubts about those downloads being authorized and I would be careful about the possibility of malicious payloads on unauthorized copies.