cad模型局部区域分割与检索技术研究(编辑修改稿)

cad模型局部区域分割与检索技术研究(编辑修改稿)内容摘要：

lafman 等 [34]用 基于 k–means 聚类 的 体类型网格分割方法 对网格曲面进行变形操作。 他们提出的 k–means 聚类 分割过程如下： (a)计算每个 网格对之间的距离 ； (b)计算出网格单元 的 初始聚类中心 ； (c)对 所有网格单元 ， 计算它们与最近聚类中心之间的距离 ； (d)通过 使 网格单元与 其 聚类中心之间的距离 为 最小 来更新聚类中心 ； (e) 重复步骤 (a)至 (d)， 直 到 聚类中心不再发生变化为止。 类似 于Shlafman 等 [34]提出的 基于 k–means 聚类网格分割方法 ， Katz 等 [35]提出 了一种基于分层 模糊 k–means 算法 的 网格模型 分割方法。 该方法的距离函数是 重心的测地距离 权和以及网格之间 角度。 在 二叉树 分割时，网格被分割为两个细分区域和一个模糊区域。 由 最小割 算法将模糊区域切割归类到两个细分区域，两个细分区域被较深的凹面分离。 分层 模糊 k–means 算法 的优点是模型被分割为有意义的组成部分，并且深度凹面符合极小值规则；缺点是分割边界没有被凹面包围，最小切割不是总能找到最优分割边界。 三维 实体 模型 分割 工程应用中的三维模型大多是参数化的 CAD实体模型 ，主要有 CSG和 Brep两 种 表达方式。 前者通过 原始体素的布尔运算 生成 实体模型，表达方式 比较 直观，容易理解 ， 但 存在着 CSG 描述 的 不唯一 性问题。 Brep 表达 包含有模型的几何和拓扑信息 ，实体与模型之间是一一 对应 关系。 但是几何和拓扑信息 以私有的数据格式存储，在不同的 CAD 系统之间转换时 ， 存在着数据丢失的情况。 实体模型分割 是将形状复杂的物体分解为简单的体元素。 现有的体分割相关研究主要集中在加工特征识别领域 ，常用的体分解方法有凸分解 [36,37]和基于壳的分解 [38,39]。 凸分解方法递归 地将初始体模型 分解 为 凸壳 、以及 凸壳 与原来形体之间的毛 坯去除体。 体方法通常用二叉树描述初始体模型，由布尔运算的并集和差集运算来实现模型体的分解。 然而 ，由于很难定义曲面的凸壳， 凸分解方法不能应用于 具有 曲面形状 的形体分割。 此外 ，一些在初始形体中不存在的 虚构 面，在形体分解过程中被产生，这些 虚构 的面可能使初始形体的特征失真。 基于壳的分解方法将初始体模型分解为不包含凹边的最大体元素。 首先，初始体模型被分解为具有简单形状的壳元素；接着，一些壳元素被合并，以便能够找到最大体元素。 该方法中， 初始体模型分解仅由布尔并运算来完成，并且能够分割具有二次曲面的体模型。 然而，由于体分解过程中仅仅应用了布尔并运算，很难得到理想的分解结果。 另外，合并壳元素的过程中寻找最大体元素所需要的时间，与壳元素的数量存在着指数级的关系。 Shah 等 [40]使用半空划分将实体模型分割成最大凸体，由模型表面的半空间交叉实现模型的半空间划分。 然而，使用弯曲表面分割实体模型时不是总能找到半空间划分操作。 Sakurai 等 [41]将实体模型分解为一组单元体，然后将相关的单元体优化组合形成最大体单元，从而实现实体模型分割。 当面壳的数 量较多时，该方法在合并单元体时计算效率较低。 Woo 等 [42]通过递归二等分实体模型和组合二分体单元的最大体单元来改善最大体分解的扩展性。 该方法在分割过程中，有时产生大量的不合理的细小特征，并且计算时间是指数级的。 马等 [43]使用切割环收缩的方法分解实体模型，通过选择特殊的切割环决定面壳的表面划分，将实体模型分割为体单元。 上述各种方法存在的问题是在模型分解过程中，往往会强行切割模型中原本不需要分割的部分而得到不合理的分割体，同时也使分割体失去了原本的设计意图。 Dong 等 [44]通过 面延伸重构体特征 的方法来 实现 多面体模型分割。 首先，通过 特征面与其邻接面延伸求交 ， 生成新的顶点和边 ；接着，依据 新生成的顶点和边 、以及 模型中原有的顶点和边 ， 构造一个线框模型 ；最后，依据 面信息将线框模型转化为实体模型。 这里的 特征面是指模型中具有加工特征痕迹的平面。 Sandiford 等 [45]和 Sashikumar 等 [46]在 Dong 方法的 基础上 ，提出 了一种 基于面延伸和边延伸的体重构方法。 该方法能够分割 具有二次曲面的模型。 Li 等 [47]提出 的基于 面延伸和边延伸的体重构 分割 方法 ，对延伸面和 延伸边进行了 更 为细致 的分析， 进一步 推广了该 类 方法的 应用 范 围。 基于延伸面或延伸边方法的 局限性在于， 延伸面和延伸边的选择 对模型 分割结果 有 直接影响。 不合理 的延伸面或延伸边选择 ，会导致 模型无法封闭。 三维模型 整体检索 国内外研究 现状 CAD模型检索是信息检索的一个重要应用。 传统的 CAD模型手工检索分类，主要依赖于人的认知对机械零件进行分类。 成组技术是最为经典的机械零件手工分类方法。 众所周知，手工分类方法是费时和易于出现错误的，并且手工分类的方法难以在企业级对数以万计的机械零件模型进行分类。 近年来，基于内容的CAD 模型自动检索已经出现 [48]。 形状描述是实现 CAD 模 型自动检索时最为重要的任务。 形状描述符是用简洁的数学方法对三维模型的形状进行抽象描述，以实现模型的形状检索。 一般地，每一种整体形状检索方法，都有自己独特的形状描述符，用于表达 CAD 模型的整体形状相似性。 大多数模型的整体形状描述符可以分类为以下三种类型：数学描述符、基于视图的描述符和基于知识的描述符。 整体形状 数学描述符 (1) 整体特征形状描述符 基于整体特征的形状描述符是用整体几何属性的特征向量表征三维模型的整体形状。 Paquet 等 [49]首次提出用边界盒表征二维视图形状，并且使用基于弦的向量 集、基于小波变换的体积占有率等整体特征比较三维形状。 Paquet 等 [50]和Zhang 等 [51]提出的三维形状匹配方法使用矩作为三维实体的特征描述符。 Lou 等[52]提出的方法采用不变的主惯量评估三维形状的相似性。 Zhang 等 [53]通过引入表面积比率、不变矩和傅里叶变换系数，对基于整体特征的三维形状描述符进行了进一步的扩展。 Sun 等 [54]使用离散小波变换描述曲面区域的曲率和曲面边界的径向距离。 Kazhdan 等 [55]提出了一种基于反射对称性的三维模型形状描述符，它具有良好的 噪音鲁棒性 和采样分辨率。 基于 整体特征的形状描述符的一个普遍缺陷是一类特征向量仅仅表征几何属性的一个方面（如不变矩、表面积比率等）。 因此，基于单一特征向量的描述符并不能全面地反映模型的形状内容。 基于数学 变换 的 形状 描述 符将三维模型的空域信息通过数学变换方法变换为 频域信息 ，用变换系数表征模型的形状特征。 球面调和函数是典型的 数学 变换 的 形状 描述 符，它用出色的调和系数近似地表征三维形状，因而能够更为全面地表征模型的形状内容。 现有的大部分相关工作是用基于球面调和的方法评估三维模型之间的几何属性的相似性 [56,57]。 Vranic 等 [56]提出了一种 基于球面调和函数的三维形状描述符。 球面调和函数主要描述模型的整体特征向量。 首先使用球面傅里叶系数从已经正交化预处理的模型中取出特征向量，接着通过比较球面调和特征向量得到相比较模型的形状相似度。 类似地，Saupe 等 [57]同时采用矩和球面调和函数评估三维模型的几何属性相似性。 Morris等 [58]将球面调和推广到生物高分子领域，用于判定蛋白质结构是否具有可以利用的生化特性。 他们用球面调和系数表征蛋白质的 结合口袋 形状，并且用系数空间的几何距离评估结合口袋之间的相似度。 Papadakis 等 [59] 提出的 三维形状 描述符用球面调和函数表征分析模型的 缩放和轴翻转不变性 ，并且用连续的主元分析法表征分析模型的旋转不变性。 基于数学变换的形状描述 符能够对三维模型进行从粗到精 的 多分辨率 形状表征， 与其它形状描述 符 有着良好的互补效果。 但 该方法要求在 数学变换前 ，需要 对 三维 模型进行规范化 的预处理 ，计算 过程比较 复杂。 (2) 基于统计的形状描述 符 基于统计的形状描述 符 是利用统计学的思想， 通过对三维形体进行采样测量， 统计 具有一定形状辨识 能 力、并能 反映模型本质内容的 形状 特征出现频率，以 统计分布曲线 或 统计直方图来表征 三维 模型的形状。 Osada 等 [60]较早用整体形状的 概率分布 表征三维模型的形状。 概率分布 是使用几何函数 A3 和 D2 等在模型表面进行随机采样，统计几何函数数值出现的次数。 这里 A3 是测量模型表面 3 个随机点之间形成的角度， D2 是测量模型表面任意 2 个随机点之间的距离。 通过评估两个相比较模型的 概率分布 ，得到相比较模型的相似度。 Ip 等 [61]通过将 D2 函数细分为 IN、 OUT 和 MIXED 三种类型，将 初始的 形状分布 统计 方法 推广 到 CAD 模型 形状检索。 IN 是指 连接 模型上 2 个点的线段完全在实体模型 内 ； OUT 是指 连接 模型上 2 个点的线段完全在模型外；MIXED 是指 连接 模型上 2 个点的线段 穿过 模型。 由 D IN、 OUT 和 MIXED的 加权 和 来度量 相比较 CAD 模型 的 相似度。 该方法 在检索 CAD 实体模型时，具有一定的精度。 其缺点是 需要 将每条 线段与三维模型求交 ，以判定其类型。 概率分布 方法的 优 点是 几何 函数简单， 描述符生成过程中不需要 姿态调整 和 模型配准等 预处理步骤。 另一类 基于统计的形状描述 符 是形状直方图。 它 最早来源于检索二维多边形的截面编码技术，其基本思想是将模型进行三维分割，并用编码的方式对分割形成的部分进行描述。 最基本的分割技术是 Ankerst 等 [62]提出的 同心球分割 、 扇 形分割以及同心球 与 扇形相结合的空间分割方法。 模型中每个分割形成的部分，在空间 占据的比例 被 编码成一个向量 ，作为模型形状比较的对象。 同心球分割 得到的 形状直方图具有旋转不变性；扇形分割 得到 的形状直方图具有比例不变性；同心球与扇形相结合的分割方法 得到的形状直方图的形状辨识能力较强，但不具备旋转不变性和比例不变性。 Kriegel 等 [63]提出了一种基于体素化模型的形状直方图描述符。 由于该方法需要考虑 的体素驻留 哪 在一个分区 比较明确，导致 计算 的复杂度比较低。 其它类型的基于统计的描述符有基于弦的测量 [64]、标量函数分布 [65]、球映射信号 [66]和基于密度的描述符 [67]等。 总的来说， 形状直方图 表征 三维模型的形状 比较 直观 ， 但 这类方法 需要 在分割前对模型进行 姿势规范化 的 预处理 ，并且 对于 某些 形状复杂的 三维 模型，由于 它们的 形状直方图 近似于 钟形曲线，导致形状直方图 比较 相似的 两 个复杂模型 ，它们的实际 形状 可能 很不相似 ， 图 给出这样一个实例。 在 图 中，三维模型 heat_exchanger1 的 D2 形状分布直方图 与 grip 的 D2 形状分布 直方图 更为相似，而实际的模型是 heat_exchanger1与 heat_exchanger2 更为相似。 图 形状直方图 对某些 复杂模型 形状辨识能力不足的实例 [68] 基于视 图 的 整体形状 描述符 与 中的整体形状数学描述符不同， 基于视 图 的整体形状描述符 是人类使用不同的感知来评估三维模型的相似性。 基于人的感知，如果两个物体从每个视角看起来都相似，或者从三维视角观察到两个物体具有很强的相似性，我们认为这两个三维物体是相似的。 （ 1）二维视图形状描述符 近二十多年来，基于内容的图像检索技术已经成为了一个活跃的研究主题。 这些图像检索方法大多将从图像中取出的颜色、纹理或 二维 轮廓等作 为形状描述符来评估二维图像之间的相似度，其中的大部分方法能够推广应用到三维模型的形状检索。 基于二维视图的三维模型检索的理论依据是：两 个三维模型 如果是 相似的， 那么 从任意视角看它们都应该是相似的。 一些不同的二维视图描述符被用于表征模型的形状，并且被作为模型形状比较的间接比较对象。 Funkhouser 等 [69]和 Garc237。 a 等 [70]使用 模型的二维轮廓 （ silhouettes） 视 图作为图像形状描述符。 与人们常用三个二维视图表征模型的形状不同， Funkhouser 等 [69]用 从 十三 个视 角 方向 投影 获得 的 二维视图 表征模 型形状，这十三个视角方向分别对应于模型所在立方体的三个侧面、四个顶点和六条边。 Chen 等 [71]提出的扩展二维轮廓视图描述符使用光场 投影 得到的十个二维 轮廓 视图表征模型的形状。 具体方法是选择十个均匀分布的光场进行投影，每个光场由一个半球里的十二面体的二十个顶点发光，投影得到十张二维轮廓 视图。 光场描述符能够有效地过滤高频率的噪声，具有 旋转不变性。 Vranic 等 [56]用视平面与物体之间的距离 作为模型的形状描述符。 他们认为，在 正交三维模型的图像中，较暗的像素显示视平面与物体之间的距离较大。 Barton 等 [72]提 出的机械零件模型检索方法用正交投影轮廓表征三维模型的形状。 为了准确地表征 CAD 模型 的形状， Pu等 [73] 提出的 基于图样 （ drawing）的 二维视图 形状描述符，同时考虑了 二维视图。