Collective Interview Question
Country: India
Use run length encoding by compressing similar bytes. Compare byte by byte data for similar bytes first record the byte then number of times the byte is repeated. If you are. Using byte compression, the maximum number limit will be 255. If you encounter this situation write the Same byte again and then the number of bytes following it until you encounter different byte. In worst case scenario none of the adjacent byte is repeated then In that case don't write the count just copy byte as is. The worst case will be that you will achieve no compression else you will achieve some compression, how much compression will be achieved will be dependent on the image. But this way will guarantee you a lossless compression.
There are other compression techniques that you can use. Most common one used is LZMA which is dictionary compression, but is harder to implement. But using LZMA will guarantee you the best compression.
LZMA doesn't guarantee the best possible compression.
in your first paragraph, if you don't put the count when none of the adjacent bytes are repeated, how will you later determine whether 11 10 encodes a pixel whose value is 11 and then a second pixel whose value is 10, or 10 pixels all of whose values are 11?
Usually, image compression is done in a lossy way, meaning information is lost during the compression process. Formats that do lossy compression, such as JPEG, retain the information that is in some sense most critical to the overall visual perception of the image and lose details that contribute less. Huge space savings are often attained this way.
There are also formats that are lossless, meaning that you can recover the exact, unaltered original from the compressed version. These usually also exploit certain properties that are frequently true about image data. For example, adjacent pixels often have similar colors, so to take a very simple scheme as an example, you could store an image as a series of mostly small numbers indicating the change in the color from one pixel to the next. Suppose you have a row of pixels whose values are 123 125 124. You can compress this by writing the values as 123 2 -1. 2 and -1 require fewer bits to represent than 125 and 124. This example is just a very simple compression scheme and more complicated schemes are possible.
Even with no special image properties to exploit, you can halve the use of space because the image in this question only has 16 colors. If a pixel can have one of 16 colors, it can be represented with 4 bits per pixel (since there are 16 different possible sequences of 0 and 1 of length 4). However, we're told in the problem that the image is presently represented with 1 byte (8 bits) per pixel instead. We can re-encode the image to use 4 bits per pixel to halve the space usage.
First translate the 8 bit to 4 bit since it only 16 colors. Then if he needs lossless, try zip.
- chenlc626 February 28, 2013