一种保持外观特征的模型简化方法.docx

一种保持外观特征的模型简化方法专利名称：一种保持外观特征的模型简化方法技术领域：本发明涉及计算机图形学的实时绘制技术领域，尤其涉及一种保持外观特征的 模型件简化方法Garland于1997年提出基于二次误差测度(Quadric Error Metric)的边折叠简化算法(简称QEM算法)(参见文献1)是至今为止在效果和性能的综合上达到的最佳的网 格模型简化算法，他以顶点到相关三角平面距离的平方和作为误差测度，能生成高质量 的简化模型，并且误差项是一个二次曲面方程形式，用矩阵表示非常方便，可以提前计 算，因此简化的速度是很快的QEM算法把确认为边界的边通常会赋予一个很大的误差 测度值，以避免对边界边的过早折叠从而造成形状的变形在带颜色属性的模型能够的 简化上，QEM算法采用了一个更高维的仿射子空间，误差度量依然利用原来的二次曲面 方程的形式，在计算上带来了方面，但是因为新顶点V’是原顶点ν到这个仿射子空间的 投影，它的误差度量可以被视为两项之和，一个是几何误差，一个是属性误差，但几何 误差项并不对应于它在R3空间中的投影因此，有可能ν并没有和几何上最近的点进行 比较，而是和属性上最近的点比较，这样可能会低估实际的误差，有时模型表面的细节 特征会发生变形甚至丢失。

文献 1 M.Garland and P.Heckbert, Simplification Using Quadric Error Metrics, ComputerGraphics (Proe.Siggraph 97), vol.31, ACM Press, New York, 1997，pp.209-216.发明内容针对上述存在的技术问题，本发明的目的是提供一种保持外观特征的模型件简 化方法，以使得简化剧烈的模型仍能保留较好的外观和形状特征为达到上述目的，本发明采用如下的技术方案①纹理图的预处理利用Mallat小波边缘检测算法从纹理图像提取边缘特征， 利用Mallat小波边缘检测算法进行纹理图像的边缘检测，并进行噪声去除主要随尺度增 加模极大值急剧减小的点，以得到符合条件的极大值，得到单象素级边缘；②利用边缘图与顶点的对应关系，确定顶点的边缘属性对于任意一个顶点，在纹理图上找到其对应的映射像素，从而决定其是否是边 缘点，对于边缘点，记录一个边缘标志b-flag = 1，对于每条边而言，它的权重值就是两个顶点的VllghtG)的和Ellght (vl, v2) =Vllght(Vl)+Vllght (v2)；③在纹理图上提取边纹理差异，边纹理差异越大，顶点对应的边被折叠的优先 级越低，所述边纹理差异度量的公式为背景技术1 b- flag = \ 0 b - flag = 0Edlff(ν 1, ν2) = α XD(vl，v2) XDrgb(ν 1, v2)其中D(vl，v2)是两个顶点的欧几里德距离，D_(vl，v2)是两个顶点颜色空 间的距离，α是一个系数常量，用来统一 D(vl，v2)和D_(vl，v2)的距离单位；④计算顶点曲率，曲率高处的顶点，顶点对应的边被折叠的优先级越低；其 中，求解三角网格表面的高斯曲率采用如下公式1 ( λ^(ν) = —— 2π- YjO1、VieN1(V) yN1(V)表示V点的邻域三角形集合，θ i表示邻域三角形顶角的大小，用减 去该点邻域三角形对应的角度和，再除以相应区域的面积A(V)，就刻画了该点曲面的弯 曲程度；⑤综合上述三个度量子项，得到边折叠的综合度量因子E(vl, v2) = Edlff (ν 1, ν2) + μ Ellght(vl, ν2)metric (vl, v2) = E(vl, v2)+Q (vl, v2)其中，μ是一个比例因子；⑥扫描所有的顶点，计算每条边的metric值，排序后对metric最小的边进行折叠，每次折叠后，利用步骤②、③、④、⑤重新计算新生成的变的metric值，再进行排 序、折叠，折叠的顶点的位置取边中点或两顶点专用综合度量数低的位置，这个折叠过 程迭代进行，直到满足简化的指定要求或无法再简化。

所述步骤①纹理图的预处理的步骤包括求整幅图像尺度为j的模极大值的平均值，作为阈值，若尺度为j的模极大值大 于这一阈值，则作为待选边缘点，低于此阈值则滤除掉，阈值如下求取γ W HP = ^—Y^W2jf(x,y)N x=l y=lW，H分别为图像的宽度和高度，N为整幅图像的象素总数，k为经验常数根据步骤④获得边收缩代价加权函数对于指定边E(vl，ν2)收缩的代价为 Q(vl，V2) = K(vl)C^+K(V2)Q2其中，(^ 表示vl和v2对应的Q矩阵用顶点视觉上的边缘属性取代传统几何上的边缘属性，维持模型的外观形状在 简化过程中的保持QEM算法的基础上，在R3空间中完成几何和属性误差项的计算，不采用高维仿 射子空间，避免几何和属性测度上的误差计算的偏差本发明具有以下优点和积极效果1)本发明在QEM算法的基础上，在R3空间中完成几何和属性误差项的计算， 不采用高维仿射子空间，避免了几何和属性测度上的误差2)本发明利用纹理图与顶点之间固有的对应关系，在纹理图中检测特征明显的 区域，并将之通过较高加权计算到原有的二次误差的方程中去，降低其对应顶点被折叠 的优先级用顶点视觉上的边缘属性取代传统几何上的边缘属性，可以更好的维持模型 的外观形状在简化过程中的保持。

