首页 > 编程资源分享区 > C/C++源代码共享 > 对Open CV 中的平面划分相关函数使用探索
2007
11-24

对Open CV 中的平面划分相关函数使用探索

对Open CV 中的平面划分相关函数使用探索

作者:龚勋


下载源代码

摘要 :Delaunay三角剖分在工程应用中非常有用,开源库OpenCV也提供了相应的函数,但是由于原始文档不是很详细,在使用过程中仍然会遇到很多麻烦,笔者就自己的理解进行了相关的总结,并解决了实际应用中的相关问题。


关键字:open cv, delaunay, 平面划分


任意点集的三角网格化(triangulation)问题一直是人们密切关注的问题。三角网格化问题在许多领域有广泛应用。Delaunay 三角剖分是目前研究应用最广的一种剖分方法,因其具备很多优点,以下简单列举两条:


空外接圆性质:在由点集V-生成的D-三角网中,每个三角形的外接圆均不包含该点集的其他任意点。
最大最小角度性质:在由点集V-生成的D-三角网中,所有三角形中的最小角度是最大的。
Open CV中有Delaunay的实现,极大地方便了广大科研工作者。尽管Open CV提供了详细的文档,并且提供了相关sample,但是由于对原文档及参考书籍[1,3,4]的理解上的不足,笔者在使用过程中仍然遇到很多问题,下面将自己的一些理解及探索进行总结,谬误之处望大家批评指正。请注意,这里并不会详细介绍Open CV如何进行delaunay划分,请参考Open CV自带的示例程序delaunay.c.


1. 也说“四方边缘(Quad-edge)”结构


图1 边e以及与边e相关的边(该图来自Open CV文档)


这个结构图非常难懂(对我而言),但是非常关键,是Open CV 平面划分的最基本元素,数据结构如下:

/* quad-edge structure fields */
#define CV_QUADEDGE2D_FIELDS() \
int flags; \
struct CvSubdiv2DPoint* pt[4]; \
CvSubdiv2DEdge next[4];

typedef struct CvQuadEdge2D
{
CV_QUADEDGE2D_FIELDS()
}
CvQuadEdge2D;


这个结构的关键数据是数组next[4],其按顺序存放四条边(代码):e,eRot以及它们的反向边。注:我这里用“边代码”,原因是Open CV是用long型的代码来表示平面划分的一条边。



  • eLnext: e的左方区域(或上方区域)是一个多边形,e是其中一条边,eLnext是指向这个区域的另一条边,这个描述有点类似于数据结构中的十字链表的表示法,与e是连接在一起的;

  • eRnext: 理解同eLnext,只不过是指向e的右方区域(或下方区域)的另一条边,与e是连接在一起的;

  • eDnext: 与e共“目的点”的另一条边;

  • eOnext: 与e共“出发点”的另一条边;

  • eRot: e的对偶边,这就没什么好解释的了。
    在了解这些知识点后,我们可以获得如下的应用:

2. 应用1-在Delaunay划分结束后获取三角形连接关系

(1) 首先,以边e开始循环查找与其相连的两条边就可以找到一个三角形,对所有边进行相同操作,就可以找到许多三角形,注意,这其中有许多重复的边,需要进行判断。主要代码如下:

for( i = 0; i < total; i++ ) // total是边数目,可以参考Open CV示例程序delaunay.c
{
CvQuadEdge2D* edge = (CvQuadEdge2D*)(reader.ptr);

if( CV_IS_SET_ELEM( edge ))
{
CvSubdiv2DEdge e = (CvSubdiv2DEdge)edge;
CvSubdiv2DEdge t = e;
CvPoint buf[3];
int iPointNum = 3;

for(int j = 0; j < iPointNum; j++ ){
CvSubdiv2DPoint* pt = cvSubdiv2DEdgeOrg( t );
if( !pt ) break;
buf[j] = cvPoint( cvRound(pt->pt.x), cvRound(pt->pt.y));
t = cvSubdiv2DGetEdge( t, CV_NEXT_AROUND_LEFT );
}
if (j == iPointNum) {

AddTriangle(buf); // 添加三角形
}

CV_NEXT_SEQ_ELEM( elem_size, reader );
}

(2) 其次,因为在Delaunay划分中,所有边是有方向的,光通过e进行轮循可能会遗失部分三角形,因此同时还得以e的反向边进行轮循,上面的代码可以改为如下:
Bool FindTriangleFromEdge(CvSubdiv2DEdge e)
{
CvSubdiv2DEdge t = e;
CvPoint buf[3];
CvPoint *pBuf = buf;
int iPointNum = 3;

for(int j = 0; j < iPointNum; j++ ){
CvSubdiv2DPoint* pt = cvSubdiv2DEdgeOrg( t );
if( !pt ) break;
buf[j] = cvPoint( cvRound(pt->pt.x), cvRound(pt->pt.y));
t = cvSubdiv2DGetEdge( t, CV_NEXT_AROUND_LEFT );
}
if (j == iPointNum) {

AddTriangle(buf); // 添加三角形
return true;
}

return false;
}

// 调用代码如下

for( i = 0; i < total; i++ )
{
CvQuadEdge2D* edge = (CvQuadEdge2D*)(reader.ptr);

if( CV_IS_SET_ELEM( edge ))
{
CvSubdiv2DEdge e = (CvSubdiv2DEdge)edge;
FindTriangleFromEdge(e);

CvSubdiv2DEdge e1 = (CvSubdiv2DEdge)edge+2; //即next[2]

FindTriangleFromEdge(e1);
}
CV_NEXT_SEQ_ELEM( elem_size, reader );
}

在上面的代码中,是直接采用数组位移法进行各种边的对应的(即edge+2),不过Open CV已经有了自己的实现函数:cvSubdiv2DRotateEdge,上面用红色粗体标注的语句可以换为:
CvSubdiv2DEdge e1 = cvSubdiv2DRotateEdge((CvSubdiv2DEdge)edge,2);
对于16个点的输入,Delaunay分割的结果如图2所示。




3. 应用2-在Vonoroi划分结束后获取多边形

参考Delaunay.c中的函数:void paint_voronoi( CvSubdiv2D* subdiv, IplImage* img );结果如图3所示。


有了应用1的分析,理解这段代码也很容易。









图2. 16个点的Delaunay三角剖分结果 图3. 相应的Voronoi划分结果



注:读者要编译附带源程序,请安装Open CV库1.0正式版(最好安装在默认目录,否则需要修改工程配置路径)。


参考文献


1.刘瑞祯,于仕琪. Open CV教程. 北京航空航天大学出版社. 2007年6月
2.高晓沨,黄懿.2D-Delaunay 三角网格的数据结构与遍历.
3.Open CV 安装文档
4.Open CV 中文网站. http://www.opencv.org.cn/


留下一个回复