基于SDF与Firefly优化的鲁棒数字水印算法

张国有，李 婧，王江帆

(太原科技大学 计算机科学与技术学院，山西 太原 030024)

1 概 述

在3D打印技术日益普及的今天，三维模型在医疗、多媒体、数学等领域得到了广泛的应用，加之目前互联网技术发达，三维产品的内容及数据信息更加容易被复制、篡改利用，因此数字产品的版权侵权问题亟需解决[1]。数字水印算法作为信息安全领域的重要研究方向，为解决三维模型版权危机问题提供了支持，三维模型数字水印技术为解决这类版权问题提供了一种有效途径。

1997年Ohbuchi等人首次提出针对三维模型数字水印的思想[2]，将数字水印技术从一二维媒体类型扩展到三维模型中来。针对三维模型开展的研究工作主要有：Zafeiriou等人提出一种基于主对象轴的盲水印算法[3]，对一般平移、旋转、均匀缩放等有较好的鲁棒性，面对剪切攻击时模型重心会改变，主对象轴就会选择出错从而导致鲁棒性变差；顶点范数作为三维模型中较为突出的特征为水印算法的研究提供很多思路，从顶点范数出发的水印算法[4-7]，对平移、旋转、顶点重排和相似变换等攻击有很强的鲁棒性，对简化和细分操作也有较强鲁棒性，但不适用于小尺寸、具有平坦区域的CAD模型，在遭受剪切攻击时会改变模型的重心，从而影响顶点范数的确定，严重影响算法实验效果；陈强等人从模型表面粗糙度展开研究[8]，引入顶点权值及其相对位置来获取顶点，且嵌入强度自适应于表面粗糙度，对平移、旋转、均匀缩放、顶点重排序及轻微剪切攻击鲁棒，但该算法在顶点个数少的模型中对粗糙度分析有偏差，影响实验效果；另一种是将模型按粗糙度值分成不同组别嵌入水印[9]，粗糙区域嵌入高强度水印，稍平滑区域嵌入低强度水印，该方法有良好的视觉掩蔽效果，不同区域分开嵌入水印，视觉失真较小、水印容量较高，对各种常见攻击甚至剪切攻击都具有鲁棒性，但遭到简化攻击时会减少顶点的数量，使得模型表面粗糙度降低，从而降低水印容量导致鲁棒性变差。2014年唐宝提出一种基于网格分割的非盲水印算法[10]，该算法先预处理再利用顶点到面片的距离进行水印嵌入，对一般剪切攻击有不错的鲁棒性，但模型在遭受严重剪切攻击时性能下降，且在顶点数目较多的模型上进行水印嵌入时算法执行效率较低；2017年Hak-Yeol等人提出针对剪切攻击的方案[11]，从模型局部形状获取参考点，以解决裁剪攻击引起的不同步问题，该方法将水印能量均匀分布到整个模型中，有助于提高水印的不可见性；次年，Han-Ul Jang等人提出一种基于一致性分割的盲水印算法[12]，以顶点范数一致性为依据、采用阶梯分析技术来确定水印方案，该方法不适用于小的模型，因为嵌入需要足够数量的顶点来有效地分割；2019年Mohamed等人提出基于小波变换的三维模型盲水印算法[13]，通过使用变换域的量化指数调制量化小波系数来嵌入水印，以网格中心和显著点之间的距离降序排列作为同步基元，对平滑、加性噪声、相似变换等攻击有较好的抵抗效果，对于严重的剪切攻击和网格重分还需要改进；2020年关素杰等人提出基于粒度计算的数字水印算法[14]，将二值图像作为水印信息嵌入到灰度图像中,对噪声和剪切攻击具有鲁棒性，该算法嵌入的水印数据不只局限于简单的二进制序列，可以更好地服务于三维模型数字水印算法。

通过对以上方法的分析，为解决严重剪切、网格简化攻击鲁棒性较差的问题，提出一种从SDF(Shape Diameter Function，形状直径函数)局部特征出发的三维网格模型水印算法：利用SDF对模型进行分区，采用改进的搜索算法[15]选择最佳嵌入顶点，以顶点局部粗糙度值为依据获得三角网格顶点最优解(即最适合嵌入水印的位置)嵌入水印，采用非盲方式完成水印提取和检测。

2 三维网格模型预处理

Shapira等人首次提出用SDF对模型进行分割[16]，模型分区操作是实现水印算法的预处理阶段。形状直径函数直观地反映模型的局部直径，使得模型分割块数是明确的，根据文献[17-18]描述，基于SDF的分割算法相较其他同类算法来说分割效果良好。

2.1 SDF分区执行过程原理

(1)在三维模型网格上任意选取顶点；

(2)以该顶点为圆锥顶点，沿顶点法向量的逆方向为中心线引出射线作圆锥体，该文取圆锥角的角度为120°并均匀选取30条射线进行实验；

(3)引出射线与模型表面网格相交，保留与相交点法向相同的射线(夹角小于90°认为方向相同)；

(4)所有射线长度加权统计，得到顶点的SDF值。

