$yuzu->log();

技術ネタなど。

カラーヒストグラムを利用した類似画像検索システムの作り方

類似画像検索 アルゴリズム

最近Machine Learning(機械学習)を勉強することが多いのですが、そこに引きづられて類似画像検索について勉強する機会があったので、その内容についてまとめます。

画像検索ではクエリにテキストを入れてテキストに関連した画像を検索します。 一方、類似画像検索ではクエリに画像を与えて似た画像を検索します。 検索クエリに画像をアップロードすることが特徴です。

この分野をCBIR(Content-based image retrieval)と呼び1992年から研究されているそうです。

検索手法は沢山ありますが、今回は、画像の色に着目して、類似画像検索システムを作ってみたいと思います。

カラーヒストグラムとは

色は色の三原色である、赤緑青、所謂RGBで表せます。 そのRGBを使って、画像中にRGBの各色が何ピクセルあるか数えて作成した棒グラフです。 たとえば、

f:id:yuzurus:20161001172211j:plain

のカラーヒストグラムを作成すると

f:id:yuzurus:20161001172228p:plain

このように描写できます。

\displaystyle

画像を減色して計算する

上記のグラフを見て気づいた方がいるかもしれませんが、減色して計算しています。

通常色はRGBの各8ビット、つまり256通りですので、表示できる色数は\( 256^{3} \) で約17,000,000通りあります。 これはあまりにも多すぎて計算量が膨大になってしまいます。 ですので、RGBを各2ビット、つまり4通り、\( 4^{3}=64 \) 通りまで減色。64次元のベクトルで計算できるようにしています。

画像の類似度の算出

画像Aのカラー値\( i \) のピクセルの個数を\( AH_i \)、2枚目の画像のカラー値\( i \) のピクセルの個数を\( BH_i \)とします。各カラー値\( min(AH_i,BH_i) \) についてを求めます。 \( min(A,B) \) とは\( A \)と\( B \)で小さい方を返す関数です。 これを全部のカラー値で足すと

{ \displaystyle D = \sum_{i=0}^{63} min(AH_i,BH_i) }

となり\( D \) をヒストグラムインタセクションいいます。

この値が大きくなればなるほど、２つの画像は類似しているということになります。

PHPによるサンプルプログラム

RGBから64色に減色するプログラム

<?php 
/**
 * ヒストグラムのビンを計算
 * @param $rgb
 * @return int
 */
function rgb2no($rgb) {
  $r = ($rgb >> 16) & 0xFF;
  $g = ($rgb >> 8) & 0xFF;
  $b = $rgb & 0xFF;
  $rn = floor($r / 64);
  $gn = floor($g / 64);
  $bn = floor($b / 64);
  return 16 * $rn + 4 * $gn + $bn;
}

カラーヒストグラム作成プログラム

/**
 * 画像からカラーヒストグラムを作成(csv形式)
 * @param $path 画像保存先
 * @param bool $cache
 * @return array
 */
function makeHistogram($path, $cache = TRUE) {
  // 結果を保存するファイル
  $csvfile = preg_replace('/\.(jpg|jpeg)$/', '-his.csv', $path);
  if ($cache) { // ヒストグラムのキャッシュを使うか
    if (file_exists($csvfile)) {
      $s = file_get_contents($csvfile);
      return explode(",", $s);
    }
  }
  $im = imagecreatefromjpeg($path);
  $sx = imagesx($im);
  $sy = imagesy($im);
  // ピクセルを数える
  $his = array_fill(0, 64, 0);
  for ($y = 0; $y < $sy; $y++) {
    for ($x = 0; $x < $sx; $x++) {
      $rgb = imagecolorat($im, $x, $y);
      $no = rgb2no($rgb);
      $his[$no]++;
    }
  }
  // 8bitに正規化
  $pixels = $sx * $sy;
  for ($i = 0; $i < 64; $i++) {
    $his[$i] = floor(256 * $his[$i] / $pixels);
  }
  file_put_contents($csvfile, implode(",", $his));
  return $his;
}

２つの画像から類似度を調べる

// $AHは画像Aのカラーヒストグラム、$BHは画像Bのカラーヒストグラム
$sum = 0;
for ($i = 0;$i < 64;$i++) {
  $sum += $min($AH[$i], $BH[$i]);
}

これらのロジックに基いて、予め用意しておいた画像を検索対象にして、検索してみましょう。 すると下記のような結果が得られます。 左上から順に類似度が高いものになります。

f:id:yuzurus:20161001183900p:plain

類似画像が検索できましたね！

参考文献

類似画像検索システムを作ろう - 人工知能に関する断創録
http://web.tuat.ac.jp/~s-hotta/gke/ch4/index.html