Methods of scene change detection and fade detection for indexing of video sequences

[0002] 1. Field of the Invention

[0003] This invention relates to methods of scene change detection and fade detection for indexing of video signal sequences of the types encountered in, for example, High Definition Television (HDTV) broadcast signals and other video distribution systems such as are encountered on world wide web video services.

[0004] 2. Description of the Prior Art

[0005] Basic methods for compressing the bandwidth of digital color video signals have been adopted by the Motion Picture Experts Group (MPEG).

[0006] The MPEG standards achieve high data compression rates by developing information for a full frame of the image only every so often. The full image frames, or intra-coded pictures are called “I-frames”, and contain full frame information independent of any other frames. B-frames and P-frames are encoded between the I-frames and store only image differences with respect to the reference anchor frames.

[0007] Typically, each frame of a video sequence is partitioned into smaller blocks of pixel data and each block is subjected to a discrete cosine transformation (DCT) function to convert the statistically dependent spatial domain picture elements (pixels) into independent frequency domain DCT coefficients.

[0008] Respective 8×8 blocks of pixels are subjected to the Discrete Cosine Transform (DCT) to provide the coded signal. The resulting coefficients typically are subjected to adaptive quantization, and then are run-length and variable-length encoded. Thus, the blocks of transmitted data typically include fewer than an 8×8 matrix of codewords. Macroblocks of intraframe encoded data (I-frames) will also include information such as the level of quantization employed, a macroblock address or location indicator, and a macroblock type, the latter information being referred to as “header” or “overhead” information.

[0009] The blocks of data encoded according to P or B interframe coding also consist of matrices of Discrete Cosine Coefficients. In this instance, however, the coefficients represent residues or differences between a predicted 8×8 pixel matrix and the actual 8×8 pixel matrix. These coefficients also are subjected to quantization and run- and variable-length coding. In the frame sequence, I and P frames are designated anchor frames. Each P frame is predicted from the lastmost occurring anchor frame. Each B frame is predicted from one or both of the anchor frames between which it is disposed. The predictive coding process involves generating displacement vectors, which indicate which block of an anchor frame most closely matches the block of the predicted frame currently being coded. The pixel data of the matched block in the anchor frame is subtracted, on a pixel-by-pixel basis, from the block of the frame being encoded, to develop the residues. The transformed residues and the vectors comprise the coded data for the predictive frames. As with intraframe coded frames, the macroblocks include quantization, address and type information.

[0010] The results are usually energy concentrated so that only a few of the coefficients in a block contain the main part of the picture information. The coefficients are quantized in a known manner to effectively limit the dynamic range of ones of the coefficients and the results are then run-length and variable-length encoded for application to a transmission medium.

[0011] The so-called MPEG-4 format is described in “MPEG-4 Video Verification Model Version 5.0”, distributed by the Adhoc Group on MPEG-4 Video VM Editing to its members under the designation ISO/IEC JTC1/SC29/WG11 MPEG 96/N1469, November 1996. The MPEG-4 video coding format produces a variable bit rate stream at the encoder from frame to frame (as was the case with prior schemes). Since the variable bit rate stream is transmitted over a fixed rate channel, a channel buffer is employed to smooth out the bit stream. In order to prevent the buffer from overflowing or underflowing, rate control of the encoding process is employed.

[0012] With the advent of new digital video services, such as video distributed on the world wide web, there is an increasing need for signal processing techniques for identifying scene changes and other characteristics in the video sequences, such as scene-change-like object changes in the MPEG-4 context. Identification of scene changes, whether they are abrupt or gradual, are useful for the purposes of indexing, which, for example, facilitates rapid and simple image retrieval and scene analysis.

[0013] In the future, it should be expected that a significant amount of digital video material will be provided in the form of compressed or coded data as described above. Operating on the video sequence information in its compressed form, rather than its decompressed or decoded form, where possible, usually permits more rapid processing because of the reduction in data size and the avoidance of transformation. It is advantageous to develop methods and techniques which permit operating directly on compressed data, rather than having to perform full frame decompression before other processing is performed.