2.2 SDF值计算的具体过程

(1)计算射线平均长度、长度标准差和有效范围：

有效范围：Range=[rm-(1/2)σ,rm+(1/2)σ]

(2)给有效范围的射线定义权重，顶点的sdf值为：

(M为落在有效范围射线数量)

(3)对上述sdf值归一化，得到其所属面片的sdf值：

log(α+1)

α是归一化系数，对顶点的sdf值进行归一化处理。

3 基于SDF的三维网格模型数字水印算法

M=(V,F)表示三维模型，V代表顶点，F代表面片。在预处理阶段将模型分割成若干块，剔除面片信息过少的分块，取k个分块进行标记并嵌入水印，每个分块表示为Mα=(Vα,Fα)，α=1,2,…,k。其中Vα和Fα表示第α个分块的顶点与面片信息。

3.1 选择嵌入顶点

在对三维网格模型进行SDF分区后筛选顶点，将嵌入顶点选择看作组合优化选择问题，引入萤火虫算法完成顶点优化选择。萤火虫算法是全局优化算法，每只萤火虫都会发光吸引同类，吸引力与自身亮度成正比，亮度模糊的个体被较亮的个体吸引，并向其周围移动，使得群体迅速收敛，整体集中于较亮的位置，算法搜索能力下降且无法跳出局部最优。该文将随机挑选各分区的数个顶点，选择分区中比这些顶点粗糙度值大的顶点作为目标靠近，以此增加搜索的多样性，避免陷入局部顶点最优解和收敛过快、水印嵌入出现分布不均的情况，从而影响视觉掩蔽效果。实现过程需要设置合适的适应度函数和阈值优化选取顶点，适应度函数根据三维模型顶点所处区域粗糙度来构造，计算相邻顶点间距离来获得量化的粗糙度值。

该算法具体实现步骤如下：

(1)初始化：采用SDF分割的区域随机生成初始种群，每个种群中有n个个体，每个个体包含n个网格点，它们随机分布在有n个样本位置的网格平面上。

(2)设定萤火虫种群，个体对光亮初始吸引度为β0=1.0，其中βmax=1.0,βmin=0.2，吸引度公式为：

β(r)=(βmax-βmin)e-γr2+βmin

γ为亮度吸引系数，r为个体间距离，吸引度是筛选顶点的粗糙度值，值越大越容易“吸引”顶点。

(3)根据萤火虫位置计算出其适应度值，适应度值越优的萤火虫亮度越高，吸引度越大。

(4)萤火虫靠近比自己亮的个体的移动距离为：

其中，Xi表示比第i个更亮的萤火虫所处位置，rand()是随机扰动，用来修正较亮萤火虫的位置，α为步长因子，取值范围为[0，1]。

(5)萤火虫靠近比自身亮的个体，步长为：

α(t)=αt

其中步长随着飞行时间增加而递减。

(6)群体中最亮的萤火虫将不再更新自己的位置，通过下式逐步更新最亮个体的位置。

(7)通过增加“记忆”即给定一个标记，使得算法执行能够直接保留适应度值最高的10%的萤火虫，缩小搜索范围继续执行步骤(3)～(6)。

(8)终止测试:达到最大迭代次数后输出优质解，结束算法，否则，搜索次数加1，跳到步骤(3)进行下一次搜索。终止条件根据适应度函数值设定。

3.1.1 设计适应度函数

适应度函数设计是选择嵌入顶点的重要步骤，与所选圆锥角度120°对应，选择平整程度在30°<θ<60°区域顶点为水印嵌入位置。具体如下：

(1)求模型顶点Vi(Xi,Yi,Zi)与相邻顶点Vj(Xj,Yj,Zj)的欧几里得距离Dij，计算顶点Vi(Xi,Yi,Zi)距离之和Wi，其中i,j=1,2,3…。公式如下：

(2)求顶点局部粗糙度值，每个区域范围内顶点较少时，将范围变大确保水印的嵌入容量，顶点较多时，将范围变小以防嵌入信息过多导致模型透明性下降。选择嵌入位置即求解下式目标函数最大值的问题：

其中，θ是经验所得平滑角度，取0°≤θ≤90°。适应度函数可设置为：

其中，f(θi)表示编号为i的平滑度函数。

3.1.2 设置终止条件

模型预先进行分区操作，区域终止条件设置为：

其中，ei表示第i个区域的最佳适应度值，当Estep小于阈值δ时，当前粗分区寻优结束，继续细化分区开始新的寻优。整个算法的停止条件为：

若Estop小于设定阈值或者达到了预先指定的适应度函数值，则满足停止条件，跳出循环。

3.2 水印嵌入

根据预处理后的顶点sdf信息构造水印序列，将模型按sdf值分区，按照分区来选择嵌入水印的顶点。水印嵌入是将每个区域的顶点sdf值进行标记并筛选顶点，修改这些顶点值来嵌入水印。该算法中计算各分区顶点归一化sdf的均值，比较各顶点sdf值与均值来确定嵌入的水印信息完成嵌入，如图1所示。

