色彩量化（Color Quantization）中位切割法（Median Cut Algorithm）

最近想研究了一下圖片色彩的量化（Color Quantization），找到很多演算法，例如中位切割法（Median Cut Algorithm）、八叉樹（Octree）...等等。

先研究簡單的中位切割法，原理很好懂，這個網站（http://acm.nudt.edu.cn/~twcourse/ColorQuantization.html）說得很清楚，這邊就不復述了。

當然了瞭解了原理，就要想辦法自己實做看看，選擇自己最熟悉的ActionScript 3 ，作出類似 iTunes 的唱片封面效果。

直接來看Code

//為了提高效率，減少圖片的像素
function narrow(src:BitmapData,size:int):BitmapData {
 var matrix:Matrix = new Matrix();
 var scale:Number = 1;

 if (src.width > src.height) {
  scale = size / src.width;
 } else {
  scale = size / src.height;
 }

 matrix.scale(scale,scale);

 var bd:BitmapData = new BitmapData(src.width * scale,src.height * scale,true,0x00000000);
 bd.draw(src,matrix);

 return bd;
}

//取得所以像素的顏色
function colors(src:BitmapData):Array {
 var _colors:Array = [];

 for (var i = 0; i < src.width; i++) {
  for (var j = 0; j < src.height; j++) {
   var value:uint = src.getPixel32(i,j);
   var red:uint = (value >> 16) & 0xFF;
   var green:uint = (value >> 8) & 0xFF;
   var blue:uint = value & 0xFF;

   _colors.push({r:red,g:green,b:blue});
  }
 }

 return _colors;
}

//中位切割
//areaNum 是希望切割成多少區域
function medianCut(src:BitmapData, areaNum:int):Array {
 var _colors:Array = colors(narrow(src,50));
 var totlePixel:int = _colors.length;
 var _box:ColorBox = new ColorBox(_colors); //ColorBox 是自定義的Class 下面會介紹
 var boxs:Array = [_box];
 var cutNum:int = areaNum - 1;

 for (var i = 0; i < cutNum; i++) {
  var temp:Array = boxs[0].medianCut();//找第一個區域進行切。因為每次切割完會進行排序，總是將體積最大的排最前面。
  boxs[0].destroy();
  boxs.splice(0,1);
  boxs = boxs.concat(temp);
  if (i != cutNum-1) { //最後一次不用排序
   boxs.sortOn("volume", Array.NUMERIC | Array.DESCENDING);//依切割出來的區域體積大小來排序
  }
 }

 //依區域內像素資料數量排序。另外如數量一樣，顏色淺的排前面，這只是我個人的偏好。
 boxs.sortOn(["count", "averageColor"], [Array.NUMERIC | Array.DESCENDING, Array.NUMERIC | Array.DESCENDING]);

 var newColors:Array = [];
 for (i = 0; i < areaNum; i++) {
  var o:Object = {};
  o.color = boxs[i].averageColor; //取得這個區域顏色的平均色
  o.proportion = boxs[i].count / totlePixel * 100; //算出這個顏色佔的百分比
  newColors[i] = o;

  boxs[i].destroy();
 }

 return newColors;
}

建立 ColorBox

class ColorBox{
 private var _l:Number = 0;
 private var _w:Number = 0;
 private var _h:Number = 0;
 private var _v:Number = 0;
 private var _c:uint = 0;

 private var points:Array;
 private var isOver:Boolean = false;

 public function ColorBox(points:Array){
  this.points = points;
  operational();
 }

 public function medianCut():Array{ //中位切割
  points.sortOn(comparison(),Array.NUMERIC); //為了要從最長的一邊切割，所以先一最長的邊進行排序
  var median:int = points.length >> 1; //算出中點
  return [new ColorBox(points.slice(0,median)),new ColorBox(points.slice(median))]; //將原始的陣列切成兩個陣列，且回傳兩個ColorBox
 }

 public function destroy(){
  points = null;
 }

 public function get volume():Number{
  return _v;
 }

 public function get count():int{
  return points.length;
 }

 public function get averageColor():uint{ //算出這個顏色的平均色
  if(isOver) return _c;
  isOver = true;
  var r:uint = 0, g:uint = 0, b:uint = 0;
  var ln:int = points.length;

  for(var i:int = 0; i < ln; i++){
   r += points[i].r;
   g += points[i].g;
   b += points[i].b;
  }

  _c = ((r / ln) << 16) | ((g / ln) << 8) | (b / ln);

  return _c;
 }

 private function operational(){ //計算區域的長、寬、高還有體積
  var rA:Array = [], gA:Array = [], bA:Array = [];
  for(var i:int = 0, ln = points.length; i < ln; i++){
   rA[i] = points[i].r;
   gA[i] = points[i].g;
   bA[i] = points[i].b;
  }

  _l = Math.max.apply(null,rA) - Math.min.apply(null,rA);
  _w = Math.max.apply(null,gA) - Math.min.apply(null,gA);
  _h = Math.max.apply(null,bA) - Math.min.apply(null,bA);

  _v = _l * _w * _h;
 }

 private function comparison():String{ //找出哪一個邊最長
  if(_l > _w) {
   if(_l > _h) return "r";
   else return "b";
  }else{
   if(_w > _h) return "g";
   else return "b";
  }
 }

}

到這裡，工具都準備好了，使用起來很簡單，調用medianCut，只要傳入目標BitmapData，還有切割的區域數量，即可。
像上面範例切割成16個區域。

medianCut(bitmapData,16)