About BBS

計算幾何

作成者: 怡土順一, 最終変更者: 怡土順一, 最終変更リビジョン: 342, 最終変更日時: 2007-10-14 23:39:34 +0900 (日, 14 10月 2007)

■ 計算幾何

OpenCVでは,点列の凸包を求めるという基本的な凸包問題や, ポリゴンで表される領域内に点が含まれるか否かを調べる点位置決定問題など, 基本的な計算幾何問題を解く関数が用意されている. また,矩形を包含する矩形の計算,点列に対する線のフィッティング(直線回 帰)を行う関数なども備える. 平面三角形細分割なども計算幾何学の範疇に含まれるが,リファレンス マニュアルでは別のセクションに分けられているので,今回はそれに従う.

サンプル


二つの矩形を包含する矩形 cvMaxRect

与えられた二つの矩形を包含する矩形を求める

サンプルコード

#include <cv.h> #include <highgui.h> #include <time.h> int main (int argc, char **argv) { IplImage *img = 0; CvRNG rng = cvRNG (time (NULL)); CvRect rect1, rect2, max; // (1)画像を作成,初期化する img = cvCreateImage (cvSize (640, 480), IPL_DEPTH_8U, 3); cvZero (img); // (2)ランダムな位置とサイズを持つ矩形を作成する rect1.x = cvRandInt (&rng) % (img->width / 4) + img->width / 4; rect1.y = cvRandInt (&rng) % (img->height / 4) + img->height / 4; rect1.width = cvRandInt (&rng) % img->width / 4 + 1; rect1.height = cvRandInt (&rng) % img->height / 4 + 1; rect2.x = cvRandInt (&rng) % (img->width / 2) + img->width / 4; rect2.y = cvRandInt (&rng) % (img->height / 2) + img->height / 4; rect2.width = cvRandInt (&rng) % img->width / 4 + 1; rect2.height = cvRandInt (&rng) % img->height / 4 + 1; // (3)矩形を包含する矩形を求める max = cvMaxRect (&rect1, &rect2); // (4)全ての矩形を描画する cvRectangle (img, cvPoint (rect1.x, rect1.y), cvPoint (rect1.x + rect1.width, rect1.y + rect1.height), CV_RGB (0, 0, 255), CV_FILLED); cvRectangle (img, cvPoint (rect2.x, rect2.y), cvPoint (rect2.x + rect2.width, rect2.y + rect2.height), CV_RGB (0, 255, 0), CV_FILLED); cvRectangle (img, cvPoint (max.x, max.y), cvPoint (max.x + max.width, max.y + max.height), CV_RGB (255, 0, 0), 2); // (5)画像を表示,キーが押されたときに終了 cvNamedWindow ("BoundingRect", CV_WINDOW_AUTOSIZE); cvShowImage ("BoundingRect", img); cvWaitKey (0); cvDestroyWindow ("BoundingRect"); cvReleaseImage (&img); return 0; }

// (1)画像を作成,初期化する
矩形を書き込むための画像領域を確保し,ゼロクリアすることで初期化する.

// (2)ランダムな位置とサイズを持つ矩形を作成する
矩形をランダムに作成する(ただし,完全なランダムではない). 画像の幅,高さの1/4以下のサイズの矩形を,画像境界からの1/4幅(高さ)以内の領域に描画する. 二つの矩形が重なることも有りうるが,今回の場合は問題ない. また,最低でも,幅,高さ1ピクセルの大きさを持つ事を保証する.

// (3)矩形を包含する矩形を求める
関数cvMaxRect()を利用して,あたえられた二つの矩形を包含する矩形を求める.

// (4)全ての矩形を描画する
計算した全ての矩形を,最初に確保した画像上に描画する.二つの矩形をそれぞれ, 青色,緑色で塗りつぶし,それを包含する矩形を赤い線で表す.

// (5)画像を表示,キーが押されたときに終了
実際に,画像を表示し,何かキーが押されるまで待つ.

実行結果例


楕円のフィッティング cvFitEllipse2

求めた輪郭に対して,楕円をフィッティングする

サンプルコード