图1 水印嵌入

具体执行过程如下：

(1)各区sdf值按升序排列并进行归一化操作，将sdf值转化到区间[0,1]内，执行如下：

(2)以长度L的水印序列为依据，将每个区域的sdf值集合再分为l个区间并以此构造l个集合，每一个集合作为一位水印的构造基元。

(3)统计每个集合中顶点sdf值的个数。

其中，λ为水印嵌入强度。

3.3 水印检测

水印检测：嵌入的逆过程，本算法非盲提取水印，需要原始模型参与，嵌入水印模型M'与原始模型M比对来检测水印信息相关度，执行过程如图2所示。

图2 水印提取

具体操作步骤如下：

(1)嵌入水印的模型M'按照预处理进行相同分区操作，以确保嵌入提取时模型分割一致性。

(2)分割后的模型M'做步骤2.2中的(1)～(3)操作，分为l个区间，与嵌入水印区域对应。

(4)对比待检测水印和原始水印的相似程度。

4 实验结果及分析

算法程序在Visual Studio 2013开发，C++语言实现，优化选择顶点是将matlab环境搭在VS上完成，选择的模型是Bunny、Dragon、Venus、Horse。为验证算法鲁棒性，进行仿射变换、简化与细化、剪切等各类攻击的测试。通过比较相关系数分析算法鲁棒性，相关系数越大，模型相似程度越高，算法性能越好。位错误率即对比原始水印与待检测水印。

4.1 透明性实验

该算法透明性的评估是通过肉眼观察模型差异大小、计算Hausdorff距离来进行。公式如下：

其中，M,M'是原始模型和嵌入后模型顶点集合，l(m,m')是两集合对应顶点欧几里得距离。阈值为0.000 37，H越小模型差异性越小，透明性越好。由表1看出嵌入水印模型与原始模型视觉上基本无差异，Hausdorff距离均小于阈值，算法透明性良好。

表1 嵌入水印前后透明性比较

4.2 鲁棒性实验

为验证该算法的鲁棒性，对Bunny、Dragon、Venus模型分别进行仿射变换、简化与细分、剪切等多种方式的攻击，以检验嵌入水印的模型与原始模型的相似程度。图3～图5分别为三个原始模型与模型在遭受不同类型的攻击后得到的部分效果图。

图3 Bunny原始模型与遭受不同类型攻击的模型图

图4 Dragon原始模型与遭受不同类型攻击的模型图

图5 Venus原始模型与遭受不同类型攻击的模型图

4.2.1 仿射变换攻击

对模型进行平移、旋转、均匀缩放攻击，这类攻击只改变模型位置、方向、角度，不会改变形状，SDF值不会改变，且在分区阶段做了归一化处理，即使改变模型比例也不会影响分区确定，因此原始模型在遭受仿射变换攻击后，提取的水印与原始水印相关系数值为1。结果如表2所示。

表2 仿射变换攻击实验结果

4.2.2 简化与细分攻击

将模型顶点数目分别简化30%、50%、70%，并采用Loop细分。简化率增加，模型相关系数降低，但在70%以上，位错误率在较小范围内，简化后顶点数目减少，仍能保持原有结构，连接框架未改变，分区嵌入也能确保提取水印准确性；同理，细分攻击不会改变模型形状使得提取水印相关性较高。结果如表3所示。

表3 简化与细分攻击实验结果

4.2.3 剪切攻击

对模型进行10%、30%、50%剪切攻击。采用SDF对模型分区，且在每个区域重复嵌入相同位序的水印信息，因此剪切之后只要仍有保存完整信息的模块存在，就可以完整提取水印信息。实验结果如表4所示。

表4 剪切攻击实验结果

4.2.4 姿势变化攻击

对Horse模型局部进行变形，在模型动态情况下验证该算法抵抗姿势变化的鲁棒性。SDF值是模型的局部特征，遭受姿势变化攻击时，模型只在局部的关节连接处有小的改变，大的局部形状并未受到扰动，对SDF值影响微乎其微。图6是Horse模型在运动过程中的姿势变化，表5是不同姿势变化的实验结果。

图6 Horse原始模型与不同姿势变化的模型图

表5 姿势变化攻击实验结果

5 结束语

当前所处时代有着巨大的版权保护的现实需求，该文所研究的数字水印技术有其重大意义。为提高数字产品的版权认证服务，提出一种从三维网格有效分割角度出发的数字水印算法，结合萤火虫搜索算法来优化并改进嵌入水印顶点位置，这些顶点在面对各类攻击时只会受到较小的扰动，稳定性较高，通过此方法可以提高水印算法性能。经实验验证，该算法除了可以完全抵抗普通攻击(平移、旋转、均匀缩放)，对剪切、简化与细分、姿势变化多种攻击都有不错的鲁棒性。

该算法应用萤火虫算法与SDF网格分割结合，算法在顶点筛选迭代过程中会在一定程度上增加时间复杂度，在今后研究中需要在兼顾水印算法鲁棒性与透明性的同时，减少优化过程的耗时。