图1是本发明提供的保持外观特征的模型件简化方法的流程图具体实施方式本发明提供的保持外观特征的模型件简化方法，在传统QEM算法的基础上，引 入图像处理的方法，根据一种新的简化算子来对几何体进行简化因为在简化之前，通 过对原始纹理图像进行边缘检测，给每条边赋以视觉效果上重要性的权值，这个成为边 折叠的一个基本依据，然后再利用这种算子时候，增加了对曲率因素的考虑，使得每次 都折叠时同时保留了视觉上重要的边和曲率变化剧烈的边，使得简化剧烈的模型仍能保 留较好的外观和形状特征下面以具体实施例结合附图对本发明作进一步说明步骤1 纹理图的预处理利用Mallat小波边缘检测算法从纹理图像提取边缘特 征利用Mallat小波边缘检测算法进行纹理图像的边缘检测，并进行噪声去除， 主要是随尺度增加模极大值急剧减小的点，以得到符合条件的极大值，得到单象素级边 缘方法是求整幅图像尺度为j的模极大值的平均值，作为阈值若尺度为j的模极大 值大于这一阈值，则作为待选边缘点，低于此阈值则滤除掉，阈值如下求取γ W HP = ^—Y^W2jf(x,y)N x=l y=lw，H分别为图像的宽度和高度N为整幅图像的象素总数k为经验常数。

原图像是f(x，y)，θ (x, y)是一个二维平滑函数，为图像在分辨率 下的水平方向和垂直方向的高频细节分量，相当于图象的水平边缘，，它实际上是图像 沿水平方向和垂直方向的二维二进小波变换，也是图像f(x，y)经一个θ(χ，y)光滑后 的梯度Kf^ ~-2J f ,_dy_这样得出来的结果是一个单象素级边缘图，它能表示原始纹理图像的边缘步骤2:利用边缘图与顶点的对应关系，确定顶点的边缘属性对于任意一个顶点，很容易在纹理图上找到其对应的映射像素，从而决定其是 否是边缘点，对于边缘点，我们记录一个边缘标志b-ikg= 1「 π 77 ,.、 J1 b~ flaS=^_7] ^(0=|θ b-flag^对于每条边而言，它的权重值就是两个顶点的VllghtG)的和即Ellght(vl，v2)= Vllght (vl)+Vllght (v2)步骤3:在纹理图上提取边纹理差异，边纹理差异越大，顶点对应的边被折叠 的优先级越低将边长也作为考虑边纹理差异的一个重要因素边长计算公式采用顶点间的欧6几里德距离，颜色距离采用上述的颜色差异值，两者之间在度量单位上并不一致，因此 我们在此基础上乘上了一个系数，以用来保持量级的相同。

