三角网格剖分范文

2024-09-20

三角网格剖分范文（精选6篇）

三角网格剖分第1篇

图像配准作为识别领域与图像处理的热门课题, 一直为国内外学者所研究。而遥感图像配准当今已经成为图像处理领域研究的一个重要分支。遥感图像的特点是数据量大, 重叠度高, 针对遥感图像的图像匹配算法必须快速而准确。一序列遥感图像经过匹配后可拼接成一幅包含图像序列信息的、大视场的、清晰完整的新图像。这种遥感图像拼接技术的关键就在于图像配准, 对于图像配准, 通常情况下对待匹配图像重叠部分的一致性求解出图像的投影变换。目前针对遥感图像的配准方法, 一般分为基于特征点的配准法, 基于变换域的配准法[1,2]以及基于灰度的配准法。

2 基于SIFT特征点的图像配准算法

传统的SIFT算法是David G.Lowe提出的基于尺度空间的图像局部特征描述算子, 它对图像的缩放、旋转及仿射变换保持尺度不变性。SIFT算法又称提取尺度不变特征点的方法。对特征点的提取, 本文采用SIFT算法[3], 在提取特征点之前, 首先构造高斯差分DOG尺度空间, 设图像的尺度空间定义为L (x, y, σ) , 可变尺度高斯函数G (x, y, σ) 和图像I (x, y) 。则可以得到:

其中G (x, y, σ) 是尺度可变高斯函数,

(x, y) 是空间坐标, σ是尺度坐标。

SIFT算法最根本的思想是用各个尺度的高斯差分核与图像I (x, y) 卷积。

其中k为常数。

在用SIFT算法提取特征点过程中, 要把每一个特征采样点与其相邻点做比较, 判断其与尺度域相邻点的大小。如图2.2所示, 中间位置的点不仅要与同一尺度周围的点比较, 还要与相邻尺度的点比较, 如图2.1中标记的点, 相邻点共有26个, 如果这个点的灰度值比周围的26个灰度值都大或者都小, 则该点就是极值点。

对于关键点, 对应领域像素的梯度方向分布特性作为其对应关键点, 找出相对应的方向, 使该点具有旋转不变的特性。特征点方向的确定要考虑周围一个窗口内所有点, 把最多点的投票方向作为主方向。对图像L (x, y) 梯度值m (x, y) 和方向θ (x, y) 对应的关系如下公式所示:

每一个关键点都包含三个信息:位置、所处尺度、方向。

3 Delaunay三角网格剖分

三角剖分 (Delaunay triangulated graph) 是代数拓扑学里最基本的研究方法。我们把一个面剖开成一块块碎片, 要求满足下面条件: (1) 每块碎片都是一个三角形; (2) 面上任何两个这样的三角形, 要么不相交, 要么恰好相交于一条公共边且不能同时交两条或两条以上的边。

Delaunay三角剖分算法相对来的说较多, 本文采用M a lab2008封装的Delaunay三角剖分算法, 构网目的是为了精简特征点, 在保证准确性的前提下, 提高程序运行效率。构网方法: (1) 将所有点存入一个点集。 (2) 利用SIFT算法提取特征点。 (3) 利用三角构网最大化最小角以及空圆特性对特征点进行三角网格剖分提出不符合构网法则的点。 (4) 将得到的n个点构成一个点集, 利用输出的n×3维矩阵构成三角网并画出。

4 基于三角剖分的配准算法

本文采用RANSAC[4] (随机抽样一致性) 方法。RANSAC方法进行重复N次采样, 找出错误匹配点最少的, 且内点数最多的组合, 并利用该组合求解出变换矩阵H, 达到图像配准功能。

算法流程如下:随机抽取m个样本, 每个样本里包含6个特征点, 抽取样本的条件是:任意3点不共线, 否则重新抽取。对选取的特征点用最小二乘法计算单适应矩阵, 选定一个阀值d, 计算图像点与匹配点之间的欧氏距离, 小于d则选为内点并记录内点数。用内点数最多的一组计算变换矩阵H。实验证明采用RANSAC提纯后的特征匹配点计算变换矩阵, 其匹配点是准确的, 变换模型也是非常精确的。

5 结束语

本文改进了一种关于遥感图像的配准方法, 在提取的SIFT特征点的基础上, 通过Delaunay三角网剖分算法提出多余的特征点得到广泛而均匀分布的特征点, 提高匹配速度与匹配精度。实验表明, 本文方法对输入图像视角, 光照变化较大情况下有较好的处理效果。

摘要：以遥感卫星图像作为研究的对象, 利用SIFT算法的旋转和尺度不变性, 提取图像的特征点并进行匹配。采用三角网格剖分进行特征点的精简, 剔除不符合构网标准的特征点, 并且保留原特征点的匹配信息。提高匹配速度和正确匹配的概率。

关键词：图像匹配,SIFT,三角剖分

参考文献

[1]Maes F, Collignon A, Vandermeulen D, etc.Multimodality imageregistration by maximization of mutual information[J].IEEETransactions on Medical Imaging, 1997, 16 (2) :187-198.

[2]黄柏圣, 许家栋.基于特征点的合成孔径雷达复图像自动配准算法[J].计算机测量与控制200917 (2) :399-401.

[3]骞森, 朱剑英.基于改进的sift特征的图像双向匹配算法[J].机械科学与术.2007, (09) :1179-1182.

圆形截面的四边形元素网格剖分第2篇

1 剖分方法

将一个圆形截面进行网格剖分,网格元素为四边形元素,如图1所示的圆形截面的剖分结果。

圆形截面具有轴对称性,以四分之一圆的剖分为例,说明如何对圆形截面进行网格剖分。

在对圆形截面的剖分中,完全在圆内的元素是正四边形元素,与圆相交的元素是不规则的元素。圆形截面剖分的难点就在于不规则元素的产生。

不失一般性,设圆心是坐标原点,过原点的水平线和垂直线分别是x轴和y轴,则可以将整个圆形截面分成四个区域,这四个区域分别对应坐标系的第Ⅰ、Ⅱ、Ⅲ和Ⅳ象限。以第Ⅰ象限的剖分为例,说明如何对圆形截面进行剖分。

1.1 创建节点

根据给定的元素的边长,创建节点。由于多数情况下半径不是元素边长的整数倍,所以需要对给定的边长进行调整,保证半径是元素边长的整数倍。调整方法是,先根据半径和给定的元素边长,计算出元素的个数,再根据半径和元素个数计算出元素的实际边长,即:

元素个数=圆的半径/给定的元素边长

实际的元素边长=半径/元素个数

计算出实际的元素边长后,就可以创建节点了。根据节点与圆的位置,可以将节点分成两类,一类是圆内的节点,另一类是圆边界上的节点,这两类节点的产生方法不同。

(1)第一类节点的产生方法如下:

上述方法产生的节点如图2中实心圆。

(2)第二类节点分两步生成。第一步是水平线与圆相交产生的节点,第二步是垂直线与圆相交的节点。

第一步产生节点的方法如下:

这一步产生的节点如图2中的空心圆。

第二步产生节点的方法如下:

这一步产生的节点如图2中的“X”。

图2中4个圆表示的是4个典型元素,在下面的叙述中将以这4个元素为例说明如何生成元素。图3是对这4个元素放大的图。

每创建一个节点,给节点一个编号,编号从1开始递增。节点的存储方法用单向链表存储,表中节点的存储顺序与节点的创建顺序相同。

图2中4个圆表示的是4个典型元素,在下面的叙述中将以这4个元素为例说明如何生成元素。图3是对这4个元素放大的图。

在图3中,实心圆表示节点,空心圆是相应元素所在正四边形被截取的顶点。

1.2 创建元素

