1. 辽宁师范大学 计算机与信息技术学院 计算机系统研究所, 辽宁 大连 116029;
2. 北京邮电大学 智能通信软件与多媒体北京市重点实验室, 北京 100876;
3. 大连理工大学 机械工程学院, 辽宁 大连 116024;
4. 辽宁省先进设计与智能计算省部共建教育部重点实验室大连大学, 辽宁 大连 116622

收稿时间: 2014-01-16; 修改时间: 2014-04-08; 定稿时间: 2014-05-21

基金项目:国家自然科学基金(60873110, 61170143, 61472170); 智能通信软件与多媒体北京市重点实验室开发课题(ITSM201301)

作者简介：王璐(1989－),女,硕士生,主要研究领域为计算机图形学.
王冠(1990－),男,硕士,主要研究领域为计算机图形学.
魏小鹏(1959－),男,博士,教授,博士生导师,主要研究领域为计算机图形学.

通讯作者：孙晓鹏(1968－),男,辽宁大连人,博士,教授,CCF高级会员,主要研究领域为计算机图形学. E-mail: [email protected]

摘要 ：首先,对空间分布不均匀且无序的三维点云构造其二维主流形,并以与球面同胚的封闭曲面网格形式给出其二维主流形的二次优化逼近,以主流形网格有序均匀的结点分布表示三维点云空间分布无序且不均匀的形状特征,降低了三维形状描述的难度;然后,以基本几何变换作为快速粗对齐、以迭代最近法向点(ICNP)方法作为精准对齐,确定两个主曲面网格之间最佳刚性变换,ICNP方法在寻找最近点时考虑法向夹角,利用了更多的几何信息,实现快速精准的刚性对齐,兼顾计算精度和速度;最后,以对齐误差作为两个3D点云之间形状差异测度.实验结果表明:所提出的基于主流形二次曲面网格优化逼近的三维点云模型形状描述方法对三维点云的分辨率和噪声等干扰因素具有较高的健壮性,可以用于三维检索的形状描述.

关键词 ： 二维主流形 网格优化逼近

3D Point Cloud Shape Feature Descriptor Using 2D Principal Manifold

1. Institute of Computer System, Department of Computer and Information Technology, Liaoning Normal University, Dalian 116029, China;
2. Beijing Key Laboratory of Intelligent Telecommunications Software and Multimedia, Beijing University of Posts and Telecommunications, Beijing 100876, China;
3. School of Mechanical and Engineering, Dalian University of Technology, Dalian 116024, China;
4. Key Laboratory of Advanced Design and Intelligent Computing of Ministry of Education Dalian University, Dalian 116622, China

Abstract : This paper first construct 2D principal manifold of the 3D point cloud which is typically unoriented and unevenly distributed in space, and give the quadratic optimized approximation of principal manifold in form of watertight mesh with spherical homeomorphism. By this method, the shape description of 3D point cloud is converted into the description of 2D principal manifold evenly spread in spherical parameter field. Then, it applies translation, rotation and scaling to the quadratic optimized mesh to align the mesh polar axis, denoting this process as initial rough alignment. Finally, the ICNP (iterative closest normal point) algorithm is used to iteratively refine the rigid transformation to bring the two meshes into the best alignment with respect to the least mean square error, and the alignment error is recorded as difference distance between two 3D point clouds. The experimental results show that the proposed 3D point cloud shape description based on quadratic optimized approximation of 2Dprincipal manifold is robust to noise and resolution, and can be used as the shape descriptor for 3D retrieval.

