一种三维工程图可逆水印算法

李 黎,赵 涵,方晓君

(杭州电子科技大学图形图像研究所,浙江杭州310018)

0 引 言

目前围绕CAD模型本身的相关研究很少,而且大多也只停留在多边形网格模型上。3D网格数字水印研究进展[1]一文中对变换域方面的研究作了很好的总结。2004年提出了基于球面参数化的三维网格模型水印算法[2、3]。这些三维网格模型水印算法原始数据不可恢复。本算法借鉴图像可逆水印算法[4],利用差值扩大法通过对Solidworks三维工程图的适当预处理来提高载体数据的冗余空间,然后将水印信息和标志位分别嵌入顶点小数部分的不同位置,实现了水印的盲提取,原始工程图数据能够完全恢复。

1 差值扩大法简介

差值扩大法是用于二维图像的可逆水印算法[5]。其基本思想可以归结为:针对原始载体两个数据点x1和x2(原始数据均为整数),首先用一组可逆变换来分别计算二者的差值d和整数均值m,即:

这组变换是可逆的,其逆变换为:

在一定误差范围内,通过将d值扩大为原来的2i倍(即左移i位),即可为待隐藏的数据提供i比特的冗余空间。将带有隐藏数据的差值记为d′结合原先的整数均值m,含水印数据可以通过逆变换式2得到。

2 Solidworks三维工程图的可逆水印算法

2.1 提高Solidworks三维工程图冗余信息

具体通过以下两个方法对Solidworks三维工程图数据增加冗余空间。

(1)Solidworks三维工程图中顶点坐标默认保留小数点后8位有效数字,将小数部分扩展为8个顶点。以某顶点x坐标为例(x=18.233 959 95),扩展为8个顶点(x1=2,x2=3,x3=3,x4=9,x5=5,x6=9,x7=9,x8=5)。水印嵌入后将上述8个顶点按顺序还原成一个顶点(18.233 959 95)。考虑到工程图的透明性,顶点整数部分未被用于水印嵌入,其值在水印嵌入前后保持不变。在Solidworks三维工程图草图中增加顶点。

(2)在工程图草图原有线段或曲线上添加一条样条曲线,使新的样条曲线与原有线段或曲线重合,然后将原有线段或曲线上的几何关系,转移到新添加的多顶点样条曲线上,最后删除原有线段或曲线。绘制新线段或曲线时可以增加适当顶点来提高信息冗余量。

2.2 选取适用于水印嵌入的顶点

排除Solidworks三维工程图中心线、基准面上顶点,及顶点小数部分第5、6或第7、8位连续两位值为9的点,按照x、y轴坐标从大到小的顺序依次选取草图中顶点。假设符合上述条件的顶点为{v1,v2,v3,v4,…}。以横坐标为例,任意一个xi可扩展为8位}将扩展后的顶点分别组合为顶点对。其中)}用于水印嵌入,}用于对应标志位嵌入。

2.3 确定水印对应的标志位

2.4 水印嵌入算法

差值扩大算法用于Solidworks三维工程图具有两个主要的优点:第一,当d值本身较小时,水印嵌入引入的误差也较小;第二,由逆变换可知,每个差值上引入的误差(d′-d)将由两个数据点x1和x2共同承担,因此每个数据点所承受的误差比较均匀。水印嵌入过程具体分为以下几个步骤。

(1)通过2.2节的方法选取顶点,{v1,v2,v3,v4,…}为符合要求的顶点。

(2)增加Solidworks三维工程图草图中的顶点。

(3)在草图中去除这些顶点的几何、拓扑关系(固定、重合、垂直等)。

(4)以横坐标为例,假设flag=1的数目为S。flag=1对应的{)}中的顶点对使用差值扩大技术嵌入水印Wi。方法如下所示:和mi通过式2进行逆变换,即可得到含水印的横坐标数据。纵坐标嵌入水印方法完全相同。

原始差值末位不再另外保存。顶点原始数据小数部分前4位可完全恢复,后4位不能恢复。

2.5 水印提取算法及数据恢复

水印的提取是水印嵌入的逆过程,本文算法中,由于水印信息和对应的标志位信息采用不同的嵌入方法,在水印的提取过程中先提取标志位信息,再提取水印信息。具体步骤如下:

再结合整数均值mi,即可通过式2完全恢复原始Solidworks三维工程图顶点原始数据。fi=0顶点数据无需变化。纵坐标水印提取、恢复方法与模坐标完全相同。

3 实验结果

为验证本文算法的有效性,选择hydraulic图来测试水印的可逆性。可用顶点数为176个(11×8×2)。为增加信息冗余量,本文在每两个顶点之间增加一个点顶点。可用顶点数为304个(19×8×2)。水印嵌入前后草图如图1所示,水印嵌入之前和之后的三维工程图hydraulic clamp如图2所示。

图1 原始草图与水印嵌入后的草图

图2 原始工程图与嵌入后的工程图

实验结果表示,本算法具有较好的透明性。另外solidworks三维工程图受平移、旋转和缩放等攻击后,顶点坐标的值不改变,所以水印对该种类型的攻击具有很好的鲁棒性。

4 结 论

本文针对solidworks三维工程图数据精度高的特点提出基于差值扩大法的可逆水印算法。由于solidworks三维工程图不允许数据随意改动,因此数据隐藏的可逆性具有十分重要的应用意义。通过水印嵌入之前的预处理提高数据的冗余量,实验结果表明本算法水印具有较好的透明性,能够抵抗平移、旋转和缩放攻击,而且能够完全恢复精度范围内数据。将来的工作还需进一步提高算法的强壮性。

[1] 张新宇,彭维,张三元.3D网格数字水印研究进展[J].计算机辅助设计与图形学学报,2003,15(8):913-920.

[2] Li Li,David Zhang,Zhigeng Pan.Watermarking 3D mesh by spherical parameterization[J].Computers&Graphics,2004,28(6):981-989.

[3] 潘志庚,孙树森,李黎.三维模型数字水印综述[J].计算机辅助设计与图形学学报,2006,8(4):1 103-1 110.

[4] 邵承永,王孝通,徐晓刚.矢量地图的无损数据隐藏算法研究[J].中国图象图形学报,2007,12(2):206-211.

[5] Tian J.Reversible water marking by difference expansion[C].Barcelona Spain:In Proceedings of IEEE international conference on Image Processing,2003,13(8):731-736.