Reversible data hiding method for multi-histogram point selection based on improved crisscross optimization algorithm

Abstract Traditional prediction error expansion (PEE)-based reversible data hiding (RDH) schemes focus on generating a sharp prediction error histogram (PEH) in order to increase embedding performance, but they neglect the influence of local complexity on embedding performance. When the PEH is partitioned into multiple sub-histograms by means of the local complexity, the embedding performance can be increased by excluding the embedding of data in the sub-histograms located in the texture regions. However, multiple sub-histograms also cause a problem about how to identify the optimal embedding points that can achieve the best visual quality for a given payload. Violent iteration is often used in RDH schemes to traverse all possible values of the embedding points in order to identify the optimal points. Therefore, we conclude that violent iteration is a very time-consuming method and that it leads to unacceptable computational complexity. The traditional multiple sub-histogram methods usually reduce the solution space (i.e., all possible combinations of the embedding points) to decrease the computational complexity. However, the solution that is obtained from the aforementioned methods may significantly deviate from the global optimal solution. Instead of shrinking the solution space by abandoning most solutions, we improve the crisscross optimization algorithm in order to search for the optimal solution in the global solution space. In this paper, the K-means clustering algorithm is used to classify all prediction errors into multiple categories according to the local complexity. Each category would generate a PEH. Subsequently, the problem of selecting the embedding points of multiple sub-histograms is transformed into a typical and multi-choice knapsack problem. The improved crisscross optimization algorithm is used to determine the approximate optimal solution. The experimental results showed that our scheme provided effective performance.