INSIGHT

インサイト

2012年29

メディアンカット法による画像の減色

こんにちは。マンガゲットの開発を担当している武上です。

先日マンガゲットではマンガコマ書き出しエンジンのリニューアルを行いました。

今日はそれに関連して画像の減色について書きたいと思います。

減色とはその名の通り、画像の色の数を減らすことです。PNGのような画像形式の場合、フルカラーで表現することもできますが、使う色数を制限することで、大幅にファイルサイズを削減することができます。 大量の画像をスマートフォン向けの大きな解像度で連続して表示させようとした場合、単純にフルカラーにしてしまうと、ダウンロードにかかる時間が長くなってしまい、マンガのコマをさくさくと読んでもらうことができなくなってしまいます。 そこで、なるべく見た目を変えずにファイルサイズをいかに削減できるかが重要になってきます。近い色をまとめることで、見た目を維持しつつ画像の色数を減らす処理が減色です。

減色の流れは、以下のように行います。

1. 元画像から実際に使われている色の集合を抽出する 2. 抽出した色集合を元に、より色数の少ない色集合(減色パレット)を作成する 3. 元画像の各画素を、作成した色集合の最も近い色にマッピングして、画像を変換する

ここで色味の仕上がりに最も重要になるのが2の減色パレットの作成です。 色数を単純に減らすだけだとマッピングした際の色の違いが大きくなってしまい、最終的な見た目が変わってしまいます。 どのようにして色数を減らすかについてはいくつか代表的なアルゴリズムがあります。

例としていくつか上げてみます。

1. 均等量子化 元画像での色分布を考慮せず単純に階調を落とす手法です。 RGBそれぞれ256階調(24bit)の画像を32階調(8bit)におとせば、色数は単純に半分になります。 24bitの画像を8bitに落とすには各画素の下位bitをビットマスクで落とすことで実現できます。

簡単に書くと各画素に対して以下のように変換していきます。

int newRed = red & 0xF0;
 int newGreen = green & 0xF0;
 int newBlue = blue & 0x80;

人間は青よりも赤と緑の変化を敏感に感じとるので、ここでは赤と緑に多めに階調を割り当てています。この手法は簡単ですが、元の色分布を無視してしまうので再現性が低いです。

2. 頻度法 各画素の利用回数をカウントして、使われる回数の多い順に色を決めていく手法です。 色の分布がある程度ばらけている場合は効果的に減色できます。ただし、例えば空が主体のイラストでは、色の分布が青系に偏っていることが多いことが予想されますが、この場合、パレットの殆どが青系で埋まってしまうため、空以外の要素の再現性が極端に低くなってしまいます。むしろ、色が均等に分布している画像のほうが少ないので、あまり上手くいきません。

3. 分布法 僕も独自に少し考えてみました。画像を小さいサイズに縮小した状態からサンプリングする手法です。縮小は欲しい色数になるぎりぎりのところまでかなり小さく縮小します。 縮小することで、低頻度の色を確率的に減らし、かつ画像の全体から平均的に色を取ることができます。仮に空主体の画像であっても、他の要素にもある程度色を割り振ることができ、ある程度の再現性は維持できます。 とはいえ、やはり頻度の多い色には引っ張られるので、低頻度の色の再現性は十分ではありません。   4. メディアンカット法 最も代表的で優れているとされる手法です。 RGBの画素を、3次元の直方体内の座標として考えて、その直方体を、画素数が同じになるように分割していく手法です。中央値(メディアン)で、分割していくのでメディアンカットといいます。

Youtubeにこの手法を視覚化した動画がありますので、まずはこちらを見ていただくとわかりやすいかと思います。

YouTubeで動画を見る

メディアンカット法は以下のように流れで実装できます。 1. 色空間から直方体を作成する(全ての色を含む) 2. 画素のない部分のカット(各画素のRGBそれぞれの最大値/最小値を求めて、範囲外を無視すればよい) 3. 直方体の最も長い辺RGBいずれかであるか調べる(最大値/最小値差が最も大きいもの) 4. 最も長い辺の中央値で分割する 5. 分割された直方体の中から最も色数が多いものを選んで、再度分割する(必要な色数になるまで分割する) 6. 各直方体の代表色を決定する(平均値)

Scalaで実際に実装してみましたので参考にしてみてください。

Quantizer.scala

