沈璐 宋晓东 邓宇

(吉林建筑工程学院基础科学部，长春130118)

在计算机视觉领域中，把由两幅或多幅图像恢复空间景物的三维几何形状的问题称为三维重构.空间点的重构通常采用三角剖分的方法来重建点与点之间的关系.三角剖分是指将有限平面点集内的点，按一定的方式连接起来，成为互不交叉的三角形网.B.Delaunay于1934年由Voronoi图(简称V图)演化出的比V图更易于分析应用的Delaunay三角网.Delaunay三角网是最接近等角或等边的最优三角网.

Visual C++是Microsoft公司推出的一种的Win 32程序开发环境，它是面向对象的可视化集成编程系统.Visual C++开发的程序具有运行速度快、可移植能力强等特点，而且它还提供了丰富的位图操作函数，对图像处理提供了极大的方便［1-3］.本文在利用Visual C++的图像基本处理的基础上，结合MFC中的链表类等数据结构完成数据的Delaunay三角剖分.

1 Delaunay三角网的基本原理

Delaunay三角网的定义:它是一系列相连的但不重叠的三角形的集合，而且这些三角形的外接圆不包含这个区域内的其他任何点［4］.Delaunay三角网的外边界是一个凸多边形，它由连接Voronoi图中的凸集形成，通常称为凸壳.

Delaunay三角网络由于具有空外接圆和最小内角最大两个性质，被广泛应用于三维模型的重构中.“空外接圆”是指任何一个三角形的外接圆均不包含其他数据点［5］.“最小内角最大”即在所有可能的三角网中，Delaunay三角网中的三角形的最小内角最大.这两点保证了三角网最接近等角或等边的最优三角网，从而确保了准确的重构物体模型.而研究人员又在数学上证明了Delaunay三角网是二维平面三角网中唯一的、最优的［6］.

2 算法实现

对空间点的三角剖分方法从数据点的结构上一般可分为两种:一种是直接对三维空间点进行剖分;另一种是映射法.根据前面介绍，我们知道Delaunay三角网具有空外接圆和最小内角最大两个特点，如果直接对三维数据点剖分，虽然将点的空间位置考虑进去了，但涉及到空间三角形的平面法向量及相应外接圆的计算和球体问题，这些运算增加了算法程序的复杂度和不稳定性.所以本文中的三角剖分还是选择映射法，即将空间中的离散点向某一平面投影(本文采用的是向Z轴投影)，然后对投影得到的数据点进行二维平面上的三角剖分，再在剖分的结果上加入第三维信息(本文中即是深度信息)，最后完成空间三维点的剖分.

2.1 数据结构

为了方便对所剖分的点集和形成的三角形进行管理，本文以Visual C++为平台，利用链表和结构体数组来实现数据点三角剖分.

2.2 逐点插入算法的实现

逐点插入法的主要步骤:

步骤1:凸壳的建立.本文采用超三角形作为Delaunay三角网的初始三角形.nvert为数据点个数，取Vertex［nvert+1］，Vertex［nvert+2］，Vertex［nvert+3］3点为初始三角形的3个顶点.其与数据点中的x，y的最大值、最小值的关系如下:(当前的三角形计数ntri为1)

步骤2:插入第一个顶点.将点集内的第一点插入到凸壳中，并将第一点与凸壳的顶点相连，即将各顶点与第一个顶点连线的顶点编号分别按照逆时针顺序暂存入数组Edge［］［］中;

步骤3:生成三角网.在已有的三角网中找出所有其外接圆包含新插入点P的三角形，将这些三角形连接成一个区域，删除此区域中各个顶点在原三角网中的三角划分，形成一个新的空腔，将P点与这个空腔中的所有顶点相连，生成新的三角形.在此过程中，如果出现Edge［1］［i］=Edge［2］［k］，Edge［2］［i］=Edge［1］［k］同时相等的情况，则删除这两个重复的边;

步骤4:三角网优化.应用LOP局部优化算法，向外更新在此之前产生的三角形;

步骤5:重复步骤3和步骤4，直到所有的点遍历完成;

步骤6:删除超三角形顶点;删掉所有包含超三角形顶点的三角形.

2.3 逐点插入法实现过程中的问题

(1)本文提出了一种生成Delaunay三角网的数据结构，建立了两个结构体和结构体数组，利用一个二维数组来暂时存储空腔顶点的编号;

(2)步骤3中，在插入点P的定位过程中，改变搜索顺序，逆序和正序相结合，可降低对存储变数据的数组的赋值次数，降低数据结构的复杂度，只采用一个二维数组就可以满足要求.如图1所示，设在P点加入前，已经形成5个三角形，并依次编号为1～5;在定位P点位置时，顺次计算外接圆包含P点的三角形，譬如图1中的2号三角形的外接圆包含P点，将三角形边数据记录在Edge［］［］中，继续搜索，找出所有外接圆包含P点的三角形，搜索过程逆序进行，遍历所有的三角形，这样的搜索过程可避免Edge［］［］中数据的混乱和不断赋值;

图1 点定位

(3)凸壳的选择.由于本文主要是对插入法的搜索策略进行改进，而没有选择将分治算法和逐点插入法结合在一起的Delaunay三角网改进策略，所以本文的凸壳选取的是超三角形;

(4)根据前面介绍我们知道Delaunay三角网是唯一确定的.因此，加入点的顺序不会影响最终的网格形状.在进行步骤2之前，本文按照临近点插入的原则，将所有数据重新排序，首先按数据点的x值的大小，划分了n个区间，在每个区间中又重新把点按y值的由小到大重新排序，最后采用各区间轮流加点的办法作为逐点插入的顺序.由改进之后的数据对比可知，数据点插入顺序的改变对较少的数据量效果不是很明显，而对于密集数据点效果较好.

3 结论

本文的三角剖分是基于双目立体视觉来进行的，其用户操作界面利用Visual C++编写完成，剖分之后的三角网络则直接绘制，如图2～图3所示.

图2 用户操作界面

图3 三角剖分结果

虽然目前常用的、有效的三角剖分主要采用映射法来完成，此种方法在平面上可达到最优剖分，然而，恢复到三维空间，却未必仍是最优的剖分，还可能会出现“尖三角形”问题，影响曲面的重构质量.所以，如何既能把数据点的三维空间位置考虑进去，又不必像直接三维剖分那样处理庞大的数据量是今后发展的方向.

［1］杨淑莹.VC++图像处理程序处理(第二版)［M］.北京:清华大学出版社，2003:95-108.

［2］孙鑫，余安萍.VC++深入详解［M］.北京:电子工业出版社，2006:4-10.

［3］章毓晋.图像工程(下册.第二版)［M］.北京:清华大学出版社，2003:7-9，104-107.

［4］Lee D T，Schachter B J.Two Algorithms for Constructing a Delaunay Triangulation［J］.Computer and Information Sciences，1980，9(3):52-54.

［5］文伟，杨耀泉，于希宁.用Visual C++语言实现的Delaunay三角剖分算法［J］.华北电力大学学报，2000，27(4):54-58.

［6］高晓沨.2D-Delaunay三角网格的数据结构与遍历［J］.天津理工大学学报，2006，22(2):66-69.