Video Encoder/Decoder System

The present invention generally relates to digital data compression and encoding and decoding of signals. More particularly, the present invention relates to methods and apparatus for encoding and decoding digitized video signals.

The development of digital data compression techniques for compressing visual information is very significant due to the high demand for numerous new visual applications. These new applications include, for example, television transmission including high definition television transmission, facsimile transmission, teleconferencing and video conferencing, digital broadcasting, digital storage and recording, multimedia PC, and videophones.

Generally, digital channel capacity is the most important parameter in a digital transmission system because it limits the amount of data to be transmitted in a given time.

In many applications, the transmission process requires a very effective source encoding technique to overcome this limitation. Moreover, the major issue in video source encoding is usually the tradeoff between encoder cost and the amount of compression that is required for a given channel capacity. The encoder cost usually relates directly to the computational complexity of the encoder. Another significant issue is whether the degradation of the reconstructed signal can be tolerated for a particular application.

As described in U.S. Pat. No. 5,444,489, a common objective of all source encoding techniques is to reduce the bit rate of some underlying source signal for more efficient transmission and/or storage. The source signals of interest are usually in digital form. Examples of these are digitized speech samples, image pixels, and a sequence of images. Source encoding techniques can be classified as either lossless or lossy. In lossless encoding techniques, the reconstructed signal is an exact replica of the original signal, whereas in lossy encoding techniques, some distortion is introduced into the reconstructed signal, which distortion can be tolerated in many applications.

Almost all the video source encoding techniques achieve compression by exploiting both the spatial and temporal redundancies (correlation) inherent in the visual source signals. Numerous source encoding techniques have been developed over the last few decades for encoding both speech waveforms and image sequences. Consider, for example, W. K. Pratt, Digital Image Processing, N.Y.: John Wiley & Sons, 1978; N. S. Jayant and P. Noll, Digital Coding of Waveforms: Principles and Applications to Speech and Video, Englewood Cliffs, N.J.: Prentice-Hall, 1984; A. N. Netravali and G. B. Haskell, Digital pictures: Representation and compression, N.Y.: Plenum Press, 1988. Pulse code modulation (PCM), differential PCM (DPCM), delta modulation, predictive encoding, and various hybrid as well as adaptive versions of these techniques are very cost-effective encoding schemes at bit rates above one bit per sample, which is considered to be a medium-to-high quality data rate. However, a deficiency of all the foregoing techniques is that the encoding process is performed on only individual samples of the source signal. According to the well known Shannon rate-distortion theory described in T. Berger, Rate Distortion Theory, Englewood Cliffs, N.J.: Prentice Hall, 1971, a better objective performance can always be achieved in principle by encoding vectors rather than scalars.

Scalar quantization involves basically two operations. First, the range of possible input values is partitioned into a finite collection of subranges. Second, for each subrange, a representative value is selected to be output when an input value is within the subrange.

Vector quantization (VQ) allows the same two operations to take place in multi-dimensional vector space. Vector space is partitioned into subranges each having a corresponding representative value or code vector. Vector quantization was introduced in the late 1970s as a source encoding technique to encode source vectors instead of scalars. VQ is described in A. Gersho, "Asymptotically optimal block quantization," IEEE Trans. Information Theory, vol. 25, pp. 373-380, July 1979; Y. Linde, A. Buzo, and R. Gray, "An algorithm for vector quantization design," IEEE Trans. Commun., vol. 28, pp. 84-95, January, 1980; R. M. Gray, J. C. Kieffer, and Y. Linde, "Locally optimal quantizer design," Information and Control, vol. 45, pp. 178-198, 1980. An advantage of the VQ approach is that it can be combined with many hybrid and adaptive schemes to improve the overall encoding performance. Further, VQ-oriented encoding schemes are simple to implement and generally achieve higher compression than scalar quantization techniques. The receiver structure of VQ consists of a statistically generated codebook containing code vectors.

Most VQ-oriented encoding techniques, however, operate at a fixed rate/distortion tradeoff and thus provide very limited flexibility for practical implementation. Another practical limitation of VQ is that VQ performance depends on the particular image being encoded, especially at low-rate encoding. This quantization mismatch can degrade the performance substantially if the statistics of the image being encoded are not similar to those of the VQ.

Two other conventional block encoding techniques are transform encoding (e.g., discrete cosine transform (DCT) encoding) and subband encoding. In transform encoding, the image is decomposed into a set of nonoverlapping contiguous blocks and linear transformation is evaluated for each block. Transform encoding is described in the following publications: W. K. Pratt, Digital Image Processing, N.Y.: John Wiley & Sons, 1978; N. S. Jaynat and P. Noll, Digital Coding of Waveforms; Principles and Applications to Speech and Video, Englewood Cliffs, N.J.: Prentice-Hall, 1984; R. C. Gonzalez and P. Wintz, Digital Image Processing, Reading, Mass.; Addison-Wesley, 2nd ed., 1987. In transform encoding, transform coefficients are generated for each block, and these coefficients can be encoded by a number of conventional encoding techniques, including vector quantization. See N. M. Nasrabadi and R. A. King, "Image coding using vector quantization: a review," IEEE Trans. Commun., vol. 36, pp. 957-971, August 1986. The transform coefficients in general are much less correlated than the original image pixels. This feature offers the possibility of modeling their statistics with well defined distribution functions. Furthermore, the image is considered to be more compact in the transform domain because not all coefficients are required to reconstruct the image with very good quality. Transform encoding is also considered to be a robust technique when compared to VQ because the transformation is fixed for all classes of images.

Although meritorious to an extent, the effectiveness of transform encoding is questionable. The effectiveness depends critically on how the bits are allocated in order to encode the individual transform coefficients. This bit rate allocations problem is documented in A. Gersho and R. M. Gray, Vector Quantization and Signal Compression, Mass.: Kluwer Academic, 1992. This bit rate allocation problem often results in a highly complex computational strategy, especially if it is adaptive, as suggested in N. S. Jayant and P. Noll, Digital Coding of Waveforms: Principles and Applications to Speech and Video, Englewood Cliffs, N.J.: Prentice-Hall, 1984. The numerous computations associated with the transformation and the bit rate allocation strategy can lead to a high-cost hardware implementation. Furthermore, most encoders using transform encoding operate on block sizes of at least 8.times.8 pixels in order to achieve reasonable encoding performance. These block sizes are very effective in encoding the low detail regions of the image, but can result in poor quality in the high detail regions, especially at low bit-rates. In this regard, see R. Clarke, Transform Coding of Images, N.Y.: Academic, 1985. Thus, VQ is still known to be a better technique for encoding high detail image blocks.

Finally, in subband encoding the image is represented as a number of subband (band pass) images that have been subsampled at their Nyquist rate. In this regard, see M. Vetterli, "Multi-dimensional sub-band coding: some theory and algorithms," Signal Processing, vol. 6, pp. 97-112, April, 1984; J. W. Woods and S. D. O'Neil, "Subband coding of images," IEEE Trans. Acoust., Speech, Signal Processing, vol. 34, pp. 1278-1288, October, 1986. These subband images are then separately encoded at different bit rates. This approach resembles the human visual system. Subband encoding is a very effective technique for high quality encoding of images and video sequences, such as high definition TV. Subband encoding is also effective for progressive transmission in which different bands are used to decode signals at different rate/distortion operating points.

However, a primary disadvantage of subband encoding is that the computational complexity of the bit rate allocations and the subband decomposition problem can lead to a high-cost hardware implementation. Furthermore, subband encoding is usually not very efficient in allocating bit rates to encode the subband images at low rates.

Hence, there is a heretofore unaddressed need in the art for a low bit rate source encoding system and method which are much simpler and inexpensive to implement and which exhibit better computational efficiency.

In accordance with a first aspect of the present invention, an apparatus for encoding an image signal is provided. The apparatus includes an acquisition module disposed to receive the image signal. A first processor is coupled to the acquisition module. At least one encoder processor is coupled to the first processor, and produces an encoded image signal under control of the first processor.

In accordance with a second aspect of the present invention, a method for generating a compressed video signal is provided. The method includes the steps of converting an input image signal into a predetermined digital format and transferring the digital format image signal to at least one encoder processor. The method further includes the step of applying, at the encoder processor, a hierarchical vector quantization compression algorithm to the digitized image signal. At the next step, a resultant encoded bit stream generated by the application of the algorithm is collected.

In accordance with a third aspect of the present invention, a method for compressing an image signal representing a series of image frames is provided. The method includes the step of analyzing a first image frame by computing a mean value for each of a plurality of image blocks within the first image frame, storing the computed mean values in a scalar cache, providing a mean value quantizer comprising a predetermined number of quantization levels arranged between a minimum mean value and a maximum mean value stored in the scalar cache, the mean value quantizer producing a quantized mean value, and identifying each image block from the plurality of image blocks that is a low activity image block. Next, each of the low activity image blocks is encoded with its corresponding quantized mean value. These steps are then repeated for a second frame of the image signal.

In accordance with a fourth aspect of the present invention, a method of periodically enhancing a video image with at least one processor, in which the video image includes a series of frames, each of the frames including at least one block, is provided. The method includes the steps of determining space availability of the processor, determining time availability of the processor, and determining the number of bits used to encode a frame. Then, a value is assigned to a first variable corresponding to the number of bits used to encode the frame. The first variable is compared to a predetermined refresh threshold. The method further includes the steps of scalar refreshing the video image if the first variable exceeds the predetermined refresh threshold, and block refreshing the video image if the first variable is less than or equal to the predetermined refresh threshold.

In accordance with a fifth aspect of the present invention, a method for transmitting data from an encoder to a decoder is provided. The method includes, in combination encoding the data into a plurality of macro rows, transmitting the macro rows from the encoder to the decoder, and decoding the macro rows at the decoder.

In accordance with a sixth aspect of the present invention, in a video conferencing system having a camera, an image processor and an image display, an apparatus for electronically panning an image scene is provided. The apparatus includes an image acquisition module disposed to receive an image signal from the camera. The image acquisition module produces a digital representation of the image signal. Means for transmitting a portion of the digital representation of the image signal to the image processor are provided. The transmitting means is coupled between the image acquisition module and the image processor. The apparatus also includes an image pan selection device coupled to the transmitting means. The image pan selection device is operable to change the portion of the digital representation of the image signal that is transmitted to the image processor.

An object of the present invention is a reduction of the number of bits required to encode an image. Specifically, an object of the invention is a reduction of the number of bits required to encode an image by using a scalar cache to encode the mean of the blocks in the different levels of the hierarchy. Yet another object of the present invention is a reduction of decoding errors caused by faulty motion cache updates in the presence of transmission errors.

A further object of the present invention is a reduction of the overall computational power required to implement the HVQC and possible reduction of the number of bits used to encode an image. Another object of the present invention is an improvement in the perceived image quality. It is further an object of the present invention to control how bits are allocated to encoding various portions of the image to improve the image quality.

Another object of the present invention is to reduce the probability of buffer overflow and control how bits are allocated to encoding various portions of the image to improve the image quality.

Furthermore, it is an object of the present invention to improve image quality and reduce artifacts caused by transmission errors. A further object of the present invention is to improve image quality by encoding the chrominance components independently of the luminance component. Still another object of the present invention is an improvement in overall image quality, particularly of the chrominance component.

It is also an object of the present invention to improve image quality by reducing encoder artifacts. Another object of the present invention is to provides a means to trade off encoder bit rate for image quality.

In addition, it is an object of the present invention to allow use of multiple processors to share in the computational load of implementing the video encoder decoder system, sometimes referred to as a codec, which allows for greater flexibility and use of general purpose devices in the implementation of the encoder/decoder system. Another object of the present invention is implementation among several devices operating in parallel.

A further object of the present invention is to keep computational requirements of the system down through the use of load balancing techniques. Moreover, it is an object of the present invention to keep the computation load down by providing the processing devices with a history of the portion of the image they have just acquired and thus increase the precision of the motion vectors along the partition boundary.

Yet another object of the invention is a reduction of the bit rate and the computational complexity. An additional object of the invention is to allow computational needs to be balanced with image quality and bit rate constraints.

It is further an object of the invention to provide a method of keeping the image quality acceptable and the bit rate down. Additionally, it is an object of the invention to reduce the memory requirements and cost of the system. Another object of the invention is bit rate management determined by a single processing device that in turn controls the various encoder devices.

An additional object of the invention is to allow for maximum throughput of data to the transmission channel, immediate bit rate feedback control to all encoding processors, and, by the use of small packets of data, reduce image inaccuracies at the decoder due to channel errors. It is also an object of the invention to allow for efficient retransmission, if necessary.

A further object of the invention is to allow for a data channel to transmit various types of data in a multiplexed fashion. In addition, it is an object of the invention to reduce bit rate by allowing the caches to have independent initial conditions. Another object of the invention is low cost and low complexity implementation of YUV-to-RGB conversion.

Yet another object of the invention is a low cost, low complexity mechanism for controlling the data to undergo YUV-to-RGB conversion. An additional object of the invention is improved error detection and concealment. Another object of the invention is to reduce the amount of time between the viewer seeing a scene of high motion begin and subsequent scenes.

Furthermore, it is an object of the invention to transmit high quality still image frames. Another object of the invention is to improve the image quality by pre-determining which areas require the most bits for encoding.

It is also an object of the invention to provide a fast, efficient, and low cost method of calculating the distortion measure used in the hierarchical algorithm. Another object of the invention is a low cost means of panning an image scene and a low cost means of zooming in and out of an image scene.

An additional object of the invention is an elimination of the need for specialized ASICs and specialized board versions. Another object of the invention is to simplify video conferencing for the user. Moreover, it is an object of the invention to allow a user to have a visual representation of who the caller is and what they may want.

These and other objects, features, and advantages of the present invention are discussed or are apparent in the following description of the invention.

In the detailed description that follows, reference will be made to the following figures:

FIG. 1A is a block diagram of a hierarchical source encoding system in accordance with the present invention;

FIG. 1B is a block diagram of a hierarchical source encoding system in accordance with a preferred embodiment of the present invention;

FIG. 2 is a block diagram of a background detector of FIG. 1A;

FIG. 3 is a graphical illustration showing conventional quadtree decomposition of image blocks performed by the hierarchical source encoding system of FIG. 1A;

FIG. 4 is a block diagram of a motion encoder of FIG. 1A;

FIG. 5 is a graphical illustration showing the functionality of the compute-and-select mechanism of FIG. 4;

FIG. 6 is a graphical illustration showing the encoding of motion vectors within a cache memory of FIG. 4;

FIG. 7 is a graphical illustration showing updating processes of various cache stack replacement algorithms for the cache memory of FIG. 4;

FIG. 8 is a block diagram for a block matching encoder of FIG. 1A;

FIG. 9 is a block diagram of a cache vector quantizer for encoding a new frame of a video sequence in the frame buffer of the hierarchical source encoding system of FIG. 1A;

FIG. 10 is a graphical illustration showing a working set model for the cache memory of FIG. 9;

FIG. 11 is a graphical illustration showing a novel adaptive working set model for the cache memory of FIG. 9;

FIG. 12 is a graphical illustration showing a raster scan technique for scanning the image blocks in one image frame;

FIG. 13 is a graphical illustration showing a localized scanning technique for scanning the image blocks in one image frame;

FIG. 14A is a schematic diagram of a preferred parallel processing architecture;

FIG. 14B is a high level diagram of the architecture of a video conferencing system;

FIG. 15 is a bit map of the format of data for the YUV-to-RGB converter shown in FIG. 14A;

FIG. 16 shows the time for each phase of pre filtering assuming the encoders shown in FIGS. 14A and 14B will be operating on byte packed data;

FIG. 17 depicts processor utilization (minus overhead) for post processing;

FIG. 18 shows the format improving the efficiency of the YUV-to-RGB convertor shown in FIG. 14A;

FIG. 19 is a table of eight gamma elements;

FIG. 20 is a graph of threshold v. buffer fullness;

FIG. 21 depicts the Y data format and U&V data format in the master video input data buffer;

FIG. 22 is a high level example of a video bit stream;

FIG. 23 is a table relating to various values of the picture start code (PSC);

FIG. 24 is a table of the fields in a macro row header;

FIG. 25 shows the format of extended macro zero information;

FIG. 26 is a table showing various decompositions of luminance of 16.times.16 blocks and their resulting bit streams;

FIG. 27 is a table of the flags used to describe the video bit stream;

FIG. 28 is a table of the various decompositions of chrominance 8.times.8 blocks and their resulting bit streams;

FIG. 29 depicts an example of encoding still image 4.times.4 blocks;

FIG. 30 shows refresh header information;

FIG. 31 is a table of the overhead associated with a bit stream structure;

FIG. 32 is a table of the fields of a picture header;

FIG. 33 depicts a packet header;

FIG. 34 depicts encoded data in C31 memory in big endian format;

FIG. 35 depicts encoded data in PC memory for the original bit stream;

FIG. 36 depicts encoded data in PC memory for a bit stream of the system;

FIG. 37 is a block diagram of an interrupt routine;

FIGS. 38-44 relate to packet definitions for packets sent to the VSA;

FIG. 38 depicts a control packet;

FIG. 39 depicts a status request packet;

FIG. 40 depicts an encoded bit stream request;

FIG. 41 depicts a decoder bits end packet;

FIG. 42 depicts a decoder bits start/continue packet;

FIG. 43 depicts a YUV data for encoder packet;

FIG. 44 depicts a drop current RGB frame packet;

FIGS. 45-53 relate to packet definitions for packets sent to the host (PC);

FIG. 45 depicts a status packet;

FIG. 46 depicts a decoder error packet;

FIG. 47 depicts a decoder acknowledgment packet;

FIG. 48 depicts an encoded bits from encoder end packet;

FIG. 49 depicts an encoded bits from encoder start/continue packet;

FIG. 50 depicts an encoded bits frame stamp;

FIG. 51 depicts a top of RGB frame packet;

FIG. 52 depicts a FIFO ready packet;

FIG. 53 depicts a YUV acknowledgment packet;

FIGS. 54-78 relate to control types and parameters for the control packet (host to VSA);

FIG. 54 depicts a control encoding packet;

FIG. 55 depicts a frame rate divisor packet;

FIG. 56 depicts an encoded bit rate packet;

FIG. 57 depicts a post spatial filter packet;

FIG. 58 depicts a pre spatial filter packet;

FIG. 59 depicts a temporal filter packet;

FIG. 60 depicts a sill image quality packet;

FIG. 61 depicts a video mode packet;

FIG. 62 depicts a video pan absolute packet;

FIG. 63 depicts a brightness packet;

FIG. 64 depicts a contrast packet;

FIG. 65 depicts a saturation packet;

FIG. 66 depicts a hue packet;

FIG. 67 depicts a super control packet;

FIG. 68 depicts a control decoding packet;

FIG. 69 depicts a motion tracking packet;

FIG. 70 depicts a request control setting packet;

FIG. 71 depicts an example of a request control setting packet;

FIG. 72 depicts a frame rate divisor packet;

FIG. 73 depicts a request special status information packet;

FIG. 74 depicts a buffer fullness information packet;

FIG. 75 depicts a YUV top of frame packet;

FIG. 76 depicts a Y data frame packet;

FIG. 77 depicts a UV data packet;

FIG. 78 depicts a YUV end of frame packet

FIG. 79 depicts data flow between image planes, a digital signal processor and an accelerator;

FIG. 80 is table that represents formulas for calculating speed improvements with an accelerator;

FIG. 81 is table that shows speed improvement for various pipeline delay lengths used with an accelerator;

FIG. 82 depicts a mean absolute error (MAE) accelerator implementation in accordance with the equation shown in the Figure;

FIG. 83 depicts a mean absolute error (MSE) accelerator implementation in accordance with the equation shown in the Figure;

FIG. 84 illustrates an mean absolute error (MAE) implementation as in FIG. 82 with interpolation to provide 1/2 pixel resolution;

FIG. 85 illustrates a mean square error (MSE) implementation as in FIG. 83 with interpolation to provide 1/2 pixel resolution;

FIG. 86 is a Karnaugh map for carry save adders in the YUV to RGB matrix;

FIG. 87 is a block diagram of a circuit that converts a YUV signal to RGB format;

FIG. 88 depicts a logic adder and a related bit table for converting the YUV signal to RGB format;

FIG. 89 depicts a logic adder and a related bit table for converting the YUV signal to RGB format;

FIG. 90 depicts a logic adder and a related bit table for converting the YUV signal to RGB format;

FIG. 91 is a block diagram timing model for the YUV to RGB conversion;

FIG. 92 is a state diagram relating to the conversion of the YUV signal to RGB format;

FIG. 93 shows a 16.times.16 image block;

FIG. 94 shows an interpolated macro block;

FIG. 95 depicts memory space at the end of step 1 of the first iteration of a first motion estimation memory saving technique;

FIG. 96 depicts the memory space at the end of step 4 of the first iteration of the first motion estimation memory saving technique; and

FIG. 97 depicts memory space addressing for three successive iterations of a second motion estimation memory saving technique.

With reference now to the figures wherein like numerals designate corresponding parts throughout the several views, FIG. 1A shows a hierarchical source encoding system 10 having multiple successive stages 11-19 for encoding different parts of an image block 21. In essence, higher bit rates are allocated to those regions of the image block 21 where more motion occurs, while lower bit rates are allocated to those regions where less motion occurs. The hierarchical source encoding system 10 has a low computational complexity, is simple and inexpensive to implement, and is suited for implementation in hardware, software, or combinations thereof.

In accordance with a significant aspect of the present invention, the hierarchical encoding system 10 utilizes cache memories with stack replacement algorithms as a noiseless method to encode motion vectors. This approach has an advantage over entropy encoding because the statistics of the motion vectors are allowed to vary with time. Another major advantage of this approach is that the cache memories can substantially reduce the computation required for matching data blocks.

