グラフィック・パターンの扱い (6) スーパーサンプリング

前章では、補間処理を利用した拡大・縮小処理の高画質化を行ってきましたが、補間処理とは異なる方法を使ったエイリアシングの抑制(アンチエイリアシング; Anti-aliasing)として、この章では「スーパーサンプリング(Supersampling)」を紹介したいと思います。

補間処理は、ピクセルの値を利用して連続関数を再現し、ピクセル間の値を求めることによって任意の位置の色コードを決めていました。どの処理についても共通していることとして、ピクセルと同じ位置の値は変化しないということがあります。そのため、例えば画像を縦横ちょうど半分のサイズに縮小するような場合、最近傍法を含むどの補間処理を利用しても結果は同じであり、画像の中の 1/4 の情報は切り捨てられてしまいます。
前の章の最初に紹介した「任意の比率での拡大・縮小処理」において、縮小処理では周囲のピクセルと合成することによって情報の欠落を抑えていました。任意の大きさにサイズを変更する場合、ピクセルをある大きさを持った一つの格子と考え、画像をその格子の集まりとして扱って、変換するサイズに合うように分割した上で、それぞれの中に含まれている元のピクセルの値をその面積比に従って合成することによって上記問題を改善させる方法があります。この方法に対する正しい名称はハッキリとは分からなかったのですが、日本では「平均画素法」として紹介されています。
また、擬似的に高解像度な画像として処理を行う手法を「スーパーサンプリング(Supersampling)」といいます。「平均画素法」はスーパーサンプリングの一つと考えることができます。

1) 平均画素法

平均画素法とは、変換前のピクセル数と変換後のピクセル数の最小公倍数を求め、それを擬似的な解像度として処理を行なう方法です。例えば、変換前が 150、それに対して変換後が 100 であれば、その最小公倍数は 300 になるので、疑似解像度を 300 とします(つまり、画像を 2倍に拡大したことになります)。これを 1/3 に縮小すれば、実際に求めたいサイズの 100 になります。よって、パターンからピクセルを読み込む速度を 1/2 (つまり 2回同じピクセルを読み込んだら次のピクセルに進む)として、読み込んだ三つの値から平均値を算出して描画する処理を繰り返すことによってパターンを縮小します。
しかし、変換前と変換後のサイズが互いに素である(共通の約数を持たない)場合などを考えると、解像度が非常に大きくなる可能性があります。極端な例として、1024 から 1023 に縮小する場合、疑似解像度は 1047552 になり、画像を 1023倍に拡大したことになります。しかも、画像は二次元なので、縦横とも同じ比率である場合、さらに二乗の約 10¹² にもなります。これだけの回数だけ処理を繰り返すのは現実的ではないので、処理方法をもう少し工夫する必要があります。

パターンを二倍に拡大して三つのピクセルから平均値を計算する前述の例は、最初のピクセルと次のピクセルの色コードを 2 : 1 の比率で合成する処理と同等です。ピクセルを点ではなく格子として扱い、全体の大きさがそろうように変換前と変換後との画像を重ね合わせたとします。この時、パターン上のピクセルに対して変換後のピクセルが重なった部分の色コードと面積を求めて、面積の比率から色を合成するようにすれば、どのような比率で拡大・縮小を行なっても処理速度に影響することはなくなります。

上図は、画像を 5/7 倍に縮小処理した場合の格子の変化を表したもので、黒枠の格子が変換前、赤枠の格子が変換後になります。左上端の赤枠格子の中には、四つの黒枠格子が重なっており、それぞれの面積は、ピクセル一つを 1としたとき 1, 0.4, 0.4, 0.16 になります。したがって、色成分にそれぞれの面積比を掛けた後、面積比の和である 1.96で除算することで、求めたい色成分を得ることができます。

平均画素法を利用した拡大・縮小処理のサンプル・プログラムを以下に示します。

/*
  GPattern::ssXLoop : 平均画素法 x成分方向の処理

  Coord<int> p : パターン上の読み込み開始位置
  double dx : 矩形の大きさ(x成分)
  const Coord<double>& u : 左側の端数分と、Y成分の格子の長さ
  double rgb[3] : 求める色コード
*/
void GPattern::ssXLoop( Coord<int> p, double dx, const Coord<double>& u, double rgb[3] )
{
  RGB c = point( p );

  // 左端の処理
  rgb[0] += (double)( c.r() ) * u.x * u.y;
  rgb[1] += (double)( c.g() ) * u.x * u.y;
  rgb[2] += (double)( c.b() ) * u.x * u.y;

  // 中央の処理
  for ( dx -= u.x ; dx > 1.0 ; dx -= 1.0 ) {
    ++( p.x );
    c = point( p );
    rgb[0] += (double)( c.r() ) * u.y;
    rgb[1] += (double)( c.g() ) * u.y;
    rgb[2] += (double)( c.b() ) * u.y;
  }

  // 右端の処理
  rgb[0] += (double)( c.r() ) * dx * u.y;
  rgb[1] += (double)( c.g() ) * dx * u.y;
  rgb[2] += (double)( c.b() ) * dx * u.y;
}

/*
  GPattern::ssMain : 平均画素法メイン・ルーチン

  const Coord<double>& p : パターンから読み込む範囲の左上座標
  Coord<double> d : 読み込む範囲の大きさ

  戻り値 : 求めた色コード
*/
RGB GPattern::ssMain( const Coord<double>& p, Coord<double> d )
{
  // pを含む格子の座標
  Coord<int> ip( (int)( p.x ), (int)( p.y ) );

  // 格子から色を抽出する面積(一つの格子を1とする)
  Coord<double> u( (double)( ip.x + 1 ) - p.x, (double)( ip.y + 1 ) - p.y );
  // 求めた uが全体の抽出幅より大きい場合(一つの格子のみで抽出する場合)の処理
  if ( u.x > d.x ) u.x = d.x;
  if ( u.y > d.y ) u.y = d.y;

  // 求める色コード
  double rgb[3] = { 0, 0, 0 };

  // d.yの値を退避
  double dy = d.y;

  // 上端の処理
  ssXLoop( ip, d.x, u, rgb );
  // 中央の処理
  for ( d.y -= u.y ; d.y > 1.0 ; d.y -= 1.0 ) {
    ++( ip.y );
    ssXLoop( ip, d.x, Coord<double>( u.x, 1.0 ), rgb );
  }
  // 下端の処理
  ++( ip.y );
  ssXLoop( ip, d.x, Coord<double>( u.x, d.y ), rgb );

  // 面積で徐算
  rgb[0] /= d.x * dy;
  rgb[1] /= d.x * dy;
  rgb[2] /= d.x * dy;

  // 範囲外であった場合に補正
  for ( int i = 0 ; i < 3 ; ++i ) {
    if ( rgb[i] < 0 ) rgb[i] = 0;
    if ( rgb[i] > UCHAR_MAX ) rgb[i] = UCHAR_MAX;
  }

  return( RGB( (unsigned char)rgb[0], (unsigned char)rgb[1], (unsigned char)rgb[2] ) );
}

