Fingerprinting segments of data content for version identification

0001This invention relates to data content identification. Examples of such content include one or more of video content, audio content, metadata content, text content, image content and so on, such as audio visual content.

0002The growth of new digital infrastructures, including digital devices and high-speed networks, combined with increasing processor power, is making content creation, manipulation and distribution both simpler and faster. While this greatly aids legitimate usage of the content, a disadvantage is that unauthorised abuse or "piracy" of such content (particularly copyright content), such as unauthorised reproduction or distribution, is also becoming easier and more damaging to the content owner.

0003The situation is made more complicated in that commercial considerations may require the content owner to allow a potential customer to see or use the content in a trial situation - perhaps as part of a professional review of the content or before committing to purchase rights to use the content from the owner. In the case of, for example, a movie film, very many copies of the content may be distributed in this way.

0004It has been proposed that a so-called "fingerprinting" technique is used to apply identification data to the content. While this does not prevent unauthorised copying, it can allow the source of the unauthorised copies to be detected. Examples of a fingerprinting technique applicable to video signals are described in GB-A-2383221 and US-A-5664018.

0005However, this technique can take a long time to carry out. Using current technology at the priority date of this application, it can take up to, say, ten hours to apply the fingerprint processing to a full length movie film.

0006This invention provides a method of detecting a version of input data content in which: <ul id="ul0001" list-style="none" compact="compact"><li>the data content is arranged as two or more segments according to a segmentation pattern; and</li><li>versions of the data content are identifiable by corresponding identification data patterns by which at least some of the segments have respective identification data;</li><li>the method comprising the steps of: <ul id="ul0002" list-style="none" compact="compact"><li>detecting identification data in respect of segments of the input data content;</li><li>comparing the detected identification data with identification data patterns corresponding to different versions of the data content; and</li><li>detecting that the input data content comprises at least a contribution from a certain version of the data content if a sum of matches obtained between the detected identification data and the identification data pattern for that version exceeds a threshold number.</li></ul></li></ul>

0007The invention builds upon an unpublished proposal to generate fingerprinted content by combining sections or "segments" of multiple master copies of the content, at least some of which carry fingerprint data. (Here the term "fingerprint" refers to the secure addition of identification data to content, ideally in such a way that its presence is substantially imperceptible to the user). The segments are combined in accordance with a segmentation pattern which may be unique or quasi-unique to a particular user of that copy of the content. An advantage of this unpublished proposal is that uniquely fingerprinted copies of the content can be generated in a much shorter time than the time which would be required to apply the full fingerprint processing to each individual copy.

0008If a suspected pirate copy of the content is discovered, it is useful to be able to identify the source of the content from which the pirate version was copied. This can identify either the producer of the pirate copy or a security lapse by a user which allowed pirate copies to be made by another. In the unpublished proposal, this would require the detection of a 100% match between the fingerprint data detected in respect of each segment and the fingerprint data known to have been used for each segment in the version issued to a user.

0009However, this basic detection technique would take no account of a failure to detect a fingerprint in respect of one or more fingerprinted segments. Such a failure could occur if the content has been the subject of certain processing, such as so-called "camcorder piracy" in the case of a movie film. Nor does this basic detection technique take any account of so-called "collusion attacks", in which pirate copies are made as a combination of multiple legitimate copies, in an attempt to remove or dilute the fingerprint data.

0010The invention addresses at least some of these problems by providing a thresholding of the sum of matches between detected identification data and the identification data pattern for a user's version, in order to detect that the user's version is a source of the unauthorised copy.

0011In order to be assured of a desired false positive detection rate, especially in the case of a so-called collusion attack where individual segments may yield plural identification data, it is preferred to derive the threshold number from the identification data detected in respect of segments of the input data content. In particular, it is preferred that the threshold number depends upon how many instances of identification data are detected in respect of each segment of the input data content. Preferably the threshold number is set so that the statistical chance of the input data content being incorrectly detected as a certain version, given the number of instances of identification data detected in respect of each segment of the input data content, is less than a threshold probability.

0012In an alternative / additional technique, it is preferred that the method comprises weighting a match between identification data detected in respect of a segment of the input data content according to the number of instances of identification data detected in respect of that segment of the input data content, the sum of matches being a weighted sum of matches.

0013It is expected that a more reliable result would be obtained where the weighting is such that a segment for which plural instances of identification data are detected contributes less to the detection of a particular version than a segment for which a single instance of identification data is detected. However, counter-intuitively, it has been detected in some empirical tests of prototypes that a better result can be obtained where the weighting is such that a segment for which plural instances of identification data are detected contributes more to the detection of a particular version than a segment for which a single instance of identification data is detected.

0014To alleviate the problem of some segments not yielding identification data, it is preferred that if identification data is not detected in respect of two or more segments of the input data content, those segments are combined into groups of two or more segments and identification data detected in respect of the combined groups of segments. This process can preferably be repeated iteratively.