从图2中可以看出,大多数元素是正四边形元素,少数元素有三角形元素、非正四边形元素和五边形元素。对圆形截面进行剖分的难点在于后三种元素的生成。

创建元素时,顺序从节点链表中取出每一个节点,用这个节点和相邻的节点构成元素。

对于任一个节点,是否能与其它节点构成元素,可以分成三种情况。第一种情况,也就是最简单的情况,一个节点与其它的三个节点构成一个正方形的元素,如图3(I)中的节点1,可以与节点2、3和4构成一个正方形的元素;第二种情况,一个节点可能与另外的4个节点、3个节点或2个节点构成一个非正方形的元素,如图3(III)中的节点1,可以与其它3个节点构成一个非正方形的元素;第三种情况,节点正好位于圆上,则此节点不能与其它的节点再构成新的元素,但已经与其前面的节点构成了元素。

下面介绍创建元素的方法。设当前元素节点的指针为currentNode,unitLen为元素的长度。

情况1

设节点currentNode(如图3(I)中的节点1)的右上对角点为p(currentNode->x+unitLen,currentNode->y+unitLen)(图3(I)中的节点3),如果p在圆内,则currentNode、p与另外两个相邻的节点(图3(I)中的节点2和4)构成一个正方形的元素。

在链表中,currentNode的下一节点就是欲生成元素的第2个节点(图3(I)中的节点2),此节点的指针为currentNode->next,这样,第2个节点就确定了。在节点表中查找p和另外一个节点的关键在于找到currentNode上方的节点(图3(I)中的节点4),找到了这个节点,则p就是此节点的下一个节点。在节点表中找currentNode上方节点的方法为:

node所指的节点就是currentNode节点上方的节点。节点3的指针就是node->next。

根据上面的计算,由currentNode开始组成的一个正方形元素的各个节点的指针分别为currentNode、currentN-ode->next、node和node->next。

情况2

节点currentNode的右上角点(如图3(II)、(III)和(IV)中的点4)不在圆内,则生成的元素如图3(II)、(II-I)和(IV)所示。这三种元素可以用同一个方法生成,方法如下。

设p表示点(currentNode->x+unitLen,y),如图3中(II)中的点2和(III)、(IV)中的点3。如果p在圆内,则p是元素上的一个点,并且在p和p的上方点(图3(II)中的点4)之间一定存在着元素上的另一个节点(图3(II)中的点3),在节点表中找该点。

则node就是点3(图3(II))的指针。

(1)如果p正好在圆上,则直接可以判定此点就是欲产生元素上的一个节点,设这个节点的指针为pNode1。

(2)如果p在圆外(如图3中(III)和(IV)中的点3),则在curentNode和p之间一定存在一个节点(如图3中(III)和(IV)中的点2)。在节点表中查找此节点。

则node就是点2(图3(III)和(IV))的指针,则pN-ode1应是点2的指针。

在点(currentNode->x,currentNode->y)和点(currentN-ode->x,currentNode->y+unitLne)之间一定存在元素上的一个节点,如图3(III)中的点5,在节点表中找这个节点。

则node所指向点5(图3(III))的指针,设这个指针为p Node11。

(3)如果p在圆内,则p就是欲产生元素上的一个节点,则pNode1=currentNode->next。

在点(currentNode->x+unitLen,current->y)(图3(II)中的点2)和点(currentNode->x+unitLen,currentNode->y+unitLen)(图3(II)中的点4)之间一定存在元素上的一个节点,如图3(II)中的点3,在节点表中找这个节点。

则node就是点3(图3(II))的指针,设这个指针为pN-ode12。

下面利用currentNode的上方点(图3(II)和(III)中点6、(IV)中的点5)的确定其余的节点。

(4)现设p是currentNode上方的一个点p(currentNode->x,currentNode->y+unitLen),如图3(II)和(III)中的点6、图4(IV)中的点5。

如果p在圆内,则p是元素上的一个节点,而且p之前还应有一个节点,如图3(II)和(III)中的点5,在节点表中查找此节点。

则node就是欲查找的点5(图3(II)和(III))。设node所指的节点指针为pNode2,点p对应的节点指针为pNode3。

(5)如果p正好在圆上,则p就是元素上的一个节点,此元素是一个三角形元素。设点p对应的节点指针为pN-ode2。

(6)如果p在圆外,如图3(IV)中的点5,则在currentNode和p之间应该有元素上的一个节点,如图3(IV)中的点6。在节点表中查找该节点。

则node就是所要找的节点的指针,设此节点的指针为pNode4。

至此,一个非正方形元素的各个节点已经全部找到,可以生成一个元素了。

简单对这个算法进行一下总结。如果是情况(1),则可先找到两个节点currentNode和pNode1;如果是情况(2),则可先找到三个节点currentNode、pNode1和pNode11;如果是情况(3),则可先找到三个节点currentNode、pNode1和pN-ode12。继续判断(4)、(5)和(6)。如果是情况(4),则后续节点是pNode2和pNode3;如果是情况(5),则后续节点只有pNode2;如果是情况(6),则后续节点是pNode4。(1)、(2)和(3)中的一种情况和(4)、(5)和(6)中的一种情况组合,就可以确定一个元素上的所有节点了。

情况3

这种情况下,节点已经位于圆上,其右侧和上方已经没有节点了,不能生成元素。

2 结束语

(1)算法的复杂性为O(n2)。

(2)在剖分过程中,会产生一些比较小的三角形元素,为更为精确地表示圆形截面,这些小的三角形元素要保留。在实际应用中,可以根据需要,将较小的元素与前面的元素进行合并,但需要另外的算法。

参考文献

三角网格剖分第3篇

关键词：特征点,表面重建,几何模型,三角剖分,纹理映射

0 引言

三维物体表面重建技术在工业设计、虚拟现实、远程医疗和训练模拟等诸多领域具有广泛的应用前景, 因此它是计算机视觉研究的热点问题之一。三维物体表面重建的实现可以基于物体表面特征点、直线段或二次曲线, 其中以基于特征点的三维重建算法最为常见, 例如双目立体视觉重建算法[1]、基于点的由运动恢复物体结构 (SFM) 算法[2,3]等等, 这些算法由两幅图像上的匹配点计算出物体表面特征点的三维世界坐标, 如果直接用这些离散的三维坐标表示物体, 既不直观也不真实, 所以有必要使用这些三维点重建出具有真实感的物体表面。一些文献[4,5,6]已经阐述了使用三维数据点恢复物体真实外观的算法, 但使用的数据是用三维扫描仪获得的点云, 而不是用图像匹配方式获得的物体表面三维点。

本文将结合实例, 阐述一个使用物体表面三维点集重建物体真实表面的算法, 与用三维扫描仪获得的点云重建物体真实表面相比, 本文的算法更为简单, 重建速度更快。算法的输入数据是用立体视觉算法得到的物体表面三维点, 输出结果是颇具真实感的三维物体表面, 算法主要分为两大步骤: (1) 物体表面三角网格化; (2) 纹理映射。

1 实例说明

图1是用数码相机拍摄的左右两幅网格墙面图像, 由立体视觉或SFM算法可知, 通过角点匹配、基本矩阵运算和三角法求解, 能够计算出图像上匹配角点对应的物体表面三维点坐标, 图1的两幅图像分别有86对匹配角点, 所以使用SFM算法能够得到86个墙表面三维点坐标, 本实例先使用这86个三维点, 在Matlab环境下将墙表面三角网格化, 然后在OpenGL环境下进行纹理映射。

因为墙面的重建是用86个三维特征点作为输入数据的, 所以重建出的墙面大小受到这些三维点所在拓扑空间的限制, 也就是说:没有三维点的墙面部分不可能被重建出来, 重建后的墙面就局限于86个三维特征点所限定的空间内。

2 物体表面三角网格化

