基于度约束的最大生成树算法提取影像拓扑骨架

最大生成树（MST）算法是在有权图的基础上提取一个包含边数最小的情况下累计权重最大的无环图的过程。虽然直接采用最大生成树算法可以保证SCN中包含边的数目最少，但是为保证SfM算法重建模型的稳定性，需要确保每对匹配点至少存在于3张影像中。本研究在最大生成树算法的基础上加入最小度约束，发展为基于度约束的最大生成树算法（Degree Bounded MST，DBMST），即当d（vi）=2时，既能保证每张影像vi均与其他两张邻接影像进行匹配，又能保证提取的SCN中边数最少。据此提取SCN的边集将组成一个有环图。

利用DB-MST提取影像拓扑骨架的步骤。

算法描述：

该算法可提取满足三目视觉匹配的影像拓扑骨架。

输入：

有权的影像拓扑关系图G=（V，E），ci，j∈{0，1}表示拓扑关系，ei，j表示边的权重。

输出：

影像拓扑骨架SCN=[n×n]，SCN（i，j）∈{0，1}。(www.xing528.com)

算法步骤：

步骤1：初始化E（SCN）=ϕ。

步骤2：以v1为始端，vn为终端提取G的最大生成树Tmst，且有d（vi）=2，i≠1，n。

步骤3：分别对v1和vn寻找其权重值次大的邻接边c1，j和ck，n。

步骤4：更新E（SCN）={E（Tmst），c1，j，ck，n}。

步骤5：据E（SCN）生成影像拓扑骨架SCN=[n×n]，SCN（i，j）∈{0，1}。