画像処理

(1) シーム・カービング

画像を拡大・縮小する場合、通常利用される方法として、「最近傍法 ( Nearest Neighbour )」や「線形補間法 ( Bilinear Interpolation )」に代表されるサンプル補間法があることを以前紹介しました (「グラフィック・パターンの扱い (5) サンプル補間」参照 )。最近、サンプル補間法とは概念のまったく異なる画像の拡大・縮小方法として「シーム・カービング ( Seam Carving )」が注目され、すでに実用的なアプリケーションも誕生しています。この手法は、画像のリサイズ処理だけに限らず、特定のオブジェクトの除外や再配置など、応用範囲が非常に広いため、これからも様々な目的に応用される可能性があるアルゴリズムです。今回は、この「シーム・カービング」について紹介したいと思います。


1) シーム・カービング

ブラウザは、世界中に散らばった様々なコンテンツを閲覧することができる便利なツールです。その中で、画像や動画を表示したり、場合によっては音楽を聴くこともできますが、特にお世話になるのはドキュメントの閲覧ではないでしょうか。ドキュメントは通常、HTML ( HyperText Markup Language ) 形式のファイルで作成され、その中のタグをブラウザが解析して見栄えよく画面上へ表示してくれます。ドキュメントの中には、インライン画像や表などが挿入されているため、ブラウザはレイアウトを自動的に調整して表示します。
現在は、ウィンドウシステム上でブラウザが動作するのが普通であり、その中ではウィンドウサイズを自由に変更することができます。ブラウザはそのサイズに合わせて、文字やインライン画像などの配置を動的に変更しなければならない場合もあります。このとき、文字やインライン画像のサイズは変化せず、その配置だけが変化します。

画像をリサイズする場合、以前紹介したサンプル補間によって、全体の配置はそのままに個々のオブジェクトをリサイズする手法がよく利用されています。例えば、名所・旧跡を背景に集合写真を撮影した画像があったとき、背景の建物も手前にいる人物も全て同等に、大きさを変化させてしまいます。しかし、ブラウザが画面のサイズに合わせてオブジェクトを再配置してくれるように、人物はそのままの大きさにして背景だけ縮小するなどの処理を行うことは今までの手法ではできません。他の手段として、周囲の画像を切り取ってしまう方法 ( Cropping ) があります。先の例であれば、人物は中央に固まっているはずなので、周囲の背景を切り取ることで実現することができます。しかし、人物が散らばって写っているような場合は、この方法も利用することができません。個々のオブジェクトを認識して、その内容はそのままでリサイズする手法を、文献では「Content-Aware Image Resizing」と呼んでいます。このリサイズを実現するための手法として「シーム・カービング」が考案されました。

Content-Aware Image Resizing」を実現する場合、個々のオブジェクトを表しているピクセル以外の部分を除外する必要があります。よって、画像の中でオブジェクトとして認識される部分とそうでない部分をどのように判別するかが非常に重要となります。そこで、周囲のピクセルに溶け込んで一体化し、そのために目立たないピクセルは重要性が低いと判断し、それを除去するようにします。文献では、この重要度のことを「エネルギー ( Energy )」と呼び、それを算出するための関数を「エネルギー関数 ( Energy Function )」と名付けています。
各ピクセルに何らかの方法でエネルギーを決めた後、次に除去すべきピクセルを選択します。このとき、全ピクセルをエネルギーの大きさでソートして、最もエネルギーの低いピクセルから除去すれば、画像全体のエネルギーの損失を最小限に抑えることができます。しかし、画像から任意の位置でピクセルを除去してしまうと、矩形の形を維持することができなくなります。そのため、例えば横 1 ラインを除去するのであれば、縦の各ラインの中で最もエネルギーの低いピクセルをひとつずつ除去すれば、矩形の形を保つことができます。しかし、今度は画像の輪郭が崩れてしまい、これも採用することはできません。
他の方法として、エネルギーの和が最も低いラインを除去する方法があります。また、残った画像のエネルギーが最大となるように、周囲を切り取るようなやり方も考えられます。しかし、このような方法では、エネルギーの高いピクセルもいっしょに除去される可能性が高くなり、エネルギーの損失は大きくなります。

下図は、上に述べたやり方を実際に使って処理した結果を表しています。元の画像 ( original ) には、ピクセルそれぞれに数値が書き込まれていますが、これがエネルギー値を表しています。この画像に対し、最もエネルギーの低いピクセルを除去する方法 ( optimal )、最小のエネルギーを持つピクセルを各行毎に選んで除去する方法 ( pixel )、最小のエネルギー和を持つ列を除去する方法 ( column ) のそれぞれを使ってピクセルを五つ分除去し、処理後のエネルギーを total として右側に示してあります。

図 1-1. ピクセル除去の方法
ピクセルの除去

シーム・カービングでは、ラインや周囲を除去する方法よりもエネルギーの損失を抑えつつ、ピクセル単位での除去のように画像の内容が崩れてしまうことがないように、八連結 ( 8-connected ) のパスの中から最もエネルギーが低いものを選択します。垂直方向のパスの場合、以下の式で表すことができます。

sx={ sxi } ( i = 1, 2, ... n )
={ ( x(i), i ) } ( i = 1, 2, ... n )

但し、| x(i) - x(i - 1) | ≤ 1

水平方向のパスならば、次のような式になります。

sy={ syj } ( j = 1, 2, ... m )
={ ( j, y(j) ) } ( j = 1, 2, ... m )

但し、| y(j) - y(j - 1) | ≤ 1

ここで、画像のサイズは m x n であるとしています。

図 1-2. 八連結によるパスの選択
水平方向垂直方向
Seam Carving

上の図は、八連結パスのイメージを、水平・垂直方向それぞれについて表したものです。左端から水平方向にパスを進める場合は、現在位置より右上・右・右下のピクセルの中から最もエネルギーの低いものを選び、その方向へパスを進めます。こうして得られたパスは、エネルギーの和が他のパスと比較して小さくなることが期待できます。よって、水平方向のパスを除去するのなら、左端のピクセルを開始位置としてパスを求める処理を最上位から順に繰り返し、その中から和が最小となるパスを選択すれば、エネルギー損失ができるだけ小さくなるようなパスを求めることができます (*1-1)。