#include <cxcore.h> #include <cv.h> #include <highgui.h> int main (int argc, char **argv) { IplImage *src_img = 0, *dst_img; IplImage *src_img_gray = 0; IplImage *tmp_img; CvMemStorage *storage = cvCreateMemStorage (0); CvSeq *contours = 0; CvBox2D ellipse; CvTreeNodeIterator it; CvPoint2D32f pt[4]; // (1)画像を読み込む if (argc >= 2) src_img = cvLoadImage (argv[1], CV_LOAD_IMAGE_COLOR); if (src_img == 0) return -1; src_img_gray = cvCreateImage (cvGetSize (src_img), IPL_DEPTH_8U, 1); cvCvtColor (src_img, src_img_gray, CV_BGR2GRAY); tmp_img = cvCreateImage (cvGetSize (src_img), IPL_DEPTH_8U, 1); dst_img = cvCloneImage (src_img); // (2)二値化と輪郭の検出 cvThreshold (src_img_gray, tmp_img, 95, 255, CV_THRESH_BINARY); cvFindContours (tmp_img, storage, &contours, sizeof (CvContour), CV_RETR_TREE, CV_CHAIN_APPROX_SIMPLE, cvPoint (0, 0)); // (3)ツリーノードイテレータの初期化 cvInitTreeNodeIterator (&it, contours, 3); while ((contours = (CvSeq *) cvNextTreeNode (&it)) != NULL) { if (contours->total > 6) { // (4)楕円のフィッティング ellipse = cvFitEllipse2 (contours); ellipse.angle = 90.0 - ellipse.angle; // (5)輪郭,楕円,包含矩形の描画 cvDrawContours (dst_img, contours, CV_RGB (255, 0, 0), CV_RGB (255, 0, 0), 0, 1, CV_AA, cvPoint (0, 0)); cvEllipseBox (dst_img, ellipse, CV_RGB (0, 0, 255), 2); cvBoxPoints (ellipse, pt); cvLine (dst_img, cvPointFrom32f (pt[0]), cvPointFrom32f (pt[1]), CV_RGB (0, 255, 0)); cvLine (dst_img, cvPointFrom32f (pt[1]), cvPointFrom32f (pt[2]), CV_RGB (0, 255, 0)); cvLine (dst_img, cvPointFrom32f (pt[2]), cvPointFrom32f (pt[3]), CV_RGB (0, 255, 0)); cvLine (dst_img, cvPointFrom32f (pt[3]), cvPointFrom32f (pt[0]), CV_RGB (0, 255, 0)); } } // (6)画像の表示 cvNamedWindow ("Fitting", CV_WINDOW_AUTOSIZE); cvShowImage ("Fitting", dst_img); cvWaitKey (0); cvDestroyWindow ("Fitting"); cvReleaseImage (&src_img); cvReleaseImage (&dst_img); cvReleaseImage (&src_img_gray); cvReleaseImage (&tmp_img); cvReleaseMemStorage (&storage); return 0; }

// (1)画像を読み込む
コマンド引数で指定されたファイル名の画像(入力画像)をオープンし,関数 cvLoadImage()で読み込む.2番目の引数にCV_LOAD_IMAGE_COLORを指定することで, カラー画像として読み込む.

// (2)二値化と輪郭の検出
読み込んだ入力画像からグレースケール画像に変換された画像を元に,さらに 二値画像を作成する.また,その二値画像から,輪郭を検出す.

// (3)ツリーノードイテレータの初期化
求めた輪郭を探索するために,ツリーノードイテレータを初期化する. 求めた輪郭は,内部にさらに輪郭を含むような木構造である場合があるが,ツ リーノードイテレータを利用することで,簡単に構造を辿ることができる. また,3番目の引数は,ノードをたどる深さを表しており,例えば"3"の場合には, 2番目の引数で指定した輪郭から数えて,3レベル下の階層までを探索する.

// (4)楕円のフィッティング
輪郭を構成する点数が6より多い場合のみ,関数cvFitEllipse2()により楕円のフィッティングを行う. これは,現在のOpenCVの実装により,点数が5点以下の場合には,エラーを返すからである. また,関数cvFitEllipse2()と,描画の関数では,楕円の角度の表現方法が異なるため, 楕円の角度を表すメンバ変数angleの値を変更する.

// (5)輪郭,楕円,包含矩形の描画
上で求めた輪郭,楕円,その楕円を包含する矩形を,入力画像に重ねて描画する.

// (6)画像の表示
実際に画像を表示して,何かキーが押されるまで待つ.

実行結果例


点列を包含する図形 cvConvexHull2, cvMinAreaRect2, cvMinEnclosingCircle

ランダムな点列を生成し,それらを包含する多角形(凸包),矩形,円を求める

サンプルコード

#include <cv.h> #include <highgui.h> #include <time.h> int main (int argc, char **argv) { int i; IplImage *img = 0; CvMemStorage *storage1 = cvCreateMemStorage (0); CvMemStorage *storage2 = cvCreateMemStorage (0); CvSeq *points, *hull; CvRNG rng = cvRNG (time (NULL)); CvPoint pt, pt0; CvBox2D box; CvPoint2D32f box_vtx[4]; CvPoint2D32f center; float radius; // (1)画像領域を確保し初期化する img = cvCreateImage (cvSize (640, 480), IPL_DEPTH_8U, 3); cvZero (img); // (2)点列の生成 points = cvCreateSeq (CV_SEQ_ELTYPE_POINT, sizeof (CvSeq), sizeof (CvPoint), storage1); for (i = 0; i < 20; i++) { pt.x = cvRandInt (&rng) % (img->width / 2) + img->width / 4; pt.y = cvRandInt (&rng) % (img->height / 2) + img->height / 4; cvSeqPush (points, &pt); cvCircle (img, pt, 3, CV_RGB (0, 255, 0), CV_FILLED); } // (3)点列に対する凸包を計算 hull = cvConvexHull2 (points, storage2); pt0 = **CV_GET_SEQ_ELEM (CvPoint *, hull, -1); for (i = 0; i < hull->total; i++) { pt = **CV_GET_SEQ_ELEM (CvPoint *, hull, i); cvLine (img, pt0, pt, CV_RGB (255, 0, 0)); pt0 = pt; } // (4)点列を包含する矩形を計算 box = cvMinAreaRect2 (points, NULL); cvBoxPoints (box, box_vtx); pt0 = cvPointFrom32f (box_vtx[3]); for (i = 0; i < 4; i++) { pt = cvPointFrom32f (box_vtx[i]); cvLine (img, pt0, pt, CV_RGB (255, 255, 0), 1); pt0 = pt; } // (5)点列を包含する円を計算 cvMinEnclosingCircle (points, ¢er, &radius); cvCircle (img, cvPointFrom32f (center), cvRound (radius), CV_RGB (0, 255, 255), 1, CV_AA, 0); // (6)画像を表示 cvNamedWindow ("FitShape", CV_WINDOW_AUTOSIZE); cvShowImage ("FitShape", img); cvWaitKey (0); cvDestroyWindow ("FitShape"); cvReleaseImage (&img); cvReleaseMemStorage (&storage1); cvReleaseMemStorage (&storage2); return 0; }

