Data Storage Carrier Objects as Illustration Watermarks for 3D Polygonal Models Henry Sonne

Data Storage:Carrier Objects as Illustration Watermarks for3D Polygonal ModelsHenry SonnetOtto-von-Guericke University∗Silvio LangeOtto-von-Guericke University∗AbstractOften,3D polygonal models are accompanied by data that explain model componentsor provide further information.Such data may be words,illustrations,videos,or audiosignals.In most cases,model and associated data are separately stored,e.g.,the modelhas links to associated data in a database.Beside a number of benefits,this approachalso has drawbacks such as database access after model propagation.In this paper,we introduce a novel methodology for storing data that is associated with model com-ponents.Similar to3D watermarking,we insert the data directly into the model.Thedata to be embedded is assigned to so-called Carrier Objects(3D polygonal objects)that are placed inside the original model afterwards.Our proposed technique allows toinsert several megabytes of data in the corresponding model components.1Introduction3D polygonal models are now widely-used.They are applied in numbers of domains,such as medicine,automotive engineering,or architecture.In many cases,those3D models are accompanied by textual information that refer to certain model components.Other accom-panying data,such as video or audio sequences,need much more storage space and hence, are exclusively stored in separatefiles.Often,the correlation between model and accom-panying data is realized by identifiers that refer to the associated data and are part of the model description.The problem is:once the model and its accompanying data shall be dis-tributed,all the data need to be packed.After being unpacked on the new owner’s computer, the different datafiles need to be managed;some of them may quickly get lost.We propose a novel technique that is based on illustrative watermarking techniques.In con-trast to traditional watermarking,illustration watermarking aims at embedding the largest possible amount of data into the cover object(object,data is associated with)instead of copyright protection and robustness against extrinsic parable to traditional wa-termarking,the embedded data shall be visually undetectable and robust against common geometric transformations(translation,rotation,and scaling)andfile format conversions.∗Department of Simulation and Graphics,D-39016Magdeburg,GermanyThe basic idea behind our proposed technique is tofill the3D polygonal model with objects (Carrier Objects)that carry the data to be embedded into the model.This technique com-prises two main aspects:(1)carrier objects are generated according to the amount of data to be encoded and(2)the carrier objects are placed inside the original ing this technique,original3D model and carrier objects become an entity.It is possible to encode an amount of data as large as several megabytes.This paper is organized as follows:After reviewing related work in Section2,the general idea behind using3D polygonal models as data containers is discussed in Section3.There-after,carrier objects are introduced in Section4.Positioning the carrier objects inside the model and retrieving the coded data are the contents of Sections5and6.Finally,Section7 summarizes this paper.2Related WorkIn[CM02],the authors state that electronic watermarking had been invented in1954.Since then,more than50years have past and manyfields of electronic watermarking are re-searched these days.In the last10years,watermarking3D models,vector graphics,audio and video data has gained more and more attention.However,image watermarking is still thefield of digital watermarking most research is focused on.There exist various publica-tions that deliver basic knowledge in the watermarking area(e.g.,C OX et al.[CMB01]). We are focused on watermarking3D geometric models.In this particularfield of digital watermarking,O HBUCHI et al.[OMA97]were thefirst to publish their work.For exam-ple,one of their introduced approaches is based on slightly modifying vertex positions to change the ratio of triangle edges and heights.In1999,B ENEDENS[Ben99]introduced an algorithm whose primary aim was to be robust against point randomization,mesh alter-ing operations,and polygon simplification.To this end,similar surface patch normals are computed,sampled to so-called bins,andfinally altered depending on the binary data to be embedded.There are numbers of other approaches that can be classified in the spatial domain(e.g.,[HB02,ME04]).Watermarking techniques in the transformed domain are an improvement compared to spa-tial domain techniques in that they are more robust against attacks.Here,a3D polygonal mesh is typically transformed into a different representation(e.g.,wavelet transform)be-fore a watermark is embedded by modifying the transformation’s(low-frequency)compo-nents.K ANAI et al.[KDK98]have been thefirst to watermark3D polygonal models in a transformed domain.Their technique is based on decomposing the3D polygonal mesh be-fore the watermark is embedded into the wavelet coefficients.A more robust technique has been introduced by P RAUN et al.[PHF99].They convert the original polygonal mesh into a multi-resolution format.Since they keep the coarse base mesh and a sequence of refine-ment operations,it is possible to identify the refinement operations that have the greatest effect on the model’s geometry.For those refinements,scalar basis functions are defined and used for watermarking.An extension to P RAUN’s approach has been introduced by Y IN et al.[YPSZ01].They construct Burt-Adelson mesh pyramids and embed watermarks in the coarser levels of those pyramids,hence,resisting multi-resolution operations.The ex-emplarily introduced transformed domain techniques are non-blind.A recently published approach in the wavelet domain(U CCHEDDU et al.[UCB04])is a blind method,which means that neither the original3D model is needed nor other data for watermark recovery.A different approach has been introduced by G ARCIA and D UGELAY[GD03].They water-mark a3D model’s texture to protect images synthesized from the model.The watermark is extracted by reversing render operations.To this end,the model’s texture is recovered by using the original3D model as well as the applied mapping function,which indicates that their proposed technique is a non-blind methodology.However,our proposed tech-nique can be compared to their approach in that vertices of the original3D polygonal mesh are not modified.But there are two main differences:a3D model’s texture is a separate data structure(can simply be exchanged,has to be stored individually,and hence,may get lost)and the amount of encodable data(data payload)strongly affects the watermark’s perception.In this paper it will be shown that,although quite different to traditional water-marking techniques,our introduced carrier objects are still interconnected with the original 3D polygonal mesh,yet without any visual effect on its geometry or topology.33D Polygonal Models as Data ContainersWhat do we want to aim at?Assume we have a3D model and data that refer to specific components of the model.The data may be explaining text,short videos,links to other data(e.g.,websites),other3D models,audio data,etc.The question that arises is how can this data be stored?A common way is to give each model’s component a unique identi-fier and store the related data separately in a database(using a hash map or a knowledge base,e.g.,[PHP+01,RSHS03]).Storing the data separately features a number of advan-tages,for example,distributed systems may access the data that is easy to administrate. However,a number of disadvantages are:When a3D model that is linked with additional data is distributed,an access to the separately stored data cannot necessarily be guaranteed. The database may be down or its access may be denied.Furthermore,altering a data item may cause problems,namely as soon as the altered data has become invalid for one of the systems accessing the database.Also,format conversions of the model data may yield the unique identifiers to be overwritten due to redefine operations.Beside storing the data in a database,it is still widespread to store the data in separatedfiles that need to be kept close-by the model.In that case,those datafiles may quickly get lost.Our goal is to show an alternative to store data that is associated with a3D model.It should not be regarded as replacement of a database(although the data payload is remarkable, a database is still more powerful),but as a new technique that may be combined with traditional techniques.What we suggest is to use illustration watermarks(refer to S ONNET et al.[SIDS03])to store object-related data(i.e.,data that relates to the specific object or region in which it is embedded).However,our technique should not be compared to the traditional water-marking techniques introduced in Section2.In contrast to making a3D model as secure as possible and to avoiding its illegal distribution,we want to increase the added value of the model.In this regard,it would make no sense to attack the watermarks embedded into theFigure1:Given a model(component)and a data stream to be encoded(a),carrier objects are generated(b).Carrier objects are3D objects into which the illustration watermarks will be embedded.At the same time,cross-sections(c)for placing the carrier objects inside the model are computed(d).The(transparently)rendered original3D model containing the (strongly magnified)carrier objects is shown in(e).model,since it would be equal to decreasing the model’s added value.Our proposed technique is based onfilling a(ideally closed)3D polygonal mesh with so-called Carrier Objects each of which storing a certain number of bytes as part of the complete watermark data stream.Figure1outlines our technique.4Carrier Objects as Illustration WatermarksA watermark data stream is embedded into carrier objects.These are3D polygonal objects whose various geometrical and topological properties can be modified to store data bits. Each carrier object can hold a certain amount of data that mainly depends on its complexity. Figure2exemplarily illustrates4carrier objects.The carrier object shown in Figure2(a) is called Primary Carrier Object(PCO)because all the consecutive carrier objects(CCO) (Figure2(b)-(d))are positioned,transformed,and assigned attributes corresponding to the PCO.4.1Characteristics of the primary carrier objectThe primary carrier object does not store any portion of the watermark data stream,but it is of high importance with regard to the consecutive carrier objects.Its geometry and topology are used as patterns when the consecutive carrier objects are encoded and decoded.While its material does not have any effect on the consecutive objects,the primary object’s number and position of vertices,orientation,and scaling are used as reference.The primary object features specific characteristics such that it can easily be recovered.For example,it has a single triangle T P that does not share any of its edges with another triangle (see Figure2(a)).Additionally,the ambient colors of the triangle’s vertices are coded:theirFigure2:Primary(a)and consecutive carrier objects(b)-(d).The consecutive carrier ob-jects have been watermarked by modifying certain material properties and applying a num-ber of transformations(e.g.,scaling,rotation,single vertex displacements).Below each object its local coordinate system is displayed.least significant bits(first bits)of the blue color channels,which are reserved and usually unset,are set.Furthermore,T P has exactly one edge E P whose end points V∗P and V∼P are specifically coded:the second bits of their ambient colors’blue channels are set.Since V∗P is the origin of the object’s local coordinate system,it is also coded:in addition to its two least significant set bits,the third bit is set as well.Andfinally,the color channel bits of the remaining vertices yield a specific code.4.2The consecutive carrier objects’data payloadO HBUCHI et al.[OMA98]have listed several embedding targets in3D polygonal models, such as shape,shape attributes,or animation parameters.All these targets were meant to be applied to one single3D object.In our case,a subset of those targets is also meant to be applied to a single3D object—namely a carrier object.But in contrast,the original3D polygonal model to be watermarked may contain numbers of carrier objects. Comparable to O HBUCHI et al.a carrier object’s embedding targets(embedding attributes) are:its transformation,geometry,topology,and material.We differentiate between at-tributes that are applied to the entire carrier object,its triangles,or its vertices,which means that some attributes depend on the object’s number of vertices(the object’s complexity). Attribute:(1)transformationA carrier object’s transformation does affect the entire object.Transformations include ro-tation,translation,and scaling(see Figure2(b)-(d)).After applying the resulting transfor-mation matrix to the current carrier object,a specific bit code is expressed.•Rotation:An angle is typically measured in radian(0-2π).Anyfloating-point number less than5.24288and in the range of0-2π(with5decimal places at most)can be expressed using19bits.Those19bits can be used for data embedding(difference between primary object’s orientation and current object’s orientation).Carried to the 3axes,57bits can be stored by an object’s rotation.•Translation:Using5places,a non-negative number(uvwxy)less than65536can be expressed using16bits.When the real position of the carrier object i(pos Ci)isgiven,its new position along axis x may be computed by multiplying pos Cix and1.0uvwxy.Hence,for each axis a total number of48bits may be coded.•Scaling:Consecutive carrier objects can be scaled only down with regard to the pri-mary object.Hence,values between0and1using5decimal places may be specified, which allows48bits to be coded in total.Attribute:(2)geometryOperations such as altering vertex positions belong in this category.Some of the carrier ob-jects’vertices in Figure2(b)-(d)have been excessively altered for illustration.Apparently does the amount of data that can be inserted per object depend on the number of available vertices.Similar to the object translation,a total number of48bits can be embedded per vertex.As can be seen in Figure2,for each carrier object a triangle is marked whose vertices may not be individually altered.The reason for this restriction is that they will be compared to the primary object’s triangle during data extraction.As a consequence,only a number of3 less the total number of carrier object vertices can be used for coding.Attribute:(3)topologyWhen the vertices of a triangle are sorted clockwise or counter-clockwise,1bit of data can be embedded per triangle.In general,the vertex order affects the orientation of the triangle’s normal and hence,its shading.However,since carrier objects are not planned to influence the original model’s appearance,this aspect can be disregarded.Attribute:(4)materialAn individual material can be applied to every single vertex.For this reason and the fact that,respectively,at least5material properties(ambient,diffuse,specular,and emissive colors as well as an object’s shininess)can be specified,the material attribute allows to code the largest number of bits.Each material’s color property can hold32bits(RGB and alpha color channels,RGBA).The material’s shininess is specified using8bits,which means that a total number of136bits can be coded per vertex.Since the three least significant bits of the ambient colors’blue channel are reserved for triangle,edge,and origin identification, the total number of codable bits per vertex is decreased to133bits.Note,that in case of a transparent original model the materials’alpha channels should be set to0(translucent carrier objects),which decreases the amount of codable data accordingly.4.3Data payload:summaryAs we know how many bits per attribute can be coded,the following equation allows to determine the total number of bits(n bits)that can be coded into a carrier object.The cal-culation depends on the carrier object’s number of vertices(n vert)and triangles(n tria).n bits=153(1)+(n vert−3)∗48(2)+n tria(3)+n vert∗133(4)(1)The number of carrier objects(n objs)needed to encode a specific amount of data(n data,in bits)can be determined using equation2.For example,in order to encode1000bytes(8000 bits)using a simple cube as carrier object(8vertices,12triangles),the equation yields a number of7carrier objects.n objs=ceiln data n bitsCCO +1PCO(2)Both attributes transformation and geometry strongly depend on exact geometric computa-tions.We assume an accuracy of at least7positions after decimal point,which,for example, can be achieved using the CGAL library[BFMS99].However,in order to be sure that the embedded bits can be correctly recovered,the bit embedding process is verified.5Watermarking the3D Polygonal ModelAs can be seen in Figure1,the generated carrier objects are placed inside the3D model. Just like the original model,carrier objects are composed of triangles such that model and carrier objects form an entity.But where should the carrier objects be placed?Their new positions should be chosen in a way such that a carrier object is neither located outside the original model nor does intersect with the model’s polygonal mesh.In general,searching for positions at which the carrier objects are to be placed can be compared to a raster operation applied to the original model.This operation can be stopped as soon as each carrier object has been positioned within the raster.In order to place the carrier objects within the model,cross-sections need to be calculated. The number of cross-sections to be calculated depends on the number of carrier objects. But,vice versa,only as many carrier objects can be inserted as space is available.In other words,if there is not enough space available,the carrier objects need to be more complex. Basically,the carrier objects’positioning includes two steps:(1)successively intersect the original model with a plane to obtain model vertices that will be connected to form a bounded area within the plane and(2)scan through those bounded areas tofind appro-priate positions.Figure3:An model’s cross-section within the x-y-plane at position z P.Figure4:Using scanlines to position carrier objects within a cross-section.5.1Computation of a cross-section’s bounded areaFigure3illustrates a single cross-section within the x-y-plane at position z P.The small (red)dots on thefigure’s right hand side symbolize the positions at which the model’s edges intersect with this current cross-section.To improve the efficiency,the edges have been sorted according to their z-values before.When the intersection vertices have been determined,they need to be appropriately con-nected.To this end,two vertices V i and V j are connected if and only if the edges E i and E j belong to one and the same triangle in the original model.E i and E j are the edges whose intersection with the cross-section resulted in V i and V j.5.2Placing carrier objects within a cross-sectionFinally,the carrier objects are placed within the area bounded by the previously connected intersection vertices.This is done using a scanline technique(see Figure4).The scanline’s increment as well as the distance between two adjacent carrier objects,located on the same scanline,depends on the carrier objects’size.Carrier objects to be positioned must not intersect with the model’s polygonal mesh.To verify this important aspect,each object’s bounding sphere is intersected with the origi-nal polygonal mesh.The reason for having chosen a bounding sphere is that intersection operations may be inefficient when the carrier objects become more complex.Figure4 exemplarily illustrates the positioning of carrier objects(with their bounding spheres and strongly magnified)for three scanlines.The efficiency of this positioning process could be improved byfinding a bounding object (e.g.,cube)inside the original model within which all carrier objects will be placed.The calculation of cross-sections and scanlines would be much faster and it would be unneces-sary to verify that no carrier object intersects with the original polygonal mesh.However,when the model’s shape is approximated by a primitive,the number of carrier object posi-tions may decrease.6Retrieving the Encoded DataDecoding the data essentially includes two main aspects:(1)Locate the primary carrier object and according to its orientation,locate the remaining(consecutive)carrier objects.(2)Decode the data embedded in the carrier objects.6.1Detecting the carrier objectsCarrier objects have specific characteristics that are incorporated in their detection process (see Section4).They are self-contained objects that do not intersect with other objects. Once the primary carrier object has been located,all the other objects can be detected using the primary object’s local coordinate system.As already addressed in Section4.1,the primary carrier object has unique characteristics. Its single triangle T P together with its normal and the edge E P(see Figure2)form the pri-mary object’s local coordinate system(x is specified by E P,z by the triangle’s normal,and y by a vector perpendicular to x and z).Using this coordinate system,all the other carrier objects can be found in the correct order.The x-y-plane is comparable to a cross-section in which the carrier objects had been positioned.Thefirst scanline and hence,the direc-tion along which to search for thefirst consecutive carrier objects,is given by E P.Since the consecutive carrier objects may be transformed,which means that they are not located exactly at an expected position,a number of search rays randomly distributed around E P (comparable to Distributed Raytracing)are used for detection.An carrier object’s trian-gle(and the object itself)can then easily be identified with its ambient color bits.When thefirst scanline has been processed,consecutive scanlines(and afterwards,consecutive cross-sections)are computed using the PCO’s local coordinate system.Since locating the carrier objects is expensive,this operation could be improved by po-sitioning the carrier objects such that the current and the following object intersect each other.That way the next carrier object is always the object that intersects with the actual object and that has not yet been processed.6.2Decoding the embedded dataWhen the carrier objects have been detected,the embedded data needs to be decoded. While the data coded in the color of their vertices can easily be decrypted,decoding the data embedded in object transformations and vertex displacements requires preprocessing. Firstly,entire CCO transformations have to be reversed.This is done using the local coor-dinate systems of T Ci(V∗Ci as origin)(0<i<n objs)and T P(V∗P as origin)(see Figure 2).After object translation and rotation have been reversed,the scaling operation can be reversed according to the triangles’proportions.Finally,when the two coordinate systems share the same base vectors,the individual vertex displacements can be reversed.In all cases,the data is coded in the dissimilarity of those transformations(compare Section4.2).Figure5:3D model data is coded inside the polygonal mesh of the vase thickness.In the first two illustrations the mesh of the vase(original and with carrier objects)is shown.The actual encoded data(water andflower,2.4MB)is visualized in thefigure’s right hand side.Figure5shows a3D model(vase offlowers)into which further model components(water,flower)have been embedded as illustration watermarks.7Summary and DiscussionFigure6:A single bone has been chosen for encoding data(a).A close-up of the bone’s mesh with carrier objects is shown in(b).The encoded data(17kByte)are textual infor-mation and a polygonal object(red muscle)that both relate to the small foot bone(c).We have introduced a novel methodology for storing data that is associated with specific3D model components(see Figure6).The data is directly integrated into the model using illus-tration watermarks carried by individual3D objects(carrier objects).Carrier objects and original3D model form a unit after the carrier objects have been placed inside the model.The encoded data is imperceptible since the polygonal mesh of the original model,which visually remains unchanged,encloses the carrier objects.Depending on the complexity of the carrier objects and the available space inside the model,several megabytes of data may be inserted.The watermarked3D model is robust against common geometric transformations(trans-lation,rotation,scaling)due to the carrier objects’local coordinate systems used during decoding.Both model and carrier objects are composed of triangles.Hence,file format conversions do not affect the embedded data as long as the complete model’s triangle struc-ture is not altered.However,from this it follows that model compression or partially cutting off model components may destroy the embedded data.Also,decreasing the accuracy of the model’s geometry(e.g.,cutting decimal places of vertex positions)has an effect on the embedded watermark.In our proposed methodology,data is added to the model.Beside increasing the overall filesize,a major amount of data has to be rendered.In order to embed a certain amount of data,the carrier objects’complexity as well as the number of less complex but faster to render carrier objects may be varied.We have tested the effect of those aspects on the actual rendering costs.The result was:when embedding1000bytes,less complex carrier objects (8vertices,747fps)yield lower rendering costs than complex carrier objects(100vertices, 583fps);but when embedding an amount of100000Bytes,rendering with complex objects was more than twice as fast as rendering with less complex objects(8fps and3fps).Thus, due to internal hard-and software optimization,a smaller number of more complex carrier objects should be preferred for larger amounts of data.But also remember in this regard, for each object a specific amount of data(153bits)is embedded per object(refer to Section 4.2).Hence,with a larger number of carrier objects the data payload is more effective. For the future,we think about replacing the carrier objects by a number of hulls whose shapes are adapted to the model’s shape(like onion skins).That way,the available space capacity inside the model can be more effectively used.Furthermore,we aim at embedding a larger amount of data into the same number of triangles to relieve the rendering costs. References[Ben99]O.Benedens.Geometry-Based Watermarking of3D Models.IEEE Computer Graphics and Applications,19(1):46–55,1999.[BFMS99]C.Burnikel,R.Fleischer,K.Mehlhorn and S.Schirra.Efficient Exact Geomet-ric Computation Made Easy.In:Proc.of the15th Annual ACM Symposiumon Computational Geometry,pp.341–350,1999.[CM02]I.J.Cox and ler.The First50Years of Electronic Watermarking.EURASIP Journal on Applied Signal Processing,2:126–132,2002.[CMB01]I.J.Cox,ler and J.A.Bloom.Digital Watermarking:Principles& Practice.Morgan Kaufmann Publishers,2001.[GD03] E.Garcia and J.-L.Dugelay.Texture-Based Watermarking of3-D Video Ob-jects.IEEE Transactions on Circuits and Systems for Video Technology,13(8):853–866,2003.[HB02]T.Harte and A.G.Bors.Watermarking3D Models.In:Proc.of IEEE2002 International Conference on Image Processing,pp.661–664,2002.[KDK98]S.Kanai,H.Date and T.Kishinami.Digital Watermarking for3D Polygons using Multiresolution Wavelet Decomposition.In:Proc.of IFIP Working Group5.2,Sixth International Workshop on Geometric Modelling:Fundamentals andApplications(GEO-6),pp.296–307,1998.[ME04]Y.Maret and T.Ebrahimi.Data Hiding on3D Polygonal Meshes.In:Proc.of the Multimedia and Security Workshop2004,pp.68–74,2004.[OMA97]R.Ohbuchi,H.Masuda and M.Aono.Watermarking Three-Dimensional Polygonal Models.In:Proc.of the ACM International Conference on Mul-timedia1997,pp.261–272,1997.[OMA98]R.Ohbuchi,H.Masuda and M.Aono.Watermarking Multiple Object Types in Three-Dimensional Models.In:Proc.of the Multimedia and Security Workshopat ACM Multimedia,pp.83–91,1998.[PHF99] E.Praun,H.Hoppe and A.Finkelstein.Robust Mesh Watermarking.In:Proc.of the26th Annual Conference on Computer Graphics and Interactive Tech-niques(SIGGRAPH’99),pp.49–56,1999.[PHP+01]A.Pommert,K.H.H¨o hne,B.Pflesser,E.Richter,M.Riemer,T.Schiemann, R.Schubert,U.Schumacher and U.Tiede.Creating a High-Resolution Spa-tial/Symbolic Model of the Inner Organs Based on the Visible Human.MedicalImage Analysis,5(3):221–228,2001.[RSHS03]F.Ritter,H.Sonnet,K.Hartmann and T.Strothotte.Illustrative Shadows:Inte-grating3D and2D Information Displays.In:Proceedings of the2003Interna-tional Conference on Intelligent User Interfaces,pp.166–173,2003.[SIDS03]H.Sonnet,T.Isenberg,J.Dittmann and T.Strothotte.Illustration Watermarks for Vector Graphics.In:Proc.of Pacific Graphics2003,pp.73–82.IEEE Com-puter Society,2003.[UCB04] F.Uccheddu,M.Corsini and M.Barni.Wavelet-Based Blind Watermarking of3D Models.In:Proc.of the Multimedia and Security Workshop2004,pp.143–154,2004.[YPSZ01]K.Yin,Z.Pan,J.Shi and D.Zhang.Robust Mesh Watermarking Based on Multiresolution puters&Graphics,25(3):409–420,2001.。