三维实体网格自适应划分加密算法

高质量的网格划分是三维建模研究的关键。根据对三维形体的几何特征和物理特征进行分析，给出三维网格划分的加密规则。三维实体网格自适应划分加密算法是通过研究网格加密区域和网格节点算法，设计基于Delaunay剖分的动态节点单元一体化三维网格自适应生成算法。

一、自适应网格加密规则

基于特征的网格划分首先须要考虑几何特征对网格的影响，几何特征区域上网格划分形式取决于特征的重要度。一个特征的重要度可以从特征的几何形状、几何参数大小、属性和约束等多方面进行评价。外加载荷的力学特性分析是研究形体工作状态的情况。这两种情况下，受力情况和几何情况完全不同，也决定了这两种模式下网格划分情况的不同。因此在网格划分的过程中要两者相互考虑、相互结合才能得到形体比较精确的三维划分。

1、基于几何特性和物理特性的加密规则

为了能够有效实现局部网格加密及加密区域的过程控制，可以对三维体的几何特性和物理特性来确定加密规则。 三维体的几何特性主要包括形状、大小和厚度等。在进行网格划分时，为了有效描述几何形体，应从几何特征出发，进行网格局部加密，其加密规则如下。

(1)特征尺寸相对总体剖分尺寸比值较小的区域为加密区域，如图1a所示。

(2)为有效描述曲面形状，将曲率变化大的区域确定为加密区域，如图1b所示。

(3)相交平面的夹角区域为加密区域，如图1c中A所示。

三维体的物理特性主要从物体的力学、温度等方面考虑。在实际应用中，零件的外形或者突出的部位在受力作用下，会引起局部应力数值急剧增加，这一力学特性往往对零件造成严重损坏。因此在进行仿真分析时为了有效描述应力集中区域、获得应力分布和数值，必须对应力集中区域进行网格的加密划分。

从物理特性出发定义网格加密规则如下。

(1)若有外形突变，则突变区域为网格加密区域，如图2a所示。

(2)若有折角变化，则折角区域为网格加密区域，如图1c中B所示。

(3)集中受力区域附近为加密区域。

(4)不同材质相接处为加密区域。

(5)温度或受力集中区域为加密区域。

2、网格加密区域范围的确定

加密区域的范围由加密区域的长度L确定，L为加密目标轴线或中心点至非加密域某点M的距离，如图2a所示。加密区域的大小与应力集中程度、几何外部特征及加密区域外的单元长度有关。 对应于几何外部特征的加密区域长度为：

Lj=(2- _α）（2-β/180）（0.5+1.5PLe) _ _(1)

对应于应力集中引发的加密区域长度为：

Ly=(1+3φ)Le _ _ (2)

加密区域长度：

L=_max_ (Lj,Ly) _ _ (3)