/*
  GPattern::ssResizePut : パターンの拡大・縮小描画(平均画素法)

  GPSet& pset : 描画用関数オブジェクト
  Coord<int>& s, e : パターンの描画開始・終了位置
  iterator_base& x, y : 描画方向
*/
void GPattern::ssResizePut( GPSet& pset, Coord<int>& s, Coord<int>& e, iterator_base& x, iterator_base& y )
{
  if ( size.x == 0 || size.y == 0 ) return;

  // 描画オブジェクトの大きさを取得
  Coord<int> dSize = pset.size();

  // 左上・右下の大小関係が逆の場合は入れ替える
  if ( s.x > e.x ) swap( s.x, e.x );
  if ( s.y > e.y ) swap( s.y, e.y );

  // 描画範囲内か
  if ( s.x >= dSize.x || s.y >= dSize.y ) return;
  if ( e.x < 0 || e.y < 0 ) return;

  // パターン読み取り位置
  Coord<double> p( 0, 0 );
  // 拡大・縮小率
  Coord<double> d;
  d.x = (double)( size.x ) / (double)( e.x - s.x + 1 );
  d.y = (double)( size.y ) / (double)( e.y - s.y + 1 );

  /*
    クリッピング処理
    s.x=e.x, s.y=e.y のときは、これらの処理は必ず行なわれないので、ゼロ除算チェックは不要
  */
  if ( s.x < 0 ) {
    p.x -= (double)( s.x ) * d.x ;
    s.x = 0;
  }
  if ( s.y < 0 ) {
    p.y -= (double)( s.y ) * d.y;
    s.y = 0;
  }
  if ( e.x >= dSize.x ) e.x = dSize.x - 1;
  if ( e.y >= dSize.y ) e.y = dSize.y - 1;

  // 描画処理
  for ( y.set( s.y, e.y ) ; y.valid() ; y.next() ) {
    double pxBuff = p.x;
    for ( x.set( s.x, e.x ) ; x.valid() ; x.next() ) {
      pset.col = ssMain( p, d );
      pset( Coord<int>( x.value(), y.value() ) );
      p.x += d.x;
    }
    p.x = pxBuff;
    p.y += d.y;
  }
}

メイン・ルーチンは ssResizePut になります。処理の内容は、今までのものとほとんど同じであり、色コードを求めるために ssMainを呼び出しています。ssMainは、パターンから色コードを読み込む範囲の開始位置とその大きさを受け取り、先に述べた手順に従って色コードを合成して、その結果を返します。読み込む範囲は、x, y方向ともに複数のピクセルにまたがるため、x方向の部分の処理を ssXLoopが行い、上端部分と中央、そして下端部分に分けて ssXLoopを呼び出しています。ssXLoopではさらに、左端部分と中央、そして右端部分について、面積比を元に色成分を加算する処理を行ないます。最後に、加算した結果を面積で割れば、全体の平均値を求めることができます。

2) 疑似解像度

平均画素法は、拡大・縮小処理に利用できる方法ですが、回転処理や自由変形処理などにも有効な方法として「疑似解像度」の概念を利用する方法があります。
グラフィック画面に描画できるピクセルの個数は、利用しているグラフィックボードやディスプレイ、またソフトウェアなどによって変化します。例えば、VGAという規格では、解像度が 640 x 480 と定められているため、そのピクセル数は 307200 になります。しかし、これは表示上の制限であり、画像処理をする上では解像度をいくらでも大きくすることができます(実際の解像度に対して、以下これを疑似解像度と呼びます)。よって、パターンの大きさが実際のサイズよりも数倍あると仮定して処理を行い、処理後に実際のサイズに縮小することで、エイリアシングを抑えることができます。

疑似解像度を使用する場合、ピクセルを分割した後の仮想画面をメモリ上に用意する必要があります。しかし、実際に解像度の何倍ものメモリを確保するのはもったいないので (例えば、1024 x 768 の解像度で True Color (24bit) の場合、1024 x 768 x 3 Byte = 2.25 MB なので、2 x 2 に分割したとしても 4倍の 9MB が必要)、確保するサイズは実際の解像度と同様として、処理結果はそれぞれのバッファに加算していき、なおかつ加算した回数をカウントする方法を使います。つまり、色合成の加算部分を先に済ませておくような形になります。処理が完了したら、加算した回数分だけ各色成分の要素を割ってから色合成してやり、それを実画面にプロットすれば処理は終りです。

疑似解像度であるといっても描画領域に変わりはないので、DrawingArea_IF(描画用オブジェクト用基底クラス)からの派生クラスとして用意すれば、今まで作成した拡大・縮小、回転、自由変形ルーチンがそのまま利用できます。描画した後、元のサイズに変換して実際の描画領域に書き込めばいいわけです。

疑似解像度を持つ描画領域クラスのサンプル・コードを以下に示します。

/**************************************************************
 SuperSamplingPattern : Supersampling用パターン
**************************************************************/

class SuperSamplingPattern : public DrawingArea_IF
{
protected:

  // パターンの要素の型
  struct Pixel {
    unsigned int r;   // RGB成分
    unsigned int g;
    unsigned int b;
    unsigned int cnt; // 加算回数
    Pixel() : r( 0 ), g( 0 ), b( 0 ), cnt( 0 ) {}
  };
  bool point( Coord<int> rc, Pixel& pixel ) const; // Pixelの取得

private:

  vector<Pixel> pattern; // 矩形パターン
  Coord<int> patSize;    // 矩形パターンのサイズ
  int mag;               // 実サイズに対する疑似解像度の倍率

public:

  /*
    コンストラクタ

    Coord<int> sz : パターンの実際の大きさ
    int mag : 倍率(疑似解像度との比率)
  */
  SuperSamplingPattern( const Coord<int>& sz, int _mag = 1 );

  /*
    要素を消去して初期化する
  */
  void init() { pattern.assign( pattern.size(), Pixel() ); }
  void init( int _mag ) { init(); if ( _mag > 0 ) mag = _mag; }

  /*
    パターン内の色コードの取得と設定(override)
  */
  bool point( Coord<int> rc, RGB& col ) const;
  bool pset( Coord<int> c, const RGB& col );

  /*
    疑似パターン・サイズの取得(override)
  */
  Coord<int> size() const { return( Coord<int>( patSize.x * mag, patSize.y * mag ) ); }

  /*
    実パターン・サイズの取得
  */
  Coord<int> realSize() const { return( patSize ); }

  /*
    パターンの描画
  */
  void put( GPSet& pset, Coord<int> s );
};

/*
  SuperSamplingPatternコンストラクタ

  const Coord<int>& sz : 実パターンのサイズ
  int _mag : 疑似サイズとの比率(倍率)
*/
SuperSamplingPattern::SuperSamplingPattern( const Coord<int>& sz, int _mag )
  : patSize( sz ), mag( _mag )
{
  if ( realSize().x < 0 ) patSize.x = 0;
  if ( realSize().y < 0 ) patSize.y = 0;

  if ( realSize().x > 0 && realSize().y > 0 )
    pattern.resize( realSize().x * realSize().y );
}

/*
  SuperSamplingPattern::point : パターンのPixel値を取得する

  指定した座標がパターン外部の場合、もっとも近いピクセルのPixel値を取得する

  Coord<int> rc : 取得する位置(実サイズ上)
  Pixel& pixel : 取得したPixel値

  戻り値 : 座標がパターンの範囲外だった場合は falseを返す
*/
bool SuperSamplingPattern::point( Coord<int> rc, Pixel& pixel ) const
{
  bool ans = true;

  if ( rc.x < 0 || rc.x >= realSize().x || rc.y < 0 || rc.y >= realSize().y ) {
    ans = false;
    if ( rc.x < 0 ) rc.x = 0;
    if ( rc.x >= realSize().x ) rc.x = realSize().x - 1;
    if ( rc.y < 0 ) rc.y = 0;
    if ( rc.y >= realSize().y ) rc.y = realSize().y - 1;
  }

  pixel = pattern[rc.y * realSize().x + rc.x];

  return( ans && ( pixel.cnt > 0 ) );
}

/*
  SuperSamplingPattern::point : パターンの色コードを取得する

  指定した座標がパターン外部の場合、もっとも近いピクセルの色コードを取得する

  Coord<int> rc : 取得する位置(実サイズ上)
  RGB& col : 取得した色コード

  戻り値 : 座標がパターンの範囲外か、またはパターン内に色コードが格納されていなかった場合は falseを返す
*/
bool SuperSamplingPattern::point( Coord<int> rc, RGB& col ) const
{
  unsigned int rgb[3] = { 0, 0, 0 };
  Pixel pixel;

  if ( ! point( rc, pixel ) ) {
    col = RGB( 0, 0, 0 );
    return( false );
  }

  rgb[0] = roundHalfUp( (double)( pixel.r ) / (double)( pixel.cnt ) );
  rgb[1] = roundHalfUp( (double)( pixel.g ) / (double)( pixel.cnt ) );
  rgb[2] = roundHalfUp( (double)( pixel.b ) / (double)( pixel.cnt ) );

  // 範囲外であった場合に補正
  for ( int i = 0 ; i < 3 ; ++i )
    if ( rgb[i] > UCHAR_MAX ) rgb[i] = UCHAR_MAX;

  col = RGB( rgb[0], rgb[1], rgb[2] );

  return( true );
}

/*
  SuperSamplingPattern::pset : パターンへの描画

  指定した座標がパターン外部の場合は処理しない

  Coord<int> c : 描画する位置(疑似サイズ上)
  const RGB& col : 描画する色コード

  戻り値 : 座標がパターンの範囲外ならば falseを返す
*/
bool SuperSamplingPattern::pset( Coord<int> c, const RGB& col )
{
  Coord<int> rc( c.x / mag, c.y / mag );
  if ( rc.x < 0 || rc.x >= realSize().x || rc.y < 0 || rc.y >= realSize().y )
    return( false );

  pattern[rc.y * realSize().x + rc.x].r += col.r();
  pattern[rc.y * realSize().x + rc.x].g += col.g();
  pattern[rc.y * realSize().x + rc.x].b += col.b();
  ++( pattern[rc.y * realSize().x + rc.x].cnt );

  return( true );
}

/*
  SuperSamplingPattern::put : パターンの描画

  GPSet& pset : 描画用関数オブジェクト
  Coord<int> s : パターンの描画開始位置
*/
void SuperSamplingPattern::put( GPSet& pset, Coord<int> s )
{
  // 描画オブジェクトの大きさを取得
  Coord<int> dSize = pset.size();

  // 描画開始位置はクリッピングエリア範囲内か
  if ( s.x >= dSize.x || s.y >= dSize.y ) return;

  // パターンサイズを読み込んで右下の座標を決定
  Coord<int> e( s.x + realSize().x - 1, s.y + realSize().y - 1 );

  // パターンはクリッピングエリア範囲内か
  if ( e.x < 0 || e.y < 0 ) return;

  // パターンからの読み込み位置
  Coord<int> p( 0, 0 );

  // クリッピング処理
  if ( s.x < 0 ) {
    p.x -= s.x;
    s.x = 0;
  }
  if ( e.x >= dSize.x )
    e.x = dSize.x - 1;
  if ( s.y < 0 ) {
    p.y -= s.y;
    s.y = 0;
  }
  if ( e.y >= dSize.y )
    e.y = dSize.y - 1;

  // パターンの描画
  int pxBuff = p.x;
  for ( ; s.y <= e.y ; ++( s.y ) ) {
    for ( int x = s.x ; x <= e.x ; ++x ) {
      if ( point( p, pset.col ) )
        pset( Coord<int>( x, s.y ) );
      ++( p.x );
    }
    p.x = pxBuff;
    ++( p.y );
  }
}

DrawingArea_IF は純粋仮想関数として、描画領域の色コードを取得する point、描画領域のドットを描画する pset、描画領域のサイズを返す size の三つが用意されていました ( 「(1) パターンの取り込みと描画」サンプルコード参照 )。よって、これらのメンバ関数は上書き(override)する必要があります。この DrawingArea_IF の派生クラスとして、SuperSamplingPattern を定義します。まず、構造体 Pixel を用意して、この中に RGB 各成分を保存する変数 r, g, b と、描画した(各成分に加算した)回数をカウントするための変数 cnt を保持します。メンバ変数として、構造体 Pixel を要素とする vector 型のバッファである pattern と、矩形パターンのサイズ(これは疑似解像度ではなく、実際に描画可能な領域のサイズを保持します)である patSize、そして最後に、疑似解像度との比率を表す倍率 mag を用意します。なお、構造体 Pixel型は派生クラスで利用する予定なので、アクセス指定子を protected としています。
pset 関数は、指定した座標に色コードを渡すために利用します。ここでの座標値は擬似解像度に対する値を取ります。前述の通り、実際に用意された配列は疑似解像度に対するものではないので、まずは座標値を実サイズに変換します。これは、座標値を magで割るだけで得ることができます。あとは、対象のバッファに色コードを加算して、カウンタを一つ増やすだけです。point関数は二つ用意されていて、後半の公開されている側は指定した座標上のピクセルに対する色コードを計算して渡します。ここでの座標値は psetの場合と異なり、実サイズに対する値を渡します。対象のバッファから RGB各成分を取得したら、それをカウンタで割ってから色コードとして合成し、結果を返します。この時、カウンタがゼロであればピクセルは描画されなかったことになるので、色コードは RGB成分が全てゼロとした値を渡し、戻り値を falseとします。描画されなかった箇所は透明色として描画したくない場合、戻り値を利用して判定することができます。もう一方の限定公開されたメンバ関数は、Pixel型の値を返すために利用するもので、派生クラス内で使うことを想定しています。
最後に、パターンを描画するためのメンバ関数として、putが用意されています。この中では、描画されていない箇所を透明色として扱い、描画はしないようになっています。

GPattern インスタンスにパターンを保持したら、通常の描画領域ではなく SuperSamplingPattern インスタンスに描画を行ないます。この時、GPattern クラスが持つどんなメンバ関数でも利用できるので、例えば拡大・縮小ルーチン一つを取ってみても、サンプル補間を利用したルーチンなどを使うことも可能です。以下に使用例を示しておきます。

Coord<int> size( 1024, 768 ); // 画像サイズ

// 描画領域 ( DrawingArea は DrawingArea_IF の派生クラス )
// 引数として画像サイズを渡す
DrawingArea Draw( size );

// ここで Draw に対して何らかの画像を描画

// 画像パターンの取得(左上側 1/4 を抽出)
GPattern pat( Draw, Coord<int>( 0, 0 ), Coord<int>( size.x / 2 - 1, size.y / 2 - 1 ) );

SuperSamplingPattern ssp( size(), 5 ); // 疑似解像度用パターン(5倍の解像度)
GPSet sspg( ssp );                     // ssp用の点描画オブジェクト
// パターンを二倍(擬似的には10倍)に拡大処理
pat.resizePut( sspg, Coord<int>( 0, 0 ), Coord<int>( size.x * 5 - 1, size.y * 5 - 1 ), nn );

GPSet g( Draw ); // Draw用の点描画オブジェクト
// Drawに処理結果を出力
ssp.put( g, Coord<int>( 0, 0 ) );

3) 誤差拡散法 (Error Diffusion Method)

疑似解像度を利用することで、かなり画質のよい変換結果を得ることができるようになります。しかし、色数の少ない環境で処理を行なった場合、縞状の模様が発生することがあります。下図は、過去に、x68030 (色数 65536 色) で自由変形を 16 倍の疑似解像度にて行なったときの結果です。元の画像は球体で、変換結果の後ろ側にその 1/4 が表示されています。それを中央でねじった形で縮小した結果を見ると、表面上に縞模様が発生しています。

疑似解像度を利用する方法では、いくつかのピクセルの色コードから求めた平均値を使って点描画を行なっているため、どうしても誤差が発生します。例えば、拡大・縮小処理を N倍の疑似解像度で行なった場合、一つのピクセルに集められる色コードは N²個になるので、点描画を行なうときは N²で割って平均値を求めることになって、その時の剰余が誤差になります。先ほどのサンプル・プログラムでは求めた値を四捨五入して整数化しているので、誤差は ± N² / 2 の範囲内の値を取ります。色コードに対する階調も N² 倍あれば、和の値をそのまま利用することができることから、平均化の処理は、階調を落とす操作である「二値化」や「減色化」とほぼ同じ処理であると見ることもできます。このような場合に、画像の劣化を抑える手段として「誤差拡散法(Error Diffusion Method)」があります。

誤差拡散法は、切り捨てられた下位ビットの値を周囲のピクセルに分配して画像の劣化を抑える手法です。ビットを切り捨てることによって階調は連続的に変化しなくなり、それによって縞模様は発生します。誤差を周囲に散らすことによって、擬似的に連続した変化に見えるようにしているわけです。
切り捨てられる端数分の"散らし方"はいくつかあります。参考文献 1 に紹介されていた方法は、端数の半分を現在位置の右隣、1/4 を右下、1/8 を左下、そして残りを下側に分配しています。他にも以下のような分配方法があります。

誤差拡散法を利用したパターン描画用のサンプル・プログラムを以下に示します。

/********************************************************************
 SSP_ErrorDiffusion : 誤差拡散法を利用したSupersampling用パターン
********************************************************************/

class SSP_ErrorDiffusion : public SuperSamplingPattern
{
public:

  /*
    コンストラクタ

    Coord<int> sz : パターンの実際の大きさ
    int mag : 倍率(疑似解像度との比率)
  */
  SSP_ErrorDiffusion( const Coord<int>& sz, int _mag = 1 )
    : SuperSamplingPattern( sz, _mag ) {}

  /*
    パターン内の色コードの取得(override)
  */
  bool point( Coord<int> c, RGB& col ) const;
};