| x(i) - x(i - 1) | ≤ 1 という条件は八連結のパスを求めるためのものですが、これを | x(i) - x(i - 1) | ≤ k (但し k ≥ 0) としたとき、k をゼロにすれば、パスは縦方向のラインを表すことになり、また 1 以上の値を使えば、パスの連結が切断されるのを許すような条件になります。

図 1-3. シーム・カービングによるピクセルの除去
シーム・カービングによるピクセルの除去

上図は、先ほど示したイメージに対してシーム・カービングでピクセル除去した結果を示しています。下側のイメージにおいて、エネルギー値が赤く示されたところはエネルギーが最小となるピクセルをたどった結果を表しています。上側には、各列の先頭を開始位置としてエネルギー和を求めた時の値が示してあります。


*1-1) 以前は「エネルギーが最小となるパス」を記述していましたが、誤りではないかとの指摘があり確かに最小とはならないことに気づきました。近隣のエネルギーが低いパスをたどる手法をとっているため、たどらなかったパスの方が最終的にエネルギーの総和が低くなることは十分にありえます。今回紹介した方法は論文中「Dynamic Programming」と名付けられたオリジナルの方法ですが、その他の方法として一般的には「最短経路問題」を解くアルゴリズムを利用することになります。なお、本当に最小のエネルギーを持ったパスを求めるためには、八連結の場合、パスの長さを N として 3N 通りの組み合わせを調べる必要があるので現実的ではありません。


2) エネルギー関数

シーム・カービングは非常に画期的な考え方ですが、その内容は非常にシンプルなもので、プログラムもそれほど苦労することなく作成することができそうです。しかし、ここで問題なるのがエネルギーの算出方法で、これは画像の内容や利用目的 ( リサイズ、オブジェクトの再配置・除去など ) によって最適な手法は変わるため、どの場合にも利用できる汎用的な方法を考案することは非常に難しいようです。まず、シンプルなエネルギー関数として、論文の中では以下の式が紹介されています。

e1( I(s) ) = | ∂I / ∂x | + | ∂I / ∂y |

上式で、I(s) は画像上のピクセルに対する値を表しているため、エネルギーは水平・垂直方向におけるピクセルの値の変化量の和から算出していることになります。ここで、ピクセルの値として様々な求め方が考えられますが、例えば輝度を値とする場合、I(s) は次のように算出することができます。

I( s ) = 0.299 * R( s ) + 0.587 * G( s ) + 0.114 * B( s )

R( s ), G( s ), B( s ) はそれぞれ、ピクセルの赤・緑・青成分を表しています。他にも、単純に RGB 成分の和を利用する方法もありますが、重要なのは、オブジェクトとして認識される部分に対してはエネルギーが高くなるような値にしなければならないということで、画像によってはこの方法では意図した通りに処理できない場合も発生します。よって、画像に対するピクセルの値を算出する方法は、対象の画像に合わせて切り替えられるようにしておかなければなりません。ここでは、この各ピクセルの値を画像の顕著性 ( Saliency ) と名付けておきます。


ピクセルの顕著性を計算するためのサンプル・プログラムを以下に示します。

/*
  Create : 顕著性データへの変換を行い saliency に登録する

  sz : データのサイズ ( 顕著性データはこの大きさにリサイズされる )
  op : 顕著性計算用関数オブジェクト
*/
template< class Op >
void Create( Matrix< double >* saliency, Coord< int > sz, Op op )
{
  assert( saliency != 0 );

  saliency->assign( sz.y, sz.x );
  Matrix< double >::iterator it = saliency->begin();
  for ( Coord< int > c( 0, 0 ) ; c.x < sz.x ; ++( c.x ) )
    for ( c.y = 0 ; c.y < sz.y ; ++( c.y ) )
      *it++ = op( c );
}

/*********************************
   輝度を使った顕著性データ
*********************************/

class ImageSaliency_Luminance
{
  const DrawingArea_IF& draw_; // 顕著性データを求める対象画像への参照

 public:

  /*
    ImageSaliency_Luminance コンストラクタ : 顕著性データを求める対象画像 draw を指定して構築
  */
  ImageSaliency_Luminance( const DrawingArea_IF& draw )
    : draw_( draw ) { assert( &draw != 0 ); }

  /*
    ImageSaliency_Luminance::operator() : c の位置の顕著性データ(輝度)を求める
  */
  double operator()( Coord< int > c ) const
  {
    RGB rgb;
    draw_.point( c, &rgb );

    return( 0.299 * rgb.r + 0.587 * rgb.g + 0.114 * rgb.b );
  }
};

/*
  CreateByLuminance : 輝度を使った画像データ draw から顕著性データ saliency への変換
*/
void CreateByLuminance( const DrawingArea_IF& draw, Matrix< double >* saliency )
{
  ImageSaliency_Luminance isLumi( draw );
  Create( saliency, draw.size(), isLumi );
}

サンプル・プログラムの中で、RGB は色コードの RGB 成分を扱うための構造体を表し、r, g, b をそれぞれ赤・緑・青各成分を保持する公開メンバ変数とします。Coord は平面上の座標を扱うための構造体で、座標値 x, y が公開メンバ変数となっています。また、DrawingArea_IF は描画用オブジェクトのための抽象クラス ( インターフェース ) で、必要な機能として、ピクセルの色コード取得 ( point )・点描画 ( pset )・画像サイズの取得 ( size )・サイズの変更 ( resize ) を純粋仮想関数として用意しています。最後に Matrix は行列クラスで、メンバ関数 assign を使って任意の行・列数にリサイズできる他、反復子 iterator を持ち、begin 関数で行列の左上隅の位置を取得できるようになています。インクリメントにより行方向下側に要素をたどり、最も下まで達したら次の列の最も上側に移る操作を反復子が右下隅に達するまで続ける仕様となっています。いずれも具体的な定義や実装は省略してあります。

画像の顕著性は Matrix オブジェクトで保持します。このオブジェクトへのポインタとそのサイズ、顕著性を計算するための関数オブジェクトを引数として関数 Create で顕著性データの作成を行います。ここで、画像データそのものは渡されず、関数オブジェクトに座標位置を渡して出力される値を顕著性として登録していることに注意してください。今後、顕著性として利用する値は輝度以外にも登場し、画像を一度他のデータに変換した上で顕著性を求める場合もあるためこのような仕様になっています。

