|
动态规划---图像压缩
问题描述分析代码如下运行结果如下结果一结果二
在算法课上遇到这个图像压缩这个问题，可以用
动态规划来求解，之前没有遇到过这个问题，在网上查找相关的题解也比较少，就写一下自己的理解。
问题描述
一幅图像的由很多个像素点构成，像素点越多分辨率越高，像素的灰度值范围为0~255，
也就是需要8bit来存储一个像素的灰度值信息。
一幅由n*m像素点构成的图像，所需存储空间大小为：n*m*8bit=8nmbit(这是非常大的，直接传输很慢)
然而，正常情况下，一幅图像的某一范围内像素点的灰度值是很接近的，表现为一幅图片某一区域颜色相近。
例如，一个像素灰度值序列P={1,2,2,2,1,2,60,55,78}(传输过程中把图像像素点转成序列，
而不是直接传输矩阵)，每个像素灰度值都用8bit来存储是非常消耗空间的，例如：
直接存储: 9*8bit=72bit，这是非常不划算的，我们想要无损压缩图片。
即：
将像素序列分段，段内的像素灰度值相似(可以用小于8bit的空间来存储一个像素灰度值)，
一段内的像素用相同的bit数来存储，只需要额外存树每段的长度和bit数即可，这样可以节省很多空间。
b[i]:第i段中每个像素的位数，1 |