やあ子どもたち。連休終わっちゃったけどちゃんと社会復帰したか。
よく画像処理などで、注目ピクセルの隣接ピクセルを参照する場合、
- 縦横方向それぞれ座標値を１だけ加減したり、
- その際に加減した後の座標値が負になっていないか、または画像サイズ上限を越えていないかをチェックしたり
するのが、とても何というか
- 汎用的でないし、
- コードの可読性も下がるしで、
そういうコードを書くのがもうホント嫌になってきてやしませんか。そこで本日は、縦横に並んだノードの集合体を、グラフノードの集合として保持することを楽しく考えていくよ。
自分の上下左右、加えて左上、右上、左下、右下のノードをそのポインタ値として保持できるデータ構造を考えよう。ポインタ値ですので、値がゼロの隣接ノードは、そこにはノードが存在しないことを意味するものとします。
class Node { Node* _left; // 左のノードを覚えてー、 Node* _right; // 右のノードも覚えてー、 Node* _above; // 上と、 Node* _below; // 下も覚えてー、 Node* _left_above;// 次は左上のノードと、 // であとはえーと、、 };
と、いきなりですが全方向分書くのが面倒ですね。早くも嫌になってきました。
そこで、各方向の名前をメンバ名とすることをやめ、８方向分、ポインタの配列にしてしまいましょう。内訳は、０番目の要素が右、１番目の要素が右上、といった具合に、半時計回りに８方向分の隣接ノードのポインタを覚えておくことにします。データ構造は以下のようになるかと思います。
class Node { public: static const int num_neib=8; Node* _neibccw[ num_neib ]; };
このように、隣接する要素との繋がり関する情報を位相情報と呼びます。Nodeクラスの保持情報として位相情報のみだと何も意味が無いので、通常はノードに座標情報や色情報、その他フラグなどを持たせたりします。こうして単なるノードが、はじめて画素ノードとして使えるようになります。
ノードグリッドとは、ノードが縦横に碁盤の目状に並んだ、いわば面構造のことです。例えばある画像データの、縦横にずらっと並んだピクセル列の各ピクセルを、ノードの集まりとして再構成することを考えます。。画像の端にあるノードの位相情報のうち画像の外側を向いたものはどれもゼロとなるはずですが、その他のノードは、全て上述の全8方向の隣接ノードを覚えている状況を思い浮かべましょう。
画像情報がノードグリッドとして得られる利点はひとえに任意のピクセルの隣接ノードが定数時間で取得可能となることです。つまり高速なわけです。例えば画像の場合、処理速度が画像の大きさによらず一定となったりします。
その他波及効果として、隣接ピクセルを参照する様々なアルゴリズムを汎用的に書くことが出来るようになります。コードの可読性も上がります。
上述のような、相互に位相情報づけされたノードグリッドが簡単に作成できたらいいなというところまで来た時に必要となるのが、これを高速に作成する手法です。何せ膨大な数にも及ぶ（500x500の画像でもざっと25万ノード！）ノード間の隣接情報構築ですので、隣接ノード同士の位相関連づけは効率的に行いたいものです。
そこで本題となりますが、以下のアルゴリズムでは、位相情報の構築にあたり探索は一切することなく、O(n）時間でノードシートの作成が終了します。
// 相互連結ノードグリッドの高速生成 template< class Node, class Func > // Node::Node( x, y ) // Node::_x, _y, _neibccw void lc_create_node_sheet( const int xres, const int yres, vector< Node* >* pvec, Func func ) { vector< Node* >& node_vec = *pvec; // （構築しながら後ろを振り返り、既存隣接ノードと相互連結を繰り返す） const pair< int, int > dir_arr[]= { make_pair( -1, 0 ), make_pair( -1, -1 ), make_pair( 0, -1 ), make_pair( 1, -1 ), }; typedef pair< int, int > PosType; for( int i=0; i<yres; ++i ) { for( int j=0; j<xres; ++j ) { Node* p = func( j, i ); node_vec.push_back( p ); for( int k=0; k<4; ++k ) { const PosType& d = dir_arr[k]; const int nei_x = j+d.first; const int nei_y = i+d.second; if( nei_x>=0 && nei_y>=0 ) { Node* nei = node_vec[ nei_x + xres*nei_y ]; p->_neibccw[4+k]=nei; nei->_neibccw[k] = p; } }// k }// j }// i return; }
次に、ノードシートを使ってできることの紹介です。ここでは簡単に20x20のノードシートを作成し、その中にドーナツを描画します。これだけなら通常の画像情報作成と変わりませんが、ここでは更に、このドーナツ形状の最外縁にあるノードや、最外縁から一回り内側にあるノードのセットについて、表示を変えてみます。
//ノードクラス定義 class Node { public: Node( int x, int y, int pos_x, int pos_y ) :_x(x) ,_y(y) ,_pos_x( pos_x ) ,_pos_y( pos_y ) ,_is_deleted(0) ,_generation(-1) { for( int i=0; i<num_neib; ++i ) _neibccw[i]=0; } static const int num_neib = 8; int _x, _y; bool _is_deleted; Node* _neibccw[ num_neib ];// [0](1,0), [1](1,1), [2](0,1),,. float _pos_x, _pos_y; int _generation; }; // 不要ノードの消去と位相整合 // _is_deletedなノードの、除去・削除（メモリ解放）・位相整合をします。 template< class Node > void lc_delete_and_remove_and_topology( vector< Node* >& node_vec ) { // 位相整合 auto& l = node_vec; for( auto inode: node_vec ) { if( inode->_is_deleted ) { for( int k=0; k<Node::num_neib; ++k ) { // k番目の方向の相手 auto neib = inode->_neibccw[k]; // 自分を指すポインタをnullに if( neib ) neib->_neibccw[(k+4)%8] = 0; }// k } }// inode // 不要ノードの除去と削除（メモリ解放） auto it = stable_partition( l.begin(), l.end(), [](Node* m){return !m->_is_deleted;} ); for_each( it, l.end(), [](Node* m){ delete m; } ); l.erase( it, l.end() ); return; } template< class Node > void lc_extract_free_edge( const vector< Node* >& node_vec, vector< Node* >* result ) { // 端ノード（FreeEdge)の検出 // (node_vecの中に、nullptrは存在しないことが前提） for( auto inode: node_vec ) { // 1つでも無効隣接ノードがあればマーク。 for( auto neib: inode->_neibccw ) { if( !neib ) { result->push_back( inode ); inode->_generation = 0; break; } }// neib }// inode return; } template< class Node > void lc_mark_next_gen( const vector< Node* >& base_node_vec, vector< Node* >* result ) { // base_gen 隣接の世代未割り振りノードに世代番号を付与。 for( auto inode: base_node_vec ) { for( auto ineib: inode->_neibccw ) { if( ineib ) { if( ineib->_generation == -1 ) { ineib->_generation = inode->_generation+1; result->push_back( ineib ); } } }// ineib }// inode return; } int main( int argc, char* argv[] ) { const int xres = 24; const int yres = 24; // 相互連結ノードシートの構築 vector< Node* > node_vec; { struct Func { Func( const float xbase, const float ybase, const float xuni, const float yuni ) :_xbase( xbase ) ,_ybase( ybase ) ,_xuni( xuni ) ,_yuni( yuni ) { } Node* operator()( const int j, const int i ) { Node* p = new Node( j, i, _xbase+j*_xuni, _ybase+i*_yuni ); return p; } float _xbase, _ybase, _xuni, _yuni; }; Func o( .0, .0, .2, .1 ); ::lc_create_node_sheet( xres, yres, &node_vec, o ); } // 相互連結ノードシートの利用。 //（円をプロットしてみます） for( auto inode: node_vec ) { const float a = .4*xres; const float b = .4*yres; const float a2 = .1*xres; const float b2 = .1*yres; float dx = inode->_x - xres * .5; float dy = inode->_y - yres * .5; inode->_is_deleted = ( dx*dx/(a*a)+dy*dy/(b*b) > 1 ) || ( dx*dx/(a2*a2)+dy*dy/(b2*b2) < 1 ); }// inode // 不要ノードの除去・削除・位相整合 lc_delete_and_remove_and_topology( node_vec ); // 端ノードの検出 vector< Node* > tmp; lc_extract_free_edge( node_vec, &tmp ); // 端ノードに対し内部にあるノードの世代検出 while( !tmp.empty() ) { vector< Node* > tmp2; lc_mark_next_gen( tmp, &tmp2 ); tmp = tmp2; }// while // 結果表示用バッファの構築 int buf[yres][xres]; for( int i=0; i<yres; ++i ) for( int j=0; j<xres; ++j ) buf[i][j]=0; // 端ノードを際立たせて表示 for( auto inode: node_vec ) { buf[inode->_y][inode->_x] = inode->_generation+1; }// i for( int i=0; i<yres; ++i ) { for( int j=0; j<xres; ++j ) { switch( buf[i][j] ) { case 0: cout << " "; break; case 1: cout << "()"; break; case 2: cout << "--"; break; case 3: cout << ".."; break; case 4: cout << ",,"; break; }// switch }// j cout << endl; }// i cout << "done."<<endl; getchar(); return 0; }
いかがでしょうか。また時間のあるときにでもこれを使った面白い事例集などできれば紹介したいと思います。