輝度データは ImageSaliency_Luminance クラスで計算します。対象画像への参照を構築時に保持し、指定した座標のピクセルを輝度に変換する処理を operator() にて実行しています。あとは、画像を指定して ImageSaliency_Luminance インスタンスを作成し、インスタンスを引数に Create を呼びだせば輝度を使った顕著性データが得られます。この処理は関数 CreateByLuminance で行われます。


顕著性を求めることができたら、次はエネルギー関数を定義してエネルギーを求める処理を行います。そのためのサンプル・プログラムを以下に示します。

/****************************************
   エネルギー計算用関数オブジェクト
*****************************************/

/*
  EnergyFunction_Base : エネルギー計算用関数オブジェクト基底クラス
*/
struct EnergyFunction_Base
{
  // 仮想デストラクタ(何もしない)
  virtual ~EnergyFunction_Base() {}

  // operator() : 二座標間のエネルギーを求める
  //
  // saliency : 顕著性データ
  // c0,c1 : エネルギー算出対象の座標
  virtual double operator()( const Matrix< double >& saliency, Coord< int > c0, Coord< int > c1 ) const = 0;
};

/*
  EnergyFunction_Row : 隣接ピクセルの顕著性データをそのまま使用する
*/
struct EnergyFunction_Row : public EnergyFunction_Base
{
  virtual double operator()( const Matrix< double >& saliency, Coord< int > c0, Coord< int > c1 ) const
  { return( saliency[c1.y][c1.x] ); }
};

/*
  EnergyFunction_L1 : 画像の顕著性の指定した二点における L1-Norm 算出
*/
struct EnergyFunction_L1 : public EnergyFunction_Base
{
  virtual double operator()( const Matrix< double >& saliency, Coord< int > c0, Coord< int > c1 ) const
  {
    double norm = 0;
    double diff = saliency[c1.y][c1.x] - saliency[c0.y][c0.x]; // 顕著性の差

    if ( c0.x != c1.x )
      norm = std::abs( diff / ( c0.x - c1.x ) );
    if ( c0.y != c1.y )
      norm += std::abs( diff / ( c0.y - c1.y ) );

    return( norm );
  }
};

/*
  EnergyFunction_L2 : 画像の顕著性の指定した二点における L2-Norm 算出
*/
struct EnergyFunction_L2 : public EnergyFunction_Base
{
  virtual double operator()( const Matrix< double >& saliency, Coord< int > c0, Coord< int > c1 ) const
  {
    double norm = 0;
    double diff = saliency[c1.y][c1.x] - saliency[c0.y][c0.x]; // 顕著性の差

    if ( c0.x != c1.x )
      norm = std::pow( diff / ( c0.x - c1.x ), 2.0 );
    if ( c0.y != c1.y )
      norm += std::pow( diff / ( c0.y - c1.y ), 2.0 );

    return( norm );
  }
};

エネルギー関数として EnergyFunction_Base を基底クラスとし、operator() 関数を純粋仮想関数として定義しています。その派生クラスは三つ用意してあり、その中の EnergyFunction_Row は隣接ピクセルの値をそのまま返す関数となっています。顕著性の変動ではなく値そのものをエネルギーとして利用することを想定しています。

EnergyFunction_L1L1 ノルムを計算するため、EnergyFunction_L2L2 ノルムを計算するために利用するクラスです。ノルムはベクトル空間上にある二点間の距離を表す関数であり、L1 ノルムは各要素の差の絶対値に対して和を取るのに対し、L2 ノルムでは差の平方に対して和を取ります。よって、p0 = ( x0, y0, I0 ) と p1 = ( x1, y1, I1 ) に対する変化量は、それぞれ以下の式で計算しています。

eL1 = | ( I1 - I0 ) / ( x1 - x0 ) | + | ( I1 - I0 ) / ( y1 - y0 ) |

eL2 = { ( I1 - I0 ) / ( x1 - x0 ) }2 + { ( I1 - I0 ) / ( y1 - y0 ) }2

ここで、In ( n = 0, 1 ) は 点 pn における顕著性を表しています。上式は次の点との差分を変化量としているため「前進差分 ( Forward Difference )」と呼ばれています。前の点との差分をとれば「後退差分 ( Backward Difference )」、前の点と次の点との差分を取れば「中央差分 ( Central Difference )」になります。

前進差分 Df = ( Fn+1 - Fn ) / ( Xn+1 - Xn )

後退差分 Db = ( Fn - Fn-1 ) / ( Xn - Xn-1 )

中央差分 Dc = ( Fn+1 - Fn-1 ) / ( Xn+1 - Xn-1 )

中央差分の場合、前後の点を元に傾きを求める事になるので、極端な例として、前後の値が等しく現在位置の値は極端に異なっていたとしても、中央差分の値はゼロになります。前進差分や後退差分に比べると、中央差分は局所的な変化に対してフィルタリングするような効果があるため、自然画のように高周波成分が小さいことが期待できる場合は有効な方法になります。


3) パスの決定

各ピクセル毎にエネルギーの最小値とその値をとるピクセルをたどることができるようになれば、パスの開始位置を決めたときのエネルギーの和を計算することができます。水平方向のパスの中から和が最小となるものを選択したければ、左上隅のピクセルから下側の方向へ順番に開始位置を変更しては和の値を計算していき、全ての計算が完了したら、和の値が最小値となった時の開始位置を選択すればよいことになります。パスが決まれば、そのピクセルを除外してすき間を詰めてしまえば縮小処理になり、逆にサンプル補間法などを使ってパスの近隣のピクセルを増やせば拡大処理となります。


パスの決定とその削除・追加を行うためのサンプル・プログラムを以下に示します。