0015Preferably the threshold number represents a number of segments less than the total number of segments, and/or a number of segments less than the total number of segments having associated identification data in that identification data pattern.

0016Although identification patterns in which only some segments carry identification data can be used, it is preferred that versions of the data content are identifiable by corresponding identification patterns by which substantially all of the segments have respective identification data.

0017This invention also provides a method of applying identification data to input data content, the method comprising the steps of: <ul id="ul0003" list-style="none" compact="compact"><li>(i) generating n instances of the input data content, where n is greater than one, at least all but one of the instances carrying respective identification data, the identification data of each of the instances carrying respective identification data being unique with respect to the respective identification data carried by the other instances; and</li><li>(ii) generating versions of the input data content by selecting segments from the n instances, so that each version of the input data content carries identification data from the instances in accordance with an associated identification data pattern;    followed by one or more iterations of the steps of:</li><li>(iii) generating m further instances of the input data content, where m is one or more, each of the m instances carrying respective identification data which is unique with respect to all of the other instances; and</li><li>(iv) generating further versions of the input data content by selecting segments from the m instances, a set of instances including the m instances, or the entire set of generated instances, so that each version of the input data content carries identification data from the instances in accordance with an associated identification data pattern.</li></ul>

0018For better detection of the origin of pirate copies, it is preferred that in step (i), all of the instances carry respective identification data which is unique with respect to the other instances.

0019This invention also provides a method of applying identification data to input data content, the method comprising the steps of: <ul id="ul0004" list-style="none" compact="compact"><li>(i) providing n instances of the input data content, where n is greater than one, at least all but one of the instances carrying respective identification data, the identification data of each of the instances carrying respective identification data being unique with respect to the respective identification data carried by the other instances; and</li><li>(ii) generating versions of the input data content by selecting segments by a predetermined segmentation pattern from the n instances, so that each version of the input data content carries identification data from the instances in accordance with an associated identification data pattern;</li></ul>    in which the segmentation pattern is such that at least one of the segments (e.g. at least a majority of the segments) is not contiguous within the input data content.

0020This aspect of the invention can provide advantages in avoiding so-called collusion attacks, in which multiple copies of fingerprinted data are combined. By using non-contiguous segments it will be harder for a group of colluders to identify the segment boundaries.

0021The invention is particularly well suited to data content comprising video content having a plurality of successive images. Preferably the identification data is encoded within the data representing at least some of the images, for example within a subset of spatial frequency components of at least some of the images.

0022This invention also provides apparatus for detecting a version of input data content in which: <ul id="ul0005" list-style="none" compact="compact"><li>the data content is arranged as two or more segments according to a segmentation pattern; and</li><li>versions of the data content are identifiable by corresponding identification data patterns by which at least some of the segments have respective identification data;</li><li>the apparatus comprising: <ul id="ul0006" list-style="none" compact="compact"><li>means for detecting identification data in respect of segments of the input data content;</li><li>means for comparing the detected identification data with identification data patterns corresponding to different versions of the data content; and</li><li>means for detecting that the input data content comprises at least a contribution from a certain version of the data content if a sum of matches obtained between the detected identification data and the identification data pattern for that version exceeds a threshold number.</li></ul></li></ul>

0023This invention also provides apparatus for applying identification data to input data content, the apparatus comprising: <ul id="ul0007" list-style="none" compact="compact"><li>(i) instance generation means for generating n instances of the input data content, where n is greater than one, at least all but one of the instances carrying respective identification data, the identification data of each of the instances carrying respective identification data being unique with respect to the respective identification data carried by the other instances; and</li><li>(ii) version generation means for generating versions of the input data content by selecting segments from the n instances, so that each version of the input data content carries identification data from the instances in accordance with an associated identification data pattern;</li><li>(iii) means for controlling the instance generation means to generate m further instances of the input data content, where m is one or more, each of the m further instances carrying respective identification data which is unique with respect to all of the other instances; and</li><li>(iv) means for controlling the version generation means to generate further versions of the input data content by selecting segments from the m instances, a set of instances including the m instances, or the entire set of generated instances, so that each version of the input data content carries identification data from the instances in accordance with an associated identification data pattern.</li></ul>

0024This invention also provides apparatus for applying identification data to input data content, the apparatus comprising: <ul id="ul0008" list-style="none" compact="compact"><li>(i) means for providing n instances of the input data content, where n is greater than one, at least all but one of the instances carrying respective identification data, the identification data of each of the instances carrying respective identification data being unique with respect to the respective identification data carried by the other instances; and</li><li>(ii) means for generating versions of the input data content by selecting segments by a predetermined segmentation pattern from the n instances, so that each version of the input data content carries identification data from the instances in accordance with an associated identification data pattern;</li></ul>    in which the segmentation pattern is such that at least one of the segments is not contiguous within the input data content.

