# Collusion Attack Resilient 3D Mesh Watermarking Based on Anti-Collusion Fingerprint Code
## 3 Proposed Method
### Watermark Embedding Algorithm  
The spectrum of a 3D mesh is computed from connectivity and coordinates of vertices of the mesh. Eigenvalue decomposition of a mesh Laplacian matrix is required to produce spectral coefficients. For the Laplacian matrix, we employed a mesh Laplacian matrix proposed by [PERSON] [16], referred to as the Kirchhoff matrix. The Kirchhoff matrix \(\mathbf{K}\) is defined as follows:  
\[\mathbf{K}=\mathbf{D}-\mathbf{A}, \tag{1}\]  
where \(\mathbf{D}\) is a diagonal matrix of which an element is defined by a degree of each vertex, and \(\mathbf{A}\) is an adjacent matrix of the mesh of which elements \(a_{i,j}\) are equal to '1' if vertices \(i\) and \(j\) are adjacent, and otherwise '0'. A mesh \(\mathbb{M}\) with \(m\) vertices produces a Kirchhoff matrix \(\mathbf{K}\) of size \(m\times m\), and its eigenvalue decomposition may be described as follows:  
\[\mathbf{K}=\mathbf{U}\mathbf{\Lambda}\mathbf{U}^{T}, \tag{2}\]  
where \(\mathbf{\Lambda}\) is a diagonal matrix composed of the \(m\) eigenvalues \(\lambda_{i}\) in ascending order, and \(\mathbf{U}\) is a unitary matrix composed of the \(m\)-dimensional normalized eigenvectors.  
The Laplacian eigenvector basis is used to perform an orthogonal decomposition of a function. The spectra of the mesh are obtained by projection of the vector according to the Laplacian basis, as indicated in the following equation.  
\[\mathbf{c}=\mathbf{U}^{T}\mathbf{x}, \tag{3}\]  
where \(\mathbf{c}=(c_{1},c_{2},...,c_{m})^{T}\) is a spectral coefficient of input mesh, and \(\mathbf{x}\) is a vector of the vertices of the mesh.  
We generate a watermark pattern using a 'group-divisible partially balanced incomplete block design' (GD-PBIBD) [26]. Using a generator proposed by [PERSON] et al. [9], the generated code set is defined as an \(N\times R\) binary matrix \(\mathbf{N}\) in which a column represents a unique fingerprint code for each user, and where \(N\) is the length of each fingerprint code. The generated fingerprint code set \(\mathbf{N}\) for \(R=s^{2(p-1)}\) recipients can protect cover work from \(n\) attackers \((s-1)\). Detailed information can be found in [26].  
For the \(u\)-th recipient, we obtain \(u\)-th column vector \(\mathbf{y}^{u}\) from the generated fingerprint code set \(N\). Each binary value '0, 1' from \(\mathbf{y}^{u}\) is encoded into two symbol vectors \(\mathbf{s}_{0},\mathbf{s}_{1}\) with same length \(L\), then we obtain a watermark sequence \(\mathbf{w}\) with length \(N\cdot L\). We use zero value vectors for symbol vector \(\mathbf{s}_{0}\). For symbol vector \(\mathbf{s}_{1}\), we use a pseudo-random sequences with positive values generated by a watermark key. We embed the generated pattern \(\mathbf{w}\) by changing the amplitude of the spectral  
\begin{table}
\begin{tabular}{l c c c c c} \hline \hline
**Algorithms** & [11] & [12] & [23] & [13] & **Ours** \\ \hline Robustness against collusion & _yes_ & _no_ & _yes_ & _no_ & _yes_ \\ \hline Bit capacity for fingerprint code & _undefined_ & \(\leq\)64 bit & \(\approx\)64 bit & \(\leq\)24 bit & \(\leq\)64 bit \\ \hline \hline \end{tabular}
\end{table}
Table 1: A summary of related robust mesh watermarking algorithms.  
coefficient vector \(\mathbf{c}\). First, we determine a frequency band for watermark embedding by selecting a start index \(i_{0}\) of the coefficient vector. The watermarking process is computed using the following equation:  
\[c^{\prime}_{(i+i_{0})}=c_{(i+i_{0})}+\alpha\cdot w_{i}\cdot|c_{(i+i_{0})}|, \tag{4}\]  
where \(1\leq i\leq(N\cdot L)\), and \(\alpha\) is the strength of the watermark \((\alpha>0)\). Here, \(c_{i}\) and \(w_{i}\) denote the \(i\)-th index of \(\mathbf{c}\) and \(\mathbf{w}\), respectively. The watermarked mesh is obtained by combining the Laplacian basis \(\mathbf{U}\) with coefficient \(\mathbf{c}^{\prime}\) as in the following equation.  
\[\mathbf{x}^{\prime}=\mathbf{U}\mathbf{c}^{\prime}, \tag{5}\]  
where \(\mathbf{x}^{\prime}\) is a vector of the reconstructed vertices for the watermarked mesh model.