Invertible embedding allows the original cover and embedded data to be perfectly reconstructed. Conventional methods use a well-designed predictor and fully exploit the carrier characteristics. Due to the diversity, it is actually hard to accurately model arbitrary covers, which limits the practical use of methods relying heavily on content characteristics. It has motivated us to revisit invertible embedding operations and propose a general graph matching model to generalize them and further reduce the embedding distortion. In the model, the rate-distortion optimization task of invertible embedding is derived as a weighted bipartite graph matching problem. In the bipartite graph, the nodes represent the values of cover elements, and the edges indicate the candidate modifications. Each edge is associated with a weight indicating the corresponding embedding distortion for the connected nodes. By solving the minimum weight maximum matching problem, we can find the optimal embedding strategy under the constraint. Since the proposed work is a general model, it can be incorporated into existing works to improve their performance, or used for designing new invertible embedding systems. We incorporate the proposed work into a part of state-of-the-arts, and experiments show that it significantly improves the rate-distortion performance. To the best knowledge of the authors, it is probably the first work studying rate-distortion optimization of invertible embedding from the perspective of graph matching model.
In this paper, we introduce a new and novel graph-theoretic steganographic approach applicable to online social networking services (SNSs). The proposed approach translates a secret message to be embedded as an undirected graph called messagegraph, the structural information of which is concealed within a new directed graph. The new directed graph is released in a SNS platform by producing a sequence of ordered multiple-user interaction events. To secure communication, we propose to split a specific vertex to multiple copies and insert new vertices and edges to the directed graph. A receiver is able to reconstruct the directed graph from observations. Both the message-graph and the secret message can be orderly retrieved without error. It is probably the first work deeply focusing on the practical design of interaction based steganography using graph-theoretic approach.