摘  要： 灭点是分层重建过程的重要信息，其求解的准确程度直接关系到最后三维重建的效果。提出了一种基于Hough算法的直线聚类检测方法求取图像中的直线信息以及基于RANSAC的由直线信息估计灭点信息的改进算法，以提高估计灭点的鲁棒性。经试验证明，将所提出的算法应用到分层重建的系统中，在仅有两幅图像的情况下能准确地对目标模型进行重建。
关键词： Hough；直线聚类检测；灭点；分层重建；RANSAC

　三维重建是计算机视觉研究的核心问题之一。早期的三维重建主要利用黑白棋盘等结构已知的标定物事先进行标定，求得摄像机内参数，但这种方法只能应付静止和已知环境条件下的重建工作。1992年，Faugeras[1]提出自定标和分层重建等概念成为三维重建中最活跃的一个研究领域，之后许多学者在这一领域进行了进一步的研究[2-4]。分层重建将重建分成以下三个层次：射影重建、仿射重建和度量重建，重建过程相对早期传统标定更具有实用性好、灵活性强的特点。
　本文在仅有两幅图且没有摄像机运动的情况下，提出了基于Hough直线聚类检测方法。该方法将直线有目的性地按角度进行分组，以减少参与灭点估计的直线样本，降低估计算法复杂度；然后提出一种改进的RANSAC算法[5]。该算法结合极线几何约束的评价函数，重新构造了代价函数，进而提高了原RANSAC算法估计灭点的鲁棒性；最后阐述了根据不同的灭点对数情况构建变换矩阵进行分层重建的方法。
由于没有场景信息时，重建结果与真实模型相差一个全局缩放因子，而这并不影响视觉效果，因此，本文提到的欧氏重建均是指相差一个常数因子的重建。
1 重建方法
1.1 灭点
　空间上的一组平行线经过透视投影成像后，在成像平面上交于一点，称为灭点，灭点图如图1所示。图中，xp(p=1，2，3)即为灭点。灭点信息一般用于摄像机参数的求解，是非标定重建(如分层重建)的重要图像信息。灭点可以由直线检测算法求取获得。

1.2 基于Hough的直线聚类检测方法
　传统算法中，主要由Burns提出了相位编组法(一种基于点梯度聚类的直线检测方式[6])，其算法易实现但目的性不强。本文采用受噪声和曲线间断的影响均较小的Hough[7]变换检测直线方法，获取直线垂线和x轴正向的夹角(参数空间下的θ)，然后将参数空间的角度范围由[-90°，90°]转化为[0°，180°]，得到直线按照角度分类的统计直方图，横坐标为角度，纵坐标为在某角度范围内直线的个数。统计前一般需要对直线之间的间断进行预处理，通过设置间隔值减少参加估计灭点直线样本的数量。具体步骤如下：
　(1)将参数空间对应的像素位置旋转90-θ°，以便使其大概位于一条垂线上。
　(2)按旋转的程度(如x值)来对这些像素位置排序。
　(3)利用一阶微分函数找到裂口，忽视掉小裂口，合并间隔小的相邻线段。
　(4)返回比设置的阈值长的线段信息，并记录θ。
　(5)设立直方图进行聚类。
　Hough变换的缺点是既耗时又占空间，因此，本文采用概率Hough变换(PHT)改进方法，减少了时间消耗和储存空间的占用。
　获得统计直方图后需要对不同方向上的直线进行总体方向上的聚类(本文假设为三个方向。两个方向的情况与此相似，本文不予介绍)。聚类采用了下面的迭代方法：
　(1)对统计直方图进行曲线拟合(如高次样条函数)。正常情况下一般可以获得非边缘2个局部最小值(波谷)作为图像的分割阈值，即初始值T1、T2(T1<T2)。
　(2)设将直线按角度分为n组，采用T1、T2分割后得到直线集按角度由小到大依次为G1、G2、G3，求得G1、G2、G3范围内每条直线平均角度为μ1、μ2、μ3，然后重新求分割阈值：
　T1=(μ1+μ2)/2，T2=(μ2+μ3)/2
　(3)重复步骤(2)，直到T1、T2不再变化。一般迭代2~3次就可收敛。
1.3 改进的鲁棒估计灭点算法
　Schaffalitzky[8]、Rother[9-10]、陈付幸等人在利用直接信息检测估计灭点时都引入了随机抽样一致性RANSAC算法，一定程度上提高了单视图求灭点的效率与准确度。
本文基于二视图极线几何的关系，根据几何约束调整代价函数，改进了RANSAC估计灭点算法，同时保证了算法的鲁棒性与准确性。
　假设m1、m2互为匹配的灭点且为某无穷远点M到二视图图像的投影点的齐次坐标，则m1~H∞m2(“~”表示相差一个常数因子)，且有mT2Fm1≈0，即灭点在二视图中仍然受到极线几何约束，且仅符合极线几何关系的点才能考虑匹配。其中F(3×3)称为基本矩阵，其描述了双摄像机的射影几何关系。

