使用JavaScript实现Median Cut算法时的调色板生成问题

我正尝试实现一段从图像中提取颜色并生成指定数量调色板颜色的代码，计划使用Median Cut算法完成此功能。目前已实现算法的前4个步骤，但在最后一步无法获取最终调色板。以下是我的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);
  }
};

你的代码存在4个核心问题，导致无法生成最终调色板，以下是问题分析和修正方案：

1. 全局变量污染导致通道极值计算错误 #

channelProperties作为全局变量，会被所有递归分支共享，不同颜色块的极值会互相覆盖，导致通道范围计算完全错误。

修正：每次处理独立的颜色块时，单独计算当前块的通道极值，不要使用全局变量。

2. 缺失递归终止条件 #

代码没有设置停止分割的条件，递归会一直分割到像素数据为空，永远不会生成调色板颜色。

修正：添加终止条件，当调色板颜色数量达到目标值，或者当前块像素数量过少时，停止分割并计算当前块的平均颜色。

3. 分割逻辑错误 #

你使用原始data而非排序后的sortedData进行分割，导致分割后的块并不是按通道排序后的结果，分割逻辑完全失效。

修正：基于排序后的像素数组进行分割，保证分割后的两个块对应通道的数值范围是连续的。

4. 缺少颜色均值计算步骤 #

Median Cut算法的最后一步是对每个最终块计算颜色均值，作为调色板的颜色，你的代码完全遗漏了这一步。

修正后的完整代码示例 #

// 目标调色板颜色数量
const TARGET_PALETTE_SIZE = 8;
// 存储最终调色板
const palette = [];

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;
  
  // 转换为[r,g,b]数组格式，简化处理（如需保留alpha可扩展）
  const pixels = [];
  for (let i = 0; i < pixelData.length; i += 4) {
    pixels.push([pixelData[i], pixelData[i+1], pixelData[i+2]]);
  }
  
  getPalette(pixels);
  console.log('最终调色板:', palette);
};

const getPalette = (pixels) => {
  // 递归终止条件：调色板数量达标，或当前块像素过少
  if (palette.length >= TARGET_PALETTE_SIZE || pixels.length <= 1) {
    const avgColor = calculateAverageColor(pixels);
    palette.push(avgColor);
    return;
  }

  // 计算当前块的各通道极值与范围
  const channelProps = calculateChannelProperties(pixels);
  
  // 获取范围最大的通道（0=红，1=绿，2=蓝）
  const highestChannel = getHighestRangeChannel(channelProps);
  
  // 按目标通道排序像素
  const sortedPixels = [...pixels].sort((a, b) => a[highestChannel] - b[highestChannel]);
  
  // 找到中位数位置分割
  const medianIndex = Math.floor(sortedPixels.length / 2);
  const lowerPart = sortedPixels.slice(0, medianIndex);
  const upperPart = sortedPixels.slice(medianIndex);
  
  // 递归处理两个子块
  getPalette(lowerPart);
  getPalette(upperPart);
};

// 计算当前像素块的各通道极值
const calculateChannelProperties = (pixels) => {
  let minRed = 255, maxRed = 0;
  let minGreen = 255, maxGreen = 0;
  let minBlue = 255, maxBlue = 0;
  
  pixels.forEach(([r, g, b]) => {
    minRed = Math.min(minRed, r);
    maxRed = Math.max(maxRed, r);
    minGreen = Math.min(minGreen, g);
    maxGreen = Math.max(maxGreen, g);
    minBlue = Math.min(minBlue, b);
    maxBlue = Math.max(maxBlue, b);
  });
  
  return {
    redRange: maxRed - minRed,
    greenRange: maxGreen - minGreen,
    blueRange: maxBlue - minBlue
  };
};

// 获取范围最大的通道索引
const getHighestRangeChannel = (props) => {
  const ranges = [props.redRange, props.greenRange, props.blueRange];
  return ranges.indexOf(Math.max(...ranges));
};

// 计算像素块的平均颜色
const calculateAverageColor = (pixels) => {
  let totalR = 0, totalG = 0, totalB = 0;
  pixels.forEach(([r, g, b]) => {
    totalR += r;
    totalG += g;
    totalB += b;
  });
  const count = pixels.length;
  return [
    Math.round(totalR / count),
    Math.round(totalG / count),
    Math.round(totalB / count)
  ];
};

内容的提问来源于stack exchange，提问作者Shardul Birje