Method and apparatus for scene change detection in digital video compression

A method of encoding a picture in an MPEG2 compliant digital video encoder. The method calculates a contrast function, EQU Contrast=.SIGMA..vertline.P(j)-P(j+1).vertline. and thereafter calculates a quantization adjustment function therefrom EQU M(i+1)=C(i+1)/C(i)!M(i), where C=Contrast, P(j) is the luminance or chrominance of the j.sup.th pixel, and M(i)is the average quantization of the i.sup.th picture. The quantization or picture type is adjusted in response to the contrast function, C.

FIELD OF THE INVENTION 
The invention relates to compression of digital visual images, and more 
particularly to temporal compression, that is the compression of 
redundancy between pictures. Redundancy between pictures is reduced, or 
even eliminated, through the use of motion vectors. In compression under 
the MPEG2 Standard the macroblock data and vector data are quantized. When 
using quantized data, picture uniformity is a function of quantization 
uniformity. That is, the requirement to provide uniformity in a picture 
means that the quantization must vary smoothly from macroblock to 
macroblock. According to the invention the quantization is adjusted to 
maintain a high degree of quantization uniformity. 
BACKGROUND OF THE INVENTION 
Within the past decade, the advent of world-wide electronic communications 
systems has enhanced the way in which people can send and receive 
information. In particular, the capabilities of real-time video and audio 
systems have greatly improved in recent years. In order to provide 
services such as video-on-demand and videoconferencing to subscribers, an 
enormous amount of network bandwidth is required. In fact, network 
bandwidth is often the main inhibitor to the effectiveness of such 
systems. 
In order to overcome the constraints imposed by networks, compression 
systems have emerged. These systems reduce the amount of video and audio 
data which must be transmitted by removing redundancy from individual 
pictures and from the picture sequence. At the receiving end, the picture 
sequence is decompressed and may be displayed in real-time. 
One example of an emerging video compression standard is the Moving Picture 
Experts Group ("MPEG") standard. Within the MPEG standard, video 
compression is defined both within a given picture and between pictures. 
Video compression within a picture is accomplished by conversion of the 
digital image from the time domain to the frequency domain by a discrete 
cosine transform, followed by quantization, variable length coding, and 
Huffman coding. Video compression between pictures is accomplished via a 
process referred to as motion estimation, in which a motion vector is used 
to describe the translation of a set of picture elements (pels) from one 
picture to another. 
The amount of bits needed to represent any one picture is directly related 
to the content and the complexity of the individual picture. Thus, each 
picture may have a different number of bits. However, effective 
transmission bandwidth utilization requires a relatively constant bit 
rate. The process of rate control is used to regulate and maintain 
approximately constant bit rate to the decoder. There are three main 
functions for bit rate control: 
(1) Picture bit allocation. 
(2) Macroblock rate control. 
(3) Macroblock adaptive quantization. 
Picture bit allocation depends on picture complexity, the requirement to 
maintain a relatively constant bit rate, and the requirement to observe 
rate control buffer limits. Macroblock rate control regulates the produced 
bits to match allocations. Macroblock adaptive quantization produces 
uniformly noticeable distortion. 
The requirement to produce uniformity in a picture means that the 
quantization varies smoothly from macroblock to macroblock. In a sequence 
of pictures within a single view, the pictures change only slightly from 
one picture to the next picture. However, when there is a change in 
picture content the quantization can and will vary sharply. Thus, a need 
exists for scene change detection to determine if two adjacent pictures 
are of similarity or are of large difference. 
OBJECTS OF THE INVENTION 
It is a primary object of the invention to provide scene change detection 
to determine if two adjacent pictures have similarity or have large 
differences. 
SUMMARY OF THE INVENTION 
These and other objects of the invention are achieved by the method of 
encoding the digital video datastream. The method first calculates a 
contrast function, 
EQU C=.SIGMA..vertline.P(j)-P(j+1).vertline. 
where C is the Contrast, and P(j) is the luminance or chrominance of the 
j.sup.th pixel, and thereafter calculates a quantization adjustment 
function therefrom, 
EQU M(i+1)=C(i+1)/C(i)!M(i), 
where M(i) is the average quantization of the i.sup.th picture. The 
quantization is adjusted in response to the contrast function, C.

