Geometric-invariant image watermarking by key-dependent triangulation

Informatica, June, 2008 by Shiyan Hu

Fast and massive dissemination of image data across the Internet imposes great challenges of protecting images against illegal access and unauthorized reproduction. Image watermarking provides a powerful solution for intellectual protection. In this paper, a new image watermarking approach robust to various geometric distortions is proposed. The new scheme involves detecting image feature points and triangulating them in a secure key-dependent manner. The neighborhood pixel ratio of gray-scale image is investigated in the paper. It is a novel robust image feature which can be seamlessly combined with the proposed key-dependent triangulation scheme. A random pre-warping framework is adopted to make the scheme robust to collusion attack. Our experiments demonstrate that the new scheme is robust to rotation, scaling, noise addition, JPEG compression, StirMark, shearing transformation, collusion, and other common attacks in both spatial and frequency domain.

Povzetek: Predstavljen je nov postopek za varovanje slik na internetu.

Keywords: image watermarking, geometric invariance, key-dependent triangulation, security, robustness

1 Introduction

Fast and massive dissemination of image data across the Internet imposes great challenges of protecting images against illegal access and unauthorized reproduction. As an effective and efficient solution, image watermarking superimposes a copyright message into a host image before dissemination and then unauthorized reproduction can be recognized by extracting the copyright information. Numerous image watermarking techniques have been proposed in the literature such as [1, 2, 3, 4, 5, 6, 7, 8]. Along with the rapid growth of novel watermarking schemes, various attacking attempts have also been developed to destroy watermarks. Among these attacks, geometric attacks are very difficult to handle. This is mainly due to the fact that slight geometric manipulation to the marked image, such as scaling or rotation, could significantly reduce the possibility of a successful watermark retrieval, provided that the watermarking extractor has no knowledge of the distortion parameters. In another word, geometric distortion can easily introduce synchronization errors into the watermark extracting process [9, 10]. In recent years, a number of approaches have been proposed to counteract the geometric synchronization attacks. Popular techniques in the literature can be loosely classified into three categories:

1. Geometric invariant domain based watermarking schemes. In these algorithms, Fourier-Mellin transform is incorporated into some watermarking schemes (e.g., [11, 12]) to tackle with geometric attacks such as rotation, scaling and translation. However, these algorithms are computationally inefficient, hard to implement and cannot survive aspect ratio change [13].

2. Template Matching-based watermarking schemes. In this class of algorithms, a template is embedded into the host image besides the watermark. The affine geometric distortions to the marked image can be reverted using the estimated parameters through detecting the template. After compensating geometric distortions, the watermark can be easily retrieved by the watermarking extractor. The major drawbacks of these techniques are that the template can be easily detected and removed by attackers [10, 14, 15].

3. Content-based watermarking schemes. This class of watermarking schemes achieve recovery from geometric distortion using image content. A particular interesting scheme in this category is proposed in [15] where feature points are used as a content descriptor. The method works as follows. First a set of feature points which are robust to geometric distortion are detected. These points are often near corners or edges of the image. A Delaunay triangulation is computed on the feature points and the watermark is then embedded into the resulting triangles. The above technique has two drawbacks. First, it always computes a Delaunay triangulation on the feature points. Therefore, provided that an attacker can successfully retrieve those feature points, the presence of a watermark can be easily determined and the watermark may be removed or distorted. Since usually well-known feature-point detectors (e.g., Harris detector [16]) are adopted, most feature points can actually be found by attackers. Second, the method is not as robust as expected: feature points are robust (i.e., can be completely retrieved by the watermarking extractor) only against small-degree rotation, and the performance of these techniques is considerably compromised when large-degree rotation occurs. This drawback has also been reported in [15, 17].

In this paper, we propose a new feature point-based image watermarking algorithm which is secure and robust to common attacks in both spatial and frequency domain. The proposed scheme first generates four image feature points using a novel robust intersection-based feature point detector. Based on the feature points, a number of additional points are generated and then triangulated in a key-dependent manner. Finally, the watermark is embedded into the resulting triangles. The key dependance properties of the proposed technique is motivated by the following results from the computational geometry literature. It is shown in [18] that there exist [OMEGA](2.33n) different triangulations for a planar set of n points in general position. Therefore, even if attackers repeat the feature points, they are generally not able to compute the right triangulation. We also consider the application of the proposed watermarking scheme to image fingerprinting. Under this situation, robustness against collusion attacks becomes critical. Therefore, a random pre-warping framework is adopted to make the proposed scheme robust against such attacks.