0025Further respective aspects and features of the invention are defined in the appended claims.

0026The invention will now be described, by way of example only, with reference to the accompanying drawings, throughout which like parts are described by like references and in which: <ul id="ul0009" list-style="none" compact="compact"><li>Figure 1 is a schematic diagram of a fingerprint encoding apparatus;</li><li>Figure 2 schematically illustrates the generation of fingerprinted copies of content using segments of multiple master copies;</li><li>Figure 3 schematically illustrates the application of the technique along VOBU boundaries in a DVD;</li><li>Figure 4 schematically illustrates non-contiguous segments;</li><li>Figure 5 schematically illustrates the application of the technique to a video-on-demand transmission;</li><li>Figure 6 schematically illustrates the application of the technique to an internet download file;</li><li>Figure 7 schematically illustrates a fingerprint detection apparatus;</li><li>Figure 8 schematically illustrates the operation of the apparatus of Figure 7;</li><li>Figure 9 schematically illustrates a segment analysis operation; and</li><li>Figure 10 schematically illustrates a master generation operation.</li></ul>

0027The present technique may be used to mark content so as to be able to uniquely identify the content (or a copy of at least part of the content) later using forensic analysis. The concept is applicable to any packetisable data such as video and audio elementary data or multiplexed streams. This does not mean to say that the data must be in a formal packetised form, but rather that the data can be manipulated as segments or portions representing subsets of the whole amount of data to be marked. The technique can be applied to packaged media (such as content stored on a storage medium such as an optical disk), content downloaded from the Internet (so-called content "pull" system), content broadcast over, for example, a digital television service (so-called content "push" system), or other content delivery formats.

0028The process of creating fingerprinted content involves creating two or more (in general, <i>m</i>) master copies M_i. The individual masters can all be marked uniquely using fingerprinting or one original can be left unmarked. In the case of video content, the techniques described in the above references allow identification data to be added to the content in such a way that the presence of the identification data is substantially imperceptible to the viewer, the identification data may be decoded later from a short section of the content (of the order of perhaps a few seconds of video) and the identification data is substantially robust against manipulation of the content such as resizing, data compression or even camcorder piracy (capturing the content by directing a video camera at a screen showing the content).

0029Then the masters are divided up identically into n number of parts (segments or portions).

0030In a basic system, the division is a simple time-division so that segment 1 comprises a first time period of the content, segment 2 follows segment 1, segment 3 follows segment 2, and so on. The segments may be of equal length or may be of different lengths.

0031In a more advanced arrangement, each segment can potentially occupy a number of non-contiguous time periods. This arrangement has advantages in resisting so-called collusion attacks, and will be described further below with reference to Figure 4.

0032In a further possibility (which may be combined with either of the two possibilities described above), the segments can be arranged as spatial divisions of video content, so that, for example, an upper part of the picture may represent a different segment to a lower part of the picture.

0033Based on a pseudo-random generation of combinations of the <i>n</i> segments from the m masters, a version of the content is created which contains the same <i>n</i> segments, but the identification data applied to those segments is combined in a pseudo-random manner. As long as a sufficient number of masters and segments is used to provide a set of permutations sufficiently large to encompass the number of versions to be distributed, no two versions need ever have the same permutation of segment identification data. This means that each version has a unique fingerprint, without the need to apply the time consuming process of bespoke fingerprint generation to produce each such version.

0034Figure 1 is a schematic diagram of a fingerprint encoding apparatus using this technique.

0035In Figure 1, an unmarked (not fingerprinted) video file 10 is supplied to two fingerprint encoders 20, 30. The video is subject to fingerprint encoding using two different sets of fingerprint data to produce two masters M₁, M₂. It will be appreciated that one of the masters might in fact be left un-fingerprinted, and it will also be appreciated that the fingerprint encoding process could be carried out as a serial process rather than the parallel one shown in Figure 1. Furthermore, the number of masters could be greater than two.

0036The two masters are subjected to MPEG2 encoding by encoders 40, 50 and compressed audio data such as AC3 audio data is multiplexed into the data by multiplexers 60, 70. This produces two so-called DVD images, that is to say the video data in a form ready to be recorded onto a DVD disk. Each image contains the fingerprint corresponding to the master M₁ or the master M₂.

0037Two image segment combiners 80, 90, which receive identification vectors from a user database 100, combine segments of the two master DVD images M₁, M₂ according to the identification vectors. The identification vectors are considered to be unique (or at least quasi-unique) by arranging that the number of masters and the number of segment alterations gives a sufficiently large population of identification vectors for the number of versions required to be produced. The output of each combiner is supplied to a respective DVD writer (a so-called "burner") 110, 120 and respective DVD disks 130, 140 are written. To produce a further DVD disk from each burner, a new identification vector is supplied from the database and a new combination of the segments of the two master DVD images M₁, M₂ is produced.

