4点同士の対応点情報からホモグラフィを線型に求める

Mat findHomography(InputArray src, InputArray dst, int method, double ransacReprojThreshold, OutputArray mask, const int maxIters, const double confidence) †

  • methodで指定した方法で、srcとdstの点同士を変換するホモグラフィを求める
↑

引数 †

  • src:Mat型の変換前の座標
  • dst:Mat型の変換後の座標
  • method:int型の内部計算方法。省略するとデフォルト0
  • ransacReprojThreshold:double型のしきい値。省略するとデフォルト3
  • mask:Mat型の出力。対応点として使われたかどうか。
  • maxIters:int型の入力。最大試行回数。省略するとデフォルト2000
  • confidence:double型の入力。省略するとデフォルト0.995
↑

返り値 †

  • Mat型のホモグラフィ
↑

Mat findHomography(InputArray src, InputArray dst, OutputArray mask, int method, double ransacReprojThreshold); †

  • findHomographyのオーバーロード
  • 内部的に前者のfindHomographyをcallする
↑

引数 †

  • オーバーロードなので、前述のfindHomographyに準ずる
↑

返り値 †

  • Mat型のホモグラフィ
↑

解説 †

  • srcはn*2もしくはn*3, dstはn*2もしくはn*3, homographyは3*3のサイズの行列
  • n*2はn行2列(n rows, 2 columns), n*3はn行3列(n rows, 3 columns)，幅が2か3で高さがn
  • nは対応点の数
  • \left(\begin{array}{cc} x_{1} & y_{1} \\ x_{2} & y_{2} \\ \vdots & \vdots \\ x_{n} & y_{n} \end{array}\right)か\left(\begin{array}{ccc} x_{1} & y_{1} & 1 \\ x_{2} & y_{2} & 1 \\ \vdots & \vdots & \vdots \\ x_{n} & y_{n} & 1 \end{array}\right)の形で渡すとOK
  • srcを\bf{x}, dstを\bf{x}^\prime, homographyを\rm{H}とすると
  • \bf{x}^\prime \simeq \rm{H}\bf{x}
  • となるhomographyを返す
  • methodは以下の4つが引数として使用できる
    • 0:全点を使って計算する。ノイズが乗った場合は自乗誤差が最小になるような行列を求める。指定を省略した場合はこの手法が使われる
    • LMEDS(4):LMEDS法を使って誤った対応を除いてホモグラフィを求める
    • RANSAC(8):RANSAC法を使って誤った対応を除いてホモグラフィを求める
    • RHO(16):RHO法を使って誤った対応を除いてホモグラフィを求める(要OpenCV3.0以降)
    • 詳細は後述
  • maskに点数と同じ数だけ要素を持った行列を渡すと，推定後に除去された点の情報が返ってくる
    • 1か0が入って返ってくるが，1が入ってる点だけが計算に利用された
    • 出力としてだけ使用できる。渡した値はOpenCVによって読まれることは無い。
  • maxItersを指定すると、収束するまでの最大試行回数を設定できる。
    • コメント文とドキュメントには2000回が最大試行回数と書いてあるが、ソースコードを読む限り別段2000回以上の試行もできる(意味があるかはわからぬ)
  • confidenceには0-1の範囲のdoubleを指定する
    • 各対応点のconfidenceでのしきい値
    • 省略すると0.995
    • この値より信頼性の低い対応点は棄却される
↑