这一步骤的目的是用物体表面上的三维特征点来恢复物体表面的几何拓扑结构。一个常用的方法是物体表面三角剖分, 三角剖分与拓扑重建密切相关, 一方面, 拓扑重建用到三角剖分。另一方面, 当采用三角网格表示曲面时, 拓扑重建的结果表现为曲面三角剖分。

2.1 映射剖分算法

曲面的三角剖分可以简单地分为两类: (1) 在曲面上直接对散乱三维点进行三角剖分。 (2) 以平面投影点集的三角剖分为基础的映射法。后者的实现比较简单。本文使用的曲面三角剖分法属于后者, 主要思路是:将物体表面上的散乱三维点投影到某个平面上, 把曲面三角剖分转化为平面三角剖分, 然后将平面剖分结果映射回曲面上去, 这种方法易于实现, 缺点是物体表面生成的三角网格质量受到表面形状以及投影平面选择好坏的影响。另外, 如果被映射的物体表面是非单值曲面, 则应先将物体表面划分成若干个拓扑曲面的并集, 然后对每个曲面单独使用映射法, 最后将所得的结果拼接起来。实践证明, 将若干个单值拓扑曲面的映射结果重新拼接并非易事, 但是, 若能保证物体表面映射到某一平面上是单值的, 那么就避开了拼接这一难题。在双目立体视觉和SFM算法中, 多数情况下使用两幅不同角度拍摄的物体照片来恢复物体原貌, 这就要求两幅照片的拍摄角度不能相差太大, 否则无法拍摄到物体的公共场景, 在这个前提下很容易找到一个平面, 使要恢复的物体表面到此平面的映射是单值的。

在本文实例中, 为了找到与墙面存在单映射关系的平面, 有必要先规定世界坐标系。在双目立体视觉或SFM算法中, 用两个摄像机或者用一个摄像机在两个不同位置对物体拍照, 因此存在左右两个摄像机坐标系, 理论上世界坐标系可以任意设置, 但是为了方便起见, 往往规定世界坐标系与左摄像机坐标系重合, 这样, 世界坐标系的Z轴从左边摄像机镜头光心出发, 与透镜垂直指向被拍摄物体表面, X、Y轴方向与图像平面的X、Y轴方向平行, 在本文中我们遵循这一规定。

我们把世界坐标系的XOY平面 (也就是物体的成像平面) 作为物体三维表面的映射平面, 显然这种映射关系是单值的。如图2所示。

在物体表面三角剖分之前, 先看一个抛物曲面三角剖分的例子。

u=-2:0.5:2; v=u;

[x, y]=meshgrid (u, v) ;

X=reshape (x, 1, size (u, 2) *size (u, 2) ) ;

Y=reshape (y, 1, size (u, 2) *size (u, 2) ) ;

Z=X.^2+Y.^2;

Point_3D=[X Y Z]; Point_2D=[X Y];

tri=delaunay (X, Y) ;

trisurf (tri, X, Y, Z) ;

trisurf (tri, X, Z, Y) ;

上述程序对定义在XOY平面上一块矩形区域的抛物面三角化, 使用的方法是前述的映射法, 曲面上一共有81个三维点, 存放在Point_3D中, 抛物面在XOY平面上的81个投影点保存在Point_2D中, 用Delauny函数在XOY平面上对这些投影点进行三角剖分, 剖分的结果保存在tri中, 这是一个N × 3矩阵, 每行的三个元素分别表示一个三角片的三个顶点在Point_2D中的下标索引, 81个映射点一共被剖分成N个三角片, 因为每个三角片的二维顶点都对应着抛物面上的一个三维顶点, 将tri中的剖分结果映射回抛物面上, 就得到了抛物面的三角剖分, trisurf函数将抛物面上的三角片显示出来, 就得到了图3, 图3 的右图是沿着Z轴的方向看到的抛物面形状。

假设图1中的两幅图像完成了角点匹配, 并用立体匹配或SFM算法求出了86个墙面上点的三维世界坐标, 结果存放在86×3的矩阵XYZ中, X、Y和Z的数值范围如下:

X∈[-2.1964 1.1014] Y∈[-0.7936 0.3663]

Z∈[8.2725 10.5555]

按照映射法编写的Matlab程序如下:

X=xyz (:, 1) ; Y=xyz (:, 2) ;

tri=delaunay (X, Y) ; % tri的每一行表示一个三角形的顶点在[X Y]中的下标

point1=xyz ( tri (:, 1) , 1:3 ) ; % 构成每个三角片的第1个顶点的X, Y, Z坐标

point2=xyz ( tri (:, 2) , 1:3 ) ; % 构成每个三角片的第2个顶点的X, Y, Z坐标

point3=xyz ( tri (:, 3) , 1:3 ) ; % 构成每个三角片的第3个顶点的X, Y, Z坐标

x=[ point1 (:, 1) point2 (:, 1) point3 (:, 1) ]; x=x′;

y=[ point1 (:, 2) point2 (:, 2) point3 (:, 2) ]; y=y′;

z=[ point1 (:, 3) point2 (:, 3) point3 (:, 3) ]; z=z′;

patch ( x, y, z, ‘g’, ‘EdgeColor’, ‘r’ ) ;

我们用patch函数替换了trisurf函数, patch函数将指定的三维空间三角形显示出来, 与trisurf函数相比更加灵活, patch函数还有一个很好的特点, 它返回的显示结果是空间三角形在XOY平面上的投影, 后面我们将会看到, 这一特性为消除XOY平面上多余的三角片提供了方便。代码执行结果如图4 所示。

对比图4和图1可以发现:图1中被匹配角点“包围”的部分墙面已经用三角片显示出来, 其余的区域则“丢失”了, 如果要观察三维的三角化墙面, 只需在figure画布上旋转图像即可。

2.2 删除多余三角片

由图4可以看出, 重建后的墙面多了一些原本不存在的三角片 (墙面的底部) , 下面我们将分析这些三角片产生的原因。

迄今为止, 我们一直用映射法进行物体表面的三角剖分, 先将物体表面特征点在XOY平面上的投影点集三角剖分, 然后映射到三维物体表面上, 图3中的抛物面在XOY平面上的外围投影点围成了一个矩形 (凸多边形) , 在矩形内分布着81个投影点, 如图5 (a) 所示;图4中的三维墙面在XOY平面上的外围投影点围成了一个凹多边形, 如图5 (b) 所示。

对前一种情况, Delaunay三角剖分不会生成多余的三角片;但是对后一种情况则不同, 由图5 (b) 所示, AB和CD上的任意三个投影点, 只要不在同一条线段上, 就可能形成一个三角剖分, 这个三角剖分映射回物体表面就是图4 (b) 中的多余三角片。

本文用人工交互的方法消除多余的三角形。

由映射法可知, XOY平面上的三角剖分与三维物体表面上的三角剖分一一对应, 所以, 只要将XOY平面上多余的三角形删去, 就删去了三维物体表面上的多余三角片。由前面的程序可知, tri矩阵包含了XOY平面上投影点的三角剖分, 只要将tri中多余的三角剖分去掉即可。

手动消除多余三角形的具体做法是:用鼠标点击图4中欲消除的三角形内任一点, 设点击处返回的坐标是 (m_x, m_y) , 只要能判断出 (m_x, m_y) 位于哪一个三角形内, 把这个三角形找到并在tri中去掉就可以了。

下面不加证明的给出一个判断某个点是否在一个三角形内部的算法。

设△abc在XOY平面上的坐标为 (xa, ya) , (xb, yb) , (xc, yc) ;p (xp, yp) 是XOY平面上任意一点。ap×ab表示矢量ap和ab的矢量积, 则有:

ap×ab= (xp-xa) · (yb-ya) - (yp-ya) · (xb-xa) (1)

同理可以求出矢量积bp×bc, cp×ca, …, 于是判别方法如下, 若满足:

ap×ab>0ANDbp×bc>0ANDcp×ca>0

ORap×ab<0ANDbp×bc<0ANDcp×ca<0

则p在Δabc内。

若满足:

ap×ab=0AND (bp×bc>0ANDcp×ca>0

OR bp×bc<0ANDcp×ca<0)

OR bp×bc=0AND (ap×ab>0ANDcp×ca>0

OR ap×ab<0ANDcp×ca<0)

OR cp×ca=0AND (ap×ab>0ANDbp×bc>0

OR ap×ab<0ANDbp×bc<0)

则p在Δabc轮廓上;其它情况则p在Δabc外。

根据上述算法, 我们可以去除tri中多余的三角片, 重新生成的墙面如图6所示。

2.3 完整恢复物体拓扑结构的条件

从图4和图6中可以看出:我们恢复的墙面的左右两个扇面不是互相垂直的, 而是有了一个狭长的过渡平面, 这与实际的墙面结构不符, 原因是:在使用SFM算法过程中, 需要对两幅图像进行角点检测、匹配, 由于没有在图1中的左右墙面的垂直交线上找到角点, 所以无法进行角点匹配, 也就无法重建出墙面垂直交线处的三维点, 所以重建出的三维墙面不能显示左右墙面互相垂直这一拓扑特征。这就意味着:如果在匹配图像上找到的角点数目不足以完整地反映物体拓扑结构的平面投影, 在三维重建的时候, 物体部分拓扑结构信息就丢失了。

由此可知:拓扑结构是物体自身固有的特性, 图像作为物体在成像平面上的透视映射包含了拓扑结构的二维信息, 从三维重建的角度看, 角点检测 (或其他基元的检测) 就是收集这些信息的关键步骤, 因此, 要想完整地恢复物体三维结构, 就需找到足够多的、分布合理的角点, 这是必不可少的条件。

3 纹理映射

要得到具有真实感效果的物体表面, 就要使用纹理映射技术把图像粘贴到三角化物体表面。Matlab的纹理映射函数warp只是调用了底层函数surface, 功能较弱, 无法对三维空间中的三角形纹理映射, 所以我们将前面得到的三角剖分结果tri矩阵在OpenGL中显示并贴纹理, 最终显示出真实的墙面。

OpenGL具有强大的图形显示功能和良好的平台移植能力, 已经被广泛应用于可视化技术, 纹理映射是其中的一个重要技术, 可以对任意的多边形纹理映射。关于OpenGL编程环境设置、像素格式和投影模式的选择等知识可以参考有关资料。

要对tri矩阵的每行包含的空间三角形纹理映射, 需要解决三个问题。

(1) 怎样使三角化的物体表面在OpenGL视口中可见?

(2) 怎样使用图像进行映射?

(3) 怎样确定纹理坐标?

第一个问题的解答涉及到OpenGL的投影方式和可视区域的剪裁, 本文使用的投影方式是正交投影, 这种投影方式常用于计算机辅助设计中;还要进行可视空间区域的剪裁, 从前面的程序可知:墙面上的特征点的三维坐标保存在XYZ矩阵中且有:

X∈[-2.1964 1.1014] Y∈[-0.7936 0.3663]

Z∈[8.2725 10.5555] (2)

因此, 使用glOrtho函数设置控件裁剪区域时, 裁剪的区域应包含式 (2) 表示的立方体区域。

关于第二个问题, 在立体视觉和SFM中, 总是由两幅以上图像三维重建, 因此最简单的方法就是任选一幅匹配的图像作为贴图的来源, 本例采用图1 (a) 作为贴图来源, 需要注意的是:一定要保证选择的图像是RGB或RGBA格式, 如果是灰度图像就要转化为前者, 否则纹理粘贴失败。另外, OpenGL规定只有宽和高均是2的整数次幂的图像才能成功贴到物体表面, 这就要求在读取图像到内存时, 只能取其中2m×2n大小的部分, 不仅如此, 就笔者的使用经验而言, 最好使2m=2n, 这样才能进一步保证纹理映射的成功率。

至于物体表面特征点对应的纹理坐标, 可以用物体特征点在匹配图像上的对应角点来获得。

设 (x1, y1, z1) , (x2, y2, z2) 、 (x3, y3, z3) 分别是一个空间三角形的三个顶点, (x1, y1, z1) 必定对应着左 (右) 匹配图像上一个角点, 设其像素坐标为 (u1, v1) , 令:

$u^{'}_{1} = \frac{u_{1}}{w i d t h} v^{'}_{1} = \frac{h e i g h t - v_{1}}{h e i g h t}$ (3)

得到的 (u′1, v′1) 就是 (x1, y1, z1) 的二维纹理坐标, 同理可以得到 (x2, y2, z2) 、 (x3, y3, z3) 的纹理坐标。对tri中包含的所有三角形做类似计算, 就得到了所有三角片的纹理坐标, 三维墙面在OpenGL中的显示结果如图7所示。

图7 (a) 是墙面三角片的结果, 它和Matlab环境下的patch函数的显示结果非常相似;图7 (b) 是三角化的墙面在三维空间旋转的结果;图7 (c) 是贴纹理后的墙面;图7 (d) 是贴纹理后的墙面在三维空间旋转的结果。

观察 (b) 和 (d) 发现, 三维重建后的墙面不像实际墙面那样平滑, 这是由于在计算物体表面特征点过程中存在角点匹配错误、计算误差或图像噪声, 较大的误差可能会使重建后的物体外观严重扭曲、变形。

4 其它物体表面重建实验

4.1 实验平台

以网格立方体和校园墙壁为实验对象, 实验硬件设备:数码相机, 用于获取物体的两副数码照片, 针对这两副照片使用立体匹配或SFM算法求出匹配角点对应的三维点坐标;实验软件环境:Matlab与VC++结合OpenGL;实验所需数据:基于立体匹配或SFM算法求出的三维点坐标集合。

4.2 立方体表面重建

用SFM算法获得了立方体表面上142个三维点坐标, 按本文算法先这些离散点在世界坐标系中三角化, 再将立方体的左图像粘贴到三角化物体表面, 得到了真实的立方体表面。

4.3 建筑物表面重建

用SFM算法获得校园墙面上87个三维点坐标, 用本文算法重建出墙面的真实外观。

5 结论

通过多次实验得知, 用基于立体匹配或SFM算法求出的三维点坐标集合重建具有真实感的物体表面, 必须满足以下条件:

(1) 在使用立体视觉或SFM算法计算物体表面三维点的坐标过程中, 两幅图像的角点匹配一定要尽量准确, 如果角点匹配不准确, 就会使求出的物体表面三维点的世界坐标误差很大, 进而使恢复的物体表面外观严重变形。

(2) 在使用立体视觉或SFM算法计算物体表面三维点的坐标过程中, 两幅图像上的匹配角点数量要足够多, 分布要合理, 至少能够反映出物体的几何拓扑结构。

(3) 用映射法对散乱的三维点三角剖分时, 要选择合理的投影平面, 尽量使物体表面在投影面上是单值映射以避免拼接问题;尽量使投影点围成的区域是凸多边形以避免产生多余的三角剖分。

参考文献

[1] Longuet-Higgins H.A computer Algorithm for reconstruction of a scene from two projections [J].Nature, 1981, 239:133-135.

[2] Ushizaki, Manabu.Reconstruction of the spatial motion and posture of tools from stereo image sequence [A].Proceedings of the SICE Annual Conference.Okayama-Proceedings, 2005.644-648.

[3]Hartley R I.Multi Viewpoint Geometry in Computer Vision[M].Cam-brige, UK:Cambrige University Press.2000.

[4] Jenke.P, Wang.M.Bayesian point cloud reconstruction [J].Computer Graphics Forum, 2006, 25 (3) :379-388.