0038Although Figure 1 shows the same number of masters, combiners and burners (i.e. two of each), it will be appreciated that this is simply for clarity of the diagram. There is no technical reason why there should be the same number of combiners and burners as masters.

0039A non-secret code linking each disk to the (secret) identification vector stored in the database 100 may be written to the disk, printed visibly on the disk or both. This is not a technical feature but rather is useful for routing the disk to the correct user. Indeed, the name of the user could be stored in the database 100 and also printed onto the surface of the respective DVD disk.

0040By way of an example, assume that there are 3 masters and each master is divided into 5 segments. This arrangement is schematically illustrated in Figure 2. Each version would be defined by a five digit "identification vector" such as '13213' or '22131'. This indicates, in a pre-defined segment order, which master was used to provide each segment of that version. Referring to Figure 2, the ID vectors used for the four example versions (a to d) at the lower part of the diagram are: <tables id="tabl0001" num="0001"><table frame="all"><tgroup cols="2" colsep="1" rowsep="0"><colspec colnum="1" colname="col1" colwidth="78.75mm" /><colspec colnum="2" colname="col2" colwidth="78.75mm" /><tbody valign="top"><row><entry namest="col1" nameend="col1" align="left">version a</entry><entry namest="col2" nameend="col2" align="left">32212</entry></row><row><entry namest="col1" nameend="col1" align="left">version b</entry><entry namest="col2" nameend="col2" align="left">11332</entry></row><row><entry namest="col1" nameend="col1" align="left">version c</entry><entry namest="col2" nameend="col2" align="left">13222</entry></row><row rowsep="1"><entry namest="col1" nameend="col1" align="left">version d</entry><entry namest="col2" nameend="col2" align="left">23221</entry></row></tbody></tgroup></table></tables>

0041At replay, there should be no difference between versions in the audio/video material enjoyed by the user (assuming that the fingerprint data has been added in such a way as to be substantially imperceptible). The only difference between the versions is in the fingerprint data.

0042The identification vector can be stored in the database in such a way as to be linked to the user that received that version.

0043The possible combinations of individual fingerprints depends on 3 factors: <ul id="ul0010" list-style="none" compact="compact"><li>i) Number of masters <i>m</i>;</li><li>ii) Number of segments <i>n</i>;</li><li>iii) Maximum number of segments that can be interchanged <i>k.</i></li></ul>

0044The formula for determining the number of combinations (<i>c</i>) distinct from a single master is <ul id="ul0011" list-style="none" compact="compact"><li>i) If all <i>n</i> segments are interchangeable then the number is<maths id="math0001" num=""><math display="block"><mrow><mtext mathvariant="italic">c</mtext><mtext> = </mtext><msup><mrow><mtext mathvariant="italic">m</mtext></mrow><mrow><mtext mathvariant="italic">n</mtext></mrow></msup><mtext mathvariant="italic">-1</mtext></mrow></math><img file="EP1501047A2_D0001.tif" /></maths></li><li>ii) If a maximum of <i>k</i> segments out of <i>n</i> are interchangeable then the number is<maths id="math0002" num=""><img file="EP1501047A2_D0002.tif" /></maths></li></ul>

0045For example, if 2(=<i>m</i>) masters for a 120 minute movie divided into 60(=<i>n</i>) segments are used, and only 20(=<i>k</i>) of the 60 segments are interchangeable, the number of combinations distinct from a single master is over 7×10¹⁵. For a simpler set-up, assuming <i>m</i>=2, <i>n</i>=20 and all 20 are interchangeable the number of combinations distinct from a single master is 1,048,575. The following table demonstrates how the number of combinations distinct from a single master scales with the number of masters and number of segments. <tables id="tabl0002" num="0002"><table frame="all"><tgroup cols="3" colsep="1" rowsep="1"><colspec colnum="1" colname="col1" colwidth="52.50mm" /><colspec colnum="2" colname="col2" colwidth="52.50mm" /><colspec colnum="3" colname="col3" colwidth="52.50mm" /><thead valign="top"><row><entry namest="col1" nameend="col1" align="left"><i>m</i></entry><entry namest="col2" nameend="col2" align="left"><i>n</i></entry><entry namest="col3" nameend="col3" align="left"><i>c</i></entry></row></thead><tbody valign="top"><row><entry namest="col1" nameend="col1" align="left">2</entry><entry namest="col2" nameend="col2" align="left">20</entry><entry namest="col3" nameend="col3" align="left">1048575</entry></row><row><entry namest="col1" nameend="col1" align="left">3</entry><entry namest="col2" nameend="col2" align="left">20</entry><entry namest="col3" nameend="col3" align="left">3486784400</entry></row><row><entry namest="col1" nameend="col1" align="left">5</entry><entry namest="col2" nameend="col2" align="left">20</entry><entry namest="col3" nameend="col3" align="left">95367431640624</entry></row><row><entry namest="col1" nameend="col1" align="left">10</entry><entry namest="col2" nameend="col2" align="left">20</entry><entry namest="col3" nameend="col3" align="left">99999999999999999999</entry></row><row><entry namest="col1" nameend="col1" /></row><row><entry namest="col1" nameend="col1" align="left">2</entry><entry namest="col2" nameend="col2" align="left">10</entry><entry namest="col3" nameend="col3" align="left">1023</entry></row><row><entry namest="col1" nameend="col1" align="left">2</entry><entry namest="col2" nameend="col2" align="left">20</entry><entry namest="col3" nameend="col3" align="left">1048574</entry></row><row><entry namest="col1" nameend="col1" align="left">2</entry><entry namest="col2" nameend="col2" align="left">60</entry><entry namest="col3" nameend="col3" align="left">1152921504606846975</entry></row><row rowsep="1"><entry namest="col1" nameend="col1" align="left">2</entry><entry namest="col2" nameend="col2" align="left">99</entry><entry namest="col3" nameend="col3" align="left">633825300114114700748351602687</entry></row></tbody></tgroup></table></tables>

