画面空間に 4 つの 2D ポイントがあり、それらを逆投影して 3D 空間に戻す必要があります。4 つの点のそれぞれが 3D 回転した剛体の四角形の角であることはわかっており、四角形のサイズもわかっています。これから3D座標を取得するにはどうすればよいですか?
特定の API を使用しておらず、既存の射影行列もありません。これを行うための基本的な数学を探しています。もちろん、単一の 2D ポイントを他の参照なしで 3D に変換するのに十分なデータはありませんが、4 つのポイントがある場合、それらはすべて同じ平面上で互いに直角であることがわかっていると思います。それらの間の距離がわかれば、そこからそれを把握できるはずです。残念ながら、私はその方法を完全に理解することはできません。
これは写真測量の傘下にある可能性がありますが、Google で検索しても役立つ情報は得られませんでした。
わかりました、私は答えを探してここに来ましたが、シンプルで簡単なものが見つからなかったので、先に進み、ばかげているが効果的な (そして比較的単純な) ことを行いました: モンテカルロ最適化です。
非常に簡単に言えば、アルゴリズムは次のとおりです。既知の 3D 座標が既知の 2D 座標に投影されるまで、投影行列をランダムに摂動します。
これはきかんしゃトーマスの静止画です。
GIMP を使用して、地面上の正方形であると思われるものの 2D 座標を見つけたとします (実際に正方形であるかどうかは、深さの判断に依存します)。
2D 画像(318, 247)で(326, 312)、 、(418, 241)、の 4 つのポイントを取得し(452, 303)ます。
(0, 0, 0)慣例により、これらの点は、(0, 0, 1)、(1, 0, 0)、およびの 3D 点に対応する必要があると言い(1, 0, 1)ます。つまり、y=0 平面の単位正方形です。
これらの 3D 座標のそれぞれを 2D に投影するには、4D ベクトルに 4x4 の投影行列を掛けてから[x, y, z, 1]、x 成分と y 成分を z で割って実際に遠近補正を取得します。これは多かれ少なかれgluProject()が行うことですgluProject()が、現在のビューポートを考慮し、別のモデルビュー マトリックスを考慮します (モデルビュー マトリックスは恒等マトリックスであると想定できます)。gluProject()私は実際に OpenGL で機能するソリューションが必要なので、ドキュメントを見ると非常に便利ですが、ドキュメントには式の z による除算がないことに注意してください。
アルゴリズムは、ある射影行列から開始し、必要な射影が得られるまでランダムに摂動することを覚えておいてください。では、4 つの 3D ポイントのそれぞれを投影し、必要な 2D ポイントにどれだけ近づくかを確認します。ランダムな摂動により、投影された 2D ポイントが上記でマークしたポイントに近づく場合、そのマトリックスを最初の (または以前の) 推測よりも改善したものとして保持します。
ポイントを定義しましょう。
# Known 2D coordinates of our rectangle
i0 = Point2(318, 247)
i1 = Point2(326, 312)
i2 = Point2(418, 241)
i3 = Point2(452, 303)
# 3D coordinates corresponding to i0, i1, i2, i3
r0 = Point3(0, 0, 0)
r1 = Point3(0, 0, 1)
r2 = Point3(1, 0, 0)
r3 = Point3(1, 0, 1)
いくつかの行列から始める必要があります。恒等行列は自然な選択のようです:
mat = [
[1, 0, 0, 0],
[0, 1, 0, 0],
[0, 0, 1, 0],
[0, 0, 0, 1],
]
実際に射影を実装する必要があります (これは基本的に行列の乗算です)。
def project(p, mat):
x = mat[0][0] * p.x + mat[0][1] * p.y + mat[0][2] * p.z + mat[0][3] * 1
y = mat[1][0] * p.x + mat[1][1] * p.y + mat[1][2] * p.z + mat[1][3] * 1
w = mat[3][0] * p.x + mat[3][1] * p.y + mat[3][2] * p.z + mat[3][3] * 1
return Point(720 * (x / w + 1) / 2., 576 - 576 * (y / w + 1) / 2.)
720 と576gluProject()はそれぞれ画像の幅と高さ (つまり、ビューポート) であり、576 から減算して、y 座標を上から数えたという事実をカウントしますが、OpenGL は通常、それらを上から数えます。下。z を計算していないことに気付くでしょう。これは、ここでは実際には z を必要としないためです (ただし、OpenGL が深度バッファーに使用する範囲内にあることを確認すると便利な場合があります)。
ここで、正しい解にどれだけ近づいているかを評価する関数が必要です。この関数によって返される値は、あるマトリックスが別のマトリックスよりも優れているかどうかを確認するために使用するものです。私は二乗距離の合計で行くことにしました。
# The squared distance between two points a and b
def norm2(a, b):
dx = b.x - a.x
dy = b.y - a.y
return dx * dx + dy * dy
def evaluate(mat):
c0 = project(r0, mat)
c1 = project(r1, mat)
c2 = project(r2, mat)
c3 = project(r3, mat)
return norm2(i0, c0) + norm2(i1, c1) + norm2(i2, c2) + norm2(i3, c3)
行列を摂動するには、ある範囲内のランダムな量で摂動する要素を選択するだけです。
def perturb(amount):
from copy import deepcopy
from random import randrange, uniform
mat2 = deepcopy(mat)
mat2[randrange(4)][randrange(4)] += uniform(-amount, amount)
project()(z を計算しないため、関数は実際にはまったく使用しないことに注意してくださいmat[2]。すべての y 座標が 0 であるため、mat[*][1]値も無関係です。この事実を使用して、それらの値を摂動しようとすることはありません。 、少しスピードアップしますが、それは演習として残されています...)
便宜上、perturb()これまでに見つけた最適な行列を何度も呼び出して近似の大部分を行う関数を追加しましょう。
def approximate(mat, amount, n=100000):
est = evaluate(mat)
for i in xrange(n):
mat2 = perturb(mat, amount)
est2 = evaluate(mat2)
if est2 < est:
mat = mat2
est = est2
return mat, est
あとは実行するだけです...:
for i in xrange(100):
mat = approximate(mat, 1)
mat = approximate(mat, .1)
これはすでにかなり正確な答えを与えていることがわかりました。しばらく実行した後、見つけたマトリックスは次のとおりです。
[
[1.0836000765696232, 0, 0.16272110011060575, -0.44811064935115597],
[0.09339193527789781, 1, -0.7990570384334473, 0.539087345090207 ],
[0, 0, 1, 0 ],
[0.06700844759602216, 0, -0.8333379578853196, 3.875290562060915 ],
]
前後の誤差あり2.6e-5。(計算で使用されなかったと言った要素が実際には最初の行列から変更されていないことに注意してください。これは、これらのエントリを変更しても評価の結果が変わらないため、変更が反映されないためです。)
以下を使用して行列を OpenGL に渡すことができますglLoadMatrix()(ただし、最初に転置することを忘れないでください。モデルビュー行列を恒等行列と共にロードすることを忘れないでください)。
def transpose(m):
return [
[m[0][0], m[1][0], m[2][0], m[3][0]],
[m[0][1], m[1][1], m[2][1], m[3][1]],
[m[0][2], m[1][2], m[2][2], m[3][2]],
[m[0][3], m[1][3], m[2][3], m[3][3]],
]
glLoadMatrixf(transpose(mat))
たとえば、z 軸に沿って移動して、トラックに沿ってさまざまな位置を取得できます。
glTranslate(0, 0, frame)
frame = frame + 1
glBegin(GL_QUADS)
glVertex3f(0, 0, 0)
glVertex3f(0, 0, 1)
glVertex3f(1, 0, 1)
glVertex3f(1, 0, 0)
glEnd()
確かに、これは数学的な観点からはあまりエレガントではありません。数値を差し込むだけで直接的な（そして正確な）答えを得ることができる閉じた形式の方程式は得られません。ただし、方程式を複雑にすることを心配することなく、制約を追加できます。たとえば、高さも含めたい場合は、家のその隅を使用して、(評価関数で) 地面から屋根までの距離はまあまあである必要があると言って、アルゴリズムを再度実行します。そうです、それは一種のブルートフォースですが、機能し、うまく機能します。
これは、マーカーベースの拡張現実の古典的な問題です。
正方形のマーカー (2D バーコード) があり、マーカーの 4 つのエッジを見つけた後、そのポーズ (カメラに対する平行移動と回転) を見つけたいとします。 概要図
この分野への最新の貢献については知りませんが、少なくともある時点 (2009 年) までは、RPP は上記の POSIT よりも優れていると考えられていました (実際、これは古典的なアプローチです)。リンクを参照してください。ソースを提供します。
http://www.emt.tugraz.at/publications/EMT_TR/TR-EMT-2005-01.pdf
http://www.emt.tugraz.at/system/files/rpp_MATLAB_ref_implementation.tar.gz
（追伸 - 少し古いトピックであることは知っていますが、とにかく、この投稿は誰かの役に立つかもしれません）
D. DeMenthonは、オブジェクトのモデルを知っているときに、2D画像の特徴点からオブジェクトのポーズ（空間内の位置と方向）を計算するアルゴリズムを考案しました。これが正確な問題です。
単一の画像からオブジェクトのポーズを見つける方法について説明します。画像内でオブジェクトの4つ以上の非同一平面上の特徴点を検出して一致させることができ、オブジェクト上のそれらの相対的なジオメトリがわかっていると仮定します。
このアルゴリズムはPositとして知られており、古典的な記事「25行のコードでのモデルベースのオブジェクトポーズ」（Webサイトのセクション4で入手可能）で説明されています。
記事への直接リンク：http ：//www.cfar.umd.edu/~daniel/daniel_papersfordownload/Pose25Lines.pdf OpenCVの実装：http：//opencv.willowgarage.com/wiki/Posit
アイデアは、正確なポーズに収束するまで、スケーリングされた正射影によって透視投影を繰り返し近似することです。
私の OpenGL エンジンでは、次のスニップはマウス/スクリーン座標を 3D ワールド座標に変換します。何が起こっているかの実際の説明については、コメントを読んでください。
/* FUNCTION: YCamera :: CalculateWorldCoordinates
引数: x マウス x 座標
y マウスの y 座標
vec 座標を保存する場所
返品: 該当なし
説明: マウス座標をワールド座標に変換します
*/
void YCamera :: CalculateWorldCoordinates(float x, float y, YVector3 *vec)
{
// START
GLint viewport[4];
GLdouble mvmatrix[16], projmatrix[16];
GLint real_y;
GLdouble mx, my, mz;
glGetIntegerv(GL_VIEWPORT, viewport);
glGetDoublev(GL_MODELVIEW_MATRIX, mvmatrix);
glGetDoublev(GL_PROJECTION_MATRIX, projmatrix);
real_y = viewport[3] - (GLint) y - 1; // viewport[3] is height of window in pixels
gluUnProject((GLdouble) x, (GLdouble) real_y, 1.0, mvmatrix, projmatrix, viewport, &mx, &my, &mz);
/* 'mouse' is the point where mouse projection reaches FAR_PLANE.
World coordinates is intersection of line(camera->mouse) with plane(z=0) (see LaMothe 306)
Equation of line in 3D:
(x-x0)/a = (y-y0)/b = (z-z0)/c
Intersection of line with plane:
z = 0
x-x0 = a(z-z0)/c <=> x = x0+a(0-z0)/c <=> x = x0 -a*z0/c
y = y0 - b*z0/c
*/
double lx = fPosition.x - mx;
double ly = fPosition.y - my;
double lz = fPosition.z - mz;
double sum = lx*lx + ly*ly + lz*lz;
double normal = sqrt(sum);
double z0_c = fPosition.z / (lz/normal);
vec->x = (float) (fPosition.x - (lx/normal)*z0_c);
vec->y = (float) (fPosition.y - (ly/normal)*z0_c);
vec->z = 0.0f;
}
2-D 空間から、作成できる有効な四角形が 2 つあります。元の行列射影を知らなければ、どれが正しいかわかりません。これは「ボックス」の問題と同じです。2 つの正方形が内側にあり、内側の 4 つの頂点がそれぞれ外側の 4 つの頂点に接続されています。ボックスを上から見ていますか、それとも下から見ていますか?
そうは言っても、行列変換 T を探しているのは...
{{x1, y1, z1}, {x2, y2, z2}, {x3, y3, z3}, {x4, y4, z4}} x T = {{x1, y1}, {x2, y2}, { x3、y3}、{x4、y4}}
(4×3)×T=(4×2)
したがって、T は (3 x 2) 行列でなければなりません。未知数が 6 個あります。
ここで、T に関する制約のシステムを構築し、Simplex で解決します。拘束を作成するには、最初の 2 点を通る線が 2 番目の 2 点を通る線と平行でなければならないことがわかっています。点 1 と 3 を通る直線は、点 2 と 4 を通る直線と平行でなければならないことがわかっています。点 1 と 2 を通る直線は、点 2 と 3 を通る直線と直交している必要があります。 1 と 2 からの線の長さは、3 と 4 からの線の長さと等しくなければなりません。1 と 3 からの線の長さは、2 と 4 からの線の長さと等しくなければならないことがわかります。
これをさらに簡単にするために、長方形について知っているので、すべての辺の長さがわかります。
これにより、この問題を解決するための多くの制約が得られるはずです。
もちろん、元に戻すには、T-inverse を見つけることができます。
@Rob: はい、無限の数の投影がありますが、ポイントが長方形の要件を満たさなければならない無限の数のプロジェクトはありません。
@nlucaroni: はい、これは投影に 4 つの点がある場合にのみ解けます。四角形が 2 点だけに投影される場合 (つまり、四角形の平面が投影面に直交する場合)、これは解決できません。
うーん... 家に帰って、この小さな宝石を書く必要があります。これは楽しそうですね。
アップデート:
Rons アプローチのフォローアップ: 四角形をどのように回転させたかがわかっていれば、Z 値を見つけることができます。
秘訣は、射影を行った射影行列を見つけることです。幸いなことに、これは可能であり、安価に行うことさえできます。関連する数学は、Paul Heckbert による論文「Projective Mappings for Image Warping」に記載されています。
http://pages.cs.wisc.edu/~dyer/cs766/readings/heckbert-proj.pdf
このようにして、投影中に失われた各頂点の均質な部分を元に戻すことができます。
これで、点ではなく 4 本の線がまだ残っています (Ron が説明したように)。ただし、元の長方形のサイズはわかっているため、何も失われません。Ron の方法と 2D アプローチからのデータを線形方程式ソルバーにプラグインし、z について解くことができるようになりました。そのようにして、各頂点の正確な Z 値を取得します。
注: これは次の理由で機能します。
本当に特殊なケースです。
お役に立てば幸いです、ニルス
ポイントが実際に長方形の一部であると仮定すると、私は一般的な考えを与えています:
最大間隔で 2 つの点を見つけます: これらはおそらく対角線を定義します (例外: 長方形が YZ 平面にほぼ平行である特殊なケースで、学生のために残されています)。それらを A、C と呼びます。BAD、BCD の角度を計算します。これらは、直角と比較して、3D 空間での向きを示します。z 距離を調べるには、投影された側面を既知の側面に関連付ける必要があります。次に、3D 投影法 (1/z ですか?) に基づいて、距離を知るための正しい軌道に乗っています。
形状が平面内の長方形であることがわかっている場合は、問題をさらに制限できます。確かに、「どの」平面を把握することはできないため、z=0 の平面上にあり、角の 1 つが x=y=0 にあり、エッジが x/y 軸に平行であることを選択できます。
したがって、3 次元の点は {0,0,0}、{w,0,0}、{w,h,0}、および {0,h,0} です。私は絶対的なサイズが見つからないことはかなり確信しているので、w / hの比率だけが関連しているので、これは不明です.
この平面に対して、カメラは空間内のある点 cx、cy、cz にある必要があり、方向 nx、ny、nz (長さ 1 のベクトルであるため、これらの 1 つは冗長です) を指している必要があり、focal_length/image_width を持っている必要があります。 wの係数。これらの数値は、3x3 射影行列に変わります。
これにより、w/h、cx、cy、cz、nx、ny、および w の合計 7 つの未知数が得られます。
合計 8 つの既知の値があります: 4 つの x+y ペアです。
これで解決できます。
次のステップは、Matlab または Mathmatica を使用することです。
3D から 2D に投影すると、情報が失われます。
単一点の単純なケースでは、逆投影により、3D 空間を通る無限の光線が得られます。
立体再構成は通常、2 つの 2D 画像から開始し、両方を 3D に投影します。次に、生成された 2 つの 3D 光線の交点を探します。
投影はさまざまな形式を取ることができます。直交または視点。正射影を想定していると思いますか？
あなたの場合、元の行列があると仮定すると、3D 空間に 4 つの光線があります。その後、3D 長方形の寸法によって問題を制限し、解決を試みることができます。
2D 投影面に平行ないずれかの軸を中心とした回転は方向があいまいになるため、ソリューションは一意ではありません。つまり、2 次元画像が z 軸に対して垂直である場合、3 次元の長方形を x 軸を中心に時計回りまたは反時計回りに回転すると、同じ画像が生成されます。y 軸についても同様です。
長方形の平面が z 軸に平行な場合、さらに多くの解があります。
元の射影行列がないため、射影に存在する任意のスケーリング係数によってさらにあいまいさが生じます。投影でのスケーリングと 3 次元での z 軸方向の平行移動を区別することはできません。これは、2 次元投影の平面ではなく、3 次元空間内の 4 点の相対位置のみに関心がある場合は問題ありません。
透視投影では、物事は難しくなります...
誰も答えなければ、家に帰ったら線形代数の本を出します。しかし、@ DG、すべての行列が可逆であるとは限りません。特異行列は可逆ではありません(行列式 = 0 の場合)。射影行列は 0 と 1 の固有値を持ち、正方でなければならないため、これは実際には常に発生します(冪等であるため、p^2 = p)。
簡単な例は [[0 1][0 1]] で、行列式 = 0 であり、これは線 x = y 上の射影です!
2D サーフェスへの投影には、同じ 2D 形状に投影される無限に多くの 3D 長方形があります。
このように考えてみてください: 3D 長方形を構成する 4 つの 3D ポイントがあります。それらを (x0,y0,z0)、(x1,y1,z1)、(x2,y2,z2)、(x3,y3,z3) と呼びます。これらの点を xy 平面に投影すると、z 座標 (x0,y0)、(x1,y1)、(x2,y2)、(x3,y3) がドロップされます。
ここで、3D 空間に投影したいので、z0、..、z3 をリバース エンジニアリングする必要があります。ただし、a) ポイント間の同じ xy 距離を維持し、b) 長方形の形状を維持する z 座標のセットは機能します。したがって、この (無限) セットの任意のメンバーは次のようになります。i <- R}。
編集@Jarrett：これを解決して、3D空間に長方形ができたと想像してください。ここで、その長方形を z 軸に沿って上下にスライドさせることを想像してください。これらの無限の量の平行移動された長方形はすべて、同じ xy 投影を持ちます。「正しい」ものを見つけたことをどのように確認しますか?
編集＃2：わかりました、これは私がこの質問に対して行ったコメントからのものです-これについての推論へのより直感的なアプローチ。
机の上に一枚の紙を持っていると想像してください。紙の各隅に無重力のレーザーポインターが取り付けられており、机に向かって下向きになっているとします。紙は 3D オブジェクトであり、机の上のレーザー ポインターのドットは 2D 投影です。
では、レーザー ポインターの点だけを見て、紙が机からどれだけ離れているかをどのように判断できるのでしょうか?
できません。用紙をまっすぐ上下に動かします。レーザー ポインターは、紙の高さに関係なく、机の上の同じスポットを照らします。
逆投影で Z 座標を見つけることは、机の上のレーザー ポインターのドットだけに基づいて紙の高さを見つけようとするようなものです。