As shown in FIG. 1A, a background detector 11 initially receives an image block 21 of size p.times.p, for instance, 16.times.16 or 32.times.32 pixels. Generally, the background detector 11 determines whether the image block 21 is either a background block or a moving block. A block diagram of the background detector 11 is shown in FIG. 2. With reference to FIG. 2, the background detector 11 comprises a compute mechanism 24 in series with a T.sub.bg flag mechanism 26, and a frame buffer 28 for receiving data from the flag mechanism 26 and for writing data to the compute mechanism 24. The frame buffer 28 can be any memory which can be randomly accessed.

In the compute mechanism 24, the image block 21 is compared with a previously encoded p.times.p image block (not shown) which has been stored in the frame buffer 28 in order to generate a difference value, or a "distortion" value. The distortion value is generated by comparing the blocks on a pixel-by-pixel basis. The compute mechanism 24 may utilize any suitable distortion measurement algorithm for determining the distortion value, but preferably, it employs one of the following well known distortion measurement algorithms: ##EQU1##

The image block 21 is classified as a background block if a distortion value is less than a predetermined threshold T.sub.bg. The comparison to the threshold T.sub.bg is performed in the T.sub.bg flag mechanism 26. If the comparison results in a difference which is less than the threshold T.sub.bg, then a flag bit 32 is set to a logic high ("1") to thereby indicate that the present image block 21 is substantially identical to the previously encoded p.times.p image block and then the system 10 will retrieve another image block 21 for encoding. In the foregoing scenario, the image block 21 is encoded with merely a single flat bit 32. In the alternative, that is, if the distortion is greater than or equal to the threshold T.sub.bg, the flag bit 32 remains at a logic low ("0") and then the system 10 will pass the p.times.p image block 21 on to the next hierarchical stage, that is, to the p/2.times.p/2 (16.times.16 pixels in this example) background detector 12.

The p/2.times.p/2 background detector 12 has essentially the same architecture and equivalent functionality as the p.times.p background detector 11, as shown in FIG. 2 or a similar equivalent thereof, but the p/2.times.p/2 background detector 12 decomposes the p.times.p image block 21 into preferably four p/2.times.p/2 image blocks 21' via a conventional quadtree technique, prior to image analysis. A conventional quadtree decomposition is illustrated graphically in FIG. 3. As shown in FIG. 3, in conventional quadtree decomposition, a p.times.p block is divided into four p2.times.p/2 blocks, which are individually analyzed, and then each of the p2.times.p/2 blocks are broken down further into p4.times.p/4 blocks, which are individually analyzed, and so on.

Thus, in the present invention, the p2.times.p/2 background detector 12 retrieves a p/2.times.p/2 image block 21' from the four possible image blocks 21' within the decomposed p.times.p image block 21 residing in the frame buffer 28 and subsequently analyzes it. Eventually, all of the p2.times.p/2 image blocks 21' are individually processed by the background detector 12. If the retrieved p2.times.p/2 image block 21' matches with the corresponding previously encoded p2.times.p/2 image block (not shown) within the frame buffer 28, then the flag bit 32' is set at a logic high to thereby encode the p2.times.p/2 image block 21', and then the background detector 12 will retrieve another p2.times.p/2 image block 21' for analysis, until the four of the p.times.p image block are exhausted. Alternatively, if the particular p/2.times.p/2 image block 21' at issue does not match the corresponding previously encoded p/2.times.p/2 image block, then the p2.times.p/2 image block 21' is forwarded to the next subsequent stage of the hierarchical source encoding system 10 for analysis, that is, to the motion encoder 13.

As shown in FIG. 4, in the motion encoder 13, the p2.times.p/2 image block 21' is analyzed for motion. For this purpose, the p2.times.p/2 motion encoder 13 comprises a compute-and-select mechanism 34 for initially receiving p2.times.p/2 image block 21', a cache memory 36 having a modifiable set of motion vectors which are ultimately matched with the incoming image block 21', a T.sub.M threshold mechanism 38 for comparing the output of the compute-and-select mechanism 34 with a threshold T.sub.M, and cache update mechanism 42 for updating the motion code vectors contained within the cache memory 36 based upon motion information received from the next subsequent hierarchical stage, or from a block matching encoder 14, as indicated by a reference arrow 43'.

The compute-and-select mechanism 34 attempts to match the incoming p2.times.p/2 image block 21' with a previously stored image block which is displaced to an extent in the frame buffer 28. The displacement is determined by a motion vector corresponding to the matching previously stored image block. Generally, motion vectors are two-dimensional integer indices, having a horizontal displacement dx and a vertical displacement dy, and are expressed herein as coordinate pairs dx, dy. FIG. 5 graphically illustrates movement of the p2.times.p/2 image block 33 within the frame buffer 28 from a previous position, indicated by dotted block 46, to a present position, denoted by dotted block 48. The displacement between positions 46 and 48 can be specified by a two-dimensional displacement vector dx.sub.i, dy.sub.i.

The compute-and-select mechanism 34 compares the current image block 21', which is displaced by dx.sub.i, dy.sub.i, with the set of previously stored image blocks having code vectors in the modifiable set {dx.sub.0, dy.sub.0, dx.sub.1, dy.sub.1 ; . . . dx.sub.n, dy.sub.n } within the cache memory 36. The code vectors have cache indices 0 through n corresponding with dx.sub.0, dy.sub.0, dx.sub.1, dy.sub.1 ; . . . dx.sub.n, dy.sub.n. From the comparison between the current image block 21' and the previously stored image blocks, a minimum distortion code vector d.sub.min (dx.sub.i, dy.sub.i) is generated. The foregoing is accomplished by minimizing the following equation: ##EQU2## where x(t) is the current image block 21' corresponding to displacement vector dx.sub.i, dy.sub.i, where x(t-1) is the previously encoded block, and where d(dx,dy) is the distortion code vector.

Next, the minimum distortion code vector d.sub.min(dx.sub.i, dy.sub.i) is forwarded to the threshold mechanism 38, where the distortion of the minimum distortion motion vector d.sub.min (dx.sub.i, dy.sub.i) is compared with the threshold. If the distortion of the minimum distortion motion vector is less than the threshold, then the flag bit 52' is set at a logic high and the cache index 53', as seen in FIG. 6, associated with the minimum distortion motion vector d.sub.min (dx.sub.i, dy.sub.i) is output from the compute-and-select mechanism 34. Hence, the image block 21' is encoded by the flag bit 52' and the cache index 53'. Alternatively, if the distortion of the minimum distortion motion vector d.sub.min (dx.sub.i, dy.sub.i) is greater than or equal to the threshold, then the flag bit 52' is maintained at a logic low and the p2.times.p/2 image block 21' is forwarded to the next stage, that is, to the p2.times.p/2 block matching encoder 14 for further analysis.

Significantly, the cache update mechanism 42 updates the cache memory 36 based on cache hit and miss information, i.e., whether the flag bit 52' is set to a logic high or low. The cache update mechanism 42 may use any of a number of conventionally available cache stack replacement algorithms. In essence, when a hit occurs, the cache memory 36 is reordered, and when a miss occurs, a motion vector which is ultimately determined by the block matching encoder 14 in the next hierarchical stage is added to the cache memory 36. When the motion vector is added to the cache memory 36, one of the existing entries is deleted.

One of the following cache stack replacement algorithms is preferably utilized: the least-recently-used (LRU) algorithm, the least frequently used (LFU) algorithm, or the first-in-first-out (FIFO) algorithm. In the LRU algorithm, the motion vector to be replaced is the one whose last reference is the oldest, or has the largest backward distance. In the LFU algorithm, the motion vector to be replaced is the one whose number of references up to that time is the smallest. Finally, the in the FIFO algorithm, the motion vector to be removed is the one which has been in the cache memory 36 the longest length of time. FIG. 7 illustrates and contrasts the foregoing cache update and replacement algorithms during both a cache hit and a cache miss. In accordance with the present invention, the stack replacement algorithm re-orders the index stack in the event of a cache hit, and in the event of a cache miss, an index is deleted and another index is inserted in its place.

As seen in FIG. 8, the block matching encoder 14, which subsequently receives the p2.times.p/2 image block 21' in the event of cache miss, employs any conventional block matching encoding technique. Examples of suitable block matching encoding techniques are a full search and a more efficient log (logarithm) search, which are both well known in the art. For this purpose, the block matching encoder 14 comprises a block matching estimation mechanism 56 for comparing the incoming p2.times.p/2 image block 21' with image blocks in the previously stored image frame of the frame buffer 28.

If a log search is employed, a three level approach is recommended. In other words, a predetermined set of blocks is first searched and analyzed. A best fit block is selected. Then, the neighborhood of the search is reduced, and another search of predetermined blocks ensues. In a three level search, the foregoing procedure is performed three times so that the reduction in neighborhood occurs three times.

Block comparison is performed preferably as indicated in equation (4) above, and the distortion vector d(dx,dy) that results in minimum distortion is selected. A select mechanism 58 selects the motion vector with minimum distortion, or d.sub.min (dx,dy), from the distortion vectors generated by equation (4) and forwards the minimum distortion vector d.sub.min (dx,dy) to the cache memory 36 (FIG. 5) of the motion encoder 13 (previous stage) for updating the cache memory 36.

The minimum distortion vector d.sub.min (dx,dy) is then compared with a predetermined threshold T.sub.M in a T.sub.M threshold mechanism 64. If the minimum distortion vector d.sub.min (dx,dy) is greater than the predetermined threshold T.sub.M, then the flag bit 65' is maintained at a logic low, and the system 10 proceeds to the next hierarchical stage, that is, the p4.times.p/4 (8.times.8 pixels in this example) motion encoder 15 for further analysis. If, however, the minimum distortion vector d.sub.min (dx,dy) is less than or equal to the predetermined threshold T.sub.M, then the flag bit 65' is set at a logic high and is output along with the minimum distortion vector d.sub.min (dx,dy), as indicated by reference arrow 66'. Thus, in this case, the p2.times.p/2 image block 21' is encoded by a flag bit 65' and the minimum distortion vector d.sub.min (dx,dy) 66' and the system 10 proceeds back to the background detector 12, where another p2.times.p/2 image block 21' is retrieved, if available, and processed.

The image analyses which took place in the p2.times.p/2 motion encoder 13 and then the p2.times.p/2 motion encoder 13 and then the p2.times.p/2 block matching encoder 14, is again repeated respectively in the p4.times.p/4 motion encoder 15 and then the p4.times.p/4 block matching encoder 16, except on a smaller image block size of p4.times.p/4 pixels. The p/4.times.p/4 motion encoder 15 decomposes the p2.times.p/2 image block 21' into preferably four p/4.times.p/4 image blocks 21" through selective scanning via the conventional quadtree technique, as illustrated and previously described relative to FIG. 3. To this end, the p4.times.p/4 motion encoder 15 could encode the p4.times.p/4 image block 21", as indicated by reference arrow 54", with a flag bit 52" set to a logic high and a cache index 53". Or, in the next stage, the p4.times.p/4 block matching encoder 16 could encode the p4.times.p/4 image block 21", as indicated by reference arrow 67", with a flag bit 65" set to a logic high and a minimum distortion motion vector 66".

The image analyses which took place in the p4.times.p/4 motion encoder 15 and then the p4.times.p/4 block matching encoder 16, is again repeated respectively in the p/8.times.p/8 (4.times.4 pixels in this example) motion encoder 17 and then the p/8.times.p/8 block matching encoder 18, except on a smaller image block size of p/8.times.p/8 pixels. The p/8.times.p/8 motion encoder 17 decomposes the p4.times.p/4 image block 21" into preferably four p/8.times.p/8 image blocks 21"' through selective scanning via the conventional quadtree technique, as illustrated and previously described relative to FIG. 3. To this end, the p/8.times.p/8 motion encoder 17 could encode the p/8.times.p/8 image block 21"', as indicated by a reference arrow 54"', with a flag bit 52' set to a logic high and a cache index 53"'. Or, in the next stage, the p/8.times.p/8 block matching encoder 18 could encode the p/8.times.p/8 image bock 21"', as indicated by reference arrow 67"' with a flag bit 65"' set to a logic high and a minimum distortion motion vector 66"'.

If the p/8.times.p/8 image block 21"' has not yet been encoded, then it is passed onto a block encoder 19 shown in FIG. 9. The block encoder may be a vector quantizer, a transform encoder, a subband encoder, or any other suitable block encoder. Transform encoding and subband encoding are described in the background section hereinbefore. Examples of vector quantizers which are suitable for the present invention are described in A. Gersho, "Asymptotically optimal block quantization," IEEE Trans. Information Theory, vol. 25, pp. 373-380, July, 1979; Y. Linde, A. Buzo, and R. Gray, "An algorithm for vector quantization design," IEEE Trans. Commun., vol. 28, pp. 84-95, January, 1980; R. M. Gray, J. C. Kieffer, and Y. Linde, "Locally optimal quantizer design," Information and Control, vol. 45, pp. 178-198, 1980. All of the foregoing disclosures are incorporated herein by reference as if set forth in full hereinbelow. It should be further noted that entropy encoding may be employed in a vector quantizer 19 to further enhance data compression.

In regard to the well known entropy encoding, also known as variable length encoding, indices within the cache 36 may be entropy encoded in order to further enhance data compression. In entropy encoding, the statistics of an occurrence of each cache index are considered, and the number of bits for encoding each index may vary depending upon the probability of an occurrence of each index.

Referring to FIG. 1B, in a preferred embodiment, prior to processing by the background detector 12, the p.times.p image block is analyzed for motion by a motion encoder as described above for a p2.times.p/2 image block. Similarly, as described above, the p.times.p image block may be forwarded to a block matching encoder for further analysis.

Cache Vector Quantizer

During initialization of the hierarchical source encoding system 10, a new image frame must be created in the frame buffer 28 of the present invention. This situation can occur, for example, when the hierarchical source encoding system 10 is first activated or when there is a scene change in the video sequence.

For this purpose, a novel vector quantizer 68 shown in FIG. 9 has been developed using the novel cache memory principles. The cache vector quantizer 68 comprises a large main VQ codebook 69 which is designed off-line and a small codebook kept in a cache memory 72 whose entries are selected on-line based on the local statistics of the image being encoded. Similar to the cache memory 36 of the motion encoders 13, 15, 17, the cache memory 72 is replenished with preferably the stack algorithms LRU, LFU, FIFO, or a novel adaptive working set model algorithm, which will be discussed in further detail later in this document.

In architecture, the cache vector quantizer 68 includes the large VQ codebook 69, the cache memory 72, a compute-and-select mechanism 74 for receiving the incoming p.times.p image block 76 and for comparing the image block 76 to code vectors in the cache memory 72, a T.sub.c threshold mechanism 78 for determining whether the minimum distortion vector is below a predetermined threshold T.sub.c, and a cache update mechanism 82 which utilizes a cache stack replacement algorithm for updating the cache memory 72. More specifically, the compute-and-select mechanism 74 performs the following equations: ##EQU3## where x is the input block 76, z.sup.1, Z.sup.2, Z.sup.3, . . . Z.sup.L are the code vectors in the cache memory 72, where k.sub.c is the selected cache index, and where 1<k<L.

The T.sub.c threshold mechanism 78 determines whether the minimum distortion motion vector d.sub.kc is below the threshold T.sub.c. If so, then a flag bit 84 is set at a logic high indicating a cache hit, and the flag bit 84 is output along with the VQ address 86, as indicated by a reference arrow 88. Alternatively, if the minimum distortion d.sub.kc is greater than or equal to the threshold T.sub.c, indicating a cache miss, then the main VQ code codebook 69 is consulted.

Preferably, the main VQ codebook 69 is set up similar to the small codebook within the cache memory 72, and compares entries to determine a minimum distortion as with the small codebook. It should be noted, however, that other well known VQ methods can be implemented in the main VQ codebook 69. As examples, the following architectures could be implemented: (1) mean removed VQ, (2) residual VQ, and (3) gain/shape VQ.

The cache update mechanism 82 implements a stack replacement algorithm for the cache memory 72. In addition to the LRU, LFU, and FIFO stack replacement algorithms discussed in detail previously, the cache update mechanism 82 can perform a novel adaptive working set model algorithm described hereafter.

It should be further noted that entropy, encoding, transform encoding, for example, discrete cosine transform (DCT) encoding, and subband encoding may be employed in the cache vector quantizer 68 to further enhance data compression.

Adaptive Working Set Model Technique

The cache size n discussed thus far relative to cache memory 36, 72 has been fixed throughout the process of encoding a particular image block. For most natural images, the rate of cache misses in the regions of low detail is much smaller than in high detail regions.

Thus, more bit rate reduction could be achieved if the cache size n were allowed to vary according to the activity of the image blocks. In the adaptive working set model technique, adaptive cache with a flexible cache size is efficiently implemented and results in a lower bit rate than is achievable using other conventional cache stack replacement algorithms, for example, LRU, LFU, and FIFO as discussed previously.

To understand the adaptive working set model technique, a brief discussion of the conventional working set model technique is warranted. In the conventional working set model technique, no particular cache stack replacement technique is utilized, and the cache memory is simply a list of the unique code vectors that occur during the near past ›t-T+1,t!, where parameter T is known as the window size. The parameter T can be a function of time. The ultimate cache size corresponds to the number of unique code vectors within the time interval. For an image source, a two-dimensional causal search window 91 can be defined, as illustrated in FIG. 10, which conceptually corresponds to the time interval of the working set model. In other words, as shown in FIG. 10, the memory space in the cache memory 72 (FIG. 9) is defined as all the blocks within the causal search window 91. As an example, the causal search window 91 is shown have a size W equal to three rows of blocks 92, each with a block size p.times.p of 4.times.4. The resulting code vector for encoding each image block x(t) is the previous block in the causal search window 91 that yields the minimum distortion, such as the minimum mean squared error ("MSE") distortion. For a given causal search window 91 having size W, the total number M of possible code vectors is given by the following equation:

One of the major advantages of the working set model for computer memory design over other replacement algorithms is the ability to adapt the size of the causal search window 91 based on the average cache miss frequency, which is defined as the rate of misses over a short time interval. Different window sizes are used to execute different programs, and the working set model is able to allocate memory usage effectively in a multiprogramming environment.

The adaptive working set model of the present invention uses the foregoing ideas to implement variable-rate image encoding. Different regions of an image require different window sizes. For example, an edge region may require a much larger search window 91 than that of shaded regions. Accordingly, a cache-miss distance is defined based on the spatial coordinates of each previously-encoded miss-block in the causal window 91 relative to the present block being encoded.

More specifically, let N(W.sub.f,r,c) be the set of indices of the miss-blocks where W.sub.f is the window size used to estimate the cache-miss distance. The spatial coordinates of the set N((W.sub.f,r,c) are illustrated in FIG. 11 as the shaded blocks 93. The average cache-miss frequency is defined as the summation of the reciprocal of each cache-miss distance within the search window: ##EQU4## where r is the row index and c is the column index. This value provides a good enough estimate of the image locality at any given region without requiring a large amount of computation.

The window size W at a given time t is updated according to the following equation: ##EQU5## where A and B are two pre-defined constants, and W.sub.max is the pre-defined maximum allowed window size.

Hence, in the adaptive working set model technique, the size of the causal search window 91 is manipulated depending upon the miss frequency. As misses increase or decrease, the window 91 respectively increases or decreases.

In accordance with another aspect of the present invention, redundant blocks within the causal search window 91 are preferably minimized or eliminated. More specifically, if a present block matches one or more previous blocks in the causal search window 91, then only a code vector representative of the offset to the most recent block is encoded for designating the present block. This aspect further enhances data compression.

Localized Scanning of Cache Indices

The method used to index the image blocks in a single image frame can also affect the average cache bit rate because the cache memory 72 updates its contents based entirely on the source vectors that have been encoded in the near past. The indexing of image blocks may be based on a raster scan, as illustrated in FIG. 12. FIG. 12 shows an example of a raster scan for scanning 256 image blocks. The major problem with this method is that each time a new row begins, the inter-block locality changes rapidly. Moreover, if the cache size is very small relative to the number of vectors in a row, many cache misses will occur whenever the cache starts to encode the source vectors in a new row.

In the preferred embodiment, the image blocks are indexed for higher performance by providing more interblock locality. In this regard, a localized scanning technique, for example, the conventional Hilbert scanning technique, is utilized for indexing the image blocks of the image frame. FIG. 13 illustrates the Hilbert scanning technique as applied to the indexing of the image blocks of the image frame of the present invention for scanning 256 image blocks.

It will be obvious to those skilled in the art that many variations and modifications may be made to the above-described embodiments, which were chosen for the purpose of illustrating the present invention, without substantially departing from the spirit and scope of the present invention. For example, the hierarchical source encoding system 10 was specifically described relative to decomposition of square image blocks of particular sizes. Obviously, to one of skill in the art, any block configuration and size may be utilized to practice the present invention.

The number of encoders used during the encoding process may be adaptively changed to improve coding efficiency. The adaptation is based upon the statistical nature of the image sequence or the scene-change mean squared error ("MSE"). Coding efficiency is improved by assuring that every level of the hierarchy has a coding gain of greater than unity. Since there are overhead bits to address the hierarchical structure (the more levels the more bits required), it is possible to have a level that has coding gain less than unity. For example, in many experiments it was seen that during rapid moving scenes, the 4.times.4 motion coder has a coding gain less than unity and is thus replaced by spatial coders.

A scalar cache may be used to encode the mean of the blocks in the different levels of the hierarchy. After the video encoder/decoder, sometimes referred to as a "codec," has performed video compression through the reduction of temporal redundancy, further gains in compression can be made by reducing the spatial redundancy. Two such methods include: a.) A "working set model" which looks for similar areas (matching blocks) of video elsewhere in the same frame. The working set model looks in a small portion of the frame near the current area being encoded for a match since areas spatially close to one another tend to be similar. This relatively small search window can then be easily coded to provide a high compression ratio. The window size can also be varied according to the image statistics to provide additional compression. The technique of varying the window size according to the image statistics is referred to as an "adaptive working set model"; and b.) A scalar cache containing the mean of previously code areas can be used to encode the current area's mean value. Again, this takes advantage of areas spatially close to one another tending to be similar. If an area can be encoded with low enough distortion (below a threshold) by using it's mean value, then a scalar cache could save encoding bits.

