Issue in implementing median cut algorithm using Javascript

Question

I am trying to implement a code that picks out colors from an image and then gets a pallet of certain colors from all the colors of the image. I am trying to use the Median Cut Algorithm for implementing this.

Currently, I am following the steps for the Median Cut algorithm mentioned here:

Here's a code snippet from my POC:

const getColor = () => {
  const canvas = document.createElement('canvas');
  canvas.width = displayImage.width;
  canvas.height = displayImage.height;
  const ctx = canvas.getContext('2d');
  ctx.drawImage(displayImage, 0, 0);
  const pixelData = ctx.getImageData(0, 0, canvas.width, canvas.height).data;
  getPallete(pixelData);
};
const getPallete = (data) => {
  // data contains image data (r,g,b,a)
  if (data.length != 0) {
    for (let i = 0; i < data.length; i += 4) {
      let [red, green, blue] = [data[i], data[i + 1], data[i + 2]];

      if (red < channelProperties.minRed) {
        channelProperties.minRed = red;
      }
      if (red > channelProperties.maxRed) {
        channelProperties.maxRed = red;
      }

      // Update minimum and maximum values for green channel
      if (green < channelProperties.minGreen) {
        channelProperties.minGreen = green;
      }
      if (green > channelProperties.maxGreen) {
        channelProperties.maxGreen = green;
      }

      // Update minimum and maximum values for blue channel
      if (blue < channelProperties.minBlue) {
        channelProperties.minBlue = blue;
      }
      if (blue > channelProperties.maxBlue) {
        channelProperties.maxBlue = blue;
      }
    }
    // gets the channel with highest range
    let highestChannel = getChannel();
    //This sorts the image data based on highest channel
    let sortedData = sortImageData(data, highestChannel);
    //This gives back the middle index
    let median = getMedian(sortedData);
    //Here I break the array from median and resend it
    const lowerPart = data.slice(0, median);
    const upperPart = data.slice(median + 1);
    getPallete(lowerPart);
    getPallete(upperPart);
  }
};

I have implemented the first 4 steps mentioned in the link. However, I am messing up in the last step or rather I am unable to figure out how to get my final pallet. Can anyone help in correcting this code/telling me what I missed?

Answer 1

Looks like you are not returning anything and you don't seem to break the recursion. Also, in the linked source, it says that you have to build averages over the buckets. And you need to specify the number of colors to find, which corresponds to the number of iterations.

Here is what I think you need to add:

const getPallete = (data, iterations) => {
  if (data.length === 0) {
    return []
  }
  
  if(iterations <= 1){
    return [getAverageColor(data)]  // <--- build bucket average
  }

  // build upper and lower bucket, same as before
  
  return [ // <--- collect and return recursion result
    ...getPallete(lowerPart, iterations-1),
    ...getPallete(upperPart, iterations-1)
  ]
}

const getAverageColor = (data) => {
  const sums = [0,0,0,0]
  for (let i = 0; i < data.length; i += 4) {
    for (let j = 0; j < 4; j++) {
      sums[j] += data[i+j]
    }
  }
  const numberOfPixels = data.length / 4
  return sums.map(v => Math.round(v/numberOfPixels))
}

Here is a quick sandbox