广州外贸型网站设计,微信小程序申请,网站开发需要经费么,韩文网站建设12 Structure Computation
本章讲述如何在已知基本矩阵 F F F和两幅图像中若干对对应点 x ↔ x ′ x \leftrightarrow x x↔x′的情况下计算三维空间点 X X X的位置。 文章目录 12 Structure Computation12.1 Problem statement12.2 Linear triangulation methods12.3 Geomet…12 Structure Computation
本章讲述如何在已知基本矩阵 F F F和两幅图像中若干对对应点 x ↔ x ′ x \leftrightarrow x x↔x′的情况下计算三维空间点 X X X的位置。 文章目录 12 Structure Computation12.1 Problem statement12.2 Linear triangulation methods12.3 Geometric error cost function12.4 Sampson approximation (first-order geometric correction)12.5 An optimal solution12.5.1 Reformulation of the minimization problem12.5.2 Details of the minimization12.5.3 Local minima12.5.4 Evaluation on real images 12.6 Probability distribution of the estimated 3D point12.7 Line Reconstruction 12.1 Problem statement
我们假设已知摄像机矩阵 P P P和 P ′ P P′基本矩阵 F F F还有两幅图像中若干对对应点 x ↔ x ′ x \leftrightarrow x x↔x′。因为有噪声的存在图像中的点反投影回去的两条射线不一定相交 x F x ′ xFx xFx′也不一定等于0所以简单三角化不一定可行。
我们先回忆一下第10章三维重建的知识。我们介绍了好几种不同种类的三维重建这取决于我们对摄像机矩阵的知晓程度。那么结合本章的三角化我们希望三角化在不同种类的重建之间能给出同样的结果。我们首先用 τ \tau τ来代表三角化的过程如果 τ \tau τ能满足下式那么我们就说三角化在变换 H H H下是不变的 τ ( x , x ′ , P , P ′ ) H − 1 τ ( x , x ′ , P H − 1 , P ′ H − 1 ) \tau(x,x,P,P) H^{-1}\tau(x,x,PH^{-1},PH^{-1}) τ(x,x′,P,P′)H−1τ(x,x′,PH−1,P′H−1)
为什么需要讨论这个这是因为我们首先需要确定三维重建的种类才能决定优化目标的形式。如果我们只知道摄像机矩阵是一个projective matrix那么我们就不能在三维空间最优化目标函数。因为这样的优化函数在投影变换中不能给出唯一的结果因为距离和垂直度等概念在projective geometry的背景下无效。所以本章给出的三角化方法优化的是二维图像上的距离所以本章的方法在投影变换projective transformation中是不变的。
12.2 Linear triangulation methods
对于两幅图像我们分别有 x P X , x ′ P X ′ xPX,xPX xPX,x′PX′我们可以将第一个方程改成 x × P X 0 x \times PX0 x×PX0第二幅图也一样。我们继续改写就可以有 A X 0 AX0 AX0。
Homogeneous method 找出 A A A最小特征值对应的特征向量
Inhomogeneous method 参见4.1.2节原书P90
讨论 Inhomogeneous method假设点不在无穷远处不适合projective reconstruction。其实这两个方法都不适合。
Inhomogeneous method适合affine reconstruction。
Homogeneous method不适合affine reconstruction。
12.3 Geometric error cost function 由于图像中有噪声的存在 x ↔ x ′ x \leftrightarrow x x↔x′其实不能满足极线的约束我们用 x ˉ , x ′ ˉ \bar{x},\bar{x} xˉ,x′ˉ表示没有噪声的点。那么我们可以构建以下优化函数 C ( x , x ′ ) d ( x , x ^ ) 2 d ( x ′ , x ^ ′ ) 2 s u b j e c t t o x ′ ^ T F x ^ 0 C(x,x) d(x,\hat{x})^2 d(x,\hat{x})^2 \\ subject \ to \ \hat{x}^{T}F\hat{x} 0 C(x,x′)d(x,x^)2d(x′,x^′)2subject to x′^TFx^0
其中 d d d表示两点之间的欧氏距离。这相当于最小化点 X X X的重投影误差该点 X X X通过与 F F F一致的投影矩阵映射到两个点如图12.2。
12.4 Sampson approximation (first-order geometric correction) 我们定义 X X X与 X ^ \hat{X} X^之间的差为 δ X \delta_X δX δ X − J T ( J J T ) − 1 ϵ \delta_X -J^T(JJ^T)^{-1} \epsilon δX−JT(JJT)−1ϵ
其中 ϵ x ′ T F x J ∂ ϵ / ∂ x [ ( F T x ′ ) 1 , ( F T x ′ ) 2 , ( F X ) 1 , ( F X ) 2 ] \epsilon x^{T}Fx \\ J \partial \epsilon/ \partial x[(F^{T}x)_{1}, (F^{T}x)_{2},(FX)_{1},(FX)_{2}] ϵx′TFxJ∂ϵ/∂x[(FTx′)1,(FTx′)2,(FX)1,(FX)2]
其中 ( F T x ′ ) 1 f 11 x ′ f 21 y ′ f 31 (F^{T}x)_{1}f_{11}xf_{21}yf_{31} (FTx′)1f11x′f21y′f31以此类推。 所以我们可以看出该差值其实是基本矩阵方程关于 x x x的导数 那么 X X X和 X ^ \hat{X} X^之间的关系可以写成 X ^ X δ X \hat{X} X \delta_X X^XδX
我们只需要把 δ X \delta_X δX算出来然后对计算出的理论点 X X X按照上式进行一个纠正就可以了。
12.5 An optimal solution
本节介绍一种可以找到全局最优解的优化函数并且是非迭代的我们同时假设噪声服从高斯分布。
12.5.1 Reformulation of the minimization problem
先对问题进行一个梳理。
我们知道第一幅图的极点一定在极线上第二幅图的极点也满足这个性质。反过来在极线上的点也满足基本矩阵的约束。那么就能让观测到的点尽可能靠近极线也就是找观测点到极线的距离并使其最小。
所以我们就可以构建出以下损失函数 d ( x , l ) 2 d ( x ′ l ′ ) 2 d(x,l)^2 d(xl)^2 d(x,l)2d(x′l′)2
我们的策略如下:
将极线方程参数化所以第一幅图像中的极线方程就可以写为 l ( t ) l(t) l(t)利用基本矩阵 F F F,和 l ( t ) l(t) l(t)来计算第二幅图像中的极线l ′ ( t ) (t) ′(t)将损失函数写成 d ( x , l ( t ) ) 2 d ( x ′ l ′ ( t ) ) 2 d(x,l(t))^2 d(xl(t))^2 d(x,l(t))2d(x′l′(t))2求解最优的 t t t
12.5.2 Details of the minimization
接下来我们讲一下需要注意的一些细节。
首先两幅图中对应点都不能与极点重合。
并且我们可以对两幅图都做一个刚体变换那么 x , x ′ x,x x,x′就可以被放置在原点 ( 0 , 0 , 1 ) (0,0,1) (0,0,1)那么两幅图的极点分别是 ( 1 , 0 , f ) , ( 1 , 0 , f ′ ) (1,0,f),(1,0,f) (1,0,f),(1,0,f′)。我们知道极点也是要满足 F F F的所以我们有 F ( 1 , 0 , f ) T ( 1 , 0 , f ′ ) F 0 F(1,0,f)^T (1,0,f)F 0 F(1,0,f)T(1,0,f′)F0如此以来我们就可以把基本矩阵表示为一种特殊形式 F [ f f ′ d − f ′ c − f ′ d − f b a b − f d c d ] F \left[ \begin{matrix} ffd -fc -fd \\ -fb a b\\ -fd c d \\ \end{matrix} \right] F ff′d−fb−fd−f′cac−f′dbd
同时我们也知道极线会通过极点 ( 1 , 0 , f ) (1,0,f) (1,0,f)我们再找一个特殊点那就是极线与 y y y轴的交点 ( 0 , t , 1 ) (0,t,1) (0,t,1)所以极线就可以写成 ( 1 , 0 , f ) × ( 0 , t , 1 ) ( t f , 1 , − t ) (1,0,f) \times (0,t,1) (tf,1,-t) (1,0,f)×(0,t,1)(tf,1,−t)那么该直线到原点的距离就是 d ( x , l ( t ) ) 2 t 2 1 ( t f ) 2 d(x,l(t))^2 \frac{t^2}{1(tf)^2} d(x,l(t))21(tf)2t2
紧接着我们找下一个极线 l ′ ( t ) F ( 0 , t , 1 ) T ( − f ′ ( c t d ) , a t b , c t d ) T l(t) F(0,t,1)T(-f(ctd),atb,ctd)^T l′(t)F(0,t,1)T(−f′(ctd),atb,ctd)T
该极线到原点的距离 d ( x ′ , l ′ ( t ) ) 2 ( c t d ) 2 ( a t v ) 2 f ′ 2 ( c t d ) 2 d(x,l(t))^2 \frac{(ctd)^2}{(atv)^2 f^2(ctd)^2} d(x′,l′(t))2(atv)2f′2(ctd)2(ctd)2
于是我们把 d ( x ′ , l ′ ( t ) ) 2 , d ( x , l ( t ) ) 2 d(x,l(t))^2, d(x,l(t))^2 d(x′,l′(t))2,d(x,l(t))2 加在一起记为 s ( t ) s(t) s(t)求导数令导数等于0就可以了。
一些讨论 s ( t ) s(t) s(t)是6次多项式那么它就有6个实根对应于3个最小值和3个最大值。顺便别忘了检查 x → ∞ x \rightarrow \infty x→∞的情况。
下面我们把整个算法流程重复一遍对应于P318算法12.1。
算法输入观测到的对应点 x ↔ x ′ x \leftrightarrow x x↔x′基本矩阵 F F F
算法输出寻找一对 x ^ ↔ x ^ ′ \hat{x} \leftrightarrow \hat{x} x^↔x^′可以使几何损失函数最小同时这一对点满足 x ^ ′ T F x ^ 0 \hat{x}^{T}F\hat{x} 0 x^′TFx^0
算法步骤 定义一对转换矩阵可以把 x ( x , y , 1 ) T , x ′ ( x ′ , y ′ , t ) T x(x,y,1)^{T},x(x,y,t)^{T} x(x,y,1)T,x′(x′,y′,t)T转换到原点 T [ 1 − x 1 − y 1 ] T\left[ \begin{matrix} 1 -x \\ 1 -y \\ 1\\ \end{matrix} \right] T 11−x−y1 T ′ T T′的形式与 T T T是类似的 将基本矩阵 F F F变成 T ′ − T F T − 1 T^{-T}FT^{-1} T′−TFT−1 计算左极点 e ( e 1 , e 2 , e 3 ) e(e_1,e_2,e_3) e(e1,e2,e3)和右极点 e ′ ( e 1 ′ , e 2 ′ , e 3 ′ ) e(e_1,e_2,e_3) e′(e1′,e2′,e3′)并且归一化使得 e 1 e 2 1 e_1e_21 e1e21 构造两个旋转矩阵这两个矩阵可以把 e e e旋转到 ( 1 , 0 , e 3 ) (1,0,e_3) (1,0,e3) ( 1 , 0 , e 3 ′ ) (1,0,e_3) (1,0,e3′). R [ e 1 e 2 − e 2 e 1 1 ] R\left[ \begin{matrix} e_1 e_2 \\ -e_2 e_1 \\ 1\\ \end{matrix} \right] R e1−e2e2e11 R ′ R R′与 R R R类似 把 F F F改成 R ′ F R T RFR^{T} R′FRT 设置以下等式 f e 3 , f ′ e 3 , a F 22 , b F 23 , c F 32 , d F 33 fe_3,fe_3,aF_{22},bF_{23},cF_{32},dF_{33} fe3,f′e3,aF22,bF23,cF32,dF33 将第6步中的等式带入 s ( t ) s(t) s(t)中求解t 对求得的解进行验证同时检查 t → ∞ t \rightarrow \infty t→∞ 的情况 将 t t t带入极线方程找到 x ^ x ^ ′ \hat{x}\hat{x} x^x^′极线知道了观测点 x , x ′ x,x x,x′也知道求直线上某个点它要满足到已知点距离最近由于我们把 x , x ′ x,x x,x′转到了原点那么问题就转变成了直线上求某一点它到原点距离最近。书中给出了一个公式对于一个一般的直线 ( λ , μ , ν ) (\lambda, \mu, \nu) (λ,μ,ν)直线上到原点最近的点是 ( − λ ν , − μ ν , λ 2 μ 2 ) (-\lambda \nu, -\mu \nu, \lambda^2\mu^2) (−λν,−μν,λ2μ2) 知道 x ^ , x ^ ′ \hat{x},\hat{x} x^,x^′后再把他们旋转到原坐标 x ^ T − 1 R T x ^ \hat{x} T^{-1} R^{T} \hat{x} x^T−1RTx^ x ^ ′ T − 1 R T x ^ ′ \hat{x} T^{-1} R^{T} \hat{x} x^′T−1RTx^′ 可以顺便利用 x ^ , x ^ ′ \hat{x},\hat{x} x^,x^′计算出三维空间点 X ^ \hat{X} X^三角化12.2
12.5.3 Local minima g ( t ) g(t) g(t)有6个自由度所以它最多有三个最小值。那么如果用迭代的方法去寻找最小值可能陷在局部最小值里出不来。
12.5.4 Evaluation on real images
本节大概展示了一些实验结果在P320
12.6 Probability distribution of the estimated 3D point
估计三维点的概率分布。
通过两幅图像估计出来的三维空间点应该是满足一定概率分布的。其准确与否主要取决于从摄像机出发的两条射线之间的角度。本节就对这个问题进行建模。书中为了简化这个问题只考虑空间某平面上的点 X ( x , y ) T X(x,y)^T X(x,y)T其图像上的点分别表示为 x f ( X ) , x ′ f ′ ( X ) xf(X), xf(X) xf(X),x′f′(X), f , f ′ f,f f,f′是 2 × 3 2 \times 3 2×3的矩阵而不是 3 × 4 3 \times 4 3×4 如果忘了可以复习一下p175 6.4.2节
我们线考虑第一幅图像上的点 x x x并且我们假设噪声服从均值为0方差为 σ 2 \sigma^2 σ2的高斯分布那么在已知 X X X的条件下 x x x的概率分布可以表示为 p ( x ∣ X ) p(x|X) p(x∣X)对第二幅图上的点 x ′ x x′有相同的结论 p ( x ′ ∣ X ) p(x|X) p(x′∣X)。那么当 x , x ′ x,x x,x′已知的时候我们可以用贝叶斯公式反推 X X X的概率分布 p ( X ∣ x , x ′ ) p ( x , x ′ ∣ X ) p ( X ) / p ( x , x ′ ) p(X|x,x) p(x,x|X)p(X) / p(x,x) p(X∣x,x′)p(x,x′∣X)p(X)/p(x,x′)
再加上 x , x ′ x,x x,x′独立的假设上式就可以化成 p ( X ∣ x , x ′ ) ∼ p ( x ∣ X ) p ( x ′ ∣ X ) p(X|x,x) \sim p(x|X)p(x|X) p(X∣x,x′)∼p(x∣X)p(x′∣X)
12.7 Line Reconstruction
我们现在要重建空间中的一个线段。它在两幅图像上分别表示为 l , l ′ l, l l,l′。我们可以把 l , l ′ l,l l,l′反投影回去那么他们在空间中就是两个平面 π , π ′ \pi, \pi π,π′, 这两个平面的交点就是所求直线。我们可以形式化的表示为 π P T l , π ′ P ′ T l ′ \pi P^Tl, \pi P^T l πPTl,π′P′Tl′那么三维空间中的线就可以用这两个平面来表示 ( L L L是一个 2 × 4 2 \times 4 2×4的矩阵) L [ l T P l ′ T P ′ ] L \left[ \begin{matrix} l^T P \\ l^T P \end{matrix} \right] L[lTPl′TP′]
空间中的点 X X X在 L L L上所以 L X 0 LX0 LX0 退化的情况
如果这个直线在极平面上那么上一节的方法就失效了而且这样直线会和基线相交。在实际情况下几乎要和基线相交的线也不能用以上方法来重建.
多平面相交的重建
假设有 n n n个平面那么我们就他们像前文 L L L一样放在一起形成一个 n × 4 n \times 4 n×4的矩阵 A A A。对 A A A做SDV分解 A U D V T AUDV^T AUDVT从 D D D中找出两个最大的特征值对应的特征向量用他们来表示平面也可以假设空间中直线 L L L投影到各个平面然后计算投影直线和观测直线之间的几何损失函数用极大似然估计求解。
