US 11,113,779 B2Granted

Digital watermarking leveraging anomalous mesh elements

AssigneeMicrosoft Technology Licensing, LLC

InventorsErik Gustaf Anders Johansson, Hans-Ulrik Tord Lindahl

Life of this patent

Estimating the term…

Loading patent…

Abstract

A technique is described herein for adding a digital watermark to a mesh. The mesh describes a three-dimensional object using a plurality of vertices and edges, which together define a plurality of polygonal shapes (e.g., triangles). The technique involves identifying at least one anomalous element of the mesh. The technique then supplements one or more of the anomalous elements by adding a computer-readable code to the anomalous element(s). That computer-readable code includes a digital watermark. An anomalous element corresponds to a part of the mesh that qualifies as a statistically atypical occurrence within the mesh, based on a specified rule that defines what constitutes a statistically atypical occurrence. In a reading stage, the technique finds the anomalous element(s). It then reads the digital watermark that has been encoded into the anomalous element(s).

Claims18

Dependent claims

One or more computing devices for creating a digital watermark, comprising:

hardware logic circuitry, the hardware logic circuitry corresponding to:
(a) one or more hardware processors that perform operations by executing machine-readable instructions stored in a memory;
or (b) one or more other hardware logic components that perform the operations using a task-specific collection of logic gates;
or (a) and (b), the operations including:
providing a file having a data structure that expresses an original mesh, the original mesh describing a three-dimensional object, the original mesh having:
a plurality of vertices that have respective locations in the original mesh;
a plurality of edges that connect the vertices together;
and
a plurality of polygonal shapes defined by the vertices and the edges;
searching the data structure for at least one anomalous element of the original mesh that qualifies as a statistically atypical occurrence within the original mesh, based on a predetermined rule that defines what constitutes a statistically atypical occurrence;
subdividing one or more anomalous elements that are identified to produce subdivisions that are chosen to collectively encode values of a computer-readable code including the digital watermark, said subdividing producing a modified mesh file and comprising, for each anomalous element of the one or more anomalous elements, adding a new vertex on each existing edge, for a plurality of existing edges, wherein the adding comprises choosing a location at which the new vertex is placed on the each existing edge, and wherein the location defines a particular value of the values of the computer-readable code;
and
storing the modified mesh file on a computer-readable medium, the computer-readable code being embedded in said one or more anomalous elements, and being extractable from said one or more anomalous elements by reading the values that are expressed by the subdivisions, said reading the values comprising, for the each anomalous element of the one or more anomalous elements, successively reading edges that include new vertices that are arrayed around a center vertex, starting with a chosen edge.

10 more elements

A method for reading a digital watermark, comprising:

receiving a file having a data structure that expresses a modified mesh, the modified mesh describing a three-dimensional object, the modified mesh having:
a plurality of vertices that have respective locations in an original mesh;
a plurality of edges that connect the vertices together;
a plurality of polygonal shapes defined by the vertices and the edges;
and
a computer-readable code that includes the digital watermark;
searching the data structure for at least one anomalous element of the modified mesh that qualifies as a statistically atypical occurrence within the modified mesh, based on a predetermined rule that defines what constitutes a statistically atypical occurrence, each of said at least one anomalous element having been subdivided to produce subdivisions that are chosen to collectively encode values of the computer-readable code;
reading the computer-readable code from said at least one anomalous element that is identified by said searching by reading the values that are expressed by the subdivisions, the computer-readable code being embedded in said at least one anomalous element, said subdivisions having been created, for each anomalous element of said at least one anomalous element, by adding a new vertex on each existing edge, for a plurality of existing edges, wherein the each existing edge, and wherein the location defines a particular value of the values of the computer-readable code;
and
processing the digital watermark in the computer-readable code,
said receiving, said searching, said reading the computer-readable code, and said processing being performed by one or more computing devices,
wherein the each anomalous element of said at least one anomalous element is associated with a center vertex, and
wherein said reading the values comprises, for the each anomalous element of said at least one anomalous element, successively reading edges that include new vertices that are arrayed around the center vertex, starting with a chosen edge.

10 more elements

A computer-readable storage medium for storing computer-readable instructions, the computer-readable instructions, when executed by one or more hardware processors, performing operations that comprise:

providing a file having a data structure that expresses an original mesh that describes a three-dimensional object, the original mesh having:
a plurality of vertices that have respective locations in the original mesh;
a plurality of edges that connect the vertices together;
and
a plurality of polygonal shapes defined by the vertices and the edges;
searching the data structure for at least one anomalous element in the original mesh, each of which includes a center vertex that is connected to more than a prescribed number of other vertices;
subdividing one or more anomalous elements that are identified so that said one or more anomalous elements collectively express a computer-readable code including a digital watermark, said subdividing producing a modified mesh file, said subdividing comprising subdividing each of said one or more anomalous elements to produce subdivisions that are chosen to collectively encode values of the computer-readable code and further comprising for each anomalous element of the one or more anomalous elements, adding a new vertex on each existing edge, for a plurality of existing edges, wherein the adding comprises choosing a location at which the new vertex is placed on the each existing edge, and wherein the location defines a particular value of the values of the computer-readable code;
and
storing the modified mesh file, the computer-readable code being embedded in said one or more anomalous elements, and being extractable from said one or more anomalous elements by reading the values that are expressed by the subdivisions, said reading the values comprising, for the each anomalous element of the one or more anomalous elements, successively reading edges that include new vertices that are arrayed around the center vertex, starting with a chosen edge.

6 more elements

Dependencies are inferred from the claim text.

Facts

Application: 16/043,199Filed 24 Jul 2018
Published: US 2020/0034944 A130 Jan 2020
Granted: 7 Sep 2021
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

G06T 1/0021
General purpose image data processing: image watermarking
G06T 1/0028
Image watermarking: adaptive watermarking, e.g. Human Visual System [HVS]-based watermarking
G06T 17/20
Three-dimensional [3D] modelling for computer graphics: finite element generation, e.g. wire-frame surface description, tesselation
G06T 2201/0051
Image watermarking: embedding of the watermark in the spatial domain