/*
  SearchMinEnergyPixel : 最小のエネルギーを持つピクセルの探索

  探索対象範囲が顕著性データのサイズと等しいとは限らないので、範囲の最大値を示す chkMax を引数として持つ。
  chkMax は、isHorizontal が true なら Y 座標、false なら X 座標の最大値を表す。

  saliency : 対象の顕著性データへの参照
  c0 : 対象のピクセルの位置へのポインタ ( 最小エネルギーを示すピクセルの位置を返す )
  chkMax : 探索対象範囲の最大値
  func : ノルム計算用関数オブジェクト
  isHorizontal : 走査方向は水平か
  constraint : 探索する幅 ( ±constraint の幅のピクセルを対象に探索する )

  戻り値 : 最小のエネルギー
*/
double SearchMinEnergyPixel( const Matrix< double >& saliency, Coord< int >* c0, int chkMax,
                             const EnergyFunction_Base& func, bool isHorizontal, int constraint )
{
  int curPos = ( isHorizontal ) ? c0->y : c0->x; // 現在位置

  int minPos = curPos - constraint; // eneMinを取る位置(比較開始ピクセルで初期化)
  if ( minPos < 0 ) minPos = 0;
  int maxPos = curPos + constraint; // 比較するピクセルの末尾
  if ( maxPos >= chkMax ) maxPos = chkMax - 1;

  // 最小エネルギーとその位置を求める
  double eneMin = std::numeric_limits< double >::max(); // エネルギー最小値
  for ( int i = minPos ; i <= maxPos ; ++i ) {
    // c0との差分を取る対象ピクセルの位置
    Coord< int > c1 = ( isHorizontal ) ? Coord< int >( c0->x + 1, i ) : Coord< int >( i, c0->y + 1 );
    double energy = func( saliency, *c0, c1 ); // 差分を元にエネルギーを計算
    if ( eneMin > energy ) {
      eneMin = energy;
      minPos = i;
    }
  }

  // c0を次の位置に変更
  if ( isHorizontal ) {
    ++( c0->x );
    c0->y = minPos;
  } else {
    c0->x = minPos;
    ++( c0->y );
  }

  return( eneMin );
}

/*
  RemoveMinEnergyPixel : 走査方向と垂直な方向にピクセルを削除して詰める

  削除対象範囲が顕著性データのサイズと等しいとは限らないので、範囲の最大値 + 1 を示す chkMax を引数として持つ。
  chkMax は、isHorizontal が true なら Y 座標、false なら X 座標の最大値 + 1 を表す。

  draw : ピクセル削除対象の画像データへのポインタ
  saliency : ピクセル削除対象の顕著性データへのポインタ
  c0 : 対象のピクセルの位置
  chkMax : 削除対象範囲の最大値
  isHorizontal : 走査方向は水平か
*/
void RemoveMinEnergyPixel( DrawingArea_IF* draw, Matrix< double >* saliency, Coord< int > c0,
                           int chkMax, bool isHorizontal )
{
  // 現在位置(走査方向に垂直な成分)
  int curPos = ( isHorizontal ) ? c0.y : c0.x;
  // コピー元のピクセルの座標(下側または右側)
  Coord< int > c1( ( ( isHorizontal ) ? c0.x : c0.x + 1 ), ( ( isHorizontal ) ? c0.y + 1 : c0.y ) );

  // 走査方向と垂直な向きにピクセルを詰める
  RGB rgb;
  while ( ++curPos < chkMax ) {
    draw->point( c1, &rgb );
    draw->pset( c0, rgb );
    (*saliency)[c0.y][c0.x] = (*saliency)[c1.y][c1.x];
    if ( isHorizontal ) {
      ++( c0.y );
      ++( c1.y );
    } else {
      ++( c0.x );
      ++( c1.x );
    }
  }
  draw->pset( c0, RGB() );
}

/*
  AddMinEnergyPixel : 走査方向と垂直な方向にピクセルを追加して広げる

  追加対象範囲が顕著性データのサイズと等しいとは限らないので、範囲の最大値 + 1 を示す chkMax を引数として持つ。
  chkMax は、isHorizontal が true なら Y 座標、false なら X 座標の最大値 + 1 を表す。
  ピクセル追加の際、行・列のサイズはひとつ増えることになるが、必要な領域はあらかじめ用意されているとみなす。

  draw : ピクセル追加対象の画像データへのポインタ
  saliency : ピクセル追加対象の顕著性データへのポインタ
  c : 対象のピクセルの位置
  chkMax : 探索対象範囲の最大値
  isHorizontal : 走査方向は水平か
*/
void AddMinEnergyPixel( DrawingArea_IF* draw, Matrix< double >* saliency, Coord< int > c,
                        int chkMax, bool isHorizontal )
{
  // コピー元位置の末尾(走査方向に垂直な成分)を追加位置で初期化
  int chkMin = ( isHorizontal ) ? c.y : c.x;
  // コピー先のピクセルの座標(下側または右側)
  Coord< int > c1( ( ( isHorizontal ) ? c.x : chkMax ), ( ( isHorizontal ) ? chkMax : c.y ) );
  // コピー元のピクセルの座標
  Coord< int > c0( ( ( isHorizontal ) ? c1.x : c1.x - 1 ), ( ( isHorizontal ) ? c1.y - 1 : c1.y ) );

  // 走査方向と垂直な向きにピクセルを空ける
  RGB rgb;
  while ( chkMax-- > chkMin ) {
    draw->point( c0, &rgb );
    draw->pset( c1, rgb );
    (*saliency)[c1.y][c1.x] = (*saliency)[c0.y][c0.x];
    if ( isHorizontal ) {
      --( c0.y );
      --( c1.y );
    } else {
      --( c0.x );
      --( c1.x );
    }
  }
  // 空いた部分は上・左側のピクセルとの平均で埋める
  if ( isHorizontal && c.y > 0 ) {
    RGB rgb0, rgb1;
    draw->point( c, &rgb0 );
    draw->point( Coord< int >( c.x, c.y - 1 ), &rgb1 );
    draw->pset( c, RGB( ( static_cast< unsigned int >( rgb0.r ) + rgb1.r ) / 2, ( static_cast< unsigned int >( rgb0.g ) + rgb1.g ) / 2, ( static_cast< unsigned int >( rgb0.b ) + rgb1.b ) / 2 ) );
    (*saliency)[c.y][c.x] = ( (*saliency)[c.y][c.x] + (*saliency)[c.y - 1][c.x] ) / 2;
  } else if ( ( ! isHorizontal ) && c.x > 0 ) {
    RGB rgb0, rgb1;
    draw->point( c, &rgb0 );
    draw->point( Coord< int >( c.x - 1, c.y ), &rgb1 );
    draw->pset( c, RGB( ( static_cast< unsigned int >( rgb0.r ) + rgb1.r ) / 2, ( static_cast< unsigned int >( rgb0.g ) + rgb1.g ) / 2, ( static_cast< unsigned int >( rgb0.b ) + rgb1.b ) / 2 ) );
    (*saliency)[c.y][c.x] = ( (*saliency)[c.y][c.x] + (*saliency)[c.y][c.x - 1] ) / 2;
  }
}