methodについて †

  • 対応点にはだいたい誤対応が含まれる
  • 通常の行列演算に誤対応が含まれていると、行列全体にノイズの影響が出る
  • 誤対応（ドキュメントでoutlier、外れ値）を除去するために、LMeDS、RANSAC、RHOなどの手法を用いる
    • LMeDS:再投影誤差の中間値が最も小さくなるような対応を初期値として選択する
    • RANSAC:対応関係の点数が最も多くなるような対応を初期値として選択する
    • RHO:RHO法を使って推定した対応を初期値として選択する。要OpenCV3.0以降
  • RANSACとRHOは誤対応だらけでも、対応関係を推定できる。そのためにはどれくらい近ければ対応していると認めるかしきい値を定める必要がある
    • パラメータのransacReprojThresholdがしきい値にあたる
  • LMeDSはしきい値をあたえないでも対応関係を推定する
    • ただし、誤対応が50%を超えている場合は推定がうまくいかない
  • RHO手法以外を指定した場合、それぞれの推定で初期推定を求めたうえで、最適化でさらなるフィッティングが行われる
    • OpenCV3.0以降ではLM法を使ったフィッティングが行われる
    • 0を指定した場合も4点より多い(5点以上)の対応点があればフィッティングが行われる
    • 何故か、RHOを指定した場合だけLM法を使わない。なにゆえだ。。
  • OpenCV 2.4系列までは、対応点は、2*N、N*2、3*N、N*3のシングルチャンネル、もしくは1*Nの2チャンネルor3チャンネルの行列でも解釈してくれる
  • OpenCV 3.0系列ではcolumn、つまり列数が2、もしくは3である必要がある
    • つまり、ラスタスキャンした時に、x0、y0、x1、y1の順もしくはx0、y0、1、x1、y1、1の順にアクセスできる必要がある。
    • バグな気がするんだけれどなぁ。
↑

導出 †

  • 以下の導出は一切知らなくてもこの関数は使える
  • 変換前を\bf{x}, 変換後を\bf{x}^\prime，ホモグラフィを\rm{H}として，次式で表せる
  • \rm{H}\bf{x}=s\bf{x}^\prime
  • ここで，ホモグラフィ行列\rm{H}も斉次座標\bf{x}，\bf{x}^\primeも，スケーリングの不定性がある
  • 言い換えれば，右辺だけ2倍しても等式が成り立ってしまう*1
  • その不定性を表すために，右辺にスケールファクターとしてsを導入した
  • 各ベクトル，行列を要素ごとに書くと，次式のようになる
\left(\begin{array}{ccc}h_{11}&h_{12}&h_{13}\\h_{21}&h_{22}&h_{23}\\h_{31}&h_{32}&1\\\end{array}\right)\left(\begin{array}{c}x\\y\\1\\\end{array}\right)=\left(\begin{array}{c}sx^\prime\\sy^\prime\\s\\\end{array}\right)
  • ホモグラフィのスケーリングを固定するために，h_{33}=1とする
  • この行列式を分解すると，下記の3本の方程式が導出される