Key words : shape feature 2D principal manifold optimized mesh approximation 3D shape retrieval 目前,多数的三维模型都是用于显示和绘制,往往只提供底层的基本几何属性和纹理外观属性,缺乏语义层的描述,导致三维模型的形状描述和检索难度要远远高于文本、图像及视频检索,三维形状的特征描述方法成为极具挑战性的难题.现有三维形状描述和检索技术可分为基于局部特征和基于全局特征两种类型:前者通过建立模型的多重局部特征,并根据特征对应关系寻找最优的匹配变换;后者将模型的内在特征压缩表示为一个特征向量或图结构,通过比较两个不同模型特征描述向量之间的相似测度来衡量两个模型之间的相似程度,常用的特征描述方法有形状分布直方图、傅里叶变换以及拓扑骨架信息等 ^[ 2 ].

本文针对三维点云模型空间分布不均匀且无序的特征,首先构造其二维主流形,并以与球同胚的封闭网格形式给出主流形的二次曲面优化逼近,将三维点云模型的形状描述问题转换为球参数域上分布均匀、沿参数方向有序的二维主流形的参数化网格形状描述问题;然后,对二维主流形的参数化曲面网格进行三维平移、旋转和缩放等基本几何变换,对齐两个曲面流形网格的极轴,作为初始粗对齐;最后,基于迭代最近法向点(iterative closest normal point,简称ICNP)方法快速比较两个曲面网格流形,实现精准对齐,并将对齐误差作为两个三维点云模型的形状相似测度.实验结果表明:基于二次主流形网格的三维点云模型形状描述方法对分辨率变化、噪声、几何变化等因素具有较高的健壮性,可以有效地描述三维模型的整体形状特征.

1 相关工作 1.1 三维形状描述及检索

三维形状检索对每个三维模型建立形状特征描述符,比较形状特征描述向量,得到模型之间的形状差异距离,以实现分类检索 ^{[ 3 , 4 ]} .现有的三维形状描述方法可以分为基于直方图、基于变换、基于二维视角以及基于图等几类 ^{[ 5 ]} .

· 基于直方图的方法通过对模型的空间分布进行统计分析实现分类.

2002年,Zahari等人 ^{[ 6 ]} 提出三维霍夫变换(3D Hough transform,简称3DHT)特征描述符,可以保持模型内在拓扑不变性,并且采用空间对齐策略以保证几何不变性,分类效果较好,但是算法复杂度比较高.2007年,Fehr等人 ^{[ 7 ]} 提出基于具有旋转不变性的球面函数提取三维形状特征,并构造形状特征直方图,然后使用支持向量机(support vector machine,简称SVM)实现模型分类.2009年,Liu等人 ^{[ 8 ]} 通过对模型进行Monte-Carlo采样统计空间分布,并构造形状特征向量,基于Minkowski norns对形状特征向量进行相似度分析,实现了三维模型检索. Akgul等人 ^{[ 9 ]} 通过核深度估计优化了直方图描述符,并使用了采样多概率深度函数描述三维形状、实现模型检索.基于直方图的特征描述虽然易于实现,但仅使用统计信息描述模型特征,容易忽略模型细节,不具有足够的识别力.

· 基于变换的方法使用信号处理技术描述三维形状特征,例如傅里叶变换、球面投影等.

2009年,Papadakis等人 ^{[ 10 ]} 使用CPCA(constrained principal component analysis)及PCA(principal component analysis)保证模型的旋转不变性,并将模型用若干球函数表示,提高描述符的识别力,其效果优于光场描述符 ^{[ 11 ]} . Tatsuma等人 ^{[ 12 ]} 提出多傅里叶光谱特征描述符,它是由4种独立的、带边缘增强的傅里叶光谱组成,可如实地捕获任意三维形状的固有特性而无需考虑模型的尺寸、方向以及初始位置,但四光谱叠加的最优权重比例未明确给出.2012年,Oliveira等人 ^{[ 13 ]} 通过构造三维模型的希尔伯特曲线,将三维形状描述降为一维的曲线形状特征描述,然后基于离散小波变换估测数对曲线进行采样,实现了对三维模型的形状描述.该方法具有低维度高精确性优点以及易于并行实现,但是对狭长以及有洞的模型健壮性不高.基于变换的特征描述符虽然对姿态变换具有一定的鲁棒性,但是获得姿态不变性的代价是丢失一些形状信息,易导致错误的检索.

