EMBEDDING DATA IN MATERIAL FIELD OF THE INVENTION The present invention relates to embedding data in material.
In this application, material means one or more of video material, audio material and data material. Video material in this context may be still images or moving images.
BACKGROUND OF THE INVENTIONIt is known to embed data symbols in material information.
A previously proposed arrangement for embedding data symbols in material information utilises a transform domain representation of the material information.
Transform domain symbols are selected and then modulated with the embedded data symbols, before the transform domain symbols are reverse transformed to reproduce the material information in which the data has been embedded. An example of such a previously proposed arrangement is illustrated in Figures 1A, 1B and 1C.
The modulation of the selected transform domain symbols is performed using an embedding scale which is shown in Figure lA. As shown in Figure lA the embedding scale is divided into predetermined regions. Each region is assigned a possible value of the data symbol to be embedded. For the example of binary data each region is assigned a binary value of'1'or'0'.
The value of a selected transform domain symbol, which in the illustrative example is"6", is then adjusted in accordance with the value of the data symbol to be embedded. The adjustment is made to the effect that the value of the transform domain symbol falls within the nearest region of the encoding scale which is representative of the data symbol to be embedded. Hence, the value of the transform domain symbol may be adjusted to fall mid-way within the"0"to"8"region of the encoding scale when it is required to embed a binary'0'as illustrated in Figure IB. Alternatively the value of the transform domain symbol is adjusted to fall mid-way within the"8"to"16"region of the encoding scale when it is required to embed a binary'1'as illustrated in Figure 1 C.
Thus, when the embedded data is detected and recovered, the transform domain symbol in which the data symbol has been embedded is known, and the encoding scale
is known. so that the region in which the adjusted transform domain symbol falls indicates the value of the embedded data symbol.
As will be appreciated, in order to minimise the effect of embedding the data on the material information. the transform domain symbol should be preferably changed by as small an amount as possible. This encourages the use of a larger number of predetermined regions in the encoding scale, the range of values of the transform domain symbol being made smaller. As a result, the amount of adjustment required to be made to the transform domain symbol so that it falls within a region assigned to a particular data symbol value is smaller.
However, a result of reducing the range of values of the encoding scale is to reduce the likelihood of correctly recovering the value of the embedded data symbol.
This is because processing such as compression encoding and analogue to digital and digital to analogue conversion has an effect of changing the values of the original transform domain symbol. This, in combination with other inaccuracies in the data detection and recovery process, can be regarded as noise. Therefore, the smaller the range of the encoding scale regions the more likely noise will cause the value of the transform domain symbol to be changed to an adjacent region, thereby potentially erroneously representing a false value for the embedded data symbol. Hence, it will be appreciated that noise having a value larger than half the magnitude of the encoding region will result in the value of the transform domain symbol being changed to another region, thereby potentially erroneously representing a false value for the embedded data symbol. In this example, experiencing noise which causes the value of the transform domain symbol to change by greater than"4"may result in a false value for the embedded data symbol.
It is desired to provide an encoding and decoding technique, which has improved robustness to noise.
SUMMARY OF THE INVENTIONAccording to a first aspect of the present invention there is provided an apparatus for embedding data in material information, the apparatus comprising an embedding processor operable to select at least one symbol of the material information for embedding a symbol of the data, to compare a value of the material information symbol with an embedding scale divided into predetermined regions, each of the
regions being associated with a value of the data symbol, and consequent upon the comparison to adjust the value of the material information symbol to fall within the nearest of the predetermined regions of the embedding scale associated with the value of the data symbol to be embedded, wherein at least one adjacent region of the embedding scale is associated with the same value of the data symbol to be embedded.
Hence, embodiments of the present invention seek to provide an advantage in increasing the likelihood of correctly recovering embedded data, or conversely reducing an amount by which the material symbols must be changed whilst providing an improved immunity to noise. This is effected by assigning the same embedded data symbol value to adjacent regions of the encoding scale. For the binary example, instead of alternating between binary'I's and'O's, the encoding scale pairs regions encoding'l's and'0's together. As a result the same encoding scale ranges, requiring the same adjustment to the material symbols, can be maintained whilst providing an improved immunity to noise. This is because even if the effect of noise on the adjusted material data symbol is to change its value to the next region, the value of the corresponding embedded data symbol is more likely to remain the same. Hence, the effect of noise would have to change the adjusted material data symbol by a greater amount for an error to occur.
Thus it has been found that the embedding technique provides an improved robustness to noise. As will be appreciated, the likelihood of the value of a material symbol being changed by noise to an adjacent region having a different associated value is generally the same as being changed to an adjacent region having the same value. Therefore, statistically, there is an increase in the likelihood over the abovedescribed technique of correctly recovering embedded data for the same amount of noise adjustment to the material symbol. Alternatively, the likelihood of correctly recovering embedded data can be maintained whilst applying a reduced amount of adjustment to the material symbol in comparison to the existing technique.
Although the data symbols may be embedded in the material information by adjusting the selected symbols of the material information in preferred embodiments the apparatus may comprise a transform processor operable to transform the material information into the transform domain, the embedding processor being operable to embed the data symbols to be embedded by comparing and adjusting selected
transform domain material information symbols in accordance with the embedding scale.
The transform processor may be a wavelet transform processor or a DiscreteCosine Transform (DCT) processor.
According to a second aspect of the present invention there is provided an apparatus for detecting and recovering data embedded in material information by the apparatus according to the first aspect of the present invention.
Other aspects and features of the present invention are defined in the appended claims.
BRIEF DESCRIPTION OF THE DRAWINGSFor a better understanding of the present invention, reference will now be made by way of example to the accompanying drawings in which:Figures lA to 1C are schematic diagrams illustrating a previously proposed technique of embedding data in material;Figure 2 is a block diagram illustrating an apparatus for embedding data in material information according to an embodiment of the present invention;Figure 3 is schematic diagram illustrating material information;Figures 4A to 4C are schematic diagrams illustrating a technique used by the apparatus of Figure 2;Figure 5 is a block diagram illustrating an apparatus for decoding embedded data in material information produced by the apparatus of Figure 2;Figure 6 is a schematic diagrams illustrating a technique used by the apparatus of Figure 5; andFigures 7A and 7B illustrate the structure of a Universal Material Identifier (UMID).
DESCRIPTION OF PREFERRED EMBODIMENTS EMBEDDER/ENCODER Figure 2 is a block diagram illustrating an apparatus 100 for embedding data in images 105 according to an embodiment of the present invention. In this preferred embodiment the images 105 are processed in the transform domain as it has been found that. particularly with Discrete Cosine Transforms (DCT), the embedding is more robust, less perceptible, and changes to DCT values are spread over a number of pixels in spatial domain. However, it will be appreciated that the present invention is not limited to this and could equally be applied to spatial domain representations of material information 105.
The apparatus 100 may receive material information generally, being either audio material, video material or data material. The material information comprises of a plurality of bits, bytes or symbols. It will be appreciated that the characteristics of the material information which is to encode the data symbol 135 will determine the embedding scale to be used.
Embodiments of the present invention find application in embedding data in any form of material information. However, in the example embodiments the material information is image data.
The apparatus 100 receives an image 105 and generates a transform domain representation of the image 115 using a transform processor 110. Where the material information 105 comprises a plurality of frames the transform processor may be arranged to produce a transform domain representation of the material information 115 for each frame of material information 105. An embedding processor 120 receives the transform domain representation of the material information 115 and data 135 to be embedded. The data comprises a plurality of data symbols. The embedding processor 120 adjusts one or more, but generally, at least one selected transform domain symbol of the transform domain representation of the material information 115 to fall within the nearest predetermined region of an embedding scale corresponding to the value of the data symbol to be embedded. As will be explained shortly, the adjusted transform domain symbols represent the value of data symbols being embedded.
For the example of video images comprising a number of frames, the embedding processor 120 may be arranged to adjust transform domain symbols of the
transform domain representation of the material information 115 in different frames. Hence. some frames may have no adjusted transform domain symbols whilst other frames may have more than one transform domain symbols. To improve the likelihood of correctly recovering the embedded data in the presence of noise, in one embodiment, the same data symbol may be embedded more than once. The data symbol may be any particular data value to be embedded. In another embodiment the data 135 may comprise a Universal Material Identifier (UMID) or a subset thereof.
The use of a UMID is advantageous as it provides for unique identification of the material information 105. UMIDs are described in more detail below in the section entitled UMIDs. The data 135 may also be encoded using known error correction coding techniques such as Reed-Solomon encoding or convolutional encoding prior to being embedded. This is advantageous since error correction coding further improves robustness to noise.
One such example of material information 105 is a DCT transform 300
illustrated in Figure 3. Here, one macro block 310 of 8x8 pixels is selected and two predetermined transform domain symbols II, h are adjusted to encode respective data symbols.
EMBEDDING/ADJUSTING TECHNIQUEThe operation of the embedding processor 120 will now be explained in more detail with reference to embedding data in the DCT transformed image in Figure 3.
Figures 4A to 4C are schematic diagrams illustrating a technique used by the apparatus 100.
Figure 4A shows an embedding scale which is divided into predetermined regions. Each region has boundaries, the boundaries being the lower and upper values of the region. Each region is assigned a possible value of the data symbol to be embedded. It will be appreciated that any suitable value could be assigned. For the example of binary data each region is assigned a binary value of'1'or'0'. Two adjacent regions of the encoding scale form a pair and each pair is assigned the same embedded data symbol value. For the binary example, the paired regions are assigned alternately'1's and'O's.
The transform domain symbol I in this illustrative example has a value of"6" but may have any integer value between"-64"and"+64". It will be appreciated that
the transform domain symbol I may have any value within a range of any suitable size and that the range need not have both positive and negative values.
The value of the transform domain symbol I in this illustrative example is then adjusted in accordance with the value of the data symbol to be embedded, to the effect that the value of the transform domain symbol I is adjusted to fall within the nearest region of the encoding scale which is associated with the data symbol to be embedded.
Consider that a binary'0'is to be embedded in the transform domain symbol I, the adjustment of the transform domain symbol I is illustrated in Figures 4B and 4C.
In Figure 4B, the location of the nearest boundary between paired regions is determined. In this example, the nearest two boundaries Bu, bu exist at the values"8"
and"-8". It will be appreciated that various techniques could be used to determine the nearest of the boundaries such as by the use of look-up tables, through arithmetic derivation or the use of counters. In preferred embodiments, the values of the boundaries are subtracted from the value of the transform domain symbol I and the boundary with the smallest result is selected. In this illustrative example, the nearest boundary is determined to be at the value"8".
In Figure 4C, the value of the selected transform domain symbol I is then adjusted in accordance with the value of the data symbol to be embedded. In this example, a value of"4"is subtracted from the boundary value to encode a binary'0' such that the value of the transform domain symbol I is adjusted to be"4". Had a binary'l'to be encoded then a value of"4"is added to the boundary value such that the value of the transform domain symbol I is adjusted to be"12". The value of"4" corresponds to half the range of the predetermined region and results in the value of the transform domain symbol I being adjusted to the mid-point of the nearest of the embedding scale regions which encodes the data symbol to be embedded.
Accordingly, the same amount of adjustment is made to the transform domain data symbol I as in the prior art approach. It will be appreciated that other techniques for adjusting the value of the selected transform domain symbol I could be used.
As explained above, noise can cause the transform domain symbol I to fall within a different region. As such, noise can cause the value of the transform domain symbol I to change by a value greater than 4 with the effect that a false value for the embedded data symbol may be decoded as is the case in the prior art. This effect is
particularly likely in the case of JPEG compression encoding. However, depending on the probability distribution of the noise, small changes of the transform domain symbol are more likely, so that, for example, in the case of Gaussian noise it can be seen that in approximately 50% of cases the value of the transform domain symbol I will be
likely to change to a value greater than"4", but still represent the correct embedded data symbol, by falling within the adjacent region of the embedding scale encoding the same data value.
It will be appreciated that this improved likelihood of correctly recovering the value of the embedded data symbol provides significant performance advantages particularly when recovering data from material information which has been subject to processing such as compression encoding and analogue to digital and digital to analogue conversion.
Whilst in preferred embodiments the value of the transform domain symbol I is adjusted to a value being the mid-point of the nearest of the embedding scale regions which encodes the data symbol to be embedded it will be appreciated that the value of the transform domain symbol I could be adjusted to any value within that embedding scale region. This is particularly advantageous where it is known that the material will be subject to a particular form of distortion as a result of noise or processing which results in a non-zero mean.
Whilst in preferred embodiments the encoding scale comprises a predetermined number of adjacent regions of equal size are used, clearly it will be appreciated that the encoding scale may be configured in any suitable manner. For example, if it is known that certain values of the transform domain symbol I will never occur then the encoding scale could be arranged to exclude these. Also, it may be desirable where the characteristics of the transform domain symbols I are known to exhibit particular properties for regions to have unequal lengths so as to minimise the adjustment in this region.
DECODERFigure 5 is a block diagram illustrating an apparatus for decoding embedded data in material information produced by the apparatus of Figure 2. The apparatus 200 receives embedded data material 125. A decoding processor 210 receives the embedded data material 125. The decoding processor 210 is provided with
information identifying which of the transform domain symbols have been embedded with data symbols. The decoding processor 210 identifies the transform domain symbols of the material information which represents an embedded symbol of the data.The decoding processor 210 compares the value of the selected transform domain symbol with an embedding scale and determines the value of the symbol of the data from the region of the scale in which the transform domain symbol falls. The data 135 is then output by the apparatus 200.
It will be appreciated that the decoding processor 210 may be arranged to decode more than one transform domain symbol of embedded data material 125. In situations where the embedded data material 125 comprises a number of frames, the decoding processor 210 may be arranged to decode transform domain symbols of the embedded data material 125 in different frames. Hence, some frames may have no transform domain symbols to decode whilst other frames may have more than one transform domain symbols to decode.
Typically, the data symbol is a binary'0'or a binary'1'. The data 135 may represent a Universal Material Identifier (UMID). The UMID provides for unique identification of the embedded data material 125.
Where the same data symbol has been embedded more than once to improve recoverability and robustness to processing and noise, the decoded values may be subject to a majority decision to determine a value for the data symbol.
In preferred embodiments when decoding data symbols a metric is generated indicative of the confidence in the decoding value. Decoded data symbols with a high confidence metric may be considered more reliable than those with a low confidence metric.
Figure 6 illustrates a technique for determining the confidence metric. A portion of the embedding scale illustrated in Figures 4A to 4C is shown, on which two data symbols II and Iz are indicated. The data symbol II has a value of'3'and falls within the region encoding a binary'0'. The boundary Bi between the pair of regions encoding a binary'0'and the pair of regions encoding a binary'1'is at the value'8'.The boundary B2 between the pair of regions encoding a binary'0'and the pair of regions encoding a binary'1'is at the value'-8'. The size of the region has the valueS. A confidence metric C (representing a confidence that the value of the embedded
data symbol is a'0'is calculated according to the difference between the mid-point of the region in which the data symbol falls and the actual value of the data symbols.
This is expressed by the equation given below: Cm =S/2-lmll -lml Where mn is the value of the mid-point of the n-th region, C is the confidence of the data symbol Im.
Therefore, for this example, a high confidence metric C is produced when the data symbol I is in the centre of the boundary region and a zero confidence metric is produced if the data symbol falls at the boundary. Therefore for the example data symbols 11, 12, shown in Figure 6, the confidence metric values Cl, C2 are I and 3 respectively. As will be appreciated this is just one example of a technique for generating the confidence metrics and other techniques may be used.
The confidence metrics can be used to improve the likelihood of correctly recovering the embedded data, for both the majority decision decoding and error correction decoding where the data has been error correction encoded. For the example of majority decision decoding, the confidence metrics can be used to weight the value of each embedded symbol value. This would be particularly advantageous if the data symbols are embedded only twice. If the data symbol values are not the same at the decoder, then the value having the highest confidence can be determined as the decoded data value.
For the example embodiment in which the data has been error correction encoded, the confidence metrics can be used in the decoding algorithm for error correction decoding. For example, if the data has been encoded using a block code such as for example a Reed-Solomon code, then a symbol comprised of bits having a low confidence can be declared as an erasure and used in a decoder employing erasure decoding. For the example of convolutional coding, the confidence metrics can be used as soft decision values in a Viterbi decoder for the convolutional code.
UMIDsA brief explanation will now be given of the structure of the UMID, with reference to Figure 7A and 7B. The UMID is described in SMPTE Journal March 2000. Referring to Figures 7A an extended UMID is shown to comprise a first set of
32 bytes of a basic UMID, shown in Figure 7B and a second set of 32 bytes referred to as signature metadata. Thus the first set of 32 bytes of the extended UMID is the basic UMID. The components are: < A 12-byte Universal Label to identify this as a SMPTE UMID. It defines the type of material which the UMID identifies and also defines the methods by which the globally unique Material and locally unique Instance numbers are created.
*A 1-byte length value to define the length of the remaining part of the UMID.
*A 3-byte Instance number which is used to distinguish between different
'instances'of material with the same Material number.
*A 16-byte Material number which is used to identify each clip. Each Material number is the same for related instances of the same material.
The second set of 32 bytes of the signature metadata as a set of packed metadata items used to create an extended UMID. The extended UMID comprises the basic UMID followed immediately by signature metadata which comprises: - An 8-byte time/date code identifying the time and date of the Content Unit creation.
sA 12-byte value which defines the spatial co-ordinates at the time of Content Unit creation.
- 3 groups of 4-byte codes which register the country, organisation and user codes.
More explanation of the UMID structure is provided in co-pending UK patent application number 0008432.7.
In so far as the embodiments of the invention described above are implemented, at least in part, using software-controlled data processing apparatus, it will be appreciated that a computer program providing such software control and a storage medium by which such a computer program is stored are envisaged as aspects of the present invention.
Although particular embodiments have been described herein, it will be appreciated that the invention is not limited thereto and that many modifications and additions thereto may be made within the scope of the invention. For example, various combinations of the features of the following dependent claims could be made with the features of the independent claims without departing from the scope of the present invention.