  Reversible data hiding (RDH) is desirable in applications where both the
hidden message and the cover medium need to be recovered without loss. Among
many RDH approaches is prediction-error expansion (PEE), containing two steps:
i) prediction of a target pixel value, and ii) embedding according to the value
of prediction-error. In general, higher prediction performance leads to larger
embedding capacity and/or lower signal distortion. Leveraging on recent
advances in graph signal processing (GSP), we pose pixel prediction as a
graph-signal restoration problem, where the appropriate edge weights of the
underlying graph are computed using a similar patch searched in a semi-local
neighborhood. Specifically, for each candidate patch, we first examine
eigenvalues of its structure tensor to estimate its local smoothness. If
sufficiently smooth, we pose a maximum a posteriori (MAP) problem using either
a quadratic Laplacian regularizer or a graph total variation (GTV) term as
signal prior. While the MAP problem using the first prior has a closed-form
solution, we design an efficient algorithm for the second prior using
alternating direction method of multipliers (ADMM) with nested proximal
gradient descent. Experimental results show that with better quality GSP-based
prediction, at low capacity the visual quality of the embedded image exceeds
state-of-the-art methods noticeably.