其中φ为应力集中度0≤φ≤1；α为特征参数比，0≤α≤1；β为界面夹角0°≤β≤180°，ρ为曲面曲率max(ρ，1/3Le)≤ρ≤min(ρ，1/3Le）。

3、加密区域节点算法

网格划分时由应力集中点的高密度向非集中区疏密度有个平缓过渡，为了能够有效描述物理特征变化、应力变化，须要实现网格的密度变化，即网格化分节点的数量及间距。

设线段AB长度为L0，加密区域最小单元边长为Le，非加密域最大单元边长为le，为实现单元边长从Lo到le平缓过渡在线段AB上插入N个节点，使得任意两个相邻边边长之比为k，即:

整理得到

所以,当已知l、L0时，任意给定比例系数k，根据上面方程式可求得在AB段内所插入的节点个数N，进而求得AB段内从密到疏的一组节点组。设第i个点距A点的距离为Li`，则

当k=1时，所插入的节点等分线段AB,各单元边长相等。

当k≥时，相邻单元尺寸相差较大,疏密单过渡不平缓。

当1<k<2时,这里取=1.618，即任意一个插入节点是其相邻两节点的黄金分点，这样可得到单元平缓过渡的效果。

因此,当给定一般单元长度时，根据式(3)得到加密区域长度；当给定最小单元长度及比例系数k时，根据式(5)可得插入的节点数N。

二、自适应三角网格自动生成

基于给出的几何特征规则和物理特征规则可以确定研究对象的加密区域、区域布点等前期处理，可以对三维体进行三角形网格自动生成，算法步骤如下。

1、对三维实体的各边单元尺寸Le进行离散，生成各棱边的节点，对三维体进行Delaunay三角化，形成初始Delaunay三角形单元，设某一三角单元边长为L1i，L2i，L3i，根据式(7)将初始三角形单元划分为“可生成新节点的三角形单元T”和“非可生成新节点三角形F”。

式中α为控制系数，取值0.8-1。

2、假设T三角形总数为X，从中选择新节点Nn的最佳节点生成边B，满足式(8)

式中Lji为第i个三角形第j条边。

设最佳节点生成边B在xy平面内两端点坐标为（x1,y1)，（x2,y2)，则新节点Nn的位置为

将以上坐标变换至三维空间，便形成了一新的节点，对新节点Delaunay三角化，又形成新的Delaunay三角单元，采用上述方法循环交替，便可实现对三维实体每一个平面进行剖分。平面上生成的节点即为三维实体平面边界的节点集。

3、对边界节点集进行Delaunay四面体剖分，经过拓扑和几何不相容性检验，生成初始四面体单元。平面内△ABC是其中生成三角形平面之一。 新节点产生示意图如图所示。

三、三维实体网格自适应划分加密算法的实验验证

将本研究算法应用在板材模型的分析中，通过以上研究确定加密区域和加密方式，上图为原始划分图，下图为经过算法三维网格划分图。

对比所划分图像可以看出基于传统加密算法的原始划分图网格分布均匀，但是没有表现出网格几何特征和物理特征的分布，不能直观对模型力学集中区域进行分析。经过算法划分的网格图形不但有效地描述了原几何形体的形态，而且有效描述了物理集中区域的网格疏密分布，按照加密规则对物体几何形状特殊和物理受力等部位着重进行加密，能够真实反映三维体的特征分布，为对模型进行详细分析能够提供更为详细的资料。

对三维实体的几何特征和物理特征进行分析给出网格加密规则和方法。设计基于Delaunay剖分的动态节点单元一体化三维网格自适应生成算法及最优节点的选取。通过对机械零件的网格划分及特征区域加密，使网格疏密分布均匀，能准确有效地描述出三维体的几何和物理特征分布，便于对三维体的构造和受力等其它方面做进一步深入研究。

三维混沌加密算法之压缩算法

为保证数字图像的安全性，提出了一种压缩图像的三维混沌加密算法。该算法是通过对已压缩的数据流进行加密而实现的。首先采用基于小波的Contourlet变换的类等级树集合分割(SPIHT)编码算法对明文图像进行压缩，得到压缩数据流，然后将压缩数据流映射为一个三维位矩阵，利用Lorenz混沌映射产生混沌序列，并对其进行预处理得到比特值序列，根据比特值序列对上述三维位矩阵进行置乱和替代操作；将置乱和替代后的位矩阵重新映射为数据流，并对其进行解码和反变换操作，得到加密后的压缩图像。

一、图像压缩算法

基于WBCT的压缩编码算法

为得到压缩后的数据流，采用压缩编码算法对明文图像进行压缩。由于提出的加密算法是将由0，1组成的数据流映射为三维位矩阵，并对该矩阵进行置乱和替代操作而实现加密的。因此所选择的压缩算法对源图像进行压缩编码后必须能产生由O，1组成的编码流，而SPIHT编码算法能够满足这一要求。并且，利用该压缩编码算法对源图像进行压缩，可得到较高的峰值信噪比(PSNR)，同时具有计算复杂度低、位速率容易控制等优点，因此选择SPIHT编码算法对源图像进行压缩处理。另外，之所以选择在WBCT域对图像进行压缩编码，是因为Contourlet变换是一种基于图像的几何性变换，能有效地表示轮廓和纹理丰富的图像，它弥补了小波变换在这方面的不足。由于拉普拉斯金字塔(Llaplacian pyramid，LP)分解存在数据冗余问题，不利于图像压缩编码，因此R．Eslami等于2004年提出了一种基于WBCT的类SPIHT编码算法。

下面简要介绍该编码算法。

WBCT的基本思想是用小波变换的Mallat塔式分解代替Contourlet变换中的LP分解，然后用方向滤波器组( dirctional filterband，DFB)分别对Mallat分解中的非LL子带进行卷积处理，原理如图1所示。图1中共进行了3次Mallat小波分解，第一次小波分解的高频(LH，HL和HH)子带方向分解数（层方向数）为4，共16×3个方向子带，第二、三次小波分解的层方向数都为3，共8×3×2个方向子带，LL子带层方向数为O（不分解）。

由于WBCT各个方向子带的排列是横向和纵向分开，因此基于WBCT的类SPIHT编码算法的相邻两级方向子带系数对应关系如图2所示。为了更高效地进行SPIHT编码，按照图3所示调整子带之间数据放置结构，原先的方向子带排列如左图，阴影部分为纵向子带，同样标称的子带为同一个上一级小波子带的对应高频子带分解，将它们的排列重新安排为右图所示。

2、压缩数据流的预处理

假设明文图像的数据矩阵为A,利用上述压缩算法对其进行编码，得到由O,l组成的压缩数据流L，长度为l。为方便对压缩数据流进行置乱和替代操作，需要对其进行预处理，将L映射为一个三维位矩阵B。令N；fc~7)，其中f(x)表示对z向下取整。如果N=~7，则三维位矩阵口的维数为NXN×N，否则其维数为N×N×(N+1)。若l<N×NX(N+1)，则矩阵B的元素通过补零填充。假设压缩数据流的长度L=71，则由其映射得到的三维数据矩阵B如图4所示。矩阵B的维数是4×4×5，图中的元素为数据流L中元素的序号。

三、图像加密算法

提出的加密算法是通过预处理后的混沌序列对位矩阵B进行置乱和替代操作实现的，并选择Lorenz混沌映射产生所需的混沌序列。

1、混沌序列的预处理

Lorenz混沌映射的动力学方程如下：

当a= 10，6—8/3，c> 24.74时，系统进入混沌状态。对Lorenz混沌映射模型进行迭代，得到的实数值混沌序列为{xk，k一1，2，…，夕），{yk，k=1，2，…，p）和{zk，k=1，2，…，户），迭代精度取为双精度。

以{z．，k=l，2，…，户）为例来说明将实数值混沌序列改写为比特序列的方法。首先将混沌序列改写为16 bit的位序列：

式中bj (xl)是lxil第歹位整数。所得到的序列为{以（砑），p一1，2，…，16；i-1，2，…，p}。然后将bj（k）改写为比特值序列{6，(z)x，k=1，2，…，16×p}:

式中r(x，y)表示z除以y后的余数。同理，可以得到由{弘，k=1，2，…，p），{2t，k=1,2，…，p）改写的比特值序列{67（kn，k=1，2，…，16×p），f67(2)上，k=1，2,--．，1 6×p）。对这3个比特值序列进行处理：

式中①表示进行异或操作，可以得到另外3个比特值序列{6’（z，∽^，忌=1，2，…，16×p），{67（z．z）．，p；1,2，”．，16×p）{67(y,Z)^,k-l,2，．“，1 6×p），它们将被用于加密在上节得到的三维位矩阵。

2、加密算法设计

所提出的加密算法的密钥设计为key:[c，z。，yo，zo，Ni，N2，Na，M，sub-key]，其中参数c为Lorenz混沌映射的参数，xo，y。，zo为Lorenz混沌映射的初始值，Ni tN2，N3，M为正整数，M∈[O，1000]，sub-key是由正整数组成的字符串。提出的加密过程如下：

1)将由压缩编码算法得到的三维位矩阵B看作是由J轴上的N个二维矩阵{Bj，i-l，2，…，N}组成，Bi的维数是(N+1)×N，如图5所示；

2)令n=[1000+N×N×(N+1)]，以a，6，c为参数，z。，yo，z。为初始值，对Lorenz映射模型迭代夕次可得到3个实数值混沌序列{Xl，k-l，2，…，p}，{yt，惫一1，2，…，p}和{戤，k一1，2，…，夕），迭代精度为双精度；

3)令ni i=(M+N/16)+l’n2 -挖一M，取上述实数值混沌序列的一部分{弧，k一刀，，ni+l．…，T2），{x，y- ni，ni+l,--，行2}和{zt，n=ni，ni+l，…，nz）。按照上节的混沌序列的预处理方法将其转换成比特值序列(67(z，3，)^，k-1，2，…，N}，{6’(z，Z)I，k-l,2，…，N）和{6,(y,Z)上，k-l,2，…，N}.

4)根据比特值序列{6’（z，∞。，k=l，2，…，N）实现对{Bi，i=l，2，…，N）的列元素的置乱和替代操作，算法如下：假设当前操作的二维矩阵为bi，若67(z，y)I为0，则:

否则：

5)为使密钥值与明文相关，利用子密钥Ni更新M的值：首先令N1'=r(Ni，N+1)，取ni(i>1)平面上的第N7．行的第1～8个比特值，将其转换成一个字节，若其值为m，将M+m赋值于M。

6)重复步骤3）～5），直到I轴上的所有二维矩阵都进行了相同操作，完成一次I轴上二维矩阵的置乱和替代操作；

7)将三维位矩阵B看作是由J轴上的N个二维矩阵(Bj，j=l，2，…，N}组成，Bj的维数是(N+1)×N，或者是K轴上的(N+1)个二维矩阵{k，k -1，2，…，N+1)组成n的维数是(N+1)×N。J轴和K轴上二维矩阵的置乱和替代操作与I轴类似，不同的是步骤4)和5）。在步骤4），Bj是利用b'(x，z)上实现置乱和替代的，风则是利用6，(y，z)．实现的；在步骤5），J轴上的二维矩阵是利用子密钥Nz更新M的值，而K轴利用子密钥N3更新M的值。

子密钥sub-key表示循环置乱和替代操作的次数。假设sub-key:12345，则表示首先对J轴上二维矩阵进行1次置乱和替代操作，然后对j轴上二维矩阵进行2次置乱和替代操作，对K轴上二维矩阵进行3次置乱和替代操作，再对J轴上二维矩阵进行4次置乱和替代操作，对J轴上二维矩阵进行5次置乱和替代操作。

四、仿真结果

1、比特值序列的随机性检验

为了检验由实数值混沌序列所产生的比特值序列的随机性，对三组比特值序列进行了频数检验、序偶检验、扑克检验和游程检验。其中频数检验就是用来测试密钥序列中和的个数是否大致相同；序偶检验用于检验一段序列中相邻比特组成的序偶的分布特性}扑克检验是用来测试各种不同排列方式出现的次数是否均匀；游程检验又被称为脚检验，是一种非参数检验法，用来检验序列中是否存在自相关。

检验结果如表1所示。

由表1可知，所产生的比特值序列通过了随机性检验，具有较好的随机性能。利用该比特值序列对位矩阵进行置乱和替代操作，能够保证加密算法的安全性。

2、加密性能分析

为了测试所提出的加密算法，针对256 pixel×256 pixel的Lenna灰度图像进行加、解密仿真实验。图6为源图像，密钥为key: [28. 35，0.11，0. 21，0.32，30，42，61，20，12345]，图7为加密后的重建图像，图8为正确解密的重建图像口其中压缩图像的压缩比率为8. 76,重建图像相对于源图像的峰值信噪比(PSNR)为30.48 dB。

抵抗穷举攻击的有效方法是要求密码系统有足够大的密钥空间并且具有非常大的密钥敏感度，抵抗已知明文攻击的有效方法是令加密算法的密钥和明文相关。将所提出的加密方法和两种典型的图像加密算法在密钥空间、密钥是否与明文相关两个方面进行比较，结果如表2所示。由该表可以看出，所提出的加密方案的密钥空间只和密钥长度有关。理论上，在计算速度允许的前提下，子密钥sub-key的长度没有限制，因此该加密算法的密钥空间可以无限大，保证了加密的安全性。加密算法的密钥和明文有关，从而能有效抵抗已知明文攻击。

为了测试密钥的敏感度，令key1：[28. 35，0. 11,0.21,0.32, 31, 42, 61, 20, 12345], keY2:[28. 351,0.11,0.21,0.32, 30, 42, 61, 20’12345],keYi，key2与key仅有微小差别，利用keyi，key2对图7进行解密，解密图像如图9所示。由图9可知，keYi，keYz均不能正确解密图像，即使解密密钥与正确的解密密钥仅有微小差别。由此看出，提出的加密算法对密钥非常敏感。

为了测试所提出加密算法的加密速度，针对不同大小的源图像，利用相同的加密和解密密钥进行加密以及解密实验，所用的时间如表3所示，表中的时间包括对图像进行编码和解码的时间。测试平台的硬件配置为：计算机的CPU主频为1.8 GHz，内存2 GB;使用的编程软件是VC6.O。

本文为收集整理，文章部分观点不代表本站观点，如有侵权或其它问题请反馈客服。https://www.wgj7.com/cjwt/16251.html