Before an image undergoes encoding, an overall scene change MSE is performed. This is to determine how much motion may be present in an image. In a preferred embodiment, the coder reaches a level of 4.times.4 blocks, then if the MSE is below a threshold, the image is encoded with a structure that finds the 4.times.4 motion vectors from a search of the motion cache or through a three step motion search. On the other hand, if the MSE is above a threshold, the 4.times.4 motion vectors are found through one of the following:

1) Working set model: the motion vector is predicted from the currently-coded image rather than from the previously-coded image;

2) Each 4.times.4 block is coded by its mean only; or

3) Each 4.times.4 block is coded by its mean and a mean-removed VQ.

Thus the structure is adapted depending upon image content.

Pseudo code relating to the encoding and decoding processes is found at Appendix 2, Appendix 3 and Appendix 5. Appendix 2 contains high level pseudo code that describes the encoding and decoding algorithm. Appendix 3 contains pseudo code related to the encoding process and buffer management shown in Appendix 5. Appendix 5 contains pseudo code of the encoding and decoding algorithm in a C programming language style.

As described in U.S. Pat. No. 5,444,489, the HVQC algorithm had the cache-miss flag located in one particular position in the cache. The presently preferred embodiment, however, allows the cache-miss flag position to vary within the cache so that it may be more efficiently encoded through techniques such as entropy encoding.

U.S. Pat. No. 5,444,489 describes a hierarchical vector quantization compression ("HVQC") algorithm. In accordance with the present invention, the HVQC algorithm may be applied to an image signal using a parallel processing technique to take advantage of higher bit rate transmission channels.

One of the basic strengths of the HVQC algorithm is its adaptability to higher bit rate transmission channels. Users of these channels typically require higher performance in terms of image size, frame rate, and image quality. The HVQC algorithm may be adapted to these channels because the computational power required to implement the algorithm may be spread out among multiple processing devices.

A preferred parallel processing architecture is shown schematically in FIG. 14A. A video front end 94, receives a video input signal 95. The video front end 94 may, for example, be a device that converts an analog signal, such as a video signal in NTSC, PAL, or S-VHS format, into a digital signal, such as a digital YUV signal. Alternatively, the video front end 94 may receive from a video source a digital signal, which the video front end may transform into another digital format. The video front end 94 may be implemented using a Philips SAA7110A and a Texas Instruments TPC 1020A.

The video front end 94 provides digitized video data to a first processor 96, where the digitized video data is preprocessed (i.e. pre-filtered). After or during pre-filtering the digitized video data, the first processor 96 transmits the data corresponding to an image frame to a second processor 97 and a third processor 98. The first processor 96 communicates with the second processor 97 and the third processor 98 through a direct memory access ("DMA") interface 99, shown in FIG. 14A as a memory and a bus transceiver.

The first processor 96 uses most of its available MIPs to perform, for example, pre and post filtering, data acquisition and host communication. The first processor 96 uses less than 30% of its available MIPs for decoding functions. The first processor 96, the second processor 97 and the third processor 98 may be off-the-shelf digital signal processors. A commercially available digital signal processor that is suitable for this application is the Texas Instruments TMS320C31 ("C31") floating point digital signal processor. A fixed point digital signal processor may alternatively be used. As a further alternative, general purpose processors may be used, but at a higher dollar cost.

For the system architecture shown in FIG. 14A, the first processor 96 operates as a "master" and the second and third processors 97 and 98 operate as "slaves." Generally, the second and third processors 97 and 98 are dedicated to the function of encoding the image data under the control of the first processor 97.

The HVQC algorithm may be implemented with multiple processing devices, such as the processor architecture shown in FIG. 14A, by spatially dividing an image into several sub-images for coding. In addition, because of the multiple processor architecture, unequal partitioning of the image among the various processing devices may be used to share the computational load of encoding an image. The partitioning is preferably accomplished by dividing the image into several spatial segments. This process is known as boundary adaptation and allows the various processing devices to share the computational load instead of each having to be able to handle a seldom seen worst case computational burden. As an alternative to dividing up the image, the system may allocate more bits for encoding the image to the processor encoding the portion of the video with more activity. Therefore, this encoder may keep trying to encode at a high quality level since it would have more bits to encode with. This technique would not, however, reduce the computational requirements as does the preferred embodiment.

The DMA interface 99 is utilized to write image data to the second and third processors 97 and 98, exchange previously coded image data, and receive encoded bit streams from both the second and third processors 97 and 98. Data passing among the processors 96, 97 and 98 may be coordinated with a communication system residing on the master processor 96.

For example, there is an exchange of image information between the processors 97 and 98 when their respective regions of the image to be encoded change due to boundary adaptation. In addition, when a boundary adaptation occurs, the processor 97 or 98 that acquires more image area to encode must receive the previously coded image plane (y, u, & v) macro row data for the image area it is now to encode and the MSE data for those macro rows. There are 144/16=9 macro rows per frame. This information provides the necessary data to perform accurate motion estimation.

The first processor 96 is also coupled to a host processor (not shown), such as the CPU of a personal computer, via a PC bus 100, an exchange register and a converter 101. The converter 101 preferably includes a field programmable gate array ("FPGA"), which produce, in response to decoded data provided by the first processor 96, 16 bit video data in RGB format for the personal computer to display. Alternatively, the converter 101 may include an FPGA that produces an 8 bit video data signal with an EPROM for color look-up table. A commercially available FPGA that is suitable for this application is available from Xilinx, part no. XC3090A. FPGAs from other manufacturers, such as Texas Instruments, part no. TPC1020A, may alternatively be used.

Referring now to FIG. 14B, the operation of the parallel processing architecture, as shown in FIG. 14A, will be described for use in an environment in which the incoming signal is a NTSC signal and the output is in RGB format.

Video Conference System Overview

Architectural Overview

The architecture of a video encoder/decoder 103 preferably includes three digital signal processors, two for video encoding and one for video decoding, data acquisition, and control. A high level view of this parallel processing architecture is shown in FIG. 14B. Within this architecture, a master/decoder processor 102 acquires digitized video data from a video interface 104, performs the pre- and post-processing of the video data, provides a host interface 106 (for bit-stream, control, and image information), decodes the incoming video bit-stream, and controls two slave encoder processors 108 and 110. The interaction between the master processor 102 and the slave encoders, 108 and 110, is through a direct memory access interface, such as the DMA interface 99 shown in FIG. 14A. The master/decoder processor 102 corresponds to the first processor 96 shown in FIG. 14A. The two slave encoder processors 108 and 110 correspond to the second and third processors 97 and 98 shown in FIG. 14A.

To communicate with the slave encoder processors, 108 and 110 the master processor 102 puts the slave encoder processors 108 and 110 into hold and then reads/writes directly into their memory spaces. This interface is used for writing new video data directly to the slave encoder processors 108 and 110, exchanging previously coded image ("PCI") data, and accepting encoded bit streams from both slave encoder processors 108 and 110. When outputting the decoded YUV data, the master processor 102 uses the YUV-to-RGB converter FPGA, as shown in FIG. 14A, to produce an 8-bit (with separate eprom for color look-up table), a 15 bit RGB, or 16-bit RGB video data for the PC to display.

High Level Encoder/Decoder Description

This section prioritizes and describes the timing relationships of the various tasks that make up the video encoder/decoder 103 and also describes the communication requirements for mapping the video encoder/decoder 103 onto three processors. The tasks will be grouped according to the various software systems of the video encoder/decoder 103. These software systems are:

1. Video Input

2. Encoding

3. Decoding

4. Video Output

5. Communication and Control

Each system is responsible for one or more distinct tasks and may reside on a single processor or, alternatively, may be spread over multiple processors. Data passing between processors is coordinated with a communication system residing on the master processor 102. The video input, video output, encoder, and decoder systems operate cyclically since they perform their task (or tasks) repeatedly.

Video Input System

The video input system has two aspects. First, a video image is collected. The video image is then processed (filtered) to spatially smooth the image and passed to the slave encoder processors 108 and 110. To maximize efficiency, the image may be transferred to the slave encoder processors 108 and 110 as it is filtered.

To collect the image, the master processor 102 receives data via the video interface 104. The video interface or video front end 104 includes an NTSC to digital YUV converter, for example. The chrominance components (UV) of the YUV data are preferably sub-sampled by a factor of two, horizontal and vertical, relative to the luminance component (Y), which is a 4:1:1 sampling scheme. NTSC provides video data at a rate of 60 fields per second. Two fields (and odd and even field) make up a single video frame. Therefore, the frame rate for NTSC is actually 30 frames per second. Two sampling rates seem to be prevalent for digitizing the pixels on a video scan line: 13.5 Mhz and 12.27 Mhz. The former gives 720 active pixels per line while the latter gives 640 active (and square) pixels per line.

The target display (VGA) uses a 640.times.480 format, therefore the 12.27 Mhz sampling rate is more appropriate and provides more time to collect data. The following assumes a sampling rate of 12.27 MHz and that one must collect 176 pixels on 144 or 146 lines of the image (QCIF format). The hardware and software described herein may be adapted to other input video formats and target display formats in a straightforward manner.

With the QCIF format, inter-field jitter may be avoided by collecting 176 samples on a line, skipping every other sample and every other line (i.e., taking every line in the given field and ignoring the lines of the other field). No noticeable aliasing effects have been detected with such a system, but anti-aliasing filters could be used to reduce aliasing.

Acquiring an image will take about 9.2 milliseconds (146 lines.times.1/15734 sec/line) using about 57% of the processor during those 9.2 milliseconds. While the image is being acquired, the master processor 102 collects and stores 176 video samples every 63.6 microseconds (1 line.times.1/15734 sec/line) at a rate of 6.14 MHz. Preferably, the front end video interface 104 interrupts the master processor 102 only at the beginning of every line to be collected. The video front end 104 will buffer 8 Ys and 4 Us and 4 Vs of video data at a time. Therefore, the master processor 102 preferably dedicates itself to video collection during the collection of the 176 samples that make up a line of video data. This may be accomplished using a high priority interrupt routine. The line collection interrupt routine is non-interruptable.

The time to collect the 176 samples of video data is 28.6 microseconds (1/(6.14 Mhz).times.176 pixels). The video input software system copies a portion of the collected data out of internal memory after the line has been collected. This will add about 8.8 microseconds to the collection of the odd lines of video data. The average total time to collect a line of video data is therefore 33 microseconds plus interrupt overhead. Assuming an average of 3 microseconds for interrupt overhead, the average total time to collect a line of video data is 36 microseconds. Therefore, processor utilization during the image acquisition is 57% (36 microseconds/63.6 microseconds.times.100). This constitutes about 8% (@ 15 frames/second) of the processor. Using this approach, the maximum interrupt latency for all other interrupts will be about 40 microseconds.

Once the image has been collected, it is preferably spatially lowpass filtered to reduce image noise. In the preferred embodiment, only the Y component is filtered. Assuming that only the Y component is filtered, the input image filtering and transfer task will consume about 10.5 msec or 15.7% of a frame time. U and V transfer will consume 340 microseconds or about 0.4% of the frame time. During the transfer of the image, the slave encoder processors 108 and 110 are in hold for a total of about 4 msec or about 6% of a frame time.

The present invention provides methods to enhance the motion estimation process by means of pre-filtering where the pre-filtering is a variable filter whose strength is set at the outset of a set of coded images to reduce the number of bits spent on motion estimation. For example, a temporal and/or spatial filter may be used before encoding an image to reduce the high frequency components from being interpreted as motion which would require more bits to encode. Typically two, one-dimensional filters are used--one in the horizontal direction and one in the vertical direction. Alternatively, other filters may be used, such as a two-dimensional filter, a median filter, or a temporal filter (a temporal filter would filter between two image planes--the one to be encoded and the previous one). As a further alternative, a combination of these filters could also be used for pre-filtering. The filter strength is set at the outset of each image macro block depending upon how much motion is present in a given macroblock.

High frequency components in the video image may arise from random camera noise and sharp image transitions such as edges. By using filters, high frequency components related to random camera noise are reduced so that they do not appear to the motion estimators as motion. Other examples of noise might include subtle amounts of motion which are not normally noticeable. That is, the goal of pre-filtering is to reduce noise artifacts and to some extent minor motion artifacts.

In addition to pre-filtering the input image signal, the master processor 102 may post-filter the encoded image signal. A temporal and/or spatial filter may be used to reduce high frequency artifacts introduced during the encoding process. Preferably, a variable strength filter based upon the hit-ratio of the predictors in the working set model is used. Thus, the filter strength is variable across the whole image. Post-filtering may be implemented using two, one-dimensional filters--one in the horizontal direction and one in the vertical direction. A median, temporal, or combination of filter types could also be used.

Encoding System

The image is in a packed format in the slave encoder processors' memory and is unpacked by the slave encoder processor once it receives the image. The encoding system is distributed over the two slave encoder processors 108, 110 with the resulting encoded bit streams being merged on the master processor 102.

The encoding system described herein allows interprocessor communication to synchronize and coordinate the encoding of two portions of the same input image. Once both the slave encoder processors 108 and 110 are ready to encode a new image, they will receive the image from the master processor 102. The slave encoder processors 108 and 110 then determine whether a scene change has occurred in the new image or whether the boundary needs to be changed. This information is then communicated between the two slave encoder processors.

If the boundary is to be changed, previously coded image (pci or PCI) data must be transferred from one slave encoder processor to the other. Boundary change is limited to one macro row per frame time where a macro row contains 16 rows of the image (16 rows of Y and 8 rows of U and V). In addition to the boundary change, extra PCI data needs to be exchanged to eliminate edge effects at the boundary line. This involves sending at least four additional rows from each slave encoder processor to the other. Assuming a one-wait state read and zero-wait state write time for interprocessor communication, the exchange of PCI data for a boundary change will take a maximum of 0.3% ((4 cycles/4 pixels).times.(16 rows Y.times.176 pixels+8 rows U.times.88 pixels+8 rows V.times.88 pixels).times.0.05 microseconds/cycle)/(66666 microseconds/frame.times.100%) for packed data and 1.3% of a frame time for byte-wide data. Preferably, the slave encoder processors 108, 110 use the unpacked format.

After the exchange of PCI data, the slave encoder processors encode their respective pieces of the video image. This process is accomplished locally on each slave encoder processor with the master processor 102 removing the encoded bits from the slave encoder processors 108, 110 once per macro row. A ping-pong buffer arrangement allows the slave encoder processors 108, 110 to transfer the previously encoded macro row to the master while they are encoding the next macro row. The master processor 102 receives the bits, stores them in an encoder buffer and ultimately transfers the encoded bit stream data to the PC host processor. As previously noted, the control structure of the encoder is demonstrated in the pseudo code at Appendix 2, Appendix 3 and Appendix 5.

Since the HVQC algorithm is a lossy algorithm, image degradation occurs over time. Therefore, the image encoding must be periodically stopped and a high quality reference image (a still image) must be transmitted. A distortion measure for each image to be encoded may be used to determine whether or not an image is to be encoded as a still image (when the video encoder can no longer produce acceptable results) or with respect to the previously coded image (video encoder can still produce an acceptable image).

At the beginning of each image, the slave encoder processors 108, 110 calculate a MSE for each 8.times.8 luminance (i.e. Y component, no chroma calculation) block. The sum of these MSEs is compared to a threshold to determine if a scene change has occurred. The background detector takes the sum of four--8.times.8 MSE calculations from the scene change test and uses that to determine if a macroblock is a background macroblock or not. 8.times.8 background detection is done by looking up the appropriate blocks MSE determined during the scene change test. Since the lowest level of the hierarchy and the still image level of the algorithm produce identical results, the use of a common VQ code and codebook for the still image encoder and the lowest hierarchical level of the encoder can save system size, complexity, and cost.

Preferably, each slave encoder processor, e.g. 108 and 110, calculates a scene change distortion measure, in the form of a MSE calculation, for the portion of the image that it is responsible for encoding. The slave encoder processor 108 then sums up all of the scene change MSEs from each of the slave encoder processors 108 and 110 to generate a total scene change MSE. In accordance with the preferred embodiment slave encoder, the slave encoder processor 110 passes its MSE calculation to the slave encoder processor 108 where it is summed with the slave encoder processor 108 MSE calculation to generate the overall scene change MSE.

In accordance with a preferred embodiment of the present invention, the three-step or the motion cache search processes are allowed to break out of the search loop (although the search process is not yet completed) because a "just good enough" match has been found. In the three-step search the distortion of the best-match is compared with the threshold in each level (there are a total of three to four levels depending on the search window size).

The search process may be terminated if at any level there is a motion vector whose resulting distortion is less than the threshold. Similarly, in the motion cache search, the resulting distortion of the motion vector in each cache entry (starting from the first entry) is compared with the threshold. The search process may be terminated if there is any entry whose resulting distortion is less than the threshold. The computational saving is significant in the motion cache search since the first entry is a most probable motion vector candidate and the method requires one MSE computation instead of L (L is the cache size) during a cache-hit. During a cache-miss, the computation increases slightly because more compares are required to implement the search process.

The bit-rate for a given frame may be reduced because the early cached motion vectors require fewer bits to encode, but this is sometimes offset by the bit-rate required by later frames because of the poorer previously coded image quality caused by the use of less precise motion vectors. Accordingly, the computational load of the encoder processors 108, 110 is reduced by thresholding each level of the three-step motion search and by thresholding each entry of the motion cache. This method may be applied to any block size at any level of the hierarchy.

In accordance with a preferred embodiment, the threshold to encode a given image block is limited to a pre-defined range, ›min.sub.-- t, max.sub.-- t!. Min.sub.-- t and max.sub.-- t are therefore further adapted on either a macro row-by-macro row basis or a frame-by-frame basis to have an even finer control over the image quality as a function of the bit-rate. The adaptation can be based on the scene-change MSE or on the image statistics of the previously coded frame.

In addition, the threshold at which a given image block is encoded may be controlled based upon the buffer fullness. In a preferred embodiment, the video encoder/decoder 103 uses piece-wise linear functions whose threshold value increase linearly with the buffer fullness. In a preferred embodiment, a distortion measure obtained by encoding an image area at a given level of the hierarchy may be compared against an adaptable threshold to enable a tradeoff between image quality, bit rate, and computational complexity. Increasing the thresholds will, in general, reduce the amount of computation, the bit rate, and the image quality. Decreasing the thresholds will, in general, increase the amount of computation, the bit rate, and the image quality. Different threshold adaptation methods include: updating after each macro row, updating after each of the largest blocks in the hierarchy (such as 16.times.16 blocks), or updating after every block of any size.

Adaptation strategy can be based on a buffer fullness measure, elapsed time during the encoding process, or a combination of these. The buffer fullness measure tells the encoder how many bits it is using to encode the image. The encoder tries to limit itself to a certain number of bits per frame (channel bit rate/frame rate). The buffer fullness measure is used to adapt the thresholds to hold the number of bits used to encode an image to the desired set point. There is a timer on the DSP and the system checks the timer at the beginning and end of the encoding process. As an image is encoded, the number of bits used to encode it must be regulated. This can be done by adapting the hierarchical decision thresholds.

Sometimes an image area may be encoded at a lower level of the hierarchy, but the gain in image quality is not significant enough to justify the additional bits required to encode it. In these cases, the determination as to which level of the hierarchy to encode an image can be made by comparing the distortion resulting from encoding an image area at different levels of the hierarchy to the number of bits required to encode the image area at each of those levels. The hierarchical level with the better bit rate-to-distortion measure is then the level used to encode that image area.

Further, encoding of the chrominance (U and V) components of an image may be improved by encoding them independently of the luminance component. The U and V components may also be encoded independently of one another. This may be achieved, for example, by encoding the chrominance components by using separate VQ caches and by using two-dimensional mean VQ. The system can either share motion information between the luminance and chrominance components to save bits, but possibly at lower image quality, or use separate/independent components at the expense of more bits to achieve higher image quality. The system can even do a partial sharing of motion information by using the luminance motion information as a starting point for performing a chrominance motion search. The decision of whether or not to share is made at the outset by how much bandwidth (i.e., bit rate) is available. In addition, it may be less expensive to make a system that shares motion information since less memory and computation would be required than if the chrominance components had to be independently determined.

Since spatially close image areas tend to be similar, it is preferable in a bit rate sense to encode these areas with similar mean values. To do this, the encoder may use various methods to compute the current image minimum and maximum mean quantizer values and then use these values to select a set of quantization levels for encoding the mean values of the variable sized image blocks. Basically this sets how many bits would be used to quantize a block with its mean value instead of a VQ value. If the block is of low activity (i.e., low frequency content), then it may be better in a bit rate sense to encode it with its mean value rather than using a VQ entry. Each block's mean value is then entered into the scalar cache. Pseudo code relating to this process is found at Appendix 2, Appendix 3 and Appendix 5.

Decoding System

The master processor 102 acquires the encoded bit stream data from the PC host (or from the encoders directly when in a command mode) and decodes the bit stream into frames of YUV image data. Control of the encoder processors bit rate generation is preferably achieved by sending the encoded bit streams to a processor, such as the processor 108, which feeds back rate control information to the encoder processors 108 and 110.

