Videos are usually compressed to reduce the bit rate while transmitting the video over communication networks.  For any communication network, errors are introduced inevitably into the compressed video bit stream due to channel noise.  Even a single bit error can lead to objectionable visual distortion at the receiver.  In some cases, the decoding can fail completely due to variable length coding (VLD).  In addition, motion compensated prediction causes error propagation in subsequent frames after any corruption in the compressed video. 
Therefore, it is very important to have an error resilient encoding and error concealment during decoding for compressed video transmitted over error-prone channels.  Error resilient encoding provides redundancy, and error concealment ‘hides’ errors.  The concealing essentially estimates a replacement value for lost information be it pixel intensities or motion vectors.  In the art, the estimated value is said to “conceal’ the error. 
Many methods are known for error resilient encoding and error concealment during decoding.  Those methods can be divided into three main approaches: spatial, temporal, and frequency.  There is also a hybrid method of these three main categories, see Cen et al., “ Decision Trees for Error Concealment in Video Decoding, ” IEEE Transactions on Multimedia, Vol.  5, No.  1, March 2003, Lee et al., “ Multiframe Error Concealment for MPEG-Coded Video Delivery Over Error-Prone Networks, ” IEEE Transactions on Image Processing, Vol.  11, No.  11, November 2002, Zhang et al., “ A Cell-Loss Concealment Technique for MPEG-2 Coded Video, ” IEEE Transactions on Circuits and Systems for Video Technology, Vol.  10, No.  4, June 2000. 
For spatial error concealment, intra-frame interpolation is the most common method.  Intra-frame interpolation uses available neighboring macroblocks (MB) to replace a missing or corrupt macroblock.  If the neighboring blocks on all four sides of the missing macroblock are available, then missing pixels can be concealed with bilinear interpolation from the four nearest pixels that are not corrupted. 
Other strategies exist.  For example, directional interpolation seeks to preserve edges.  Those methods either have blurred effect on the reconstructed image or high computational complexity.  They are not suitable for real-time applications. 
In temporal error concealment, motion compensation prediction is the most common approach.  Due to a higher correlation in the temporal domain than the spatial domain, most concealment methods focus on motion vector recovery so that a lost macroblock can be motion-compensated from a reference frame.  The lost motion vectors can be replaced by redundant motion vectors, zero vectors, vectors from spatially or temporally adjacent macroblocks, or the average or median of motion vectors of adjacent macroblocks. 
However, all of above approaches suffer from poor concealment quality after false recovery happens for missing motion vector.  Even when a corrupted macroblock is surrounded by correctly decoded macroblocks, the decoder cannot determine which neighboring motion vector would provide a good concealment. 
In frequency concealment, discrete cosine transform (DCT) coefficients of missing macroblocks are estimated using the corresponding DCT coefficients of neighboring blocks.  Those methods usually attempt to estimate low frequency coefficients.  Therefore, those methods have the same effects as the spatial concealment methods. 
U.S. Pat.  No.  6,512,795 B1, “Error concealment for video services, ” issued to Zhang et al.  on Jan. 28, 2003, describes a motion vector estimation method for error concealment.  That method exploits temporal correlation in the estimation process.  A full search is performed within a previous frame for a best match to the available lines of decoded pixels from the current frame.  That method has high computational complexity and is not feasible for real-time video transmission, especially in a high error rate situation. 
U.S. Pat.  No.  6,128,339, “Apparatus and method for masking video data errors, ” issued to Park, on Oct. 3, 2000, describes a method for error detecting and concealing.  That system includes two buffers for storing video data.  The first buffer stores the reference frame and the second buffer stores the current frame.  When an error is detected at a location, the method copies the video data stored at the location in the first frame buffer to the same location in the second frame buffer to conceal the errors.  Then, the error detector updates the first frame buffer with the second frame, reads the video data into the second frame buffer and repeats the error detection process.  That method introduces mismatching errors especially for a video with excessive motion. 
U.S. Pat.  No.  5,912,707, “Method and apparatus for compensating errors in a transmitted video signal, ” issued to Kim, on Jun. 15, 1999, and U.S. Pat.  No.  5,737,022, “Motion picture error concealment using simplified motion compensation, ” issued to Yamaguchi et al.,  on Apr. 7, 1998, also describe error detecting and concealing.  Similar to the above patent, they reconstruct the current frame from motion vectors for the current frame and a reconstructed preceding frame.  That method includes the steps of detecting a lost block containing errors, providing pixel values of neighboring blocks of the lost block in the reconstructed current frame and motion vectors, generating a compensation block based on the motion vectors for the neighboring blocks, and providing the compensation block as a substitution block for concealing the lost block. 
Most of the above methods focus on utilizing motion vectors and motion compensation methods for inter-frame error concealment.  As stated before, those methods suffer from either poor concealment quality when false recovery happens for a missing motion vector, or slow concealment because of full search computation. 
Some of the prior methods describe intra-frame error concealment, but they either introduce large estimation errors to the reconstructed image or have high computational complexity. 
FIG.  1 shows a typical prior art error concealment process for a lost 16×16 macroblock (MB) 100 of an intra-frame of a compressed video.  The 16×16 pixels are conventionally arranged in a rectangular array.  In FIG.  1 there are concealed pixels 101, candidate pixels 102, a current pixel 103, and lost pixels 104.  The concealed pixels have previously been recovered, and the lost pixels are yet to be concealed.  The current pixel to be concealed is recovered from the nearest candidate pixels along outer boundaries of adjacent macroblocks.  In the example, the nearest candidate pixels in the adjacent macroblock are directly above, below, to the left and to the right of the current pixel, but in the adjacent blocks.  The intensity of the candidate pixels can be combined in some weighted manner to determine the value of the current pixel to be concealed. 
The concealment is performed in raster scan order from upper left corner of the MB to the lower right corner of the MB.  Pixels near the top of the MB are concealed earlier than those near the bottom.  However, concealment in this way gives large estimation errors because the candidate pixels 102 are generally far away from the pixels to be concealed, i.e., along outer boundaries of neighboring macroblocks. 
Given the above prior art, there is a need to provide new encoding and decoding methods compressed videos transmitted over error prone networks.