· 基于二维视角的方法将三维模型视为若干二维图像的集合.

2010年,Papadakis等人 ^{[ 14 ]} 将三维模型投影到与模型主轴对齐的圆柱侧面获取三维模型的描述.与球谐函数相比,该特征描述符在欧式空间中的采样更加均匀.Shih等人 ^{[ 15 ]} 结合圆柱投影描述符和径向距离描述符,提高了检索准确性.2011年,Lee等人 ^{[ 16 ]} 结合高程值、径向距离、网格角度等3种投影特征描述符,每种投影特征都包含6个灰度图像,然后使用角度径向变换提取每个图像的特征向量,并实现了三维形状匹配.2012年,Tang等人 ^{[ 17 ]} 基于任意角度的视图特征对模型进行描述,并对视图特征进行聚类,通过样本训练确定正匹配和负匹配.该算法剔除了相机阵列设置的限制,增大了实验自由度.基于二维视角的特征描述方法虽具有较高的识别力,但是其舍弃了模型的三维信息,并且计算复杂度高.

· 基于图的方法通过建立模型的拓扑和几何特征来描述三维形状,更加直接具体.

2007年,Chaouch等人 ^{[ 18 ]} 在三维模型包围盒的6个投影平面上构造指定行列数目的深度线,通过深度线的空间姿态信息获取特征线队列,并将队列之间的海明距离作为三维模型相似度的衡量标准.2009年,Tierny等人 ^{[ 19 ]} 将每个模型提取附带几何属性的Reeb图,通过比较两个Reeb图的最大公共子图描述两个三维模型的局部形状相似性.该方法对于非刚体变换和噪声具有较高的健壮性.2011,年Shao等人 ^{[ 20 ]} 结合基于向量化轮廓的二维形状表示方法和基于采样的形状匹配策略,通过记录邻近点之间的变换,减少了采样配准的计算代价.不过,视点数量是否充分将影响最后的检索结果.2012年,Eitz等人 ^{[ 21 ]} 首先搜集了大量的骨架模型,然后基于Bag-of- Features方法构造模型的线条图,最后基于Gabor滤波器建立模型之间的变换,但是所收集到的骨架精准性难以保证.基于图的特征描述符可以描述模型的拓扑信息,但是难以获取且需要后续的图匹配操作,时间和空间复杂度较高.

1.2 主流形及应用

主流形是嵌入高维空间的非欧氏低维流形,即点集的非线性主成分和子空间的概括.1984年,Hastie ^{[ 22 ]} 将穿过数据中心的平滑曲线或曲面定义为主流形曲线或曲面,主流形上的每个点都是该点在原始点集中的局部平均.不同于其他的非线性扩展,主流形具有形式简单、自身一致性、几何解释清晰等特点.

对于 r 维随机变量 P ,其一维主流形定义如下:设 G ( l )={ G ₁ ( l ), G ₂ ( l ),…, G _r ( l )}是具有 r 个分量的向量函数,每一个分量都为参数 l 的光滑函数,将 r 维点集 P 投影到曲线 G ( l )中最近点,将投影指标记作:

l _f ( p )=max _l { l :|| p -G( l )||=inf _m || p -G( m )||}.

从而,通过参数索引确定一维流形上的最近点信息.如果对于所有的 l 均有 G ( l )= E ( P | l _f ( p )= l ),其中, E 为数学期望,则称 G ( l )为点集 P 的一维主流形,即主曲线.主曲线上的点可以视为所有投影点的平均,可以最小化重构误差: D ² ( P , G )= E (|| P - G ( & lt; span lang="EN-US" style='font-family:Symbol' xml:lang="EN-US">l _f ( P ))|| ² ),其中, D ² ( P , G )表示 P 与 G 之间的距离误差,|| P - G ( l _f ( P ))||表示 P 和 G ( l _f ( P ))之间的欧氏距离.