Generally, the HVQC algorithm allocates bits on an as needed basis while it encodes an image. This can present some image quality problems since initially, the encoder has many bits to use and therefore its thresholds may be artificially low. As coding progresses and the allocation of bits is used up, areas that require more bits to encode are unduly constrained. Therefore, the HVQC algorithm preferably examines the entire image data before the encoding of an image is begun to make an estimate of how many bits are to be used to code each area of the image. Thresholds may be determined not only by looking at how much distortion is present in the overall image as compared to the previously coded image, but also on a block by block basis and then adjusting the thresholds for those areas accordingly.

Since the decoder processor must track the encoder processors, it is important that the decoder processor track even in the presence of channel errors. This can be done by initialization of the VQ and motion caches to set them to a set of most probable values and then to re-initialize these caches periodically to prevent the decoder from becoming lost due to transmission errors.

The master processor 102 (i.e. decoder) preferably uses a packed (4 pixels per 32-bit word) format to speed the decoding process. In a preferred embodiment, this process takes about 30% of a frame time (@ 15 frames/second) per decoded image frame.

Once the decoded image is formed, the Y component is filtered and sent to the YUV to RGB converter. The filter and transfer of the Y and the transfer of the U and V components takes 15 msec or 22.5% of the frame. Pseudo code for the decoding operations is found at Appendix 2 and Appendix 5.

The most computationally intensive portions of the HVQC algorithm are its block matching computations. These computations are used to determine whether a particular block of the current image frame is similar to a similarly sized image block in the previously coded frame. The speed with which these calculations can be performed dictates the quality with which these computations can be performed. The preferred architecture can calculate multiple pixel distortion values simultaneously and in a pipelined fashioned so that entire areas of the image may be calculated in very few clock cycles. Accelerator algorithms are employed to calculate the distortion measure used in the hierarchical algorithm.

Since the amount of computation and bits spent encoding and refreshing an area of the picture is dependent upon the amount of time left to encode the image and the number of bits left to encode the image with, the overall image quality may be improved by alternating the scanning pattern so that no image blocks receive preferential treatment. The scanning pattern may correspond to scanning from the top of the image to the bottom or from the bottom to top.

During image scenes with large amounts of motion, the encoder can generate far more bits per image frame than the channel can handle for a given image frame rate. When this occurs, there can be a large amount of delay between successive image frames at the decoder due to transmission delays.

This delay is distracting. Take the example of a first person listening to and viewing an image of a second person. The first person may hear the voice of the second person but, in the image of the second person, the second person's mouth does not move until later due to the delay created by a previous sequence. One way to overcome this is to not encode more image frames until the transmission channel has had a chance to clear up, allowing reduction of latency by skipping frames to clear out the transmission channel after sending a frame requiring more bits than the average allocated allotment.

The system does two types of frame skipping. First, immediately after encoding a still image it waits for the buffer to clear before getting a new image to encode, as shown in the pseudo code below:

Second, when encoding video, a different method is used that is a little more efficient in that the processor does not have to wait for communications, but instead generates an estimation of how many frames to skip (based on how many bits were used to encode the last image) and then starts encoding the next frame after that, on the assumption that the buffer will continue emptying while the image is being collected and initially analyzed for a scene change. For instance, the following pseudo code demonstrates this process:

In addition, the software tells the video front end acquisition module when to capture an image for encoding by sending it a control signal telling it how may frames to skip (NumFramesToSkip).

The average allocated allotment of bits is determined by the channel bit rate divided by the target frame rate. It is calculated before each image is encoded so that it can be updated by the system.

Video Output System

The post decoder spatial filter is responsible for filtering the Y image plane and transferring the Y, U, and V image planes to the host. The filter operation preferably uses no external memory to perform the filter operations. This requires that the filter operation be done in blocks and the filtered data be directly transferred into a YUV to RGB FIFO. For this purpose, the block size is two lines. The filter uses a four line internal memory buffer to filter the data. The format of data for the YUV-to-RGB converter is shown in FIG. 15.

Task Prioritization and Timing Relationships

Task prioritization and timing are preferably handled by the master processor 102 since it controls data communication. Except where otherwise noted, task prioritization and timing will refer to the master processor 102.

The highest priority task in the system is the collection of input image data. Since there is little buffer memory associated with the video front end 104, the master processor 102 must be able to collect the video data as it becomes available. Forcing this function to have the highest priority causes the next lower priority task to have a maximum interrupt latency and degrades system performance of the lower priority task.

Slave processor communication is the next highest priority task. The slave processors 108, 110 have only one task to perform: encoding the video data. To accomplish this task, the slaves must communicate a small amount of data between themselves and the video image must be transferred to them by the master processor 102. This communication of data must take place in a timely fashion so as to not slow the slave processors 108, 110 down.

Next in the priority task list is the PC host communication. By far, the highest bandwidth data communicated between the master processor 102 and the PC host will be the RGB output data. Preferably, this data is double buffered through a FIFO. This allows the PC host the most flexibility to receive the data.

The remaining tasks (input image pre-processing and decoding) are background tasks. If one assumes that the master processor 102 is not over allocated (this must be true for the system to function) the background tasks will execute in a well-defined order. Once the input image is acquired, it will be filtered (pre-processed) and sent to the slave processors 108 and 110. The next background task will be to decode the bit stream coming from the PC host. Once this task is complete, the master processor 102 will post-process the image and transfer to the YUV-to-RGB FIFO as a foreground task.

Encoder Memory Organization

For the video encoder/decoder 103 described herein, the memory system has 128 kwords of 32-bit memory followed by 128 kwords of byte-wide memory that is zero filled between bits 9 to 23 bits and the remaining upper 8 bits float.

YUV-to-RGB Conversion

A FPGA has been designed that implements that RGB conversion using two-bit coefficients. The design requires nearly all of the logic units of a Texas Instruments TPC1020. The functions of this subsystem are to take data from an input FIFO and to convert this data to 15 or 16-bit RGB output. An interface is provided to an 8-bit EPROM to support 256 color VGA modes. Further details of this process are found below in the sections titled "YUV to RGB Conversion" and "Video Teleconferencing," and in Appendix 6.

Memory Requirements

This section summarizes the memory requirements of a preferred embodiment video algorithm. All multi-dimensional arrays are allocated as a matrix that allocates an array of pointers to point to each row of data. This requires an extra "num-rows" of data elements. For QCIF image planes this accounts for the extra 144 data words. This includes all of the large memory structures and most of the smaller structures. The process employed to derive memory requirements is found at Appendix 1.

Pre- and Post-Filtering

The pre- and post-filters are preferably row-column filters that filter the image in each dimension separately. The filter implementation may use internal memory for buffering. The internal memory is totally dynamic, i.e. it may be re-used by other routines. Less overhead will be incurred if the filter code is stored in internal memory (less than 100 words, statically allocated).

The pre-processing filter may be a five phase process. First, the data must be input from the video front end 104. Second, the row-wise filtering is performed. This filtering assumes a specific data format that contains two pixels per 32-bit word. The third phase reformats the output of the row-wise filter. The fourth phase performs the column-wise filter and fifth phase re-formats the data into whatever format the encoder will use.

The fastest way of implementing this method is with 7-bit data. If 8-bit samples are used, the performance will be degraded slightly. FIG. 16 shows the time for each phase assuming the encoder will be operating on byte packed data. This also assumes zero overhead for calling the function and function setup. It should be much less than one cycle per pixel (0.5 will be used in this discussion). The last phase consumes time in both the master processor 102 and encoder processors 108, 110, which is where the actual data transfer from master to encoder takes place.

Total processor utilization for filtering, Y, U and V at 15 frames per second can be calculated as follows (if just Y is filtered, the total time is reduced by 1/3):

Total master processor 102 utilization for 7-bit data is then 29.7%. For 8-bit data, the master processor 102 utilization is 32.5%. For both cases the encoder processor utilization is 3.5% (data transmission).

The post processing may also be accomplished using a five step process. The data must be reformatted from the packed pixel to a filter format. Step two filters the data column-wise. Step three reformats the data. Step four filters the data row-wise. Step five reformats and transmits the data to the YUV-to-RGB interface. FIG. 17 depicts the processor utilization (minus overhead) for these phases.

Total master processor 102 utilization for filtering 7-bit Y, U and V data is then 32.1%. For 8-Bit data the master processor 102 utilization is 35.7%. The output system is assumed to take data in the low byte at zero wait states.

Master processor 102 utilization may be decreased by more than 7% if the YUV-to-RGB interface could take two Ys at a time and both the U and V at a time in the format shown in FIG. 18. In addition, master processor 102 utilization may be decreased by at least 3% if the YUV interface could take the 8-bit data from either bits 8-15 or 24-31 of the data bus as specified by the address.

YUV-to-RGB Conversion

This section summarizes the YUV-to-RGB conversion of image data for Host display conversion. This section assumes the YUV components are 8-bit linearly quantized values. It should be noted that a Philips data book defines a slightly compressed range of values for the digital YUV representation.

Approximate coefficients may be implemented with only hardware adder/subtractors i.e., no multiplier, if the coefficients contain only two bits that were on (set to one). This effectively breaks the coefficient down in two one-bit coefficients with appropriate shifting. For lack of a better name, the rest of this section will call these coefficients "two-bit" coefficients. The two-bit coefficient method requires no multiplier arrays.

The actual coefficients are:

R=1.403.times.V+Y

G=Y-0.714.times.V-0.344.times.U

B=1.773.times.U+Y

Testing of the two-bit coefficients revealed no subjective difference when compared directly with the eight bit coefficients. The two-bit coefficient values are:

R=1.500.times.V+Y

G=Y-0.750.times.V-0.375.times.U

B=1.750.times.U+Y

Coefficient error ranges from 1.2% to 9%. The 9% error occurs in U coefficient of the G equation. This error is mooted by the other components of the equation. Shift operations do not involve logic. It is important to remember that the hardware must hard limit the RGB to 8-bits. Therefore, an overflow/underflow detector must be built into the hardware that implements this conversion.

Threshold Adaption

In a preferred embodiment, the video encoder system compares the mean squared error (MSE) between the current image and the last previously coded image to a threshold value. The video encoder looks at the ratio of buffer fullness to buffer size to determine how to set the g parameter for adjusting the threshold value. For a single encoder system, this is modified to be approximately:

(buffer fullness/buffer size)+(cumulative number of bits/expected number of bits) -0.4.

Both systems, single and dual encoder, perform their threshold adaptation strategy on a block-by-block basis, but do not take into account whether or not a particular block has a high MSE with respect to other blocks in the image. The following is a method for adapting thresholds in a way that will better allocate bits and computational power for single and multi-encoder systems.

As previously noted, the system does not compare the current block's MSE to the MSE of other blocks in the image, and therefore the system may spend a lot of time and bits trying to encode a given block when that time and those bits may have been better spent (proportionally) on other blocks with higher MSEs. This effect can be compensated for by using a block's MSE value to adjust its threshold level.

Since a scene change calculation is performed at the beginning of the encoding process for each frame, the MSEs for 8.times.8 blocks are readily available (stored in memory). In addition, the MSEs for 16.times.16 blocks are available from the 8.times.8 blocks by adding four localized 8.times.8 blocks together--this step is already done during the encoding process. By analyzing the MSE data before encoding, one can come up with any number of methods for partitioning the image blocks into various "bins" for allocating system resources so that the calculation time and encoding bits are efficiently distributed over the image. Each of these "bins" would specify a unique multiplicative constant to the threshold equation. This would allow more time and bits to be spent on the blocks that need it (those with a high MSE) and not waste those resources on blocks that do not.

Initially, the problem of how to classify image blocks can be addressed by having a fixed number of default MSE ranges (possibly derived from a series of test sequences) so that any given blocks' MSE value can be categorized with a lookup table. This could possibly be done at only the 16.times.16 block level so as to reduce the number of lookups to that required for the 99 blocks. The 16.times.16 block level category could then be extended down to the lower levels of the hierarchy. If calculation power permits, then the lower hierarchical levels could do their own categorization on a block-by-block basis. Ideally, this block-by-block categorization would occur at all levels of the hierarchy. Each of these categories would then be used to modify the threshold levels.

A fixed number of default MSE ranges could be extended to more ranges, or even turned into a function, such as a piece-wise linear curve. One could even base the ranges/function on the statistics of each individual image in a sequence (if one had the processing power). Any number of techniques could be employed.

The proposed enhancements should fit in with the buffer fullness constraint used by the preferred embodiment algorithm to adjust the thresholds by realizing that the ratio of bits calculated to bits expected can be re-calculated from the new distribution of expected bits for each block. That is, the bits expected calculation is no longer just a function of time, but instead is based upon both the elapsed time and the expected number of bits to encode each of the previously encoded blocks.

In addition, to adjust the number of expected bits used to encode a frame, the threshold for each block can be scaled by the following factor:

(allowed number of bits per frame).backslash.(sum of expected bits for all the image blocks).

The above ratio could be modified by using (allowed number of bits per frame-refresh bits per frame) in the numerator to allow for some amount of refresh to be performed each frame.

The proposed video coder algorithm enhancements distribute the bits spent encoding an image to those areas that need them in a mean squared error sense. Additionally, it helps with the computational processing power spent in encoding an image by also concentrating that power in those areas that need it in a mean squared error sense. This not only better utilizes resources in a multi-encoder environment, but it also helps with the realization of a 15 frames per second, 19.2 KHz, single video encoder/decoder system.

Further details of the process for adjusting the quality of the video coder with adaptive threshold techniques are found in the following section.

The quality and the bit rate of the video algorithm are controlled by the levels of the hierarchy that are used to encode the image. While encoding all the blocks with the 4.times.4 VQ results in the highest quality, it also imposes the largest bit-rate penalty, requiring over 3000 bits per macro row (over 27000 bits per frame). The hierarchical structure of the video coder addresses this problem by providing a collection of video coders, ranging from a very high coding gain (1 bit per 256 pixels) down to more modest coding gains (14 bits per 16 pixels). Adjusting the quality is the same problem as selecting the levels of the hierarchy that are used to encode the image blocks.

The selection of the levels of the hierarchy that are used and the particular encoders within each level of the hierarchy are controlled by thresholds. A distortion measure is calculated and this value is compared to a threshold to see if the image block could be encoded at that level. If the distortion is less than the threshold, the image block is encoded with that encoder. The thresholds are preferably adjusted for every image block based upon a measure of the image block activity (defined as the standard deviation).

The dependence on the block activity follows a psychovisual model that states that the visual system can tolerate a higher distortion with a high activity block than a low activity block. In other words, the eye is more sensitive to distortion in uniform areas than in non uniform areas.

The threshold value, T, that is used for any image block may be written as:

where N is the dimension of the image block (typically 16, 8, or 4), .sigma. is the standard deviation of the image block, .alpha. and .beta. are weighing parameters, and .gamma. an overall scale parameter whose value preferably varies based on buffer fullness and the type of encoding. The bias term, bias›N!, is used to compensate for the fact that at a given distortion value, a larger image block may appear to have lower quality than a smaller image block with the same distortion. The bias term, therefore, attempts to exploit this phenomena by biasing the smaller image block size with a larger threshold, i.e. larger bias›N!. In a preferred embodiment, the bias terms are: 1, 1.2, and 1.4 for 16.times.16, 8.times.8, and 4.times.4 image blocks, respectively.

In addition, there is a constraint that .alpha. and .beta. must sum to 1. In a preferred embodiment, .alpha.=0.2 and .beta.=0.8. A large value of .alpha. biases the encoder to put more emphasis on the variance of the image block so that higher variance blocks (i.e., higher activity blocks) are encoded at earlier levels of the hierarchy and at lower bit rates because there is a higher threshold associated with those blocks.

As noted above, the value of the scale parameter .gamma. preferably varies as the HVQC algorithm is applied. A larger value of .gamma. forces more image blocks to be encoded at the higher levels of the hierarchy because the threshold becomes much higher. On the other hand, when .gamma. is assigned a smaller value, more image blocks may be encoded at the lower levels of the hierarchy.

There is a different value of .gamma. for each of the individual encoders. In a preferred embodiment of the present invention, .gamma. is an array of eight elements, three of which may be used. These elements are shown in FIG. 19 in which .gamma. ranges from a low of 6 to a high of 80.

Gamma›BG16!, appropriately scaled by the bias term for other image block sizes, is used for all the background and motion tests. The actual value of gamma›BG16! used within the coder is determined by the buffer fullness. Smaller thresholds are used when the buffer is nearly empty and larger thresholds are used when the buffer is almost full. As shown in FIG. 20, the values for bgth16›0!, bgth16›1!, bgth16›2!, f1, and f2 used for a preferred embodiment are listed below. These values indicate that the system is operating with a set of relatively small thresholds (between bgth16›0! and bgth16›1!) until the buffer fills to 70 percent full. Above f2, the overflow value, bgth.sub.-- overflow is used. The following variables correspond to FIG. 20:

With respect to external controls, the channel capacity determines the bit rate that is available to the encoder. The bit rate, i.e. number of bits per second, is used in forming the encoder buffer size that is used in the ratio of the buffer fullness to buffer size. The buffer size is computed as 3.75.times.bits per frame. When used with the frame rate, the number of bits per frame can be determined. The bits per frame are used to determine if there are bits available for refreshing after the image has been coded.

Frame rate specifies what frame rate is used with the channel capacity to compute the number of bits per frame. The motion tracking number is used to scale the ratio of the buffer fullness to buffer size. A small number makes the buffer appear empty and hence more bits are generated.

Further details on threshold adjustment are found in Appendix 4, which contains code in the C programming language for computing thresholds.

System Software

The video encoder/decoder system 103 may be composed of three TMS320C31 DSP processors. Specifically, in the preferred embodiment, there is a master processor 102 and two slave processors 108, 110. Under this architecture, the master processor 102 is responsible for all data input and output, overall system control, coordinating interprocessor communication, decoding images and pre- and post-processing of the images, such as filtering. The slave processors 108, 110 are solely responsible for encoding the image.

The software system (micro-code) for the video encoder/decoder 103 is formed from three parts: the system software, encoding software and decoding software. The system software provides the real-time interface to the video source date, bit stream data, image transfer to the host and overall system control and coordination. This section is intended to give an overview perspective of the video encoder/decoder system software. The major data paths and data buffering will be described. Interrupt processing on the master processors is then discussed. A major portion of the section is dedicated to describing the system source code modules from an overview perspective.

There are two basic data paths in the video encoder/decoder 103. One is the encoder data path while the other is the decoder data path. For the encoder, the data path starts at a video source on the master processor 102, it is then filtered and transferred by the master to the slaves 108, 110. The slaves 108, 110 encode the data one macro row at a time sending the encoded bits back to the master processor 102. A macro row is a horizontal strip of the image containing 16 full rows of the image. The master processor 102 buffers these bits until the host requests them. The video source can be either the video front end 104 or the host depending on the video mode set in the video encoder/decoder 103 status. By default the video mode is set to the host as the source.

The decoder data path starts with encoded data flowing into the decoder buffer from either the host when in "Normal" or the encoder buffer when in "pass through" mode. The master processor 102 then decodes the encoded data into an image or frame. The frame is then filtered by the master processor 102 and transferred to the host through the YUV to RGB converter system two lines at a time. This converter system contains a FIFO so that up to five lines of RGB data can be buffered up in the FIFO at any given time. The data is synchronously transferred two lines at a time. In theory, the image can be filtered and transferred to the host in one long burst. In practice this is not completely true. For about 9 milliseconds of a frame time, interrupts from the video input line collection system can cause the video encoder/decoder 103 to not keep up with the host if the host is fast enough.

The decoded image that is to be filtered and passed to the host becomes the reference frame for the next decoded image. This provides a double buffer mechanism for both the filter/data transfer and the decoding process. No other buffers are required to provide a double buffer scheme.

Besides the major data paths, there is a small amount of data that must flow between the slave processors 108, 110 every frame. This data path is a result of splitting the encoding process between the two slave processors 108, 110. This data path is handled by the master processor 102.

The major data buffers for the video encoder/decoder 103 are the master video input data buffer, the master decoder image buffers, the master decoder encoded bit buffer, the master encoder encoded bit buffer, the slave encoded bit buffer, and the slave packed image buffers and the slave unpacked encoder image buffers.

The master video input data buffer consists of three buffers containing the Y, U & V image planes. The Y image is formatted with two pixels per word. The size of the Y buffer is 178.times.144/2 or 12,672 words. There are two extra lines to make the spatial filtering easier and more efficient. The Y data format and U & V data format are shown in FIG. 21.

The U & V images are packed four pixels per word in the format received from the video front end 104. The least significant byte of the word contains the left most pixel of the four pixels. The size of each U & V buffer is 89.times.72/4 or 1602 words. There is an extra line because the system is collecting two extra Y lines. The names of these buffers are inputY, inputU and inputV.

There are two master decoder image buffers. One is used to send a decoded image to the host and as a reference to decode the next image, while the other is used to build the next decoded image from the reference image. Because the reference image is undisturbed by the decoding process, it can also be transferred to the host. Once a newly decoded image has been formed, it is then used as the reference image for the next decode. This approach allows for concurrent decoding with image transfer.

The master decoder encoded bit buffer is used to store encoded bit data to be decoded by the decoder. The buffer is a circular buffer. The bits are stored in packets. Each packet has an integer number of macro rows associated with it. The first word in the packet contains the number of bits in the data portion of the packet. Each macro row within the packet starts on a byte boundary. Bits in between macro rows that make up the gap must be zero. These bits are referred to herein as filler bits. The last macro row may be filled out to the next byte boundary with filler bits (value zero).

