中位切割演算法

维基百科,自由的百科全书
跳到导航 跳到搜索

中位切割演算法(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[编辑]

 1 class Color
 2   attr_reader :R, :G, :B
 3   def initialize(r = rand(256), g = rand(256), b = rand(256))
 4     @R = r
 5     @G = g
 6     @B = b
 7   end
 8   def inspect
 9     return "{R: #{@R}, G: #{@G}, B: #{@B}}"
10   end
11 end
12 def get_colors(image_input, need_num)
13   regions = [image_input.flatten]
14   while regions.size < need_num
15     new_regions = []
16     for region in regions
17       max_color = [:R, :G, :B].map{|color|
18         colors = region.map(&color)
19         next [colors.max - colors.min, color]
20       }.max[1]
21       new_order = region.sort_by(&max_color).reverse
22       middle = new_order.size / 2
23       new_regions.push(new_order[0, middle], new_order[middle, middle + 1])
24     end
25     regions = new_regions
26   end
27   return regions.map{|region|
28     next Color.new(*[:R, :G, :B].map{|color| (region.map(&color).inject(&:+) / region.size.to_f).round })
29   }
30 end
31 get_colors(Array.new(10){ Array.new(10){ Color.new } }, 16)

另見[编辑]

引用[编辑]

外部連結[编辑]