21

私は 2 セットの 3D ポイント (元の点と再構成された点) とペアに関する対応情報を持っています。2 乗距離の合計が最小になるように、再構成セットを変換する 3D 変換とスケーリング係数を見つける必要があります (回転も同様に良いですが、ポイントも同様に回転するため、これは最優先事項ではなく、単純化のために省略される可能性があります。速度）。それで私の質問は - これは解決され、インターネットのどこかで利用可能ですか? 個人的には最小二乗法を使いたいのですが、あまり時間がないので（数学は多少得意ですが、あまり使わないので避けた方がよいでしょう）、他のソリューションが存在する場合は、それを使用したいと考えています。OpenCV を使用するなど、C++ でのソリューションを好みますが、アルゴリズムだけでも十分です。

そのような解がない場合は、私が自分で計算します。あまり迷惑をかけたくありません。

解決策：（あなたの回答から）
私にとってはカブシュアルゴリズムです。
基本情報: http://en.wikipedia.org/wiki/Kabsch_algorithm
一般的な解決方法: http://nghiaho.com/?page_id=671

まだ解決されていません: スケールも必要です。SVD のスケール値は私には理解できません。すべての軸に対して約1〜4のスケールが必要な場合(私が推定)、SVDスケールは約[2000、200、20]であり、まったく役に立ちません。

4

8 に答える 8

23

すでに Kabsch アルゴリズムを使用しているため、それを拡張してスケールを取得する Umeyamaの論文を参照してください。ポイントの標準偏差を取得し、スケールを次のように計算するだけです。

(1/sigma^2)*trace(D*S)

ここDで、 は回転推定における SVD 分解の対角行列であり、 (Kabsch が反射を適切な回転に修正するために使用する)の行列式の符号に応じて、S単位行列または対角行列のいずれかです。したがって、 がある場合は、最後の要素に +-1 を掛け ( の行列式の符号に応じて)、それらを合計し、ポイントの標準偏差で割ってスケールを取得します。[1 1 -1]UV[2000, 200, 20]UV

Eigenライブラリを使用している次のコードをリサイクルできます。

typedef Eigen::Matrix<double, 3, 1, Eigen::DontAlign> Vector3d_U; // microsoft's 32-bit compiler can't put Eigen::Vector3d inside a std::vector. for other compilers or for 64-bit, feel free to replace this by Eigen::Vector3d

/**
 *  @brief rigidly aligns two sets of poses
 *
 *  This calculates such a relative pose <tt>R, t</tt>, such that:
 *
 *  @code
 *  _TyVector v_pose = R * r_vertices[i] + t;
 *  double f_error = (r_tar_vertices[i] - v_pose).squaredNorm();
 *  @endcode
 *
 *  The sum of squared errors in <tt>f_error</tt> for each <tt>i</tt> is minimized.
 *
 *  @param[in] r_vertices is a set of vertices to be aligned
 *  @param[in] r_tar_vertices is a set of vertices to align to
 *
 *  @return Returns a relative pose that rigidly aligns the two given sets of poses.
 *
 *  @note This requires the two sets of poses to have the corresponding vertices stored under the same index.
 */
static std::pair<Eigen::Matrix3d, Eigen::Vector3d> t_Align_Points(
    const std::vector<Vector3d_U> &r_vertices, const std::vector<Vector3d_U> &r_tar_vertices)
{
    _ASSERTE(r_tar_vertices.size() == r_vertices.size());
    const size_t n = r_vertices.size();

    Eigen::Vector3d v_center_tar3 = Eigen::Vector3d::Zero(), v_center3 = Eigen::Vector3d::Zero();
    for(size_t i = 0; i < n; ++ i) {
        v_center_tar3 += r_tar_vertices[i];
        v_center3 += r_vertices[i];
    }
    v_center_tar3 /= double(n);
    v_center3 /= double(n);
    // calculate centers of positions, potentially extend to 3D

    double f_sd2_tar = 0, f_sd2 = 0; // only one of those is really needed
    Eigen::Matrix3d t_cov = Eigen::Matrix3d::Zero();
    for(size_t i = 0; i < n; ++ i) {
        Eigen::Vector3d v_vert_i_tar = r_tar_vertices[i] - v_center_tar3;
        Eigen::Vector3d v_vert_i = r_vertices[i] - v_center3;
        // get both vertices

        f_sd2 += v_vert_i.squaredNorm();
        f_sd2_tar += v_vert_i_tar.squaredNorm();
        // accumulate squared standard deviation (only one of those is really needed)

        t_cov.noalias() += v_vert_i * v_vert_i_tar.transpose();
        // accumulate covariance
    }
    // calculate the covariance matrix

    Eigen::JacobiSVD<Eigen::Matrix3d> svd(t_cov, Eigen::ComputeFullU | Eigen::ComputeFullV);
    // calculate the SVD

    Eigen::Matrix3d R = svd.matrixV() * svd.matrixU().transpose();
    // compute the rotation

    double f_det = R.determinant();
    Eigen::Vector3d e(1, 1, (f_det < 0)? -1 : 1);
    // calculate determinant of V*U^T to disambiguate rotation sign

    if(f_det < 0)
        R.noalias() = svd.matrixV() * e.asDiagonal() * svd.matrixU().transpose();
    // recompute the rotation part if the determinant was negative

    R = Eigen::Quaterniond(R).normalized().toRotationMatrix();
    // renormalize the rotation (not needed but gives slightly more orthogonal transformations)

    double f_scale = svd.singularValues().dot(e) / f_sd2_tar;
    double f_inv_scale = svd.singularValues().dot(e) / f_sd2; // only one of those is needed
    // calculate the scale

    R *= f_inv_scale;
    // apply scale

    Eigen::Vector3d t = v_center_tar3 - (R * v_center3); // R needs to contain scale here, otherwise the translation is wrong
    // want to align center with ground truth

    return std::make_pair(R, t); // or put it in a single 4x4 matrix if you like
}
于 2015-08-27T08:53:53.103 に答える
7

3D 点の場合、この問題は絶対方向問題として知られています。C++ 実装は Eigen http://eigen.tuxfamily.org/dox/group__Geometry__Module.html#gab3f5a82a24490b936f8694cf8fef8e60および論文http://web.stanford.edu/class/cs273/refs/umeyama.pdfから入手できます。

cv::cv2eigen() 呼び出しで行列を固有値に変換することにより、opencv 経由で使用できます。

于 2014-08-09T23:02:46.317 に答える
4

両方のポイントセットの変換から始めます。それらの図心が座標系の原点と一致するようにします。並進ベクトルは、これらの重心の違いにすぎません。

これで、行列PとQとして表される2セットの座標ができました。線形演算子（スケーリングと回転の両方を実行する）を適用することにより、他のポイントから1セットのポイントを取得できます。この演算子は、3x3行列Xで表されます。

P * X = Q

適切なスケール/回転を見つけるには、この行列方程式を解き、Xを見つけてから、それぞれがスケーリングまたは回転を表すいくつかの行列に分解する必要があります。

それを解く簡単な（しかしおそらく数値的に安定していない）方法は、方程式の両方の部分を転置行列Pに乗算し（非正方行列を取り除くため）、次に方程式の両方の部分を逆行列PT *に乗算することです。 P：

P T * P * X = P T * Q

X =（P T * P）-1 * P T * Q

特異値分解を行列Xに適用すると、2つの回転行列とスケール係数を持つ行列が得られます。

X = U * S * V

ここで、 Sはスケール係数（座標ごとに1つのスケール）を持つ対角行列です。UとVは回転行列です。一方はポイントを適切に回転させて座標軸に沿ってスケーリングできるようにし、もう一方はポイントをもう一度回転させて方向を揃えます。ポイントの2番目のセットに。

例（簡単にするために2Dポイントを使用）：

P =  1     2     Q =   7.5391    4.3455
     2     3          12.9796    5.8897
    -2     1          -4.5847    5.3159
    -1    -6         -15.9340  -15.5511

方程式を解いた後：

X =  3.3417   -1.2573
     2.0987    2.8014

SVD分解後：

U = -0.7317   -0.6816
    -0.6816    0.7317

S =  4  0
     0  3

V = -0.9689   -0.2474
    -0.2474    0.9689

ここで、SVDは、マトリックスPに対して実行したすべての操作を適切に再構築してマトリックスQを取得しました。角度0.75で回転し、X軸を4スケール、Y軸を3スケール、角度-0.25で回転します。

ポイントのセットが均一にスケーリングされる場合（スケール係数は各軸で等しい）、この手順は大幅に簡略化される可能性があります。

Kabschアルゴリズムを使用して、平行移動/回転の値を取得するだけです。次に、これらの平行移動と回転を実行します（図心は座標系の原点と一致する必要があります）。次に、ポイントの各ペア（および各座標）について、線形回帰を推定します。線形回帰係数は、まさにスケールファクターです。

于 2013-01-25T16:11:32.147 に答える
1

ICP（反復最接近点）を試してみることをお勧めします。3Dポイントの2つのセットが与えられると、最初のセットから2番目のセットに移動するための変換（回転+平行移動）が通知されます。C ++の軽量実装に興味がある場合は、libicpを試してください。

幸運を！

于 2012-11-19T16:36:46.877 に答える
1

良い説明対応する3Dポイント間の最適な回転と平行移動を見つける

コードはmatlabにありますが、cv::SVD関数を使用してopenglに変換するのは簡単です。

于 2012-11-18T04:37:35.593 に答える
0

ポイントがすべての方向に均一にスケーリングされている場合、スケールはSVDなしで推測できます（SVDのスケールマトリックスも理解できませんでした）。これが私が同じ問題を解決した方法です：

  1. ポイント クラウド内の各ポイントから他のポイントまでの距離を測定して、距離の 2 次元テーブルを取得します。ここで、(i,j) のエントリはノルム (point_i-point_j) です。もう一方のポイント クラウドに対して同じことを行うと、2 つのテーブルが得られます。1 つは元のポイント用で、もう 1 つは再構築されたポイント用です。

  2. 1 つのテーブルのすべての値を、他のテーブルの対応する値で割ります。ポイントが互いに対応しているため、距離も対応しています。理想的には、結果のテーブルはすべての値が互いに等しいものであり、これがスケールです。

  3. 部門の中央値は、探しているスケールにかなり近いはずです。平均値も近いですが、外れ値を除外するために中央値を選択しました。

これで、スケール値を使用して再構築されたすべてのポイントをスケーリングし、回転の推定に進むことができます。

ヒント: ポイント クラウド内のポイントが多すぎてそれらすべての間の距離を見つけることができない場合は、両方のポイント クラウドで同じサブセットである限り、距離のより小さなサブセットも機能します。理想的には、測定ノイズがない場合、たとえば 1 つの点群が回転するだけで他の点群から直接派生する場合など、1 つの距離ペアだけが機能します。

于 2015-07-28T07:37:26.993 に答える