/**********************************************************************************
 SSP_FloydSteinberg : FloydSteinberg型誤差拡散法を利用したSupersampling用パターン
**********************************************************************************/

class SSP_FloydSteinberg : public SuperSamplingPattern
{
public:

  /*
    コンストラクタ

    Coord<int> sz : パターンの実際の大きさ
    int mag : 倍率(疑似解像度との比率)
  */
  SSP_FloydSteinberg( const Coord<int>& sz, int _mag = 1 )
    : SuperSamplingPattern( sz, _mag ) {}

  /*
    パターン内の色コードの取得(override)
  */
  bool point( Coord<int> c, RGB& col ) const;
};

/********************************************************************************
 SSP_JJN : Jarvis, Judice & Ninke型誤差拡散法を利用したSupersampling用パターン
********************************************************************************/

class SSP_JJN : public SuperSamplingPattern
{
public:

  /*
    コンストラクタ

    Coord<int> sz : パターンの実際の大きさ
    int mag : 倍率(疑似解像度との比率)
  */
  SSP_JJN( const Coord<int>& sz, int _mag = 1 )
    : SuperSamplingPattern( sz, _mag ) {}

  /*
    パターン内の色コードの取得(override)
  */
  bool point( Coord<int> c, RGB& col ) const;
};

/****************************************************************
 SSP_ErrorDiffusion : Supersampling用パターン(誤差拡散法適用版)
****************************************************************/

/*
  SSP_ErrorDiffusion::point : パターンの色コードを取得する

  指定した座標がパターン外部の場合、もっとも近いピクセルの色コードを取得する
  剰余を周囲に分散して加算する

      画素 1/2
  1/8 残り 1/4

  Coord<int> c : 取得する位置(実サイズ上)
  RGB& col : 取得した色コード

  戻り値 : 座標がパターンの範囲外か、またはパターン内に色コードが格納されていなかった場合は falseを返す
*/
bool SSP_ErrorDiffusion::point( Coord<int> c, RGB& col ) const
{
  Pixel pixel;
  Pixel buff;
  if ( ! SuperSamplingPattern::point( c, pixel ) )
    return( false );

  unsigned int rgb[3] = {
    pixel.r / pixel.cnt,
    pixel.g / pixel.cnt,
    pixel.b / pixel.cnt,
  };
  // 範囲外であった場合に補正
  for ( int i = 0 ; i < 3 ; ++i )
    if ( rgb[i] > UCHAR_MAX ) rgb[i] = UCHAR_MAX;
  col = RGB( rgb[0], rgb[1], rgb[2] );

  // 端数を取得
  pixel.r %= pixel.cnt;
  pixel.g %= pixel.cnt;
  pixel.b %= pixel.cnt;

  // 右側に端数の半分を加算
  buff.r = pixel.r >> 1;
  buff.g = pixel.g >> 1;
  buff.b = pixel.b >> 1;
  buff.cnt = pixel.cnt;
  const_cast<SSP_ErrorDiffusion&>( *this ).add( Coord<int>( c.x + 1, c.y ), buff );
  pixel.r -= buff.r;
  pixel.g -= buff.g;
  pixel.b -= buff.b;

  // 右下側に端数の1/4を加算
  buff.r >>= 1;
  buff.g >>= 1;
  buff.b >>= 1;
  const_cast<SSP_ErrorDiffusion&>( *this ).add( Coord<int>( c.x + 1, c.y + 1 ), buff );
  pixel.r -= buff.r;
  pixel.g -= buff.g;
  pixel.b -= buff.b;

  // 左下側に端数の1/8を加算
  buff.r >>= 1;
  buff.g >>= 1;
  buff.b >>= 1;
  const_cast<SSP_ErrorDiffusion&>( *this ).add( Coord<int>( c.x - 1, c.y + 1 ), buff );
  pixel.r -= buff.r;
  pixel.g -= buff.g;
  pixel.b -= buff.b;

  // 下側に端数の残りを加算
  const_cast<SSP_ErrorDiffusion&>( *this ).add( Coord<int>( c.x, c.y + 1 ), pixel );

  return( true );
}

/***********************************************************************************
 SSP_FloydSteinberg : Supersampling用パターン(Floyd & Steinberg型誤差拡散法適用版)
***********************************************************************************/

/*
  SSP_FloydSteinberg::point : パターンの色コードを取得する

  指定した座標がパターン外部の場合、もっとも近いピクセルの色コードを取得する
  剰余を周囲に分散して加算する

       画素 7/16
  3/16 5/16 1/16

  Coord<int> c : 取得する位置(実サイズ上)
  RGB& col : 取得した色コード

  戻り値 : 座標がパターンの範囲外か、またはパターン内に色コードが格納されていなかった場合は falseを返す
*/
bool SSP_FloydSteinberg::point( Coord<int> c, RGB& col ) const
{
  Pixel pixel;
  Pixel buff;
  if ( ! SuperSamplingPattern::point( c, pixel ) )
    return( false );

  unsigned int rgb[3] = {
    pixel.r / pixel.cnt,
    pixel.g / pixel.cnt,
    pixel.b / pixel.cnt,
  };
  // 範囲外であった場合に補正
  for ( int i = 0 ; i < 3 ; ++i )
    if ( rgb[i] > UCHAR_MAX ) rgb[i] = UCHAR_MAX;
  col = RGB( rgb[0], rgb[1], rgb[2] );

  // 端数を取得
  pixel.r %= pixel.cnt;
  pixel.g %= pixel.cnt;
  pixel.b %= pixel.cnt;

  // 右側に端数の7/16を加算
  buff.r = ( pixel.r * 7 ) >> 4;
  buff.g = ( pixel.g * 7 ) >> 4;
  buff.b = ( pixel.b * 7 ) >> 4;
  buff.cnt = pixel.cnt;
  const_cast<SSP_FloydSteinberg&>( *this ).add( Coord<int>( c.x + 1, c.y ), buff );

  // 左下側に端数の3/16を加算
  buff.r = ( pixel.r * 3 ) >> 4;
  buff.g = ( pixel.g * 3 ) >> 4;
  buff.b = ( pixel.b * 3 ) >> 4;
  const_cast<SSP_FloydSteinberg&>( *this ).add( Coord<int>( c.x - 1, c.y + 1 ), buff );

  // 下側に端数の5/16を加算
  buff.r = ( pixel.r * 5 ) >> 4;
  buff.g = ( pixel.g * 5 ) >> 4;
  buff.b = ( pixel.b * 5 ) >> 4;
  const_cast<SSP_FloydSteinberg&>( *this ).add( Coord<int>( c.x - 1, c.y + 1 ), buff );

  // 右下側に端数の1/16を加算
  pixel.r >>= 4;
  pixel.g >>= 4;
  pixel.b >>= 4;
  const_cast<SSP_FloydSteinberg&>( *this ).add( Coord<int>( c.x + 1, c.y + 1 ), pixel );

  return( true );
}