0046Figure 3 schematically illustrates the application of the technique along VOBU boundaries in a DVD.

0047A VOBU (<i>V</i>ideo <i>OB</i>ject <i>U</i>nit) is a small (typically a few seconds) contiguous sequence of video (and associated audio) stored on a DVD. It must include one or more self contained "Groups of Pictures" (GOPs) which can be understood by the MPEG decoder of the DVD player. All seeking, jumping, etc on replay is guaranteed to occur at a VOBU boundary so that the decoder need not be restarted and that the location jumped to is always the start of a valid MPEG stream. VOBUs can be organised into <i>VOBU Groups,</i> which in turn can be arranged into <i>VOBs</i> (Video OBjects). Each VOBU Group is a standalone, multiplexed unit and does not have dependencies on previous or later units. A VOBU Group can have as many VOBUs as necessary or appropriate.

0048For simplicity of the diagram, Figure 3 shows only two masters M₁ and M₂. These may be individually fingerprinted or one may be fingerprinted while the other is not. The two masters are MPEG2 encoded and pre-multiplexed into a VOBU and VOBU Group structure. The masters are segmented for the purposes of the present technique along VOBU group boundaries.

0049Then based upon a quasi-unique identification vector as described above, the segments are combined in a pseudo-random manner to recreate a unique DVD recording, which can then (for example) be burnt onto a recordable DVD (DVD-R). This process takes much less time than preparing a bespoke fingerprinted DVD-R, as the fingerprinting has to be done only to the masters which are then pre-multiplexed. The process of individualisation in respect of each version is simply concerned with concatenating data segments.

0050Once the VOBU groups are combined, then an IFO generation process takes place which calculates the offsets of each VOBU inside the newly created VOB. (In DVD video disk encoding, the IFO is a file stored on the DVD disk which contains Information. While the main component of the DVD is represented by the VOB files which contain MPEG-2-encoded audio, video and subtitle streams, the IFO files provide information for the DVD player as to where the DVD chapters start, where certain audio tracks are located, and the like.) To the DVD player the VOB appears to be fully self-consistent, as any properly-encoded DVD, but internally it is a combination of VOBU Groups from two or more distinct DVD encodes. The VOB follows the DVD specification constraints.

0051If one of these DVDs is pirated, either by a direct copy (so-called "ripping") or by re-encoding in, for example, the so-called DiVx or Xvid formats, it should be possible to identify the source of the pirate copy, i.e. the owner of the version form which the pirate copy was made. To do this, the video stream of the pirate copy is analysed. The segment boundaries are identified, and the identification data carried by the fingerprint in respect of each segment is decoded. This generates an identification vector which can be compared with the identification vectors stored in the database that was created when the discs were burned. Since each disc will have a quasi-unique identification vector, this should allow the identification of the source.

0052Figure 4 schematically illustrates an arrangement using non-contiguous segments. Here, the segments are numbered 1, 2, 3, 4, 5... and it can be seen that during the length of the video material (viewed from left to right across the page) each segment is split into two or more non-contiguous parts. The way in which this can help to defeat so-called collusion attacks will be discussed below.

0053The same concept may be used with, for example, internet downloads or video-on-demand arrangements, or other content delivery mechanisms where an individual content package is delivered to each user or group of users.

0054Figure 5 schematically illustrates the application of the technique to a video-on-demand (VOD) transmission. Here, two masters M₁, M₂ divided into segments (shown for simplicity as contiguous segments) are combined by a combiner 80' in accordance with an identification vector received from a database 100'. The combined video stream is handled by a VOD server 200 and transmitted by a cable network to a user's VOD set-top box 210. The user views the file on a television set 220.

0055Similarly, in Figure 6, a database 100" supplies an identification vector to a combiner 80" in order to combine two master copies M₁, M₂. The combined file is transmitted by a web server 230, over an internet connection and to a client personal computer (PC) 240.

