## 4 Proposal
### Tiling with Unequal Patches  
Watermarking methods that partition the image into square patches use identical non-overlapping patches of predetermined size. In this work, we used a tiling with square patches of different sizes, in order to take advantage of the different correlation levels in various areas of the image. To keep the complexity of the tiling under control, edges of the (composite) patches are constrained to be multiples of a _basic patch_ of \(B\)-by-\(B\) pixels. The value of \(B\) can be predetermined (e.g., 8 pixels, a value widely used in image compression) or set in accordance with the properties of the specific images considered in an application.  
The tessellation is obtained by means of a greedy algorithm that considers basic patches one at a time, in a prefixed order. Basic patches are scanned in row-wise order, starting from the upper left corner. For each basic patch considered, the tessellation algorithm evaluates if the patch should be kept as is, or if it should be integrated in a composite square patch. In our framework, the decision is based on the combination of two functions:  
* A _quality function_\(\psi(p)\) that determines if it is convenient to expand a patch \(p\) including its western, southwestern, and southern neighbors. The quality function can be a general measure of the spatial correlation among pixels or of the entropy, or a pixel value prediction method such as, for example, Checkerboard Based Prediction (CBP) [25]. An alternative idea that can be used when the actual embedding function is computationally light is to actually apply it to the patches separately and to the combined patch, comparing the relative gain/loss. Clearly, storing partial results speeds the computation up.
* A _penalty function_\(\xi(p)\) accounting for constraints that a bigger patch imposes over adjacent patches. Figure 1 shows, for example, that a 3-by-3 patch (labeled as \(c\)) constrains the two basic patches labeled \(a\) and \(b\) to be considered as basic patches only. As penalty function, we used a count of the basic patches that were deprived from the opportunity of being expanded: \[\xi(p)=\#(\text{constrained basic patches})\]  
The final scoring function \(\omega(p)\) is given by  
\[\omega(p)=\frac{\psi(p)}{Q+\xi(p)}\]  
where \(Q\) is a parameter controlling the weight of the penalty function. Low values for \(Q\) will enlarge the impact of small increases of \(\xi(p)\). Within a patch, an efficient embedding algorithm with low  
Figure 1: The 3 \(\times\) 3 patch \(c\) constraints patches \(a\) and \(b\) to be 1 \(\times\) 1.  
distortion and high payload is used. While our system can handle all algorithms that can operate locally (which include the vast majority of embedding algorithms), in our preliminary experiments we used the embedding algorithm based on the Slantlet transform [26]. The slantlet transform has been shown to outperform the Discrete Wavelet Transform (DWT) as far as the compromise between smoothness and localization is concerned, making it a strong candidate for transform-based embedding.  
In order to describe the tessellation with sufficient detail to allow reconstruction on the receiving side, information regarding the tessellation should be embedded in the image as well. When a patch \(p_{i}\) is considered, the position of next basic patch in the sequence can obviously be determined, given the size of \(p\). Once the next patch \(p_{i+1}\) is determined, its edge size \(s_{i+1}\) is embedded as auxiliary information in patch \(p_{i}\). Note that the size of the initial patch is embedded at last using a generic RDH algorithm. It will be extracted as a preliminary operation during recovery. Recovery should proceed in the same order as embedding. Edge sizes will typically be small integers, thus requiring a small number of bits. In addition, a limit can be easily imposed the maximum patch size (e.g., 4) so that the number of bits needed to encode \(s_{i+1}\) will be known in advance.