How to evenly distribute numbers 0 to n into m different containers

Question

I am trying to write an algorithm for a program to draw an even, vertical gradient across an image. I.e. I want change the pixel color from 0 to 255 along the m rows of an image, but cannot find a good generic algorithm to do so.

I've tried to implement something like this using opencv, but it does not seem to work

#include <opencv2/opencv.hpp>

int main(){

  //Make the image white.
  cv::Mat Img(w_height, w_width, CV_8U);
  for (int y = 0; y < Img.rows; y += 1) {
      for (int x = 0; x < Img.cols; x++) {
        Img.at<uchar>(y, x) = 255;//White
      }
  }

  // try to create an even, vertical gradient
  for(int row = 0; row < Img.rows; row++ ){
    for(int col = 0; col < Img.cols; col++){
      Img.at<uchar>(row, col) = col % 256;
      } 
    }
  cv::imshow("Window", Img);
  cv::waitKey(0);
  return 0;
}

Answer 1

Solving this problem requires the knowledge of three simple tricks:

1. Interpolation:

The process of gradually changing from one value to another is called interpolation. There are multiple ways of interpolating color values: the simplest one is to interpolate each component linearly, i.e. in the form of:

interpolated = start * (1-t) + dest * t.

Where

• start is the value you are interpolating from towards the value dest.
• t denotes how close the interpolated value should be to the destination value dest on a scale of 0 to 1 with 0 being the pure start color and 1 being the pure dest color.

You will find that linear interpolation in the RGB color space doesn't produce natural color paths. As an advanced step, you could utilise the HSV color space instead. See this question for further information about color interpolation.

2. Discretisation:

Unfortunately, interpolation produces real numbers. Thus, we have to discretise them to be able to use them as integer color values. The best way to do this is to round to the nearest integer by using e.g. round() in C++.

3. Finding the interpolation point:

Now, we just need a real-valued interpolation point t at each row of our image. We can deduce a formula for this by analysing what output we want to see:

• For the bottommost row (row 1) we want to have t == 0 since that is where we want our pure start color to appear.
• For the topmost row (row m) we want to have t == 1 since that is where we want the pure destination color to appear.
• For every other row we want t to scale linearly with the distance to the bottommost row.

A formula to achieve this result is:

t = rowIndex / m

The approach can readily be adapted to other gradient directions by changing this formula appropriately.

Sample code (using linear interpolation, C++):

#include <algorithm>
#include <cmath>

Color interpolateRGB(Color from, Color to, float t)
{
    // Clamp __t__ to range [0,1]
    t = std::max(std::min(0.f, t), 1.f);

    // Interpolate each RGB component
    uint8_t r = std::roundf(from.r * (1-t) + to.r * t);
    uint8_t g = std::roundf(from.g * (1-t) + to.g * t);
    uint8_t b = std::roundf(from.b * (1-t) + to.b * t);

    return Color(r, g, b);
}

void fillWithGradient(Image& img, Color from, Color to)
{
    for(size_t row = 0; row < img.numRows(); ++row)
    {
        Color value = interpolateRGB(from, to, row / (img.numRows()-1));

        // Set all pixels of this row to __value__
        for(size_t col = 0; col < img.numCols(); ++col)
        {
            img.setPixel(row, col, value);
        }
    }
}

Answer 2

The basic idea would be to use the remainder of the division r of n/(m-1) and adding it to n on each iteration:

#include <iostream>
#include <vector>
using namespace std;

vector<int> gradient( int n, int m ) {
  div_t q { 0, 0 };
  vector<int> grad(m);
  for( int i=1 ; i<m ; ++i ) {
    q = div( n + q.rem, m-1 );
    grad[i] = grad[i-1] + q.quot;
  }
  return grad;
}

int main() {
  for( int i : gradient(255,10) ) cout << i << ' ';
  cout << '\n';
  return 0;
}

Output:

0 28 56 85 113 141 170 198 226 255