Process, apparatus and system for encoding video signals using motion estimation

At least one region of each video frame is designated for intra encoding. One or more regions of each video frame are designated for inter encoding. One or more motion vectors are selected for each region designated for inter encoding, wherein at least one motion vector is a non-zero motion vector. The plurality of video frames are encoded in accordance with the designation of regions for intra encoding, the designation of regions for inter encoding, and the selection of motion vectors, wherein the designation of regions for intra encoding and the selection of motion vectors are adapted to ensure error recovery during decoding of the encoded video frames.

BACKGROUND OF THE INVENTION 
1. Field of the Invention 
The present invention relates to video processing, and, in particular, to 
computer-implemented processes, apparatuses, and systems for compressing 
and decompressing video signals for applications with limited 
transmission, storage, and/or processing capacities. 
2. Description of the Related Art 
It is desirable to provide real-time video conferencing over a conferencing 
network in which each node in the network is a personal computer (PC) 
system. Each PC-based node transmits and receives video signals with each 
other PC-based node over a communications link. Conventional 
communications links include, but are not limited to, a local area network 
(LAN) or an integrated services digital network (ISDN) line. 
Conventional communications links have finite transmission bandwidth. In 
order to provide video conferencing of sufficient quality, it is desirable 
to apply compression processing to the video signals to reduce the amount 
of information used to represent each frame of the video stream for 
transmission. Decompression processing is then applied by the receiving 
node to reconstruct each video frame for display. 
In addition, conventional PC-based conferencing systems have finite 
processing bandwidth in which to implement the video compression and 
decompression processes. It is therefore further desirable to provide 
video compression and decompression processes that may be implemented in 
real time on PC-based conferencing systems to provide video conferencing 
of sufficient quality. 
It is accordingly an object of this invention to provide computer-based 
processes, apparatuses, and systems for performing video compression and 
decompression processing to provide real-time video conferencing of 
sufficient quality over a video conferencing network comprising nodes of 
finite processing bandwidth and communications links of finite 
transmission bandwidth. 
Further objects and advantages of this invention will become apparent from 
the detailed description of a preferred embodiment which follows. 
SUMMARY OF THE INVENTION 
The present invention is a computer-implemented process, apparatus, and 
system for encoding video signals. Each video frame of a plurality of 
video frames is divided into a plurality of regions. At least one region 
of each video frame is designated for intra encoding. One or more regions 
of each video frame are designated for inter encoding. One or more motion 
vectors are selected for each region designated for inter encoding, 
wherein at least one motion vector is a non-zero motion vector. The 
plurality of video frames are encoded in accordance with the designation 
of regions for intra encoding, the designation of regions for inter 
encoding, and the selection of motion vectors, wherein the designation of 
regions for intra encoding and the selection of motion vectors are adapted 
to ensure error recovery during decoding of the encoded video frames.

DESCRIPTION OF THE PREFERRED EMBODIMENT(S) 
POINT-TO-POINT CONFERENCING NETWORK 
Referring now to FIG. 1, there is shown a block diagram representing 
real-time point-to-point video conferencing between two PC systems, 
according to a preferred embodiment of the present invention. Each PC 
system has a conferencing system 100, a camera 102, and a monitor 106. The 
conferencing systems communicate via an integrated services digital 
network (ISDN) line 110. Each conferencing system 100 receives, digitizes, 
and compresses the analog video signals generated by camera 102. The 
compressed digital video signals are transmitted to the other conferencing 
system via ISDN line 110, where they are decompressed and converted for 
display in a window on monitor 106. Each conferencing system 100 may also 
display the locally generated video signals in a separate window on 
monitor 106 for monitoring of the local video processing. 
Camera 102 may be any suitable camera for generating NTSC or analog 
video signals. Those skilled in the art will understand that, in 
alternative embodiments of the present invention, camera 102 may be 
replaced by any other suitable source of unencoded video signals, such as 
a VCR for playing back recorded unencoded video signals or an antenna or 
cable for receiving unencoded video signals from a remote location. 
Monitor 106 may be any suitable monitor for displaying video and graphics 
images and is preferably a VGA monitor. 
CONFERENCING SYSTEM HARDWARE CONFIGURATION 
Referring now to FIG. 2, there is shown a block diagram of the hardware 
configuration of each conferencing system 100 of FIG. 1, according to a 
preferred embodiment of the present invention. Each conferencing system 
100 comprises host processor 202, video board 204, communications board 
206, and ISA bus 208. 
Referring now to FIG. 3, there is shown a block diagram of the hardware 
configuration of video board 204 of FIG. 2, according to a preferred 
embodiment of the present invention. Video board 204 comprises industry 
standard architecture (ISA) bus interface 310, video bus 312, pixel 
processor 302, video random access memory (VRAM) device 304, video capture 
module 306, and video analog-to-digital (A/D) converter 308. 
VIDEO SIGNAL PROCESSING 
Referring to FIGS. 2 and 3, software running on host processor 202 provides 
the top-level local control of video conferencing between a local 
conferencing system (i.e., local site, local node, or local endpoint) and 
a remote conferencing system (i.e., remote site, remote node, or remote 
endpoint). Host processor 202 controls local video signal processing and 
establishes links with the remote site for transmitting and receiving 
audio and video signals over the ISDN. 
During video conferencing, video A/D converter 308 of video board 204 
digitizes analog video signals received from camera 102 and transmits the 
resulting digitized video to video capture module 306. Video capture 
module 306 decodes the digitized video into YUV color components and 
delivers subsampled digital YUV9 video bitmaps to VRAM 304 via video bus 
312. Video microcode running on pixel processor 302 compresses the 
subsampled video bitmaps and stores the resulting compressed video signals 
back to VRAM 304. ISA bus interface 310 then transmits via ISA bus 208 the 
compressed video to host processor 202. Host processor 202 transmits the 
compressed video signals to communications board 206 via ISA bus 208 for 
transmission to the remote site over ISDN line 110. 
In addition, communications board 206 receives from ISDN line 110 
compressed video signals generated by the remote site and transmits the 
compressed video signals to host processor 202 via ISA bus 208. Host 
processor 202 decompresses the compressed video signals and transmits the 
decompressed video to the graphics device interface (GDI) (not shown) of 
the operating system (for example, Microsoft.RTM. Windows) for eventual 
display in a display window on monitor 106. 
Those skilled in the art will understand that, if there is sufficient 
processing bandwidth, the video compression processing of the present 
invention may alternatively be implemented in a host processor such as 
host processor 202. Similarly, the video decompression processing of the 
present invention may alternatively be implemented in a pixel processor 
such as pixel processor 302. 
PREFERRED HARDWARE CONFIGURATION FOR CONFERENCING SYSTEM 
Referring again to FIG. 2, host processor 202 may be any suitable 
general-purpose processor and is preferably an Intel.RTM. processor such 
as an Intel.RTM. i486.TM. or Pentium.TM. microprocessor. Host processor 
202 preferably has at least 8 megabytes of host memory. Bus 208 may be any 
suitable digital communications bus and is preferably an Industry Standard 
Architecture (ISA) PC bus. Communications board 206 may be any suitable 
hardware/software for performing communications processing for 
conferencing system 100. 
Referring again to FIG. 3, video A/D converter 308 of video board 204 may 
be any standard hardware for digitizing and decoding analog video signals 
that are preferably NTSC or standard video signals. Video capture 
module 306 may be any suitable device for capturing digital video color 
component bitmaps and is preferably an Intel.RTM. ActionMedia.RTM. II 
Capture Module. Video capture module 306 preferably captures video as 
subsampled 4:1:1 YUV bitmaps (i.e., YUV9 or YVU9). Memory 304 may be any 
suitable computer memory device for storing data during video processing 
such as a random access memory (RAM) device and is preferably a video RAM 
(VRAM) device with at least 1 megabyte of data storage capacity. Pixel 
processor 302 may be any suitable processor for compressing video data and 
is preferably an Intel.RTM. pixel processor such as an Intel.RTM. 
i750.RTM. Pixel Processor. Video bus 312 may be any suitable digital 
communications bus and is preferably an Intel.RTM. DVI.RTM. bus. ISA bus 
interface 310 may be any suitable interface between ISA bus 208 and video 
bus 312, and preferably comprises three Intel.RTM. ActionMedia.RTM. Gate 
Arrays and ISA configuration jumpers. 
VIDEO SIGNAL ENCODING 
Referring now to FIG. 4, there is shown a top-level flow diagram of the 
processing implemented by pixel processor 302 of FIG. 3 to compress (i.e., 
encode) the subsampled YUV9 video signals generated by video capture 
module 306 and stored to VRAM 304, according to a preferred embodiment of 
the present invention. YUV9 video signals comprise sequences of video 
frames having three planes of 8-bit component signals (Y, U, and V) with U 
and V subsampled by 4.times. in both directions. Thus, for every 
(4.times.4) block of Y component signals, there is one U component signals 
and one V component signal. 
Pixel processor 302 preferably encodes each component plane independently 
for each video frame with no grouping or interleaving of the component 
signals. The component planes are preferably encoded in the order Y, V, 
and U. For purposes of encoding, each component plane is subdivided into a 
grid of (16.times.16) macroblocks. Each macroblock is further divided into 
a set of four (8.times.8) blocks. 
Each component plane may be divided into one or more slices, where each 
slice comprises a integer number of rows of macroblocks. A slice may not 
span different component planes. The segmentation of component planes into 
slices may be dictated by such parameters as the transmission bandwidth 
and reliability of the communications line between nodes in the 
conferencing network, the processing bandwidth of decoders, and the video 
quality requirements of the video conferencing. These factors contribute 
to the selection of numbers of rows of macroblocks to be encoded into a 
single slice. 
Referring now to FIG. 5, there is shown a representation of a preferred 
sequence of processing the blocks and macroblocks of each component plane 
of each video frame during encoding (and decoding). The macroblocks of 
each component plane are traversed in raster-scan order starting at the 
top-left corner (i.e., macroblock i+1 immediately following macroblock i 
and macroblock j+1 immediately following macroblock j), while the blocks 
within each macroblock are processed in the order top-left (block 1), 
bottom-left (block 2), bottom-right (block 3), and top-right (block 4). As 
a result, for adjacent macroblocks i and i+1, block 4 of macroblock i is 
adjacent to block 1 of macroblock i+1. 
If the width (i.e., number of columns) of a component plane is not evenly 
divisible by 16, then partial macroblocks are preferably added at the 
right edge of the plane. Similarly, if the height (i.e., number of rows) 
of a component plane is not evenly divisible by 16, then partial 
macroblocks are preferably added at the bottom edge of the plane. If 
either dimension is not evenly divisible by 8, then partial blocks are 
preferably added at the appropriate edges. 
The encoder (i.e., preferably pixel processor 302 of FIG. 3) preferably 
encodes partial blocks by padding them out to the full (8.times.8) size 
(using a selected method such as replicating the last column or row). The 
resulting padded blocks are encoded as if they were originally full 
blocks. The decoder (i.e., preferably host processor 202 of FIG. 2) 
reconstructs an original partial block by decoding the full (8.times.8) 
padded block and then saving only the appropriate partial block to the 
final image bitmap in memory. The decoder determines the location and size 
of partial blocks from the image dimensions which are encoded in the 
compressed video signal, as described in further detail later in this 
specification in conjunction with FIG. 15. 
Blocks that are part of partial macroblocks but which lie completely 
outside the image are called "phantom blocks." Phantom blocks are 
preferably not encoded and are therefore not processed by the decoder. 
Referring again to FIG. 4, the encoder begins video signal encoding for the 
current input frame by performing motion estimation (step 402 of FIG. 4). 
Motion estimation generates a motion vector for each (16.times.16) 
macroblock of each component plane of the current frame. The motion vector 
specifies the (16.times.16) macroblock of the reference frame that most 
closely matches the macroblock of the current frame (within specified 
ranges of allowable motion). The reference frame (i.e., companded frame) 
is the result of compressing and expanding the previous input frame. 
Motion estimation is described in further detail later in this 
specification in the section entitled "Motion Estimation." 
After motion estimation, each macroblock is classified as to whether it is 
to be encoded as an inter macroblock or an intra macroblock (step 404). An 
inter macroblock is encoded with respect to the corresponding 
motion-compensated macroblock of the reference frame. An intra macroblock 
is not encoded with respect to any previous frame. The classification of 
macroblocks as inter and intra is described in further detail later in 
this specification in the section entitled "Macroblock Classification." 
After macroblock classification, a temporal pre-filter is applied to the 
current input frame (step 406). The temporal pre-filter is described in 
further detail later in this specification in the section entitled 
"Temporal Pre-Filtering." 
After temporal pre-filtering, a quantization level is selected for each 
macroblock (step 408). The quantization level identifies the quantization 
table used in quantization (step 416), as described below. Selection of 
quantization level is described in further detail later in this 
specification in the section entitled "Quantization Level Selection." 
Block subtraction is then applied to all those (8.times.8) blocks that are 
part of macroblocks to be encoded as inter macroblocks (step 410). Block 
subtraction involves generating the differences between the components of 
a temporally pre-filtered block of the current frame and the corresponding 
components of the corresponding motion-compensated block of the reference 
frame. 
A forward discrete slant transform (FDST) is then applied (step 412). For 
inter blocks, the FDST is applied to the component differences generated 
during block subtraction. For intra blocks, the FDST is applied to the 
temporally pre-filtered component values. The forward (and inverse) 
discrete slant transforms are described in further detail later in this 
specification in the section entitled "Discrete Slant Transform." The 
result of applying the FDST to an (8.times.8) block in the pixel component 
domain is an (8.times.8) block of DST coefficients in the spatial 
frequency domain. 
If the current block is an intra block, then the DC coefficient (i.e., the 
(0,0) DST coefficient in the (8.times.8) block) is encoded as a predicted 
value with respect to prevDC, where prevDC is the DC coefficient of the 
previous intra block in the current slice (following the block scanning 
sequence of FIG. 5) (step 414). The value that is encoded is the 
difference between the DC coefficient for the current block and prevDC. 
The value of prevDC is preferably initialized to 8*64 or 512 at the start 
of each image slice. Those skilled in the art will understand that this 
preferred initial value for prevDC represents the gray level midway 
between 0 and 127, times 8 (to scale the integer arithmetic to allow three 
fractional bits). 
Quantization is then applied to the blocks of DST coefficients (step 416) 
using the quantization table previously selected for the current block (in 
step 408) the current DST coefficient. Those skilled in the art will 
understand that, for typical blocks of YUV video component signals, many 
of the 64 DST coefficients are close enough to zero to be represented in 
the compressed video bitstream as zero without significant loss of video 
quality at playback. Quantization is described in further detail later in 
this specification in the section entitled "Quantization." 
After quantization, the quantized DST coefficients are run-length encoded 
using the zig-zag scan sequence represented in FIG. 6 (step 418). The 
quantized DST coefficients are run-length encoded as run-val pairs 
comprising a run of sequential zero DST coefficients followed by a 
non-zero quantized DST coefficient. Common run-val pairs may be further 
encoded as a single value that represents an index to a run table and a 
val table. 
The run-val pairs (or run-val table indices) are then variable-length 
encoded using Huffman encoding (step 420) to generate the block signals of 
the encoded video bitstream. Huffman encoding is also used to encode the 
macroblock signals of the encoded video bitstream. Variable-length 
encoding are described in further detail later in this specification in 
the section entitled "Variable-Length Encoding." The resulting Huffman 
encoded signals for the macroblocks and blocks are then combined with 
slice and picture header signals to form the compressed video bitstream. 
The compressed video bitstream format is described in further detail later 
in this specification in the section entitled "Compressed Video Signal 
Format." 
A reference frame is generated corresponding to the current input frame for 
use in encoding the next input frame. The reference frame is generated by 
decoding the encoded video frame corresponding to the current input frame. 
Since zig-zag run-length encoding (step 418 of FIG. 4) and Huffman 
encoding (step 420) are lossless procedures (i.e., no information is 
lost), generation of the reference frame preferably begins with the 
quantized DST coefficients (generated at step 416). 
The quantized DST coefficients are dequantized (step 422), the DC 
prediction for intra blocks is undone (step 424), and the inverse discrete 
slant transform (IDST) is applied to the resulting dequantized DST 
coefficients (step 426). If the block was encoded as an inter block, then 
block addition is performed to add the IDST results to the corresponding 
motion-compensated block of the previous reference frame (step 428). If 
the block was encoded as an intra block, then no block addition is 
performed. In either case, clamping is performed (step 430) and a temporal 
post-filter (corresponding to the temporal pre-filter) is applied to the 
clamped results (step 432). Clamping limits the signals to be within a 
specified range, preferably between 8 and 120, inclusive. Temporal 
post-filtering is described in further detail later in this specification 
in the section entitled "Temporal Post-Filtering." The output of the 
temporal post-filter is the reference frame used to encode the next input 
frame. 
Those skilled in the art will understand that, in alternative preferred 
embodiments, the reference frame may be generated from the encoded video 
frame by pixel processor 302 or by host processor 202. 
MOTION ESTIMATION 
As described above in reference to step 402 of FIG. 4, the encoder performs 
motion estimation to identify, for each (16.times.16) target macroblock of 
the current image, a (16.times.16) macroblock from the reference image 
that matches (relatively closely) the target macroblock. In general, the 
encoder implements motion estimation as a three-step log search to 
identify a motion vector within a specified pixel range of the current 
macroblock. According to a preferred embodiment, the pixel range is 
specified as +/-7 pixels in the horizontal and vertical directions. 
Motion estimation preferably is based on the sum of absolute differences 
(SAD(i,j)) between the component signals of the target macroblock and the 
component signals of the macroblock in the reference frame corresponding 
to the motion vector (i,j). In a preferred embodiment, only 64 of the 
possible 256 component differences are used to compute the SAD. These 64 
differences preferably correspond to every other row and every other 
column starting at one corner of the (16.times.16) macroblock. 
A preferred three-step log search is implemented for each target macroblock 
of the current image as follows: 
(1) Compute SAD(0,0) between the target macroblock and the macroblock in 
the reference image corresponding to a motion vector of (0,0). 
(2) If SAD(0,0) is less than a specified threshold (preferably 192 
(corresponding to an average component difference magnitude of 3 for the 
64 differences)), then select (0,0) as the motion vector for the target 
macroblock and terminate motion estimation for the current target 
macroblock. 
(3) Otherwise, compute SAD(i,j) between the target macroblock and the 
macroblocks in the reference image corresponding to the motion vectors 
(-4,-4), (0,-4), (4,-4), (-4,0), (4,0), (-4,4), (0,4), and (4,4). 
(4) Select the position (i.sub.1,j.sub.1) with the lowest SAD(i,j) among 
all nine SAD(i,j) (including SAD(0,0). 
(5) Compute SAD(i,j) between the target macroblock and the macroblocks in 
the reference image corresponding to the motion vectors (i.sub.1 
-2,j.sub.1 -2), (i.sub.1 -2,j.sub.1), (i.sub.1 -2,j.sub.1 +2), 
(i.sub.1,j.sub.1 -2), (i.sub.1,j.sub.1 +2), (i.sub.1 +2,j.sub.1 -2), 
(i.sub.1 +2,j.sub.1), (i.sub.1 +2,j.sub.1 +2). 
(6) Select the position (i.sub.2,j.sub.2) with the lowest SAD(i,j) among 
the last nine SAD(i,j) (including SAD(i.sub.1,j.sub.1). 
(7) Compute SAD(i,j) between the target macroblock and the macroblocks in 
the reference image corresponding to the motion vectors (i.sub.2 
-1,j.sub.2 -1), (i.sub.2 -1,j.sub.2), (i.sub.2 -1,j.sub.2 +1), 
(i.sub.2,j.sub.2 -1), (i.sub.2,j.sub.2 +1), (i.sub.2 +1,j.sub.2 -1), 
(i.sub.2 +1,j.sub.2), (i.sub.2 +1,j.sub.2 +1). 
(8) Select the position (i.sub.3,j.sub.3) with the lowest SAD(i,j) among 
the last nine SAD(i,j) (including SAD(i.sub.2,j.sub.2) as the motion 
vector for the target macroblock and terminate motion estimation for the 
current target macroblock. 
This method of motion estimation involves (at most) 25 SAD computations for 
each target macroblock. Those skilled in the art will understand that 
other constraints may be imposed on motion estimation to limit the number 
of SAD computations in the above procedure. For example, target 
macroblocks near the edges of a slice have a reduced number of SAD 
computations. Additional constraints on motion estimation may be imposed 
to promote error recovery as described in the next section of this 
specification. 
MOTION ESTIMATION RULES TO PROVIDE ERROR RECOVERY 
In a preferred embodiment of the present invention, each frame in a 
sequence of video frames has one row of macroblocks in the Y component 
plane that is encoded entirely as intra blocks. The position (within the Y 
component plane) of the macroblock row that is intra encoded changes from 
frame to frame in an orderly cyclical manner (e.g., from top to bottom and 
then jump back to top). For (160.times.120) frames (i.e., 160 columns and 
120 rows), it takes 8 frames for the intra-encoded macroblocks to cycle 
through the possible positions. During the 8-frame cycling period of this 
example, the entire U component plane of one of the 8 frames and the 
entire V component plane of one of the remaining 7 frames are intra 
encoded. Those skilled in the art will understand that one reason for 
implementing this cyclical intra encoding is to refresh periodically all 
the pixel locations with intra encoded signals, while attempting to 
maintain relatively uniform bit rates over the video stream. 
In a video conferencing network, frames (or portions of frames) may be lost 
or corrupted during transmission from one node to another, or as a result 
of CPU cycle bottlenecks. For encoded video signals in which some of the 
macroblocks of each image may be encoded as inter macroblocks, 
straightforward cyclical intra encoding does not ensure automatic recovery 
from such errors. Those skilled in the art will understand that error 
recovery may not be achieved if motion compensation causes "good" 
macroblocks (i.e., those macroblocks ultimately based only on intra 
macroblocks decoded after the error) to become corrupted by "bad" 
macroblocks (i.e., those macroblocks not ultimately based only on intra 
macroblocks decoded after the error). 
Referring now to FIG. 7, there is shown a representation of the general 
motion estimation rules applied by pixel processor 302 of FIG. 3 during 
the encoding of a Y component plane of a frame j of a sequence of video 
frames, according to a preferred embodiment of the present invention. The 
preferred general motion estimation rules may be summarized as follows: 
For frame j, image region i (comprising one or more rows of macroblocks) is 
the cyclical intra-encoded image region: 
ME Rule (A) For all of the target macroblocks in image region i-1 (where 
image region i-1 is the image region immediately above image region i and 
has the same number of rows of macroblocks as image region i), motion 
estimation may consider only those reference macroblocks within image 
region i-1 of the reference frame j-1 (i.e., the companded frame 
corresponding to the previous frame j-1). 
ME Rule (B) For each of the other image regions k (having the same number 
of rows of macroblocks as image region i), the target macroblocks of image 
region k (1) may not have motion vectors that correspond to image regions 
above image region k of the reference frame j-1 and (2) may not have 
motion vectors that correspond to image region i of the reference frame 
j-1. 
These preferred rules ensure automatic error recovery within a finite 
recovery period, when the intra encoding cycles from frame to frame in 
top-to-bottom order. The finite recovery period is equal to the 
intra-encoding cycling period. 
Those skilled in the art will understand that motion estimation under the 
above rules for error recovery will be affected by the edges of the Y 
component plane, the number of rows of macroblocks per intra-encoded image 
region, and the limitations on range of allowable motion vectors. In a 
preferred embodiment, each intra-encoded image region has only one row of 
macroblocks and the allowable motion vectors are limited to +/-7 pixels in 
the horizontal and vertical directions. 
Those skilled in the art will also understand that the preferred motion 
estimation rules ensure that, during the error recovery period, no part of 
the image that recovers (via the cyclical intra-encoded rows) becomes 
corrupted again. To provide faster error recovery (at the expense of a 
higher average bit rate), the number of rows of macroblocks in the 
intra-encoded image region may be increased. 
The motion compensation rules of the present invention, along with the 
cyclical intra encoding, also ensure accurate decoding of encoded video 
signals within a finite initialization period at the beginning of a 
networking session and for video conferencing nodes that join a networking 
session already in progress. 
MACROBLOCK