Weighted bipartite graph for locating optimal LSB substitution for secret embedding

Simple least-significant-bit (LSB) substitution is an approach used to embed a secret image in the least significant bits of the pixels in a host image. In order to reduce the degradation of host image after embedding, an optimal LSB substitution scheme was proposed by [9]. Because the exhaustive search for an optimal solution was very time consuming, however, Wang et al. [9] proposed a genetic algorithm to search for approximate optimal solutions. Also, Chang et al. [10] proposed a dynamic programming strategy to efficiently obtain an optimal solution. In this paper, in virtue of efficient algorithm, we propose a new approach to find an optimal solution, which is inspired on the maximum matching of a weighted bipartite graph. Regardless the time required for constructing a weighted bipartite graph, in theory, the time complexity of our approach is O(N 3) only, it is obviously better than the complexity analysis of O(2 N ) in [10], where N is equal to 2 k for k-LSB.