图像量化算法问题：给定量子值数量求解最小总代价

解法思路 #

灰度值取值范围仅为0~255，数值范围极小，所以可以基于区间动态规划求解，时间复杂度完全可控。 #

具体实现步骤 #

1. 统计灰度频率
   不需要保留原始图像的二维结构，只需要统计每个灰度值（0~255）出现的次数即可，相同灰度值的代价计算方式完全一致，统计后可以大幅降低计算量。
2. 预处理区间代价矩阵
   定义cost[l][r]为将所有灰度值在[l, r]区间内的像素分配到同一个量子值的最小总代价。对于任意区间，最小代价出现在量子值取区间的加权中位数（权重为对应灰度的出现次数）时，也可以直接暴力枚举区间内的所有可能量子值计算最小代价，因为区间最大长度仅256，计算成本极低。
3. 动态规划求解最优解
   定义dp[i][j]为覆盖0~i的所有灰度值，使用j个量子的最小总代价：

• 边界条件：dp[i][1] = cost[0][i]，即只用1个量子覆盖0~i所有灰度的最小代价就是区间[0,i]的最小代价
• 转移方程：dp[i][j] = min(dp[k][j-1] + cost[k+1][i])，其中k的取值范围是[j-2, i-1]，表示前k个灰度用j-1个量子覆盖，剩下的k+1~i用第j个量子覆盖
• 最终结果：dp[255][quantums]，就是覆盖所有0~255灰度，用指定数量量子的最小总代价

额外剪枝：如果允许的量子数量大于等于图像中不同灰度值的数量，或者quantums>=256，直接返回0，此时可以给每个存在的灰度值分配一个专属量子，总代价为0。 #

代码实现 #

def solve(n, m, image, quantums):
    # 统计每个灰度的出现频率
    freq = [0] * 256
    for row in image:
        for val in row:
            freq[val] += 1
    
    # 特殊情况剪枝：量子数足够覆盖所有可能灰度，代价为0
    if quantums >= 256:
        return 0
    # 统计不同灰度的数量，如果量子数大于等于它也直接返回0
    distinct = sum(1 for x in freq if x > 0)
    if quantums >= distinct:
        return 0
    
    # 预处理cost[l][r]: 区间[l,r]用一个量子的最小代价
    cost = [[0]*256 for _ in range(256)]
    for l in range(256):
        for r in range(l, 256):
            min_c = float('inf')
            # 枚举这个区间的量子值q，找最小代价
            for q in range(l, r+1):
                cur = 0
                for v in range(l, r+1):
                    cur += freq[v] * abs(v - q)
                if cur < min_c:
                    min_c = cur
            cost[l][r] = min_c
    
    # 动态规划初始化
    INF = float('inf')
    dp = [[INF]*(quantums+1) for _ in range(256)]
    # 边界：j=1的情况
    for i in range(256):
        dp[i][1] = cost[0][i]
    
    # 填充dp表
    for j in range(2, quantums+1):
        # j个量子至少要覆盖j个灰度，所以i从j-1开始
        for i in range(j-1, 256):
            # k至少是j-2：前k个用j-1个量子，至少需要j-1个灰度，k >= (j-1)-1 = j-2
            for k in range(j-2, i):
                if dp[k][j-1] + cost[k+1][i] < dp[i][j]:
                    dp[i][j] = dp[k][j-1] + cost[k+1][i]
    
    return dp[255][quantums]

# 测试用例
if __name__ == "__main__":
    image = [[7,2,8], [8,2,3], [9,8,255]]
    print(solve(3,3,image,3))  # 输出3
    print(solve(3,3,image,10)) # 输出0

内容的提问来源于stack exchange，提问作者Pankaj Sharma