Data decoding system

The subject of the invention is a data decoding system, especially data as an additional information to a moving image.

With the development of multimedia techniques, large amounts of digital video and acoustic information were present in intemet systems or CD-ROM software. For digital video and audio information, it's easy to create the perfect copy without compromising quality, so illegal use and copyright protection is becoming a problem. In order to prevent illegal third party copying of media data, such as video and audio data, the technique of hiding additional information, e.g. the signature of the creator (author), in the source data of the media becomes the focus. When digital video or other similar data is copied illegally, you can know if the copy is illegal or not by confirming the signature hidden in the copy and specifying the source. A hiding technique like this is called data hiding.

Figure 1 shows a half-tone image obtained when digital data is imaged on a screen monitor. In the data of the carrier of Fig. 1, which is a digital image, messages such as a babysitter, river, preschooler and birds have been hidden, as shown in Fig. 1b. The carrier data is obtained by segmenting the image, obtained, for example, from photographs, into very small parts and numerically express the brightness and hue of each part. During this time, the original numerical value of the image for the image is slightly changed intentionally. If there is a small change in the numerical value, there will be almost no picture noise and you will not be able to sense the noise. If this feature is used skillfully, completely different information (message data) may be hidden in the source video signal. This message data can be any information, for example, grid patterns, tab lines or signatures of video image makers. The message data hidden in the carrier data can be extracted by processing it with the help of a special program. Therefore, based on the extracted message data, you can check whether the media data has changed.

The method of compressing moving images (video data) in the MPEG technique is also known. In the case where some additional information is input into the MPEG video bit stream, a method of hiding additional information in a user data field has usually been used. In this way, however, the field can be easily separated from the media data, so there is a problem that detecting and deleting additional hidden information is easy.

183 642

The essence of the data decoding system, according to the invention, inserted as additional information to a moving image formed by a plurality of frames by specifying at least one insertion area in the frames of a moving image, associating according to the rule of inserting data for insertion with a set of characteristics of the insertion area and determining the characteristic of each insertion area by reference to the insertion rule according to the content of the insertion data and then extracting the inserted data from each insertion area by reference to the extraction rule according to the characteristic . that it contains an area specifier specifying at least one insertion area with inserted information attached to the extractor extracting inserted information from the interframe prediction type in the insertion area by reference to the extraction rule according to which the type of interframe prediction corresponds to the content of the data to be extracted, wherein the extractor output is attached to a decoder that decodes encoded data from an extractor.

The subject of the invention is presented in the embodiment in the drawing, with reference to the coding system and the decoding system of the moving image and the procedures implemented therein, in which Fig. 1 shows the half-image obtained when the digital data is imaged on the screen monitor, Fig. 2 - diagram sequence of frames, Fig. 3 - scheme of the macroblock system in frame B, Fig. 4 - scheme of the relationship between the type of prediction and macroblock prediction error, Fig. 5 - reference images in the case where a change of images takes place, Fig. 6 - block diagram of the moving image coding system and Fig. 7 - block diagram of the moving image decoding system.

Initially, a case report will be made in which some additional information (message data) is inserted into the video bit stream compressed in MPEG (carrier data). The MPEG technique uses forward prediction based on a reference frame in the past, backward prediction based on a reference frame in the future, and bidirectional prediction based on reference frames in the past as well as in the future. Figure 2 shows a sequence of frames that includes three types of frames, I frame, P frames and B frames to perform bidirectional prediction.

Frame I is an internally coded frame and all macroblocks in this frame are compressed by intra-frame coding (without interframe prediction). The P frame is a coded predicted (forward) frame and all macroblocks in this frame are compressed by intra-frame coding or forward predicted coding. In addition, the B frame is a bidirectional predicted frame, interpolation coded. Macroblocks in frame B can be mainly encoded by using forward prediction, backward prediction, bidirectional prediction or intra-frame coding. The I frame and P frames are encoded in the same order as the original moving image. On the other hand, B frames are inserted between I frame and P frames, and after processing the I and P frames, B frames are coded.