The size of this buffer is set to 48 Kbits or 1536 words in a preferred embodiment. The size of this buffer could be reduced substantially. It is preferably large so that one can use different techniques for temporal synching. The decoder buffer is maintained through a structure known as MDecoder and reference by GlobalDecoder. MDecoder is of type ChannelState and GlobalDecoder is of type ChannelState.

The master encoder encoded bit buffer is used to combine and store encoded bit data from the slaves processors 108, 110. The buffer is a circular buffer. Each slave processor 108, 110 sends encoded bits to the master processor 102 one macro row at a time. As the master processor 102 receives macro rows from the slave processors 108, 110, it places them in the master encoded bit buffer in packet format. The lower 16 bits of the first word of each packet contain the number of encoded bits in the packet followed by the encoded bits. If the first word of the packet is negative it indicates that this packet contains what is known as a picture start code. The picture start coded packet delimits individual frames of encoded bits. Any unused bits in the last words of the packet are zero.

There are two slave encoded bit buffers, which are preferably "Ping-Pong" buffers. Each slave processor 108 or 110 contains a Ping-Pong buffer that is used to build and transfer encoded bits one macro row at a time. While one macro row is being encoded into one of the Ping-Pong buffers, the other is being transmitted to the master processor 102. Ping and pong may each have a size of 8192 bits. This restricts the maximum macro row size to 8192 bits.

The slave packed image buffer is used to receive the filtered video input image from the master processor 102. The Y, U & V image planes are packed 4 pixels per word. The sizes are preferably 176.times.144/4 (6336) words for y and 88.times.7/4 (1584) words for U & V. The encoder will unpack this buffer into an unpacked encoder image buffer at the start of an encoding cycle.

There are two slave unpacked encoder image buffers. One that is the current unpacked video image to be coded and one that is an unpacked reference image. At the beginning of a coding cycle the packed image buffer is unpacked into the current video image buffer. The reference image is the last encoded image. For still image encoding the reference image is not used. As the encoder encodes the current video image, the current video image is overwritten with coded image blocks. After the current image has been fully coded, it then becomes the reference image for the next encoding cycle.

The master processor 102 is responsible for video input collection and filtering, image decoding and post filtering, bit stream transfer both from the encoder to the host and from the host to the decoder, inter-slave communication and overall system control. The master processor 102 is the only processor of the three that has interrupt routines (other than debugger interrupts). The master has interrupt routines for the video frame clock, video line collection, RGB FIFO half full, exchange register in and out and the slave/debugger.

The highest priority interrupt is the video line collection interrupt. This is the only interrupt that is never turned off except to enter and exit a lower priority interrupt. Interrupt latency for this interrupt is kept to a minimum since the video line collection system has very little memory in it.

The next highest priority interrupt is the slave interrupt. This allows the slave processors 108, 110 to communicate between the slave and the master and also between slaves with the help of the master. Timely response to slave requests allows the slaves more time to do the encoding.

The next highest priority interrupts are the exchange register interrupts. There are two interrupts for each direction (four total) of the exchange register. Two are used to process CPU interrupts while the other two are used to process DMA interrupts (transfer). The CPU interrupt grants external bus access to the DMA that is a lower priority device on the bus thereby guarantying a reasonable DMA latency as seen from the host. When the master processor 102 turns off interrupts, the DMA can still proceed if it can gain access to the external bus. Normally, the only time the CPU interrupts are off is when the master is collecting a video input line or the master is trying to protect code from interrupts. In both cases, the code that is being executed should provide sufficient external bus access holes to allow for reasonable DMA latency times.

The next highest priority interrupt is the RGB FIFO half-full interrupt. This interrupt occurs any time the FIFO falls below half full. This allows the master processor 102 to continually keep ahead of the host in transferring RGB data assuming that the master is not busy collecting video line data.

The lowest priority interrupt is the frame clock that interrupts 30 times a second. This interrupt provides for a video frame temporal reference, frame rate enforcement and simulated limited channel capacity in "pass through" and "record" modes.

The software is structured to allow up to three levels of interrupt processing. The first level can process any of the interrupts. While the video line interrupt is being processed, no other interrupt can be processed. If the slave, frame or exchange register interrupt is being processed, the video line collection can cause a second level interrupt to occur. While the RGB interrupt is being processed, the slave, frame or exchange register can cause a second level interrupt to occur, and while that second level interrupt is being processed, the video collection interrupt could cause a third level interrupt.

The host communication interface is a software system that provides a system for communicating between the video encoder/decoder 103 and the host processor. There are two hardware interfaces to support this system. The former was designed for low bandwidth general purpose communication, while the later was designed to meet the specific need of transferring high bandwidth video data to be displayed by the host. Only the 16 bit exchange register can cause a host interrupt. Interrupts are provided for both the host buffer full and the from host buffer empty conditions.

As data is received from the host, it is processed by a protocol parsing system. This system is responsible for interpreting the header of the protocol packets and taking further action based on the command found in the header. For protocol packets that contain data, the parser will queue up a DMA request to get the data. The name of the protocol parser is HOST.sub.-- in() and can be found in the file host.sub.-- if.c.

Data to be sent to the host takes one of two forms. It is either general protocol data or YUV data to be converted to RGB. In either case the data is sent to the host through a queuing system. This allows for the master processor 102 to continue processing data (decoding) while the data transfer takes place. The system is set up to allow 20 outstanding messages to be sent to the host. In most cases, there will be no more than 2 or 3 outstanding messages to be sent to the host.

Although YUV data is sent through the YUV to RGB converter system, the associated message informing the host of data availability is sent through the exchange register. This system contains a FIFO that will buffer up to 5 full lines of YUV data. When YUV data is ready to be sent to the host, the master processor places the data into the YUV to RGB FIFO, either two or six lines at a time depending on the size of the image. Each time the two or six lines are placed into the FIFO, the master processor 102 also queues up a protocol message to the host indicating that it has placed data in the FIFO. The master processor 102 will place data in the FIFO any time the FIFO is less than half full (and there is data to be sent). This allows the master processor 102 to keep ahead of the host unless the master processor 102 is collecting a line of video data or moving PCI data from one slave processor to the other (i.e., has something of a higher priority to do).

YUV frames are queued up to be sent to the host with the RGB.sub.-- queue() function. Packets of data to be sent to the host are queued up with the HOST.sub.-- queue() and HOST.sub.-- queueBitBuffer() functions. The HOST.sub.-- queue() function issued to queue up standard protocol packets. The HOST.sub.-- queueBitBuffer() is used to queue up a bit stream data buffer that may contain several protocol packets containing bit stream information (macro rows). The HOST.sub.-- vsaRespond() function issued to send status information to the host. Further details of the video encoder/decoder host software interface are provided below.

The video front end interface is responsible for collecting and formatting video data from the video capture board. From the application level view, the video front end system collects one frame at a time. Each frame is collected by calling the VIDEO.sub.-- start() function. The video start function performs several tasks. First, it looks at the video encoder/decoder status and sets the pan, pre-filter coefficients, frame rate, brightness, contrast, hue and saturation. Then it either arms the video front end 104 to collect the next frame or defers that to the frame interrupt routine depending on the state of the frame sampling system.

The frame sampling system is responsible for enforcing a given frame rate. If the application code requests a frame faster than the specified frame rate, the sampling waits an appropriate time before arming the video collection system. This system is implemented through the frame clock interrupt function FRAME.sub.-- interrupt(). The FRAME.sub.-- interrupt() function is also responsible for coordinating the simulated limited channel capacity in "record" and "pass-through" modes. It may do this by requesting that encoded bits be moved from the encoder buffer to their destination on every frame clock. The amount of data moved is dependent on the specified channel capacity.

Once the video front end system has been armed, it will collect the next frame under interrupt control. The video lines are collected by two interrupt routines. One interrupt routine collects the even video lines and the other interrupt routine collects the odd lines. This is necessary to save time since it is necessary to decimate the U&V components in the vertical direction. The even line collection interrupt routine collects and places the Y component for that line into an internal memory buffer. The U&V components are stored directly to external memory. The odd line collection interrupt routine discards the U&V components and combines the Y components from last even line with the Y components from the current line and places these in external memory. The format of the Y image is compatible with the spatial filter routine that will be used to condition the Y image plane.

Since the video line collection interrupts could interrupt code that has the slave processors 108, 110 in hold (master processor 102 accessing slave memory), the interrupt code releases the hold on the slave processors 108, 110 before collecting the video line. Just before the interrupt routine returns, it restores the previous state of the slave hold.

The front end spatial filter is responsible for filtering and transferring the Y image plane to the slave processors 108, 110. The image is transferred in packed format (four pixel per word). The slave processors 108, 110 are put into hold only when the data transfer part of the process is taking place. Two lines of data are filtered and transferred at a time. The function InputFilterY() is used to filter and transfer one Y image plane.

The U&V image planes are transferred to the slave using the moveImageToSlave() function. This function moves the data in blocks from the master to the slave. The block is first copied into internal memory, then the slave is placed into hold and the data is copied from internal memory to the slave memory. The slave is then released and the next block is copied. This repeats until the entire image is moved. The internal memory buffer is used because this is the fastest way to move data around in the C31 processor.

The post decoder spatial filter is responsible for filtering the Y image plane and transferring the Y,U&V image planes to the host. The filter operation uses no external memory to perform the filter operations. This requires that the filter operation be done in blocks and the filtered data be directly transferred into the YUV to RGB FIFO. For this purpose, the block size is two lines.

The filter uses a four line internal memory buffer to filter the data. To get things started (i.e., put two lines into the internal memory buffer and initialize the filter system) the function OutputFilterYinit() is used. Each time the system wishes to place two more lines of data into the FIFO it calls the OutputFilterY() function. These two functions are used exclusively to filter and transfer an image to the FIFO. They do not coordinate the transfer with the host. Coordination is performed by the RGB back end interface described next.

The RGB back end is responsible for coordinating the transfer of selfview and decoded images to the host. In the case of the decoded image, the Y plane is also spatially filtered. There are three types of images that can be transferred. They are a decoded image of size 176.times.144, a selfview image of size 176.times.144 and a selfview image of size 44.times.36. The video encoder/decoder system is capable of transferring both a selfview and a decoded image each frame time. The smaller selfview image is a decimated version of the larger selfview image.

Whenever the application code wants to send an image to the host it calls the RGB.sub.-- queue() function passing it the starting address of the Y,U&V image planes and what type of image is being transferred. The queuing system is then responsible for filtering if it is a decoded image and transferring the image to the host. Selfview images are not filtered. The queuing system can queue up to two images. This allows both a selfview and a decoded image to be simultaneously queued for transfer.

The images are transferred to the host in blocks. For the large images, the transfer block size is two lines. For the small image, the transfer block size is six lines. This makes the most effective use of the FIFO buffer in the YUV to RGB converter while allowing the host to extract data while the C31 is filling the FIFO.

The mechanisms used to trigger the filtering/transfer or transfer of the image block is the FIFO half full interrupt. When the FIFO goes from half full to less than half full it generates an interrupt to the C31. This interrupt is processed by the RGB.sub.-- interrupt() function. The interrupt function filters and transfers a block of data using the OutputFilterY() function in the case of a decoded image. In the case of a selfview image, the interrupt function copies the image block using the OutputY() function for a large selfview image or the OutputYsmall() function for the small selfview image. The OutputFilterY() and OutputYsmall() functions also transfer the U&V image planes.

The RGB.sub.-- dropCurrent() function is called whenever the video encoder/decoder 103 wants to stop sending the current image to the host and start processing the next image in the queue. This function is called by the host interface when the host sends the drop frame protocol packet.

The slave communication interface is used to coordinate the transfer of video images to the slaves, transfer encoded bit stream data from the slave processors 108, 110 to the master processor 102, transfer data between the slaves and transfer data from the slaves to the host. The latter provides a way to get statistical data out of the slave processors 108, 110 and is used for debugging only. When a slave needs service it interrupts the master processor 102. The interrupt is processed by the SLAVE.sub.-- request() function. The types of slave requests that can be processed are:

The request "Request New Frame" is made right after the encoder unpacks the packed video image at the beginning of an encoding cycle. SLAVE.sub.-- request() simply records that the slave wants a new frame and returns from the interrupt. The main processing loop is then responsible for filtering and transferring the new image to the slave. Once the main processing loop has transmitted a new image to the slave the newFrameAvailable flag in the communication area is set to TRUE.

The request "Request Scene Change Information" is used to exchange information about the complexity of the image for each slave. If the value exchanged is above some threshold, both slaves will encode the frame as a still image. The slaves transmit their local scene change information to the master as part of this request. Once both slaves have requested this information, the master exchanges the sceneValue in the respective communication areas of the slave processors 108, 110 with the other slave's scene change information.

The request "Request Refresh Bits" is similar to the scene change information request. The difference is that it is requesting a different type of information. However, this information is exchanged just like the scene change information.

There are two types of buffer fullness requests. In one case the master responds instantly with the size of the master's encoder encoded bit buffer. In the other case, the slave is wanting to wait until the master encoder buffer is below a specified size and for the other slave to request this information.

The request "Request PCI" is used to send or receive previously coded image data to or from the other slave processor. This is used when the adaptive boundary is changed. There are two forms of this request. One for sending PCI data and one for receiving PCI. After one slave sends a receive request and the other sends a send request, the master processor 102 then copies the PCI data from the sender to the receiver.

The request "Send Encoded Bits" is used to transfer a macro row of data to the master to be placed in the master's encoder encoded bit buffer. There are two forms of this request. One to send a picture start code and one to send a macro row. The picture start code is sent before any macro rows from either processor are sent.

The request "Acknowledge Slave Encoder Buffer Cleared" is used to acknowledge the master's request for the slaves to clear their buffers. This allows the master processor 102 to synchronously clear its encoder bits buffer with the slave clearing its buffer.

The request "Send Data to Host" is used to transmit a data array to the host processor. This is used to send statistical data to the host about the performance of the encoder.

The master processor 102 can send messages to the slave through the SLAVE.sub.-- inform() function. The slave processors 108, 110 are not interrupted by the message. The slaves occasionally look (once a macro row or once a frame) to see if there are any messages. The types of messages are as follows:

The message "Image Ready" informs the slave that a packed image is ready.

The "Clear Encoder Buffer" message tells the slave to clear its Ping-Pong bit buffers and restart the encoding process with the next video frame. The slave will respond after resetting its buffers by sending back an acknowledgment (Acknowledge Slave Encoder Buffer Cleared).

The "Still Image Request" message is used to tell the slave to encode the next frame as a still image.

The "Scene Change Information" message is used to respond to the slaves request to exchange scene change information.

The "Refresh Bits" message is used to respond to the slaves request to exchange refresh bit information.

The "Buffer Fullness" message is used to respond to the slaves request to wait until the size of the master's encoder encoded bit buffer has fallen below a certain level.

The master bit buffer interface is responsible for managing the encoder encoded bit buffer and the decoder encoded bit buffer on the master processor 102. The bit buffers are managed through a structure of type ChannelState. The bits are stored in the buffer in packets. A packet contains a bit count word followed by the encoded bits packed 32 bits per word. Bits are stored most significant to least significant. The important elements of this structure used for this purpose are:

wordsinBuffer This contains the current number of words in the buffer. This includes the entire packet including the storage for the number of bits in the packet (see description of bit data buffers above)

BufferIndex This is the offset in the buffer where the next word will be taken out.

BufferIntPtrindex This is the offset in the buffer where the next word will be placed. If BufferintPtrindex is equal to Bufferindex there is no data in the buffer.

BufferFullness This measures the number of bits currently in the buffer. This does not include unused bits in the last work of a packet or the bit count word itself.

It only includes the actual bits that will be decoded. It does include any fill bits if they exist.

bitPos This points to the current bit in the current word to be decoded.

This is not used for the Encoder buffer.

bitsdLeftInPacket This is used to indicate how many bits are left to be decoded in the decoder buffer. This is not used for the encoder buffer.

pastBits This is used for keep track of the past bits when checking for unique picture start codes. This is not used otherwise.

buffer This is a pointer to the beginning of the bit buffer.

There are two functions that can place data into the decoder buffer. They are putDecoderBits() and encoderToDecoder(). The function putDecoderBits() is used to put bits from the host into the decoder buffer. The encoderToDecoder() function is used in the "pass-through" mode to move bits from the encoder buffer to the decoder buffer.

The getBits() function is used to extract or look at a specified number of bits from the current bit position in the buffer. The bitsInPacket() function is used to find how many bits are left in a packet. If there are no bits or only fill bits left in the packet the size of the next packet is returned. The skipToNextPacket() function is used when the decoder detects an error in the packet and wants to move to the next packet ignoring the current packet.

The moveEncoderBits() function is used to simulate a limited channel capacity channel when the system is in the "record" or "pass-through" mode.

The getEncoderBits() function is used to move encoder bits from the master processor 102 encoder encoded bit buffer to the host. This is used in the real-time mode when there is a real limited bit channel system (like a modem) requesting bits from the video encoder/decoder system.

The encoderToHost() function is used to build a host protocol buffer from the encoder buffer. The host protocol buffer can contain multiple protocol packets. This function is called by the moveEncoderBits() and getEncoderBits() functions.

The main() function and main processing loop, masterLoop() is responsible for coordinating a number of activities. First it initializes the video encoder/decoder 103 subsystems and sends the initial status message to the host. It then enters a loop that is responsible for coordinating 6 things.

1. Filtering and transferring the input video image to the slaves.

2. Video input capture.

3. Transfer of selfview image to the host.

4. Transfer of YUV image to host.

5. Decoding and transfer of the decoding image to the host.

6. Transfer of encoder encoded bits to host under certain conditions.

If an input video frame is ready and the slave has requested a new frame, the main processing loop does the following. If the video encoder/decoder 103 status indicates that a selfview image should be sent to the host and the video encoder/decoder 103 is not currently sending a selfview frame, it will queue up the new frame to be sent to the host. It will then filter and transfer the new frame to the slave processors 108, 110. This process does not alter the input image so it does not effect the selfview image. If the host has requested that the frame be sent in YUV format, the YUV image will then be transmitted to the host in YUV format. Finally, the video input system will be restarted to collect the next frame.

If the decoder state is non-zero and the processing loop was entered with a non-zero flag, the DECODE.sub.-- image() function is called to coordinate the decoding and transfer to the host of the next video frame.

The last part of the main processing loop checks to see if encoded bits can be sent to the host if any are pending to be sent. If the host had requested encoder encoded bits and the encoder buffer was emptied in the host interrupt processing function before the request was satisfied the interrupt routine must exit leaving some number of bits pending to be transmitted.

The DECODE.sub.-- image() function is responsible for coordinating the decoding process on a frame by frame basis and the transmission of the decoded frames to the host. A flag is used to coordinate the decoding and transferring of decoded images. The flag is called OKtoDecode. It is not OK to decode if there is a decoded frame currently being transmitted to the host and the next frame has already been decoded. This is because the decoder needs the frame being transmitted to construct the next decoded frame.

Once that old frame has been completely transmitted to the host, the recently decoded frame is queued to be transmitted and the decoding process can continue. If the decoder bit buffer starts to back up (become full) the decoder will go on without queuing up the previously decoded image. This results in the currently transmitted image being overwritten with newly decoded data. This could cause artifacts in the frame being sent to the host.

The decoding process gets or looks at bits in the decoder buffer by calling the getBits() and bitsInPacket() function. If during the decoding process, the getBits() or the bitsInPacket() function finds the decoder buffer is empty, it waits for the buffer to be nonzero. While it waits it calls the masterLoop() function with a zero parameter value. This allows other tasks to be performed while the decoder is waiting for bits.

The slave processors 108, 110 are responsible for encoding video frames of data. This is their only responsibility, therefore there is not much system code associated with their function. The slave processors 108, 110 do not process any interrupts (except for the debugger interrupt for debugging purposes). There is a simple communication system that is used to request service from the master. All communication from the master to the slave is done on a polled basis.

The slave and the master communication through a common communication structure located at 0.times.400 in the slave address space. The structure is defined in the slave.h file as a typedef SLAVE.sub.-- Request. The name of this structure for the slave processor is SLAVE.sub.-- com. The master processor 102 accesses the communication area at offset 0.times.400 in the slave memory access window. For slave 1, the communication structure would reside at location 0xa00400 in the master processor 102. For slave 2, the communication structure would reside at location 0xc00400. In order for the master to gain access to this structure, it must first place the slave(s) into hold.

Every time the slave processor needs to request service from the master processor 102 it first checks to see if the master has processed the last request. It does this by checking the hardware bit SEx.sub.-- THBE (where "x" indicates slave encoder processor is to be checked) that indicates that the slave is currently requiring service from the master. If the master has not processed the last request the slave waits until it has. When there is no pending service, the slave places a request or command in the communication structure element name "cmd". It also places any other data that the master will need to process the command in the communication structure. If the communication requires synchronization with the other slave or a response before the slave can continue, the slave also sets the communicationDone flag to FALSE. Then the slave sets the hardware request flag. If the slave needs a response before going on it will poll the communicationDone flag waiting for it to go TRUE. Once the flag is TRUE, any requested data will be available in the communication structure.

Video Bit Stream

This section describes the bit stream that is in use in the video encoder/decoder system when compiled with picture start code (PSC) equal to four. This section addresses the header information that precedes each macro row and the format of the bit stream for video, still, and refresh information.

FIG. 22 shows a high level example of a video bit stream where the video sequence includes the first frame coded by the still image coder and the second frame coded by the video coder followed by the refresh data for part of the macro row.

To accommodate macro rows that may be dropped by the supervisor instead of being sent to the decoder because of channel errors, the decoder can decode each macro row in a random order and independently from other macro rows. This flexibility is achieved by adding a macro row address (macro row number) and macro header information to each encoded macro row.