0056It should be noted that as far as the VOD server and subsequent processing is concerned, and as far as the web server 230 and subsequent processing is concerned, the protected file is like any other file. The security obtained by combining fingerprinted masters has no relevance on the VOD server or the web server, nor on the end user's enjoyment of the content.

0057Despite the perceived robustness and low false positive rate of the underlying fingerprint technology, a segmentation system using the technology inappropriately could potentially have a higher false positive rate and little collusion robustness. At least some of these difficulties can be addressed by an appropriate decoding strategy.

0058Figure 7 schematically illustrates a fingerprint detection apparatus.

0059The apparatus of Figure 7 comprises a personal computer 300 having a display 310, a keyboard 320 and a user input device such as a mouse 330. The personal computer has a central processing unit 340, read only memory 350, random access memory 360, disk storage 370, a network interface 380 by which a connection may be made to a network such as the internet 390 and input/output processing 400, for example set up to read and/or write data to/from a DVD disk 410. The software by which the personal computer implements the present techniques (and indeed the software controlling the version generation techniques described here) may be supplied on a storage medium such as the disk storage 370 or a removable medium such as the optical disk 410, and/or via a network or internet connection such as the connection via the network interface 380.

0060Figure 8 schematically illustrates the operation of the apparatus of Figure 7.

0061In Figure 8, a suspect pirate copy of protected content is read from a DVD disk 500. At 510, the content is divided into segments in accordance with the predetermined (and secret) segmentation pattern and the segments are analysed for fingerprint data. At 520 a threshold amount is derived from this analysis. The way in which the threshold is derived will be described below, but in basic terms this is a statistical calculation in order to give a required or desired false positive rate (i.e. a required assurance that the end result is valid) given the distribution of identification data amongst the segments.

0062At 530, the segment identification data are tested against user identification vectors read from a copy of the database 100. Matching identification data are detected.

0063Finally, at 550, the threshold is applied to the results of the test carried out at 530. Any users whose identification vectors match sufficiently as to result in a test score which exceeds the threshold are considered to be sources of the pirate copy.

0064At a basic level, as mentioned above the decoder could decode identification data from each segment of the pirate copy to produce a decoded identification vector, and then attempt to match this decoded identification vector with the identification vector previously stored in respect of each user. However, in order to be robust against potential failure to decode identification data from a segment (e.g. if the content has been processed too severely or if the segment has been deleted from the content altogether), it is important that the decoder does not search for identification data match on every single segment. Instead, a good decoder strategy is to test for there being an identification data match on sufficiently many segments. Exactly what threshold number of matches is considered sufficient will depend on the desired false positive rate - if the threshold is too small then it is more likely that an innocent recipient's random identification vector will match the decoded identification vector sufficiently to indicate a match.

0065In the presence of collusion, it is possible that the underlying fingerprint decoder manages to decode multiple identification data for each segment (depending on how the collusion attack was performed).

0066In this situation a good decoding strategy is still to test for there being sufficiently many matches of a user's identification vector with the decoded identification vector. However, as noted, the decoded identification vector may have multiple identification data per segment. This fact increases the likelihood of an innocent user's pseudo-random identification vector happening to sufficiently match the decoded identification vector that the innocent user is deemed to be the source of the pirate copy. The threshold of matching segments should therefore be set to avoid this problem. Note that the threshold will actually depend on how many identification data are decoded per segment, which itself depends on how the collusion has been performed.

0067In the decoded identification vector, let the weight <i>w</i> of a segment be the number of information data decoded from that segment. Suppose there are <i>m</i> masters, then for each segment 0 ≤ <i>w</i> ≤ <i>m</i> . Segments of weight 0 offer no information in a matching process, as no match is possible. Similarly, segments of weight <i>m</i> offer no information in a matching process, as a match is always possible.

0068A preferred decoding strategy is, for each recipient, to count the number of matches between the recipient's identification vector and the decoded identification vector, concentrating only on segments of weight 1 ≤ <i>w</i> &lt; <i>m</i> . If the number of matches for a particular recipient's identification vector is greater than or equal to a threshold <i>t</i>, then that recipient can be accused of participating in the piracy. What follows is a method of calculating <i>t</i> to guarantee a specified false positive rate, <i>p</i>.

0069For 1 ≤ <i>w</i> &lt; <i>m</i>, let <i>c</i>_<i>w</i> be the number of segments of weight <i>w</i> in the decoded identification vector, i.e. the number of segments from which <i>w</i> identification data have been decoded.

0070Then<maths id="math0003" num=""><img file="EP1501047A2_D0003.tif" /></maths> represents the total number of segments of weight 1 ≤ <i>w</i> &lt; <i>m.</i>

0071For 1 ≤ <i>w</i> &lt; <i>m</i> let<maths id="math0004" num=""><img file="EP1501047A2_D0004.tif" /></maths> For any segment of weight <i>w</i> in the decoded identification vector, the probability of there being a match with the corresponding segment in an independent random identification vector is <maths id="math0005" num=""><math display="inline"><mrow><mfrac><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext mathvariant="italic">m</mtext></mrow></mfrac></mrow></math><img file="EP1501047A2_D0005.tif" /></maths>. As there are <i>c</i>_<i>w</i> such segments in the decoded identification vector, <i>B</i>_<i>w</i> represents the binomial probability distribution of the number of matches between the decoded identification vector and an independent random identification vector, when considering only segments of weight <i>w</i>.

0072For any random identification vector, (independent of the decoded identification vector), let <i>A</i> be a random variable that represents the number of matches between the random identification vector and the decoded identification vector, when considering only segments of weight 1≤ <i>w</i> &lt; <i>m</i> in the decoded identification vector. Then<maths id="math0006" num=""><img file="EP1501047A2_D0006.tif" /></maths>

0073IF the population is of size <i>y</i>, then thershold <i>t</i> can be calculated as the smallest positive integer such that<maths id="math0007" num=""><img file="EP1501047A2_D0007.tif" /></maths> where the false positive rate is <i>p.</i>

0074Another possible algorithm will now be described.

0075It may be advantageous to associate more significance to a match with a segment of one weight as opposed to a match with a segment of another weight. It may therefore be desirable to have a weighted sum for calculating the number of matches. For 1 ≤ <i>w</i> &lt; <i>m,</i> let <i>α</i>_<i>w</i> be a positive integer.

0076For any identification vector, <i>V</i>, let <i>c</i>_<i>w</i>_,_<i>V</i> be the number of segments of weight <i>w</i> in the decoded identification vector that match the corresponding segment in <i>V</i> (for 1 ≤ <i>w</i> &lt; <i>m).</i> Then let the weighted sum for calculating the number of matches be<maths id="math0008" num=""><img file="EP1501047A2_D0008.tif" /></maths> Note that this is equivalent to the previous strategy when <i>α</i>_<i>w</i> = 1, for 1 ≤ <i>w</i> &lt; <i>m.</i>

0077For any random identification vector, (independent of the decoded identification vector), let <i>A</i> be a random variable that represents the weighted sum of matches between the random identification vector and the decoded identification vector, when considering only segments of weight 1 ≤ <i>w &lt; m</i> in the decoded identification vector. Then<maths id="math0009" num=""><img file="EP1501047A2_D0009.tif" /></maths>

0078If the population is of size <i>y</i>, then threshold <i>t</i> can be calculated as the smallest positive integer such that<maths id="math0010" num=""><img file="EP1501047A2_D0010.tif" /></maths> where the false positive rate is <i>p.</i>

0079Tests have shown that using a weighted sum for the match count is sometimes slightly better and sometimes worse than using a non-weighted match count. It is, of course, possible to use a non-weighted and multiple weighted sums to perform many tests. In this case, the false positive rate, <i>p</i>, for each test must be reduced so that the overall combined false positive rate from all of the tests is low enough.

0080Empirical results have shown that a weighting of α_w = <maths id="math0011" num=""><math display="inline"><mrow><mfrac><mrow><msup><mrow><mtext mathvariant="italic">m</mtext></mrow><mrow><mtext>2</mtext></mrow></msup></mrow><mrow><mtext mathvariant="italic">m</mtext><mtext> - </mtext><mtext mathvariant="italic">w</mtext><mtext> + 1</mtext></mrow></mfrac></mrow></math><img file="EP1501047A2_D0011.tif" /></maths> for 1 ≤ <i>w &lt; m</i> works well.

0081In the absence of collusion, the weighted and non-weighted decoding strategies are equivalent and work very well. For example, with (i) only 2 masters, (ii) 10000 recipients, (iii) 120 segments (e.g. 2-hour movie, 1 minute per segment), and (iv) a false positive of 10^-8, it is possible to successfully detect the source of the pirate copy when only 40 of the segments yield segment identification data. With 4 masters, only 20 of the segments need to yield segment identification data in order for the source of the pirate copy to be determined.

0082Collusion, though, makes the situation much more tricky. It is difficult to determine the best collusion strategy that a set of colluders should adopt. Ignoring the collusion response of the underlying fingerprinting technology, one strategy for the colluders is to generate an identification vector with at most only one identification data per segment. If the segmentation pattern is known (or can be determined) then the colluders could form an attacked copy simply by selecting different segments from the copies they have available (e.g. if there are <i>z</i> colluders, then ¹/_<i>z</i> of the segments in the attacked version could come from each colluder).

0083It is therefore important that the attackers are not able to determine which portions of the movie constitute a segment. The encoding should preferably therefore be set up to (i) use a large number of segments and (ii) form each segment from smaller sections pseudorandomly distributed across the movie (as in Figure 4, above). This should make it impossible or at least very difficult for the attackers to isolate individual segments, meaning that each segment will, in all likelihood, yield more than one segment identification data.

