# Fragile Watermarking of 3D Models in a Transformed Domain
## 3 The Karhunen-Loeve Transform  
The discrete Karhunen-Loeve Transform (KLT) (also called Hotelling transform or Principal Component Analysis (PCA)) is a linear transformation that maps vectors from one \(n\)-dimensional vector space to another vector space of the same dimension: this mapping is defined by a square matrix of size \(n\times n\), called the kernel.  
Differently from other linear transformations like the discrete cosine transform or the Fourier transform, one of the characteristics of the KLT is having a kernel that is not fixed a priori, i.e., its transformation matrix is computed from a set of vectors that must be given to define the mapping.  
This characteristic of the KLT is exploited in the present algorithm to have a compact, secure, and efficient way to define a secret space of embedding: if the set of vectors used in computing the KLT kernel is kept secret, then also the kernel will be secret, defining a transformed domain in which to embed the watermark securely; for example, using a secret image's pixel values to define these vectors, then only the entities possessing this image will be able to verify the integrity of the 3D model. Moreover, lacking knowledge of the embedding space does not allow modifying the 3D model without altering the fragile watermark.  
Consider a set of vectors \(\{\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{r}\}\) of an \(n\)-dimensional vector space, and compute their mean vector \(\mathbf{m}=E\{\mathbf{x}_{i}\}\). Then, evaluate the covariance matrix of the centered vectors \(\mathbf{C}=E\{\left(\mathbf{x}_{i}-\mathbf{m}\right)\left(\mathbf{x}_{i}- \mathbf{m}\right)^{\prime}\}\), where \(\mathbf{z}^{\prime}\) represents the conjugate transpose of \(\mathbf{z}\). The eigenvectors \(\mathbf{e}_{i},i=1,2,\ldots,n\), of the covariance matrix \(\mathbf{C}\), computed as:  
\[\mathbf{C}\mathbf{e}_{i}=\lambda_{i}\mathbf{e}_{i} \tag{1}\]  
define an orthonormal basis for the \(n\)-dimensional vector space; the \(\lambda_{i}\)s are the associated eigenvalues. Thus, arranging the eigenvectors as rows of a matrix \(\mathbf{A}\) in descending sort order of the respective eigenvalues, the KLT \(\mathbf{y}\) of a vector \(\mathbf{x}\) is computed as:  
\[\mathbf{y}=\mathbf{A}(\mathbf{x}-\mathbf{m}). \tag{2}\]  
Each element of the vector \(\mathbf{y}\) is called the coefficient of the transform; the position of every coefficient in the vector \(\mathbf{y}\) is called the order of the coefficient.  
It is possible to reverse the transformation process through the inverse KLT:  
\[\mathbf{x}=\mathbf{A}^{-1}\mathbf{y}+\mathbf{m} \tag{3}\]  
which, by the orthonormality of \(\mathbf{A}\), may be also written as:  
\[\mathbf{x}=\mathbf{A}^{\prime}\mathbf{y}+\mathbf{m}. \tag{4}\]  
One property of the eigenvectors is that they define the directions of maximum data spread in the data sample, and sorting them according to their associated eigenvalues allows exploiting the energy compaction property of the KLT transform, useful when expressing the elements of the vector space with a reduced number of coefficients: it may be shown that the eigenvalues represent the variance of the coefficients in each dimension.  
For more details on the KLT, see [21].