The information (message data) insertion area is macroblocks of frame B and 1bit of information can be inserted relative to 1 macroblock. Therefore, when the message data is formed by a number of bits, it is necessary to perform the insertion process relative to the macroblocks corresponding to the number of bits. Figure 3 is a schematic diagram of the macroblock system in frame B. The macroblock is a 16x16 motion compensation unit that compresses video data by reducing their temporal redundancy.

Macroblocks in frame B can be classified into the following four groups as prediction types.

1. INTERCODED MACROBLOCK.

An internally encoded macroblock is a macroblock that is encoded only by information in the macroblock itself, without performing interframe prediction.

2. MACROBLOCK PROJECTED FORWARD.

The forward predicted macroblock is a macroblock that is predicted forward and coded by reference to either an internally coded frame (I frame) in the past

183 642 or to the coded forward predicted frame (P frames) in the past. In particular, the 16 pixel x 16 pixel square area is recovered, which is most similar in the past reference frame, and the macroblock has a prediction error (AP), which is the difference between it and the recovered square area, and also has information about the relative spatial position (motion vector) . Here, the AP prediction error is expressed as a difference in brightness or a color difference obtained for 16 x 16 pixels. The way a similar square area is selected depends on the encoders -.

3. BACKGROUND PROJECTED MACROBLOCK.

A backward predicted macroblock is a backward predicted macroblock that is encoded by reference to either an internally encoded frame (I frame) in the future or a coded forward predicted frame (P frame) in the future. The area that is most similar in the future reference frame is recovered and this macroblock has a prediction error (AN), which is the difference between it and the recovered area, and also has information about the relative spatial position (motion vector).

4. BIDIRECTED PROJECTED MACROBLOCK.

Bidirectional Predicted Macroblock is a bidirectional macroblock that is predicted bidirectionally and encoded by reference to a past reference frame and a future reference frame. Both the most similar area in the past reference frame and the most similar area in the future reference frame are recovered and this macroblock has a prediction error ((AN + Δ P) / 2) that is the difference between it and the average (per pixel) of these two areas, and also has information about the spatial relative position (of two motion vectors) between them.

In order to insert message data, at least one macroblock that is given in the insertion process must first be specified in frame B. This can be defined, for example, as individual macroblocks (insertion areas) that occur between the first line and the third line of the B frame, or it can be defined as all macroblocks in a certain frame. In addition to the macroblock previously defined as the format in this way, it can also be determined by using an algorithm that produces a position sequence.

Then, with respect to the macroblock specified as the subject of the insertion process, 1 data bit is inserted into 1 macroblock, based on the insertion rule, that the information bits correspond to the macroblock prediction type. For example, the following insert rule exists:

Inserted information bit Bit 1

Bit 0

No insertion

Prediction type of interframe macroblock

Bidirectional projected macroblock (represented by B)

Forward Predicted Macroblock (represented by P) or Backward Predicted Macroblock (represented by N)

Internally coded macroblock

For example, consider the case where 1010.4 message data is inserted, data bits are inserted in sequence in 4 insertion areas (macroblocks) between the first left macroblock and the fourth left macroblock of the first line shown in Fig. 3. First, the first data bit is 1, so the prediction type of the leftmost macroblock (first insertion area) is defined as bidirectional prediction (B) according to the given rule. The prediction error in this case becomes the prediction error, which is the difference from the average area that is most similar in the past reference frame and the area that is most similar in the future reference frame.

183 642

The next data bit is 0. Therefore, the type of prediction of the second macroblock (second insertion area) is either forward (P) or reverse (N) prediction according to the insertion rule. In this case, in order to eliminate image degradation, the prediction error in the forward prediction and the prediction error in the backward prediction are compared to select the type, with the prediction error being smaller. In the example of Fig. 3, because the prediction error in forward prediction is smaller than in retrograde prediction, forward prediction (P) is selected for the second macroblock.

