Why is compression used
Simple maths states that images represent very large arrays (pixels x bits x RBG x time (video)) - this represents a lot of memory.
Computers and in particular mobile phones have limited space.
the main reason why compression works
Reduncancy - not all pixel values are equal, some are repeated or not even used. in flat images we may not care about the accuracy of the pixel values
Name one of the main benefits of compression
It works across multiple devices. This is because standards are used: such as JPEG or MPEG.
Describe at a very high level the process for a compression an algorithm
Input -> Encode -> Decoder -> output
Describe the process of an encoder
- an image in deconstructed into sub images.
- forward transform is performed.
- Quantisation is performed.
- symbol encoder
Describe the process of a decoder
- Symbol decoder
- Inverse transform
- Merge sub-images together into a final compressed image.
- Compressed image outputted.
How is a histogram used in image compression
To calculate the amount of times a given grey scale of all of the pixels is used
Key points for encoding grey values
- Find the most common grey values.
2 calculate the most individual probabilities of all of the grey values. - this are your symbols.
Define symbol
The grey scale value for a given pixel or set of pixels
Describe a simple 5 part symbol encoder algorithm
- Create a histogram of all of the grey values
- use the histogram to calculate the probabilities - these are the symbols.
- order the symbols in order of there frequency
- give short binary values to the most common values
- repeat for all values
what does Huffman coding do?
it uses a probabilistic tree method to calculate how to assign bits to symbols such that it will produce the lowest average bit rate per a symbol.
Describe the 6 parts to the Huffman coding algorithm
- calculate the probabilities of each symbol occurring and order them from highest to lowest
- take the two lowest probablities and add the together to create a new “source reduction” or iteration of the list of symbols
- Reorder the probablities and repeat step 2 until just two symbols remain.
- start with the last iteration and work backwards, placing bits next to each number. -
- Each time proablilites were added - split the bits up into two.
- follow this all the way back to the beginning - you will then have bits for every symbol.
Key parts of why huffman works
- each symbol has unique bits
- This is mathematically the shortest way of calculating how to assign the bits
3.