[5] Yu Y, A Ferencz, J Malik.Extracting Objects from Range and Radiance Images [J].IEEE Trans, Visualization and Computer Graphics (S1077-2626) , 2001, 7 (4) :351-364.

[6] Funatomi.Takuya, Moro.Lsao.Surface reconstruction from point cloud of human body by clustering [J].Systems and Computers in Japan, 2006, 37 (11) : 44-56.

[7]Xue Yong.On the reconstruction of three-dimensional complex geolog-ical objects using Delaunay triangulation[J].Future Generation Com-puter Systems, 2004, 20 (7) :1227-1234.

三角网格剖分第4篇

三坐标测量机以其优异的智能化程度和测量精确度被广泛的应用于制造业的质量控制、产品检测和计算机辅助设计当中。在对自由曲面进行测量时,需要用到三坐标测量机的球形测头,但是测头自身也是有一定的体积的,因此测量结果实际上是与被测量曲面距离为r(测头半径)的包络面,所以,为了得到所需要的测量数据,就必须求出由测头圆心部位轨面所形成的包络面,也就是所谓的测头半径补偿。在一些对精度要求较高的测量工作中,无法忽略测头半径对测量数据所造成的影响,这样,就需要一个科学的半径补偿算法来对测头半径所产生的误差进行消除。

1 常用的半径补偿算法

1.1 二维补偿法

二维补偿法的操作方法比较简单,使用范围需也相对较广,该方法在测量时会把测量点与测头半径之间的关系转化为二维情况,现阶段比较常用的二维测量法有三点共圆法和测量方向补偿法。

1.2 三维补偿法

在对一些形状规则的表面(如二次曲面、平面等)进行测量时,二维补偿是比较精确的,而在对一些形状较为复杂的曲面(如增加器叶轮叶面)进行测量时,测点位置的曲面法向适量则往往与上述补偿方向分别位于不同的平面内,如果继续使用二维补偿势必会出现误差,所以,在这种情况下就需要采用三维补偿法来进行有关计算。

从本质上看,三维补偿法的原理就是将探头与被测曲面的法矢计算出来,而补偿方法的选择则应根据被测曲面的实际情况来决定,现阶段实际工作中常用的计算方法有以下几种:微平面法、迭代修正法、规则网格均值计算法、B样条曲面补偿法、参数曲面法、三角网格法。

1.3 三维半径补偿方法的比较

微平面法能够模拟出某一点的法向量,但是该方法对于α的距离要求较高,因此不仅效率低下,且难以实现。规则网络均值计算法是一种效率较高的补偿算法,但是它对测量点的排列要求比较严格。迭代修正法和参数曲面法的计算原理非常复杂,并且效率较低。从理论上来看,B样条曲面补偿法是最为精确的计算方法,但是使用该方法的前提条件是要重新构建曲面,由此而导致的大量偏微分计算非常耗时。三角网络法是一种高校、简便的半径补偿方法,但是在三角网格化过程的计算方面则有待进一步的完善。相对于其他方法来说,Delaunay三角剖分在技术和方法上都显得更加成熟,其特点就是在剖分过程中引入了优化原则,赋予了三角剖分更强的适应性,不仅降低了操作难度,还让测量结果变得更加准确。同时,该方法能够适用于任意多边形轮廓,应用范围极广。

2 Delaunay三角剖分

三角剖分在实际中运用的最多也是Delaunay三角剖分,它是一种特殊的三角剖分。1934年,俄国数学家Delaunay提出三角形最小内角最大的三角化准则,并证明在四点或四点以上共圆条件下的平面散乱点存在的三角化方式。

2.1 Delaunay三角剖分的定义

三角剖分是:假设V是二维实数域上的有限点集,边e是由点集中的点作为端点构成的封闭线段,E为e的集合。那么该点集V的一个三角剖分除了端点,平面图中的边不包含点集中的任何点,且没有相交边;平面图中所有的面都是三角面,且所有三角面的合集是散点集V的凸包。

三角剖分中如果点集V的一个三角剖分T只包含一条边e,其两个端点为a,b,存在一个圆经过a,b两点,圆内不含点集V中任何其他的点,称之为Delaunay三角剖分。

2.2 Delaunay三角剖分的特性

1)空圆特性:Delaunay三角网是唯一的,任意四点不能共圆。在Delaunay三角形网中任一三角形的外接圆范围内不会有其它点存在。如图1所示:

2)最大化最小角特性:在散点集可能形成的三角剖分中,Delaunay三角剖分所形成的三角形的最小角最大。从这个意义上讲,Delaunay三角网是“最接近于规则化的“的三角网。具体的说是指在两个相邻的三角形构成凸四边形的对角线,在相互交换后,六个内角的最小角不再增大。如图2所示:

此外Delaunay三角剖分剖分还具有,最接近、唯一性、最优性、区域性等显著的点。

3 对基于Delaunay三角剖分的测头半径补偿法的分析和探讨

Delaunay三角剖分能够通过CMM对已经获得的有序数据的点列进行测量,使多边形轮廓的构造变得更加简单易行,在实际工作中也更容易实现。下面就以某次测量作为实例,对该方法的计算过程进行简要介绍:

3.1 在单一多边形中的应用

第一步就是要建立数据链表。该方法对于数据的测量是有一定规律的,所得到的每一行数据都有其规律可循。我们首先取相邻的两行数据构建链表AB和链表CD。对距离‖AC‖和‖AD‖进行计算,如果‖AC‖<‖AD‖,那么就将A、C连接在一起,否则的话就连接A、D。根据图3可建立链表ABDC和ACDB。

需要注意的是,在刚开始进行链表的建立时(即选取第一、二行时)必须要首先明确链表的旋转方向,以便使生成的法矢量与补偿方向相同。我们假设数据属于内向补偿,那么整个链表就是按照顺时针的方向进行旋转,因此,我们取的是链表ABCD。去掉链表中的i+2行数据,我们就可以建立链表EF,然后对i+1行数据进行反向重构,从而建立链表CD,确保了补偿方向的一致性。

然后对新链表中D与EF的距离进行计算,将距离最小的端点连接到一起,形成链表CDFE。对有关数据进行循环取行,最终形成一个完整的链表结构。

随后,我们就要开始利用基于Delaunay三角剖分的测头半径补偿法。首先去链表结构中的第i个链表环,如果没有符合要求的链表环,则终止该程序。然后,对任意一边V1、V2,遍历全部的节点Vj。由于符合要求的三角形可能存在很多歌,因此本次研究主要根据以下四条原则对其进行判断:1)三角形共存原则,即节点Vj与V1、V2不共线。2)三角形独立原则,即线段V1V2、V1Vj与任何一个多边形的轮廓都不相交。3)可见原则,就是指有向线段V1V2与节点Vj所构成的三角形,必须与链表自身的旋转方向一致。4)最大内角最小原则,即在全部符合要求的节点中,应选择能使∠V1VjV2的值最大的节点。上述原则的应用能够有效保证三角形的匀称度。

在将节点Vj确定下来后,根据其与线段V1V2的关系形成新的三角形与多边形轮廓。在这一过程中,主要应注意以下问题:1)如果节点Vj与V1和V2均不相邻,那么就将节点V2用Vj代替,并在链表中插入有向线段VjV2;2)如果Vj是有向线段V1V2的后一节点,那么就要用Vj替代V2,并将有向线段V2Vj删除;3)如果Vj是有向线段V1V2的前一节点,那么就要用Vj替代V1,并将有向线段V1Vj删除;4)如果Vj与V1、V2都相连,那么应在链表中同时删除这三条边。前面所述四种情况详如图4所示。

之后,把所生成的三角形放入相应的链表中,如果链表非空,则重新进行遍历;如果为空,则输出全部的三角形,并将i加1后去链表结构中的第i个链表环。执行结果详见如图5所示。