To support macro row independence, each of the motion caches must be reset before encoding and decoding each macro row. This modification results in a slightly lower PSNR (0.1 dB) for a number of file-io sequences, but it was seen to have no perceptual degradation in both the file-io and the real-time simulations. The motion vectors should be reset to some small and some large values to account for the high-motion frames (the latest source code resets to only small motion vectors). The still image encoder is also macro row addressable, and therefore the still image VQ cache should be reset before encoding and decoding each macro row.

There are four compiling options that affect how header information is added to the bit stream. These options are controlled by the compiler define switch PSC which is set in the master and slave make files. The meaning of the different values of PSC are detailed in FIG. 23. Referring to FIG. 23, the default configuration of the encoder/decoder is PSC=4.

Macro rows of data may have leftover bits that are used to align the macro rows to byte boundaries. There will always be fewer than eight fill bits and their value will be zero. They will be a part of the bit stream, but the decoder knows not to interpret them.

This use of fill bits and packetizing the macro rows has ramifications for detecting bit errors because it indicates (without decoding the data) the boundaries of the macro rows. This information can be used to skip to the next macro row packet in the event the decode becomes confused.

By aligning the macro row packets of encoded data on known boundaries such as, for example, byte boundaries, the decoder can determine whether it has left over bits, or too few bits, for decoding the given macro row. Once errors are detected, error concealment strategies of conditionally replenishing the corrupted macro rows can be performed and decoding can continue with the next macro row packet of data. This allows the detection of bit errors through the use of the macro row packetized bit stream.

The format of the encoded data depends on the type of encoding (video or still) and at which level of the hierarchy the bits are generated. Regardless of the type of data, each macro row of data begins with the macro header, defined as follows.

Video, still images, and refresh data are encoded on a macro row basis and packetized according to their macro row address. The header information for each macro row includes the fields shown in FIG. 24. The amount of overhead is 8 bits per macro row. The information is found in the bit stream in the order given in FIG. 24, i.e., the data type is the first two bits, the macro row address the next four bits, etc.

Referring to FIG. 24, the data type (DT) (2 bits) specifies what type of data is encoded: 00 means video data, 01 means still image data, 10 represents VQ refresh data, and 11 represents scala refresh data. The macro row address (MRA) (4 bits) specifies which of the nine (for QCIF) macro rows the encoded data corresponds to. The value in the bit stream is the macro row address plus five. The HVQ structure bit (HS) (1 bit) specifies whether the structure of the encoder hierarchy for the macro row has been modified to support the working set model (HS=1) or is using the 4.times.4 motion cache (HS=0). This bit is ignored by the still image decoder and the refresh decoder. The relative temporal reference (RTR) (1 bit) signifies whether the encoded macro row is part of the current frame or the next frame. The value toggles between 0 and 1 when the frame changes. All macro rows encoded from the same input frame will have the same RTR. It is important to note that the RTR is not the least significant bit of the absolute frame reference. The RTR is an independent flag that differentiates between this frame and the next frame.

In addition to the macro row header information, macro row zero (for video and still data types, not for refresh) contains the temporal reference information and once every 15 frames, frame rate information, and possibly other information as specified by a picture extended information (PEI) bit. The format of the extended macro row zero information is shown in FIG. 25.

Every macro row zero that contains either video or still encoded data has a 6 bit temporal reference that counts the absolute frame number, modulo 60. If the value of the PEI after the temporal reference is found to be 1, the next 6 bits correspond to the frame rate divisor. The decoder uses the frame rate information and the temporal reference information to synchronize the output display of the decoded images. The frame rate divisor is sent once every 15 frames by the encoder. The actual frame rate is calculated by dividing 30 by the frame rate divisor. The value of 0 is used to tell the decoder that it should not try to time synchronize the display of decoded images.

After the frame rate information, another PEI indicates whether there is other information available in the bit stream. The decoder will continue to read and throw away these 6 bit fields and then check for another PEI. The cycle continues until the value of the PEI is found to be 0.

Video images use a quad-tree decomposition for encoding. The format of the output bit stream depends on which levels of the hierarchy are used and consequently follows a tree structure. The bit stream is perhaps best described through examples of how 16.times.16 blocks of the image are encoded. Considering that a QCIF image is composed of 99 16.times.16 blocks. FIG. 26 shows several different decompositions for 16.times.16 blocks and the resulting bit stream. The notation of Flag.sup.c indicates the complement of the bit stream flag as defined in FIG. 27, which depicts the flags used to describe the video bit stream. There are three valid data items that have been added to the cache during the encoding process. Miss entries are entries to indicate that suitable entry was not found in the cache. Invalid entries are entries that do not contain valid data because they represent uninitialized values.

Referring to FIG. 26, part a., the 16.times.16 block is encoded as a background block. In part b., the 16.times.16 block is coded as an entry from the motion 16 cache. In part c., the 16.times.16 block is encoded as a motion block along with its motion vector. In part d., the 16.times.16 block is decomposed into 4 8.times.8 blocks which are encoded as (starting with the upper left block) as a background 8.times.8 block, another background 8.times.8 block, a hit in the motion 8 cache, and as an 8.times.8 motion block and the associated motion vector. In part e., the 16.times.16 block is divided into 3 8.times.8 blocks and 4 4.times.4 blocks. The upper left 8.times.8 block is coded as a motion 8 cache hit, the second 8.times.8 block is decomposed and encoded as a VQ block, a hit in the motion 4 cache, the mean of the block and finally as a VQ block. The third 8.times.8 block is encoded as an 8.times.8 motion block and its motion vector and the final 8.times.8 block is encoded as a motion 8 cache hit.

With respect to color information and flag bits, the color information is coded on a block by block basis based on the luminance coding. FIG. 28 shows some sample decompositions of color (chrominance) 8.times.8 blocks and descriptions of their resulting bit streams.

Still images are encoded in terms of 4.times.4 blocks. The coding is performed using a cache VQ technique where cache hits require fewer bits and cache misses require more bits to address the VQ codebook. Assuming that each 4.times.4 block is coded sequentially (there are a total of 1584 4.times.4 luminance blocks), FIG. 29 shows an example of coding 4 luminance blocks. Here, Mn.sub.1 is the mean of the first block, Mn.sub.4 is the mean of the fourth block, VQ.sub.1 and VQ.sub.4 are the VQ addresses of the first and fourth block, respectively, and C.sub.2 and C.sub.3 are the variable length encoded cache locations. C.sub.1 and C.sub.4 are invalid cache positions that are used as miss flags. The VQ addresses have one added to them before they are put into the bit stream to prevent the all-zero VQ address.

After every four 4.times.4 luminance blocks have been encoded, the corresponding 4.times.4 chrominance blocks (first U and then V) are encoded using the same encoding method as the luminance component. Different caches are used for the color and luminance VQ information.

Since the coder is lossy, the image must be periodically re-transmitted to retain a high image quality. Sometimes this is accomplished by sending a reference image called a "still." Other times the image can be re-translated piece-by-piece as time and bit rate permit. This updating of portions of the encoded image can be done through various techniques including scalar absolute refreshing, scalar differential refreshing, block absolute refreshing, and block differential refreshing.

Refresh is used to improve the perceptual quality of the encoded image. In the absence of transmission errors, the coded image is known to the transmitter along with the current input frame. The transmitter uses the latter to correct the former provided that the following two conditions are true: first, that the channel has extra bits available, and second that there is time available. Whether or not there are bits available is measured by the buffer fullness; refreshing is preferably performed only when the output buffer is less than 1/3 full. Time is available if no new input frame is waiting to be processed. The two independent processors also perform their refreshing independently and it is possible on some frames that one of the processors will perform refreshing while the other does not.

There are two levels of refreshing--block based or VQ (4.times.4) and pixel based refreshing. The refresh header information includes the fields shown in FIG. 30. Each of these levels is further divided into absolute and differential refresh mode with the mode set by a bit in the header.

Referring to FIG. 30, the refresh header information includes the field of the macro row header. Note that the extended macro row zero information does not apply to the refresher information, i.e., refresh macro rows do not contain extended information about the temporal reference and frame rate. The refresh address field specifies the starting 4.times.4 block that the refresher is encoding within the specified macro row. For QCIF images, there are 176 4.times.4 blocks in each macro row. The bit stream interface adds 31 to the refresh block address to prevent the generation of a picture start code. The decoder bit stream interface subtracts this offset.

The "number of 4.times.4 blocks" field enumerates the number of 4.times.4 blocks of the image that are refreshed within this macro row packet. This field removes the need for a refresh end code.

As discussed, the system uses both VQ or block and scalar refreshing. The absolute refresher operates on 8.times.8 blocks by encoding each of the four luminance 4.times.4 blocks and single U and V 4.times.4 blocks independently. This means that the refresh information will always include an integer multiple of four luminance 4.times.4 blocks and one U and one V 4.times.4 block.

This section describes the VQ refreshing that occurs on each 4.times.4 luminance block and its corresponding 2.times.2 chrominance blocks through the use of 2, 16, or 24 dimensional VQ codebooks.

For VQ refreshing, each 4.times.4 luminance block has its mean and standard deviation mean calculated. The mean is uniformly quantized to 6-bits with a range of 0 to 255 and the quantized 6-bit mean is put into the bit stream. If the standard deviation of the block is less than a threshold, a flag bit is set and the next 4.times.4 luminance block is encoded. If the standard deviation is greater than the threshold, the mean is removed from the block and the 255 entry VQ is searched. The 8-bit address of the VQ plus one is placed into the bit stream (zero is not allowed as a valid VQ entry in a preferred embodiment--the decoder subtracts one before using the address).

The mean and standard deviation of the associated 4.times.4 U and V blocks are computed. If the maximum of the U and V standard deviations is less than a threshold then the U and V means are used to search a two-dimensional mean codebook that has 255 entries. The resulting 8-bit VQ address plus one is put into the bit stream. If the maximum of the U and V standard deviations is greater than the threshold a 16-dimensional 255-entry VQ is searched for both the U and the V components. The two resulting 8 bit VQ addresses plus one are put into the bit stream.

VQ refreshing may be absolute of differential. For absolute VQ refreshing (19 bits per 4.times.4 block), each 4.times.4 luminance block has its mean calculated and quantized according to the current minimum and maximum mean for the macro row, and the 5-bit quantized value is put into the bit stream. The mean is subtracted from the 4.times.4 block and the result is used as the input to the VQ search (codebook has 255 entries). The resulting 8-bit VQ address is placed into the bit stream. The means of the 2.times.2 chrominance blocks are used as a 2-dimensional input to a 63 entry VQ. The resulting 6-bit address is placed into the bit stream. The result is 19 bits per 4.times.4 block.

For differential VQ refreshing (8 bits per 4.times.4 block), each 4.times.4 luminance block and the associated 2.times.2 chrominance blocks are subtracted from their respective values in the previously coded frame. The difference is encoded as an 8-bit VQ address from a 24-dimensional codebook that has 255 entries. The result is 8 bits per 4.times.4 block.

Scalar refreshing is a mode that is reserved for when the image has had VQ refreshing performed on a large number of consecutive frames (for example, about 20 frames). This mode has been designed for when the camera is pointing away from any motion. The result is that the coded image quality can be raised to near original quality levels.

As with block refreshing, scalar refreshing may be either absolute or differential. For absolute scalar refreshing (168 bits per 4.times.4 block), the 4.times.4 luminance and 2.times.2 chrominance blocks are encoded pixel by pixel. These 24 pixels are linearly encoded with 7-bit accuracy resulting in 168 bits per 4.times.4 block.

For differential scalar refreshing (120 bits per 4.times.4 block), the 4.times.4 luminance and 2.times.2 chrominance blocks are encoded pixel by pixel. First the difference between the current block and the previously code block is formed and then the result is coded with 5 bits for each pixel (1 for the sign and 4 for the magnitude). The resulting 4.times.4 block is encoded with 120 bits.

The system selects one of the available methods of refreshing. The mode selected is based upon how many bits are available and how many times an image has been refreshed in a given mode. In terms of best image quality, one would always use absolute scalar refreshing, but this uses the most bits. The second choice is differential scalar refreshing, followed by absolute VQ, and finally differential VQ. In pseudo code the decision to refresh using scalar or VQ looks like this:

where cumulative.sub.-- refresh.sub.-- bits is a running tally of how many bits have been used to encode a given frame, TOO.sub.-- MANY.sub.-- VQ.sub.-- REFRESH.sub.-- BITS is a constant, also referred to as a refresh threshold, and SET.sub.-- SCALAR.sub.-- REFRESH is a variable which is set to let other software select between various refresh sub-routines.

The system allows different methods and the use of all, or some combination of these methods, to perform the refreshing based on bit rate and image quality factors.

FIG. 31 depicts the overhead associated with the bit stream structure.

Picture Header Description

With respect to the picture header, in the default configuration of the encoder/decoder (compiled with PSC=4), the picture header is not part of the bit stream. This description of the picture header is only useful for historical purposes and for the cases where the compile switch PSC is set to values 1 or 3.

The picture header precedes the encoded data that corresponds to each frame of image data. The format of the header is a simplified version of the H.261 standard, which can require up to 1000 bits of overhead per frame for the header information. A preferred picture header format only requires 23 bits (when there is no extended picture information) for each video and still image frame and includes the fields shown in FIG. 32 and described below.

In an attempt to save bits, the code works whether or not there is a start code as part of the bit stream.

Referring the FIG. 32, the picture header includes a picture start code (PSC) (16 bits), a picture type (PTYPE) (1 bit) and a temporal reference (TR) (6 bits). With respect to the picture start code, a word of 16 bits with a value of 0000 0000 0000 0111 is a unique bit pattern that indicates the beginning of each encoded image frame. Assuming there have been no transmission bit errors or dropped macro rows the decoder should have finished decoding the previous frame when this bit pattern occurs.

The picture type bit specifies the type of the encoded picture data, either as still or video data as follows:

PTYPE=`0`: moving picture (encoded by the video coder)

PTYPE=`1`: still picture (encoded by the still image coder)

With respect to the temporal reference, a five bit word ranging from 000010 to 111110 indicates the absolute frame number plus 2 (modulo 60) of the current image based on the information from the video front end 104. The bit stream interface adds two to this number to generate 6-bit numbers between 2 and 61 (inclusive) to avoid generating a bit field that looks like the picture start code. The decoder bit stream interface subtracts two from this number. This is field is used to determine if the encoders have missed real-time and how many frames were dropped.

Error Concealment

There are three main decoding operations: decoding still image data, decoding video data, and decoding refresh data. This section discusses how undetected bit errors can be detected, and the resulting error concealment strategies.

Several bit error conditions may occur in both the video and still image decoding process. For an invalid macro row address error, the system ignores the macro row packet and goes to next macro row packet. For a duplicated macro row address error, a bit error is either in the macro row address or the next frame. The system uses the RTR (relative temporal reference) to determine if the duplicated macro row data is for the next frame or the current frame. If it is for the next frame, the system finishes the error concealment for this frame and sends the image to the YUV to RGB converter and begins decoding the next frame. If it is for the current frame, then the system assumes there is a bit error in the address and operates the same as if an invalid macro row address were specified.

For an error of extra bits left over after the macro row, the system overwrites the macro row with the PCI macro row data as if macro row had been dropped and never decoded. The system then continues with the next macro row of encoded bits. For an error of too few bits for decoding a macro row, the system overwrites the macro row with the PCI macro row data as if macro row had been dropped and never decoded. The system then continues with the next macro row of encoded bits. Another possible error is an invalid VQ address (8 zeros). In this case, the system copies the mean from a neighboring 4.times.4 block.

Another error is video data mixed with still data. In this case, the system checks the video data RTR. If it is the same as the still RTR then there is an error condition. If the RTR indicates the next frame, then the system performs concealment on the current frame, sends image to the YUV to RGB converter and continues with decoding on the next frame. Another error is refresh data mixed with still data. This is most likely an undetected bit error in the DT field because the system doe not refresh after still image data. In this case, the macro row should be ignored.

There are also a number of bit errors that are unique to the video image decoder. One type of error is an invalid motion vector (Y,U,V). There are two types of invalid motion vectors: 1. Out of range motion value magnitude (should be between 0 and 224); and 2. Motion vector that requires PCI data that is out of the image plane. In this situation, the system assumes a default motion vector and continues decoding.

Another video image decoder error is refresh data mixed with video data. In this case, the system does the required error concealment and then decodes the refresh data.

With respect to refresh data error conditions, one error is an invalid refresh address. In this case, the system ignores the macro row data and skips to the next macro row packet.

Packetizing of the Encoded Data

It is desirable to transmit the encoded data as soon as possible. The preferred embodiment allows the encoding of images with small packets of data which can be transmitted as soon as they are generated to maximize system speed, independent of synchronization with the other devices.

For example, by macro-row addressing the image data, image areas can be encoded in arbitrary order. That is, no synchronization is required among processors during the encoding of their respective regions because the decoder can interpret the macro rows and decode in arbitrary order. This modular bit stream supports the merging of encoded macro-row packets from an arbitrary number of processors. The macro row packets are not the same size. The packets sent over the modem, which consist of 1 or more macro rows, are not the same size either.

In addition, it is often desirable to use a single transmission channel to transmit various data types (voice, video, data, etc.) simultaneously. The preferred embodiment uses variable length packets of video data which may be interleaved at the data channel with other types of data packets.

Software Interface Between Video Encoder/Decoder and Host

This section describes the software protocol between the host processor (PC) and the video encoder/decoder 103. There are two phases of communication between the PC and the video encoder/decoder 103. The first phase is concerned with downloading and starting the video encoder/decoder microcode. This phase is entered after the video encoder/decoder 103 is brought out of reset. This is referred to as the initialization phase. After the initialization phase is complete, the communication automatically converts to the second phase known as the run-time phase. Communication remains in the run-time phase until the video encoder/decoder 103 reset. After the video encoder/decoder 103 is taken out of reset it is back in initialization phase.

The video encoder/decoder 103 is placed in the initialization phase by resetting the video encoder/decoder 103. This is accomplished by the following procedure:

1. Set bit 0 in the host control register (Offset 0.times.8) to one.

2. Reading the 16 bit exchange register (Offset 0.times.0) to make sure it is empty.

3. Reading the 8 bit master debug register (Offset 0.times.404) to make sure it is empty.

4. Set bit 0 in the host control register (Offset 0.times.8) to zero.

5. Wait (perhaps as much as a few milliseconds) for the video encoder/decoder 103 to set the MD.sub.-- THBF (bit 0) in the debug port status register to one.

6. Send the microcode file 16 bits at a time to the video encoder/decoder through the 16 bit exchange register (Offset 0.times.0).

The data transfer must be coordinated with the FHBE (bit 1) in status and control register (Offset 0.times.C) (i.e., data can only be placed in the 16 bit exchange register when the FHBE flag is one).

After the last 16 bit word of the microcode is transferred to the video encoder/decoder 103, the video encoder/decoder 103 will automatically enter the run-time phase.

The run-time phase is signaled by the video encoder/decoder 103 when the video encoder/decoder 103 sends a status message to the host. All run-time data transmission between the Host and video encoder/decoder 103 is performed either through the 16 bit exchange register or RGB FIFO. All data sent from the host to the video encoder/decoder 103 is sent through the 16 bit exchange register.

Data transmitted from the video encoder/decoder 103 to the host can be broken down into two categories. One category is RGB image data and the other contains everything else. The RGB FIFO is used exclusively to convert YUV data to RGB data and transmit that data in RGB format to the host. Since the RGB FIFO has no interrupt capability on the host side, coordination of the RGB data is accomplished by sending a message through the 16 bit exchange register. The host does not need to acknowledge reception of the RGB data since the FIFO half full flag is connected to one of video encoder/decoder's master processor 102 interrupts.

All data transmission, other than RGB FIFO data, will take place in the context of a packet protocol through the 16 bit exchange register. The packets will contain a 16 bit header word and optionally some amount of addition data. The packet header contains two fields, a packet type (4 bits) and the size in bits (12 bits) of the data for the packet (excluding the header), as shown in FIG. 33.

If the packet only contains the header the data size will be zero. Data will always be sent in increments of 16 bits even if the header indicates otherwise. The number of optional 16 bit words is calculated from the optional data size field of the packet header as:

It should be noted that the only case where the number of bits will not necessarily be a multiple of 16 is in the packets containing encoded bit stream data. In this case, if the header indicates the optional data (bit stream data) is not an increment of 16 bits, the last bits are transferred in the following format. If there are 8 or fewer bits, the bits are left justified in the lower byte of the 15 bit word. If there are more than 8 bits, the first 8 bits are contained in the lower byte of the 16 bit word and the remaining bits are left justified in the upper byte of the 16 bit word. All unused bits in the 16 bit word are set to zero. This provides the host processor with a byte sequential data stream.

FIG. 34 shows encoded data in C32 memory (Big Endian Format), FIG. 35 shows encoded data in PC memory for an original bit stream in the system, and FIG. 36 shows encoded data in PC memory for a video encoder/decoder system.

With respect to timing of packet transfers, from the video encoder/decoder 103's point of view, packet transfers occur in one or two phases depending on the packet. If the packet contains only the header, there is only one phase for the transfer. If the packet contains a header and data, there are two phases to the transfer. In both cases, the header is transferred first under CPU interrupt control (Phase 1). If there is data associated with the packet, the data is transferred under DMA control (Phase 2). Once the DMA is finished, CPU interrupts again control the transfer of the next header (Phase 1).

The video encoder/decoder 103 transfers the data portion of packets under DMA control in one direction at a time. For example, this means that if the video encoder/decoder 103 is currently transferring the data portion of a packet A to the host, the host will not be able to send the data portion of packet B to the video encoder/decoder 103 until the transfer of packet A from the video encoder/decoder 103 is done. This is not the case for transfers of packet headers. The host must be careful not to enter a dead lock situation in which the host is trying to exclusively read or write data from or to the video encoder/decoder 103 while the video encoder/decoder 103 is trying to DMA data in the other direction.

