Data Compression Lec#10-2018

OR-ing Bits
This method starts with a sparse string L1 of size n1 bits. In the first step, L1 is divided into k substrings of equal size. In each substring all bits are logically OR-ed, and the results (one bit per substring) become string L2, which will be compressed in step 2. All zero substrings of L1 are now deleted. Here is an example of a sparse, 64-bit string L1, which we divide into 16 substrings of size 4 each:
L1 = 0000|0000|0000|0100|0000|0000|0000|1000|0000
|0000|0000|0000|0010|0000|0000|0000.
After ORing each 4-bit substring we get the 16-bit string L2 = 0001|0001|0000|1000.
In step 2, the same process is applied to L2, and the result is the 4-bit string
L3 = 1101, which is short enough so no more compression steps are needed. After deleting all zero substrings in L1 and L2, we end up with the three short strings
L1 = 0100|1000|0010, L2 = 0001|0001|1000, L3 = 1101.
The output stream consists of seven 4-bit substrings instead of the original 16! (A few more numbers are needed, to indicate how long each substring is.) The decoder works differently (this is an asymmetric compression method). It starts with L3 and considers each of its 1-bits a pointer to a substring of L2 and each of its 0-bits a pointer to a substring of all zeros that is not stored in L2. This way string L2 can be reconstructed from L3, and string L1, in turn, from L2. Figure 8.21 illustrates this process. The substrings shown in square brackets are the ones not contained in the compressed stream.
This method becomes highly inefficient for strings that are not sparse, and may easily result in expansion. We analyze the worst case, where every group of L1 is nonzero. All n1 bits of string L1 need be written on the output stream. This already shows that there is going to be no compression. String L2 consists of n1/k 1’s, so all of it has to be written on the output stream. String L3 similarly consists of n1/k2 1’s, and so on. The size of the output stream is thus
















Block Truncation Coding
Block Truncation Coding, or BTC, is a type of lossy image compression technique for greyscale images. It divides the original images into blocks and then uses quantize to reduce the number of grey levels in each block whilst maintaining the same mean and standard deviation. BTC has also been adapted to video compression
BTC was first proposed by Professors Mitchell and Delp at Purdue University. Another variation of BTC is Absolute Moment Block Truncation Coding or AMBTC, in which instead of using the standard deviation the first absolute moment is preserved along with the mean. AMBTC is computationally simpler than BTC. AMBTC was proposed by Lema and Mitchell.
Sub blocks of 4x4 pixels allow compression of about 25% assuming 8-bit integer values are used during transmission or storage. Larger blocks allow greater compression ("a" and "b" values spread over more pixels) however quality also reduces with the increase in block size due to the nature of the algorithm.
Compression procedure
A 256x256 pixel image is divided into blocks of typically 4x4 pixels. For each block the Mean and Standard Deviation are calculated, these values change from block to block. These two values define what values the reconstructed or new block will have, in other words the blocks of the BTC compressed image will all have the same mean and standard deviation of the original image. A two level quantization on the block