常用的线性降维方法PCA在处理多元正态分布的椭圆分布数据效果较好,但对一般的非线性数据结构的效果比较差,比如二次、三次或高次多项式数据;同时,线性的主成分分析受随机扰动的影响也比较大.而二次主流形作为非线性主成分分析方法,较好地回避了此类缺陷,并能够消除高维数据的统计冗余,降低了数据信息的损失.

主流形在一些领域应用比较广泛,例如分子生物学分析 ^{[ 23 ]} 、动态系统分析等.在文字检索处理方面,Sun等人 ^{[ 24 ]} 对比了3种不同主流形匹配算法在跨语言文本检索中的匹配效果,这3种方法都是将数据视为高维空间中的向量,通过主流体提取算法,将数据从不同的多重高维度空间嵌入到相同的低维度空间中,实现了不同类型的数据分类.He等人 ^{[ 25 ]} 针对图像和视频处理问题提出半监督降维方法MMP(maximum margin projection),该方法建立局部的主流形结构,对图像及视频进行降维,与待检索图像相似度高的图像在低维度空间中趋近于待检索图像,从而实现图像的检索.Chen等人 ^{[ 26 ]} 通过直方图估计和高斯混合模型估算视频队列的特征概率分布,提取概率特征分布主流形,将高维视频数据投影到低维空间,在低维空间比较映射队列实现视频的检索.在三维数字几何处理方面,Guskov ^{[ 27 ]} 首先将输入模型分裂成多个Voronoi部分、建立参数化曲面,通过优化全局平滑函数生成最后的参数域,即主曲面参数域,最后对参数域进行重采样实现模型的重新网格化.

本文首先构造三维点云模型的二次主流形,并实现二次主流形的曲面网格逼近;然后,从距离、面积、平滑性这3方面优化主流形的参数化曲面网格;最后,基于极轴实现主流形曲面网格的粗对齐、基于ICNP实现主流形曲面网格的快速精准精对齐,并将两个主流形曲面网格间的配准误差作为三维形状的相似测度,实现了三维点云模型的形状描述.

2 主流形的曲面逼近及优化 2.1 二维主流形的二次曲面网格逼近

Hastie ^{[ 22 ]} 将主流形视为 r 维空间中的参数化流体,并分别定义了一维主流形和二维主流形.1997年,Kegl ^{[ 28 ]} 采用了梯度优化算法提出了有长度约束的 K 主流形,并指出:如果数据点集存在有限的二阶矩,则其主流形一定存在.根据文献 ^{[ 4 ]} 可知,三维点云模型存在有限的二阶矩,故可以定义三维点云模型的一维主流形和二维主流形(或主曲面).

二维主流形由两个参数( l ₁ , l ₂ )控制生成,可表示为 G ( l ₁ , l ₂ )={ G ₁ ( l ₁ , l ₂ ), G ₂ ( l ₁ , l ₂ ),…, G _r ( l ₁ , l ₂ )},二维主流形上的点同样是原始投影点的局部均值,可最小化重构误差.对于三维点云模型输入的点集合 P ={ p _i , i =1,2,…, m },本文给出球形拓扑点云二维主流体的二次曲面逼近网格构建算法,描述如下 ^{[ 29 ]} :

Step 1.对其进行主成分分析PCA,得到 P 的第一、第二和第三主轴 Y ₁ , Y ₂ , Y ₃ ,以3个主轴为轴构建椭球面;

Step 2.以 Y ₃ 与椭球的两个交点为极点,以 Y ₁ , Y ₂ 形成的主椭圆为赤道,以椭球面的经度和纬度方向为参数( l ₁ , l ₂ )的方向,沿( l ₁ , l ₂ )进行均匀的20 x 20采样;