[0014] It is known that when a block (macroblock) contains an edge boundary of an object, the energy in that block after transformation, as represented by the DCT coefficients, includes a relatively large DC coefficient (top left corner of matrix) and randomly distributed AC coefficients throughout the matrix. A non-edge block, on the other hand, usually is characterized by a similar large DC coefficient (top left corner) and a few (e.g. two) adjacent AC coefficients which are substantially larger than other coefficients associated with that block. This information relates to image changes in the spatial domain and, when combined with image difference information obtained from comparing successive frames (i.e. temporal differences) factors are available for distinguishing one video object (VO) from another. If only the DC values of macroblocks are used, an image that results will be a blurred version of the original image which retains much of the content of the original.

[0015] Thus, previous work in indexing from compressed video had mostly emphasized DC coefficient extraction. In a paper entitled “Rapid Scene Analysis on Compressed Video”, IEEE Transactions on Circuits and Systems for Video Technology, Vol. 5, No. 6, December 1995, page 533-544, Yeo and Liu describe an approach to scene change detection in the MPEG-2 compressed video domain, as well as review earlier efforts at detecting scene changes based on sequences of entire (uncompressed) image data, and various compressed video processing techniques of others. Yeo and Liu introduced the use of spatially reduced versions of the original images, so-called DC images, and DC sequences extracted from compressed video to facilitate scene analysis operations. Their DC image is made up of pixels which are the average value of the pixels in a block of the original image and the DC sequence is the combination of the resulting reduced number of pixels of the DC image.

[0016] Won et al, in a paper published in Proc. SPIE Conf. on Storage and Retrieval for Image and Video Databases, January 1998, describe a method to extract features from compressed MPEG-2 video by making use of the bits expended on the DC coefficients to locate edges in the frames. However, their work is limited to I-frames only. Kobla et al describe a method in the same Proceedings using the DC image extraction of Yeo et al to form video trails that characterize the video clips. Feng et al (IEEE International Conference on Image Processing, Vol. 11, pp. 821-824, Sept. 16-19, 1996), use the bit allocation across the macroblocks of MPEG-2 frames to detect abrupt scene changes, without extracting DC images. Feng et al's technique is computationally the simplest since it does not require significant computation in addition to that required for parsing the compressed bitstream.

[0017] In accordance with a first aspect of the present invention, computationally simple methods have been devised which employ combinations of certain aspects of Feng et al's approach and Yeo et al's approach to give accurate and simple abrupt and/or gradual scene change detection. The present inventors also have investigated techniques that make use of bit allocation information to extract features and detect gradual scene changes, each of which is described in further detail in concurrently filed applications.

[0018] Previous work in gradual scene change detection has employed various techniques such as considering the edge change fractions, a twin comparison approach, block matching based motion compensation-estimation, the detection of plateaus in a delayed frame difference metric, and a video edit model based approach. Of these, only the approach of detecting plateaus operates in the compressed domain.

[0019] It should be noted that the DC image extraction based technique is good for I-frames since the extraction of the DC values from I-frames is relatively simple. However, for P-frames, additional computation typically is needed. The present inventors have determined, that, once a suspected scene/object change has been accurately located in a group of consecutive frames/objects by use of a DC image extraction based technique, application of an appropriate bit allocation-based technique, and/or an appropriate DC residual coefficient processing technique to P-frame information in the vicinity of the suspected change information quickly and accurately locates the cut point. This combined method is applicable to either MPEG-2 sequences or MPEG-4 multiple object sequences. In the MPEG-4 case, it has been found to be advantageous to use a weighted sum of the change in each object of the frame, using the area of each object as the weighting factor.

[0020] The bits allocated to the DC coefficients of P-frames are also used to detect fade-in and fade-out gradual scene changes.

[0021] In accordance with this first aspect of the present invention, a method of processing digital image-representative video data in compressed form comprises the steps of extracting, from a sequence of digital image-representative video data in compressed form, which comprises at least I-frames and P-frames occurring between the I-frames, sub-sequences of frames, each including at least a set of temporally adjacent I-frames. The compressed form data for each sub-sequence is processed to extract corresponding DC image values for each of the I-frames. Corresponding DC image values for temporally adjacent pairs of the I-frames are compared to detect instances of difference information exceeding a first threshold value. Pairs of the I-frames which indicate potential scene changes are identified according to the comparing step. The process further comprises retrieving video data for P-frames occurring only between those I-frames identified from the DC image differences as indicating potential scene changes, and detecting the occurrence of scene changes by at least one of the steps of determining bit allocation distribution differences across the retrieved P-frames to locate the occurrence of abrupt scene changes and by determining numbers of positive and negative DC residual coefficients in the retrieved P-frames in excess of a second threshold value to locate fade in and fade out, respectively.

