跳转到内容

中位切割算法

维基百科,自由的百科全书

中位切割算法(Median cut) 是Paul Heckbert于1979年提出来的算法。概念上很简单,却也是最知名、应用最为广泛的减色算法(Color quantization英语Color_quantization)。常见的影像处理软件如Photoshop、GIMP...等,都使用了这个算法或其变种。[1]

算法

[编辑]

假如你有任意一张图片,想要降低影像中的颜色数目到256色。

  1. 将图片内的所有像素加入到同一个区域
  2. 对于所有的区域做以下的事:
    1. 计算此区域内所有像素的RGB三元素最大值与最小值的差。
    2. 选出相差最大的那个颜色(R或G或B)
    3. 根据那个颜色去排序此区域内所有像素
    4. 分割前一半与后一半的像素到二个不同的区域(这里就是“中位切割”名字的由来)
  3. 重复第二步直到你有256个区域
  4. 将每个区域内的像素平均起来,于是你就得到了256色

算法的限制

[编辑]

因为每次循环区域的数量都会加倍,所以最终产生的颜色数量必定为2的次方。假如有特殊需要其它数量的颜色时,可以先产生超过需求的颜色数量,再合并多余的颜色直到符合所需的数量。

实作范例

[编辑]

ruby

[编辑]
class Color
  attr_reader :R, :G, :B

  def initialize(r = rand(256), g = rand(256), b = rand(256))
    @R = r
    @G = g
    @B = b
  end

  def inspect
    return "{R: #{@R}, G: #{@G}, B: #{@B}}"
  end
end

def get_colors(image_input, need_num)
  regions = [image_input.flatten]

  while regions.size < need_num
    new_regions = []
    regions.each do |region|
      max_color = [:R, :G, :B].map do |color|
        colors = region.map(&color)
        next [colors.max - colors.min, color]
      end.max[1]

      new_order = region.sort_by(&max_color).reverse
      middle = new_order.size / 2
      new_regions.push(new_order[0, middle], new_order[middle, middle + 1])
    end
    regions = new_regions
  end

  return regions.map do |region|
    Color.new(*[:R, :G, :B].map{|color| (region.map(&color).inject(&:+) / region.size.to_f).round })
  end
end

get_colors(Array.new(10){ Array.new(10){ Color.new } }, 16)
# => [{ R: 187, G: 226, B: 184 }, { R: 185, G: 169, B: 189 }, ...]

另见

[编辑]

引用

[编辑]

外部链接

[编辑]