// (1)画像領域を確保し初期化する
8ビット3チャンネルの画像領域を確保し,ゼロクリアする.

// (2)点列の生成
関数cvSeqPush()を用いて,CvSeq型の配列に画像内に収まる座標を持つ点を格納する. また,そのランダムに生成された20個の点を画像領域内に描画する.

// (3)点列に対する凸包を計算
関数cvConvexHull2()により,与えられた点列に対する凸包を計算する. 2番目の引数がメモリストレージの場合には,CvSeq型の配列に凸包を構成する点の各座標へのポインタが格納される. ちなみに2番目の引数が配列の場合は,インデックスが格納された配列が返されるが,詳しくはリファレンス マニュアルを参照すること. 計算された凸包を描画するために,CV_GET_SEQ_ELEM()マクロを利用する. このマクロの最後の引数はインデックスを表すが,"-1"は(多くのightweight Languagetoと同様に)配列の最後のインデックスを表す. このようにして,順次凸包の頂点座標を取り出し,関数cvLine()で,それらを結ぶ線を描くことにより,凸包を描画する.

// (4)点列を包含する矩形を計算
関数cvMinAreaRect2()により,点列を包含する矩形を求める.関数cvBoundingRect()とは異なり, この間数は,cvBox型の値を返す.つまり,得られる矩形は,傾きも考慮された最小の包含矩形である. また,関数cvBoxPoints()により,得られた包含矩形の頂点を計算し,それらを繋ぐことで矩形を描画する.

// (5)点列を包含する円を計算
関数cvMinEnclosingCircle()により,点列を包含する円を計算し,描画する.

// (6)画像を表示
実際に,点列とそれを包含する3種類の図形が描画された画像を表示し,何かキーが押されるまで待つ.

実行結果例

OpenCV-1.0 リファレンス マニュアル
OpenCV-1.1pre リファレンス マニュアル
OpenCVサンプルコード


画素値の直接操作
部分画像のシャッフル
画像の連結
画像のコピー
画像形状の変形
タイリング
画像の反転
逆行列(擬似逆行列)の計算
色空間の写像
離散フーリエ変換
階層構造を持つ輪郭の座標取得
図形の描画
ポリゴンの描画
凸ポリゴンの描画
テキストの描画
IplImage構造体情報の保存
マップのシーケンスを保存
IplImage構造体情報の読み込み
マップのシーケンスを読み込む
K-means法によるクラスタリング
クラスタリングによる減色処理
エッジの検出
コーナーの検出
並進移動のためのピクセルサンプリング
回転移動のためのピクセルサンプリング
画像のサイズ変更
画像のアフィン変換(1)
画像のアフィン変換(2)
画像の透視投影変換
全方位画像の透視投影変換
モルフォロジー変換
平滑化
ユーザ定義フィルタ
境界線の作成
画像の二値化
画像の二値化(大津の手法)
画像ピラミッドの作成
画像ピラミッドを用いた画像の領域分割
平均値シフト法による画像のセグメント化
Watershedアルゴリズムによる画像の領域分割
輪郭の検出と描画
画像のモーメントを計算
ハフ変換による直線検出
ハフ変換による円検出
距離変換とその可視化
不要オブジェクトの除去
ヒストグラムの描画
ヒストグラム間の距離
二次元のヒストグラム
バックプロジェクションパッチ
ヒストグラムの均一化
テンプレートマッチング
形状のマッチング
点列を包含する矩形
輪郭領域の面積と輪郭の長さ
二つの矩形を包含する矩形
楕円のフィッティング
点列を包含する図形
動的背景更新による物体検出
snakeによる輪郭追跡(静止画)
オプティカルフロー1
オプティカルフロー2
オプティカルフロー3
Condensation
顔の検出
カメラキャリブレーション
歪み補正
マップを利用した歪み補正
サポートベクターマシン
画像の各ピクセル値を特徴ベクトルとしたSVMの学習
画像の各ピクセル値を特徴ベクトルとしたSVMによる物体検出
マウスイベントの取得
トラックバーの利用
カメラからの画像キャプチャ
動画としてファイルへ書き出す
ラベリング