Reversible binary image watermarking method using overlapping pattern substitution

This paper presents an overlapping pattern substitution (PS) method. The original overlapping PS method as a reversible data hiding scheme works well with only four pattern pairs among fifteen possible such pairs. This paper generalizes the original PS method so that it will work well with an optimal pair from among the fifteen possible pattern pairs. To implement such an overlapping PS method, changeable and embeddable patterns are first defined. A class map is virtually constructed to identify the changeable and embeddable pairs. The run-lengths between consecutive least probable patterns are recorded. Experiments show that an implementation of our overlapping PS method works well with any possible type of pairs. Comparison results show that the proposed method achieves more embedding capacity, a higher PSNR value, and less human visual distortion for a given embedding payload.