/*
  SearchMinEnergyPath : 最もエネルギーの和が低くなるパスの探索

  探索対象範囲が顕著性データのサイズと等しいとは限らないので、範囲の最大値を示す chkMax を引数として持つ。
  chkMax は、isHorizontal が true なら Y 座標、false なら X 座標の最大値を表す。

  saliency : 対象の顕著性データへの参照
  chkMax : 探索対象範囲の最大値
  movMax : 走査方向の範囲の最大値
  func : ノルム計算用関数オブジェクト
  isHorizontal : 走査方向は水平か
  constraint : 探索する幅 ( ±constraint の幅のピクセルを対象に探索する )

  戻り値 最小値を取るパスの開始位置
*/
int SearchMinEnergyPath( const Matrix< double >& saliency, int chkMax, int movMax,
                         const EnergyFunction_Base& func, bool isHorizontal, int constraint )
{
  int minPos = 0; // 最小値を取るパスの開始位置

  double eneErrSumMin = std::numeric_limits< double >::max(); // パスのエネルギー和最小値
  for ( int i = 0 ; i < chkMax ; ++i ) {
    // エネルギー計算開始位置
    Coord< int > c = ( isHorizontal ) ?
    Coord< int >( 0, i ) : Coord< int >( i, 0 );
    // パスのエネルギー和
    // 二つの引数を開始位置として初期化する。通常のノルムの場合はゼロになる。
    double eneErrSum = func( saliency, c, c );

    // エネルギー和の計算
    for ( int j = 0 ; j < movMax - 1 ; ++j ) {
      eneErrSum += SearchMinEnergyPixel( saliency, &c, chkMax, func, isHorizontal, constraint );
      if ( eneErrSumMin < eneErrSum ) break;
    }

    // 最小値なら更新
    if ( eneErrSumMin > eneErrSum ) {
      eneErrSumMin = eneErrSum;
      minPos = i;
    }
  }

  return( minPos );
}

/*
  RemoveMinEnergyPath : 最もエネルギーの和が低くなるパスを削除する

  削除対象範囲が顕著性データのサイズと等しいとは限らないので、範囲の最大値を示す chkMax を引数として持つ。
  curPos, chkMax は、isHorizontal が true なら Y 座標、false なら X 座標の最大値を表す。

  draw : 対象の画像データへのポインタ
  saliency : 対象の顕著性データへのポインタ
  curPos : 処理開始位置
  chkMax : 探索対象範囲の最大値
  movMax : 走査方向の範囲の最大値
  func : ノルム計算用関数オブジェクト
  isHorizontal : 走査方向は水平か
  constraint : 探索する幅 ( ±constraint の幅のピクセルを対象に探索する )
*/
void RemoveMinEnergyPath( DrawingArea_IF* draw, Matrix< double >* saliency,
                          int curPos, int chkMax, int movMax,
                          const EnergyFunction_Base& func, bool isHorizontal, int constraint )
{
  // 処理開始位置
  Coord< int > c = ( isHorizontal ) ?
    Coord< int >( 0, curPos ) : Coord< int >( curPos, 0 );

  // ピクセルの削除処理
  for ( int j = 0 ; j < movMax - 1 ; ++j ) {
    // 座標をバッファ buff に代入して最小エネルギーのパスへ更新する
    Coord< int > buff( c );
    SearchMinEnergyPixel( *saliency, &c, chkMax, func, isHorizontal, constraint );
    // ピクセルを削除し、走査方向と垂直な方向に詰める
    RemoveMinEnergyPixel( draw, saliency, buff, chkMax, isHorizontal );
  }
  RemoveMinEnergyPixel( draw, saliency, c, chkMax, isHorizontal );
}

/*
  AddMinEnergyPath : 最もエネルギーの和が低くなるパスにピクセルを追加する

  追加対象範囲が顕著性データのサイズと等しいとは限らないので、範囲の最大値を示す chkMax を引数として持つ。
  curPos, chkMax は、isHorizontal が true なら Y 座標、false なら X 座標の最大値を表す。
  ピクセル追加の際、行・列のサイズはひとつ増えることになるが、必要な領域はあらかじめ用意されているとみなす。

  draw : 対象の画像データへのポインタ
  saliency : 対象の顕著性データへのポインタ
  curPos : 処理開始位置
  chkMax : 探索対象範囲の最大値
  movMax : 走査方向の範囲の最大値
  func : ノルム計算用関数オブジェクト
  isHorizontal : 走査方向は水平か
  constraint : 探索する幅 ( ±constraint の幅のピクセルを対象に探索する )
*/
void AddMinEnergyPath( DrawingArea_IF* draw, Matrix< double >* saliency,
                       int curPos, int chkMax, int movMax,
                       const EnergyFunction_Base& func, bool isHorizontal, int constraint )
{
  // 処理開始位置
  Coord< int > c = ( isHorizontal ) ?
    Coord< int >( 0, curPos ) : Coord< int >( curPos, 0 );

  // ピクセルの削除処理
  for ( int j = 0 ; j < movMax - 1 ; ++j ) {
    // 座標をバッファ c0 に代入して最小エネルギーのパスへ更新する
    Coord< int > buff( c );
    SearchMinEnergyPixel( *saliency, &c, chkMax, func, isHorizontal, constraint );
    // ピクセルを追加し、走査方向と垂直な方向に広げる
    AddMinEnergyPixel( draw, saliency, buff, chkMax, isHorizontal );
  }
  AddMinEnergyPixel( draw, saliency, c, chkMax, isHorizontal );
}