[0022] In the drawing:

[0023] FIG. 1 is a schematic block diagram which illustrates certain aspects of the present invention.

[0024] Referring to the schematic diagram of FIG. 1 of the drawing, it can be seen that methods according to a first aspect of the present invention make use of a preliminary step which involves locating suspected scene changes using only I-frame information in the compressed domain (block 20 of the diagram). This step relies upon use of DC image-based criteria to “qualify” certain pairs of frames as indicating gradual or abrupt scene changes. Thereafter, the qualified frame associated information is further processed to locate abrupt and/or fade-in, fade-out scene changes using either a bit allocation distribution criterion across P-frames (block 30) or a criterion comparing the number of positive/negative DC residual coefficients (block 40) with respect to each P-frame in the regions where there is a suspected scene or object change.

[0025] In this manner, temporal segmentation markers may be generated and are associated with the input video sequence to locate and identify the particular types of scene changes of the video sequence.

[0026] Specific preferred arrangements for each of the abrupt scene change and fade-in/fade-out scene change detection steps will now be described in detail. It should be appreciated that there is substantial opportunity for varying details of these steps without departing from the more general aspects of the present invention. Detailed method steps are, however, indicated below to provide an appreciation for the possible variations to persons skilled in this art.

[0027] Simply stated, one aspect of the present method comprises the following steps:

[0028] 1. Locate the GOP's in which scene changes are suspected to exist by using the DC—image-based process on successive I-frames;

[0029] 2. Apply the bit allocation-based criterion to P-frames in each of the GOP's selected in step 1 to locate cut points.

[0030] To apply this latter technique to MPEG-4 compressed video, the following detailed steps are employed.

[0031] Since MPEG-4 is object-based, similarly located objects in two adjacent frames are compared. The temporal change in each object is measured in terms of the numbers of bits for encoding and a weighted average of the changes (differences) over all the objects in a frame is determined, with the weight being related to the fraction of the total frame area occupied by the object. Object changes also are detected by repeating the procedure at the object level in each shot or scene. Changes above a threshold level indicate a suspected scene change.

[0032] Since the number of bits taken to encode each object varies significantly, a fixed threshold is not suitable as it might be in MPEG-2 data. Using a fixed threshold with MPEG-4 data results in false detection and/or fails to detect scene changes at the object level. A combination of a fixed threshold and a sliding window therefore is used to ensure that the detection works at all bit rates of interest.

[0033] It should also be taken into account that frame replication is sometimes used when changing from one frame rate to another. This practice can lead to a false scene change detection where bit allocation techniques are employed as described above. Therefore, as a further refinement, by splitting the bit allocation bit image into two images, one corresponding to the bit allocation for motion vectors and the other corresponding to the residual, frame replication can then be detected as a sudden dip in the number of bits required to encode the motion vectors, as well as an accompanying dip in the number of bits required to encode the residual. This simultaneous dip in both parameters disqualifies this data from the scene change determination. Thus this added refinement eliminates a false detection problem where frame replication is used.

[0034] The specific steps employed for abrupt scene change detection are as follows:

[0035] 1. Let the test sequence S consist of frames I₀PP . . . I₁PP . . . I₃. . .

[0036] 2. Form a sub-sequence S₁consisting of the I-frames I₀I₁. . .

[0037] 3. Carry out scene change detection of S₁using the DC image based criterion. That is, for each macroblock, determine an average DC value equal to ¼ the sum of the DC values for each 8×8 block in the macroblock, compare temporally adjacent corresponding macroblocks to determine the difference for each macroblock. The sum of the absolute values of the differences for all macroblocks in the frame is then calculated and is divided by the sum of the absolute values of the DC values for all macroblocks in the frame to provide a normalized change per macroblock. It is then possible to determine that a potential scene change exists when any frame to frame difference (normalized change per macroblock) is greater than a selected first threshold value. It has been determined empirically that a threshold of 0.25 is a suitable threshold.

[0038] In the MPEG-4 case, while comparing frames, compare objects occupying the closest corresponding spaces in the frames, and if the objects being compared are of different sizes, obtain the best match between the two objects to compute the difference criterion by using a motion-estimation-like process. Let the area of each object O_ibe A_i, its difference criterion be d_iand the difference criterion corresponding to frame n be D_n. Then the total criterion will be: $D=\frac{\sum A_1*D_n}{\sum _1{A}_1}$