3.2 对于任意点补偿矢量的计算

链表和三角形的旋转方向以及法向矢量都是相同的,如果以补偿矢量相反的视角去看图3中的P点,就是图6的样子,具体算法如下。

对于补偿矢量的计算从本质上看是一个加权平均的过程,本文采用下面的计算公式:

公式中的n所代表的是有多少个三角形围绕点P。

3.3 对于边界点补偿矢量的计算

对于边界点来说,由于围绕点p的三角形并不完整,因此继续采用公式(1)的话势必会带来误差过大的问题,针对此种情况,可以采用增加点数的方式来完成边界点补偿矢量的计算。由三角形分析结果可知,将会出现3中P1和P2两种情况,具体情况如图7所示。

符号的标注方法应该按照下面的方式进行:P点的前后分别为点O和点Q,根据PQ、OP所构成三角形对应的点S、R增设点S′、R′,这样一来,就可以形成3个三角形。不过,要注意确保所形成的3个三角形的旋转方向与剖分后的三角形旋转方向的一致性。

根据上述内容,点S′、R′就要满足下列条件:

在上面的公式中,θab所表示的是ab边所对应的两个三角形的平面法矢所形成的夹角,则代表着ab边的总长,在求出R′、S′之后,就可以通过(1)来对点P处的补偿法矢进行计算了。

3.4 半径补偿的实现

在计算出补偿矢量np之后,就可以对有关数据点进行求值。设测头的半径为r,那么半径补偿公式就可以写成下面的形式:

4 实例分析

按照前面所讲述的内容,我们首先对需要测量的曲面中的有序点进行Delaunay三角剖分,结果如图8所示(实线部分)。然后,利用公式(3)对经过半径补偿的点的Delaunay三角剖分和点云进行计算(虚线部分),通过对比我们可以发现,在补偿前后,点云所构成的两个曲面实际上就是两个等距面,其距离就是我们所要求的三坐标测量机球形测头的半径。

5 结束语

本文通过对基于Delaunay三角剖分的半径补偿法的研究,对这一方法在半径补偿中的良好效果进行了分析和说明,证明该方法能够有效改善三角网格的质量,提高了边界点法向矢量的估算精度以及边界点半径补偿的准确性,具有非常好的应用前景。

参考文献

[1]李海生.Delaunay三角剖分理论及可视化应用研究[M].哈尔滨:哈尔滨工业大学出版社,2010.

[2]杨钦.限定Delaunay三角网格剖分技术[M].北京:电子工业出版社,2005.

[3]孙科,田怀文.三坐标测量机测头半径补偿实用算法[J].机械,2009,36(2):6-8.

三角网格剖分第5篇

随着航天技术的发展,人类在外太空的探索不断扩展,深空背景下的目标数目呈日益增加的趋势,单个成像跟踪平台难以有效的完成对多个目标的检测跟踪,针对这一状况多成像器条件下的协同目标检测与跟踪成为图像处理领域的热点,在民用与军事上都具有重要意义。而其中多成像器间的协同目标交接即多成像器条件下的目标对应是多成像器多目标跟踪研究中的重点与难点。文献[1]通过计算不同成像平面中目标区域的混合高斯模型(Gaussian Mixture Model)来完成目标在不同成像平面的对应,文献[2]使用目标的纹理信息作为特征完成目标对应。但是由于深空目标距离成像器较远,在成像平面上表现为点目标,基本没有形状信息,机器视觉中基于目标图像形状及灰度特征的对应方法难以适用,因此需要研究新的多成像器目标对应算法。当成像平面上存在多个点目标,且目标形成一定的几何分布,可以利用目标间构成的几何分布在不同成像平面下的投影不变性来完成多成像器目标对应。

多个成像器间的姿态变化将导致目标间所构成的几何组合在不同成像平面上产生较大形变,致使基于几何相似性的目标对应算法失效。随着微电子技术的发展,IMU等姿态测量设备的测量精度日益提高。Mirisola在文献[3]中使用惯导信息对图像进行旋转补偿来进行目标轨迹估计。Bleser在文献[4]中探讨了通过图像和惯导数据融合来完成增强现实(Augmented Reality)技术中的目标跟踪。一般深空背景下的目标检测、跟踪系统中,成像器是固定在带有姿态测量设备的运动平台上的,因此通过平台间姿态测量数据的交互,可以得到多个成像器的空间姿态分布关系。通过姿态信息的融合将有助于解决由于几何组合形变导致目标对应失效的问题。

本文针对深空背景下红外目标本身形状及灰度特征区分不显著的现状,提出了利用多个目标的几何组合来完成目标在不同成像器平面对应的算法。该算法基于Delaunay三角剖分对二维平面点集划分具有唯一性的特点,通过剖分后的三角形相似搜索来完成目标的对应。

1 目标点集的Delaunay三角剖分

深空背景下的红外小目标检测技术一直是红外图像信息处理中的重要问题,针对这一问题国内外学者进行了深入研究并提出了多种解决方案,文献[5]采用动态规划方法进行红外小目标检测跟踪,文献[6-7]采用粒子滤波来完成目标检测跟踪。按照目前较为认可的分类可将目标检测算法划分为“先检测后跟踪(DBT:Detect-Before-Track)”和“先跟踪后检测(TBD:Track-Before-Detect)”两大类,其主要依据是目标检测过程是否明确对单帧图像进行阈值分割[8]。本文主要探讨多个成像器间目标检测结果之间的对应关系,对具体的目标检测算法不做详细探讨。各个成像器采用相应的目标检测算法后,得到一系列的目标点集。由于深空背景下红外目标的形状及灰度特征不显著,因此难以直接基于目标的这些特征来完成多个成像器间目标点集的对应。同时目标点集中多个目标点的几何组合,在不同的成像平面保持一定的不变性,可以用来完成成像器间的目标对应。而三角形的几何相似在算法上较易实现,因此下面来考虑目标点集的三角剖分。

如何把一个散点集合剖分成不均匀的三角形网格,这就是散点集的三角剖分问题,三角剖分是代数拓扑学里最基本的研究方法。以目标点集坐标向量形成的平面为例,把平面剖开成一块块碎片,要求满足两个条件:

1)每块碎片都是三角形;

2)平面上任何两个这样的三角形,要么不相交,要么恰好相交于一条公共边(不能同时交两条或两条以上的边)。

由拓扑学知识可以知道,对于任何平面都存在三角剖分。

尽管有多种方法实现点集的三角剖分,但是俄国数学家Delaunay在1934年证明:必定存在且仅存在一种剖分(一般称之为Delaunay三角剖分)算法,使得所有三角形的最小内角之和最大。因此,Delaunay三角剖分能够尽可能地避免病态三角形的出现。且具有如下性质:

1)空外接圆性质:由点集所形成的Delaunay三角剖分中,每一个三角形的外接圆均不包含该点集中的其它任意点;

2)最大最小角性质:在Delaunay三角剖分中,三角形的最小角是相对于其它有可能的三角剖分的角最大;

3)唯一性:对于一个点集,其二维Delaunay三角剖分是当且仅有一个的;

4)区域性:新增、删除、移动某一个顶点时只会影响临近的三角形。

目前主要的Delaunay三角剖分的算法有:分治法、逐点插入法、三角网生长法等[9]。

经过Delaunay三角剖分后,目标点集被划分为一系列不相交的三角形集合。由初等几何知识可知当三角形的三个对应点的内角相等时,两个三角形相似。因此定义两个三角形ΔABC和ΔA′B′C′相似度测度函数为式(1),其中α是由ΔABC的三个角从大到小顺序排列组成的向量,β是由ΔA′B′C′的三个角从大到小顺序排列组成的向量。