A similar procedure is used repeatedly for the third insertion area and the fourth insertion area. As a result, the prediction type of the third macroblock becomes bidirectional prediction (B) and the prediction type of the fourth macroblock is referred to as backward prediction (N) because the prediction error in retrospective prediction is smaller.

In the manner described above, the first to fourth insertion interframe prediction types are BPBN types, and 4 bits 1010 (4 bits of message data) are inserted into these areas. If an attempt is made to insert data bits into a certain insertion area, there will be cases in which the image quality is significantly impaired. In such cases, the insertion of data bits into the insertion area is not carried out, and the insertion area prediction type is an internally coded macroblock that represents "insertion prohibition".

Next, a description will be given of how to extract the message data inserted in the previously mentioned procedure. Where message data is extracted, information must first be provided to specify the macroblock in which the message data has been inserted. Detailed information may be provided by an external unit. It is also possible to insert detailed information into the data itself first. In addition, in the event that the position of the insertion region is standard or if an algorithm for generating position sequences is known, the message data may be extracted.

Based on the type of prediction in the specified Insert Area, information inserted in this area is extracted with reference to the extraction rule. This extraction rule is the rule according to which the type of macroblock prediction corresponds to the information bits, this extraction rule must be given as information when the extraction is carried out.

For example, the extraction rule will be given below. It should be noted that the corresponding relationship between the type of prediction in this extraction rule and the information bits are the same as for the specified insertion rule. Also, if the prediction type is an internally coded macroblock, it is judged that no data bit has been inserted in the insertion area.

Extracted information bit Bit 1

Bit 0

Data bit has not been inserted

Prediction type of the inter-macro macTOblock

Two-block predicted macroblock (represented by B)

MakroMok pI'zewidy valid in pzzód (we represent pz / ez P) or backward predicted macroblock (represented by N)

Internally coded macroblock

The following is a description of the case in which the message data was inserted as shown in Fig. 3. Suppose it was already known that the message data bits were inserted

183 642 as a premise in the insertion areas from the first macroblock on the left to the fourth macroblock of the first line in Fig. 3. Since the leftmost prediction type of macroblock is bidirectional prediction (B), the bit value of 1 is secreted by reference to the isolation rule. The prediction type of the second macroblock is forward prediction (P), so a bit value of 0 is extracted according to the extraction rule. By repeatedly applying the same procedure to two other macroblocks, a bit value of 1 and a bit value of 0 are extracted in order. As a result, message data bits 1010 are extracted from these areas.

If the rightmost prediction type of macroblock is an internally coded macroblock, it will be judged according to the given extraction rule that a data bit has not been inserted into this macroblock. As a result, the message data bits are as follows: 1010.

The macroblock prediction type within the range allowed for each frame can be freely chosen by the encoder. Typically, the macroblock prediction type is selected with the least prediction error. However, it is characteristic of this embodiment that the type of macroblock prediction is selected according to the insertion rule given. Because the relationship between the type of prediction and the information bits in the extraction rule is identical to that given in the insertion rule, the inserted data can be exactly extracted by reference to the extraction rule.

However, if the prediction type is determined according to the insertion rule, it will be possible that the prediction type will be selected in which the prediction error is so great that the deterioration of image quality can be recognized visually. For the prediction error, there are many cases where the sum of the absolute values ​​or the sum of the square values ​​of the prediction errors are used for each pixel, but the MPEG coding technique does not specify which standard is used, so the encoder can freely apply any standard for prediction errors. However, no matter what standard is used, if the type of prediction is selected, in which the prediction error is too large, there will be a deterioration in image quality. Therefore, a certain threshold value is set for the prediction error. In the event that the prediction error in the selected prediction type is greater than the threshold value, it is desirable that the insertion of the data bit is not performed in the macroblock. In this macroblock, an internally encoded macroblock is made according to the insertion rule. This point will be described in more detail with reference to figure 4.