/*********************************************************************************
 SSP_JJN : Supersampling用パターン(Jarvis, Judice & Ninke型誤差拡散法適用版)
*********************************************************************************/

/*
  SSP_JJN::point : パターンの色コードを取得する

  指定した座標がパターン外部の場合、もっとも近いピクセルの色コードを取得する
  剰余を周囲に分散して加算する

            画素 7/48 5/48
  3/48 5/48 7/48 5/48 3/48
  1/48 3/48 5/48 3/48 1/48

  Coord<int> c : 取得する位置(実サイズ上)
  RGB& col : 取得した色コード

  戻り値 : 座標がパターンの範囲外か、またはパターン内に色コードが格納されていなかった場合は falseを返す
*/
bool SSP_JJN::point( Coord<int> c, RGB& col ) const
{
  Pixel pixel;
  Pixel buff;
  if ( ! SuperSamplingPattern::point( c, pixel ) )
    return( false );

  unsigned int rgb[3] = {
    pixel.r / pixel.cnt,
    pixel.g / pixel.cnt,
    pixel.b / pixel.cnt,
  };
  // 範囲外であった場合に補正
  for ( int i = 0 ; i < 3 ; ++i )
    if ( rgb[i] > UCHAR_MAX ) rgb[i] = UCHAR_MAX;
  col = RGB( rgb[0], rgb[1], rgb[2] );

  // 端数を取得
  pixel.r %= pixel.cnt;
  pixel.g %= pixel.cnt;
  pixel.b %= pixel.cnt;

  // 端数の7/48を加算
  buff.r = pixel.r * 7 / 48;
  buff.g = pixel.g * 7 / 48;
  buff.b = pixel.b * 7 / 48;
  buff.cnt = pixel.cnt;
  const_cast<SSP_JJN&>( *this ).add( Coord<int>( c.x + 1, c.y ), buff );
  const_cast<SSP_JJN&>( *this ).add( Coord<int>( c.x, c.y + 1 ), buff );

  // 端数の5/48を加算
  buff.r = pixel.r * 5 / 48;
  buff.g = pixel.g * 5 / 48;
  buff.b = pixel.b * 5 / 48;
  const_cast<SSP_JJN&>( *this ).add( Coord<int>( c.x + 2, c.y ), buff );
  const_cast<SSP_JJN&>( *this ).add( Coord<int>( c.x - 1, c.y + 1 ), buff );
  const_cast<SSP_JJN&>( *this ).add( Coord<int>( c.x + 1, c.y + 1 ), buff );
  const_cast<SSP_JJN&>( *this ).add( Coord<int>( c.x, c.y + 2 ), buff );

  // 端数の3/48を加算
  buff.r = pixel.r * 3 / 48;
  buff.g = pixel.g * 3 / 48;
  buff.b = pixel.b * 3 / 48;
  const_cast<SSP_JJN&>( *this ).add( Coord<int>( c.x - 2, c.y + 1 ), buff );
  const_cast<SSP_JJN&>( *this ).add( Coord<int>( c.x + 2, c.y + 1 ), buff );
  const_cast<SSP_JJN&>( *this ).add( Coord<int>( c.x - 1, c.y + 2 ), buff );
  const_cast<SSP_JJN&>( *this ).add( Coord<int>( c.x + 1, c.y + 2 ), buff );

  // 端数の1/48を加算
  buff.r = pixel.r / 48;
  buff.g = pixel.g / 48;
  buff.b = pixel.b / 48;
  const_cast<SSP_JJN&>( *this ).add( Coord<int>( c.x - 2, c.y + 2 ), buff );
  const_cast<SSP_JJN&>( *this ).add( Coord<int>( c.x + 2, c.y + 2 ), buff );

  return( true );
}

誤差拡散法を適用したバージョンは全て、前に示した SuperSamplingPattern クラスからの派生クラスとして、パターンから色コードを取得するときに、誤差を計算して周囲に散らす処理を行っています。その処理をするためのメンバ関数が point になります。
point関数は DrawingArea_IF での純粋仮想関数であり、constメンバ関数として定義されています。constメンバ関数は、自分自身(*this)の内容を変更しないことを保証する関数であり、インスタンス内のメンバ変数に対して変更を行おうとした場合、コンパイラがそれを検出してエラーを返します。しかし、誤差拡散法では周囲のパターンに誤差分を散らす処理を行うため、メンバ変数の変更が必要になります。その処理はメンバ関数 addが行い、この関数は constメンバ関数ではありません。constメンバ関数の中でそうではない関数を利用することはできないので、このままでは処理をすることができません。
色コードを取得する場合、通常はパターン内の情報が変わることはないので constメンバ関数として用意するのが普通だと思います。そのため、今回の場合は特殊な例であるということが分かるように、const_cast演算子を使って constを除去する対応にしました。なお、constメンバ関数であることを宣言するためには、関数宣言や定義の中で、引数リストの後ろに const句を付加します。

誤差の散らし方を任意に変更したい場合、分配する比率やその位置をパラメータとして渡せた方が汎用性が高く、記述する内容もコンパクトになります。しかし、今回はサンプルであることもあって、それぞれの方法に対して一つずつ派生クラスを用意することで手抜きをしました。

4) ディザ法(Dithering)