/*
  SeamCarving_Remove : シーム・カービング削除処理

  探索は一回の削除処理ごとに再度行う

  draw : 対象の画像データへのポインタ
  saliency : 対象の顕著性データへのポインタ
  removeCnt : 削除する行・列の数
  func : ノルム計算用関数オブジェクト
  isHorizontal : 走査方向は水平か
  constraint : 探索する幅 ( ±constraint の幅のピクセルを対象に探索する )
*/
void SeamCarving_Remove( DrawingArea_IF* draw, Matrix< double >* saliency, int removeCnt,
                         const EnergyFunction_Base& func, bool isHorizontal, int constraint )
{
  assert( draw != 0 && saliency != 0 && &func != 0 && constraint >= 0 );

  // 探索対象範囲の最大値
  int chkMax = ( isHorizontal ) ?
    std::min( static_cast< int >( saliency->rows() ), ( draw->size() ).y ) :
    std::min( static_cast< int >( saliency->cols() ), ( draw->size() ).x );
  // 走査方向の範囲の最大値
  int movMax = ( isHorizontal ) ?
    std::min( static_cast< int >( saliency->cols() ), ( draw->size() ).x ) :
    std::min( static_cast< int >( saliency->rows() ), ( draw->size() ).y );

  for ( int i = 0 ; i < removeCnt ; ++i ) {
    int removePos = SearchMinEnergyPath( *saliency, chkMax, movMax, func, isHorizontal, constraint );
    RemoveMinEnergyPath( draw, saliency, removePos, chkMax, movMax, func, isHorizontal, constraint );
    --chkMax;
  }
}

/*
  SeamCarving_Add : シーム・カービング追加処理

  探索は一回の追加処理ごとに再度行う

  draw : 対象の画像データへのポインタ
  saliency : 対象の顕著性データへのポインタ
  addCnt : 追加する行・列の数
  func : ノルム計算用関数オブジェクト
  isHorizontal : 走査方向は水平か
  constraint : 探索する幅 ( ±constraint の幅のピクセルを対象に探索する )
*/
void SeamCarving_Add( DrawingArea_IF* draw, Matrix< double >* saliency, int addCnt,
                      const EnergyFunction_Base& func, bool isHorizontal, int constraint )
{
  assert( draw != 0 && saliency != 0 && &func != 0 && constraint >= 0 );

  // 探索対象範囲の最大値
  int chkMax = ( isHorizontal ) ?
    std::min( static_cast< int >( saliency->rows() ), ( draw->size() ).y ) :
    std::min( static_cast< int >( saliency->cols() ), ( draw->size() ).x );
  // 走査方向の範囲の最大値
  int movMax = ( isHorizontal ) ?
    std::min( static_cast< int >( saliency->cols() ), ( draw->size() ).x ) :
    std::min( static_cast< int >( saliency->rows() ), ( draw->size() ).y );

  draw->resize( Coord< int >( ( isHorizontal ) ? movMax : chkMax + addCnt,
                              ( isHorizontal ) ? chkMax + addCnt : movMax ) );
  saliency->resize( ( isHorizontal ) ? chkMax + addCnt : movMax,
                    ( isHorizontal ) ? movMax : chkMax + addCnt );
  for ( int i = 0 ; i < addCnt ; ++i ) {
    int addPos = SearchMinEnergyPath( *saliency, chkMax, movMax, func, isHorizontal, constraint );
    AddMinEnergyPath( draw, saliency, addPos, chkMax, movMax, func, isHorizontal, constraint );
    ++chkMax;
  }
}

関数 SearchMinEnergyPixel は、次のパスへ進むことのできるピクセルの候補それぞれに対して現在位置からのエネルギー求め、その中から最小の値を取るピクセルの位置をそのエネルギー値とともに返します。候補にできるピクセルの範囲はメンバ変数 constraint で指定します。例えば、水平方向に左端から右方向へパスを走査する場合、constraint の値が 1 であれば、現在位置 p0 = ( x0, y0 ) に対して ( x0 + 1, y0 - 1 )、( x0 + 1, y0 )、( x0 + 1, y0 + 1 ) の三点が次のパスの候補となります。ここで constraint をゼロにすれば、パスはラインの形をとり、また 1 よりも大きな値とすることで、パスの連結が切断される形を許すようになります。isHorizontal は、パスの走査を水平・垂直どちらの方向で行うかを表したもので、true なら水平方向、false なら垂直方向であることを示しています。
SearchMinEnergyPixel は、戻り値としてエネルギーを返すだけではなく、引数として渡されたピクセルの現在位置 c0 も同時に更新していることに注意して下さい。エネルギーは、パス上の次の点として候補となる各ピクセルに対して計算し、その中の最小値を返します。この時、最小値を取るピクセル位置も同時に更新すれば、最小値を取るパスを連続して走査していくことができるようになります。また、エネルギーを求めるために、先に定義したエネルギー関数 EnergyFunction_Base を利用します。従って、引数としてエネルギー関数オブジェクトへの参照 func が渡されています。

SearchMinEnergyPath は、各開始位置ごとのエネルギー総和の中から最小となる位置を求めるための関数です。以下に、処理の例を示します。

図 3-1. パスの走査の様子
パスの走査の様子

上図は、水平方向のパスを上側から順次走査した時の様子を表したものです。各ピクセルにおけるエネルギーの最小値とそのピクセル位置を SearchMinEnergyPixel 関数で求めると、各開始位置ごとに赤色で示したパスが得られます。エネルギー最小値は図の上側に示した値で、その和が右側に示されています。エネルギーの和の中での最小値は赤色で示されています。上の図では、三つ目のパスまで走査が完了し、最小値を取るパスは二番目で、その値が 2.7 であることを示しています。

エネルギー最小値を取るパスの開始位置が分かれば、もう一度パスの走査を行いながらピクセルの除去や追加を行えばサイズの変更が可能になります。RemoveMinEnergyPathAddMinEnergyPath がその処理を行うための関数で、内部ではそれぞれ RemoveMinEnergyPixel, AddMinEnergyPixel を呼び出して、ピクセルの除去 ( 追加 ) と水平・垂直方向に詰める ( 広げる ) 処理を行います。
ピクセルの除去や追加は画像データと顕著性データの両方に対して行います。エネルギーの計算には顕著性データを利用するのに対し、実際に拡大・縮小を行うのは画像データになるからです。このとき、画像データと顕著性データのサイズは同じであることが前提になりますが、もしサイズが異なる場合に範囲外へのアクセスが発生することを避けるため、小さい側のサイズに合わせて処理を行うようにしています。SeamCarving_RemoveSeamCarving_Add がそのチェック作業を行い、SeamCarving_Add の場合は画像と顕著性データのリサイズを行った上で、パスの探索 ( SearchMinEnergyPath ) とピクセルの追加・削除 ( AddMinEnergyPath / RemoveMinEnergyPath ) を指定した回数分行います。