\left\{\begin{array}{l}h_{11}x+h_{12}y+h_{13}=sx^\prime\\h_{21}x+h_{22}y+h_{23}=sy^\prime\\h_{31}x+h_{32}y+1=s\\\end{array}
  • ただ，3本の方程式それぞれはsに関して従属性があるので，独立な方程式は2本得られる
  • 3本の式からsを消去して次の2式を得る
\left\{\begin{array}{c}h_{11}x+h_{12}y+h_{13}&=\(h_{31}x+h_{32}y+1\)x^\prime\\h_{21}x+h_{22}y+h_{23}&=\(h_{31}x+h_{32}y+1\)y^\prime\\\end{array}
  • \rm{H}のパラメータを含む項だけを左辺に移して整理して，次の2式を得る
\left\{\begin{array}{c}h_{11}x+h_{12}y+h_{13}-h_{31}xx^\prime-h_{32}yx^\prime&=x^\prime\\h_{21}x+h_{22}y+h_{23}-h_{31}xy^\prime-h_{32}yy^\prime&=y^\prime\\\end{array}
  • これを行列の形で表すと，次式になる
\left(\begin{array}{cccccccc}x&y&1&0&0&0&-xx^\prime&-yx^\prime\\0&0&0&x&y&1&-xy^\prime&-yy^\prime\\\end{array}\right)\left(\begin{array}{c}h_{11}\\h_{12}\\h_{13}\\h_{21}\\h_{22}\\h_{23}\\h_{31}\\h_{32}\\\end{array}\right)=\left(\begin{array}{c}x^\prime\\y^\prime\\\end{array}\right)
  • この連立方程式を解けばホモグラフィの8つのパラメータh_{11}-h_{32}が求まる
  • 1つの対応点から得られる方程式は2本
  • よって8÷2で4組の対応点が必要となる
  • 今\bf{x}_i=\left(\begin{array}{c}x_i & y_i\\\end{array}\right)という点を4組導入すると，次式のように書き換えられる
\left(\begin{array}{cccccccc}x_1&y_1&1&0&0&0&-x_1x_1^\prime&-y_1x_1^\prime\\0&0&0&x_1&y_1&1&-x_1y_1^\prime&-y_1y_1^\prime\\x_2&y_2&1&0&0&0&-x_2x_2^\prime&-y_2x_2^\prime\\0&0&0&x_2&y_2&1&-x_2y_2^\prime&-y_2y_2^\prime\\x_3&y_3&1&0&0&0&-x_3x_3^\prime&-y_3x_3^\prime\\0&0&0&x_3&y_3&1&-x_3y_3^\prime&-y_3y_3^\prime\\x_4&y_4&1&0&0&0&-x_4x_4^\prime&-y_4x_4^\prime\\0&0&0&x_4&y_4&1&-x_4y_4^\prime&-y_4y_4^\prime\\\end{array}\right)\left(\begin{array}{c}h_{11}\\h_{12}\\h_{13}\\h_{21}\\h_{22}\\h_{23}\\h_{31}\\h_{32}\\\end{array}\right)=\left(\begin{array}{c}x_1^\prime\\y_1^\prime\\x_2^\prime\\y_2^\prime\\x_3^\prime\\y_3^\prime\\x_4^\prime\\y_4^\prime\\\end{array}\right)
  • 両辺それぞれ行列\rm{A}，\rm{X}，\rm{B}の行列で書き換えると次式になる
\rm{A}\rm{X}=\rm{B}
  • ここで\rm{A}，\rm{B}は既知，\rm{X}が未知である
  • \rm{A}が正方行列の場合
    • \rm{A}^{-1}\rm{B}=\rm{X}となるので，パラメータ(=ホモグラフィ)が求められる
  • \rm{A}が非正方行列の場合
    • 4点以上からホモグラフィを推定する場合は，\rm{A}は非正方行列になる
    • その場合は擬似逆行列を利用して求めれば良い
    • 必要数以上ある対応点の組から，誤対応をLMeDs推定やRANSAC推定を利用して除去する
↑

サンプルコード †

  • findHomography と warpPerspective を使ったサンプルコード
  • 対応点からホモグラフィを推定し、本の表紙を、もとある本の上に重畳する
  • ロバスト推定のための各手法の効果を示すために、ノイズを加えた場合も表示する 
    1. #include <opencv2/calib3d/calib3d.hpp>

    2. #include <opencv2/highgui/highgui.hpp>

    3. #include <opencv2/imgcodecs/imgcodecs.hpp>

    4. #include <opencv2/imgproc/imgproc.hpp>

    5. #include <iostream>

    6.  

    7. const char inputForegroundImageFilename[] = "file/path/to/opencv/samples/data/box.png";

    8. const char inputBackgroundImageFilename[] = "file/path/to/opencv/samples/data/box_in_scene.png";

    9. const unsigned char kHigh = 255;

    10. const double kSigma = 1.0;

    11.  

    12. // in order of {x0,y0,1,   x1,y1,1,   x2,y2,1,   x3,y3,1,}

    13. // corresponding points in box.png

    14. // feature points extracted using SURF

    15. const double srcPoints[] = {

    16. 	224, 53,1,145,161,1,240,185,1,204,135,1,159,174,1,200,63, 1,236,154,1,229,163,1,170,170,1,

    17. 	218,155,1,237,152,1, 83, 54,1,188,166,1, 95,145,1,201,193,1,132,140,1,180,159,1,150, 46,1,

    18. 	180,183,1,180,132,1,155,152,1,145, 93,1, 63,132,1, 89,101,1,148, 95,1,228,130,1,210,147,1,

    19. 	133,175,1,154, 44,1, 70, 89,1,167,146,1,158,167,1,166,150,1,159, 85,1, 53, 73,1, 37, 91,1,

    20. 	 90,117,1,107,163,1,

    21. };

    22.  

    23. // corresponding points in box_in_scene.png

    24. // feature points extracted using SURF

    25. const double dstPoints[] = {

    26. 	243, 53,1,173,249,1,222,269,1,207,239,1,179,257,1,211,199,1,223,250,1,218,256,1,186,256,1,

    27. 	213,251,1,223,250,1,152,191,1,195,254,1,147,237,1,338,324,1,168,234,1,192,252,1,188,190,1,

    28. 	190,264,1,194,235,1,187,298,1,181,213,1,133,229,1,149,214,1,349,320,1,218,256,1,209,247,1,

    29. 	163,255,1,188,190,1,176,239,1,185,245,1,278,156,1,185,245,1,370,288,1,136,198,1,149,214,1,

    30. 	149,230,1,123,264,1,

    31. };

    32. const unsigned int cPoints = 38;

    33. const cv::Scalar lineColor = cv::Scalar(kHigh,kHigh,kHigh,0);

    34.  

    35. // draw lines between corresponding points

    36. // concatenate them horizontally to show it in one image

    37. void drawCorrespondingLine(const cv::Mat& foreground, const cv::Mat& background, cv::Mat& result, const cv::Mat& src, const cv::Mat& dst, const cv::Mat Mask)

    38. {

    39. 	using namespace cv;

    40. 	int heightDiff = background.rows - foreground.rows;

    41. 	if(heightDiff < 0)

    42. 	{

    43. 		// to connect in one image, foreground image must be equall or shorter than background in height

    44. 		result = background.clone();

    45. 		return;

    46. 	}

    47.  

    48. 	Mat object;

    49. 	Mat space;

    50. 	if(heightDiff > 0)

    51. 	{

    52. 		// add a blank space below the foreground

    53. 		space = Mat(heightDiff, foreground.cols, CV_8UC1);

    54. 		vconcat(foreground, space, object);

    55. 	}

    56. 	else

    57. 	{

    58. 		// foreground and background are same height

    59. 		// just copy the foreground

    60. 		object = foreground.clone();

    61. 	}

    62. 	// concatenate them horizontally

    63. 	hconcat(object, background, result);

    64.  

    65. 	// draw lines

    66. 	for(int iColumn = 0;iColumn < dst.rows;iColumn++)

    67. 	{

    68. 		if(Mask.data[iColumn] != 0)

    69. 		{

    70. 			Point objPoint  = Point((int)src.at<double>(iColumn, 0),                 (int)src.at<double>(iColumn, 1));

    71. 			Point backPoint = Point((int)dst.at<double>(iColumn, 0)+foreground.cols, (int)dst.at<double>(iColumn, 1));

    72. 			line(result, objPoint, backPoint, lineColor);

    73. 		}

    74. 	}

    75. }

    76.  

    77. // estimate the homography and show the estimated result

    78. void estimateHomography(cv::Mat& src, cv::Mat& dst, int method, const char* windowName)

    79. {

    80. 	using namespace cv;

    81.  

    82. 	Mat pointMask  = src.clone();

    83. 	Mat homography = Mat(3, 3, CV_64FC1);

    84. 	// estimate the homography

    85. 	homography = findHomography(src, dst, method, 3.0f, pointMask);

    86.  

    87. 	Mat foreground = imread(inputForegroundImageFilename, IMREAD_GRAYSCALE);

    88. 	Mat background = imread(inputBackgroundImageFilename, IMREAD_GRAYSCALE);

    89. 	Mat result     = background.clone();

    90. 	Mat whiteImage = Mat().zeros(foreground.size(), CV_8UC1);

    91. 	Mat maskImage  = Mat().zeros(background.size(), CV_8UC1);

    92. 	Mat correspondence;

    93.  

    94. 	// draw lines between corresponding lines

    95. 	drawCorrespondingLine(foreground, background, correspondence, src, dst, pointMask);

    96.  

    97. 	// warp the image based on homography

    98. 	warpPerspective(foreground, result, homography, result.size(),INTER_LINEAR, BORDER_TRANSPARENT);

    99.  

    100. 	// resize the mask to show which points are used

    101. 	resize(pointMask, pointMask, Size(20, background.rows), 0, 0, INTER_NEAREST);

    102. 	pointMask.convertTo(pointMask, CV_8U);

    103. 	pointMask *= kHigh;

    104.  

    105. 	// concatenate them horizontally

    106. 	std::vector<Mat> inputLists;

    107. 	inputLists.push_back(correspondence);

    108. 	inputLists.push_back(result.clone());

    109. 	inputLists.push_back(pointMask);

    110. 	hconcat(inputLists, result);

    111.  

    112. 	// show the image

    113. 	namedWindow(windowName);

    114. 	imshow(windowName, result);

    115. 	waitKey(0);

    116.  

    117. 	destroyAllWindows();

    118.  

    119. };

    120.  

    121. int main(int argc, char **argv){

    122.  

    123. 	using namespace cv;

    124. 	Mat src        = Mat(cPoints, 3, CV_64FC1, (void*)srcPoints);

    125. 	Mat dst        = Mat(cPoints, 3, CV_64FC1, (void*)dstPoints);

    126.  

    127. 	// estimate homography using default method

    128. 	estimateHomography(src, dst, 0,      "default");

    129. 	// estimate homography using RANSAC estimation method

    130. 	estimateHomography(src, dst, RANSAC, "RANSAC");

    131. 	// estimate homography using LMeDS estimation method

    132. 	estimateHomography(src, dst, LMEDS,  "LMeDS");

    133. 	// estimate homography using RHO estimation method

    134. 	estimateHomography(src, dst, RHO,    "RHO");

    135.  

    136. 	// estimate homography with some noise on the coordinates

    137. 	// in order to show the tolerance against the noise

    138. 	Mat srcNoiseAdded = src.clone();

    139. 	Mat dstNoiseAdded = dst.clone();

    140. 	RNG noise;

    141.  

    142. 	// add gaussian noise

    143. 	for(int i = 0;i < src.rows;i++)

    144. 	{

    145. 		srcNoiseAdded.at<double>(i,0) += noise.gaussian(kSigma);

    146. 		srcNoiseAdded.at<double>(i,1) += noise.gaussian(kSigma);

    147. 		dstNoiseAdded.at<double>(i,0) += noise.gaussian(kSigma);

    148. 		dstNoiseAdded.at<double>(i,1) += noise.gaussian(kSigma);

    149. 	}

    150.  

    151. 	// estimate the homography using each method

    152. 	estimateHomography(srcNoiseAdded, dstNoiseAdded, RANSAC, "RANSAC");

    153. 	estimateHomography(srcNoiseAdded, dstNoiseAdded, LMEDS,  "LMeDS");

    154. 	estimateHomography(srcNoiseAdded, dstNoiseAdded, RHO,    "RHO");

    155.  

    156.  

    157. 	// estimate homography with wrong correspondence

    158. 	// add ranndom correspondence coordinates and see if estimation can reject them

    159. 	srcNoiseAdded = src.clone();

    160. 	dstNoiseAdded = dst.clone();

    161.  

    162. 	// fill the noisePart with random coordinates

    163. 	// concatenate them using push_back()

    164. 	Mat noisePart = Mat(20, 3, CV_64FC1);

    165. 	noise.fill(noisePart, RNG::UNIFORM, Mat::zeros(1, 1, CV_64FC1), Mat::ones(1, 1, CV_64FC1) * 200);

    166. 	srcNoiseAdded.push_back(noisePart);

    167. 	noise.fill(noisePart, RNG::UNIFORM, Mat::zeros(1, 1, CV_64FC1), Mat::ones(1, 1, CV_64FC1) * 200);

    168. 	dstNoiseAdded.push_back(noisePart);

    169.  

    170. 	// estimate the homography using each method

    171. 	estimateHomography(srcNoiseAdded, dstNoiseAdded, RANSAC, "RANSAC");

    172. 	estimateHomography(srcNoiseAdded, dstNoiseAdded, LMEDS,  "LMeDS");

    173. 	estimateHomography(srcNoiseAdded, dstNoiseAdded, RHO,    "RHO");

    174.  

    175. 	return 0;

    176. }
↑

実行結果 †

  • 誤対応を含んだ推定結果
  • ハードコードされている対応点の座標には、誤対応点が38点中6点含まれている
  • 一番右側に表示されている白い帯は、ホモグラフィ推定に使われた対応点を表す(白=1=使用された、黒=0=誤対応)
    • 通常の推定結果
      • たった6点の誤対応のために推定が上手く行かない
      • 誤対応を推定しないので、Maskはすべての要素が1になる
        result000-noEstimation.png
    • RANSAC手法を使用した推定結果
      • 誤対応を取り除いて、正しくホモグラフィが推定されている
        result001-RANSAC.png
    • LMeDs手法を使用した推定結果
      • 誤対応を取り除いて、正しくホモグラフィが推定されている
      • RANSAC、LMeDs、RHOの3つの中で、LMeDsが一番数多くの正しい対応点を使用している
        result002-LMeD.png
    • RHO手法を使用した推定結果
      • 誤対応を取り除いて、正しくホモグラフィが推定されている
        result003-RHO.png
  • ノイズを加えた場合
  • 各座標に\sigma=1.0のノイズを加えてみた
    • RANSAC手法を使用した推定結果
      result004-RansacWithNoise.png
    • LMeDs手法を使用した推定結果
      result005-LmedWithNoise.png
    • RHO手法を使用した推定結果
      result006-RhoWithNoise.png
    • 一応RANSACが良い推定結果を出しているが、たまたまであり、これはロバスト推定ではなく、LM法による最適化のおかげ
    • ノイズの乗り方では、下図の様に、RANSACを使用してもホモグラフィの推定に失敗することもある
      result004.png
  • 誤対応を大量に含む場合
  • 乱数で発生させた適当な座標を対応点に追加してみた
    • RANSAC手法を使用した推定結果
      • 誤対応を取り除いて、正しくホモグラフィが推定されている
      • 右側の白い帯が特徴点が使われたか否かを表しているが、帯の下半分が黒くなっている
      • つまり誤対応として除去されたことを意味する
        result007-RansacWithWrongCorrespondence.png
    • LMeDs手法を使用した推定結果
      • もともとあった6点の誤対応に加え、20点の誤対応を追加したため、ホモグラフィの推定に失敗している
      • 右側の帯を見ると、誤対応関係を多数含んで無理やりホモグラフィを推定している
        result008-LmedWithWrongCorrespondence.png
    • RHO手法を使用した推定結果
      • 誤対応を取り除いて、正しくホモグラフィが推定されている
      • RANSAC同様、右側の帯下半分が黒くなっている
        result009-RhoWithWrongCorrespondence.png
  • RHOとRANSACの違いは検証できず
  • 対応点関係が十分にあるのならば、RANSACやRHOで弾いてしまうのが既知
  • ただし、誤対応の数が十分に少ないとわかっているならば、LMeDs手法の方も使える。
↑

実体ファイル †

↑

OpenCV 3.0系列 †

  • findHomography
    • modules/calib3d/include/opencv2/calib3d/calib3d.hpp
    • modules/calib3d/src/fundam.cpp
↑

OpenCV 2.4系列 †

  • modules/calib3d/include/opencv2/calib3d/calib3d.hpp
  • modules/calib3d/src/fundam.cpp
↑

その他 †

  • 2.4系列だと、findHomographyはCインタフェースのラッパー

ジャンル:OpenCV:OpenCV 2.4:OpenCV 3.0:OpenCV 3.1準拠
*1 厳密には等式(=)でなく，相似\(\simeq\)が成り立つ．解説の節では関係性を=ではなく\simeqで表している．等式に書き換えるためにはスケールファクタが必要
添付ファイル: fileresult009-RhoWithWrongCorrespondence.png 581件 [詳細] fileresult008-LmedWithWrongCorrespondence.png 612件 [詳細] fileresult007-RansacWithWrongCorrespondence.png 567件 [詳細] fileresult006-RhoWithNoise.png 630件 [詳細] fileresult005-LmedWithNoise.png 568件 [詳細] fileresult004.png 594件 [詳細] fileresult004-RansacWithNoise.png 591件 [詳細] fileresult003-RHO.png 626件 [詳細] fileresult002-LMeD.png 637件 [詳細] fileresult001-RANSAC.png 595件 [詳細] fileresult000-noEstimation.png 662件 [詳細]
トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2016-01-14 (木) 12:32:40 (889d)