[0039] 4. From the previous step identify pairs I_m, I_m+1that have a suspected scene change. Let the corresponding GOP's be G_test[1], G_test[2] . . .

[0040] 5. For each GOP from the previous step carry out scene change detection using:

[0041] (a) P frame to P frame comparison using a bit allocation (bits per macroblock) criterion;

[0042] (b) If no scene change is detected in the previous step, let the GOP previous to the tested GOP be GOP_prevand the GOP succeeding the tested GOP be GOP_next. Then take the last P frame of GOP_prevand compare it with the first P-frame of GOP_test, using the bits per macroblock criterion, and similarly take the last P-frame of the tested GOP and compare it with the first P-frame of GOP_next. If a scene change is then detected, declare the scene change occurrence at the corresponding I-frame or else declare failure of the bit allocation based algorithm. If the algorithm fails, use the DC image-based algorithm for the next sequence.

[0043] 6. Segment S into shots based on the above scene change detection.

[0044] 7. In the MPEG-4 case, repeat the same procedure within each shot to detect abrupt object changes.

[0045] It has also been observed that an ambiguity may arise when a scene change is located either at an I-frame or at a P-frame that immediately follows an I-frame. Recall that the definitive scene change processing steps are taken with respect to P-frame information after a suspected scene change has been identified by inspecting I-frame information. Then, if the GOP sequence is taken as I₁P₁P₂P₃—I₂and a spike is detected in the bit rate difference function at the comparison of P₁and P₂, according to the prior approach of Feng et al described above, a scene change would be declared between P₁and P2. However, the change actually may have occurred between I₁and P₁or at P₂.

[0046] If the scene change actually occurred between I1 and P₁, the bit allocation of the latter frame will differ sufficiently from that of P₂to imply the occurrence of a scene change at that point, even though the two adjacent P-frames are, in fact, similar in content. In fact, it is the similarity between P₁and P₂which gives rise to the difference in bit allocations in the two. The ambiguity in the timing of the scene change can be resolved by reference to the bits spent on motion vectors in the two adjacent P-frames. That is, the sum total of bits spent on motion vectors is calculated for each frame whenever the ambiguity possibility arises ( i.e. when the bit allocation criterion as described below indicates occurrence of a scene change between a P₁and a P₂frame). A scene change between I₁and P₁will induce a spike in the motion vectors spent on P₁. If the scene does not change immediately following such a spike, the number of bits spent on motion vectors in the following frames will display a continuity in magnitude which is not shared by the bits spent on the motion vectors of P1. By comparing the bits spent on motion vectors for P₁, to the following frames, the scene change can be defined as occurring between I₁and P₁. If the scene change occurred, in fact, at P2, then the anomalous motion vector allocation will be seen at P₂. It is a computationally simple process to analyze this motion vector information in the manner described.

[0047] The Bit Allocation Based Criterion.

[0048] For each object, construct a “bit rate matrix” which consists of the number of bits required to encode each macroblock. Let R={r(i,j)} and S={s(i,j)} be two rate matrices, then the rate difference between R and S is $d\left(R,S\right)=\sum _{i,j}\left|r\left(i,j\right)-s\left(i,j\right)\right|$

[0049] where r(i,j) is the number of bits required by the (i,j)^thmacroblock of the object in one P-frame and s(i,j) is the number of bits required by the corresponding block in the next P-frame. Given a sequence of rate matrices R_m,m=1,2 . . . N+1, we can obtain the normalized rate difference sequence RP_m,m=1,2, . . . , N as ${\mathrm{RP}}_m=\frac{d\left(R_m{\mathrm{RP}}_{m+1}\right)}{T_m}$

[0050] where T_mis the total number of bits required by the m^thobject of the sequence RP_m. Use a sliding window (i.e. a predetermined number of frames before and after a frame of interest) to process the rate difference sequence RP_mso as to capture local variation. Declare a scene change from R_ito R_i+1if

[0051] 1. The difference RP₁is the maximum within a symmetric sliding window of size 2k−1 frames and

