計算幾何

作成者: 怡土順一, 最終変更者: 怡土順一, 最終変更リビジョン: 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種類の図形が描画された画像を表示し，何かキーが押されるまで待つ．