以两个成像器为例,假设两个成像器检测得到的目标点集经过Delaunay三角剖分后,分别得到M和N个三角形。按式(1)计算三角形相似度测度后得到一个M×N的矩阵,矩阵元素记为MNij(0≤i

2 几何组合形变及补偿

当各个成像器之间存在较大的位置平移或姿态转动,使三维空间中多个目标形成的几何组合在不同视角下的成像平面中的投影具有较大的变形,导致基于角度的三角形相似度测度函数失效,因此需要考察成像器位置平移或姿态转动对三角形角度形变的影响。

2.1 坐标定义

为了后续讨论的方便,首先说明在成像系统中存在的图像坐标系,成像器坐标系以及世界坐标系之间的关系。

在成像器像平面上建立的以光轴与成像平面交点1O为原点,以图形边界为X,Y轴的坐标系,称为图像坐标系,记为O1XY。以成像器光心O为原点,x轴与y轴分别于图像坐标系X轴与Y轴平行,z轴为摄像机光轴,组成的直角坐标系称为成像器坐标系,记为Oxyz,OO1为成像器焦距记为f。由于固定成像器的运动平台运行于环境中的任意位置,在环境中选择一个基准坐标系来描述成像器的位置,并用它来描述环境中任何物体的位置,该坐标系称为世界坐标系[10],记为OwXwYwZw。世界坐标系与成像器坐标系之间的关系可以用旋转矩阵R和平移向量t来描述。图1描述了三个坐标系的相互关系,式(2)使用旋转矩阵和平移向量描述了空间中某一点P在世界坐标系下坐标X=(Xw,Yw,Zw1,)T与在成像器坐标系下坐标x=(x,y,z)1,T之间的数学关系。

2.2 空间目标点几何组合在不同视角成像平面的关系

由针孔成像模型可得到成像器坐标系中一目标点P(X,Y,Z)与图像平面中像点p(x,y)的关系为

基于式(2)和式(3)即可探讨三维空间中目标点形成的几何组合在不同视角成像平面中所成像的关系。为了易于讨论以两个成像器CAM1与CAM2为例,且不失一般性假设世界坐标系与CAM1的成像器坐标系重合并保持静止,设世界坐标系中存在由三个目标P1(0,0,10 000),P2(300,400,10 020),P3(-500,200,10 050)构成的三角形,因世界坐标系与CAM1成像器坐标系重合,且目标位置保持不变,因此三个目标形成的三角形在CMA1成像平面中保持不变。以三角形对应点角度为考察对象,研究随着CAM2在世界坐标系中的位置及姿态变化,目标点形成的三角形在CAM2成像平面上所成像对应点角度的变化关系。

图2和图3分别描述了CAM2在世界坐标系中平移和姿态变化时其所成像对应点的角度变化情况,图2中X轴为相机平移距离(单位:m),Y轴为相应的角度变形(单位:°);图3中X轴为相机旋转角度(单位:°),Y轴为相应的角度变形(单位:°)。从中可以得出如下结论:

1)CAM2沿X、Y、Z轴平移,在-5 000～5 000 m范围平移,随着远离坐标原点,角度偏差逐渐增大。

2)CAM2沿X、Y、Z轴旋转,在-60°～60°范围转动,随着偏离0°,角度偏差逐渐增大。

3)姿态转动较平移对角度变形具有更大的影响,当姿态转动超过20°后,所成像点形成的三角形具有较大的角度偏差,会引起基于三角形相似性测度函数的三角形相似判定方法失效。

因此如果能够针对CAM2的平移和姿态转动进行补偿计算将会使基于三角形相似性测度函数的相似判别更加准确。从式(2)和式(3)可以得出,为了完成平移补偿,需要得到目标相对于成像器的距离信息,而在纯角度跟踪系统中距离信息是比较难以获取的。姿态补偿则只需要CAM2成像器相对于世界坐标系的姿态转动信息,该信息可以由成像器所在的运动平台的姿态测量设备来提供。因此引入如图4所示虚拟成像平面VCAM2的概念来进行姿态补偿,VCAM2坐标定义如图4虚线表示,其成像平面与CAM1成像平面平行,VCAM2的旋转角度可由成像器所在运动平台的姿态测量设备获取。同样基于式(2)和式(3)可将在CAM2成像平面上所成像经过坐标变换重新投影到VCAM2成像平面上。图5描述了VCAM2平面上像点与CAM1中像点对应角度的偏差,可以发现经过补偿后可以弥补成像点三角形的角度偏差。

3 基于Delaunay三角剖分的多成像器多目标对应算法

根据以上讨论可以得到如图6所示以两个成像器为例的基于Delaunay三角剖分的多成像器多目标对应算法,该算法流程一共分为五步,分别为

1)各成像器独自进行多目标检测,得到目标点集;2)根据成像器所在平台的姿态测量设备获取的姿态信息,进行姿态补偿;3)对姿态补偿后的目标点集进行Delaunay三角剖分;4)计算三角形相似度测度函数得到相似度矩阵;5)根据相似度矩阵得到相似三角形,完成多成像器多目标对应信息输出。

4 仿真结果与分析

以两个成像器为例进行仿真,完成对算法性能考核。仿真场景设置如图7所示,具体参数设置为

1)以CAM1成像器坐标系为世界坐标系;

2)在距离CAM1成像器10 km处,分布着由10个目标组成的目标群,目标位置测量存在均值为零,高斯噪声影响,随机分布在半径1 km范围内;CAM1与CAM2均可完全检测到10个目标。

3)对目标群进行观测时,CAM1与CAM2均对准目标群中心。并且假设CAM1在整个观测过程中位置保持不变。CAM2通过在Y轴和Z轴方向的平移以及X轴方向的姿态转动来调整观测视场。

按式(4)定义目标对应成功率sP来考察算法目标对应性能。N为仿真次数,Ne为错误匹配点数,NT为正确匹配点数

采用蒙特卡洛仿真方法,每种场景仿真10 000次,验证算法性能。共仿真三种场景:

1)CAM2分布沿Y轴,Z轴平动;2)CAM2沿X轴姿态转动;3)CAM2保持与目标群距离不变,视场中心对准目标群中心,通过Y、Z平移与及X轴姿态转动观测目标群。

图8,图9及图10分别为三种场景下的仿真结果,图8中X轴为相机平移距离(单位:m),Y轴为目标对应成功比例;图9及图10中X轴为相机旋转角度(单位:°),Y轴为目标对应成功比例。图8表明随着CAM2沿Y轴平移距离增大,目标对应性能下降,但当平移距离达5 km时,目标对应成功率仍在82%以上;当沿Z轴平移时,对应成功率也随距离增大而下降。图9表明随着角度姿态偏移加大,目标对应性能下降,当最大偏移达到60°时目标对应成功率下降到85%;经过姿态补偿后,目标对应成功率保持在100%左右。因此当经过姿态补偿后,目标对应的误配将主要由成像器的平移引起。图10表明了在同时存在成像器平移和姿态转动情况下的目标对应成功率,引入姿态补偿后在各个转动角度,目标对应成功率均得到了提升。

结束语

针对深空背景下目标在成像平面呈小目标分布,目标本身没有更多信息可供利用,同时多个目标间形成的几何组合在多个成像器平面存在一定不变性的特性,本文提出了基于Delaunay三角剖分的多成像器目标对应算法。通过两个成像器条件下的仿真结果表明,提出的算法可以完成深空背景下红外小目标在多个成像平面的目标对应。该算法对如何完成深空背景下多个小目标在多成像器平面的对应提供了一种新的解决思路。

本文只是初步探讨了利用目标间的几何组合完成目标在多成像器平面对应的算法。由于目标成像尺寸、对比度、信噪比及目标个数等条件的影响,将导致多个成像器的目标检测结果存在误检、漏检情况。如何在多个成像器的检测性能存在差异的情况下提高目标对应算法的稳健性,以及如何充分利用目标点组合的几何特征,以提高三角形匹配的有效性等问题是下一步研究中要进一步深入的课题。