[0052] 2. The difference RP₁is also n times the second largest maximum in the sliding window. k=3 and n=2 are used in examples that have been tested. The choice of these parameters depends on empirical data as well as frame rate, the frequency of periodic I-frames, and additional factors. Note that the rate difference can be computed only between two I frames/objects or between two P frames/objects. In other words, all the frames in the sequence R_ishould all be either I or P frames (objects). Note also that in an MPEG-4 sequence, all the objects need not necessarily be “refreshed” with intra-coding at the same time.

[0053] DC Sequence Based Criterion.

[0054] In this approach, a sequence of DC images (objects) X−{dc(i,j)} is constructed where dc(i,j) is the DC value of the (ij)^thmacroblock of the image (object). Extraction of DC values from Intra- coded frames or objects is simple since it only requires entropy decoding as noted above, but extraction of DC values from Predictive or P frames (objects) requires more computation and memory. Thereafter, a difference sequence is constructed as in the previous sequence using one of several possible metrics. The metric (d_c(X,Y) is used between two frames X and Y as defined below: $d_c\left(X,Y\right)=\sum _{i,j}\left(\left|x_{i,j}-y_{i,j}\right|\right)$

[0055] One can therefore construct a sequence d_c(X_i,X_i+1) for the sequence and use the previously described sliding window approach to detect scene changes.

[0056] Fade Detection Using Changes in Bits Taken to Encode DC Components of Residuals.

[0057] It has been observed that, when there is a gradual scene change, every block of the image includes a DC correction term, since the image is fading in from a completely black frame or fading out to a completely black frame. With this in mind, it has been found that bit allocation profiles for DC components of residual blocks provide an indicator for fade detection. In accordance with one aspect of the present invention, a method of fade detection comprises the following steps.

[0058] 1. Compare the DC images of successive I-frames to locate suspected scene changes. This has been found to be necessary for the method of detecting abrupt scene changes as described above. This step helps save computation, since a search is made thereafter for a scene change only in the signal segments in which successive I-frames differ widely, thus avoiding processing the entire signal sequence.

[0059] 2. For each P-frame in the regions in which there is a suspected scene change, the number of blocks with negative DC components as well as the number of blocks with positive DC components are counted. For the MPEG-2 as well as the MPEG-4 case, this step would be straightforward from the VLC parsing, since every non-zero DC component will be allocated a non-zero number of bits and a sign bit that indicates whether the component is positive or negative. Zero DC components are indicated by the run-lengths and thus can be readily skipped.

[0060] 3. Determine the characteristic of the two numbers obtained above versus the frame number, and determine the regions in which suspected scene changes have been located according to step 1 above.

[0061] 4. Declare a fade-out if the number of negative transitions is consistently greater than or equal to 60% of the total number of non-zero transitions over a period of time (number of frames) corresponding substantially to a normal scene change interval (approximately one second). Conversely, declare a fade-in if the number of positive transitions meets the aforementioned threshold.

[0062] This fade detection technique capitalizes on the motion search carried out by the encoder. It measures the rate spent on encoding the DC difference between a particular macroblock and its closest match in the previous frame. As a still further refinement of scene change detection, the possibility of a scene change occurring at a B-frame between two P-frames also may be detected, once it has been determined that the two particular P-frames lie between two I-frames for which a scene change is indicated. By so defining the scene change interval, it will be known that the scene change occurred not later than the last P-frame in that interval. However, the scene change may have occurred at the first P-frame or at a B-frame intermediate the two P-frames. To make the further determination, advantage is taken of the fact that the bits encoded as part of the B-frame information include a FLAG which identifies which of the preceding or succeeding P-frames served as the reference frame for constructing the B-frame in question. The B-frame is constructed using either forward or backward or bidirectional comparisons with adjoining P-frame information. The FLAG will identify the particular comparison employed.

[0063] By inspecting the flag, one can determine the following:

[0064] 1. If the B-frame relied on the proceeding P-frame as a reference, than the minimum difference existed in that direction and the scene change should be identified as occurring at the later P-frame;

[0065] 2. If the B-frame relied on the following (later) P-frame as a reference, than the minimum difference existed in that direction and the scene change should be identified as occurring at the B-frame;

[0066] 3. If the B-frame relied on a bidirectional comparison, no scene change occurred between the P-frames and, therefore, the scene change should be identified as occurring at the first (earlier) P-frame.

[0067] While the invention has been described in terms of a preferred embodiment, various modifications may be employed without departing from the scope of the invention, which is set forth in the following claims.