CXCORE リファレンスマニュアル

最終変更者: 怡土順一, 最終変更リビジョン: 488, 最終変更日時: 2009-08-30 02:33:43 +0900 (日, 30 8月 2009)

基本構造体（Basic Structures）
配列操作（Operations on Arrays）
動的構造体（Dynamic Structures）
- メモリストレージ（Memory Storages）
- シーケンス（Sequences）
- セット（Sets）
- グラフ（Graphs）
- 木（Trees）
描画関数（Drawing Functions）
データ永続性と実行時型情報（Data Persistence and RTTI）
その他の関数（Miscellaneous Functions）
エラーハンドリングとシステム関数（Error Handling and System Functions）
- エラーハンドリング（Error Handling）
- システム関数（System Functions）

動的構造体（Dynamic Structures）

グラフ（Graphs）

CvGraph

重み付きの有向または無向グラフ

    #define CV_GRAPH_VERTEX_FIELDS()    ¥
        int flags; /* 頂点フラグ */   ¥
        struct CvGraphEdge* first; /* 最初の辺 */ 

    typedef struct CvGraphVtx
    {
        CV_GRAPH_VERTEX_FIELDS()
    }
    CvGraphVtx;

    #define CV_GRAPH_EDGE_FIELDS()      ¥
        int flags; /* 辺フラグ */     ¥
        float weight; /* 辺の重み */ ¥
        struct CvGraphEdge* next[2]; /* 辺リストにおける次の辺．始点（0），終点（1） */ ¥
        struct CvGraphVtx* vtx[2]; /* 始点（0），終点（1） */

    typedef struct CvGraphEdge
    {
        CV_GRAPH_EDGE_FIELDS()
    }
    CvGraphEdge;

    #define  CV_GRAPH_FIELDS()                  ¥
        CV_SET_FIELDS() /* 頂点のセット */   ¥
        CvSet* edges;   /* 辺のセット*/

    typedef struct CvGraph
    {
        CV_GRAPH_FIELDS()
    }
    CvGraph;

構造体 CvGraph は，OpenCVで使用されるグラフの基本構造である．

グラフ構造体は，CvSet（一般的なグラフの特性とグラフ頂点を記述）を継承し，さらにメンバーとしてもう一つのセット（グラフの辺を記述）を含んでいる．

頂点，辺，グラフヘッダの構造体は，他の拡張可能なOpenCVの構造体と同じ方法（構造体の拡張やカスタマイズをシンプルにするマクロを用いて）で宣言される．頂点と辺の構造体は明示的には CvSetElem を継承していないが，それらはセットの要素の二つの条件（先頭に整数フィールドflagsを持ち，CvSetElem構造体と合致する）を満足している．フィールド flags は，頂点と辺が存在していることを示すだけでなく，他の目的（例えば，グラフの走査（cvCreateGraphScanner 等を参照））にも用いられるので，このフィールドを直接使用しないほうが良い．

グラフは辺のセットとして表現され，各辺はそこに接続する辺のリストを持つ．情報の重複をできる限り避けるために，違う頂点への接続リストが交互に配置される．

グラフは有向か無向かのいずれかである．無向グラフの場合，頂点AからBへの接続と，頂点BからAへの接続の区別はなく，グラフ上にはどちらか一方しか同時に存在できない．これらの接続はそれぞれ辺 <A, B> ，<B, A> と表現される．

CreateGraph

空のグラフを生成する

CvGraph* cvCreateGraph( int graph_flags, int header_size, int vtx_size,
                        int edge_size, CvMemStorage* storage );

graph_flags: 生成したグラフのタイプ．無向グラフの場合，CV_SEQ_KIND_GRAPH，有向グラフの場合，CV_SEQ_KIND_GRAPH | CV_GRAPH_FLAG_ORIENTED．
header_size: グラフのヘッダサイズ（sizeof(CvGraph)以上）．
vtx_size: グラフの頂点サイズ（カスタマイズされた頂点の構造体は CvGraphVtx で始まらなければならない（ CV_GRAPH_VERTEX_FIELDS() を使用））．
edge_size: グラフの辺サイズ（カスタマイズされた辺の構造体は CvGraphEdge で始まらなければならない（ CV_GRAPH_EDGE_FIELDS() を使用））．
storage: グラフコンテナ．

関数 cvCreateGraph は，空のグラフを生成し，そのポインタを返す．

GraphAddVtx

グラフに頂点を追加する

int cvGraphAddVtx( CvGraph* graph, const CvGraphVtx* vtx=NULL,
                   CvGraphVtx** inserted_vtx=NULL );

