FIELD OF THE INVENTION

The present invention relates to a method of authenticating data content. Particularly, but not exclusively the invention relates to a method of authenticating watermarked media content and a method of indexing media content.

BACKGROUND OF THE INVENTION

Watermarking is a technique that is regularly used in copyright protection to determine the ownership or media data content or to detect the origin of physical or electronic media that has been illegally redistributed. The technique involves embedding auxiliary identification information indicating ownership or customer ID into media data content in the form of a media signal before the media data content is distributed. Generally the embedded watermark is in the form of machine readable code and should be invisible and unobtrusive and not interfere with the protected media content. The media content may be image, video or audio data. It may also include other types of media objects including documents, software, multidimensional graphics models and surface textures of objects. For example, referring to Figure 1a a media content provider distributes media content such as a television program to a number of customers. One of the customers then redistributes his copy to others via the internet. The problem is then how to determine if the media data content which has been subsequently detected originates from that content provider. The next problem involves determining which customer was responsible for redistributing the media data content over the Internet.

JP2004112318, for example, describes a watermarking based image protection method in which the ownership information is embedded into images before they are distributed. By detecting whether or not the watermark exists in an image or not, the copyright of the image distributed over Internet can be authenticated. However, considering that operations such as compression, rotation, shearing, scaling, translation, and the like are often performed on the images successfully detecting the watermark in the operated images is becoming increasingly difficult. Prior art techniques suffer the drawback that embedded watermark are often not robust to such geometrical transformations or desynchronisation operations. Another requirement in media content distribution is content indexing. Content indexing refers to the finding specific data files from within a number of data files stored in a database.

FR2843212 describes a content index method based on image feature extraction and matching. In the described method, a feature of an image is extracted and compared with the features extracted from images stored in a database or with features directly stored in a database, to find one or more matching images. For media related services, often both content index and copyright protection are required. Currently the two functionalities are performed independently

SUMMARY OF THE INVENTION

Accordingly, it would be advantageous to provide a method of authenticating content data which implements both a copyright protection technique and a content indexing functionality. It would also be desirable to provide a method of authenticating data content with improved robustness to desynchronisation operations.

To better address one or more of the foregoing concerns, in accordance with a first aspect of the invention there is provided a method of watermarking data content for distribution, the method comprising: embedding auxiliary identification information in a data content; extracting a feature from the data content embedded with the auxiliary identification information; storing the extracted feature in a feature database, the extracted feature being associated with identification data identifying the data content from which the feature has been extracted, wherein the extracted feature stored in the feature database is usable to identify a detected data content and to determine operation parameters for rectifying the detected data content such that auxiliary identification information is extractable therefrom for authentication of the detected data content.

By a method of watermarking is meant a method in which auxiliary data in embedded in a data content for authentication or identification purposes. The auxiliary identification information may be a digital watermark. The data content may be a digital media content such as image, audio or video data. The feature may be a feature or a group of features.

The extracted feature may be a corner point based feature. Such features are more robust to desynchronisation operations.

The auxiliary identification information may be embedded into the wavelet domain of the data content. For example embedding the auxiliary identification information may include transforming the data content by wavelet transformation to obtain sub-bands r ^s where re{0,1 ,2,3} is the resolution level, and se{LL,LH,HL,HH} is the orientation; and wherein the auxiliary information is embedded into the sub-bands according to the expression:

ot ^S h ^≠ er ^L w ^L ise where α represents the embedding strength where (0< α< 1); l + aw _t > 0 ).

Preferably re{2,3} in order to provide a more robust auxiliary identification information.

A second aspect of the invention provides a method of authenticating data content the method comprising extracting a feature from a data content; comparing the extracted feature with a plurality of features stored in a feature database in order to determine at least one matching feature from the plurality of stored features wherein each of the stored features has been extracted from a corresponding data content embedded with auxiliary identification information prior to distribution of said data content; determining a transform relationship between the extracted feature and the matching feature; rectifying the data content according to the determined transform relationship; and extracting auxiliary identification information from the rectified data content so that the auxiliary identification information is usable for authentication of the data content. Matching the extracted feature with the matching feature may comprise determining the difference Dist (F ₁ F') between the extracted Feature F' and a matching feature F ₁ according to the expression

and comparing Dist (F ₁ F') to a predetermined feature matching threshold T _F .

Determining a transform relationship between the extracted feature and the matching feature may include determining a transformation according to:

where, (x',y') and (x,y) correspond to the corner point coordinates of the extracted feature F' and the matching feature F _k , respectively.

The data content may be rectified or emended by rectifying a pixel position (x',y') in the data content according to:

dx' - ay' - cd + af y _k = bd - ae

where, (x' _k .y' _k ) is the corresponding pixel position in the rectified data content.

Authentication of the auxiliary information may include computing a correlation value for correlating the extracted auxiliary information to a known auxiliary information according to the expression computing a threshold according to

and determining if p≤T to authenticate the auxiliary information.

A third aspect of the invention provides an apparatus for embedding authentication information in data content for distribution, the apparatus comprising: an embedder for embedding auxiliary identification information in a data content; a feature extractor for extracting a feature from the data content embedded with the auxiliary identification information; a feature database for storing the extracted feature , the extracted feature being associated with identification data identifying the data content from which the feature has been extracted, wherein the extracted feature stored in the feature database is usable to identify a detected data content and to determine operation parameters for rectifying the detected data content such that auxiliary identification data is extractable therefrom for authentication of the detected data content.

The feature extractor may be operable to extract a corner point based feature from the data content embedded with the auxiliary identification information.

A fourth aspect of the invention provides an apparatus for authenticating data content the apparatus comprising a feature extractor for extracting a feature from a data content; a processor for comparing the extracted feature with a plurality of features stored in a feature database in order to determine at least one matching feature from the plurality of stored features wherein each of the stored features has been extracted from a corresponding data content embedded with auxiliary identification information prior to distribution of said data content; determining a transform relationship between the extracted feature and the matching feature; and rectifying the data content according to determined transform relationship; the apparatus further comprising an extractor for extracting auxiliary identification information from the rectified data content so that the auxiliary identification information is usable for authentication of the data content.

A fifth aspect of the invention provides an method of data content authentication comprising, prior to distribution of a first data content, embedding auxiliary identification information in the first data content; extracting a first feature from the first data content embedded with the auxiliary identification information; storing the extracted first feature in a feature database, the extracted first feature being associated with identification data identifying the first data content from which the first feature has been extracted, and distributing the first data content; and on detection of a second data content after distribution, extracting a second feature from the second data content; comparing the second feature with the first feature stored in the feature database in order to determine if the second feature matches the first feature; and if it is determined that the second feature matches the first feature determining a transform relationship between the second feature and the first feature; rectifying the second data content according to the determined transform relationship; and extracting auxiliary identification information from the rectified second data content so that the auxiliary identification information is usable for authentication of the second data content.

A sixth aspect of the invention provides a system for authenticating data content, the system comprising an embedder for embedding auxiliary identification information in a data content; a first feature extractor for extracting a first feature from the data content embedded with the auxiliary identification information; a feature database for storing the extracted feature , the extracted feature being associated with identification data identifying the data content from which the feature has been extracted, a second feature extractor for extracting a second feature from distributed data content; a processor for comparing the second feature with the first feature stored in the feature database in order to determine if the second feature matches the first feature; and if it is determined that the second feature matches the first feature the processor being operable to determine a transform relationship between the second feature and the first feature; rectifying the second data content according to the determined transform relationship; and a watermark extractor for extracting auxiliary identification information from the rectified second data content so that the auxiliary identification information is usable for authentication of the second data content. The first feature extractor and the second feature extractor may be the same feature extractor or separate feature extractors.

Aspects of the invention provide a mechanism which combines both copyright protection and media content index since a feature extracted from watermarked media content can be used for media content indexing in a database as well as for rectifying a watermarked media content, which has been detected after distribution, for media content authentication. Moreover, the extracted feature stored in the feature database improves the watermarking algorithm's robustness. Since the data content is emended or rectified according to the determined transformation undergone by the feature extracted from the data content, a watermark can thereby be extracted from the rectified or emended data content and thus used for authentication purposes.

The methods according to the invention may be computer implemented. The methods may be implemented in software on a programmable apparatus. They may also be implemented solely in hardware or in software, or in a combination thereof.

Since the present invention can be implemented in software, the present invention can be embodied as computer readable code for provision to a programmable apparatus on any suitable carrier medium. A tangible carrier medium may comprise a storage medium such as a floppy disk, a CD-ROM, a hard disk drive, a magnetic tape device or a solid state memory device and the like. A transient carrier medium may include a signal such as an electrical signal, an electronic signal, an optical signal, an acoustic signal, a magnetic signal or an electromagnetic signal, e.g. a microwave or RF signal.

BRIEF DESCRIPTION OF THE DRAWINGS

Embodiments of the invention will now be described, by way of example only, and with reference to the following drawings in which:-

Figure 1 A is a schematic view of a media content being distributed to the public;

Figure 1 B is a flow chart illustrating a method of authenticating media content according to the prior art;

Figure 2A is a flowchart illustrating a method of embedding a watermark in media content according to an embodiment of the invention;

Figure 2B is a flowchart illustrating a method of authenticating media content according to an embodiment of the invention;

Figure 3A is a flowchart illustrating a method of embedding a watermark in media content according to a particular embodiment of the invention;

Figure 3B is a flowchart illustrating a method of authenticating media content according to a particular embodiment of the invention;

Figure 4 is an example of an image highlighting corner features;

Figure 5 is an example of an original image and corresponding operated images;

Figure 6A is a graphical illustration of an example of corner point matching between features in an original image and features in a rotated original image;

Figure 6B is a graphical illustration of watermark detection with watermark correlation and threshold; and Figure 7 is a table illustrates the example of the results of a robustness test under the conditions of various attacks.

DETAILED DESCRIPTION

A method of authenticating content data according to an embodiment of the invention will be described with reference to Figures 2A to 4B.

With reference to Figures 2 and 3, the method of authenticating content data includes five principal steps:

^■ media watermark embedding;

^■ robust feature extraction and registration;

^■ media distribution; ■ watermark extraction and authentication; and

^■ media indexing.

Referring to Figure 2A step S1 of the method according to the first embodiment of the invention comprises embedding a watermark W into media data content P under the control of a key K to generate watermarked media C. Key K controls the watermark embedding position or parameters. In this embodiment of the invention, the watermark W represents the ownership information or customer ID. The embedding method may be performed according to existing watermarking algorithms such as, for example, those descried in documents Cox et al.: Secure Spread Spectrum Watermarking for Multimedia. IEEE Trans, on Image Processing, Vol. 6, No. 12.

(1997) 1673-1687, or Cheng et al.: Optimum Detection and Decoding of Multiplicative Watermarks in DFT Domain. Proceedings of IEEE International Conference on Acoustics, Speech and Processing, Vol. 4. (2002) 3477-3480. Preferably, a method which is more robust to robust to general attacks such as the method described in Cheng et al. An Additive Approach to Transform-Domain Information Hiding and Optimum Detection Structure. IEEE Transactions on Multimedia, Vol. 3, No. 3, pp. 273-284, 2001 , is implemented. These watermarking algorithms embed a watermark into the spatial domain or frequency domain of image, video or audio content data. Such algorithms are often robust to general attacks such as adding noise, compression, A/D or D/A conversion, filtering, etc.

In step S2 a feature F is extracted from the watermarked media C and in step S3 stored and registered in a feature database D having a size M. In the feature database D, the feature F is associated with data representing the watermarked media content C from which it has been extracted. An example of a data structure of the feature database is shown in Table 1.

Table 1 : Example of a data structure of the feature database

In Table 1 , the first column represents the names of media signals, for example, Lena is the name of an image. And the second column represents the features which are extracted from the media signals, for example, F ₀ is extracted from the signal named Lena.

The feature F should satisfy two requirements: firstly, feature F should be robust to watermarking attacks, such as general geometrical attacks including rotation, shearing, translation, scaling, etc operations. Secondly, feature F should be usable in media indexing and be of a smaller data volume compared to the media data content itself. A feature as such as corner point, boundary, edge, histogram, may, for example, be used to this end.

In step S4 the watermarked media is distributed to a number N of customers by means such as broadcasting, multicasting, unicasting, etc. Some customers may directly distribute the received media over Internet, or distribute it after operations such as recompression, scaling, translation, etc have been performed on the watermarked media content C. This distributed media content represented as C may then be distributed freely from one person to another.

Authentication of detected media content will now be described with reference to Figure 2B. If media content C is subsequently detected the steps of authentication of the detected media content are carried out. In step S6 a watermark W is extracted from the detected media content C and compared in step S7 with the original watermark W. In this embodiment the watermark extraction method is symmetric to the watermark embedding method of step S1. If the difference |W'-W| between the original watermark W and the extracted watermark W is less than Tw where Tw corresponds to a predetermined watermark matching threshold, then the watermark W is authenticated, the media content C is deemed as being copyright protected, and the authentication process terminates. From the identification of W matching W the origin of the detected media content C may be determined, as well as the identity of the customer to whom that media content C was distributed to.

If |W'-W| >T then the process continues to step S8 where a feature F' is extracted from the detected media content C. In step S9 the extracted feature F' is compared with features F, stored in the feature database D. The results from the comparison provide the n (1≤n<M) most matched features (Fo, F-i, ... ,F _n- i) where M is the number of features F, stored in the feature database D. The matching algorithm is based on the comparison |F'- FJ between the extracted feature F' and the stored feature F, where i=0,1 ,...,n-1 and T _F where Tp corresponds to a predetermined feature comparison threshold. If the difference |F'- F,| between the extracted feature F' and the stored feature F, is less than T _F , i.e. |F'- F,| <T _F , the feature F ₁ is deemed to be a matching feature. Otherwise, the feature F, is not deemed to be matched.

The n media contents associated with the n features correspond to the matching index results. From the n indexed features, each pair of matching features (F', F ₁ ) (i=0,1 ,...,n-1) is used to compute the transformation from F, to F' caused by attack operations, by for example comer matching, and the determined transformation is then used accordingly to rectify or emend the media content from C to C" in step S10. For example, if F, is different to F in terms of rotation angle, then C is inverse rotated by the same angle in order to provide the original watermarked media content. From the rectified media C", a watermark W" can be extracted in step S11 and compared with the original watermark W in step S12. If the difference |W'-W| between the extracted watermark W and the original watermark W is less than Tw, i.e. |W'-W| < Tw then the watermark W is deemed to exist in the detected media content, and the media content is deemed to be copyright protected. The authentication process then terminates. Otherwise, steps S8 to S10 are repeated feature by feature F ₁ until i=n or the original watermark W is detected. From the identification of W the origin of the detected media content C may be determined, as well as the identity of the customer to whom that media content C was distributed to

In step S5 of Figure 2A the media index created using the registered Features F ₁ is used to find the original media content C corresponding to C from feature database D. When robust feature F' is extracted from the received media C in step S7 and matched with the feature database D in step S9 of the feature extraction process the matching result gives the n (1<n<M) most matched features (F ₀ , F-i, ... ,F _n- i). The n media contents corresponding to the respective n features constitute the index results.

In a particular embodiment of the invention a corner point is used as the extracted feature. An image ownership protection and index method using corner point features is illustrated in Fig. 3A, which depicts the process of watermark embedding and Figure 3B which illustrates the feature extraction process, the watermark extraction and the authentication processes.

With reference to Figure 3A the watermark embedding and feature extraction process according to this particular embodiment of the invention includes an initial step S21 in which the original media content which in this embodiment comprises an image P, a watermark W and a key K are initialized. In this particular embodiment, the watermark W to be embedded in the image P, is a Gaussian sequence W=[Wo, Wi,...,w _m .i]. In step S22 watermark W is embedded into the wavelet domain of image P under the control of key K, resulting in watermarked media C. In this embodiment, key K controls the permutation of the watermark W. A permutation method based on pseudorandom numbers or a chaotic map may be used. In the watermark embedding step S22, the image P is firstly transformed by wavelet transformation, which produces coefficients in different sub-band. For example, if image P is decomposed into 4 resolution levels by wavelet transformation, the produced sub-bands are denoted by r ^s where re{0,1 ,2,3} is the resolution level, and se{LL, LH, HL ₁ HH) is the orientation; L - Low frequency, H - High frequency. Here, LL, LH, HL and HH denote 4 different frequency bands divided by wavelet transformations.

In watermark embedding step S22 the watermark W is embedded into the sub-bands according to the expression:

e

where m represents the length of watermark sequence, w, is the i-th watermark value in the watermark sequence. In order to keep the watermark robust, preferably re{2,3}

α represents the embedding strength where (0< α< 1); \ + aw _t > 0 ), which ranges from [0,1] and can be computed by a human visual system (HVS) such as described in A. S. Lewis, and G. Knowles: Image Compression Using the 2-D Wavelet Transform. IEEE Transactions on Image Processing, Vol. 1 , No. 2. (1992) 244-250; or set as a constant.

After embedding, the sub-bands are inversely transformed by wavelet transformation, and the produced watermarked image is C.

In step S23, by studying the pixels of the image C the corner features F=[f _o ,fi,...,f _R -i] can be extracted from image C using for example a corner and edge detection method such as, for example, that described in C. Harris and M. Stephens: A

Combined Corner and Edge Detector. 4th Alvey Vision Conference. (1988) 147-151 ; or H. Moravec: Obstacle Avoidance and Navigation in the Real World by a Seen Robot Rover. Technical Report CMU-RI-TR-3. Robotics Institute, Carnegie-Mellon University. (1980). Edges are generally points where there is a boundary (or an edge) between two image regions. In practice, edges are usually defined as sets of points in the image which have a strong gradient magnitude Corner points are typically points of the image where the difference between adjacent pixels is generally high in all directions. A corner can be defined as the intersection of two edges and may also be defined as a point for which there are two dominant and different edge directions in a local neighbourhood of the point.

f,=(x,,y,) (i=0,1 R-1 ) correspond to the co-ordinates of a comer point. The corner points are generally robust to geometric operations such as rotation, shearing, scaling, translation, etc. Typically, for different images, the number of the extracted corner points differs. In order to maintain coherence, only R corner points are selected as the feature F. The selection can be random.

Figure 4A illustrates the selection of a number of corner points f _ι =(Xι,yι) in an image.

In step S24, the watermarked image C is registered by storing the corner points f,=(x _t ,y,) of feature F and the corresponding image name in the feature database D. An example of the data structure of the database is shown in Table 2.

Table 2

In step S25, the watermarked and registered image C is distributed to customers.

The watermark embedding and feature extraction process according to this particular embodiment will now be described with Figure 3B In step S31 , image C is detected. Here, image C is the operated copy of image C, which has been attacked by operations such as adding noise, compression, rotation, shearing, scaling, translation, etc. Tw is a threshold used to determine the existence of a watermark. T _F is the threshold used to determine the matching features.

In step S32, the watermark W in image C is permuted under the control of key K. The sub-bands of the watermark W are obtained by wavelet transformation, and the correlation value:

1 r,s

/. W m /=1

and the watermark threshold:

Wtr are computed.

In step S33 the computed correlation value p for watermark W is compared to the threshold T _w if p> T _w ,, then the watermark W is deemed as existing, and the authentication process terminates.

Otherwise, if ρ< T _w then the following steps of the process are carried out . In step S34, a feature F'=[f ₀ ,f i,...,f _R -I] composed of R corner points is extracted from the watermarked image C. In step S35 the n closest matching features SF=(F ₀ , F-i, ... ,F _n- i} are obtained by computing the distance DiSt(F ₁ , F') and comparing with the threshold T _F .

The extracted feature F' and the stored features F ₁ are compared according to the expression:

If Dist\F _o F ) ≤ Tp th _en the feature F ₁ is deemed to be a matching feature.