　其中，C1为灭点位于直线上的最小化，C2为灭点位于极线上的最小化，C3为灭点到直线的距离和最小化，C4为灭点到对应极线距离和最小化。相比较而言，C1、C3之间和C2、C4之间都有相近最小化的代数意义，但是C3、C4比数值上的最小化C1、C2代价函数更具有几何意义，更能反映极线几何约束关系，所以本文选择C3、C4为评价灭点的双重代价函数。
　本文改进后的灭点估计算法步骤如下：
　(1)从检测到的直线中按照方向进行聚类，将分类中方向大致相同的直线随机选择M组数据样本，每组样本的大小为3[8]，在一定的置信概率下，保证M组样本中至少有一组样本不包含错误直线。
　(2)分别估计M组样本的灭点，并用所有直线段来检验消失点(全数据检验)，通过C=C3C4代价函数选择包含最多直线的灭点作为最优灭点，将最优灭点包含的直线作为局内直线(inliers)。本步骤需要反复进行。
　(3)用划分的inliers直线数据重新计算灭点，搜索附近外直线参加计算灭点。此步也可以重复进行。
　(4)由步骤(3)获得的稳定的数据作为正确的inliers 直线数据来估计最终消失点。
1.4 射影重建、仿射重建及欧氏重建
　本文根据获取灭点信息的不同情况，分别进行分层重建。分层重建即按照射影几何的层次关系依次实现射影重建、仿射重建和欧氏重建。当求得基础矩阵后就可以获得射影空间中的三维模型Xp，其与真实场景模型Xe之间相差一个射影变换T，则有：
　Xp=TAETAP Xe
　即确定无穷远平面π∞的位置(3个自由度)，获得变换矩阵TAP，将射影重建升级为仿射重建，然后确定无穷远平面上绝对二次曲线ω的位置(5个自由度)，获得变换矩阵TAE，从而将仿射重建升级为欧氏重建。
当有3对灭点时，可线性求解π∞，根据其灭点正交性线性求解ω；当少于3对灭点时，则采用模约束[2]等方式求解π∞及其对应的单应矩阵H∞，由w=HT∞ ωH∞，根据至少一对正交的灭点求解ω。对于单灭点的情况一般在多视图下重建。
1.5 误差检验
　本文采用反投影方法进行误差验证。当欧氏重建结束后，通过非线性最小化将空间点反投影到平面，将投影后的点信息与原点的欧式距离作为评价误差，则有：

　其中，i为视图数，j为每个视图上的特征点数。根据误差评价重建效果，若误差较大可进一步缩小1.2节和1.3节算法的阈值，以增加准确度。
2 实验过程
　实验一：对一张如图2所示的640×480的建筑物图片，采用本文的直线聚类检测算法进行处理，实验中分组数为180。图3为处理直线中小于5个像素的间断连接的聚类情况(T1=46.380 9，T2=132.707 2)，图4为图3按单位度数进行统计的直方图。对间断点进行处理，对间断小于20像素的直线进行合并，间断点处理后直线提取如图5所示，其统计图如图6所示。图4、图6的横坐标表示直线方向(单位为度)，纵坐标表示按某个组间间隔分组的每组直线数量。本文按角度分为180组，即组间间隔为1°。