Step 3.以20 x 20的采样点为结点集合 V ,在采样点间沿参数( l ₁ , l ₂ )方向顺次连接,构造边的集合,记作 E ,从而得到封闭的二维主流形的逼近网格 M _G ,记为 M _G ={ V , E };

Step 4.将 M _G 作为初始二维主流形的二次曲面网格逼近,调整 M _G 得到优化网格逼近(见第3.2节).

2.2 逼近网格的优化

对于主流形的初始网格 M _G ={ V , E }, V ={ v _i , i =1,2,…, t }为 M _G 的结点集合, E ={ e _i , i =1,2,…, s }为 M _G 的无向边集合.设边 e _i 的一个相邻边为 e _k ,则定义结构 R _i ={ e _i , e _k },将所有结构的集合记为 R ={ R _i , i =1,2,…, r }.

对于给定三维模型,令其顶点集合 P ={ p _i , i =1,2,…, m },根据点 p _i 距离 M _G 上 t 个结点中的结点 v _i 距离最近的分类原则,将集合 P 划分为 t 个子集,记为 K ={ K _i , i =1,2,…, t },其中, K _i ={ p _j :|| p _j - v _i ||≤|| p _j - v _a ||, a =1,2,…, i - 1, i +1,…, t ; j =1, 2,…, m }.令:

其中, e _i (0), e _i (1)分别为边 e _i 的两个端点, R _i (1), R _i (2)分别为 R _i 中两个度为1的端点, R _i (0)为 R _i 中度为2的点, w _j 为点 p _j 的权重, l _i 为边 e _i 的权重, m _i 为 R _i 的权重, w _j , l _I , m _i 为常参数.令 U = U _Y + U _E + U _R ,最小化 U ,得到更新后的点集 V .迭代进行该过程,直到 U 的变化小于给定阈值,此时,图 M _G 即为三维模型顶点集合 P 的二维主流形优化逼近.这里, U _Y 控制二维主流形的宏观位置, U _E 控制二维主流形的面积, U _R 控制二维主流形的平滑性 ^{[ 29 ]} .如 图 1 所示,该二维主流形表现为封闭的二次曲面网格,可以精确地描述三维模型的整体形状特征. 3 网格对齐与形状相似测度

三维模型的形状描述及匹配的实质是将多个局部空间的三维数据统一到世界坐标系中,然后,基于几何学与统计学的算法寻找模型之间的最优变换,以最小化模型点集之间的距离.本文将该匹配过程分为基于主流形极轴的粗对齐以及基于ICNP的精准对齐等两个步骤.

3.1 主流形网格的粗对齐

粗对齐通过简单的平移、旋转和缩放等基本几何变化,简单快速地消除三维模型数据点集之间的位置和姿态差异,为后续基于ICNP的精准对齐提供好的初始条件,并降低ICNP的迭代次数、提对齐精准度.本文提出的二维主流形的逼近网格的拓扑结构为封闭的球形网格,故基于基本几何变化的粗对齐方法如下:

对于两个主流形的初始网格 M _G 和${M'_G}$:

Step 1. 分别连接它们的两个极点 p ₁ 和 p ₂ 、${p'_1}$和${p'_2}$作为它们各自的极轴,记为 L 和 L ¢ ;

Step 2. 平移主流形网格 M _G ,使其极点 p ₁ 与${M'_G}$的极点${p'_1}$对齐;

Step 3. 旋转主流形网格 M _G ,使其极轴 L 与与${M'_G}$的极轴 L ¢ 重合;

Step 4. 以 p ₁ 为缩放中心、以 L ¢ / L 为缩放系数对 M _G 缩放,使 M _G 的极点 p ₂ 与${M'_G}$的极点${p'_2}$重合.

至此,完成基于基本几何变换的主流形网格粗对齐.

3.2 基于 ICNP 的精准对齐

主成分分析(PCA)以及迭代最近点(ICP)算法 ^{[ 30 ]} 经常用以解决三维模型的旋转、平移以及缩放不变性问题: PCA仅能够实现模型的粗略对齐,ICP算法则通过反复迭代、寻找待比较模型之间的最佳变换矩阵,但模型的初始位置对ICP算法的准确性有较大影响.ICNP算法是ICP算法一种改进,同样通过反复迭代以确定模型之间最佳刚性变换 ^{[ 31 ]} .与ICP不同,ICNP在寻找最近点时考虑法向夹角,迭代过程中利用了更多的几何信息,故所得的对齐结果更加精准.具体过程如下:

对于经过粗对齐的两个主流形网格 M _G 和${M'_G}$,首先对 M _G 中的每一个结点 v _i ,在${M'_G}$中寻找与其欧式距离最小的点 ,其中, ,这里,${k_1} = \arg {\min _{j \in [1,t]}}||{v_i} - {v'_j}||$;然后,在以 为中心的邻域点集内,迭代寻找与 v _i 法向夹角最小值的点 ,其中, $ = {v'_{{k_2}}},{k_2} = \arg {\min _{j \in \Omega }}(\arccos ({\alpha _i},{\beta _j}))$, W 为相应邻域内的点在原点集${v'_i}$中的索引值集合, a _i 和 b _j 分别为点 v _i 和${v'_j}$的单位法向量,将 记作 v _i 的CNP(closest normal point).对 M _G 进行平移旋转变换以减小 和 v _i 的距离总和,即最小化目标函数:

记 d ( M _G ,${M'_G}$)= F ( R ₀ , T ₀ ),令 d ( M _G ,${M'_G}$)为两个二维主流形的二次逼近曲面的形状差异测度,显然, d ( M _G ,${M'_G}$) 越小,两个二维主流形之间形状差异就越小,对应的两个三维点云模型的形状相似度就越高.

4 实验结果与分析 4.1 实验环境

本文的实验数据来自Princeton大学的三维模型数据库,选取茶杯、桌椅、鱼、汽车等48类共1 230个模型进行了实验.实验的软件环境是主频为2.4Ghz的Intel Xeon处理器、16GB RAM以及64位Windows 7操作系统,使用Matlab以及C++编程.本文根据检索评价基准,基于距离矩阵 ^{[ 32 ]} 、Tier图 ^{[ 32 ]} 、Precision-recall曲线 ^{[ 32 ]} 、GSS S曲线 ^{[ 33 ]} 、最近邻 ^{[ 32 ]} 、First tier ^{[ 32 ]} 、second tier ^{[ 32 ]} 、E-measure ^{[ 32 ]} 、DCG ^{[ 32 ]} 等工具对实验结果进行分析.

4.2 二维主流形的二次逼近网格

部分三维点云模型的二次流形曲面逼近网格如 图 2 所示.显然:同一类模型的流形网格相似度较高,并且极轴长度也大体相近;而不同类别的模型之间,其流形网格的形状差别显著,极轴的长度和方向也存在明显差异.

为了验证本文二次主流形的曲面网格提取算法对噪声的健壮性,我们对输入点云模型上每个顶点的法向方向进行随机扰动,扰动角度区间为[0 ° ,10 ° ];同时,对每个顶点按照新的法向进行了位置扰动,扰动距离为[- d , d ], d 为最大扰动距离.按照最大扰动距离与模型最长轴比值的不同,分为3%,5%及10%等三级扰动,实验结果如 图 3 所示. 图 4 是同一个杯子模型、不同分辨率情况下的主流形网格曲面形状, 图 4 (a)~ 图 4 (d)中,三维模型的顶点集合分别为1 000,4 000,8 000,10 000等不同的大小规模; 图 4 (e)是对模型进行旋转之后的主曲面形状.

表 1 为 图 4 中模型与数据库中其他模型之间相似测度的距离矩阵.显然,本文算法对噪声干扰、细分和简化、以及旋转变换等情况具有较强的健壮性.