中位切割演算法()是Paul Heckbert於1979年提出來的演算法。概念上很簡單,卻也是最知名、應用最為廣泛的減色演算法()。常見的影像處理軟體如Photoshop、GIMP...等,都使用了這個演算法或其變種。
演算法
假如你有任意一張圖片,想要降低影像中的顏色數目到256色。
將圖片內的所有像素加入到同一個區域
對於所有的區域做以下的事:
計算此區域內所有像素的RGB三元素最大值與最小值的差。
選出相差最大的那個顏色(R或G或B)
根據那個顏色去排序此區域內所有像素
分割前一半與後一半的像素到二個不同的區域(這裡就是「中位切割」名字的由來)
重複第二步直到你有256個區域
將每個區域內的像素平均起來,於是你就得到了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 [{ R: 187, G: 226, B: 184 }, { R: 185, G: 169, B: 189 }, ...]
另見
- k-d樹
引用
外部連結
*[http://micro.magnet.fsu.edu/primer/java/digitalimaging/processing/colorreduction/index.html Image quantization]
*[http://www.leptonica.com/papers/mediancut.pdf Median cut + variations]
*[https://metacpan.org/pod/Image::Pngslimmer Image::Pngslimmer Perl module at CPAN]
*[https://web.archive.org/web/20160323053348/http://gl.ict.usc.edu/Research/MedianCut/ A Median Cut Algorithm for Light Probe Sampling]
评论 (0)