0084The colluders may, instead, choose the more conventional collusion attack of, say, averaging frames together. In such an approach, the collusion response of the underlying fingerprinting technology is important. For a given segment, the fingerprint detector will hopefully detect some or all of the segment identification data. Detecting the users who are the source of the pirate copy becomes easier as the number of segment identification data increases. However, it is possible that, given sufficiently many colluders, such an attack causes the detector to fail to detect any identification data over the period of a segment. It is therefore important that the segments are sufficiently long enough to survive the anticipated attacks (be it collusion or more general processing, such as compression, resizing, etc).

0085A balance must be made between (i) ensuring that a segment is sufficiently long to allow the fingerprint detector to detect segment identification data and (ii) ensuring that there are as many segments as possible to make the segmentation pattern as difficult to deduce as possible.

0086Reducing the population size can also help improve the decoding. Having generated a set of fingerprinted masters, the segment multiplexing can begin to produce the fingerprinted copies for distribution. Meanwhile, a new set of fingerprinted masters can be being generated as a background processes. Once this has been done, these masters could be used instead. This essentially reduces the population size for each set of masters. Alternately, the new masters could be used in addition to the old masters, thereby increasing the number of masters for future copies. This process will be described with reference to Figure 10 below.

0087In the case that not every segment yields identification data, perhaps because of processing or camcorder piracy applied to the content, a technique will now be described using coalesced segments to attempt to derive identification data from those segments. Of course, this assumes that the segments were intended to carry identification data. It will be known from the segmentation pattern and the nature of the masters (i.e. was one master an un-fingerprinted file?) whether identification data is expected for each segment. This does point to an advantage of using all fingerprinted masters (rather than one unmarked fingerprinted master) because the expectation then is that every segment will carry some sort of identification data.

0088Referring to Figure 9, at a step 600 the segments are analysed for identification data. At a step 610, a detection is made as to whether all segments have yielded at least one identification data. If this is true then the process (as regards analysing the segments) ends. If it is not true, control passes to a step 620.

0089At the step 620 a detection is made as to whether the segments for which identification data is expected but has not been obtained can be coalesced. Basically, this question could be considered as a detection of whether more than one segment has not yielded identification data as expected.

0090If the answer is no, i.e. there is only one such segment, then the process ends. If the answer is yes, then control passes to a step 630 at which the unsuccessfully decoded segments are coalesced.

0091The process of coalescing segments can take place in several stages. For example, if several segments were expected to carry identification data but have not yielded such identification data on decoding, then the segments could be combined in pairs in an arbitrary grouping (perhaps, temporally adjacent pairs of unsuccessfully decoded segments could be combined). In this case, if there is an odd number, one of the pairs could be made up to a group of three. Or a different rule could be applied, for example so that the unsuccessfully decoded segments are coalesced into groups of three and so on. The coalesced segments are then passes back to the step 600 for a repeated analysis to try to detect identification data.

0092Of course, it may be that the unsuccessfully decoded segments making up a coalesced segment all happen to carry the same identification data. In this case, coalescing the segments will mean that the decoder is more likely to detect the identification data. (In general, the longer a section of fingerprinted video material, the more likely it is that a decoder will detect the identification data). If the segments did not carry the same identification data, there is still a chance that coalescing them may assist in detection, or alternatively as the group of initial segments making up a coalesced segment grows, it becomes more likely that two or more of the initial segments would carry the same identification data.

0093So, after one stage of coalescing segments, if there are still two or more unsuccessfully decoded (coalesced) segments, a further stage of coalescing can take place. This can repeat in an iterative manner until only one unsuccessfully decoded coalesced segment remains.

0094Figure 10 schematically illustrates an alternative master generation operation. In this example, three parallel fingerprint encoders are used, referred to as encoders 1, 2 and 3. Figure 10 is divided into four columns illustrating the operation of encoders 1, 2 and 3 in the left most three columns and the combiner/burner arrangement (80, 110 or 90, 120) in the right most columns.

0095At a first stage of encoding, the encoders generate three masters M₁, M₂, M₃. These are combined and DVDs are produced from the three masters.

0096Once the three masters have been produced, the encoders are then free to produce three further masters M₄, M₅, M₆. During the time that these further masters are being prepared, the DVDs that are produced by the combiner/burner will be based only on masters M₁ to M₃. However, once the further masters M₄ to M₆ are available, it is possible for the combiner/burner to produce versions based on <ul id="ul0012" list-style="bullet" compact="compact"><li>only the masters M₄ to M₆</li><li>all of the masters M₁ to M₆ or</li><li>any permutation thereof</li></ul>

0097The process can continue iteratively. In general, using current technology it is expected to take ten times as long to produce a fingerprinted master as to do the combination and writing of a single output version.