連続的に変化しているデータを離散的なデータに変換することを「量子化(Quantization)」といいます。「アナログ-デジタル変換(A/D変換)」は、連続量であるアナログ信号を離散データであるデジタル信号に変換しているため、その中で量子化を行っています。
デジタル信号に変換したときにアナログ信号が持つ情報をどの程度保持できるかは、サンプリングの回数と離散値の情報量(ビット数)に依存します。例えば、0 から 1の間で変化する時系列データを量子化するとき、一秒単位よりも 0.1秒毎でサンプリングした方が情報の欠落は少なくなり、また、同じサンプリング回数でも、サンプリングした値を 0.1刻みで離散値に変換するよりは、0.01刻みで変換した方が元のデータにより近くなります。量子化は、許容されている情報量(ビット数)に収まるように近似値を求める操作になるので、ビット数が大きいほど精度が上がることになります。

離散的なデジタル信号のビット数を小さくする(下位ビットの情報を落とす)操作は量子化処理そのものです。しかし、単純に下位ビットを落とす処理を行うと、データ間の差が非常に大きくなると同時に、同じ値を持つ範囲が広がります。

上の図は、連続的なデータをサンプリングして離散データにした後、量子化処理を行ったときのグラフの変化を表したものです。サンプリングを行った結果、横軸方向の変化は離散データになりますが、値そのものはまだ変化していません。前回紹介したサンプル補間処理を利用すれば、離散データから連続データを近似的に再現することもできます。しかし、量子化はデータの変化量を飛び飛びの値にしてしまいます。サンプリング間隔を狭くしてデータ量を増やしたとしても、切り捨てられるビット数が多ければ、変化量の小さい箇所は全て同じ値になり、ある箇所で大きく値が変化することになります。これが画像に対して行われると、縞状の模様として現れることになります。
誤差拡散法では、切り捨てられた値を周囲に分配することで、画質の劣化を抑えていました。しかし、結果的には近隣の値の差がさらに大きくなることになってしまいます。それにもかかわらず、画質がよくなったように見えるのは、人が画像を見るとき、近隣の変化よりも全体の変化を重視する傾向があるからです。このように、量子化による影響を小さくするため意図的に追加されるノイズのことを「ディザ(Dither)」といい、それを利用した処理を「ディザ法(Dithering)」といいます。誤差拡散法は、ディザ法の一種と考えられることができます。

ディザ法は、誤差拡散法のほかに「オーダードディザリング(Ordered Dithering; 組織的ディザ法、配列ディザ法とも呼ばれる)」や「ランダムディザ法(Random Dithering)」などがあります。ランダムディザ法は、その名の示す通り、乱数を使ってノイズを発生させる方法で、オーダードディザ法はあらかじめ決められた値をノイズとして利用する方法です。ここでは、オーダードディザ法について紹介をします。

前に述べた通り、オーダードディザ法では加算する誤差をあらかじめ決めておいて、それを順番に加えていく方式を取っています。この誤差のパターンはディザマトリックス(Dither Matrix)と呼ばれる行列で表され、例えば、代表的なディザマトリックスである Bayer 型のパターンは次のように定義されます。

このとき、n x n のディザマトリックスの各要素は必ず 0 から 2ⁿ - 1 までの値が重複する事なく入ることになります。例えば 8 x 8 のディザマトリックスは

となり、0 から 63 までの値が重複する事なく入っています。

このディザマトリックスを n x n の格子パターンに対して繰り返し適用していきます。上記の 8 x 8 サイズの行列ならば、8 x 8 のパターンごとにマトリックスの各要素と該当するピクセルの色成分を加算していく事になります。

オーダードディザ法を利用したパターン描画用のサンプル・プログラムを以下に示します。

/*****************************************************************************
 SSP_OrderedDithering : オーダードディザ法を利用したSupersampling用パターン
*****************************************************************************/

class SSP_OrderedDithering : public SuperSamplingPattern
{
  vector<int> matrix;   // ディザマトリックス
  unsigned int matSize; // matrixの行列サイズ
  int dmi;              // ディザマトリックスの要素を加算する比率(値が大きいほど影響度が小さくなる)

public:

  /*
    コンストラクタ

    const Coord<int>& sz : 実パターンのサイズ
    int _mag : 疑似サイズとの比率(倍率)
    unsigned int size : ディザマトリックスのサイズ(2の指数表現;2^size)
    unsigned int _dmi : ディザマトリックスの要素を加算する比率
  */
  SSP_OrderedDithering( const Coord<int>& sz, int _mag = 1, unsigned int size = 3, unsigned int _dmi = 4 );

  /*
    パターン内の色コードの取得(override)
  */
  bool point( Coord<int> c, RGB& col ) const;
};

/*
  SSP_OrderedDithering コンストラクタ

  const Coord<int>& sz : 実パターンのサイズ
  int _mag : 疑似サイズとの比率(倍率)
  unsigned int size : ディザマトリックスのサイズ(2の指数表現;2^size)
  unsigned int _dmi : ディザマトリックスの要素を加算する比率(値が大きいほど影響度が小さくなる)
*/
SSP_OrderedDithering::SSP_OrderedDithering( const Coord<int>& sz, int _mag, unsigned int size, unsigned int _dmi )
  : SuperSamplingPattern( sz, _mag )
{
  dmi = ( _dmi > 0 ) ? _dmi : 1;
  matSize = ( size > 0 ) ? ( 1 << size ) : 2;
  matrix.resize( matSize * matSize );

  // 2 x 2 サイズで初期化
  matrix[0] = 0;
  matrix[1] = 2;
  matrix[matSize] = 3;
  matrix[matSize + 1] = 1;

  // ひとつ前のサイズの行列の要素を元に構築
  for ( unsigned int cnt = 2 ; cnt < matSize ; cnt *= 2 ) {
    for ( unsigned int r = 0 ; r < cnt ; ++r ) {
      for ( unsigned int c = 0 ; c < cnt ; ++c ) {
        matrix[r * matSize + c] *= 4;
        matrix[r * matSize + cnt + c] = matrix[r * matSize + c] + 2;
        matrix[( r + cnt ) * matSize + c] = matrix[r * matSize + c] + 3;
        matrix[( r + cnt ) * matSize + cnt + c] = matrix[r * matSize + c] + 1;
      }
    }
  }

  // 中央値で減算する(平均値をゼロにする)
  for ( unsigned int r = 0 ; r < matSize ; ++r )
    for ( unsigned int c = 0 ; c < matSize ; ++c )
      matrix[r * matSize + c] -= matSize * matSize / 2;
}

