Watermarking vector graphics

Introduction. Digital watermarking is a technique which embeds specific imperceptible statistical features into a digital asset (e.g., pictures or audio data) based on a secret key. Only if the key is known the existence of the watermark can be validated with some certainty.

Our contribution. One common way to watermark vector graphics is to embed statistical features by slightly dislocating the vertices. However, for many applications it is very important that certain topological properties of the input are not changed when embedding the watermark. For instance, it is crucial that no shortcuts are introduced in a PCB layout due to the watermark. Likewise, we do not want that streets and rivers overlap in a geographic map because of the watermark embedding.

In [HHMK14, Hub*12, Hub*10], we introduced a watermarking framework that allows to plug in an ordinary watermarking scheme for geometric data and still provides the following topological guarantees:

• The number of vertices and segments remains the same.
• The incidence orders of segments at vertices do not change.
• No intersections among segments are introduced.
• The containment relations connected between components of the figures are not changed.

In order to achieve this goal we compute, what we call, a maximum perturbation region (MPR) around each vertex which gives us the following guarantee: As long as vertices stay within their MPR, all the topological guarantees from above hold. (The above picture shows a part of the city of Salzburg and the blue circles show the MPRs.) The geometric problem here is to come up with algorithms that compute such MPRs that are large to allow high watermark embedding capacities but still small enough to respect the topological guarantees. In [HHMK14, Hub*12, Hub*10] we presented two algorithms: one is based on triangulations, the other is based on Voronoi diagrams.