サンプル・プログラムを利用して、以下の画像に対して縮小処理をしてみます。これらの画像は、The USC-SIPI Image Database (http://sipi.usc.edu/database/index.html) から拝借したものです。どちらの画像も、実サイズは 512 x 512 になります。

図 3-2. シーム・カービング削除処理のテスト画像
SplashSailboat on lake
Splash 湖上のヨット

サイズを 3 / 4 に縮小した結果を以下に示します。シーム・カービング処理は、先に水平方向のパスを削除した後で、垂直方向のパスの削除を実施しています。下側には比較のために、バイリニア補間を使った通常の縮小処理を行った結果を示しています。

図 3-3. シーム・カービング削除処理の結果
シーム・カービング処理 ( L1 ノルム )
処理時間 3.78 sec処理時間 4.03 sec
Splash(Seam Carving L1-Norm) Sailboat on lake(Seam Carving L1-Norm)
シーム・カービング処理 ( L2 ノルム )
処理時間 4.48 sec処理時間 4.00 sec
Splash(Seam Carving L2-Norm) Sailboat on lake(Seam Carving L2-Norm)
通常の縮小処理(バイリニア補間)
Splash(bilinear) Sailboat on lake(bilinear)

左側のミルククラウンの写真は、王冠の画像に少し崩れた部分が見られますが比較的きれいに処理されています。周囲にある背景が削除され、ちょうどトリミングと同じような効果が得られています。右側の湖の写真は、個々のオブジェクトが中央に集められたような形でリサイズされており、木の間から見える湖の景色が狭まっているのが分かると思います。このように、個々のオブジェクトがバラバラに配置されていたとしても、それをうまく再配置するような作用がシーム・カービング処理によって得られます。
なお、L1 ノルムを使った場合、ミルククラウンの画像は縦につぶれたような状態になっています。左側の画像については L2 ノルムの方がきれいに処理されています。

上記処理は八連結パスに制限したものですが、この制限を緩めて ±5 までの範囲のピクセルから最小エネルギーを探索するようにしたところ、以下のような結果になりました。

図 3-4. シーム・カービング削除処理の結果 ( ±5 の探索幅 )
シーム・カービング処理 ( L1 ノルム )
処理時間 7.85 sec処理時間 7.12 sec
Splash(Seam Carving L1-Norm) Sailboat on lake(Seam Carving L1-Norm)
シーム・カービング処理 ( L2 ノルム )
処理時間 8.21 sec処理時間 6.41 sec
Splash(Seam Carving L2-Norm) Sailboat on lake(Seam Carving L2-Norm)

ある程度は予想できることですが、ノルム計算による差異よりも違いがはっきりとしていて、制限を緩めた分、より小さいエネルギーへ移動する自由度が増えるので、各オブジェクトがしっかりと残るようになりました。しかし、探索時間は長くなるので処理時間は倍増しています。

次に、以下の画像に対して拡大処理をしてみます。この画像も、The USC-SIPI Image Database (http://sipi.usc.edu/database/index.html) から拝借したものです。

図 3-5. シーム・カービング追加処理のテスト画像
Tree (実サイズ 256 x 256)
木

サイズを横方向にだけ 5 / 4 に拡大した結果を以下に示します。

図 3-6. シーム・カービング追加処理の結果
処理時間 0.228 sec
Tree(Seam Carving)

縮小(削除)処理とは異なり、拡大(追加)処理ではほとんど同じパス上のみに対して実行されるため、意図した結果にはなりません。追加したピクセルは周囲の平均値を元に色コードを決めていることから、エネルギーは低いままである傾向になり、毎回同じ箇所が選択されてしまうことになるわけです。追加処理を行うには、他の手法を行う必要があります。


4) 画像の拡大

エネルギーの和が最小となるパスを毎回決めて処理する場合、追加処理に対しては毎回ほぼ同じ箇所が選択されてしまうのは前の章で示した通りです。これを回避するために、エネルギーの低いパスを複数選択しておいて、それらを一度に処理しまう方法が考えられます。この場合、選択できるパスの候補は画像のサイズ ( 横または縦方向のピクセル数 ) 分までになり、全てのパスが選択された状態は、画像をちょうど二倍に拡大したのと同じことになります。

早速、サンプル・プログラムを示したいと思います。

/*
  GetEnergyPath : 各パスごとにエネルギーの和を求める

  探索対象範囲が顕著性データのサイズと等しいとは限らないので、範囲の最大値を示す chkMax を引数として持つ。
  chkMax は、isHorizontal が true なら Y 座標、false なら X 座標の最大値を表す。

  saliency : 対象の顕著性データへの参照
  index : 低いエネルギーを持った座標値のリスト(昇順でソートして返す)
  count : 取得する座標の数
  chkMax : 探索対象範囲の最大値
  movMax : 走査方向の範囲の最大値
  func : ノルム計算用関数オブジェクト
  isHorizontal : 走査方向は水平か
  constraint : 探索する幅 ( ±constraint の幅のピクセルを対象に探索する )
*/
void GetEnergyPath( const Matrix< double >& saliency, vector< int >* index,
                    int count, int chkMax, int movMax,
                    const EnergyFunction_Base& func, bool isHorizontal, int constraint )
{
  std::multimap< double, int > energy; // 各座標ごとのエネルギー和

  for ( int i = 0 ; i < chkMax ; ++i ) {
    // エネルギー計算開始位置
    Coord< int > c = ( isHorizontal ) ?
      Coord< int >( 0, i ) : Coord< int >( i, 0 );
    // パスのエネルギー和
    // 二つの引数を開始位置として初期化する。通常のノルムの場合はゼロになる。
    double eneErrSum = func( saliency, c, c );

    // エネルギー和の計算
    for ( int j = 0 ; j < movMax - 1 ; ++j )
      eneErrSum += SearchMinEnergyPixel( saliency, &c, chkMax, func, isHorizontal, constraint );

    energy.insert( pair< double, int >( eneErrSum, i ) );
  }

  // 低いエネルギーを持つ座標値を抽出する
  size_t sz = ( count < 0 ) ? 0 : count;
  if ( sz > energy.size() ) sz = energy.size();
  std::multimap< double, int >::const_iterator cit = energy.begin();
  index->resize( sz );
  for ( size_t i = 0 ; i < sz ; ++i ) {
    (*index)[i] = cit->second;
    ++cit;
  }
  std::sort( index->begin(), index->end() );
}

/*
  SeamCarving_OneTimeRemove : シーム・カービング削除処理

  探索は一度にまとめて行う

  draw : 対象の画像データへのポインタ
  saliency : 対象の顕著性データへのポインタ
  removeCnt : 削除する行・列の数
  func : ノルム計算用関数オブジェクト
  isHorizontal : 走査方向は水平か
  constraint : 探索する幅 ( ±constraint の幅のピクセルを対象に探索する )
*/
void SeamCarving_OneTimeRemove( DrawingArea_IF* draw, Matrix< double >* saliency, int removeCnt,
                                const EnergyFunction_Base& func, bool isHorizontal, int constraint )
{
  assert( draw != 0 && saliency != 0 && &func != 0 && constraint >= 0 );

  // 探索対象範囲の最大値
  int chkMax = ( isHorizontal ) ?
    std::min( static_cast< int >( saliency->rows() ), ( draw->size() ).y ) :
    std::min( static_cast< int >( saliency->cols() ), ( draw->size() ).x );
  // 走査方向の範囲の最大値
  int movMax = ( isHorizontal ) ?
    std::min( static_cast< int >( saliency->cols() ), ( draw->size() ).x ) :
    std::min( static_cast< int >( saliency->rows() ), ( draw->size() ).y );

  vector< int > index;
  GetEnergyPath( *saliency, &index, removeCnt, chkMax, movMax, func, isHorizontal, constraint );
  for ( size_t i = index.size() ; i > 0 ; --i ) {
    RemoveMinEnergyPath( draw, saliency, index[i - 1], chkMax, movMax, func, isHorizontal, constraint );
    --chkMax;
  }
}

/*
  SeamCarving_OneTimeAdd : シーム・カービング追加処理

  探索は一度にまとめて行う

  draw : 対象の画像データへのポインタ
  saliency : 対象の顕著性データへのポインタ
  addCnt : 追加する行・列の数
  func : ノルム計算用関数オブジェクト
  isHorizontal : 走査方向は水平か
  constraint : 探索する幅 ( ±constraint の幅のピクセルを対象に探索する )
*/
void SeamCarving_OneTimeAdd( DrawingArea_IF* draw, Matrix< double >* saliency, int addCnt,
                             const EnergyFunction_Base& func, bool isHorizontal, int constraint )
{
  assert( draw != 0 && saliency != 0 && &func != 0 && constraint >= 0 );

  // 探索対象範囲の最大値
  int chkMax = ( isHorizontal ) ?
    std::min( static_cast< int >( saliency->rows() ), ( draw->size() ).y ) :
    std::min( static_cast< int >( saliency->cols() ), ( draw->size() ).x );
  // 走査方向の範囲の最大値
  int movMax = ( isHorizontal ) ?
    std::min( static_cast< int >( saliency->cols() ), ( draw->size() ).x ) :
    std::min( static_cast< int >( saliency->rows() ), ( draw->size() ).y );

  draw->resize( Coord< int >( ( isHorizontal ) ? movMax : chkMax + addCnt,
                              ( isHorizontal ) ? chkMax + addCnt : movMax ) );
  saliency->resize( ( isHorizontal ) ? chkMax + addCnt : movMax,
                    ( isHorizontal ) ? movMax : chkMax + addCnt );

  vector< int > index;
  GetEnergyPath( *saliency, &index, addCnt, chkMax, movMax, func, isHorizontal, constraint );
  for ( size_t i = index.size() ; i > 0 ; --i ) {
    AddMinEnergyPath( draw, saliency, index[i - 1], chkMax, movMax, func, isHorizontal, constraint );
    ++chkMax;
  }
}

パスを複数個まとめて取得する処理は関数 GetEnergyPath で行っています。仕組みは単純で、STL ( Standard Template Library ) のコンテナ・クラス multimap を使ってエネルギー値をキーに座標値を登録し、その先頭の要素から必要数分だけ座標値を取り出して、最後に座標値でソートします。map, multimap はキーと値のペアを要素とする連想配列で、内部ではキーを使って自動的に昇順ソートされます。従って、登録が完了したらそのまま低いエネルギーを持った座標を取得することができます。但し、エネルギーが完全に等しいピクセルが存在する可能性もあるので、キーの重複を許す multimap の方を使っています。

座標値が取得できれば、順番に取り出して削除・追加処理を行うだけです。但し、上側から処理を行うと座標値がずれていくため、下側のピクセルから順に処理する必要があります。最後に座標値でソートする必要があるのはそのためです。なお、パスの移動方向もまとめて配列に保持しておくとエネルギー計算が一度で済むという利点がありますが、ピクセルの削除・追加によってパスが変化する場合もあるので一長一短があります。

下図は、上記サンプル・プログラムを使った拡大処理の結果です。先の結果と比較すると、一箇所だけに集中して画像が伸ばされてしまうような現象は回避できていることが分かると思います。

図 4-1. シーム・カービング追加処理の結果 (2)
処理時間 0.165 sec
Tree(Seam Carving)

下図は、削除処理を Splash 画像に対して試した結果です ( L1 ノルム使用 ; 八連結パス )。前の結果より形状は保たれた状態となり、一度にパスを走査することでエネルギーを計算する回数が少なくなるため処理時間も半分近くまで短縮できました。一回の処理ごとにパスを検索しなおす場合と、一気にエネルギーの低いパスを取得してしまう場合とでは結果に微妙な差が生じますが、それを無視すれば一括処理を行う方がパフォーマンス的にも有利になります。

図 4-2. シーム・カービング削除処理の結果 (2)
処理時間 2.17 sec
Splash(Seam Carving)

今回は、シーム・カービング処理そのものの考え方について紹介しました。この中で利用されている顕著性データやエネルギー関数については、文献の中では様々な手法が使われており、それらを切り替えることで、今回のやり方ではうまく処理できない画像に対しても有効となる可能性もあります。次回は、画像の顕著性を求めるための手法について紹介する予定です。


<修正履歴>
  1. サンプル・プログラムを少し変更しました。処理の内容そのものは変わっておらず、継承の仕方を少し見直しただけです (2009-11-03)。
  2. サンプル・プログラムを大幅に変更しました。大半をクラスから関数の形に置き換えてあります (2016-08-23)。
<参考文献>
  1. Shai Avidan, Ariel Shamir, (2007). "Seam Carving for Content-Aware Image Resizing"
  2. Wikipedia

[Go Back]前に戻る [Back to HOME]タイトルに戻る
inserted by FC2 system