/*
  SSP_OrderedDithering::point : パターンの色コードを取得する

  指定した座標がパターン外部の場合、もっとも近いピクセルの色コードを取得する

  Coord<int> c : 取得する位置(実サイズ上)
  RGB& col : 取得した色コード

  戻り値 : 座標がパターンの範囲外か、またはパターン内に色コードが格納されていなかった場合は falseを返す
*/
bool SSP_OrderedDithering::point( Coord<int> c, RGB& col ) const
{
  Pixel pixel;
  if ( ! SuperSamplingPattern::point( c, pixel ) )
    return( false );

  int error = matrix[( c.y % matSize ) * matSize + ( c.x % matSize )] / dmi;
  int rgb[3] = {
    roundHalfUp( (double)( (int)( pixel.r ) + error ) / (double)( pixel.cnt ) ),
    roundHalfUp( (double)( (int)( pixel.g ) + error ) / (double)( pixel.cnt ) ),
    roundHalfUp( (double)( (int)( pixel.b ) + error ) / (double)( pixel.cnt ) ),
  };

  // 範囲外であった場合に補正
  for ( int i = 0 ; i < 3 ; ++i ) {
    if ( rgb[i] < 0 ) rgb[i] = 0;
    if ( rgb[i] > UCHAR_MAX ) rgb[i] = UCHAR_MAX;
  }

  col = RGB( rgb[0], rgb[1], rgb[2] );

  return( true );
}

誤差拡散法の場合と同様に、オーダードディザ法も SuperSamplingPattern クラスからの派生クラスとして、point 関数を使って、ディザマトリックスの要素を計算値に加算してから色コードを返すようにしています。行列の要素は全て正値であり、そのまま加算した場合は常に全体が明るくなってしまうので、行列を求めた後でその中央値を減算することで、全体の平均値がゼロになるようにしています。また、パラメータの dmi でディザマトリックスの要素を除算することで、誤差分を小さくすることができるようにしてあります。dmi の値が大きくなるほどディザマトリックスによる影響度は小さくなります。

オーダードディザは、画像の二値化をする場合に劣化を抑えるためにも利用されます。その場合は、ディザマトリックスの要素を加算するのではなく、しきい値として利用します。二値化する場合、その結果は 0(黒) か 1(白) のいずれかになるので、例えば 0 から 255 までの値を色コードとしてとり得るときは、0 から 127 を 0、128 から 255までを 1 とするのが単純な二値化の手法になります。しかし、単純な二値化では、白または黒の連続した領域が大きくなる傾向があり、元画像からの劣化が非常に激しくなります。そこでディザマトリックスの値をしきい値として利用することで、行列の要素の小さな箇所では白になる傾向が高く、逆に大きな箇所では黒になる傾向が高くなります。よって、黒と白の領域が近隣についてもバラつくようになり、劣化を抑えた(元画像に近いように見える)画像とすることができます。なお、誤差拡散法の場合は誤差を散らす処理を行っているだけなので、二値化を行う際は判定方法としてオーダードディザ法を併用するようなこともできます。

5) テスト結果

今まで紹介した手法を利用した処理の結果を、前章にて使用したサンプル画像の "Lenna" を使って再度テストしてみます(実際には 512 x 512 のサイズです)。

以下の画像は、左側が目のあたりを三倍に拡大した時の結果、右側が全体を 1/3 に縮小した結果です。

九つの結果の処理条件は、次のようになります。なお、いずれの場合も補間法は「最近傍法」を使用しています。

拡大処理においては、疑似解像度による効果はある程度あるようで、ジャギーが目立たなくなっています(特に目の部分)。縮小画像ではさらに大きな効果があり、特に画像が滑らかになる傾向が見られます。しかし、どちらの変換結果に対しても、疑似解像度の倍率を上げたことに対する変化はあまりありません。また、誤差拡散法やオーダードディザ法による効果はまったく見られません。ディザマトリックスのサイズを大きくすると、各要素が持つ値の範囲は大きくなり、それだけ画像に与える影響が大きくなるので、右下隅の結果はディザがハッキリとわかるくらいに強く現れています。

上の画面は、自由変形処理ルーチンを利用した回転処理の結果で、各結果の条件は拡大・縮小処理の場合と同様です。通常の処理では画像の輪郭が非常に荒れた状態になっているのが、疑似解像度を利用することでかなり改善されていることがわかります。

全体を通して見ると、疑似解像度は縮小を伴う処理を行う場合に非常に効果があることがわかります。倍率を大きくするほど処理時間が長くなるという欠点はありますが、5倍程度の倍率で充分効果がある上に、どのような変形ルーチンに対しても有効なので、非常に有用な方法だと思います。しかし、通常の拡大処理に対してはあまり画質が改善されない場合もあります。
ディザ法による画質の改善は「皆無」と言っていいでしょう。この方法によって効果があるのは色数がもっと少ない場合で、True Color の場合は利用する意味があまりないようです。

	現在位置	[7/16]
[3/16]	[5/16]	[1/16]

		現在位置	[7/48]	[5/48]
[3/48]	[5/48]	[7/48]	[5/48]	[3/48]
[1/48]	[3/48]	[5/48]	[3/48]	[1/48]

D_n =	4D_n/2	4D_n/2+2U_n/2
D_n =	4D_n/2+3U_n/2	4D_n/2+U_n/2

U_n =	1	1	...	1
	1	1	...	1
	:	:	...	:
	1	1	...	1

D₈ =	0	32	8	40	2	34	10	42
	48	16	56	24	50	18	58	26
	12	44	4	36	14	46	6	38
	60	28	52	20	62	30	54	22
	3	35	11	43	1	33	9	41
	51	19	59	27	49	17	57	25
	15	47	7	39	13	45	5	37
	63	31	55	23	61	29	53	21

通常の補間法	疑似解像度(x5)	疑似解像度(x15)
疑似解像度(x5) + 誤差拡散法	疑似解像度(x5) + Floyd Steinberg型誤差拡散法	疑似解像度(x5) + Jarvis, Judice & Ninke型誤差拡散法
疑似解像度(x5) + オーダードディザ法(8x8行列;dmi=1)	疑似解像度(x5) + オーダードディザ法(8x8行列;dmi=2)	疑似解像度(x5) + オーダードディザ法(32x32行列;dmi=1)

D₂ =	0	2
D₂ =	3	1