package org.srkm.image
import javax.imageio.ImageIO
import java.io.File
import java.awt.image.BufferedImage
import scala.collection.mutable.ListBuffer
import scala.collection.mutable.HashMap
object Quantizer {
//usage Quantizer <image-src> <image-dest> <max-color>
  def main(args:Array[String]):Unit = {
    val srcPath = args(0)
    val destPath = args(1)
    val maxcolor = args(2).toInt;
    val src = ImageIO.read(new File(srcPath))
    val colors = extractColors(src)
    println("colors:" + colors.size)
    val pallet = medianCut(colors, maxcolor);
    println("pallet:" + pallet.size)
    val dest = quantize(src, pallet)
    ImageIO.write(dest, "png", new File(destPath))
  }
  def extractColors(src:BufferedImage):List[Color]={
    val w = src.getWidth()
    val h = src.getHeight()
    var colors = new HashMap[Int, Color]
    (0 to w-1).foreach({x=>
      (0 to h-1).foreach({y=>
        val rgb = src.getRGB(x,y)
        val r = (rgb >> 16) & 0xFF
        val g = (rgb >> 8)  & 0xFF
        val b = rgb         & 0xFF
        val c = new Color(r,g,b)
        if(!colors.contains(rgb)){
          colors.put(rgb, c)
        }
      })
    });
    return colors.values.toList;
  }
  def medianCut(colors:List[Color], maxColor:Int):List[Color]={
    val cube = new ColorCube(colors)
    val divided = divideUntil(List(cube), maxColor)
    return divided.toList.map(_.average);
  }
  def divideUntil(cubes:List[ColorCube], limit:Int):List[ColorCube]={
    cubes match {
      case c if c.size >= limit => cubes
      case _ => {
        val largest = largestCube(cubes)
        val divided = largest.divide()
        if(divided.size < 2){
          cubes
        }else{
          val result = cubes.remove(_==largest) ::: divided
          divideUntil(result,limit)
        }
      }
    }
  }
  def largestCube(cubes:List[ColorCube]):ColorCube={
    var max:ColorCube = null
    var maxCount = 0
    cubes.foreach({x=>
      if(x.colorCount > maxCount){
        max = x
        maxCount = x.colorCount
      }
    })
    max
  }
  def quantize(src:BufferedImage, pallet:List[Color]):BufferedImage={
    val w = src.getWidth()
    val h = src.getHeight()
    val dest = new BufferedImage(w, h, BufferedImage.TYPE_BYTE_INDEXED)
    (0 to w-1).foreach({x=>
      (0 to h-1).foreach({y=>
        val rgb = src.getRGB(x,y)
        val r = (rgb >> 16) & 0xFF
        val g = (rgb >> 8)  & 0xFF
        val b = rgb         & 0xFF
        val c = new Color(r,g,b)
        dest.setRGB(x, y, c.searchClosestColor(pallet).toInt)
      })
    })
    return dest;
  }
}

ColorCube.scala

package org.srkm.image
import scala.collection.mutable.ListBuffer
class ColorCube(colors:List[Color]) {
  val cs=colors
  var minR = 255
  var maxR = 0
  var minG = 255
  var maxG = 0
  var minB = 255
  var maxB = 0
  colors.foreach({color=>
    if(color.red < minR) minR = color.red
    if(color.red > maxR) maxR = color.red
    if(color.green < minG) minG = color.green
    if(color.green > maxG) maxG = color.green
    if(color.blue < minB) minB = color.blue
    if(color.blue > maxB) maxB = color.blue
  })
  def divide():List[ColorCube]={
    val cut = largestEdge()
    val med = median(cut)
    return divideBy(cut, med)
  }
  def divideBy(cut:Int, median:Int):List[ColorCube]={
    var list0:ListBuffer[Color] = new ListBuffer()
    var list1:ListBuffer[Color] = new ListBuffer()
    colors.foreach({c=>
      if(c.get(cut) < median){
        list0 += c
      }else{
        list1 += c
      }
    })
    if(list0.size > 0 && list1.size > 0){
      List(new ColorCube(list0.toList), new ColorCube(list1.toList));
    }else{
      Nil
    }
  }
  def median(cut:Int)={
    val edge = colors.map(_.get(cut)).sort((a,b)=>a > b)
    edge.take(edge.size/2+1).last
  }
  def largestEdge():Int={
    val diffR = maxR-minR
    val diffG = (maxG-minG) * 0.8
    val diffB = (maxB-minB) * 0.5
    if(diffG >= diffB){
      if(diffR >= diffG){
        Color.RED
      }else{
        Color.GREEN
      }
    }else{
     if(diffR >=diffB){
       Color.RED
     } else{
       Color.BLUE
     }
    }
  }
  def colorCount:Int = cs.size
  def average():Color={
    var sumR = 0
    var sumG = 0
    var sumB = 0
    colors.foreach({c=>
      sumR += c.get(Color.RED)
      sumG += c.get(Color.GREEN)
      sumB += c.get(Color.BLUE)
    })
    val c = new Color(sumR/colors.size, sumG/colors.size, sumB/colors.size)
    c.searchClosestColor(colors)
  }
}

Color.scala

package org.srkm.image
class Color(r:Int, g:Int, b:Int) {
  def red=r;
  def green=g;
  def blue=b;
  def get(w:Int)={
    w match {
      case Color.RED => red;
      case Color.GREEN => green;
      case Color.BLUE => blue;
    }
  }
  def toInt():Int={
    (r<<16)+(g<<8)+b
  }
  def searchClosestColor(pallet:List[Color]):Color={
    var min=0;
    var found:Color = null
    var closest:Color = null
    pallet.foreach({p=>
      val d = (Math.pow(red-p.red,2)+Math.pow(green-p.green,2)+Math.pow(blue-p.blue,2)).toInt
      if(d==0){
        found = p
        closest = p
      }else if(min==0 || d<min){
        closest = p
        min = d
      }
    })
    if(found == null){
      closest
    }else{
      found
    }
  }
}
object Color {
  val RED:Int = 0
  val GREEN:Int = 1
  val BLUE:Int = 2
}

githubにも上げました

サンプルでは人間の視覚が敏感な肌色に近い色の再現度を上げるために、カットすべき辺を見つける際、赤>緑>青の順で優先度を設定しています。

では!