最后的边纹理差异度量的公 式为Edlff(ν 1, ν2) = α XD(vl，v2) XDrgb(ν 1, v2)其中D(vl，v2)是两个顶点的欧几里德距离，D_(vl，v2)是两个顶点颜色空 间的距离，α是一个系数常量，用来统一 D(vl，v2)和 _(ν1，ν2)的距离单位我 们采用原纹理图像作为颜色空间，将RGB分别作为颜色空间的坐标轴，则每一个颜色对 应颜色空间中的一个点，2个颜色之间的差异越大，它们在颜色空间中所对应点之间的距 离也越大；反之亦然，而颜色差异最大的黑色(0，0，0)与白色055，255，255)所对应 点之间的距离也最远步骤4:计算顶点曲率，曲率高处的顶点，顶点对应的边被折叠的优先级越 低高斯曲率反映了曲面局部的弯曲程度我们求解三角网格表面的高斯曲率采用 的公式为1 ( λ^(ν) = —— 2π- YjO1、VieN1(V) yN1(V)表示V点的邻域三角形集合，θ i表示邻域三角形顶角的大小，用减 去该点邻域三角形对应的角度和，再除以相应区域的面积A(V)，就刻画了该点曲面的弯 曲程度由此可以得到如下边收缩代价加权函数对于指定边E(vl，ν2)收缩的代价为 Q(vl, v2) = K(vl) Q+K(v2) Q2, Q1 Q2表示vl和v2对应的Q矩阵(见参考文献1)。

步骤5:综合上述三个度量子项，得到边折叠的综合度量因子E (vl，v2) = Edlff (ν 1, ν2) + μ Ellght(vl, v2)metric (vl, v2) = E(vl, v2)+Q (vl, v2)其中，μ是一个比例因子步骤6:扫描所有的顶点，计算每条边的metric值，排序后对metric最小的边进行折叠，每次折叠后，利用步骤2、3、4、5重新计算新生成的变的metric值，在进行排 序，折叠，折叠的顶点的位置取边中点或两顶点专用综合度量数低的位置，这个折叠过 程迭代进行，直到满足简化的指定要求(面数)或无法再简化以上实施例仅供说明本发明之用，而非对本发明的限制，有关技术领域的技术 人员，在不脱离本发明的精神和范围的情况下，还可以作出各种变换或变型，因此所有 等同的技术方案，都落入本发明的保护范围权利要求1.一种保持外观特征的模型件简化方法，其特征在于，包括以下步骤纹理图的预处理利用Mallat小波边缘检测算法从纹理图像提取边缘特征，利用 Mallat小波边缘检测算法进行纹理图像的边缘检测，并进行噪声去除主要随尺度增加模极 大值急剧减小的点，以得到符合条件的极大值，得到单象素级边缘；.1:利用边缘图与顶点的对应关系，确定顶点的边缘属性对于任意一个顶点，在纹理图上找到其对应的映射像素，从而决定其是否是边缘 点，对于边缘点，记录一个边缘标志b_flag=l，1 b ■- flag = 1V1- . Υ ) = J hskt、J [O b - Pag=Q对于每条边而言，它的权重值就是两个顶点的的和Ei^vi v2) = Vi^(Vl) + V^(v2)；.S在纹理图上提取边纹理差异，边纹理差异越大，顶点对应的边被折叠的优先级越 低，所述边纹理差异度量的公式为Ε^ νΙν!) = α χ D (vl,v2) χ ^,(ν1,ν2)其中D是两个顶点的欧几里德距离，是两个顶点颜色空间的距离，α是一个系数常量，用来统一D Grl^g和Dt^Ciiv均的距离单位；J:计算顶点曲率，曲率高处的顶点，顶点对应的边被折叠的优先级越低；其中，求 解三角网格表面的高斯曲率采用如下公式ι (Λ^(V) = T7v 2π- Y1S, aW、_JM1W表示V点的邻域三角形集合，ft-表示邻域三角形顶角的大小，用2JT减去该点邻域三角形对应的角度和，再除以相应区域的面积A(v)，就刻画了该点曲面的弯曲程 度；1；综。