Otherwise, F ₁ is deemed as not matching. The n images corresponding to the n features in SF correspond to the indexed images.

In step S36 k is set to 0, (where k is the matching feature number of the n matching features ranges from 0 to n-1 ) and the following operations are performed:

For k= 0 to k = n-1 two features (Fk, F') are matched by computing the parameters (a,b,c,d,e,f) of an affine transformation according to:

where, (x',y') and (x,y) correspond to the corner point coordinates of F' and F _k , respectively.

Using at least three point pairs, the parameters of H can be computed. The computing method may be least square method, such as described in G. Xue and P. Lu: A Counter-Geometric Distortions Data Hiding Scheme Using Double Channels in Color Images. The 3rd IWDW. (2004) 42-54; or a coarse matching before random sample consensus (RANSAC) method such as described in M. A. Fishier and R. C. Bolles: Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography. The Communications of the ACM, Vol. 24, No. 6. (1981 ) 381-395.

In step S37 the computed parameters (a,b,c,d,e,f) are then used to rectify the image from C to C' _k . That is, these parameters are used to emend the pixel position (x',y') in C according to:

where, (x'k.y'k) is the pixel position in corresponding image CV

In step S38 from the emended image C' _k , a watermark correlation p and a watermark threshold T is computed, respectively, according to a similar method to that of step S32.

In step S39 if the watermark correlation ρ<T, then the watermark is deemed as existing i.e. the image is copyright protected, and the authentication process is terminated.

Otherwise, if p≥T, the following steps are then performed:

k is set to k=k+1 , and the process returns to step S36 until K = n. If k reaches n in step S40 then it is deemed that there is no watermark in the image and thus determined that the image is not copyright protected. The authentication process then terminates.

An example of results of the process are shown in Figures 5 to 7. In this example, m=1000, R=80, TF=20 n=10, and the test image includes baboon, plane, lena, Elaine, Barbara, etc. Fig. 5 shows the corner detection results of the original and operated images where i) is the original image, ii) a cropped image iii) a rotated image, iv) a scaled imaged v) a sheared image and vi) a translated image. Figure 6A graphically illustrates the result of corner point matching of a rotated image and Figure 6B illustrates watermark detection with correlation and threshold. Figure 7 presents a table showing the robustness test under the condition of various attacks. The table of Figure 7 illustrates that the scheme can survive the desynchronization attacks of global geometrical transform and general signal processing attacks. For example, the angle range against the rotation attack and the rotation-scaling one is up to 10 degrees.

