中位切割演算法

中位切割演算法（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 }, ...] 

另見

• k-d樹

引用

1. JavaScript图像处理(6) - 减色算法(Color Reduction) - Peihong's Infinite Dimensional Space - 博客频道 - CSDN.NET. blog.csdn.net. [2016-06-30]. （原始内容于2016-08-18）. 

外部連結

• Image quantization（页面存档备份，存于互联网档案馆）
• Median cut + variations（页面存档备份，存于互联网档案馆）
• Image::Pngslimmer Perl module at CPAN（页面存档备份，存于互联网档案馆）