DETAILED DESCRIPTION OF THE INVENTION 
The invention relates to MPEG and HDTV compliant encoders and encoding 
processes. The encoding functions performed by the encoder include data 
input, motion estimation, macroblock mode generation, data reconstruction, 
entropy coding, and data output. Motion estimation and compensation are 
the temporal compression functions. They are repetitive functions with 
high computational requirements, and they include intensive reconstructive 
processing, such as inverse discrete cosine transformation, inverse 
quantization, and motion compensation. 
More particularly the invention relates to motion estimation, compensation, 
and prediction, and even more particularly quantization during motion 
estimation, compensation, and prediction. Motion compensation exploits 
temporal redundancy by dividing the current picture into blocks, for 
example, macroblocks, and then searching in previously transmitted 
pictures for a nearby block with similar content. Only the difference 
between the current block pels and the predicted block pels extracted from 
the reference picture is actually compressed for transmission and 
thereafter transmitted. 
The simplest method of motion compensation and prediction is to record the 
luminance and chrominance, i.e., intensity and color, of every pixel in an 
"I" picture, then record changes of luminance and chrominance, i.e., 
intensity and color for every specific pixel in the subsequent picture. 
However, this is uneconomical in transmission medium bandwidth, memory 
bandwidth, processor capacity, and processing time because objects move 
between pictures, that is, pixel contents move from one location in one 
picture to a different location in a subsequent picture. A more advanced 
idea is to use a previous or subsequent picture to predict where a block 
of pixels will be in a subsequent or previous picture or pictures, for 
example, with motion vectors, and to write the result as "predicted 
pictures" or "P" pictures. More particularly, this involves making a best 
estimate or prediction of where the pixels or macroblocks of pixels of the 
i.sup.th picture will be in the i-1.sup.th or i+1.sup.th picture. It is 
one step further to use both subsequent and previous pictures to predict 
where a block of pixels will be in an intermediate or "B" picture. 
To be noted is that the picture encoding order and the picture transmission 
order do not necessarily match the picture display order. See FIG. 2. For 
I-P-B systems the input picture transmission order is different from the 
encoding order, and the input pictures must be temporarily stored until 
used for encoding. A buffer stores this input until it is used. 
For purposes of illustration, a generalized flow chart of MPEG compliant 
encoding is shown in FIG. 1. In the flow chart the images of the i.sup.th 
picture and the i+1.sup.th picture are processed to generate motion 
vectors. The motion vectors predict where a macroblock of pixels will be 
in a prior and/or subsequent picture. The use of the motion vectors 
instead of full images is a key aspect of temporal compression in the MPEG 
and HDTV standards. As shown in FIG. 1 the motion vectors, once generated, 
are used for the translation of the macroblocks of pixels, from the 
i.sup.th picture to the i+1.sup.th picture. 
As shown in FIG. 1, in the encoding process, the images of the i.sup.th 
picture and the i+1.sup.th picture are processed in the encoder 11 to 
generate motion vectors which are the form in which, for example, the 
i+1.sup.th and subsequent pictures are encoded and transmitted. An input 
image 111' of a subsequent picture goes to the Motion Estimation unit 43 
of the encoder. Motion vectors 101 are formed as the output of the Motion 
Estimation unit 43. These vectors are used by the Motion Compensation Unit 
41 to retrieve macroblock data from previous and/or future pictures, 
referred to as "reference" data, for output by this unit. One output of 
the Motion Compensation Unit 41 is negatively summed with the output from 
the Motion Estimation unit 43 and goes to the input of the Discrete Cosine 
Transformer 21. The output of the Discrete Cosine Transformer 21 is 
quantized in a Quantizer 23. The output of the Quantizer 23 is split into 
two outputs, 121 and 131; one output 121 goes to a downstream element 25 
for further compression and processing before transmission, such as to a 
run length encoder; the other output 131 goes through reconstruction of 
the encoded macroblock of pixels for storage in Frame Memory 42. In the 
encoder shown for purposes of illustration, this second output 131 goes 
through an inverse quantization 29 and an inverse discrete cosine 
transform 31 to return a lossy version of the difference macroblock. This 
data is summed with the output of the Motion Compensation unit 41 and 
returns a lossy version of the original picture to the Frame Memory 43. 
As shown in FIG. 2, there are three types of pictures. There are "Intra 
pictures" or "I" pictures which are encoded and transmitted whole, and do 
not require motion vectors to be defined. These "I" pictures serve as a 
source of motion vectors. There are "Predicted pictures" or "P" pictures 
which are formed by motion vectors from a previous picture and can serve 
as a source of motion vectors for further pictures. Finally, there are 
"Bidirectional pictures" or "B" pictures which are formed by motion 
vectors from two other pictures, one past and one future, and can not 
serve as a source of motion vectors. Motion vectors are generated from "I" 
and "P" pictures, and are used to form "P" and "B" pictures. 
One method by which motion estimation is carried out, shown in FIGS. 3a and 
3b, is by a search from a macroblock 211 of an i.sup.th picture throughout 
a region of the next picture to find the best match macroblock 213. 
Translating the macroblocks in this way yields a pattern of macroblocks 
for the i+1.sup.th picture, as shown in FIGS. 4a and 4b. In this way the 
i.sup.th picture is changed a small amount, e.g., by motion vectors and 
difference data, to generate the i+1.sup.th picture. What is encoded are 
the motion vectors and difference data, and not the i+1.sup.th picture 
itself. Motion vectors translate position of an image from picture to 
picture, while difference data carries changes in chrominance, luminance, 
and saturation, that is, changes in shading and illumination. 
Returning to FIGS. 3a and 3b, we look for a good match by starting from the 
same location in the i.sup.th picture as in the i+1.sup.th picture. A 
search window is created in the i.sup.th picture. We search for a best 
match within this search window. Once found, the best match motion vectors 
for the macroblock are coded. The coding of the best match macroblock 
includes a motion vector, that is, how many pixels in the. y direction and 
how many pixels in the x direction is the best match displaced in the next 
picture. Also encoded is difference data, also referred to as the 
"prediction error", which is the difference in chrominance and luminance 
between the current macroblock and the best match reference macroblock. 
The number of bits needed to represent any one picture is directly related 
to the content and the complexity of that picture. Thus, each individual 
picture may have a different number of bits. The process of bit rate 
control is used to regulate and maintain the bit rate to the encoder 
approximately constant. There are three main functions for bit rate 
control: 
(1) Picture bit allocation. 
(2) Macroblock rate control. 
(3) Macroblock adaptive quantization. 
Picture bit allocation depends on picture complexity, the requirement to 
maintain a relatively constant bit rate, and the requirement to observe 
rate control buffer limits. Macroblock rate control regulates the produced 
bits to match allocations. Macroblock adaptive quantization produces 
uniform distortion. 
The requirement to produce uniformity in a picture means that the 
quantization varies smoothly from macroblock to macroblock. In a sequence 
of pictures within a single view, the pictures change slightly from one 
picture to the next picture. Thus, within a scene the average quantization 
value of a picture is a good starting quantization value for the next 
picture. 
However, where there is a scene change the average quantization may, and 
frequently does, change abruptly from one picture in a sequence to the 
next picture in the sequence. Thus, a need exists for scene change 
detection to determine if two adjacent pictures are of similarity or are 
of large differences. 
The scene change can be of, for example, Luminance difference between 
frames, or Chrominance difference between frames. 
The contrast or difference measurement is determined by 
EQU C=.SIGMA..vertline.P(j)-P(j+1).vertline. 
where C is the contrast, P(j) is the luminance or chrominance of the 
j.sup.th pixel, j is the pixel location in the picture and the summation 
is taken over the entire picture. 
A large C value indicates higher differences between pixels within the 
pictures, that is, higher picture complexity. The encoder process can be 
adjusted according to the complexity of the picture. 
In the case of field based coding, the calculation of contrast is divided 
into odd and even luminance and chrominance. These field based values for 
C are used to adjust the quantization on a field picture boundary. For 
this purpose the calculation of C is performed on pixels of the same 
parity field. That is, 
EQU C.sub.lum,odd =.SIGMA..vertline.P(j)-P(j+1).vertline. 
where P(j) and P(j+1) are luminance pixels of the odd field, and 
EQU C.sub.lum,even. =.SIGMA..vertline.P(k)-P(k+1).vertline. 
where P(k) and P(k+1) are luminance pixels of the even field. 
Similarly, 
EQU C.sub.chr,odd =.SIGMA..vertline.P(j)-P(j+1).vertline. 
where P(j) and P(j+1) are chrominance pixels of the odd field, and 
EQU C.sub.chr,even =.SIGMA..vertline.P(k)-P(k+1).vertline. 
where P(k) and P(k+1) are chrominance pixels of the even field. 
Furthermore, the calculation of C for chrominance data should be done 
independently for the Cb and Cr components of color. This leads to the 
following method for determining values of contrast for the chrominance 
picture data, 
EQU C.sub.chr,odd,Cb =.SIGMA..vertline.P(j)-P(j+1).vertline. 
where P(j) and P(j+1) are horizontally adjacent Cb pixel components of the 
odd field. The same can be done for Cr, 
EQU C.sub.chr,odd,Cr =.SIGMA..vertline.P(j) P(j+1).vertline., 
and for the even field, 
EQU C.sub.chr,even,Cb =.SIGMA..vertline.P(j)-P(j+1).vertline., 
EQU C.sub.chr,even,Cr =.SIGMA..vertline.P(j)-p(j+1).vertline.. 
Including the chrominance components in the contrast operations enables the 
encoder to detect changes in which the luminance component remains 
constant, but the chrominance is changing. This results in a much more 
accurate starting quantization for the next picture. 
When the encoder processes a picture the quantization is adjusted according 
to 
EQU M(i+1)=C(i+1)/C(i)!M(i), 
where M(i) is average quantization of the i.sup.th picture. 
A large value of C indicates more complexity and details in the picture. A 
smaller value of C indicates less complexity and details in the picture 
and a smaller quantization value. When the encoder goes from a picture of 
small C to the next picture of larger C, a relatively larger quantization 
is needed to maintain a relatively equal number of bits produced in each 
picture. The ratio 
C(i+1)/C(i)! 
allows the amount of changes needed to be based on picture contrast. This 
adjustment, at the start of the picture, allows a better and faster 
control in the required adaptive quantization and bit regulation during 
coding. In IPB (Intra-Predicted-Bidirectional) coding, a large picture 
contrast can be used by the encoder to force an I (Intra) picture. 
While the invention has been described with respect to certain preferred 
embodiments and exemplifications, it is not intended to limit the scope of 
the invention thereby, but solely by the claims appended hereto.