Figure 4 is a diagram explaining the relationship between the prediction type and macroblock prediction error. In this figure, the ordinate represents a prediction error, with a larger prediction error indicating a greater deterioration in image quality. Also, the threshold value was set as the degree of allowable prediction error, i.e. an assessment standard in which there is no perceptible degradation of image quality. In fig. 4 three short horizontal lines (i), (ii) and (iii), connected by a single vertical line, indicate any of the 3 prediction errors for forward prediction, backward prediction and bidirectional macroblock prediction. Due to the relationship between the threshold value and 3 prediction errors, the macroblock can be classified into 4 types (a), (b), (c) and (d). That is, these 4 types include case (type (a)) where 3 prediction errors are all smaller than the threshold value, case (type (b)) where any of the prediction errors exceeds the threshold value, case (type (c)) where 2 prediction errors exceed the threshold and case (type (d)) where all prediction errors exceed the threshold.

For a (d) macroblock, even if any prediction type is selected, all prediction errors will exceed the threshold value and there will be a significant deterioration in image quality, so it is undesirable to use this type of macroblock as the insertion area. In this case, this macroblock becomes an internally coded macroblock according to the insertion rule. However, in MPEG coding, most macroblocks in frame B have interframe prediction (forward prediction, backward prediction, or

183 642 bidirectional prediction), and indeed this type of macroblock is unlikely to occur.

For type (a) macroblock, even if any type of prediction is selected, it is not possible for the prediction error to exceed the threshold value. That is, even if any data is inserted that the image quality degradation will not be visible, so this type of macroblock can be used as the insertion area. Also, even for type (b), even if this block is used as the insertion area, it will be seen that there will be no noticeable degradation in image quality. It is usually not possible for bidirectional prediction error to become the worst of the three prediction errors, i.e. it is not possible for bidirectional prediction error to be a horizontal line (i). According to the insert rule, both bit value 1 and bit value 0 can be inserted into this block type without exceeding the threshold value. Therefore, when the specified insertion rule is used, data bits can be inserted into macroblocks of types (a) and (b) without substantially causing image degradation.

For type (c) it is undesirable from the given rule to use this type of block as the insertion area. In the case where the bi-directional prediction error is a horizontal line (iii), both the forward prediction error and the backward prediction error exceed the threshold value and as a result image deterioration will occur depending on the inserted data bit. However, even in this case, when the prediction error in the type of prediction corresponding to the data bit currently being inserted does not exceed the threshold value, for example in the case where the prediction error when a certain bit value is inserted according to the insertion rule is smaller than the threshold value indicated by a horizontal line (iii), it is possible to use this type of block as the insertion area.

According to the above points, three types of prediction errors are obtained for a certain macroblock into which data is inserted. Then, in the case where the prediction error of the prediction type determined based on the insert rule exceeds a predetermined threshold value, it is desirable to prohibit inserting data into this macroblock. In this case, the macroblock prediction type for which data insertion is prohibited is in-frame coding according to the insert rule.

It should be noted that internally encoded macroblocks of type (c) and (d) become unacceptable bits that cannot be used as a data insertion area. However, as described, the actual rate of occurrence is slow, so that unacceptable bits can be compensated by error correction coding in the case where the inserted information is allowed to have excess.

The macroblock type and bit of inserted data are associated and determined when coding a moving image. Therefore, the message data can be inserted into a moving image without significantly affecting the efficiency of the compression of the moving image, and also without causing a substantial deterioration in image quality. In addition, it is very difficult to delete message data inserted in this way from a moving image. In addition, since the amount of information inserted is almost independent of the image content, it is possible to effectively insert message data.

When image change takes place, most of the macroblocks in B-frames between I-frame and P-frame or between P-frames, before or after the change, are of the type (c) shown in Fig. 4. when the images change⁷. Fig. 5a shows the case in which there is no change of images and Fig. 5b shows the case in which the change of images takes place between frame2 and frame 3. In the figures, two opposite end frames are I or P frames and the two middle frames are frames B. In addition, the arrow shown in the figures indicates a reference relationship between the frames.

If there is no change in the images, there are a large number of bidirectional macroblocks in frame B. However, if there is image change, such as that shown in Fig. 5b, the number of backward and bidirectionally predicted macroblocks in frame 2 will be significantly reduced and most macroblocks will become forward predicted macroblocks, so that the prediction errors become less than the threshold of Fig. 4 Also number 8

