Random matching pursuit for image watermarking

The classical solution to an underdetermined system of linear equations mainly has two opposite directions, which lead to either a large ℓ2-norm sparse solution or a non-sparse minimum ℓ2-norm solution. In this paper, we systematically show that by modifying the well known basic matching pursuit (BMP) algorithm originally proposed to identify the sparse solution, an alternative solution between the two classical ones could be obtained. The modified algorithm, termed as random matching pursuit (RMP), is then used to create a novel image watermarking framework. Compared to conventional systems, the security is substantially improved by the use of random over-complete dictionaries and the order parameter of RMP. Capacity can also be increased thanks to the transform with over-complete dictionaries that could expand signal dimension. Meanwhile, imperceptibility and robustness properties of the proposed design framework are not compromised. The classical spread spectrum (SS) and improved spread spectrum (ISS) techniques are applied to the proposed framework for practical implementations. The novelty and effectiveness of the proposed systems are supported by rigorous performance analysis and experimental results using an image dataset. This paper reveals the potential of using over-complete dictionaries in multimedia watermarking systems, which theoretically leads to the exploration of alternative candidates among the infinite solutions to underdetermined linear systems other than minimum ℓ2-norm and sparse ones.