Abstract: In order to embed a high capacity of the watermarks into a 3D mesh model, this paper proposes
a novel semi-blind watermark algorithm based on Tutte Laplacian eigenvectors. In the process of
embedding watermarks, it first computes the Tutte Laplacian matrix and then obtains eigenvectors of the
matrix. A watermark is then embedded into these eigenvectors. To reduce the distortion of the embedded
models, we formulate the selection of entries of the eigenvector matrix to be modified as an optimization
issue and then design a heuristic method to solve the problem. During the extraction process, we detect the
watermark information by using the modified eigenvectors minus the corresponding eigenvectors calculated
from the watermarked model. As for models with large number of vertices, the spectral cluster algorithm is
used by cutting those mesh models into sub-meshes. The watermark is repeatedly embedded into each
sub-mesh. The proposed method can semi-blindly detect the watermark in the sense that it doesn’t need the
original model in the extracting process. The experimental results show that the proposed method can not
only resist attacks such as affine transformation, random additive noise, mesh smoothing, uniform
quantization as well as cropping but also outperform state-of-the-art approaches in embedding capacity.

Key words: 3D mesh models, digital watermark, Tutte Laplacian, eigenvalue decomposition