Pan*_*rma 13 algorithm data-structures
我遇到了一个问题，无法找到可行的解决方案。
图像量化
给定一个灰度图像，每个像素的颜色范围从（0到255），将值的范围压缩到给定数量的量子值。
目标是以最小的所需成本总和来实现这一点，像素的成本定义为其颜色与其最接近的量子值之间的绝对差。
例子
有3行3列，图像[[7,2,8],[8,2,3],[9,8 255]]量子= 3个量子值。最佳量子值为(2,8,255)导致成本总和最小|7-8| + |2-2| + |8-8| + |8-8| + |2-2| + |3-2| + |9-8| + |8-8| + |255-255| = 1+0+0+0+0+1+1+0+0 = 3
功能说明
完成编辑器中提供的求解功能。该函数采用以下 4 个参数并返回最小成本总和。
n 表示图像的行数
m 表示图像的列数
image 代表图像
Quantums 表示量子值的数量。
输出：打印单个整数成本的最小总和/
Constraints:
1<=n,m<=100
0<=image|i||j|<=255
1<=quantums<=256
Sample Input 1
3
3
7 2 8
8 2 3
9 8 255
10
Sample output 1
0
解释
最佳量子值为{0,1,2,3,4,5,7,8,9,255} 领先成本总和|7-7| + |2-2| + |8-8| + |8-8| + |2-2| + |3-3| + |9-9| + |8-8| + |255-255| = 0+0+0+0+0+0+0+0+0 = 0
谁能帮助我找到解决方案？
显然，如果我们拥有与不同像素一样多或更多的可用量子，则可以返回 0，因为我们为每个相等的不同像素设置了至少足够的量子。现在考虑将量程设置为已排序、分组列表的最低编号。
M = [
[7, 2, 8],
[8, 2, 3],
[9, 8, 255]
]
[(2, 2), (3, 1), (7, 1), (8, 3), (9, 1), (255, 1)]
2
我们记录所需的差值总和：
0 + 0 + 1 + 5 + 6 + 6 + 6 + 7 + 253 = 284
现在，通过将量程增加 1 来进行更新，我们观察到每个元素的移动量为 1，因此我们需要的只是受影响元素的计数。
增量 2 至 3
3
1 + 1 + 0 + 4 + 5 + 5 + 5 + 6 + 252 = 279
或者
284 + 2 * 1 - 7 * 1
= 284 + 2 - 7
= 279
考虑使用单个量子从左侧遍历，仅计算对位于量子值左侧的已排序分组列表中的像素的影响。
为了在添加量子时仅更新左侧，我们有：
left[k][q] = min(left[k-1][p] + effect(A, p, q))
其中是对（排序、分组列表）effect中元素的影响，当我们根据它们是否更接近或来增量减少并更新对范围内像素的影响时。随着每轮 的增加，我们可以使用增量移动的指针将相关位置保留在已排序、分组的像素列表中。Ap[p, q]pqqk
如果我们有一个解决方案
left[k][q]
q当包含k最右边量子集作为数字 的量子时，对于左侧的像素来说是最好的q，那么完整的候选解将由下式给出：
left[k][q] + effect(A, q, list_end)
where there is no quantum between q and list_end
时间复杂度为O(n + k * q * q) = O(n + quantums ^ 3)，其中n是输入矩阵中的元素数量。
Python代码：
def f(M, quantums):
pixel_freq = [0] * 256
for row in M:
for colour in row:
pixel_freq[colour] += 1
# dp[k][q] stores the best solution up
# to the qth quantum value, with
# considering the effect left of
# k quantums with the rightmost as q
dp = [[0] * 256 for _ in range(quantums + 1)]
pixel_count = pixel_freq[0]
for q in range(1, 256):
dp[1][q] = dp[1][q-1] + pixel_count
pixel_count += pixel_freq[q]
predecessor = [[None] * 256 for _ in range(quantums + 1)]
# Main iteration, where the full
# candidate includes both right and
# left effects while incrementing the
# number of quantums.
for k in range(2, quantums + 1):
for q in range(k - 1, 256):
# Adding a quantum to the right
# of the rightmost doesn't change
# the left cost already calculated
# for the rightmost.
best_left = dp[k-1][q-1]
predecessor[k][q] = q - 1
q_effect = 0
p_effect = 0
p_count = 0
for p in range(q - 2, k - 3, -1):
r_idx = p + (q - p) // 2
# When the distance between p
# and q is even, we reassign
# one pixel frequency to q
if (q - p - 1) % 2 == 0:
r_freq = pixel_freq[r_idx + 1]
q_effect += (q - r_idx - 1) * r_freq
p_count -= r_freq
p_effect -= r_freq * (r_idx - p)
# Either way, we add one pixel frequency
# to p_count and recalculate
p_count += pixel_freq[p + 1]
p_effect += p_count
effect = dp[k-1][p] + p_effect + q_effect
if effect < best_left:
best_left = effect
predecessor[k][q] = p
dp[k][q] = best_left
# Records the cost only on the right
# of the rightmost quantum
# for candidate solutions.
right_side_effect = 0
pixel_count = pixel_freq[255]
best = dp[quantums][255]
best_quantum = 255
for q in range(254, quantums-1, -1):
right_side_effect += pixel_count
pixel_count += pixel_freq[q]
candidate = dp[quantums][q] + right_side_effect
if candidate < best:
best = candidate
best_quantum = q
quantum_list = [best_quantum]
prev_quantum = best_quantum
for i in range(k, 1, -1):
prev_quantum = predecessor[i][prev_quantum]
quantum_list.append(prev_quantum)
return best, list(reversed(quantum_list))
输出：
M = [
[7, 2, 8],
[8, 2, 3],
[9, 8, 255]
]
[(2, 2), (3, 1), (7, 1), (8, 3), (9, 1), (255, 1)]
2