graph: グラフ．
vtx: 追加される頂点の初期化に使用される，オプションの入力引数（sizeof(CvGraphVtx)の領域を超えたユーザー定義フィールドのみコピーされる）．
inserted_vertex: オプションの出力引数．NULLでない場合，新しい頂点のアドレスがここに書かれる．

関数 cvGraphAddVtx はグラフに頂点を追加し，頂点のインデックスを返す．

GraphRemoveVtx

グラフから頂点を削除する（インデックス指定）

int cvGraphRemoveVtx( CvGraph* graph, int index );

graph: グラフ．
vtx_idx: 削除される頂点のインデックス．

関数 cvGraphRemoveVtx は，指定した頂点とその頂点に接続するすべての辺をグラフから削除する．入力された頂点がグラフに存在しない場合は，エラーを出力する．戻り値は削除された辺の数，あるいは頂点がグラフに存在しない場合は-1である．

GraphRemoveVtxByPtr

グラフから頂点を削除する（ポインタ指定）

int cvGraphRemoveVtxByPtr( CvGraph* graph, CvGraphVtx* vtx );

graph: グラフ．
vtx: 削除される頂点へのポインタ．

関数 cvGraphRemoveVtxByPtr は，指定した頂点とその頂点に接続するすべての辺をグラフから削除する．入力された頂点がグラフに存在しない場合は，エラーを出力する．戻り値は削除された辺の数，あるいは頂点がグラフに存在しない場合は-1である．

GetGraphVtx

インデックスを用いてグラフの頂点を検索する

CvGraphVtx* cvGetGraphVtx( CvGraph* graph, int vtx_idx );

graph: グラフ．
vtx_idx: 頂点のインデックス．

関数 cvGetGraphVtx は，グラフの頂点をインデックスから検索し，そのポインタを返す．頂点がグラフ内に存在しない場合は，NULLを返す．

GraphVtxIdx

グラフ頂点のインデックスを返す

int cvGraphVtxIdx( CvGraph* graph, CvGraphVtx* vtx );

graph: グラフ．
vtx: グラフ頂点へのポインタ．

関数 cvGraphVtxIdx は，ポインタで指定されたグラフ頂点のインデックスを返す．

GraphAddEdge

グラフに辺を追加する（インデックス指定）

int cvGraphAddEdge( CvGraph* graph, int start_idx, int end_idx,
                    const CvGraphEdge* edge=NULL, CvGraphEdge** inserted_edge=NULL );

graph: グラフ．
start_idx: 辺の始点を示すインデックス．
end_idx: 辺の終点を示すインデックス．無向グラフの場合，順序はどちらでもよい．
edge: オプションの入力パラメータ．辺の初期化のためのデータ．
inserted_edge: 入力された辺のアドレスを保存するための，オプションの出力パラメータ．

関数 cvGraphAddEdge は，指定した二つの頂点を接続する．この関数は，追加に成功すると1を返し，すでに二つの頂点を接続する辺が存在する場合は0を返し，頂点のどちらかが存在しない，始点と終点が同じとき，他の重大な問題があるときには-1を返す．後者の場合（すなわち，結果が負のとき），この関数はデフォルトでエラーも出力する．

GraphAddEdgeByPtr

グラフに辺を追加する（ポインタ指定）

int cvGraphAddEdgeByPtr( CvGraph* graph, CvGraphVtx* start_vtx, CvGraphVtx* end_vtx,
                         const CvGraphEdge* edge=NULL, CvGraphEdge** inserted_edge=NULL );

graph: グラフ．
start_vtx: 辺の始点を示す頂点へのポインタ．
end_vtx: 辺の終点を示す頂点へのポインタ．無向グラフの場合，順序はどちらでもよい．
edge: オプションの入力パラメータ，辺の初期化データ．
inserted_edge: 辺の集合の中で入力された辺のアドレスを保存するための，オプションの出力パラメータ．

関数 cvGraphAddEdgeByPtr は指定した二つの頂点を接続する．この関数は，追加に成功すると1を返し，すでに二つの頂点を接続する辺が存在する場合は0を返し，頂点のどちらかが存在しない，始点と終点が同じとき，他の重大な問題があるときには-1を返す．後者の場合（すなわち，結果が負のとき），関数はデフォルトでエラーも出力する．

GraphRemoveEdge

グラフから辺を削除する（インデックス指定）

void cvGraphRemoveEdge( CvGraph* graph, int start_idx, int end_idx );