摘要：针对深空背景下,目标距离成像器较远,目标在多个成像器平面呈弱小目标,目标点之间的形状及灰度特征没有明显区别的现状,提出了基于目标点之间形成的几何组合来完成目标点在不同成像平面对应的算法。该算法首先对各个成像器目标检测后获取的目标点集根据成像器间的姿态信息进行旋转补偿,然后对补偿后的目标点集进行Delaunay三角剖分,最后根据剖分后三角形的相似性测度来完成多个成像器平面的目标对应。对算法在各个场景下的目标对应性能进行了仿真与分析。

关键词：多成像器,多目标,目标对应,三角剖分

参考文献

[1]Hyun-Uk Chae,Kang-Hyun Jo.Appearance feature based human correspondence under non-overlapping views[C]//Proceedings of the5th international conference,Ulsan,South Korea,Sep2009.Berlin:Springer,2009:635-644.

[2]LIU Qiang-qiang,LUO Xi-ling,ZHANG Jun.A New Method of Correspondence for Multiple Cameras Based on Texture Energy[C]//2009Second International Conference on Machine Vision,Dubai,United Arab Emirates,December28-30,2009:264-269.

[3]Mirisola L G B,Dias J,Almeida A T de.Trajectory recovery and3d mapping from rotation-compensated imagery for an airship[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems,San Diego,CA,Oct29-Nov2,2007:1908-1913.

[4]Bleser G,Wohlleber C,Becker M,et al.Fast and stable tracking for AR fusing video and inertial sensor data[C]//Short Papers Proceedings.Plzen:University of West Bohemia,2006:109-115.

[5]张兵,卢焕章.动态规划算法在运动点目标检测中的应用研究[J].电子与信息学报,2004,26(12):1895-1900.ZHANG Bin,LU Huan-zhang.Dynamic programming algorithm for detecting moving point targets[J].Journal of Electronics&Information Technology,2004,26(12):1895-1900.

[6]Boers Y,Driessen H.A particle filter based detection scheme[J].IEEE SP Letter(S070-9908),2003,10(10):300-302.

[7]陈东,林建粦,马德宝.粒子滤波在空间光电小目标跟踪中的应用[J].光电工程,2011,38(3):1-8.CHEN Dong,LIN Jian-lin,MA De-bao.Application of Particle Filter on the Tracking of Dim Photoelectrical Target in Space[J].Opto-Electronic Engineering,2011,38(3):1-8.

[8]杨磊.复杂背景条件下的红外小目标检测与跟踪算法研究[D].上海:上海交通大学,2006.YANG Lei.Study on infrared small target detection and tracking algorithm under complex background[D].Shanghai:Shanghai JiaoTong University,2006.

[9]Tsai V J D.Delaunay triangulations in TIN creation:an overview and a linear-time algorithm[J].Int.J.of.GIS(S365-8816),1993,7(6):510-524.

三角网格剖分第6篇

在应用计算机辅助设计技术进行水轮机的选型设计、经济运行和过渡过程数字仿真等工作时,常采用大量离散数据点表示水轮机特性曲线。而水轮机特性曲线数据是由转轮模型试验获得的,这些特性曲线均是一系列大量的离散数据点,即以单位流量Q11和单位转速n11作为坐标系的一系列等值平面曲线数据点[1]。实质上是用二维的图形表述三维的信息,表达不直观。本文针对不规则离散的水轮机特性数据,利用MATLAB强大的数据处理功能[2],通过三次样条插值和Delaunay三角剖分求取水轮机特性曲线。

1水轮机特性离散数据采集

水轮机流量特性为Q11=f(α,n11)(α为水轮机导叶开度),实际上是水轮机模型综合特性在三维坐标系(Q11,n11,α)中的三维曲面投影到(n11,Q11)平面上的一系列等高线。在MATLAB程序中,首先要为X、Y、Z三个变量进行赋值,再把在Excel表格中处理好的数据列复制、粘贴到MATLAB的变量值表中,这样能够把大量的列项量数值快速地复制给MATLAB中的变量。为了表示各采样点的地理位置,需要绘制采样点的分布图,如图1所示。

2数据插值和等值线的绘制[3]

水轮机特性采样点多,呈不规则分布,其生成的等值线或等值面(如图2所示)需要进行数据插值和数据网格化。常用的插值算法有线性插值、最近邻插值、三次多项式插值和样条插值4种。其中线性插值和最近邻插值结果所构成的曲面不平滑,精度较低;三次多项式插值结果所构成的曲面较平滑;样条插值结果所构成的曲面最平滑,精度高。

在任意插值计算区间[a,b]的每一个子区间[xk,xk+1]上,三次样条函数为:

undefined。 (1)

其中:x为水轮机的单位转速;hk为相邻水轮机单位转速的差值,记为hk=xk+1-xk;mk为三次样条插值函数的二阶导数;Ak、Bk为积分常数,undefined。y为水轮机的单位流量;mk可通过下面方程组解出:

undefined

。 (2)

其中:undefined;λk=2mk-1+mk。

三次样条插值的计算步骤如下:首先确定端点条件,然后构成相应的方程式组(2),求出mk(k=1,2,3,…,n),最后根据式(1)求得各子区间[xk,xk+1]上的三次样条插值函数。

3插值三维网格曲面绘制和Delaunay三角网

通过MATLAB可以实现三维网格曲面图形的绘制[4]。插值数据生成的三维网格见图3,生成的三维表面图见图4。

不规则三角网可减少规则格网方法带来的数据冗余,同时计算效率也较高。如何把一个散点集合剖分成不均匀的三角形网格,这就是散点集的三角剖分问题。不规则三角网模型是根据区域有限个点集将区域划分为相连的三角面网格,区域中任意点落在三角面的顶点、边上或三角形内。在实际中,运用最多的三角剖分是Delaunay三角剖分[5]。

要满足Delaunay三角剖分必须符合两个重要的准则:一是最大-最小化角特性,即在散点集可能形成的三角剖分中,Delaunay三角剖分所形成的三角形最小角最大;二是空圆特性,即Delaunay三角网是唯一的(任意4点不能共圆),在Delaunay三角网中,任一三角形的外接圆范围内不会有其他点存在。

生成的三维三角网格图见图5,生成的三维三角网曲面图见图6。

4结果比较分析

通过计算,对三维曲面中的开度值α与原图的等开度值α作比较,处理结果见图7。

在图7中取误差最大的一条等开度线(α=20 mm)作误差分析,其数据见表1。通过比较可知,最大绝对误差不超过0.2 mm。由此可见,本文提出的求取水轮机特性曲线中随机插值点的方法是可行的,能满足工程的实际要求。

5结论

本文针对不规则离散的水轮机特性,利用MATLAB强大的数据处理功能,通过三次样条插值和Delaunay三角剖分确保了其计算精度和唯一性,对水轮机的正确选型和优化设计是有利的。

摘要：针对不规则的离散水轮机特性数据,提出一种求取水轮机特性曲线的随机插值点方法。即利用MAT-LAB对离散数据进行采样,然后应用Delaunay算法对采样的数据进行三角剖分,并通过三次样条函数插值,保证其计算精度。通过某水电站的HLPO140-LJ-485的数据验证,该方法可行有效。

关键词：水轮机特性,MATLAB,Delaunay三角剖分,三次样条函数插值

参考文献

[1]张昌期.水轮机-原理与数学模型[M].武汉:华中工学院出版社,1988.

[2]蔡旭辉,刘卫国,蔡立燕.MATLAB基础与应用教程[M].北京:人民邮电出版社,2009.