[R05] Run length encoding results in compression by describing the data in the form of runs. 3.[R05] 行程编码通过以行程的形式描述数据而导致压缩。 • Does it always lead to compression? When would it not lead to compression? Is such cases, does the message have high entropy or low entropy? •它总是导致压缩吗 ? 何种情况下它不会导致压缩 ? 在这种情况下,消息具有高熵还是低熵 ? • Which image will result in better run length encoding among the ones shown in Figure 6-18? Assume all images are of the same size and list them in the order of best achieved compression using RLE. •如图 6-18 中所示,哪一幅图像将会有更好的行程编码 ? 假设所有图片具有相同的大小并将他们按照使用 RLE 压缩取得最佳压缩的顺序进行排序。 Figure 6 – 18 图 6 - 18 • Suppose you had a color image with each pixel represented as 24 bits— there are 2^24 possible symbols. You write a program that takes each pixel as a symbol and performs RLE to compress the sequence. Is there a more efficient way to use RLE in this case? •假设读者有一幅彩色图像每个像素表示为 24 位 --- 有 2的24次方 种可能的符号。请读者编写一个程序,将每个像素作为一个符号读取出并执行 RLE 来压缩序列。在这种情况下是否有一种使用 RLE 更有效的方式吗 ? • How does quantization affect RLE? If you were to quantize the images in Figure 6-18 before you perform RLE, would quantization help or hurt? • 量化是如何影响 RLE 的 ? 如果在执行 RLE 之前量化图 6–18 中的图像,将有助于量化还是无益于量化 ? • RLE is known to perform poorly when there is no repetition as suggested in the text. So while AAABBBCCCDDD compresses, ABCDEFGH does exactly the opposite, and AABBCDEF is the same. Suggest a scheme that would ensure a better performance irrespective of how the symbols occur. •正如课文中所述当没有重复内容时, RLE 表现不佳。所以尽管 AAABBBCCCDDD 会压缩, ABCDEFGH 则恰恰相反, AABBCDEF 同样也是如此。提出一项方案来保证更好的性能而与符号如何出现无关。 • How does your scheme perform in the best-case and worst-case scenarios? •你的方案如何在最好的和最坏的场景下运行的 ? 参考答案 1. Runlength Encoding Question · No it does not always lead to compression, if the signal is completely random where there are no runs but every symbol differs from the other, then it will not lead to compression · Assuming that you are scanning in row order for run length analysis, the order of compression from best to worst is as follows – · Yes there is, you can de-correlate the color channels RGB and treat each channel differently for runs. Normally, the variation in each channel is less than taking RGB values together. · Yes quantization does indeed help RLE – when signal samples are quantized to a fixed number of intervals (the number of intervals is almost always less than the number of input symbols), more input symbols map to the same value, reducing the entropy and thus increasing the chances of runs. This helps RLE · To ensure better performance, assume that whenever there is a run, you insert a specific symbol to show that a run exists, else if there is no run then the input remains the same. If we use a special symbol + to indicate that a run exists then ABCDEFGH -> ABCDEFGH AABBCDEF -> +2A+2BCDEF AAAAAACCCCCC -> +5A+5C · When no runs are present, input is same as output. Every run thus has three chars – a + to indicate there is a run, a number to represent length of run, and the run char. This will not be efficient if there are a lot of consecutive runs of length 2. But in general for the best and worst case of the general working of RLE, it performs much better.