归一化八点算法及图像之间基础矩阵求解

归一化8点算法及图像之间基础矩阵求解

多视图几何时利用在不同视点所拍摄图像间的关系，来研究照相机之间或者特征之间关系的一门科学。多视图几何中最重要的内容是双视图几何。如果有一个场景的两个视图以及视图中的对应图像点，那么根据照相机的空间相对位置关系、照相机的性质以及三维场景点的位置，可以得到对这些图像点的一些几何关系约束。

归一化8点算法介绍

基本矩阵是由下述方程定义：

其中x↔x’x↔x′是两幅图像的任意一对匹配点。由于每一组点的匹配提供了计算F系数的一个线性方程，当给定至少7个点（3×3）的齐次矩阵减去一个尺度，以及一个秩为2的约束），方程就可以计算出未知的FF。我们记点的坐标为x=(x,y,1)T，x’=(x’,y’,1)Tx=(x,y,1) T，x′=(x′,y′,1) T，则对应的方程为：

展开后有：

把矩阵F写成列向量的形式，则有：

给定n组点的集合，我们有如下方程：

如果存在确定（非零）解，则系数矩阵AA的秩最多是8。由于F是齐次矩阵，所以如果矩阵A的秩为8，则在差一个尺度因子的情况下解是唯一的。可以直接用线性算法解得。

如果由于点坐标存在噪声则矩阵A的秩可能大8（也就是等于9，由于A是n×9的矩阵）。这时候就需要求最小二乘解，这里就可以用SVD来求解，ff的解就是系数矩阵A最小奇异值对应的奇异向量，也就是A奇异值分解后A=UDVT

中矩阵V的最后一列矢量，这是在解矢量ff在约束‖f‖下取‖Af‖最小的解。以上算法是解基本矩阵的基本方法，称为8点算法。

归一化8点算法步骤

由于基本矩阵有一个重要的特点就是奇异性，F矩阵的秩是2。如果基本矩阵是非奇异的，那么所计算的对极线将不重合。所以在上述算法解得基本矩阵后，会增加一个奇异性约束。最简便的方法就是修正上述算法中求得的矩阵F。设最终的解为F′ ，令detF′=0下求得Frobenius范数（二范数）‖F−F ′‖最小的F′F′ 。这种方法的实现还是使用了SVD分解，若F=UDV ，此时的对角矩阵D=diag(r,s,t)，满足r≥s≥t，则F′=Udiag(r,s,0)VT 最小化范数‖F−F′‖，也就是最终的解。

所以8点算法由下面两个步骤组成：
1.求线性解 由系数矩阵AA最小奇异值对应的奇异矢量ff求的FF。
2.奇异性约束 是最小化Frobenius范数∥F−F′∥‖F−F′‖的F′F′代替FF。

归一化8点算法总结

8点算法是计算基本矩阵的最简单的方法。为了提高解的稳定性和精度，往往会对输入点集的坐标先进行归一化处理。在MVG的估计一章中推荐各向同性归一化，OpenCV的8点算法也是使用了各向同性，也就是使得各个点做平移缩放之后到坐标原点的均方根距离等于2–√ 2 。

对于归一化八点算法的总结如下：
给定n≥8n≥8组对应点xi↔x′i ，确定基本矩阵FF使得x’TiFxi=0x
算法：
1.归一化：根据xˆi=Txi，xˆ′i=T′x′i ，变换图像坐标。其中T和T′ 是有平移和缩放组成的归一化变换。
2.求解对应匹配的基本矩阵F’。
1.求线性解：用由对应点集xˆi↔xˆ′i 确定的系数矩阵Aˆ 的最小奇异值的奇异矢量确定Fˆ。
2.奇异性约束：用SVD对Fˆ 进行分解，令其最小奇异值为0，得到Fˆ′ 使得detF’=0。
3.解除归一化：令F=T’TFˆ′T。矩阵F就是数据xi↔x′i 对应的基本矩阵。

通常SVD算法来计算最小二乘法，由于上面的算法得出的解可能秩不为2（基础矩阵的秩小于等于2），所以需要通过最后一个奇异值置0来得到秩最接近2的基础矩阵。上面的函数忽略了一个重要的步骤：对图像坐标进行归一化，这可能会带来数值问题。

八点算法的优点：
线性求解，容易实现，运行速度快 。
八点算法的缺点：
对噪声敏感。

对极几何与基础矩阵

基本矩阵体现了两视图几何（对极几何，epipolar geometry）的内在射影几何（projective geometry）关系，基本矩阵只依赖于摄像机的内部参数K和外部参数R、t

对极平面 = 包含基线的平面
对极线 = 对极平面与像平面的交线
对极点= 基线与像平面相交点= 光心在另一幅图像中的投影

基础矩阵是对极几何的代数表达方式
基础矩阵描述了图像中任意对应点 x↔x’ 之间的约束关系

F 为 3x3 矩阵，秩为2，对任意匹配点对 x↔x’ 均满足xTFx’=0

1. 转置: 如果 F 是表述点对 (x, x’)之间的基础矩阵, 则 FT 表述点对 (x’,x)之间的基础矩阵；
2. 对极线: F 可以将点 x 映射到对应像平面上一条线 l=Fx’，同理可得 l’=FTx
3. 对极点: 对于所有对极线, 有 eTFx’=0, 全x’ →eTF=0, 同理有 Fe’=0
4. F 自由度为 7 , i.e. 3x3-1(homogeneous)-1(rank2)

实验详细需求

分别用七点、八点、十点（匹配点），计算基础矩阵
图片包含三种情况，即：
（1）左右拍摄，极点位于图像平面上，如图所示

（2）像平面接近平行，极点位于无穷远，如图所示

（3）图像拍摄位置位于前后，如图所示

针对上述情况，画出极点和极线，其中点坐标要均匀分布于各行

实验过程及代码

我是用了SIFT对两个图像进行特征提取以及匹配，然后使用归一化8点算法进行基本矩阵的求解。

代码实现：

# coding: utf-8
from PIL import Image
from numpy import *
from pylab import *
import numpy as np
from PCV.geometry import homography, camera,sfm
from PCV.localdescriptors import siftcamera = reload(camera)
homography = reload(homography)
sfm = reload(sfm)
sift = reload(sift)# 提取特征
im1 = array(Image.open('D:/test/test5/7.jpg'))
sift.process_image('D:/test/test5/7.jpg', 'im1.sift')im2 = array(Image.open('D:/test/test5/8.jpg'))
sift.process_image('D:/test/test5/8.jpg', 'im2.sift')l1, d1 = sift.read_features_from_file('im1.sift')
l2, d2 = sift.read_features_from_file('im2.sift')matches = sift.match_twosided(d1, d2)ndx = matches.nonzero()[0]
x1 = homography.make_homog(l1[ndx, :2].T)#将点集转化为齐次坐标表示
ndx2 = [int(matches[i]) for i in ndx]
x2 = homography.make_homog(l2[ndx2, :2].T)#将点集转化为齐次坐标表示d1n = d1[ndx]
d2n = d2