小黑算法成长日记9：基于动态规划灰度值分段存储的图像压缩算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
p = [10,12,15,255,1,2]    #像素点灰度值数组
def length(value):    #计算像素点灰度值的存储位数（相当于log取整）
    i = 0
    while value != 0:
        i += 1
        value = (int)(value / 2)
    return i
def Compress(p,header):    #动态规划计算出最优分段(即分段后图像存储花费内存空间最小)
    LMax = 256    #规定的最大段长
    P = p[:]    #像素点灰度值的克隆(规范操作)
    P.insert(0,0)    #为了后续算法实现的方便，使索引从1开始
    n = len(p)    #像素点个数
    b = [0]    #像素点位数数组，在首位置插入0是索引从1开始
    s = [0] * (n+1)    #记录存储空间的动态规划最优分段数组s
    l = [0] * (n+1)    #记录分段长度的动态规划最优分段数组l
    for i in range(1,n+1):    #动态规划开始
        b.insert(i,length(P[i]))
        bmax = b[i]
        s[i] = s[i-1] + bmax    #初始化s[i]与l[i]
        l[i] = 1
        for j in range(2,i+1):    #从第i个元素开始依次向前将p[i-j+1,i]合并为一段，通过j的累加，比较并选择出最优的划分
            if j > LMax:
                break
            if b[i-j+1] > bmax:    #以本段元素中最大的位数为本段每个元素的存储位数
                bmax = b[i-j+1]
            temp = s[i-j] + bmax * j
            if temp < s[i]:    #记录最优值和段长
                s[i] = temp
                l[i] = j
        s[i] += header    #段头信息所消耗的存储空间
    print('记录存储空间的动态规划最优分段数组s：',s)
    print('记录分段长度的动态规划最优分段数组l:',l)
    print('最优的存储空间大小为:',s[n])
    return s,l,b
def trace(b,l):    #倒序追踪分段信息
    back = []
    t = len(b) - 1
    while t != 0:
        back.append((l[t],b[t]))
        t -= l[t]
    k = 1    #段的编号
    for i in range(len(back)-1,-1,-1):
        print('第',k,'段的元素个数为:',back[i][0],',存储单元的位数为:',back[i][1])
        k += 1
print('像素点灰度值数组:',p)
s,l,b = Compress(p,11)
trace(b,l)