如何基于灰度图像直方图选取最优压缩值以最小化总MSE

你面临的问题属于最优标量量化的经典场景，对应的成熟解决方案是Lloyd-Max量化器，完全匹配你的输入输出要求，具体说明如下：

核心最优条件 #

你要最小化总MSE的目标，天然满足两个互锁的最优约束，不需要引入复杂的argmax运算：

• 所有原始灰度值必须映射到距离它最近的目标新灰度值，两个相邻新值X_new_k和X_new_{k+1}的决策边界为两者的中点值
• 每个新值X_new_k必须是它覆盖的原始灰度区间的加权平均值，权重就是每个原始灰度对应的频次h(x)

求解步骤 #

任意直方图输入下没有通用闭式解，只有均匀分布、高斯分布等特殊分布存在闭式结果。但通用迭代解法收敛极快，且仅基于直方图运算，计算成本极低：

• 初始化M个新值：可以直接选取直方图中频次最高的M个原始灰度，也可以在灰度值域上均匀采样M个点
• 计算决策边界：取相邻两个当前新值的中点作为分界，将所有原始灰度划分到M个独立区间
• 更新新值：对每个区间计算加权平均：sum( x * h(x) for x in 区间 ) / sum( h(x) for x in 区间 )，作为该区间的新值
• 重复上述边界计算和新值更新步骤，直到所有新值的更新幅度小于预设阈值（通常1e-3即可），一般迭代10次以内即可收敛

示例验证 #

你给出的测试场景完全符合该算法的输出结果：

测试用例像素值{1,1,1,1,2,2,2,2,3,3}，对应h(1)=4、h(2)=4、h(3)=2
当M=2时，迭代后得到的最优新值为{1,2}，映射结果和你给出的最优结果一致
当M=1时，加权平均值为(14 + 24 + 3*2)/(4+4+2)=1.8，取整后为2，和你的示例结果完全匹配

内容的提问来源于stack exchange，提问作者markk borras