183 642 evenly predicted and bidirectional macroblocks in frame 3 will be significantly reduced and most macroblocks will become retrospectively predicted macroblocks, so that the prediction errors become less than the threshold in Fig. 4. Therefore, it is undesirable to insert data into such frames. Therefore, the number of forward predicted macroblocks and the number of retrospectively predicted macroblocks is controlled, and when these numbers are less than a certain threshold, it is judged that image change has occurred. In this case, it is desirable not to insert data into such frames, i.e. according to the insertion rule, it is desirable that the prediction type be made into an internally encoded macroblock.

When considering the quality of the image, one should pay attention to the phenomenon of occlusion, which means that by moving a certain object, something hidden behind the object will suddenly appear or vice versa, hide. When occlusion takes place, the macroblocks associated with the occlusion throughout the entire frame are of the type (c) shown in Fig. 4. In this case, as described, if the prediction error of the prediction type determined according to the insertion rule is less than the threshold value, there will be no problem, but in a case other than this, there will be a noticeable degradation of image quality. When image quality is of great importance, deterioration can be prevented by applying an error correction code. That is, 1 bit of information is not expressed by a single macroblock, but instead an excess is entered into the information and the equivalent of 1 bit information is expressed by multiple macroblocks. In this case, a single insertion area is formed by a set of macroblocks.

For example, you can see a case where the equivalent of 1 bit information is expressed by three macroblocks. In this case, even if one of the three macroblocks were of a prediction type opposite to the data bit being expressed, the data bit could be accurately expressed by the other two macroblocks. If the internally coded macroblocks, in an amount greater than a predetermined number, are contained in a certain set of macroblocks that express 1 information bit, the data bit will not be inserted into the macroblock set. Conversely, if two or more macroblocks are of the type (c) shown in Fig. 4, it is necessary that some macroblocks become internally encoded macroblocks to clearly indicate that the data has not been inserted. This can also be used for insertion and isolation using a statistical technique. That is, each time statistical property occurs, many insertion areas are prepared, for example 100 areas, and 1 bit of information can be expressed by many areas. In this sense, redundancy means that 1 bit of information is not caused to correspond to a single processing area in one to one relationship, but rather causes it to correspond to multiple areas.

When occlusion occurs, it is contemplated that many of the adjacent macroblocks existing in the occlusion-related portion are of type (c) shown in Fig. 4. From this point of view, for a set of macroblocks that creates an error correction code, it is desirable to use macroblocks that occur at a distance from each other in the frame.

Although the given embodiment has been described with reference to the MPEG technique, other techniques than the MPEG technique can be used, also other methods of image compression, using the inter-frame prediction coding technique, and in this sense the insertion area is not limited to macroblocks.

In addition, you can use different rules, not just the specified insertion and extraction rules. For example, it is also possible to insert three data values ​​into a single macroblock, so that the forward predicted macroblock, the backward predicted macroblock and the bidirectional predicted macroblock correspond in turn to the bit values ​​of 0, 1 and 2 respectively.

It is also possible to insert data into the described P-frame. Since the P-frame macroblocks are forward-predicted macroblocks and internally coded macroblocks, the bit values ​​correspond to those macroblocks. However, from the point of view of suppression, deterioration of image quality and increase in data quality, as described above, it is desirable to insert data into the B frame instead of the P frame. The reason is that if the macroblock, which is an internally coded macroblock, is the predicted macroblock in

183 642 forward by the insertion rule, the image quality will be impaired or the amount of data will otherwise be increased.