graph: グラフ．
start_idx: 辺の始点を示す頂点のインデックス．
end_idx: 辺の終点を示す頂点のインデックス．無向グラフの場合，順序はどちらでもよい．

関数 cvGraphRemoveEdge は，指定された二つの頂点を接続する辺を削除する．頂点が（この順序で）接続されていない場合，この関数は何もしない．

GraphRemoveEdgeByPtr

グラフから辺を削除する（ポインタ指定）

void cvGraphRemoveEdgeByPtr( CvGraph* graph, CvGraphVtx* start_vtx, CvGraphVtx* end_vtx );

graph: グラフ．
start_vtx: 辺の始点を示す頂点へのポインタ．
end_vtx: 辺の終点を示す頂点へのポインタ．無向グラフの場合，順序はどちらでもよい．

関数 cvGraphRemoveEdgeByPtr は，指定された二つの頂点を接続する辺を削除する．頂点が（この順序で）接続されていない場合，この関数は何もしない．

FindGraphEdge

グラフから辺を検出する（インデックス指定）

CvGraphEdge* cvFindGraphEdge( const CvGraph* graph, int start_idx, int end_idx );
#define cvGraphFindEdge cvFindGraphEdge

graph: グラフ．
start_idx: 辺の始点を示す頂点のインデックス．
end_idx: 辺の終点を示す頂点のインデックス．無向グラフの場合，順序はどちらでもよい．

関数 cvFindGraphEdge は，指定した二つの頂点を接続する辺を検出し，そのポインタを返す．辺が存在しない場合はNULLを返す．

FindGraphEdgeByPtr

グラフから辺を検出する（ポインタ指定）

CvGraphEdge* cvFindGraphEdgeByPtr( const CvGraph* graph, const CvGraphVtx* start_vtx,
                                   const CvGraphVtx* end_vtx );
#define cvGraphFindEdgeByPtr cvFindGraphEdgeByPtr

graph: グラフ．
start_vtx: 辺の始点を示す頂点へのポインタ．
end_vtx: 辺の終点を示す頂点へのポインタ．無向グラフの場合，順序はどちらでもよい．

関数 cvFindGraphEdgeByPtr は，指定した二つの頂点を接続する辺を検出し，そのポインタを返す．辺が存在しない場合はNULLを返す．

GraphEdgeIdx

グラフの辺のインデックスを返す

int cvGraphEdgeIdx( CvGraph* graph, CvGraphEdge* edge );

graph: グラフ．
edge: 辺へのポインタ．

関数 cvGraphEdgeIdx は，グラフの辺のインデックスを返す．

GraphVtxDegree

頂点に接続している辺の数を数える（インデックス指定）

int cvGraphVtxDegree( const CvGraph* graph, int vtx_idx );

graph: グラフ．
vtx: 頂点のインデックス．

関数 cvGraphVtxDegree は，指定した頂点に接続した（入る/出る両方向の）辺の数を返す．辺の数を数えるために，以下のコードが用いられる．

    CvGraphEdge* edge = vertex->first; int count = 0;
    while( edge )
    {
        edge = CV_NEXT_GRAPH_EDGE( edge, vertex );
        count++;
    }

マクロ CV_NEXT_GRAPH_EDGE( edge, vertex ) は， vertex へ接続する，edge の次の辺を返す．

GraphVtxDegreeByPtr

頂点に接続している辺の数を数える（ポインタ指定）

int cvGraphVtxDegreeByPtr( const CvGraph* graph, const CvGraphVtx* vtx );

graph: グラフ．
vtx: 頂点へのポインタ．

関数 cvGraphVtxDegreeByPtr は，指定した頂点に接続した（入る/出る両方向の）辺の数を返す．

ClearGraph

グラフをクリアする

void cvClearGraph( CvGraph* graph );

graph: グラフ．

関数 cvClearGraph は，グラフから全ての頂点と辺を削除する．この関数の時間計算量は O(1)である．

CloneGraph

グラフをコピーする

CvGraph* cvCloneGraph( const CvGraph* graph, CvMemStorage* storage );

graph: コピーするグラフ．
storage: コピーのためのコンテナ．

関数 cvCloneGraph は，グラフの完全コピーを作成する．グラフの頂点や辺が外部データへのポインタを持つ場合，そのポインタはコピーしたグラフでも共有される．この関数は頂点や辺の集合を最適化(デフラグメント)するため，新しいグラフの頂点と辺のインデックスが元のグラフのものと違う可能性がある．

CvGraphScanner