The rules for transferring data are as follows. There are three cases. The first case is when the host is trying to send or receive a packet with no data. In this case there is no conflict. The second case is when the host is trying to send a packet (call it packet A) containing data to the video encoder/decoder 103. In this case, the host sends the header for packet A, then waits to send the data. While the host waits to send the data portion of packet A, it must check to see if the video encoder/decoder 103 is trying to send a packet to the host. If the host finds that the video encoder/decoder 103 is trying to send a packet to the host, the host must attempt to take that packet. The third case is when the host is receiving a packet (call it packet B) from the video encoder/decoder 103. The host first receives the header for packet B, then waits for the data. If the host was previously caught in between sending a header and the data of a packet (call it packet C) going to the video encoder/decoder 103, it must check to see if the video encoder/decoder 103 is ready to receive the data portion of packet C. If so the video encoder/decoder 103 must transfer the data portion of packet C before proceeding with packet B.

This implies that the host interrupt routine will have three states for both receiving and sending packets (six states total). State one is idle, meaning no packet is currently being transferred. State two is when the header has been transferred and the host is waiting for the first transfer of the data to occur. State three is when the transfer of data is occurring. When the interrupt routine is in state two for the receiver or the transmitter, it must be capable switching between the receiver and transmitter portion of the interrupt routine based on transmit or receive ready (To Host Buffer Full and From Host Buffer Empty). Once in state three, the host can exclusively transfer data with only a video encoder/decoder 103 timeout loop.

FIG. 37 is a flow diagram of a host interrupt routine that meets the above criteria. For clarity, it does not contain a video encoder/decoder 103 died time out. Time outs shown in the flow diagram should be set to a value that is reasonable based video encoder/decoder 103 interrupt latency and on the total interrupt overhead of getting into and out of the interrupt routine (this includes system overhead).

As shown in FIG. 37, the video encoder/decoder 103 enters the host interrupt routine at step 112 and proceeds to step 114, where the routine checks for a transmit ready state (To Host Buffer Full). If the system is not in the transmit ready state, the routine proceeds to step 116, where the system checks for a receive ready state (From Host Buffer Empty) and a packet to transfer. If both are not present, the routine proceeds to check for time out at step 118 and returns from the host interrupt routine, at step 120, if time is out. If time is not out at step 118, the routine returns to step 114.

If the system is in the transmit ready state at step 114, the host interrupt routine proceeds to step 122, where the routine polls the receive state. If the receive state is "0" at step 122, then the routine reads a packet header and sets the receive state to "1" at step 124. The routine then proceeds to look for packet data at step 126 by again checking for a transmit ready state (To Host Buffer Full). If the buffer is full, the routine reads the packet data and resets the receive state to "0" at step 130, and then the routine proceeds to step 116. On the other hand, if the buffer is not full, the routine proceeds to step 128, where it checks for time out. If there is no time out, the routine returns to step 126, whereas if there is a time out at step 128 the routine proceeds to step 116. If the receive state is not "0" at step 122, then the routine proceeds directly to step 130, reads data, sets the receive state to "0" and then proceeds to step 116.

Referring again to FIG. 37, if the system is in the receive ready state and there is a packet to transfer at step 116, then the system proceeds to step 131, where the routine polls the transmit state. If the transmit state is "0" at step 131, the routine proceeds to step 132, where the routine writes the packet header and sets the transmit state to "1." The routine again checks whether the From Host Buffer is empty at step 133. If it is not, the routine checks for time out at step 134. If time is out at step 134, the routine returns to step 116, otherwise the routine returns to step 133.

When the From Host Buffer is empty at step 133, the routine proceeds to step 136, where the routine writes the first data and sets the transmit state to "2." The routine then proceeds to step 137, where it checks for more data. If more data is present, the routine proceeds to step 139 to again check whether the From Host Buffer is empty. On the other hand, if no more data is present at step 137, the routine sets the transmit state to "0" at step 138 and then returns to step 116.

If the From Host Buffer is empty at step 139, the routine proceeds to step 141, where it writes the rest of the data and resets the transmit state to "0," and the routine then returns to step 116. On the other hand, if the From Host Buffer is not empty at step 139, the routine checks for time out at step 140 and returns to step 139 if time is not out. If time is out at step 140, the routine returns to step 116.

At step 131, if the transmit state is not "0," then the routine proceeds to step 135, where the routine again polls the transmit state. If the transmit state is "1" at step 135, then the routine proceeds to write the first data and set the transmit state to "2," at step 136. If the transmit state is not "1" at step 135, then the routine proceeds to write the rest of the data and reset the transmit state to "0" at step 141. As noted above, the routine then returns to step 116 from step 141.

A control packet is depicted in FIG. 38. The control packet always contains at least 16 bits of data. The data is considered to be composed of two parts, a control type (8 bits) and required control parameter (8 bits) and optional control parameters (always a multiple of 16 bits). The control type and required parameter always follow the Control Packet header word. Any optional control parameters then follow the control type and required parameter.

A status request packet is depicted in FIG. 39. The status request packet is used to request that the video encoder/decoder 103 send a status packet. The status packet contains the current state of the video encoder/decoder 103.

An encoded bit stream request packet is depicted in FIG. 40. The encoded bits stream request packets request a specified number of bits of encoded bit stream data from the local encoder. The video encoder/decoder 103 will respond by sending back N macro rows of encoded bit stream data (through the packet protocol). N is equal to the minimum number of macro rows that would contain a number of bits equal to or greater than the requested number of bits. Only one request may be outstanding at a given time. The video encoder/decoder 103 will send each macro row as a separate packet. Macro rows are sent in response to a request as they are available. The requested size must be less than 4096 bits.

A decoder bits packages are shown in FIGS. 41 and 42. Encoded data is sent in blocks. There are two types of packets used to send these blocks. The packets about to be described are used to transmit encoded bit stream data to the local decoder. One type of packet is used to send less than 4096 bits of encoded data or to end the transmission of more than 4095 bits of encoded data. The other is used to start or continue the transmission of more than 4095 bits of encoded data. The video encoder/decoder 103 will respond by sending back RGB data of the decoded bit stream after sufficient encoded bit stream bits have been sent to and decoded by the video encoder/decoder 103.

A decoder bits end packet is depicted in FIG. 41 and a decoder bits start/continue packet is depicted in FIG. 42. If less than a multiple of 16 bits is contained in the packet, the last 16 bit word contains the bits left justified in the lower byte first, then left justified in the upper byte. Left over bits in the last 16 bit word are discarded by the decoder.

As the decoder decodes macro rows from the packet it checks to see if there are less than eight bits left in the packet for a given macro row. If there are less than eight and they are zero, the decoder throws out the bits and starts decoding a macro row from the next packet. If the "left over bits" are not zero, the decoder signals a level 1 error.

If a block contains less than 4096 bits it will be transmitted with a single decoder bits end packet. If the block contains more than 4095 bits, it will be sent with multiple packets using the start/continue packet and terminated with the end packet. The start/continue packet must contain a multiple of 32 bits. One way to assure this is to send the bits in a loop. If the bits left to send is less than 4095, send the remaining bits with the start/continue packet and loop.

Referring to FIG. 43, the YUV data for encoder packet is used to send YUV data to the encoder. It is needed for testing the encoder. It would also be useful for encoding YUV data off-line. For the purposes of the image transfer as well as the encoding process, a YUV frame contains 144 lines of 176 pixel/line Y data and 72 lines of 88 pixels/line of U and V data. Because the data size field in the packet header is only 12 bits, it will take multiple packets to transfer a single YUV image. Y data must be sent 2 lines at a time. U&V data are sent together one line at a time (One line of U followed by one line of V). All of the Y plane can be sent first (or last) or the Y and UV data may be interspersed (i.e., two lines of Y, one line of U&V, two lines of Y, one line of U&V, etc.).

Referring to FIG. 43, for the data type:

0=Start New Frame

1=Continue Transferring Frame, data is 2 lines of Y data

2=Continue Transferring Frame, data is one line of U data followed by one line of V data.

3=End frame

A drop current RGB frame packet is depicted in FIG. 44. The drop current RGB frame packet is used to tell the video encoder/decoder 103 to drop the current RGB frame being transmitted to the host. The video encoder/decoder 103 may already put some of the frame into the FIFO and it is the responsibility of the host to extract and throw away FIFO data for any FIFO ready packets received until the next top of frame packet is received.

A status packet is depicted in FIG. 45. The status packet contains the current status of the video encoder/decoder system. This packet is sent after the microcode is downloaded and started. It is also sent in response to the status request packet.

The packet is formatted so that it can be used directly with the super control packet defined below in the control types and parameters section. The microcode revision is divided into two fields: major revision and minor revision. The major revision is located in the upper nibble and the minor revision is located in the lower nibble.

A decoder error packet is depicted in FIG. 46. The decoder error packet tells the host that the decoder detected an error in the bit stream.

The "error level" shown in FIG. 46 is as follows:

1. Decoder bit stream error, decoder will continue to decode the image.

2. Decoder bit stream error, decoder has stopped decoding the input bit stream.

The decoder will search the incoming bit stream for a still image picture start code.

3. Column mismatch of the YUV data sent from the host.

4. Too many Y pixels sent from host for current YUV frame.

5. Too many UV pixels sent from host for current YUV frame.

5. Not enough YUV data sent from host for last YUV frame.

A decoder acknowledge packet is depicted in FIG. 47. The decoder acknowledge packet is only sent when the video encoder/decoder 103 is in store/forward mode. It would be assumed that in this mode the bit stream to be decoded would be coming from disk. Flow control would be necessary to maintain the specified frame rate and to not overrun the video encoder/decoder 103 computational capabilities. The acknowledge packet would signal the host that it could send another packet of encoded bit stream data.

The encoded bits from encoder packets are used to send a macro row of encoded bits from the local encoder to the host. These packets are sent in response to the host sending the encoded bit stream request packet or placing the encoder into record mode.

Referring to FIGS. 48 and 49, there are two types of packets used to send these macro rows. One type of packet is used to send less than 4096 bits of encoded macro row data or to end the transmission of more than 4095 bits of encoded macro row data. The other is used to start or continue the transmission of more than 4095 bits of encoded macro row data. FIG. 48 depicts encoded bits from encoder end packet. FIG. 49 depicts encoded bits from encoder start/continue packet. If fewer than a multiple of 16 bits are contained in the packet, the last 16 bit word contains the bits left justified in the lower byte first, then left justified in the upper. Unused bits in the last 16 bit word are set to zero.

If a macro row contains less than 4096 bits it will be transmitted with a single encoded bits from encoder end packet. If the macro row contains more than 4095 bits, it will be sent with multiple packets using the start/continue packet and terminated with the end packet. The start/continue packets will contain a multiple of 32 bits.

The encoded bits frame stamp packet, as depicted in FIG. 50, is used to send the video frame reference number from the local encoder to the host. This packet is send at the beginning of a new frame in response to the host sending the encoded bit stream request packet. The frame reference is sent modulo 30. The frame type is one if this is a still image or zero if a video image.

A top of RGB image packet, depicted in FIG. 51, is send to indicate that a new frame of video data will be transmitted through the RGB FIFO. The parameter indicates what type of image will be contained in the FIFO. This packet does not indicate that there is any data in the FIFO.

Frame Types:

0.times.01=Self view large

0.times.02=Self view small

0.times.04=Decoded image large

There are two image sizes. The large size is 176 columns.times.144 rows (2 lines sent for every FIFO ready packet). The small size is 44 columns.times.36 rows (6 lines sent for every FIFO ready packet).

The frame number is the frame number retrieved from the decoded bit stream for the decoded image and the frame number from the video acquisition system for the self view image. The number is the actually temporal reference modulo 30.

A FIFO ready packet, as depicted on FIG. 52, is sent when there is a block of RGB data ready in the FIFO. The block size is set by the type of video frame that is being transferred (see RGB top of frame packet).

A YUV acknowledge packet, as depicted in FIG. 53, is sent to tell the host that it is ok to send another YUV frame. Control types and parameters for the control packet (Host to video encoder/decoder 103). Each control type has a default setting. The default settings are in place after the microcode had been downloaded to the video encoder/decoder 103 and until they are changed by a control packets.

A control encoding packet is depicted in FIG. 54. This control is used to change the state of the encoding process (e.g. start, stop or restart). Re-start is used to force a still image. The default setting is encoding stopped and decoder in normal operation.

Referring to FIG. 54, for the encoder state parameter:

0=Stop encoding

1=Start encoding

2=Re-start encoding

3=Start encoding in record mode (bit rate enforced by video encoder/decoder 103)

If bit 3 of the encoder state parameter is set to one, the encoder buffer is cleared before the new state is entered.

A frame rate divisor packet is depicted in FIG. 55. This control is used to set the frame rate of the video capture system. The default is 15 frames per second.

Referring to FIG. 55, for the frame rate divisor parameter:

2=15 frames per second

3=10 frames per second

4=7.5 frames per second

5=6 frames per second

6=5 frames per second

10=3 frames per second

15=2 frames per second; and

30=1 frame per second.

An encoded bit rate packet is depicted in FIG. 56. This control is used to set the encoded bit stream rate for the local encoder. The default is 19.2 kbits per second (parameter value of 63). Referring to FIG. 56, with respect to the bit rate parameter:

If bit 7 of the bit rate parameter is 0

ActualBitRate=(BitRateParameter+1) *300 bits/sec else

ActualBitRate=(BitRateParameter *0.times.7f)+1) *1000 bits/sec

A post spatial filter packet is shown in FIG. 57. This control is used to set the post spatial filter. The filter weight parameter specifies effect of the filter. A parameter value of zero provides no filtering effect. A value 255 places most of the emphasis of the filter on adjacent pixels. The default value for this filter is 77. The spatial filter is implemented as two 3 tap, one dimensional linear filters. The coefficients for these filters are calculated as follows: ##EQU6##

Where p is the value of the parameter divided by 256.

A pre spatial filter packet is shown in FIG. 58. This control is used to set the pre spatial filter. A temporal filter packet is shown in FIG. 59. This control is used to set the temporal filter for the encoder. The filter weight parameter specifies effect of the filter.

A parameter value of zero provides no filtering effect. A value 255 places most of the emphasis of the filter on the previous image. The temporal filter is implemented as:

where p is the value of the parameter divided by 256.

A still image quality packet is shown in FIG. 60. This control is used to set the quality level of the still image coder. A quality parameter of 255 indicates the highest quality still image coder and a quality parameter of zero indicates the lowest quality still image coder. There may not be 256 different quality levels. The nearest implemented quality level is selected if there is no implementation for the specified level. The default is 128 (intermediate quality still image coder).

A video mode packet is depicted in FIG. 61. This control is used to set video input & output modes. The large and small self view may not be specified at the same time. It is possible that the PC's or the video encoder/decoder's bandwidth will not support both a large self view and a large decoded view at the same time. Large views are 176.times.144 and small views are 4.times.36. The default setting is no views enabled. The reserved bits should be set to zero. Referring to FIG. 61, for the video source:

0=Video source is the host interface through YUV packets; and

1=Video source is the video front end.

A video pan absolute packet is shown in FIG. 62. This control is used to set electronic pan to an absolute value. Because the video encoder/decoder system is not utilizing the complete video input frame, one can pan electronically (select the part of the video image to capture). Planning is specified in 1/2 pixel increments. The pan parameters are 8 bit signed numbers. The Y axis resolution is 1 pixel. The default pan is (0,0) which centers the captured image in the middle of the input video image. The valid range for the x parameters is about -100 to +127. The valid range for the y parameter is -96 to +96.

A brightness packet is show in FIG. 63. The brightness packet controls the video front end 104 brightness setting. The brightness value is a signed integer with a default value as zero.

A contrast packet is shown in FIG. 64. The contrast packet controls the video front end 104 contrast setting. The contrast value is an unsigned integer with a default setting of 128.

A saturation packet is shown in FIG. 65. The saturation packet controls the video front end 104 saturation setting. The saturation value is an unsigned integer with a default value of 128.

A hue packet is shown in FIG. 66. The hue packet controls the video front end 104 hue setting. The hue value is a signed integer with a default value of zero.

A super control packet is shown in FIG. 67. The super control packet allows all of the above defined control to be set all at once. See above for the various parameter definitions.

A control decoding packet is shown in FIG. 68. This control is used to change the state of the decoding process (e.g. look for still image or normal decoding). The default setting for the decoder is normal decoding. For the decoder state parameter:

0=Decoder not decoding

1=Decoder normal operation (decoding, decoder does not acknowledge encoded bit packets)

2=Decoder in playback mode (decoder acknowledges encoded bit packets); and

3=Decoder in bit stream pass through mode (decoder gets bits from local encoder).

If bit 3 of the decoder state parameters is set to one, the decoder buffer is cleared before the new state is entered.

The set motion tracking control is used to set the motion tracking state of the encoder. This parameter is used to trade frame rate for better quality video frames. A value of zero codes high quality frames at a slower rate with longer delay. A value of 255 will track the motion best with the least delay, but will suffer poorer quality images when there is a lot of motion. The default setting is 255. A motion tracking packet is shown in FIG. 69.

The request control setting packet is used to request the value of the specified control setting. The video encoder/decoder 103 will respond by send back a packet containing the requested value. The packet will be formatted so that it could be used directly to set control value. A request control setting packet is shown in FIG. 70.

An example of a request control setting packet is shown in FIG. 71. If the PC sent the request control setting packet of FIG. 71, the video encoder/decoder 103 would respond by sending back a frame rate divisor packet formatted, as shown in FIG. 72.

A request special status information packet is shown in FIG. 73. The request special status setting packet is used to request the value of the specified status setting. The video encoder/decoder 103 will respond by send back a packet containing the requested value. This will be used mainly for debugging.

Request for the following information types will result in the video encoder/decoder 103 sending back a packet as shown in FIG. 74, which depicts buffer fullness (type 0.times.81).

A request YUV frame (type 0.times.82) causes the video encoder/decoder 103 to send to YUV frames of data until the request is made a second time (i.e., the request is a toggle). The video encoder/decoder 103 will send back YUV frames through the packet protocol. There are four types of packets that will be sent. A packet indicating the top of frame, a packet containing two lines of Y data, a packet containing one line of U data followed by one line of V data and a packet indicating the end of the frame. A YUV top of frame is depicted in FIG. 75 and a Y data frame is depicted in FIG. 76. A UV data frame is depicted in FIG. 77 and a YUV end of frame is depicted in FIG. 78.

Means Squared Error (MSE) Hardware

As previously noted, the preferred architecture can calculate multiple pixel distortion values simultaneously and in a pipelined fashion so that entire areas of image may be calculated in very few clock cycles. Two accelerator algorithms may be used, the Mean Squared Error (MSE) and the Mean Absolute Error ("MAE"). In a preferred embodiment, the algorithm is optimized around the MSE calculations because the MSE results in the lowest PSNR. The amount of quantization or other noise is expressed as the ratio of peak-to-peak signal to RMSE expressed in decibels (PSNR).

Computing the MSE and MAE in digital signal processor (DSP) software takes about the same computer time. In a TMS320C31 digital signal processor manufactured by Texas Instruments, also referred to as a C31, the MSE takes 2 clock cycles and MAE takes 3 cycles. A TMS320C51 digital signal processor running at twice the clock speed can calculate the MSE and MAE in 5 clocks. The MSE accelerator requires multipliers whereas the MAE can be implemented with only adders, rendering the hardware implementation of the MAE easier.

The accelerator connects to the slave encoder memory bus and receives control from the slave DSP as shown in FIG. 79. Preferably, the DSP fetches 32 bit words, 4 pixels, from memory and passes it to the accelerator. There are four accelerator modes. The first mode, MSE/MAE calculations, is the most used mode. This mode may be with or without motion. The second mode, scene change MSE/MAE calculation, is done once per field. This mode computes MSE/MAE on every 8.times.8 block and stores result in internal DSP RAM, compares the total error of a new field with the previous field's total error, and then software determines if still frame encoding is necessary. The third mode, standard deviation calculations, calculates the standard deviation for each block to be encoded to measure block activity for setting the threshold level. The fourth mode is a mean calculation. This is rarely computed, only when the algorithm is in the lowest part of hierarchy.

Referring to FIG. 79, a memory read takes one DSP clock, and therefore transfers four pixels in one clock. An MSE/MAE accelerator 142 requires four NCI (newly coded image) pixels from a NCI memory 144 and four PCI (previously coded image) pixels from a PCI memory 146 for processing by a DSP 148. In a preferred embodiment, the DSP 148 is a Texas Instruments TMS320C31 floating point DSP. A fixed point DSP or other digital signal processor may also be used. The DSP 148 reads the result from the accelerator 142 along the data bus 150, which takes one clock. For a 4.times.4 block without motion, it thus takes nine clocks plus any hardware pipeline delays, four clocks for NCI data, plus four clocks for PCI data, plus one clock to read the result, 4+4+1=9. FIG. 79 also includes a new image memory 152.

If a motion search is necessary, then a second set of four PCI pixels must be read from memory. The accelerator stores the first set of PCI data and uses part of the second PCI data. The DSP instructs the accelerator how to process (MUX) the appropriate pixels. For a 4.times.4 block with motion it takes 13 clocks plus pipeline delays, which is four clocks for NCI data, four clocks for PCI data, four clocks for the second set of PCI data, and one clock for reading the result, 4+4+4+1=13.

The 8.times.8 blocks are calculated in the same way. Without motion takes 33 clocks plus pipeline delay, and with motion it takes 49 clocks plus pipeline delay.

