Image Quantization with quantums Algorithm question

Question

I came across a question and unable to find a feasible solution.

Image Quantization

Given a grayscale mage, each pixels color range from (0 to 255), compress the range of values to a given number of quantum values.

The goal is to do that with the minimum sum of costs needed, the cost of a pixel is defined as the absolute difference between its color and the closest quantum value for it.

Example

There are 3 rows 3 columns, image [[7,2,8], [8,2,3], [9,8 255]] quantums = 3 number of quantum values.The optimal quantum values are (2,8,255) Leading to the minimum sum of costs |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

Function description

Complete the solve function provided in the editor. This function takes the following 4 parameters and returns the minimum sum of costs.

n Represents the number of rows in the image

m Represents the number of columns in the image

image Represents the image

quantums Represents the number of quantum values.

Output: Print a single integer the minimum sum of costs/

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

Explanation

The optimum quantum values are {0,1,2,3,4,5,7,8,9,255} Leading the minimum sum of costs |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

can anyone help me to reach the solution ?

Answer 1

Clearly if we have as many or more quantums available than distinct pixels, we can return 0 as we set at least enough quantums to each equal one distinct pixel. Now consider setting the quantum at the lowest number of the sorted, grouped list.

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

[(2, 2), (3, 1), (7, 1), (8, 3), (9, 1), (255, 1)]
 2

We record the required sum of differences:

0 + 0 + 1 + 5 + 6 + 6 + 6 + 7 + 253 = 284

Now to update by incrementing the quantum by 1, we observe that we have a movement of 1 per element so all we need is the count of affected elements.

Incremenet 2 to 3

3
1 + 1 + 0 + 4 + 5 + 5 + 5 + 6 + 252 = 279

or

284 + 2 * 1 - 7 * 1
= 284 + 2 - 7
= 279

Consider traversing from the left with a single quantum, calculating only the effect on pixels in the sorted, grouped list that are on the left side of the quantum value.

To only update the left side when adding a quantum, we have:

left[k][q] = min(left[k-1][p] + effect(A, p, q))

where effect is the effect on the elements in A (the sorted, grouped list) as we reduce p incrementally and update the effect on the pixels in the range, [p, q] according to whether they are closer to p or q. As we increase q for each round of k, we can keep the relevant place in the sorted, grouped pixel list with a pointer that moves incrementally.

If we have a solution for

left[k][q]

where it is the best for pixels on the left side of q when including k quantums with the rightmost quantum set as the number q, then the complete candidate solution would be given by:

left[k][q] + effect(A, q, list_end)
  where there is no quantum between q and list_end

Time complexity would be O(n + k * q * q) = O(n + quantums ^ 3), where n is the number of elements in the input matrix.

Python code:

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

Output:

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

Answer 2

I would propose the following:

step 0

Input is:

image = 7 2 8
        8 2 3
        9 8 255

quantums = 3 

step 1

Then you can calculate histogram from the input image. Since your image is grayscale, it can contain only values from 0-255.

It means that your histogram array has length equal to 256.

hist = int[256]                    // init the histogram array
for each pixel color in image      // iterate over image 
   hist[color]++                   // and increment histogram values


hist:
value  0 0 2 1 0 0 0 1 2 1 0    . . .      1
---------------------------------------------
color  0 1 2 3 4 5 6 7 8 9 10   . . .     255  

How to read the histogram:

color 3 has 1 occurrence
color 8 has 2 occurrences

With tis approach, we have reduced our problem from N (amount of pixels) to 256 (histogram size). Time complexity of this step is O(N)

step 2

Once we have histogram in place, we can calculate its # of quantums local maximums. In our case, we can calculate 3 local maximums. For the sake of simplicity, I will not write the pseudo code, there are numerous examples on internet. Just google ('find local maximum/extrema in array' It is important that you end up with 3 biggest local maximums. In our case it is:

hist:
value  0 0 2 1 0 0 0 1 2 1 0    . . .      1
---------------------------------------------
color  0 1 2 3 4 5 6 7 8 9 10   . . .     255 
           ^           ^                   ^  

These values (2, 8, 266) are your tops of the mountains.

Time complexity of this step is O(quantums) I could explain why it is not O(1) or O(256), since you can find local maximums in a single pass. If needed I will add a comment.

step 3

Once you have your tops of the mountains, you want to isolate each mountain in a way that it has the maximum possible surface.

So, you will do that by finding the minimum value between two tops In our case it is:

value  0 0 2 1 0 0 0 1 2 1 0    . . .      1
---------------------------------------------
color  0 1 2 3 4 5 6 7 8 9 10   . . .     255
           ^           ^  
          |  \       /   \                        
       - -      _ _ _       _     . . .   _ ^                                                           

So our goal is to find between index values:

from 0 to 2     (not needed, first mountain start from beginning)
from 2 to 8     (to see where first mountain ends, and second one starts)
from 8 to 255   (to see where second one ends, and third starts)
from 255 to end (just noted, also not needed, last mountain always reaches the end)

There are multiple candidates (multiple zeros), and it is not important which one you choose for minimum. Final surface of the mountain is always the same.

Let's say that our algorithm return two minimums. We will use them in next step.

min_1_2 = 6
min_2_3 = 254

Time complexity of this step is O(256). You need just a single pass over histogram to calculate all minimums (actually you will do multiple smaller iterations, but in total you visit each element only once.

Someone could consider this as O(1)

Step 4

Calculate the median of each mountain. This can be the tricky one. Why? Because we want to calculate the median using the original values (colors) and not counters (occurrences).

There is also the formula that can give us good estimate, and this one can be performed quite fast (looking only at histogram values) (https://medium.com/analytics-vidhya/descriptive-statistics-iii-c36ecb06a9ae)

If that is not precise enough, then the only option is to "unwrap" the calculated values. Then, we could sort these "raw" pixels and easily find the median.

In our case, those medians are 2, 8, 255

Time complexity of this step is O(nlogn) if we have to sort the whole original image. If approximation works fine, then time complexity of this step is almost the constant.

step 5

This is final step.

You now know the start and end of the "mountain". You also know the median that belongs to that "mountain"

Again, you can iterate over each mountain and calculate the DIFF.

diff = 0
median_1 = 2
median_2 = 8
median_3 = 255
for each hist value (color, count) between START and END      // for first mountain -> START = 0, END = 6
                                                              // for second mountain -> START = 6, END = 254
                                                              // for third mountain -> START = 254, END = 255            
   diff = diff + |color - median_X| * count

Time complexity of this step is again O(256), and it can be considered as constant time O(1)