# A Large Capacity Histogram-Based Watermarking Algorithm for Three Consecutive Bins
## 1 Introduction  
With the rapid growth of popular and low-cost access to image editing applications, some intentional or unintentional manipulations of digital media during transmission are becoming available [1; 2]. This will bring a troublesome issue for copyright protection and authentication since these illegally-manipulated copies of digital media may be easily redistributed and transmitted. Robust watermarking [3] is the technique that embeds information in the image to provide authentication, copyright protection, copy control, etc. The objective of earlier research works of robust watermarking was primarily to realize the capability to resist common image processing operations [4], while recent research works have been prone to emphasizing the functions of resisting geometric attacks [5; 6; 7; 8; 9; 10; 11; 12]. Geometric attacks primarily introduce some synchronization errors between the encoder and the decoder. Under geometric attacks, the watermark is still present, whereas the detector is no longer able to extract it. Therefore, how to design a watermarking algorithm robust to geometric attacks has become indispensable and vital in the digital watermarking field. A variety of watermarking-related methods has been proposed so far, and they can be classified into three categories: inverse transformation based [5; 6; 7], geometric invariance domain based [8; 9; 10], and feature area embedding based [11; 12]. Inverse transformation-based methods mainly exploit exhaustive search [5] and the embedding template, in addition to the watermark [6] to resist geometric attacks. The implementations of geometric invariance domain-based methods need to usethe mathematical transform on the input image before embedding and extracting procedures, like the image normalization method [9] and Zernike moments [10]. Feature area embedding-based methods extract feature points [11] or salient points such as the eyes and the mouth [12] firstly and then embed the watermark in them. Among various categories, geometric invariance domain-based methods are usually vulnerable to cropping attacks; in contrast, feature area-based methods can provide better robustness. However, all the above schemes, both the earlier and recent schemes robust to geometric attacks, are not fully satisfied. On the one hand, these schemes suffer from computational efficiency problems in the watermark embedding and extracting procedure. On the other hand, these schemes cannot efficiently implement watermark robustness to some geometric attacks, such as random bending attacks (RBAs) and random cropping. It is well known that in an image that has undergone geometric attacks, there may occur three different changes: pixel position, pixel value, and pixel number. In this case, the positions or values of some pixels may be modified; even the number of pixels may be decreased or increased linearly (scaling the size of the image). Based on the analysis, [PERSON] et al. [13] developed an invariant watermarking solution to geometric attacks by using the histogram and the mean. In their method, the histogram shape was used to embed the watermark based on the property that the histogram shape is only related to the pixel count of each grayscale, not the position of pixels. Nevertheless, there exist some issues in [PERSON] et al. 's method [13]: (1) randomly selecting pixels to modify may bring a relatively weak robustness to JPEG compression; (2) the visual quality of some smooth areas in an image will seriously reduce with the increase of the bins' size; (3) bad bins may exist (the occurrence frequencies of pixels in these bins are zero or few). To solve the first problem, [PERSON] et al. [14] used a novel pixel modification method, i.e., mean squared error (MSE), to choose some blocks to modify preferably. The second issue can be resolved by the methods of [14; 15; 16].