For the software to compute an MSE, first it reads a 16.times.16 block of NCI and PCI data into internal memory. Then it takes 2 clocks per pixel for either the MSE or MAE calculation, or a total of 128 clocks for an 8.times.8 block, or 32 clocks for a 4.times.4 block. For comparison purposes, only the actual DSP compute time of 128 or 32 clocks are compared. The hardware is not burdened with the overhead associated with transferring the 16.times.16 blocks, therefore the actual hardware speed up improvement is greater than the value calculated.

Other overhead operations not included in the calculations are: instruction cycles to enter a subroutine, instructions to exit a routine, time to communicate with the hardware, etc. The overhead associated with these operations represents only a small percentage of the total and they tend to cancel each other when comparing hardware to software methods, so they are not included in the calculations.

FIG. 80 is a table that represents the formulas for calculating speed improvements. The expression represents a ratio between total time taken by software divided by the time for implementing the calculations in hardware. "Pd" represents the hardware pipeline delay. Assuming a pipeline delay of 3 clocks, speed improvement is found. With respect to the worst case scenario, a 4.times.4 condition, assuming that motion is present 3 out of 4 times, then the average speed improvement is (32/12*1+32/16*3)4=2.167 times over the software only implementation. For the 8.times.8 case, assuming motion 3 out of 4 times, then the average improvement is (128/36*1+128/52*3)/4=2.74 times over the software only implementation.

Overall, assuming the hierarchy stays in the 8.times.8 mode 3 out of 4 times, then the total speed improvement would be (32/12*1+32/16*3)14*1+(128/36*1+128/52*3)14*3)14=2.593 times over the software only implementation.

FIG. 81 shows the speed improvement for various pipeline delay lengths. Assuming a motion search is required 3:1 and that the 8.times.8 block is required 3:1 compared to 4.times.4 in the overall section.

With respect to programmable logic devices (PLDs), a preferred embodiment employs, for example, Altera 8000 Series, Actel ACT 2 FPGAs, or Xilinx XC4000 Series PLDs.

FIG. 82 depicts a mean absolute (MAE) accelerator implementation in accordance with the equation shown in the Figure. As shown at 162, the input is 4 newly coded image pixels (NCI), which is 32 bits, and, as shown at 164, 4 previously coded image pixels (PCI). As shown at 166, if a motion search is necessary, the system further requires an additional 4 PCI pixels. As seen at 168, the PCI pixels are multiplexed through an 8 to 4 bit multiplexer (MUX), which is controlled by a DSP (not shown). As shown at 170, a group of adders or summers, adds the newly encoded pixels and the previously encoded pixels and generates 9 bit output words. As seen at 172, the absolute value of these words, generated by removing a sign bit from a 9 bit word resulting in an 8 bit word, is then input into a summer 174, the output of which is a 10 bit word input into a summer 176. The summer 176 then accumulates the appropriate number of bits depending on the operation mode.

FIG. 83 depicts a mean absolute (MSE) accelerator implementation. The configuration of this implementation is similar to that shown in FIG. 82, and includes a group of multipliers 202.

FIG. 84 illustrates an mean absolute error (MAE) implementation for calculating the MAE of up to four pixels at a time with pixel interpolation for sub-pixel resolution corresponding to the equation at the top of FIG. 84. The implementation includes a 32 bit input. As seen at 202, four non-interpolated pixels are transmitted via a pixel pipe to a series of summers or adders 204. At 206, four previously encoded pixels are input into a 8 to 5 multiplexer (MUX) 208. The output of the MUX 208 is horizontally interpolated with a series of summers or adders 210 and the output 9 bit words are manipulated as shown at 212 by the DSP (not shown). The resulting output is transmitted to a 4 pixel pipe 214 and is vertically interpolated with a series of summers or adders, as seen at 216. As seen at 217, the absolute value of the output of the adders 204 is input to adders 218, the output of which is provided to adder 220. The adder 220 accumulates the appropriate number of bits depending on the mode of operation.

FIG. 85 illustrates a mean square error (MSE) implementation for calculating the MAE of up to four pixels at a time with pixel interpolation for sub-pixel resolution corresponding to the equation at the top of FIG. 85. The implementation includes a 32 bit input. As seen at 222, four non-interpolated pixels are transmitted via a pixel pipe to a series of summers or adders 224. At 226, four previously encoded pixels are input into a 8 to 5 multiplexer (MUX) 228. The output of the MUX 228 is horizontally interpolated with a series of summers or adders 230 and the output 9 bit words are manipulated as shown at 232 under the control of the DSP (not shown). The resulting output is transmitted to a 4 pixel pipe 234 and is vertically interpolated with a series of summers or adders, as seen at 236. As seen at 237, the squared value of the output of the adders 224 is input to adders 238, the output of which is provided to adder 240. The adder 240 accumulates the appropriate number of bits depending on the mode of operation.

Video Teleconferencing

Video teleconferencing allows people to share voice, data, and video simultaneously. The video teleconferencing product is composed of three major functions; video compression, audio compression and high speed modem. The video compression function uses the color space conversion to transform the video from the native YUV color space to the host RGB display format.

A color space is a mathematical representation of a set of colors such as RGB and YUV. The red, green and blue (RGB) color space is widely used throughout computer graphics and imaging. The RGB signals are generated from cameras and are used to drive the guns of a picture tube. The YUV color space is the basic color space used by the NTSC (National Television Standards Committee) composite color video standard. The video intensity ("luminance") is represented as Y information while the color information ("chrominance") is represented by two orthogonal vectors, U and V.

Compression systems typically work with the YUV system because the data is compressed from three wide bandwidth (RGB) signals down to one wide bandwidth (Y) and two narrow bandwidth signals (UV). Using the YUV color space allows the compression algorithm to compress the UV data further, because the human eye is more sensitive to luminance changes and can tolerate greater error in the chrominance information.

The transformation from YUV to RGB is merely a linear remapping of the original signal in the YUV coordinate system to the RGB coordinate system. The following set of linear equations can be used to transform YUV data to the RGB coordinate system:

R=Y+1.366*V-0.002*U

G=Y-0.700*V-0.334*U

B=Y-0.006*V+1.732*U

This type of transformation requires hardware intensive multipliers. Approximate coefficients can be substituted which simplifies the hardware design. Two-bit coefficients can be implemented in hardware with adders, subtractor and bit-shifts (no multipliers). The two-bit coefficient method requires no multiplier arrays. A simplified set of equations follow:

R=Y+1.500*V

G=Y-0.750*V-0.375*U

B=Y+1.750*U

Coefficient errors due to this approximation range from 1.2% to 9%. The 9% error occurs in the U coefficient of the G equation. To implement the two-bit coefficients in hardware, the equations can be viewed where the multiplication is a simple bit shift operation. Shift operations do not involve logic. It is important to remember that the hardware must hard limit the RGB data range. Therefore, an overflow/underflow detector must be built into the hardware that implements this conversion.

The YUV to RGB matrix equations use two-bit coefficients which can be implemented with bit-shifts and adds. High speed adder structures, carry save and carry select, are used to decrease propagation delay as compared to a standard ripple carry architecture. The two types of high speed adders are described below.

Carry save adders reduce three input addends down to a sum and carry for each bit.

Let A=An-1 . . . A1A0 and B=Bn-1 . . . B1B0 and D=Dn-1 . . . D1D0 be the addend inputs to an n-bit carry save adder. Let Ci be the carry output of the ith bit position and Si be the sum output of the ith position. Ci and Si are defined as shown in FIG. 86. A sum and carry term is generated with every bit. To complete the result, the sum and carry terms must be added in another stage such as a ripple adder, carry select adder or any other full adder structure. Also note that the carry bus must be left shifted before completing the result. For instance, when the LSB bits are added, sum S0 and carry C0 are produced. When completing the result, carry C0 is added to sum S1 in the next stage, thus acting like a left bus shift.

FIG. 87 is a block diagram of a color space converter that converts a YUV signal into RGB format. The R component is formed by coupling a 1V, a 0.5V and a 1Y signal line to the inputs of a carry save adder 242, as shown in FIG. 87. The carry and sum outputs from the carry save adder 242 are then coupled to the inputs of a full adder 243. The sum output of the full adder 243 is then coupled to an overflow/underflow detector 244, which hard limits the R data range.

The B component of the RGB formatted signal is formed by coupling a 2 U, a -0.25 U and a 1Y signal line to the inputs of a carry save adder 245. The carry and sum outputs of the carry save adder 245 are coupled to the inputs of a full adder 246, whose sum output is coupled to an overflow-underflow detector 247. The overflow-underflow detector 247 hard limits the B data range.

The G component of the RGB formatted signal is formed by coupling a -0.25 U, a -0.125 U and a -0.5V signal line to the inputs of a carry save adder 248. The carry and sum outputs of the carry save adder 248 are coupled, along with a -0.25V signal line, to the inputs of a second carry save adder 249. The carry and sum outputs of the carry save adder 249 are coupled, along with a 1Y signal line, to the inputs of a third carry save adder 250. The carry and sum outputs of the third carry save adder 250 are coupled to the inputs of a full adder 251, as shown in FIG. 87. The sum output of the full adder 251 is coupled to an overflow/underflow detector 252, which hard limits the data range of the G component.

In a preferred embodiment, the Y signal has eight data bits and the U and V signals have seven data bits and a trailing zero bit. U and V signals may therefore be processed by subtracting 128. In addition, the Y, U and V signals are preferably sign extended by two bits, which may be used to determine overflow or overflow state. For example, 00=OK, 01=overflow, 11=underflow and 10=indeterminant. Each of the adders shown in FIG. 87 is preferably, therefore, a 10 bit adder.

FIGS. 88, 89 and 90 depict a carry select adder configuration related bit tables for converting the YUV signal to RGB format. FIG. 88 includes a carry select adder 253 coupled to a full adder 254 that generate the R component of the RGB signal. FIG. 89 includes a carry select adder 255 coupled to a full adder 256 that generate the B component of the RGB signal. FIG. 90 includes carry select adders 257, 258, 259 and a full adder 260 that generate the G component of the RGB signal.

FIG. 91 is a block diagram timing model for an YUV to RGB color space converter. A FIFO 262 is coupled by a latch 264 to a state machine 266, such as the Xilinx XC3080-7PC84 field programmable gate array. The state machine 266 includes an RGB converter 272 that converts a YUV signal into a RGB formatted signal. The converter 272 is preferably a ten bit carry select adder having three levels of logic (as shown in FIGS. 87-90). The RGB formatted data is coupled from an output of the state machine 266 into a buffer 270. In accordance with the preferred embodiment, the state machine 266 is a memoryless state machine that simultaneously computes the YUV-to-RGB conversion while controlling the flow of data to and from it.

The carry select adder, as implemented in the Xilinx FPGA, adds two bits together and generates either a carry or a sum. Carry select adders are very fast because the propagation delays and logic levels can be kept very low. For instance, a ripple carry adder of 10 bits requires 10 level of logic to compute a result. A 10 bit carry select adder can be realized in only three levels of logic.

Sums and carries are generated, and in some cases, a carry is generated without completing the carry from lower order bits. For instance, carry four (C4) generates two carry terms, each based on the outcome of carry two (C2). Equation C.sub.-- 40 is based on C2 being zero, and C.sub.-- 41 is based on C2 being one. Once C2 is determined, then the appropriate signal, C.sub.-- 40 or C.sub.-- 41, can be selected in later logic levels.

Generating multiple carries allows for parallel processing, because the carries can be generated without waiting for earlier results. This idea greatly improves the speed of an adder as compared to ripple carry architecture.

Similarly, higher order bits will generate multiple carry types which will be completed in following levels of logic. As the lower order sums and carries are generated, the upper order results can be determined. The entire adder tree is completed in only three levels of logic. Appendix 6 contains code for implementing the carry select adder and the carry save adder.

FIG. 92 is a state diagram relating to the conversion of the YUV signal to RGB format in accordance with the timing model shown in FIG. 91.

Since different platforms have different color space requirements, the output color space converter shown in FIG. 91 is in-circuit configurable. The application software queries the platform to determine what color space it accepts and then reconfigures the color space converter appropriately. In the preferred embodiment, YUV-to-RGB 565 color space conversion is performed. Nonetheless, the FPGA shown in FIG. 91 may perform RGB color space conversions to different bit resolutions or even to other color spaces.

Half-Pixel Motion Estimation Memory Saving Technique

In video compression algorithms, motion estimation is commonly performed between a current image and a previous image (commonly called the reference image) using an integer pixel grid for both image planes. More advanced techniques use a grid that has been upsampled by a factor of two in both the horizontal and vertical dimensions for the reference image to produce a more accurate motion estimation. This technique is referred to as half-pixel motion estimation. The motion estimation is typically performed on 8.times.8 image blocks, or on 16.times.16 image blocks (macro blocks), but various image block sized may be used.

Assume that 16.times.16 image blocks (macro blocks), as shown in FIG. 93, are used with a search range of approximately .+-.16 pixels in the horizontal and vertical directions and that the image sizes are QCIF (176 pixels horizontally by 144 pixels vertically) although other image sizes could be used. Further assume that each pixel is represented as one byte of data, and that motion searches are limited to the actual picture area. A 16 pixel wide vertical slice is referred to as a macro column and a 16 pixel wide horizontal slice is referred to as a macro row. An interpolated macro row of reference image data is 176.times.2 bytes wide and 16.times.2 bytes high. FIG. 94 shows a macro block interpolated by a factor two horizontally and vertically.

When designing video compression algorithms, there is a trade-off between computation power and memory usage. On the one hand, if one has more computational power and memory bandwidth, then one can save on memory space by performing the interpolation on a 3.times.3 macroblock portion of the reference image for each macro block of the current image to undergo motion estimation. On the other hand, if one can afford to use more memory to save computational power then one can interpolate the full reference image before any motion estimation is performed and therefore only interpolate each portion of the image once. This provides computational savings since one is only interpolating the image once instead of multiple times. This computational savings comes at the cost reference image memory size which must be four times the original reference image memory size (176.times.144.times.2.times.2=101,376 bytes). In a preferred embodiment, there are two methods of reducing the computation and the memory requirements simultaneously.

The first method involves using a memory space equivalent to three of the macro rows interpolated up by a factor of two in both the horizontal and the vertical directions in place of the whole reference image plane interpolated up in size. That is, the memory size is 3.times.176.times.16.times.2.times.2=33,792 bytes. This reduces the interpolated reference image memory requirement by approximately 67%. This interpolated reference image memory space is best thought of as being divided up into thirds with the middle third corresponding to roughly the same macro row (but interpolated up in size) position as the macroblock being motion estimated for the current image. The motion estimation using this memory arrangement can be implemented as follows:

1.) Copy the first three (top) interpolated macro rows of the reference image data into the previously described memory space (note: this is 3.times.176.times.16.times.2.times.2 bytes of video data) and calculate the motion estimation for the first two current image macro rows. FIG. 95 depicts the memory space after this step during the first iteration of the first method.

2.) Copy the second third of the interpolated macro row of the reference image data into the memory space where the first third of the interpolated macro row of the reference image data currently resides. (In the first iteration of the algorithm, interpolated macro row 2 is copied with memory holding interpolated macro row 1).

3.) Copy the last third interpolated macro row of the reference image data into the memory space where the second third of the interpolated macro row of the reference image data currently resides. (In first iteration of the algorithm, interpolated macro row 3 is copied into the old interpolated macro row 2 memory space).

4.) Copy the next interpolated macro row of the reference image data into the memory space where the last third of the interpolated macro row of the reference image data currently resides. (In first iteration of the algorithm, interpolated macro row 4 is copied into the old interpolated macro row 3 memory space). FIG. 96 depicts the memory space after this step after the first iteration of the first method.

5.) Calculate the motion estimation for the next current image macro row assuming that its reference position is centered in the middle third of the interpolated reference image memory space.

6.) Return to step 2.

This first method requires that additional time and memory bandwidth be spent performing the copies, but saves memory and computational power.

The second method, like the first method, involves using a memory space equivalent to three of the macro rows interpolated up by a factor of two in both the horizontal and the vertical directions. Unlike the first method, the second method uses modulo arithmetic and pointers to memory to replace the block copies of the first method. The second method is better than the first method from a memory bandwidth point of view, and offers the memory and computational power savings of the first method.

Three macro rows of interpolated reference image data corresponds to 96 horizontal rows of pixels. If, as in method 1, the memory space of the interpolated reference image is divided up into thirds, then the middle third of the memory space begins at the 33rd row of horizontal image data. A pointer is used to locate the middle third of the memory space. Assuming that a number system starts at 0, then the pointer will indicate 32. The motion estimation of the second method using this memory arrangement can be implemented as follows:

1.) Calculate and copy the first three (top) interpolated macro rows of the reference image data into the previously described memory space (3.times.176.times.16.times.2.times.2 bytes of video data) and calculate the motion estimation for the first two current image macro rows (pointer was initialized to 32).

2.) Set the pointer to 64 and copy the next interpolated macro row of reference image data into memory rows 0-31.

3.) Calculate the motion estimation for the next current image macro row assuming that its reference position is centered in the middle third of the interpolated reference image memory space.

4.) Set the pointer to 0 and copy the next interpolated macro row of reference image data into memory rows 32-63.

5.) Calculate the motion estimation for the next current image macro row assuming that its reference position is centered in the middle third of the interpolated reference image memory space.

6.) Set the pointer to 32 and copy the next interpolated macro row of reference image data into memory rows 63-95.

7.) Calculate the motion estimation for the next current image macro row assuming that its reference position is centered in the middle third of the interpolated reference image memory space.

8.) Return to step 2.

FIG. 97 depicts memory space addressing for three successive iterations of a second motion estimation memory saving technique. The numbers on the left indicate the horizontal memory space addresses. The "X" indicates the center interpolated macro row and pointer location. FIG. 97 gives a conceptual view of how using a pointer and modulo arithmetic makes the memory space appear to "slide" down an image.

The above two methods can be extended to cover extended motion vector data (.about..+-.32 pixel searches instead of just the .about..+-.16 pixel searches described previously) by using a memory space covering five interpolated macro rows of reference image data. This larger memory space requirement will reduce the interpolated reference image memory requirement by approximately 45% instead of the 67% savings that using only three interpolated macro rows of reference image data gives. Of course the second method uses modulo 160 arithmetic.

Panning and Zooming

Traditional means of implementing a pan of a video scene is accomplished by moving the camera and lens with motors. The hardware in a preferred embodiment uses an electronic means to accomplish the same effect.

The image scanned by the camera is larger than the image required for processing. An FPGA crops the camera image to remove any unnecessary data. The remaining desired picture area is sent to the processing device for encoding. The position of the desired image can be selected and thus "moved" about the scanned camera image, and therefore has the effect of "panning the camera." The software tells the input acquisition system to change the horizontal and vertical offsets that it uses to acquire the image into memory. The application software provides the users with a wire frame diagram showing the total frame with a smaller wire frame inside of it which the user positions to perform the panning operation.

Traditionally, a zoom in a video scene is accomplished by moving the camera and lens with motors. In a preferred embodiment, electronics are used to accomplish the same effect.

For the preferred embodiment, the image scanned by the camera is larger than the image required for processing. Accordingly, the video encoder/decoder 103 may upsample or subsample the acquired data to provide zoom in/zoom out effects for a video conferencing environment. For example, every pixel in a given image area may be used for the most zoomed in view. A zoom out effect may then be achieved by decimating or subsampling the image capture memory containing the pixel data. These sampling techniques may be implemented in software or hardware. A hardware implementation is to use sample rate converters (interpolating and decimating filters) in the master digital signal processor or in an external IC or ASIC.

Sending High Quality Still Images

A video conferencing system employing the invention may also be used to send high quality still images for viewing and recording to remote sites. The creation of this still can be initiated through the application software by either the viewing or the sending party. The application then captures the image, compresses it, and transmits it to the viewer over the video channel and data channel for maximum speed. In applications using more than one processing device, the still image can be compressed by one of the processing devices while the main video conferencing application continues to run.

In a preferred embodiment, the still is encoded in one of two methods, depending upon user preference--1.) a HVQC still is sent, or ii.) a differential pulse code modulation (dpcm) technique using a Lloyd-max quantizer (statistical quantizer) with Huffman encoding. Other techniques that could be used include JPEG, wavelets, etc.

In applications using more than one processing device, the MD is used to actually do the stills encoding as a background task and then sends the still data with a special header to tell the receiving codec what the data is. The receiver's decoder would then decode the still on its end.

Stills and video conferencing frames are presented to the user in separate application windows. The stills can then be stored to files on the users system which can then be called up later using a software or hardware decoder.

In accordance with the present invention, a video sequence may be transmitted over an ordinary modem data connection, either with another party or parties, or with an on-line service. Upon connection, the modems exchange information to decide whether there is to be a two-way (or more) video conference, a single ended video conference, or no video conference. The modem may then tell the application software to automatically start up the video conference when appropriate. In addition, the system described herein provides the users the capability of starting an application at any point during their conversation to launch a data and/or video conference.

In addition, the video encoder/decoder 103 described herein may be used with a telephone, an audio compression engine and a modem to produce a video answering machine. For this embodiment, a DRAM may be used to store several minutes of data (multiple audio/video messages). The answering machine may play an audio/video message to the caller and may then record a like image. The caller may choose to send either a video sequence or a still image, such as by pushing appropriate buttons on the telephone. The caller may be given the option of reviewing the video sequence or still image by preventing the encoding and transmission of the video until the caller presses an appropriate button to signal its approval.

It is to be understood, however, that additional alternative forms of the various components of the described embodiments are covered by the full scope of equivalents of the claimed invention. Those skilled in the art will recognize that the preferred embodiment described in the specification may be altered and modified without departing from the true spirit and scope of the invention as defined in the following claims, which particularly point out and distinctly claim the subjects regarded as the invention. ##SPC1##