グラフ走査状態のための構造体

    typedef struct CvGraphScanner
    {
        CvGraphVtx* vtx;       /* 現在の頂点（あるいは辺の始点） */
        CvGraphVtx* dst;       /* 現在の辺の接続先頂点 */
        CvGraphEdge* edge;     /* 現在の辺 */

        CvGraph* graph;        /* 走査中のグラフ */
        CvSeq*   stack;        /* 走査中の頂点スタック */
        int      index;        /* 走査済みの頂点の下限インデックス */
        int      mask;         /* イベントマスク */
    }
    CvGraphScanner;

構造体 CvGraphScanner は，深さ優先走査のために用いられる．以下の関数の説明を参照．

CreateGraphScanner

グラフの深さ優先走査のための構造体を生成する

CvGraphScanner* cvCreateGraphScanner( CvGraph* graph, CvGraphVtx* vtx=NULL,
                                       int mask=CV_GRAPH_ALL_ITEMS );

graph

グラフ．

vtx

走査開始頂点．NULLの場合，走査は先頭の頂点（頂点シーケンスのうち最小のインデックスを持つ頂点）から始まる．

mask

イベントマスク．どのイベントにユーザが着目したいのかを指定する（関数 cvNextGraphItem はユーザーにコントロールを返す）． CV_GRAPH_ALL_ITEMS（すべてのイベントに着目）か，以下のフラグの組み合わせ．

CV_GRAPH_VERTEX - はじめてアクセスした頂点で停止する
CV_GRAPH_TREE_EDGE - tree edgeで停止する（tree edge は最後にアクセスした頂点と次にアクセスされる頂点を接続する辺のこと）
CV_GRAPH_BACK_EDGE - back edgeで停止する（back edge は最後にアクセスした頂点と探索木内でのその親のいずれかを接続する辺のこと）
CV_GRAPH_FORWARD_EDGE - forward edgeで停止する（forward edge は最後にアクセスした頂点と探索木内でのその子のいずれかを接続する辺のこと． forward edge は有向グラフの走査においてのみ有効）
CV_GRAPH_CROSS_EDGE - cross edgeで停止する（cross edge は異なる探索木同士か同じ木の枝同士を接続する辺のこと． cross edges は有向グラフの走査においてのみ有効）
CV_GRAPH_ANY_EDGE - 任意の辺で停止する（tree, back, forward そしてcross edges）
CV_GRAPH_NEW_TREE - すべての新しい探索木の先頭で停止する．走査プロセスが，走査開始頂点（initial vertex）から到達可能なすべての頂点と辺にアクセスする場合（アクセスされた頂点は辺とともに一つの木（tree）を構成する），グラフ中でまだアクセスされていない頂点を探索し，その頂点からの探索を再開する．新しい木の開始前（最初に cvNextGraphItem が呼ばれる，全く初めての場合も含む）に， CV_GRAPH_NEW_TREE イベントを生成する．
無向グラフにおいては，各探索木が，グラフの接続される一つの成分に対応する．
CV_GRAPH_BACKTRACKING - 逆探索（バックトラッキング，既にアクセスされた頂点を逆に戻っていく）中に，すべてのアクセス済みの頂点で停止する．

関数 cvCreateGraphScanner は深さ優先走査のための構造体を生成する．初期化された構造体は，関数 cvNextGraphItem （逐次走査処理）で用いられる．

NextGraphItem

グラフ走査処理を1ステップ，あるいは数ステップ進める

int cvNextGraphItem( CvGraphScanner* scanner );

scanner: グラフ走査状態．この関数で更新される．

関数 cvNextGraphItem は，ユーザーが着目したイベント（cvCreateGraphScanner の mask 引数で指定される）に合致するか，すべての走査が終了するまで，グラフ内を順に走査する．前者の場合，この関数は上記の mask パラメータで指定されたイベントを返し，次の呼び出しで走査を再開する．後者の場合，CV_GRAPH_OVER (-1) を返す．イベントが CV_GRAPH_VERTEX，CV_GRAPH_BACKTRACKING，CV_GRAPH_NEW_TREE の場合，現在の走査中の頂点は scanner->vtx に保存される．辺に関係しているイベントの場合，現在走査対象の辺は scanner->edge に，一つ前にアクセスした頂点は scanner->vtx に，辺のもう一方（終点）の頂点は scanner->dst にそれぞれ保存される．

ReleaseGraphScanner

グラフの走査処理を終了する

void cvReleaseGraphScanner( CvGraphScanner** scanner );

scanner: スキャナへのポインタのポインタ．

関数 cvGraphScanner は，グラフの走査処理を終了し，スキャナを解放する．

CXCORE リファレンス マニュアル

CXCORE リファレンスマニュアル