# A Robust and Secure Watermarking Approach Based on Hermite Transform and SVD-DCT
## 3 Materials and Methods
### Jigsaw Transform and Cellular Automata
#### 3.2.2 Elementary Cellular Automata  
Elementary Cellular Automata consist of a grid of cells of width \(X\) and height \(Y\). Each cell has two possible states: ON and OFF. Initially, all cells start turned OFF, except for the first row, which has an arbitrary configuration. The grid will evolve through a series of iterations. In iteration \(i\), the \(i+1\)th row is modified. The new value of a cell is determined by the neighborhood of the cell in the same column in the row above (the parent row). The neighborhood of a cell consists of three cells: the cell itself and its two horizontal neighbors (handling the edge cases with modular arithmetic). Therefore, there are \(2^{3}=8\) possible neighborhoods and, consequently, \(2^{8}=256\) possible rules for the next iteration of the automaton. In this paper, we focused on the rule known as Rule 105 according to the Wolfram code described in [44] to classify the rules of the ECA, depicted in Figure 4.  
Figure 3: Examples of the JST using an image grayscale image of \(512\times 512\) px. (**a**) _Barbara_ image. (**b**) JST result using blocks of \(64\times 64\) (\(\mathcal{M}=64\)). (**c**) JST result using blocks of \(32\times 32\) (\(\mathcal{M}=256\)). (**d**) JST result using blocks of \(8\times 8\) (\(\mathcal{M}=4096\)).  
For the purposes of our work, we considered a variant of the ECA, where cells can have values ranging from 0 to an integer \(k\), and instead of using Rule 105 to determine if a cell should be ON or OFF, we used it to determine if a cell should increase its value by an odd number \(n\) or not (changing its parity) based on the parity of the values of the corresponding neighborhood, considering even cells as OFF states and odd cells as ON states. If the new value is greater than \(k\), we made use of modular arithmetic to return it to our desired range of values. We also considered a finite grid in the vertical direction; if we performed a number of iterations greater than the amount of rows and we ran out of rows to modify, we continued with the top row considering the bottom row as its parent row. This allowed us to start the first iteration in the first row and to easily apply elementary cellular automata to the gray images. In Figure 5, we show this variation of Rule 105 on a gray image. The process is reversible by applying the algorithm to the rows in reverse order and subtracting by \(k\). The exact size of the key space of our ECA is unknown; its upper bound must be \(Y\times k^{X\times Y}\) since that is the total amount of configurations the matrix could have considering all possible values of the matrix and all possible rows that can be modified in a given iteration of the automaton. Evolving the ECA beyond that amount of iterations would lead to a repeated state. Since it is likely that a repeated state will occur before that amount of iterations, the key space of our ECA was \(K_{CA}\leq Y\times k^{X\times Y}\).  
Figure 4: Elementary cellular automaton with Rule 105. (**a**) The new state of a cell is based on each possible neighborhood of the cell in the same column in its parent row. (**b**) ECA is applied on a \(50\times 51\) grid using 34 iterations, with the first row starting with all cells in the OFF state, except for the cell at the center.  
Figure 5: Variation of the ECA with Rule 105. (**a**) Increment on the value of a cell based on each possible neighborhood of the cell in the same column in its parent row. (**b**) Our modified ECA was applied on a \(128\times 128\) gray image using 80 iterations, with \(k=157\).