The embodiments of the invention provide the advantage that a mechanism for both copyright protection and media content index is provided since the extracted feature can be used for content index as well as for media content authentication. Moreover, the extracted feature stored in the feature database improves the watermarking algorithm's robustness.

Embodiments of the invention find application in the distribution of media content data by media service providers to customers where both copyright protection and content index functionalities are required.

Although the present invention has been described hereinabove with reference to specific embodiments, the present invention is not limited to the specific embodiments, and modifications will be apparent to a skilled person in the art which lie within the scope of the present invention.

For example, although in the preceding embodiment the media data content is constituted of an image, it will be appreciated that in alternative embodiments of the invention the media content data may be any audio, video or image data content.

While in the foregoing embodiments of the invention, a corner point based feature is used, it will be appreciated that in alternative embodiments of the invention other features such as boundary, edge or histogram features may be used .

Many further modifications and variations will suggest themselves to those versed in the art upon making reference to the foregoing illustrative embodiments, which are given by way of example only and which are not intended to limit the scope of the invention, that being determined solely by the appended claims. In particular the different features from different embodiments may be interchanged, where appropriate.

In the claims, the word "comprising" does not exclude other elements or steps, and the indefinite article "a" or "an" does not exclude a plurality. The mere fact that different features are recited in mutually different dependent claims does not indicate that a combination of these features cannot be advantageously used. Any reference signs in the claims should not be construed as limiting the scope of the invention.