Note: Descriptions are shown in the official language in which they were submitted.
2~7~950
M~T~030
DE~IV~TION ~ND USE OF MOTION VECTORS IN ~ DIFFERENTIA~
PUL,SE CODE MODUL~TION SYSTEM
BACKGROUND OF THE INVENTION
In a Differential Pulse Code Modulation (DPCM)
system referred to as Independent Search, IS, that has
. been suggested by the Moving Picture Experts Group and-
described in articles 1, 2 and 3, identified at the end
of the specification that are hereby incorporated by
reference, three types of frames are used as illustrated
in Fig. 1. The letters indicate the type o~ frame, and
the numerical subscripts indicate the order of occurrence
of the frames at the input to the system. I0 and I9 are
called intraframes. Each of these intraframes is encoded
;
,
dlm-015 ~ mata-030~patO01
.. ...
. , ~ ' , , ' .
. . .
~,
.
~i~ ' 2~78~0
M~ 030 - 2 -
'
,
by using only pixels within the rame. The encoded
frames are then transmitted.
~ predicted frame such as P3 is encoded from I~
in the following manner. P3 is partltioned into
identical blocks, e.g. having eight pixels in a ~lde,
that are called motion blocks. For each mo~ion block in
- P3, a search is made in the I0 frame for a block of the
same shape and size that matches the motion block. When
the matching block is located, its po~ition relative to
the motion block is indicated by a motion vector (mv)
representing the number of pixels lef~ or right and the
number of pixels up or down from the motion block to the
matching block. These motion vectors axe transmitted.
Also, the differences between the motion blocks and
corresponding matching blocks are formed. This is called
;~ residue, and it is encoded and transmitted. At the
decoder, the Io frame is decoded and the predicted frame
P3 is formed by displacing appropriate matching blocks in
I0 using the motion vectors. The residue for the various
blocks is then added. The frame P6 is encoded in like
manner from P3. When a number of P frames have been
encoded from preceding P frames in this manner, the
accumulative error may become so great that another I
frame is sent as described, and a new series of P frames
is formed from it. The I and P frames are called anchor
fremes.
;' '
. . .
: . .
";
2~ 9~0
M~rA-030 - 3 -
The s ~rames occur between anchor ~rames, and
the motio~ vectors u~ed in encoding them are illustrated
in Fig. 2. The firs~ numeral in a subscript of a motion
vector mv indicates the frame in which a motion block i9
located and the second numeral indicates the frame being
searched for a matching block. Thus, in encoding the
frame P3 as noted above, mv30 i9 a motion vector
indicating the position of a block in I0 that matches a
motion bloclc in frame P3 and mv63 i9 a motion vector
~ 10 indicating the position of a block in P3 that matches a
; motion block in P6.
For each motion block in a B frame, two motion
vectors are deri~ed, one referenced to a subsequent
anchor frame and one anchor referenced to a previous
anchor frame. Thus, mv23 indicates the position of a
matching block in P3 relative to a motion block in B2 and
.~
mv20 indicates the position of a matching block in I0
~` relative to a motion bloclc in B2. What to transmit to
;~ .
the decoder can be determined by finding for each block
which of the following modeg of operation produces the
least Mean Square Error (MSE~ as this will reduce the bit
~ xate required. Eor each motion block, the MSE i9
,~ calculated by adding the squa~es of the differences
between the corresponding pixels of the motion block and
the matching block and dividing the rasult by the number
of pixels in the motion block. In what is called a
backward mode, the MSE is calculated between the mo~ion
..~.
'
,: `
~' ~
, ~ .
.. ; ,, . r~ ; r ~ C.~ , S; ' "~:
r ' , ~ ~ ' .
~' ',
... .
~ .
:
.
2~7~g~0
MAT~-030 - ~ -
block in s2 and the matching block in P3, and in a
forward mode, the MSE calcu]ation is done with the
matching bloclc being in I0. In what is called an
interpolative mode, the matching blocks in P3 and I0 are
averaged, and the MSE i9 calculated with this averaged
matching bloclc. Whichever mode produces the least MSF is
conveyed to the decoder. Thus, if the backward mode
produces the least MSE, a motion vector mv23 i3
transmitted along with an indication that it is the
backward vector, and if the forward mode produces the
least MSE, a motion vector mv20 is tran~mitted along with
an indication that it is the Eorward vector. If the
interpolative mode produces the least MSE, both vectors
mv23 and mv20 are transmitted along with an indication
that both vectors are being transmitted. Of cour9e, for
the selected mode, the re~idue obtained by subtracting
the matching block from the motion block i9 also encoded
and transmitted.
Fig. 1 shows the various frames in the order
that they are received by the encoder and pre~ented to
the viewer, and Fig. 3 illustrates the order in which the
frame~ of Fig. 1 are procesged. Both P 3 and Io must be
available before B-2 and B 1 can be processed as
described above, and Io must be retained in memory until
P3 is available before B1 and B2 can be processed. The
frame order of Fig. 3 is also the order in whlch the
frames are transmitted.
,, .
,
2~8~
MAT~-030 5
In sw~nary, transmission must include the Io
frames, the P to I frame motion vectors such as mv30, the
residue for predicted frame~ such as P3, the residue for
each B frame that results from the selected mode of
operation and at least one motion vector for each B frame
along with signals indicating the mode of operation that
has been selected. How a decoder can reconstruct the
frameY from this information is thought to be obvious.
In article 4, which i~ i~corporated herein by
reference, a differential pulse code modulation system i9
described that i9 like the IS system de~cribed above
except for the fact that the motion vectors for the B
frames ~re derived from motion vectors such as mv30 or
mv63 of Fig. 2 that indicate the relative po~ition of a
block in an anchor frame that matches a block in the next
anchor frame. The motion vector selected for a motlon
block in a B frame is the motion vector for a block in
the later anchor frame that is in the same spatial
position. If linear motion i9 assumed, a motion vector
mv20 (i, j) would equal 2/3 mv30 (i, j) and mv23 (i, j3
would equal -1/3 mv30 (i, j). While this method has the
advantage o~ not transmitting motion vectors for the B
~rames, the motion vectors that are used re~uire the
transmission of a significant amount of residue in most
cases.
. ' '
. ~ ~
2~78~
MA'l`~-030 - 6 -
In article 5, which is incorporated herein by
reEerence, the bloclcs in khe earlier and later anchor
frames that are at the ends of a vector such as mv30 or
mv63 that pass through a block in a B frame are averaged
to produce the data in that block. ~lthough this method
doe~ not requlre the transmi~ion oE motion vectors for
the B frames! it suffers from gap and overlap problems.
I
BRIEF DESCRIPTION OF THE INVENTION
In accordance with this invention, motion
vectors for a block in a B frame are derived ~rom the
motion vector f~r a motion block in tlle followlng anchor
frame whose pro~ection along its motion vector to the
previous anchor frame has the most overlap with that
bloc]c. Thus, it is not necessary, ag on the IS system,
to find matching bloclcs in subsequent and previou~ anchor
` frames so as ~o find motion vector~3 suc~ ~ mv20 and mv23
! 0~ Fig. 4- Instead, the motion vectors for a motion
block in a B2 frame are mv20 (i, j) = 2/3 mv30 (k, 1) and
m23 (i, j) = -1/3 mv30 (k, l), where k and l are
selected, as explained in the description of Fig. 4.
Once these B frame motion vector~ are derived, they can
j be used at the encoder in the various modes discussed in
connection with the IS system to determine which mode
produces the least residue. It i~ then only nece~sary to
transmit the mode rather than the motion vectors.
'
2~78~5~
M~TA-030 - 7 -
Whereas the mo~ion vector for the later anchor
frame is expressed in integral numbers of pixel spacing,
the motion vector for a bloc)c in a B frame may be
expressed in terms o~ Eractlons of pixel spacings, This
i.s because the motion vector for a B Erame is a fraction
of the motion vector for a P frame. Where two B frame~
Bl and B2 are used as in the drawings, the resolution of
the shorter motion vectors for B frame motion blocks is
1/3 of a pixel spacing and that for the longer motion
vector is 2/3 of a pixel spacing. Therefore, when these
motion vectors are used in reconstructing a frame from
pixels and interpolation i9 used, a better image can be
formed. In order to obtain an independent motion vector
with 1/3 pixel resolution for a motion block in the B2
frame, nine times as many locations in each of the I0 and
P3 frames wouid have to be examined.
The major advantages oE deriving the motion
vectors for the B frame from the P frame vectors in
accordance ~ith this invention lie in the fact that in
most situations less residue i9 produced than in the IS
system and no motion vectors for the B frames need to be
~ent. As in an IS sy~tem, a signal indicating mode has
to be sent, but it requires significantly fewer blts than
a motion vector.
: (
2~7~
M7~TA- O 3 0 ~ 8
BRIEF DESCRIPTION OF T~IE DR7~WINGS
Fig. 1 illustrates the I, ~ and P ~rames u~ed
in a IS s~s~em;
Fig. 2 illustrate~ the motion vector~ used in
an IS system;
. Fig. 3 illustrates the order in which the
frames are processed in an IS system;
10 Fig. 4 illustrates how motion vectors for B
frames are derived from motion vectors Eor P frames in
accordance with this invention;
Fig. 5 illustrates the four blocks in a B frame
that can be intercepted by the projection of a motlon
block in the P frame along its motion vector to a
previous anchor rame;
Fig. 6 shows the input and outputs of an area
overlap motion vector calculator used in an er~odiment of
this invention;
Figs. 7, 8, 9 and 10 constitute a flow chart
for the operation of an area overlap motion vector
calculator oE this invention u~ing t~e upper left corner
of a motion block in a P frame as a poin~ of reference;
'
'
2~7~
MATA-030 9
Fig. 11 is a block ~iagram oE an encoder for a
system employing independent search, IS;
F'lg. 12 i9 a bloc]c diagram of means for
selecting the mode for predicting B frames and for
forming the pred.icted B Erame in an IS system;
Fig. 13 is a block diagram of the decoder for
an IS system;
Fig. 14 is a block diagram of an encoder using
the area overlap method of this invention for determining
motion vectors for predicted blocks in B frames;
Fig. 15 is a block diagram of one means for
selecting the mode for predicting B frames and for
forming the predicted B frames;
Fig. 16 is a bloc]c diagram of a second means
for selecting the mode for predicting B frames and for
forming the predicted B frames;
Fig. 17 is a block diagram of a decoder for a
system using the area overlap method of this invention
for determining motion vectors;
Fig, 18 illustrates the order in which frames
are received and processed at the decoder; and
: .
.
,
- 2~7~0
MATA-030 - 10 -
Fig. 19 illustrates the order in which frames
are output Erom the decoder to image reproduction mean~.
DErt'~I~ED DESCRIPTION OF T~IE INVEMTION
Reference is made to Figs. 4 and 5 for an
explanation of the area~overlap method used by this
invention to derive the mokion vectors for a bloc]c in a B
frame. In Fig. 4, frames Io, sl, ~2 and P3 are shown.
They are partit~oned into identical rectangular block~ of
pixels that are Ll pixels.wide and L2 pixel~ hlgh and
located in accordance with i and j coordinates having an
origin at the upper left corners of the frames. Within
each frame, pixel~ are identified by x, y coordinates.
In ~ig. 4, a motion bloclc at i - 0, ~ - 0 of a
P3 frame i9 shown by the shading as being projected
toward the Io frame in a direction parallel to its motion
vector 2. The area of intersection of the projection
with. the.Bl frame i9 shown by a rectangle 4, and the area
of intersection of the projection with the ~2 frame is
shown by a rectangle 5.
A method for determining the area of overlap of
the area of inter~ection ~ with the various blocks of the
Bl frame will now be explained by xeference ~o Figs. 4
2~78~
MAT~-030 - 11 -
and 5. Although any point in a motion block of P3 could
be used as a reference, the upper leEt hand corner 6 is
used in th:is particular example. Its projection ls shown
as intersecti~g the s1 frame at 6~ in a bloc]c at j = 0, i
- 2. Observation will ~how that the area o~ intersection
4 can only overlap foux block~ in ~1~ the one inter9ected
by the projection of the corner 6, which is 6', the one
to the right, the one below and the one on a diagonal,
i.e. those at j = 0, i = 2; j = 1, i - 2, j = 0, i = 3
and j = 1,~i = 3.
-The area in pixels of the overlap with each of
the four block~ can be determined by the following
formula:
AO = (L1 - ¦x - u¦) (L2 - ¦~ - v¦)
~ L1 ~2 + ¦x - u¦ ¦Y - v¦ - L2 ¦x u¦ - L1 ¦Y - v¦
where L1 equals the width of a mo~ion block in pixels, L2
the height of a motion block in pixels, u, v are the
values of the x, y coordinates in pixels of a reference
point having a defined relationship to the projection of
a motion block in the P frame onto a B Erame, and x, ~
~ ,
:"
2~7~
M~TA-030 - 12 -
are the coordinate~ in pixels of a xeference point having
the same defined relation3hip to a B frame motion block.
By way oE example, ~uppose we wish to find the
area oE overlap of the projection of the motion bloclc in
the upper leEt corner of the P3 frame of FicJ. 4 with the
motion bloclc at j = 1, i = 2 of the Bl frame. As shown
in Fig. 5, L~ = 16 pixels and ~2 = 8 pixels. ~y
observation, the width of the overlap is 12 pixels and
its height is 6, so that the de3ired area is.l2 x 6 = 72
pixels. If the defined relationship is that the
reference point is ~he top le~t corner of a block, then
u = 12 and v ~ 18 and x = 16 and ~ = 16 so that the area
of overlap in accordance with the formula is:
AO = [16 - ¦16 - 12¦] [8 - ¦16 - 18¦]
= [16 -4] [~ - 2]
= 12 x 6 = 72
As illustrated by the flow charts of Figs. 6
through 10 for calculating the areas of overlap ~0, the
area~ of overlap in each of the blocks of a s frame are
derived for each motion block in a P frame and the vector
for the block in the B fr~ne is derived from the vector
2~78~
M~TA-030 - 13 -
of the motion block in the P frcime whose pro;ection has
the most overlap.
ReEerence is now rnade to Figs. 6 through 10 for
a description of a flow chart of a way for determining
the motion vectors of a B frame in accordance with the
algorithm just described. It is thought that the
comments in the various bloclss malce the chart self-
explanatory, but its general operation i~ as follows.
The following terms are.used:
,
T - frame number;
N - (N-l) B frames between ahchor frames;
Axea Table - current best area overlap for each B
frame motion block;
Best mv - current be~t P frame motion vector
~ 15 for each B frame motion block;
; d - distance to the previous anchor
frame;
(i, ~) - location of P and B frame motion
blocks. From top left corner, i
motion blocks down, j motion blocks
'
8 ~ ~ ~
MATA-030 - 1~ -
to the right; are used as block index
in loops
tlBl, ~Bl), (lB2, ~B2), ~iB3, ~B3), (lB4, ~B4) - location
of B frame motion blocks. From top
left corner iBk motion bloclc~ down,
~Bk motion blocks to the right;
(x, y) - pixel coordinates bE top left corner
of B frame motion blocks;
(tlvP, tlhP) - pixel coordinates of top left corner
of P-frame motion block in the P-
frame;
(u, v) - pixel coordinates of top left corner
of P frame motion block projected
onto B frame;
k - B frame motion block loop counter;
and
AO - area overlap.
~;
.
In a block 7 of Fig. ~, the motion vectors
(PMv) from the next anchor Erame to the previou9 anchor
'
.
9~ ~
M~T~-030 ~ 15 -
frame are supplied to the calculator, and it s~pplie~, in
a manner explained in connection with Figs. 7 through 10,
the forward and backward motion vectors for a B frame.
l'he blocks a, lo, 12 and 14 of Fig. 7 are for
initialization. In bloc)c 16, the pixel coordinate9 of
the top left corner o~ a P frame motion bloclc are found,
and using the P frame motion vector~, block 1~ locates
the coordinate~ of ~he top left corner of the pro~ection
block onto the s frame of interest. In bloc]c 20, the
block in the s frame through which ~he projection of the
upper left corner of the motion block in the P frame
passes is identified, and in block 22 the other three
blocks where there may be overlap with the projected
motion block in the P frame are identified. In block 24,
k i~ set to l and the next time through the loop it will
be set at 2.
In block 26, the x and y coordinates in pixels
are determined for each of the blocks identified in
blocks 20, 22, and 2~, and the formula for AO is applied
to each of them. A~ the AO for each of the four blocks
in a B frame i~ calculated, a decision is made, block 30,
a~ to whether the ~O is grea~er than an AO previou~ly
calculated. If it i~ larger, a block 32 updates a table
for that s block, and the procedure goe~ to a block 34
which add~ 1 to k. If block 30 indicates that the AO i~
not larger than what ig in the table, the table i.~ not
:'
:
2~78~0
~r~ 030 - 16 -
changed, and the p~ocedure goes ~o the block 3~. A block
36 asks whether k i9 greater than 4. If not, the~ the
procedure loops back to the block 26 as indicated by a
line 37.
I~ Ic is greater than 4, it means that all four
blocks which a projected motion block of a P frame might
intersect have been processed. ~ block 3~ then iterates
i and j so as go to another motion bloc]c in the P frame.
A block 40 then checks to see if all P rame motion
blocks have heen processed. If not, the procedure loops
back to the block 16 as indicated by the line 41. If so,
i and j are set to O in block 42 and the procedure i8 set
to derive the forward and backward B frame motion vectors
from the selected P frame motion vector.
`~15 ! Then, for each B frame motion block, the
; vectors from the table are obtained that are for the
motion block in a P frame having a pro;ection on that ~
; frame block with the most overlap, block 44. The vectors
are then scaled so as to take into account the position
of the B frame between two anchor frames. If Bl i9 the
bloc]c under consideration, the backward vector would be
-2/3 mv30 and the orward vector would be +1t3 mv30. As
;~ this is done for each B frame block, the i and j
; coordinates are iterated. ~ block 4~ as~s if all B frame
blocks have been processed. If not, the procedure loops
back to the block 44 as indicated by a line 45, but if
.
........ ~
2~78~5
~r~- 030 - 17 -
all B frame blocks have been processed, the calculation~
are complete until it is desired to obtain the motion
vectors for the block~ of another B frame.
Fig. 11 shows a block diagram of an encoder for
a system which uses the independent search method
previously referred to in which forward and backward
vectors are derived Eor each block in a ~ frame by a
block matching process. Signals from a source 51 are
digitized in an A/D device 52 and applied to the I, P
~ 10 terminal o~ a switch 53. When coding an I frame, the
: switch 53 i9 in contact with itY I, P terminal 90 that
: the signals for this frame are transferred block by block- to the positive input of a subtracter 54. ~lso, the
negative input ~9 connected to ground by a switch 61.
The blocks of digiti~ed data are tran~foxmed blocl~ by
block into DCT coefficients by a Discrete Cosine
Transform processor 55. These coefficients are quantized
by a quantizer 56 so as to reduce the resolution of
coefficients for higher frequencies.
The quantized coefficients are variable length
coded by a variable length coder, VLC, 63, and the
resulting bit stream i9 coupled to a FIF0 buffer 64. The
output of the FIF0 buffer 64 is a bit stream having a
constant bit rate and is transmitted to an output channel
by a ~ignal conveyor 66. The fullnes~ of the FIF0 buffer
64 i~ examined by a buffer controller 65 that adjust9 the
,
~ , ~
;''''~
,
2 ~ 0
M~TA-030 - la -
step ~ize oE the quantizer 56 so as to increase or
decrease the bit rate of the signal applied to the VLC 63
and thereby prevent it from overflowing. I'hus, an I
frame i~ intra-coded so that no reference i9 made to any
S other frame The I frame is recovered, albeit with
quantization error, by an inver.se quantizer 57 and
inverse DCT, IDCT 58 and applied to an adder 59. ~t this
time, the output of the adder 59 is connected via a
switch 120 to the input of a series of frame delays 61a -
61e.
Note that all digitized frames at the output ofthe A/D device 52 are applied to a series of frame delays
60a through 60e. The B frames immediately following the
I frame just described are applied to the fr~me delays
60a - 60e, but the switch 53 is input connected to
terminal B so that the B frames are merely held for
future processing, while previous B frames are supplied
to terminal B of switch 53 for processing.
The next P frame, P3, for example, is encoded
by again placing the switch 53 in contact with its I, P
terminal and placing the switch 61 in contact with its P,
B terminal. The switch 120 at the output of the adder 59
is connected to a terminal 121 that is connected to the
input of a series of fr~me delays 62a - 62e.
2 ~
MAT~-030 - 19 -
The input digitized I0 frame i9 now at the
output of the frame delay 60c which i~ connected to the f
input of a motion estimator 67, and the input P3 frame is
applied to the g input of the motion estimator 67. In a
manner well ]c~own to those s]c:illed in the art, the motion
e~timator 67 derives the motion vector~ lilce mv30 ~ Fig.
2 that indica~e for each motion block in P3 where a
matching bloclc may be found in I0. These motion vectors
appear at the output FMv of the motion estimator 67 and
are applied to the VLC 63 for transmission to a decoder
and to a motlon compensator means 68.
he motion compensator 68 is coupled by a line
68' to the positive input of the adder 54 so as to
receive the digitized input data for P3, and a switch 73
: 15 connects an input of the compensator 68 to the output of
the delay 61c so as to receive the frame IO that was
recovered by the inverse ~uantizer 57 and the inverse DCT
59. By using the motion vectors from the motion
~: estimator 67, the motion compensator 68 forms a predicted
. 20 frame for P3 which is supplied to the adder 59 and via a
line B and the switch 61 to the negative input of the
subtracter 54 wherein it is subtracted from the input
data for P3 by the subtracter 54 so as to derive the
difference or residue signal.
This residue signal is transformed into DCT
coefficients that are quantized in a ~imilar way as the
,~
- .
'~ ' .
~7
~*~r~- 030 20 -
Io frame men~ioned earlier. ~lso, the operatlons
performed by the VLC 63, the FIFO 64, the inverse
quantizer 57 and the inverse DCT 58 are the same as when
the I ~rame was processed. The output of the IDCT 58
represents residue and i9 added ~o the predlcted P3 fxame
by the adder 59, and the adder output is stored in a
series of frame dela~s 62a - 62e. Note that the
processed anchor frames are alternately stored in the
frame delays 61a - 61e and 62a - 62e. Thus, I0 was
applied to the delays 61a - 61e.
At this point, the encoder has in memory the
original data for the I0 frame and a P~ frame that ha~
been derived from the I0 frame in the manner described.
At a decoder, the coded I0 frame iis decoded and a
predicted P frame is derived from it with the aid of the
motion vectors like mv30. The coded residue signal is
decoded and added to the predicted P frame to produce the
P3 frame
In an IS system, the best mode for forming a
frame from the I and P frame on either side of it is
determined iIl the following way. ~he input Bl frame i9
now available at the output of the ~rame delay 60c that
is connected to.the f input of the motion estimator 67.
I0 is at the output of the frame delay 60d and is
connected to the input h of the motion estimator by
positioning a switch 77, and the input frame P3, which i9
2 ~
M~I'A-030 - 21 -
at the outpu~ of the frc~me delay 60a, i9 coupled to the
input e of the motion estimator 67 by positioning a
switch 76. For every motion bloc]c in sl, ~he motion
estimator 67 finds a matching bloclc in the previou~
anchor frame I0 so as to produce a Eorward motion vector
FMv ~uch a~ mvl0 oE Fl~. 2. For every motioll bloc]c i~ H
a matching block is also found ln the next anchor frame
P3. This results in a backward motion vector BMv such as
mv13 in Fig. 2.
10One or both of the motion vectors derived as
just described may be sent to the VLC 63 for coding based
on a decision made by the motion compensator 68 in a
manner illustrated in Fig. 12. The selection made i9
called a mode, and a signal indicating the mode is sent
` 15via a line M to the VLC 63 for encoding. The B frames
are not trahsmitted, but they are reconstructed at a
decoder from one or both of the anchor frames by using
the motion vectors in accordance with the mode signal.
Thus, if the mode signal indicates that the matching
block in P3 gives best results, that matching block is
used. If the matching block in I0 i9 best, it i9 . used,
and if a combination of blocks produces the best results,
the combination i9 used. This in done on a block by
block basis so that different modes may apply to
differen~ blocks.
.
2~78~0
M~r~-030 - 22 -
In addition to motion vectors and mode signals,
the encoder must encode the difference between a selected
matching block or combination of matching block~ and the
correspondin~ bloclc in the ~ Erame as it is supplied by
the A/D device 52. Thi.s i9 done by supplying the
selected matc}ling bloc~ or combination of matching blocks
to the negative input oE the subtracter 5~ via the line B
and the switch 61. ~he differences or residue at the
output of the ~ubtracter ~ are then processed by the DCT
55, the quantizer 56, the V~C 63, the F~FO 64 and applied
to the signal conveyor 66. There is no need to form a
predicted block with the inverse quantizer 57 and the
inverse DCT 58 as decoded s frames are not needed by the
encoder and therefore need not be formed at the encoder.
Therefore, the switch 120 is set on an open terminal.
The manner in which the best mode is selected
in an IS system is as follows. Whereas the motion
vectors FMv and BMv for a ~ frame are derived from the
actual anchor frames on either side of it, these actual
frames are not available at the decoder so that the best
mode must be selected on the basis of the anchor frames
available at the encoder. ~nchor frames substantially
identical to those recovered at a decoder were produced
at the output of adder 59 and alternatively applied by
the switch 120 to the series of frame delays 61a - 61e
and the frame delays 62a - 62e as previously described.
Future anchor frames are supplied to an input a of the
2~7~9~
Ml~'r~- 030 ~ Z3
motion Compensator 68 by me~ns of a switch 69 and
switches 71 and 72, and past anchor frames by s~itches
70, 74 and 75 to an input b of the motion compensator 68.
By way of example, when the bes~ mode is to be determined
for B1, the switch 71 is placed in contact with the
output oE the frame delay 62a, and the ~witch 69 i~
placed in contact with the switch 71 so that the next
anchor frame P3, which is at the output of 62a is applied
to the a input of the motion compensator 68; the switch
74 is placed in contact with the output oE the frame
delay 61d, and the switch 70 is placed in contact with
the swit~h 74 90 that the previous anchor frame I0, which
is at the output of the frame dela~ 61d is applied to the
b input. Also, switches 77 and 76 are appropriately set
so as to choose input frames I0 and P3 respectively.
Referring to Fig. 12, the FMv and aMv motion
vectors supplied by the motion estimator 67 are used to
select the appropriate forward and bac]cward predicted
motion blocks from the past and future anchor frames by
selection blocks 80 and 89 respectively. These motion
blocks are respectively supplied to Mean Square Error
(MSE) calculators 85 and 84. The other input to each of
these calculators is the input B frame motion block.
Additionally, a third motion block called an
"interpolative predicted motion block" may be generated
by performing a weighted average on the forward and
backward predicted motion bloc]cs. ~or example, an
. ' : . , . :
: ~ ~' ' ' ' ' '
. .
.
2~3~
MATA-030 - 2~ -
amplifier 81 may multiply the output o~ the block from
the past anchor frame by K and the one from t}le future
anchor frame by l-K. In the case of sl, K = 2/3. The
interpolative predicted motion block i~ supplied to a
- 5 third MSE calculator ~tage 86.
` .
Each of these MSE calculators calculates the
mean square error between the input motion bloc]c and the
predicted or matching motion block. These errors are
supplied to a selector 87 which determines the minimum of
the three errors and con~rols a switch 88 so as to choose
the predicted motion block which resulted ln the least
error. This chosen predicted motion block appears on the
lead ~ of the motion compensator 68 of Fig. 11 and is
supplied through the switch 61 to subtracter 54. Al90,
mode information as to which predicted block is selected
is supplied by the selector 87 and by a lead M to the VLC
63 for coding and transmission to the receiver.
`` Specifically, the mode information tells the receiver
which of the three predic~ion modes was used i~ the
prediction of each motion block when frame Bl was coded.
!,
Figure 13 shows the block diagram of the
decoder for the independent search method IS. ~n input
means 97 receives the bit rate reduced signal and
supplies it to a variable length decoder (VLD) 98. The
VLD separates the block data into essentially four types
of information: video da~a in the form o~ quantized DCT
r
:
~ .
2 ~ 0
030 - 25 -
coe~ficien~s, ~orward mo~ion vectors FMv, bac)cward motion
vectors sMv~ and mode information. The quantized DCT
coefficients are dequantized b~ inverse quantizer 99 and
supplied to a IDCT 100 which transEorms them into residue
pixels to be added to the prediction information which
will be generated in the following manner. Mote that
the prediction information is absent for intra-Erames
(zero pixels). The prediction for P frames is obtained
a3 follows. One of the two frame stores 102 and 103
contains the previous anchor frame which is to be used in
generating the prediction. U3ing the forward motion
vector information, the appropriate motion block is
chosen from ~he previous anchor frame. After passing
through switch 107, it is supplied to an adder 101 where
it is added to the residue signal to form the P frame at
a terminal iog. ~ust as in the encoder, a switch 106 is
operated so as to store received anchor frames
alternately in frame stores I and II, but received B
frames are not stored in either frame store.
When B frames are to be predicted, the mode --
information instructs the displacement blocks 104 and 105
as well as switch 107 as to the t~pe of prediction to be
used (i.e. forward, backward, or interpolative). Using
this information as well as the appropriate motion
vectors that go along with the mode information, the
proper motion block or blocks are chosen from one or both
frame stores 102 and 103. Bither the forward or backward
't~r '~ 'J,~ , S ;.,~,
` ~7~0
M~TA-030 - 26 -
or interpolative predicted motion block i9 supplied
through the s~/itch 107 to the adder 101. ~l adder lOB
performs the weighted average of the forward and backward
motion bloclcs as required Eor interpolative predlction.
Frame stores I and II each have taps for a delay of 1, 2,
3, 4 or 5 Erames in a manner ~imilar to frame delays 61
and 62 in the encoder. The prediction is passed to the
adder 101 where it is added to the residue signal to form
the reconstructed B frames at the terminal 109.
The reconstructed frames will appear at
terminal 109 in decoder processing order, Fig. lB.
Switch 130 puts the frames back into display order as
shown in Fig. 19. When a reconstructed B frarne occurs at
terminal lO9 switch 130 is set so as to supply it
immediately to video output terminal 131. When
reconstructed anchor frame occurs at texminal 109, switch
106 i9 set so as to route it to one of the frame stores;
and switch 130 i9 set as to supply the anchor frame in
the other frame store to the video output terminal 131.
For example, if frame I0 is in frame store I,
and P3 is in frame store II, then Bl is the next frame to
be processed as shown in Fig. 18. It is immediately sent
out. Similarly, B2 is imrnediately se~t out. The next
fxame to be processed is P6. It is stored in frame store
I while P3 in frarne store II is sent out.
- 2~78~
MATA-030 - 27 -
, Area Overla~ Method (AO)
' I'he ~rea Overlap method o~ this invention
diEfers from the Independent Search method mainly in the
way that the predic~ion of s Erames i9 done. The AO
,; method uses P Erame motion vectors such as mv30 for
predicting B frame motion blocks in the following way. '
In this discussion, re~erence is made to the use of
motion vectors for frame P3 (with respect to I0) for the
purpose of predicting B1 and B2.
Fig. 14 i9 a block diagram ~or an encoder
incorporating this invention. Those components
corresponding to components in F'ig. 11 are designated in
the same way. Forward motion vectors for P3, such as
mv30, are stored in a memory 89 for a period (delay) o-E
one or two frames as required by frames Bl and B2
respectively (see Fig. 3). The stored motion vectors are
supplied ~y the Fmv Memory 89 to an Area Overlap Motion
Vector Calculator 90 where forward and baclcward motion
vectors AO F~v'and ~O B~v are calculated for B frame
motion blocks in a manner described by reference to Figs.
4 through 10. As previously explained, a backward motion
vector for a B1 bloc]c = -2/3 of motion vector mv30, and
the forward motion vector is 1/3 mv30. These motion
vectors are supplied to the motion compensator 68 vla a
lead M'.
:
,~'
~ 2~78~0
MAT~-030 - 2~ -
Motion compensation m~y be done in a number o~
ways. One way is shown in E~ig. 15; another way i9 shown
in Fig. 16. Corresponding components in these figures
and Fig. 12 are identi~ied in the same wa~. In Fig. 15
the AO motion vectors are supplied to displacement blocks
91 and 92 that are capable of doing spatial interpolation
at subpixel locations. A weighted average is performed
on the outputs of the selected displaced motion blocks by
multipliers 93 and 94 and an adder 95 to yield an AO
predicted motion block at the output oE the adder. This
becomes a fourth candidate to be chosen by the swit~h 8~.
The calbulations o~ mean square error are made in an MSE
calculator 96, and the results are supplied to minimum
selector a7 in a manner previously explained in
connection with Fig. 12. We now have four possible
predicted motion blocks, and once again the selector 87
instructs switch 88 to select the predicted motion block
which yields the least error. The information as to
which of these modes yields the lea~t error is also sent
to the receiver as before. Fig. 16 is an alternative
method for motion compensation. It difEers ~rom Fig. 15
only in that the AO predicted motion block has replaced
the interpolative predicted motion block as a candidate,
whereas in Figure 16 the ~O predicted motion block was
added to the list of candidates to be checked.
Whereas the AO motion vectors, ~O FMv and AO
BMv, derived in accordance with this invention have been
2~7~9~
MATA-030 ~9
~,
,
shown as being used in a bidirectional mode~ they may
also be used in unidlrectional modes in a manner similar
to the FMv and BMv vectors of the IS system.
A décoder for the ~O method is shown in Fi~ure
17 in which components corresponding to those of Fig. 13
are designated in the same way. In view oE the fact that
motion vectors for B frames can also be derived in
accordance with this invention from motion vcctors for an
anchor frame ~hat is xeferenced to a previous anchor
frame, bloclcs 110 and 111 are used by the decoder for
this purpose. These are identical to blocks 89 and 9~ in
Fig. 14. The mode information instructs the displacement
~- blocks 104 and 105 as well as switch 107 as to the
~` prediction mode to be used for B frame motion blocks.
Otherwise, the operation of this decoder is identical to
that of the decoder for the IS method.
REFERENCES:
l] S. M. E. Group, MPEG Video Simula~ion Model Three lSM3).
International Organization for Standardization, July 1990.
[2] D. S. R. Center, NBC, N. ~. Philips, and T. C. Electronics,
Advanced Digital Television Sys~em Descripe:ioIl. The Advanced
Television Research Consortium, Februar~ 1991.
~3] A. Puri and R. Aravind, " On comparing motion-interpolation
structures for video coding,'~ i~ SPIE Visual Co~llun~ca~ions and
Im~ge Proces~sing, pp. 1560-1571, 1990.
' '
,
2 ~
M~TA-030 - 30 -
[4] A. Puri, R. ~ravind, B.G. Haskell and R. Leonardi, " Video
Codlng with Motion-Compen~ated Interpolation for CD-ROM
~pplications," in Signal Processillg: Image Conununication,
pp. 127-1~ ugust 1990.
~ ..
[5] ~. Naga~a, I. lnove, ~. Tanaka and N. l'akeguchi, "Moving
Picture Coding System for Digital Storage Media Using Hybrid
Coding," in Signal Processing: Image Conununication,
pp. 109-116, ~ugust 1990.
.. ,_~,, . , ..... ,., . . ., ... ,~ , ...................... . . ............ .
:
