A Blind Watermarking Algorithm for Copyright Protection of Vector Geospatial Data Under Controllable Errors Based on DFT
-
摘要: 传统的DFT(discreteFouriertransform)变换域水印算法中,水印直接嵌入变换后的系数,导致矢量空间数据误差较大。针对此类算法的缺点,本文提出了基于DFT的可控误差矢量空间数据盲水印算法。该算法通过放大处理DFT变换系数,将水印嵌入幅度系数和相位系数中,水印提取采用投票原则,无需原始数据的参与。试验表明,水印嵌入矢量空间数据引起的误差很小;水印对数据格式转换及常见的几何变换攻击具有很好的鲁棒性。Abstract: InDFTwatermarkingalgorithms,thewatermarksareoftenembeddeddirectlyinthetrans formationcoefficients,causinglargeerrorsinwatermarkeddata.Toovercomesuchdisadvantageofthesealgorithms,ablindwatermarkingalgorithmforcopyrightprotectionofvectorgeospatialdatabasedonerrorreductionisproposed.ThisalgorithmamplifiestheDFTtransformcoefficientsandem bedsthewatermarksintheamplitudecoefficientsandphasecoefficientsbyDFTtransform,andthewatermarkisembeddedseveraltimes.Inaddition,thevotingprincipleisutilizedtodetectthewater mark.Nooriginaldataisneededinthewatermarkextractionprocedure.Theexperimentshaveshownthatspatialaccuracyofthewatermarkeddataisacceptableandthealgorithmisrobusttoavarietyofgeometrictransformationattacks.
-
Keywords:
- DFT /
- controllableerrors /
- vectorgeospatialdata /
- blindwatermarking
-
聚类是数据挖掘的基础技术，有广泛的应用前景[1-2]。聚类算法主要分为层次聚类法、网格聚类法、分割聚类法和密度聚类法[3]。其中，分割聚类法简单、快速，广泛应用于各个领域，典型的分割聚类法是K-means算法和K-medoids算法。在实际应用中，这两种算法由于需要用户输入聚类个数，聚类结果与初始点选择有关等缺点，不能很好地满足用户的需要[4]。《Science》中提出的峰值密度聚类算法虽然解决了上述问题，但存在阈值需要人为输入的问题[5]。
本文根据数据场，提出了数据质量聚类中心的概念。数据场将物质粒子间的相互作用及场描述方法引入到抽象的数域空间，实现数据对象或者样本点间相互作用的形式化描述[6]和计算。数据场将数据所具有的固有属性定义为数据的质量，并根据实际挖掘视角的不同，表示数据不同的属性。本文中，数据质量将代表数据的密集程度，并以此确定聚类中心，该方法无需用户输入聚类个数，也无需选择初始点，更无需人为设定阈值。
1 数据质量聚类
在物理场中，物体的质量是不能改变的，是物体固有的属性。同理，在数据场中，数据的质量也代表了每个数据自身的固有属性。所不同的是，在数据场中，数据并不是实际存在的物体，可以这样认为，n维数据集构成了一个n维的数据空间，数据集中每一个数据就是存在于这个n维空间中的“物体”，其各种属性都遵从于这个n维空间自身的特点。
定义：设数据集α含有N个数据点，α ={x1, x2…xn}，其中xi={xi1, xi2…xip}，组成一个P维空间Ω，在空间Ω中的数据点xi所固有的属性τ，称之为点xi在数据集α中的数据质量。
需要注意的是，定义中数据质量代表的是数据在数据集中的固有属性，这个固有属性会随着数据挖掘视角的不同而改变。一个数据点在数据集中可能会具有多种不同的固有属性，应当根据当前的挖掘任务赋予数据相应的属性。因此，数据场中数据质量具有集群性，即只在数据集中具有质量；空间唯一性，即相关的属性只在对应的数据集中存在；可变性，即根据需求不同代表的数据属性也不同。
聚类算法的目的是让类内相似度最高，类间相似度最低。反映在数据集的空间分布上，就是相似度高的数据分布在同一个类簇中，不同的类簇代表了不同的类别。因此，在聚类分析中，一般取数据密集程度这一属性作为数据的质量。此时，数据场中的数据质量本质上是反映数据集中数据的密集程度，处于密集区域的数据具有较大的数据质量，处于稀疏区域的数据具有较小的数据质量。
图 1所示的红色点标出的是数据集中质量较大的点，与所描述的数据质量概念一致，这些点都处于数据集中的密集区域。在聚类分析中，处于密集区域的点都有可能成为聚类中心。图 1中所示的数据集含有5 000个点，而质量较大的点约有1 000个，显然，只根据数据的质量不能确定数据集的聚类中心。
类比于物理场中的引力，聚类中心应当具有较大的质量，能够吸引其他质量较小的点在其周围形成一个类簇。同时，各个聚类中心应当相距较远，从而使聚类中心之间的作用力很小，直至可以忽略，这样，类簇与类簇间的相互关系就很弱，而类簇内的相互关系就很强，满足了最基本的聚类思想。
因此，数据质量聚类算法使用数据质量和数据之间的距离两个属性共同确定一个聚类中心。其中，数据之间的距离属性定义为：在数据集{x1, x2…xn}中，所有比xi质量大的点到xi距离的最小值；如果点xi是数据集中质量最大的点，那么其距离属性就为数据集中其他点xj(j≠i)到xi距离的最大值。
数据距离属性的计算式为：
$$ {{\delta }_{i}}=\left\{ \begin{align} &\underset{j:{{m}_{j}}>{{m}_{i}}}{\mathop{\min }}\, ({{d}_{ij}}), \ \ \exists \ {{m}_{i}}<{{m}_{j}} \\ &\underset{j=1, 2, \cdots , n}{\mathop{\max }}\, ({{d}_{ij}}), \ \ \nexists \ {{m}_{i}}<{{m}_{j}} \\ \end{align} \right. $$ (1) 式中，m表示数据的质量，dij表示两点间的距离。当数据集x1, x2…xn中存在比xi数据质量大的点xj，即mi＜mj时，数据之间的距离为所有比xi质量大的点到xi距离的最小值；如果不存在比xi数据质量大的点xj，即xi是数据集中质量最大的点，那么其距离属性就为数据集中其他点xj(j≠i)到xi距离的最大值。所以点xi的mi和δi都较大时，可以确定是聚类中心。在实际操作中，为了便于准确找到数据集中同时具有较大数据质量和较大距离属性的点，用数据集中每个数据点的质量属性作为横坐标、距离属性作为纵坐标绘制的决策图来确定聚类中心。在决策图中，同时具有较大横坐标和纵坐标数值的点会脱离其他只具有1个较大属性的点或者不具有较大属性的点，从而可以将这些脱离出来的点作为聚类中心。
图 2所示为数据集的决策图，可以发现，只有少数几个点的两个属性都较大，这些点用红色标出，作为备选聚类中心。
2 数据质量聚类算法实验验证
2.1 实验数据
数据质量聚类算法的核心是确定聚类中心，涉及数据的质量和距离两个属性。其中，距离属性计算使用欧氏距离，质量的计算采用参考文献[7]中的方法。在确定聚类中心后，先进行数据类别的划分，即将剩余点划入与其最近的聚类中心，形成一个个类簇，然后根据用户需要输出聚类结果。算法流程如图 3所示。
通过一系列的对比实验验证数据质量聚类算法的聚类效果，并与传统的K-means算法、K-medoids算法和文献[1]中的峰值密度聚类算法进行了对比。
在对比实验中，采用7个数据集进行实验。数据集A1、A2、A3分别含有3 000个点和20个类簇、5 250个点和35个类簇、7 500个点和50个类簇，并且3个数据集中类簇内点的个数均为150个。数据集S1、S2、S3、S4都含有5 000个点和15个类簇，但是每个数据集中类簇的扩展程度不一样，而且4个数据集中每个类簇的中心是已知的[8]。这7个数据集的二维可视图如图 4和图 5所示，图 4和图 5中的横、纵坐标分别为数据集二维可视图的X轴和Y轴。
2.2 对比实验
首先对数据集A1, A2, A3分别使用数据质量聚类算法和K-means算法、K-medoids算法和峰值密度聚类算法进行聚类。将得到的聚类结果进行二维可视化展示，同时，对每个数据集中聚类结果进行统计，记录每种算法在每个类簇中聚集的点个数，与数据集实际每个类簇中应有点的个数进行对比，计算出准确率。
因K-means算法和K-medoids算法需要输入聚类个数，故按照数据集实际情况输入。数据质量聚类算法使用决策图确定聚类中心，如图 6所示为数据集A1、A2和A3通过决策图选出的聚类中心。图 6中彩色点为聚类中心，即横坐标和纵坐标都较大的点。所选出的聚类中心个数在数据集A1中为20，在A2中为35，在A3中为50，这与数据集原有的类簇个数相同。
图 7是4种聚类算法的结果图，从图 7中可以发现，数据质量聚类算法和峰值密度聚类算法都有较好的聚类效果。对于聚类算法的准确率统计每一个数据集中4种算法对每一个类簇聚类的准确率，即类簇内点的个数和实际每个类内点的个数比值。统计结果如表 1所示。
![]()
图 7 数据集A1、A2、A3聚类结果比较Figure 7. Comparison of Clustering Results on Datasets A1, A2, A3表 1 数据集A1、A2、A3实验平均准确率统计表/%Table 1. Clustering Accuracies of Datasets A1, A2, A3/%数据集 K-means
算法K-medoids
算法峰值密度
聚类数据质量
聚类A1 86.87 70.33 95.33 96.00 A2 76.84 79.73 96.65 96.91 A3 79.81 61.17 96.17 97.49 从表 1的统计结果中可以发现，数据质量的聚类算法具有最高的平均准确率，相比于传统的K-mean算法和K-medoids算法分割聚类算法，在准确率上提高了很多，同时，与最新的峰值密度聚类算法相比，准确率也有所提高。
在数据集S1、S2、S3、S4中，每个类簇的中心是已知的，通过比较4种算法得到的聚类中心与实际中心的偏差量，对比每种算法确定聚类中心的效果。使用决策图确定数据质量聚类算法的聚类中心。K-means算法与K-medoids算法依然输入真实的类簇个数，4种算法聚类结果二维可视图如图 8所示。
![]()
图 8 数据集S1、S2、S3、S4聚类结果比较Figure 8. Comparison of Clustering Results on Datasets S1, S2, S3, S4在图 8中，数据质量聚类算法和峰值密度聚类算法的聚类效果直观上要优于K-means算法和K-medoids算法。在对比聚类效果后，统计4种聚类算法所确定的聚类中心与实际中心位置的误差率。具体计算式为：
$$ {{\gamma }_{i}}=\frac{1}{2}(\frac{{{x}_{i}}-{{a}_{i}}}{{{a}_{i}}}+\frac{{{y}_{i}}-{{b}_{i}}}{{{b}_{i}}}) $$ (2) 式中，xi和yi为实验中得到的聚类中心的坐标；ai和bi为数据集类簇实际的坐标。γi值越小，说明越接近实际的类簇中心。每个数据集中的平均误差率统计结果如表 2所示。
表 2 数据集S1、S2、S3、S4聚类中心平均误差率统计/%Table 2. Error Rate of Clustering Centers for Datasets S1, S2, S3, S4/%数据集 K-means
算法K-medoids
算法峰值密度
聚类数据质量
聚类S1 0.37 0.49 2.81 0.14 S2 0.53 0.74 0.31 0.11 S3 0.98 1.55 0.66 0.15 S4 1.39 1.71 0.46 0.14 从表 2中可以看出，数据质量聚类算法所确定的聚类中心与实际聚类中心的误差率最小，几乎与实际中心重合，明显优于K-means算法、K-medoids算法和峰值密度聚类算法。
综合数据集A1、A2、A3和数据集S1、S2、S3、S4的实验结果，可以认为数据质量聚类算法比传统的分割聚类算法和峰值密度聚类算法有更好的聚类效果。
2.3 实验结果分析
上述实验结果说明，数据质量聚类算法不仅可以准确提取出聚类中心的个数，而且在剩余点的划分上也有很高的准确率，对于数据集A1、A2、A3平均准确率分别达到了96.00%、96.91%和97.49%。在确定聚类中心上，本文方法也有很高的准确率，对于数据集S1、S2、S3、S4，聚类中心的平均误差率分别为0.14%、0.11%、0.15%和0.14%。数据质量聚类算法不仅在各项指标上明显优于传统的K-means算法和K-medoids算法，而且优于峰值密度聚类算法。
对于数据集A1、A2、A3，数据质量聚类算法比峰值密度聚类算法在平均准确率上分别提高了0.67、0.26和1.32个百分点，而对于数据集S1、S2、S3、S4，聚类中心的平均误差率分别降低了20.07、2.82、4.40和3.29倍。综合以上实验结果，可以证明数据质量聚类算法能够准确确定聚类中心，并能够得到准确的聚类结果。
3 结语
传统的中心聚类算法虽然简单快速，但是需要用户输入较多参数，并且具有球形偏差，在实际应用中有较多限制。本文提出了数据质量的概念，即代表了数据场中数据的固有属性，并且根据挖掘视角的不同，数据质量所代表的属性也不同。在本文中，赋予数据质量数据密集程度的属性，结合物理场中引力的概念，提出一种确定聚类中心的新方法，即具有较大质量和较大距离属性的点可以视为聚类中心。本文方法解决了需要用户输入参数、聚类结果受初始点影响等问题，减少了中心聚类算法在实际应用中的限制。实验结果证明，数据质量聚类算法能够准确找到数据集的聚类中心，并具有较为准确的聚类结果。
数据质量聚类算法虽然较为准确，但在实际应用中需要提高算法的效率，可以采取分布式计算的方式，这将是下一步研究的方向。
-
[1] YanHaowen,LiJun,WenHong.AKeyPoints BasedBlindWatermarkingApproachforVectorGeo SpatialData[J].犆狅犿狆狌狋犲狉狊，犈狀狏犻狉狅狀犿犲狀狋犪狀犱犝狉犫犪狀犛狔狊狋犲犿狊，２０１１，３５（６）：４８５４９２[2] NiuXiamu,ShaoChengyong,WangXiaotong.ASurveyofDigitalVectorMapWatermarking[J].犐狀狋犲狉狀犪狋犻狅狀犪犾犑狅狌狉狀犪犾狅犳犐狀狀狅狏犪狋犻狏犲犆狅犿狆狌狋犻狀犵，犐狀犳狅狉犿犪狋犻狅狀犪狀犱犆狅狀狋狉狅犾，２００６，２（６）：１３０１１３１６[3] KangHII,KimKII,ChoiJUK.AVectorWa termarkingUsingtheGeneralizedSquareMask[C].InformationTechnology:CodingandComputing,ProceedingsofInternationalConferenceonIEEE,SanJose,California,USA,2001[4] LeeSH ,KwonKR.VectorWatermarkingSchemeforGISVectorMapManagement[J].犕狌犾 狋犻犿犲犱犻犪犜狅狅犾狊犪狀犱犃狆狆犾犻犮犪狋犻狅狀狊，２０１３，ｄｏｉ：１０．1007/s11042 011 0894 y[5] SolachidisV,NikolaidisN,PitasI.FourierDe scriptorsWatermarkingofVectorGraphicsImages[C].Proceedingsof2000InternationalConferenceonIEEE(ImageProcessing),VancouverBC,Can ada,2000[6] SolachidisV,PitasI.WatermarkingPolygonalLinesUsingFourierDescriptors[J].犆狅犿狆狌狋犲狉犌狉犪狆犺犻犮狊犪狀犱犃狆狆犾犻犮犪狋犻狅狀狊，犐犈犈犈，２００４，２４（３）：44 51[7] GiannoulaA,NikolaidisN,PitasI.WatermarkingofSetsofPolygonalLinesUsingFusionTechniques994武汉大学学报·信息科学版2015年7月[C].MultimediaandExpo,ICME’02,Lausanne,Switzerland,2002[8] KitamuraI,KanaiS,KishinamiT.CopyrightPro tectionofVectorMapUsingDigitalWatermarkingMethodBasedonDiscreteFourierTransform[C].Geoscienceand Remote Sensing Symposium,IGARSS’01,Sydney,2001[9] WangQisheng,ZhuChangqing,XuDehe.Water markingAlgorithmforVectorGeo spatialDataBasedonDFTPhase[J].犌犲狅犿犪狋犻犮狊犪狀犱犐狀犳狅狉犿犪 狋犻狅狀犛犮犻犲狀犮犲狅犳犠狌犺犪狀犝狀犻狏犲狉狊犻狋狔，２０１１，３６（５）：523 526(王奇胜,朱长青,许德合.利用DFT相位的矢量地理空间数据水印方法[J].武汉大学学报·信息科学版,2011,36(5):523 526)[10] XuDehe,ZhuChangqing,WangQisheng.BlindWa termarkingModelofVectorSpatialDataBasedonDFTofQIM[J].犌犲狅犿犪狋犻犮狊犪狀犱犐狀犳狅狉犿犪狋犻狅狀犛犮犻 犲狀犮犲狅犳犠狌犺犪狀犝狀犻狏犲狉狊犻狋狔，２０１０，３５（９）：１１００ 1103(许德合,朱长青,王奇胜.利用QIM的DFT矢量空间数据盲水印模型[J].武汉大学学报·信息科学版,2010,35(9):1100 1103)[11] WANGQisheng.ResearchonDigitalWatermarkingforVectorGeo spatialDataBasedonDFT[D].Zhengzhou:InformationEngineeringUniversity,2008(王奇胜.基于DFT的矢量地理空间数据数字水印技术研究[D].郑州:信息工程大学,2008)[12] XuDehe.ResearchontheModeloftheDigitalWater markingforVectorGeo spatialDataBasedonDFT[D].Zhengzhou:InformationEngineeringUniversity,2008(许德合.基于DFT的矢量地理空间数据数字水印模型研究[D].郑州:信息工程大学,2008)[13] ZhaoLin.ResearchonAdaptiveVectorMapWa termarkingAlgorithmBasedonDFT[D].Harbin:HarbinEngineeringUniversity,2009(赵林.基于DFT自适应矢量地图水印算法的研究[D].哈尔滨:哈尔滨工程大学,2009)[14] MinLianquan.ASurveyofWatermarkingTech niquesforVectorMapData[J].犑狅狌狉狀犪犾狅犳犌犲狅 犿犪狋犻犮狊犛犮犻犲狀犮犲犪狀犱犜犲犮犺狀狅犾狅犵狔，２００９（２）：９６１０２（闵连权．矢量地图数据的水印技术综述［Ｊ］．测绘科学技术学报，２００９（２）：９６１０２）
下载:
计量
- 文章访问数: 1346
- HTML全文浏览量: 64
- PDF下载量: 382