Figure 6 is a block diagram of a moving image coding system. Memory 61 contains moving image data consisting of multiple frames. The first frame memory 62 stores the past reference frame and the second frame memory 63 stores the future reference frame for display. The area specifier 64 specifies the location where data is inserted as additional information. Thus, at least one area is detailed in the frame. The error calculator 65 calculates the forward prediction error, backward prediction error and bidirectional prediction error based on the data stored in the memories of 62 and 63 frames. The forward prediction error is calculated from both the insertion area and the reference area in the past reference frame to which it is referenced, through the insertion area using forward prediction. Backward prediction error is calculated from both the insertion area and reference area in the future reference frame that is referenced by the insertion area using backward prediction. Bidirectional prediction error is calculated from both the insertion area and reference areas, both in the past and future reference frame, which is referenced by the insertion area, using bidirectional prediction. Decision selection block 66 inserts the data inserted into the insertion area by controlling the characteristics of the area, which is the insertion area, with a reference to the insertion rule.

Specifically, the insert rule specifies that when a single data bit is inserted into the insert area, the prediction type in the insert area uses either forward prediction or bidirectional prediction. Also, when other data is inserted, it specifies that the prediction type uses bidirectional prediction. Decision selection block 66 determines the type of interframe prediction in the insertion area according to the content of the inserted information, and also lists the reference area to which it refers, by the insertion area according to the determined type of interframe prediction, and furthermore specifies any of the first, second or third prediction error . Then, encoder 67 encodes the signal that was derived from decision selection block 66.

Decision selection block 66 is designed such that for a certain insertion area, when the prediction error in the type of interframe prediction, determined based on the insertion rule, exceeds the predefined threshold value, insertion of data into this insertion area is prohibited. At the same time, deterioration of the image quality by insertion is prevented. Decision Selection Block 66 is also designed such that when the number of forward prediction references or the number of backward prediction references in a bidirectionally predicted frame is less than a predetermined number, insertion of data into the insertion area in that frame is prohibited. By counting the number of references, a change in images can be detected. Therefore, when there is a change of images, the insertion of data into the frame associated with the change is prohibited. As a result, image quality deterioration can be prevented.

Figure 7 is a block diagram of a moving image decoding system. Memory 71 contains encoded motion image data into which additional information is inserted. The area specifier 72 specifies at least one insertion area into which additional information in the frame is inserted. The extractor 73 extracts additional information, inserted into the insertion area, from the type of interframe prediction in the insertion area with reference to the isolation rule. Then, the decoder 74 decodes the encoded data that was output from the extractor 73, thereby reproducing the moving image.

In MPEG, B-frames are not referenced to other frames, so even if the type of macroblock prediction in frame B were changed, it would not be possible for the change to affect other frames. By using this fact, fingerprint data can be inserted. Fingerprint data is specific information that varies for each owner. A typical example of using fingerprint data is when the moving image data is issued to a third party, the publisher inserts the mark into the moving image data,

183 642 so that a third party who receives stations can be specified. If this is done in this way, the source of the copy may be specified when an illegal document, such as an illegal document is being implemented. Therefore, if the video data circulates illegally, there could be a charge for any unauthorized copy. Also, information on the registration of the legal owner is entered into the encrypted video product, and fingerprint data can be inserted according to the registration information.

In the case where fingerprint data are inserted, both "bi-directionally predicted macroblock" and "forwardly predicted macroblock where the prediction error is smaller" are maintained, which are generated when MPEG coding is implemented. Then the correct macroblock is selected according to the third person who receives the stations. Even if this is done in this way, there would be no effect on other frames or the data layer, for example the abscissa, which is larger than the macroblock layer of the corresponding frame.

183 642

<img file="PL183642B1_D0001.tif" />

FIG, 2

macroblock

<img file="PL183642B1_D0002.tif" />

FIG. 3

<img file="PL183642B1_D0003.tif" />

TYPE

FIG. 4 (IP)

<img file="PL183642B1_D0004.tif" />

3 4

<img file="PL183642B1_D0005.tif" />

2 = 3 4 b

FIG. 5

183 642

<img file="PL183642B1_D0006.tif" />

<img file="PL183642B1_D0007.tif" />

FIG. 7

183 642

<img file="PL183642B1_D0008.tif" />

FIG. 1

UP Department of Publications. Circulation of 60 copies Price PLN 4.00