基于量子算法的图像量化问题

Question

我遇到了一个问题，却找不到可行的解决办法。

图像量化

给定灰度图像，每个像素的颜色范围从(0到255)，将值的范围压缩到给定数量的量子值。

我们的目标是用所需成本的最小和，将像素的成本定义为其颜色与其最近的量子值之间的绝对差值。

示例

有3行3列，[7,2,8，8,2,3，9,8 255]量子数=3个量子values.The最优量子值为(2,8,255)，从而得到了最小的费用之和，得出最小的费用之和为:x_(7)-8~(2-2)，x~(2)+2+(2)，+(2)，2(2)，2(2)，2(2)，2(2)，2(2)，2(2)，2(2)，2(2,255)个量子最优量子值(2，8,255)，得到了最小的费用之和，得到了最小的费用之和

功能描述

完成编辑器中提供的解题功能。此函数接受以下4个参数，并返回最小的成本总和。

N表示图像中的行数。

M表示图像中的列数。

图像表示图像

量子数表示量子值的数目。

输出:打印一个整数，最小成本之和/

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}，导致了最小费用之和x_(7-7)x+x~(2-2)x+x~(8)+x~(8)+x_(8)，+(8)，(8)，8(8)，8(8)，8(2)，2(2)，2(2)，2(2)，2(2)，(2)，2(2)，2(2)，2(2)，(2)，(2)，(2)，(2)，2(2)，2(2)，2((2))，(2)，(2)，2(2)，2(2)，2(2)，(2)，(2)，(2)，(

有人能帮我找到解决办法吗？

Answer 1

显然，如果我们有许多或更多的量子比不同的像素，我们可以返回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来进行更新，我们观察到每个元素有一个移动，所以我们所需要的只是受影响元素的计数。

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是对A中的元素(排序的分组列表)的影响，因为我们逐步减少p并更新对范围内像素的影响，[p, q]根据它们是否更接近p或q。当我们为每一轮q增加k时，我们可以将相关的位置保留在排序的分组像素列表中，并使用一个指针递增地移动。

如果我们有办法

left[k][q]

对于q左侧的像素而言，如果将最右边的量子集作为q数的k量子数包括其中的最佳像素，则由以下方法给出完整的候选解决方案：

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]
]

k = 3

print(f(M, k)) # (3, [2, 8, 255])


M = [
  [7, 2, 8],
  [8, 2, 3],
  [9, 8, 255]
]

k = 10

print(f(M, k)) # (0, [2, 3, 7, 8, 9, 251, 252, 253, 254, 255])