ペイント・ルーチン(シード・フィル アルゴリズム)について、二回に渡って説明してきました。これで基本的なことについては全て紹介してしまいましたので、ここではペイント・ルーチンの応用例について紹介したいと思います。
前回まで説明してきたペイント・ルーチンは、同一色の領域内を別の色に塗り直す仕様であるため、画面に描かれた絵の上にさらに別の輪郭を描き、その内側を塗り潰すような用途には使用できません。そこで、ある色で囲まれた領域内を塗り潰すようなペイント・ルーチンを考えてみます。
このような処理を実現するためには、シード及び上下ラインから左右方向に境界を探す時、「領域色だったら続けて走査する」ところを「境界色でなかったら続けて走査する」処理に変更する必要があります。
境界色内の塗り潰しを行う場合、処理済みのシードであるかをチェックする方法を変更する必要があります。前回までに紹介したサンプル・プログラムでは、シードとして登録された位置の色が「領域色でなければ」処理をスキップするようにしてありますが、境界内の塗り潰しではこの方法は使えません。この部分の対応方法については、最後にあるサンプル・プログラムの解説の中で説明してありますので、そちらを御覧ください。
カラー画像の表色系として、以下のようなものが挙げられます。
RGB から輝度を抽出するには、以下の式を使用します。
Y = 0.299R + 0.587G + 0.114B
赤(R)・青(B)・緑(G) の成分の組み合わせによって、人間の目が識別できる色のほとんどを表すことができます。しかし、各成分は同じ情報量を保持させる必要があり、見た目を変えることなくどれか一つの成分だけ間引いてしまうようなことはできません。通常人間の目は、輝度の差に対して敏感で、色味の差に対しては輝度に比べて鈍感であると言われています。そこで、RGB 成分ではなく輝度とその他の色味成分で表すことができれば、色味成分だけを間引くことで、見た目をほとんど損なうことなくデータ圧縮することができます。このような色成分の一つとして YUV 形式 があります。
YUV 成分の Y は「輝度」を表し、U は青成分と輝度の差 B - Y を、V は赤成分と輝度の差 R - Y をそれぞれ表します。Y は RGB 各成分から求められるので、緑成分と輝度の差 G - Y を持たなくても計算することはできます。この値を持つようにすると成分の数が 4 つに増えてしまい圧縮する意味がなくなってしまいます。RGB から Y への変換式は、先に示したように
で表されます。但し、WR = 0.299, WG = 0.587, WB = 0.114 です。これらの定数は、RGB 各成分が輝度に寄与する重み付け係数と考えることができます。R, B からこの Y 成分を引けば V, U がそれぞれ求められるわけですが、YUV が元々カラーテレビへ送る信号として利用することを目的としていたので、このままの値では信号を送るための電圧レベルがオーバーフローします。そのため、係数を掛けて値を変換する処理が必要になります。RGB 各成分が 0 から 1 の範囲の値をとる時、U, V の最大値 UM, VM はそれぞれ 0.436, 0.615 となっているので、
より B = 1, R = G = 0 のとき U は最大値となります。よって、
よりこれが 0.436 となるためには KU ≡ 0.436 / 0.886 ≈ 0.492 を掛けて補正する必要があり、このときの U の計算式は
となります。同様にして V の計算式は、補正項が KV ≡ 0.615 / ( 1 - 0.299 ) = 0.877 となることを利用して
と求めることができます。YUV 成分から RGB 成分を求めるときは、U = 0.492( B - Y ), V = 0.877( R - Y ) より
B = Y + ( 1 / 0.492 )U = Y + 2.03U
R = Y + ( 1 / 0.877 )V = Y + 1.14V
を使って R, B 成分が得られ、G 成分は
G | = | ( Y - 0.299R - 0.114B ) / 0.587 |
= | [ 1.70Y - 0.509( Y + 1.14V ) - 0.194( Y + 2.03U ) ] | |
= | Y - 0.395U - 0.581V |
となります。
U, V の最大値 UM, VM をどちらも 0.5 とした場合、
KU = 0.5 / ( 1 - 0.114 ) ≈ 0.564
KV = 0.5 / ( 1 - 0.299 ) ≈ 0.713
となり、UV 各成分は
U = -0.169R - 0.331G + 0.500B
V = 0.500R - 0.419G - 0.0813B
で求められます。これは YCbCr と呼ばれ、基本的な考え方は YUV と同じです。YUV がアナログなシステムで利用されるのに対し、YCbCr はデジタルなシステムで利用されます。U, V 成分は、RGB 成分が 0 から 1 までの値をとるとき -0.5 から 0.5 までの範囲となります。従って、デジタル信号ではこちらの方が扱いやすくなります。
今でこそ多色化によって、自然画もきれいに表示できるほど画像の表現力が向上していますが、昔のパソコンは 8色や 16色程度の表現力しかなかったので、タイル・パターンによって擬似的に色数を向上させる手段が必須でした。当時のグラフィック・エディタにはたいてい、タイル・パターンで塗り潰す機能があったわけです。
対応方法としては、線分の代わりにパターンの一ライン分を描画する形になるので、アルゴリズム自体は変えず、点描画だけを変更すれば実現可能です。パターン内のどの位置のラインを使用するかは、画面の左上隅からパターンを並べた場合を想定して、描画するピクセルがパターン中のどの位置にあるかを調べて決めるのが通常だろうと思います。
具体的には、大きさ PDX x PDYのパターン配列 pat[PDX][PDY]を使い、線分の描画部分を以下のように変更することになります。
:
/* LX-RXのパターン線分を描画 */
for ( i = lx ; i <= rx ; i++ )
pset( i, y, pat[(i % PDX)][(UY % PDY)] );
:
現在では、擬似的に色数を増やすような必要はほとんどないと思いますので、用途としては、あるパターンの画像で塗り潰す他、別の画像の内容を、ある閉領域上に重ね合わせるような処理に利用することができます。
これも 8色や 16色といった色数の少ないモードでの使用を前提にしたもので、複数のパレットを一度に塗り潰すというものです。タイル・パターンを塗り潰す場合(タイル・ペイントとは逆の処理)などに利用できます。
この場合は塗り潰し対象のパレットを指定する必要があります。通常は、8ないし 16ビットの変数を用意して、ビットが立った位置の色を塗り潰し対象とするなどとします。ビットの立った位置の色を境界色となるようにすることも可能です。
/* Coord : 座標定義用構造体 */ template<class T> struct Coord { : }; /* RGB : RGB成分定義用構造体 */ class RGB { : }; /* pset : 画像に点を描画する */ void pset( const Coord<int>& c, const RGB& col ) { : } /* point : 画像の点から色コードを取得する */ void point( const Coord<int>& c, RGB& col ) { : } /* 点描画用基底クラス */ class PSetBase { public: virtual void operator()( const Coord<int>& c ) = 0; // 点描画 virtual ~PSetBase() {} // 仮想デストラクタ }; /* GBoxPatternSet : 矩形パターンに従った点描画クラス */ class GBoxPatternSet : public GSetBase { vector<RGB> pattern; Coord<int> size; public: /* コンストラクタ */ // 全パラメータの指定 GBoxPatternSet( const vector<RGB>& pat, const Coord<int>& s ) : pattern( pat ), size( s ) {} void operator()( const Coord<int>& c ); }; /* GBoxPatternSet::operator() : 矩形パターンに従った点描画処理 const Coord<int>& c : 描画位置 */ void GBoxPatternSet::operator()( const Coord<int>& c ) { if ( size.x <= 0 || size.y <= 0 ) return; Coord<int> pc( c.x % size.x, c.y % size.y ); if ( pc.x < 0 ) pc.x += size.x; if ( pc.y < 0 ) pc.y += size.y; unsigned int i = pc.y * size.x + pc.x; if ( i < pattern.size() ) pset( c, pattern[i] ); } /************************************************************** ピクセルの比較用クラス **************************************************************/ /* GCheckBase : 基底(抽象)クラス */ class GCheckBase : public GPSetBase { public: // 比較結果を返す virtual bool matched() const = 0; }; /* GCheck : 指定した色コードと一致するか比較する (領域色の塗り潰し用) */ class GCheck : public GCheckBase { RGB dest; public: RGB src; GCheck( const RGB& col ) : src( col ) {} void operator()( const Coord<int>& c ) { point( c, dest ); } bool matched() const { return( src == dest ); } }; /* GNotCheck : 指定した色コードと異なるか比較する (境界色での塗り潰し用) */ class GNotCheck : public GCheck { public: GNotCheck( DrawingArea& d ) : GCheck( d ) {} GNotCheck( DrawingArea& d, const RGB& col ) : GCheck( d, col ) {} bool matched() const { return( ! GCheck::matched() ); } }; /************************************************************** GDraw : 図形描画用基底クラス **************************************************************/ class GDraw { protected: Coord<int> drawSize; // 画像の大きさ public: GDraw( int sx, int sy ) { setSize( sx, sy ); } GDraw( const Coord<int>& s ) { setSize( s ); } virtual ~GDraw() {} // 描画エリアの大きさのセット void setSize( int sx, int sy ) { setSize( Coord<int>( sx, sy ) ); } void setSize( const Coord<int>& s ) { if ( s.x > 0 && s.y > 0 ) drawSize = s; } // 描画処理 virtual void operator()( GSetBase& pset ) = 0; }; /************************************************************** GPaint : ペイント用クラス **************************************************************/ class GPaint : public GDraw { public: /* 公開メンバ変数 */ Coord<int> coord; // 開始座標 private: /* バッファのデータ構成 */ struct Buffer { int lx; // 領域左端のX座標 int rx; // 領域右端のX座標 int y; // 領域のY座標 int oy; // 親ラインのY座標 }; queue<Buffer> queueBuff; // シード候補を登録するqueue map< int, vector< Coord<int> > > mapDrawn; // 描画済みの領域 GCheckBase* gCheck; // シード候補判定用関数オブジェクト bool drawn( int x, int y ) const; void scanLine( int lx, int rx, int y, int oy ); public: // コンストラクタ GPaint( GCheckBase& _gCheck, int x = 0, int y = 0, int sx = 0, int sy = 0 ) : GDraw( sx, sy ), coord( Coord<int>( x, y ) ), gCheck( &_gCheck ) {} // ペイント関数 void operator()( GPSetBase& pset ); void operator()( const Coord<int>& c, GPSetBase& pset ) { coord = c; (*this)( pset ); } }; /* GPaint::drawn : すでに描画済みかどうかを判定する int x, y : シード候補の座標 */ bool GPaint::drawn( int x, int y ) const { map< int, vector< Coord<int> > >::const_iterator mapCit = mapDrawn.find( y ); if ( mapCit == mapDrawn.end() ) return( false ); vector< Coord<int> >::const_iterator vecCit = ( mapCit->second ).begin(); while ( vecCit != ( mapCit->second ).end() ) { if ( x >= vecCit->x && x <= vecCit->y ) return( true ); ++vecCit; } return( false ); } /* GPaint::scanLine : 線分からシードを探索してバッファに登録する int lx, rx : 線分のX座標の範囲 int y : 線分のY座標 int oy : 親ラインのY座標 */ void GPaint::scanLine( int lx, int rx, int y, int oy ) { Buffer buff; while ( lx <= rx ) { /* 非領域色を飛ばす */ for ( ; lx <= rx ; lx++ ) { (*gCheck)( Coord<int>( lx, y ) ); if ( gCheck->matched() ) break; } if ( ! gCheck->matched() ) break; buff.lx = lx; /* 領域色を飛ばす */ for ( ; lx <= rx ; lx++ ) { (*gCheck)( Coord<int>( lx, y ) ); if ( ! gCheck->matched() ) break; } buff.rx = lx - 1; buff.y = y; buff.oy = oy; queueBuff.push( buff ); } } /* GPaint::operator() : 塗り潰し処理 GPixelOp& pset : 点描画用関数オブジェクト */ void GPaint::operator()( GPixelOp& pset ) { mapDrawn.clear(); Buffer buff; buff.lx = buff.rx = coord.x; buff.y = buff.oy = coord.y; queueBuff.push( buff ); do { buff = queueBuff.front(); queueBuff.pop(); /* すでに描画済みならスキップ */ if ( drawn( buff.lx, buff.y ) ) continue; int lxsav = buff.lx - 1; int rxsav = buff.rx + 1; /* 右方向の境界を探す */ while ( buff.rx < drawSize.x - 1 ) { (*gCheck)( Coord<int>( buff.rx + 1, buff.y ) ); if ( ! gCheck->matched() ) break; ++( buff.rx ); } /* 左方向の境界を探す */ while ( buff.lx > 0 ) { (*gCheck)( Coord<int>( buff.lx - 1, buff.y ) ); if ( ! gCheck->matched() ) break; --( buff.lx ); } /* lx-rxの線分を描画 */ for ( int x = buff.lx; x <= buff.rx; x++ ) pset( Coord<int>( x, buff.y ) ); ( mapDrawn[buff.y] ).push_back( Coord<int>( buff.lx, buff.rx ) ); /* 真上のスキャンラインを走査する */ int uy = buff.y - 1; if ( uy >= 0 ) { if ( uy == buff.oy ) { if ( lxsav >= 0 ) scanLine( buff.lx, lxsav, uy, uy + 1 ); if ( rxsav < drawSize.x ) scanLine( rxsav, buff.rx, uy, uy + 1 ); } else { scanLine( buff.lx, buff.rx, uy, uy + 1 ); } } /* 真下のスキャンラインを走査する */ int dy = buff.y + 1; if ( dy < drawSize.y ) { if ( dy == buff.oy ) { if ( lxsav >= 0 ) scanLine( buff.lx, lxsav, dy, dy - 1 ); if ( rxsav < drawSize.x ) scanLine( rxsav, buff.rx, dy, dy - 1 ); } else { scanLine( buff.lx, buff.rx, dy, dy - 1 ); } } } while ( queueBuff.size() > 0 ); }
サンプル・プログラムの中は、以前説明した関数オブジェクトや演算子の多重定義(operator〜)・テンプレート・仮想関数などを多用しており、さらに C++用の標準ライブラリ(Standard Template Library)のいくつかを利用しています。このあたりの内容については、以下の章である程度詳しく説明してあります。
ペイント・ルーチン自体のアルゴリズムは前の章とほとんど変わりません。変更された箇所としてまず挙げられるのが、点描画用の関数を外部から引数として渡すことができるようになった点と、スキャンラインを走査するときの判定ルーチンを外部から渡すことができるようになった点の二つです。判定ルーチンも切り離したので、領域色や境界色の指定は判定ルーチン側で行う必要があります。このための関数オブジェクトとして GCheckBaseの派生クラスである GCheckと GNotCheckがあり、前者が領域色指定用、後者が境界色指定用となります。領域色を塗り潰す場合は、塗り潰しを開始する点の色コードを領域色として GCheckのメンバ変数 srcにセットし、境界色で囲まれた部分を塗り潰す場合は、境界色の色コードを GNotCheckのメンバ変数 srcにセットします。ちなみに GNotCheckは GCheckから派生したクラスになっていて、両者の違いは判定用関数(matched)の戻り値が反転しているところだけになります。
もう一つの大きな違いは、すでに処理済みのシードであるかをチェックする部分です。前回のサンプル・プログラムでは、領域色でなかったらスキップするようにしていました。しかし前述の通り、境界色を指定した場合はこの方法は使えません。描画色であればスキップするようにした場合、たまたま最初から描画色と同じだった場合に誤判定する可能性があります。それだけではなく、点描画は任意に変更できるので、領域色を指定する場合でも、一度処理したところが領域色のままである可能性もあり(実際に塗り潰しなどを行うのではなく別の画面にコピーする場合など)、どのような場合にも対処できる方法としては、処理した場所を登録しておいて、その情報を使ってチェックをするのが最も確実です。そのための関数として drawnが用意されています。線分を描画した後その情報を記録しておき、drawnの中でシードの座標が描画済みの領域内にあるかを記録した内容から判定してその結果を返します。
今回のサンプルでは、Standard Template Library(STL)が多用されています。STLには、コンテナと呼ばれる、複数のデータを保持するために用意されたオブジェクト用のクラスが多数用意されています。今回利用したコンテナを以下に示します。
ほとんどのコンテナクラスは、テンプレート引数を持っています。例えば、int型のデータを持つ可変長配列を用意する場合は、以下のように宣言します。
要素数を指定しない限り、宣言したばかりのvectorはサイズが 0です。これに要素を追加したり(push_back(末尾に追加)や insert(途中に挿入)など)、削除したり(erase)することで、任意の長さの配列を作成することができます。要素にアクセスする場合は、通常の配列と同様に vecInt[i]のように記述します。
vectorによく似たコンテナに listがありますが、用途が異なります。vectorが、サイズの変更が可能な「配列」として使われるのに対し、listは、途中にある要素の挿入や削除を頻繁に行う場合に適したコンテナになります。したがって、vectorを使って要素の挿入や削除を頻繁に行うのは効率の悪い処理である反面、要素へのアクセスはデータ量に依存せず高速にできるのに対し、listでは要素の挿入や削除が効率よくできる反面、要素へのアクセスはデータ量に比例して長くなります。
queueは、先入れ先出し(First In, First Out; FIFO)の形でデータを保持するためのコンテナクラスです。要素は末尾側から追加されていき、先頭側から取り出されます。そのため、先に追加された要素が先に取り出される形になるわけです。逆に、後入れ先出し(Last In, First Out; LIFO)の形で保持するためのコンテナが stackになります。
queueは、ペイント・ルーチンにおけるシードのように、複数の要素を順番に処理する場合の待ち行列として頻繁に利用されます。またstackは、サブルーチンを呼び出す時に、引数や、処理後の戻り先アドレスを保持する場合に利用されます。サブルーチン呼び出しは入れ子状に発生することから、最後に追加された要素が先に取り出されないと正しく元に戻すことができなくなるので、stackのような構造が必要になるわけです。stackはその他にも、計算式の評価やコンパイラでの構文解析などで利用されています。
先頭と末尾の両端から要素の追加や取り出しができるコンテナは dequeと呼ばれ、トランプなどのカード(スペルは違いますが、こちらもデック(deck)と言います)を表現するときなどに利用できます。
mapは、キーと値の対から構成されるコンテナで、利用頻度は非常に高いです。STLの mapでは、キーとして指定できるデータ型は、"より小さい"を表す比較演算子を持っていればどんなものでも利用できるので、例えば文字列をキーとした配列などのようなイメージで利用することができます。
キーと値の対を構造体として定義して、vectorや listをコンテナとして利用することでも実現ができそうに見えますが、mapが持つ大きな利点は要素へのアクセスが早いところにあります。vectorや listを利用した場合は、キーが一致する要素を線形探索する必要があるため、処理時間はデータ量に比例してしまいます。
mapを利用するには、キーと値の両方のデータ型をテンプレート引数として渡す必要があります。
上の例では、キーを string型、値を int型として mapを定義しています。"White"をキーとする値 0xFFFFFFを追加する場合は、
と記述します。値を取得する場合、
と記述することで可能です。mapにはその他に、キーによる探索や要素の挿入・削除などの処理を行うためのメンバ関数も用意されています。
vectorや list、mapなどのコンテナは、反復子(iterator)を持っています。反復子は、繰り返し処理を抽象化した概念であり... と言うとよくわからない表現になりますが、C言語におけるポインタを使った繰り返し処理に近いものとして考えればイメージできるのではないかと思います。
int型の配列に、添字と同じ値の要素を代入する単純な処理を行う場合、以下のように記述することができます。
const unsigned int SIZE = 100; int array[SIZE]; for ( unsigned int i = 0 ; i < SIZE ; ++i ) array[i] = i;
これをポインタを使って記述すると、次のようになります。
int i = 0; for ( int* p = array ; p < array + SIZE ; ++p ) *p = i++;
vectorは配列と同等の使い方ができるので、同じ処理を次のように記述して行うことができます。
const unsigned int SIZE = 100; vector<int> array( SIZE ); for ( unsigned int i = 0 ; i < array.size() ; ++i ) array[i] = i;
arrayを構築するときに渡す引数 SIZEは要素数を表します。このように vectorでは、あらかじめ配列のサイズを指定して構築することが可能です。また、メンバ関数 sizeは要素数を得たいときに利用します。
配列でポインタを利用したように、vectorでは反復子を利用して同様な記述が可能です。
vector<int>::iterator it = array.begin(); int i = 0; while ( it != array.end() ) *it++ = i++;
非常に長い名前の vector<int>::iteratorが反復子の型、itが反復子を表します。beginはコンテナの最初の要素を指し示す反復子を返し、endは末尾の要素の次の要素を指し示す反復子を返します。itとarray.end()が等しくなったら、末尾までの処理が完了したことを意味します。*itが反復子が指し示している要素を表しているので、反復子はちょうどポインタと同じ意味を持っていることになります。
コンテナクラスは要素を複数持つため、中の要素に対して反復処理を実行することが多々あります。全てのコンテナクラスが配列のように単純な構成を持っているわけではないので、次の要素へ移行する方法は一意に決まっているわけではありません(全てのコンテナクラスが、配列のように要素を順番に並べて保持しているわけではないことに注意してください)。それらを同じ書式で表すために用意されたのが反復子です。反復子を利用すれば、全ての要素に対して、順番に処理できることが保証されていることになります。
mapの場合はキーと値の二つの要素が存在するため、それぞれにアクセスするために firstとsecondの二つのメンバ変数が反復子に対して用意されています。
サンプル・プログラムの中では、二つのコンテナを組み合わせて利用している箇所があります。
この場合、キーが int型、Coord<int>を要素とする vectorが値となる mapを定義したことになります。関数 drawnの中では、まず map用のメンバ関数 findで、キーを使って探索を行い、キーが一致した要素の反復子 mapCitを得ます。
要素が見つからなかった場合は、mapCitの値は mapDrawn.end()になるので、そこで処理を終了します。そうでなければ、mapCit->secondが vector< Coord<int> >型のコンテナを示すことになるので、最初の要素を指す反復子 begin()を取得します。
mapCitとvecCitのどちらも、const_iteratorというデータ型になっています。これは中の要素が定数であることを表し、内容の変更を行わないことを明示していることになります。
あとは、vecCitが ( mapCit->second ).end()を示すまで、繰り返し処理を行います。
while ( vecCit != ( mapCit->second ).end() ) { : ++vecCit; }
mapDrawnの構造を見ればわかるように、描画済みであるかをチェックするためのデータには描画した線分(Y座標と両端のX座標)を使っています。データ量を小さくするための手段ですが、もっと単純に、画像と同じサイズのデータ領域を用意して、描画した部分のフラグを立てておくことでも対応は可能です。
◆◇◆更新履歴◆◇◆
◎ 「補足説明 -- YUV 変換」の内容を大幅に見直しました (2014-11-15)。
前に戻る | タイトルに戻る |