Reversible data hiding for binary images based on adaptive overlapping pattern

Pattern substitution (PS) method (Ho et al., Comput. Stand. Interfaces 31:787–794, 2009) is a recent reversible data hiding method for binary images. It generates one pattern pair, the patterns in which are called PM and PF, and substitutes between them to embed one bit. Two types of PS have been proposed: non-overlapping PS and overlapping PS. However, Dong et al. (ETRI J. 37:990–1000, 2015) states that the overlapping PS sometimes cannot decode correctly, which is called as miscoding problem. Moreover, to the PS-based methods (Ho et al., Comput. Stand. Interfaces 31:787–794, 2009; Dong et al., ETRI J. 37:990–1000, 2015; Dong et al., Lect. Notes Comput. Sci. 6526:3516–3522, 2011), although chosen of two patterns to form the pattern pair which relates the embedding performance much, the previous methods only use a fixed pattern pair during the whole data hiding process. In order to overcome these two shortcomings, this paper proposes an adaptive overlapping PS method. Firstly, two modes of the embedding are proposed so that the miscoding problem can be solved. Secondly, one window which contains the context of current processing pixel is generated and updated when the process proceeds to the next pixel. Thus, the optimum pair of the local context for embedding can be chosen. Thirdly, in order to get a smaller location map, a three-round embedding mechanism is also proposed. With these three improvements, our method can embed larger payloads with less distortion than the previous works.