　由图5、图6可以看到，通过直线段的连接，调整间隔连接为15个像素，可使直线的数量减少，达到合并和减少样本的目的(T1=46.303 9，T2=132.638 4)。
　实验二：采用实验室系统来模拟分层重建[11]，生成空间以XW为顶点物体(形如小房子)并沿z轴平移5个单位，随机增加0~0.002的噪音。模拟如表1、表2的初始内参A，通过A将三维点信息投影到模拟的二视图平面(模拟摄像机位置)上，让其中一个摄像机位于坐标轴中心，其分层重建模型如图7所示。本文所有实验使用同一观察视角(函数view(200，20))。图7~图11(x，y，z)为坐标系模拟物体所在的三维空间，单位为数值1。

　进行分层重建的步骤如下：
　(1)射影重建：根据模拟照相机中的二维点求取基础矩阵后进行射影重建，其效果图如图8所示。
　(2)仿射重建：原物体XW点附近随机添加带噪声点10个，以这些点连接的直线作为样本，然后通过本文算法估计3个正交方向3对灭点，根据无穷远性质获得变换矩阵进而完成仿射重建，其效果如图9、图10所示。

　(3)欧氏重建：由3对灭点线性求得绝对二次曲线的图像进行欧氏重建(相差一个常数因子)，其结果如图11所示，实验结果如表2所示。
　通过与传统代价函数只有C3算法作为评价比较，其重建效果如图12所示，由图可以得出本文算法能够获得较准确的估计灭点，从而获得更好的分层重建效果。估计灭点的比较如表3所示。

　本文方法主要是基于二视图的重建方法，当灭点为两对或更少时可采用多视图增加约束的方法实现。
　本文主要介绍了分层重建中灭点信息的求取过程中两个阶段的研究，即首先采用直线聚类检测方法检测直线，然后将分类后的直线样本通过改进的RANSAC估计算法类进行灭点估计。将直线检测与灭点的估计融合在一起，提高了灭点求取算法的效率和鲁棒性，使灭点的估计更具有针对性，同时根据得到的灭点信息结果介绍了对应的重建策略。本方法进行了分层重建，并通过模拟实验得到了理想结果。
参考文献
[1] FAUGERAS O D. Stratification of 3-D vision： projective， affine and metric representations[J]. Journal Optical Society of America， 1995，12(3)：465-484.
[2] POLLEFEYS M， GOOL V L， OOSTERLINCK A. The modulus constraint： A new constraint for self-calibration[C]. Proceedings  of  International Conference on Pattern Recognition， Vienna， Austria， 1996： 349-353.
[3] TRIGGS B. Auto-calibration and the absolute quadric[C].Proceedings of IEEE Conference on Computer Vision and Pattern Recognition， Puerto Rico， USA， 1997：610-614.
[4] HARTLEY R I. Euclidean reconstruction and invariants from multiple images[J].IEEE Transactions on Pattern Analysis and Machine Intelligent，1994，16(10)： 1020-1041.
[5] FISCHLER M A， BOLLES R C . Random sample consensus： a paradigm for model fitting with applications to image analysis and automated cartography[J]. Communications of the ACM， 1981，24(6)： 380-395.
[6] BURNS J B， HANSON A R. RISEMAN E M. Extracting straight lines[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，1986(4).
[7] LINGWORTH J， KITTLER J.A survey of the Hough transforms [J]. CVGIP， 1988，44：87-116.
[8] SCHAFFALITZKY F， ZISSERMAN A. Planar grouping for automatic detection of vanishing lines and points [J]. Image and Vision Computing， 2000，18(9)： 645-658.
[9] ROTHER C. A new approach for vanishing point detection in architectural environments[C]. British Machine Vision Conference (BMVC)， Bristol， UK， 2000： 382-392.
[10] ROTHER C . Multi-view reconstruction and camera recovery using a real or virtual reference plane[C]. PhD thesis， Royal Institute of Technology， Sweden， 2003.
[11] Yi Ma. An invitation to 3d vision[EB/OL]. http：//vision.ucla. edu/MASKS，2010-12-10.