Abstract:
A method of compressing and decompressing an image, and an associated system. In an encoder, the image is partitioned among boundary pixels and interior blocks. The boundaries of the interior blocks are interpolated, preferably using dynamic programming, to produce approximation sets that are subtracted from the interior blocks to produce difference sets. The boundary pixels and the difference sets are transmitted to a decoder that interpolates the boundaries to reconstruct the approximation sets, adds the reconstructed approximation sets to the difference sets to reconstruct the interior blocks, and merges the interior blocks with the boundary pixels to reconstruct the image.

Description:
[0001]    This is a continuation-in-part of U.S. Provisional Patent Application No. 60/331,239, filed Nov. 13, 2001 
     
    
     
       FIELD AND BACKGROUND OF THE INVENTION  
         [0002]    The present invention relates to image and video compression and, more particularly, to a method and system of image compression and decompression that uses an interpolation method such as dynamic programming to predict approximations of significant portions of an image, with the approximations being subtracted from those portions of the image to produce difference images and with the approximations being added to the difference images to reconstruct the original image.  
           [0003]    Digital imaging is the process of converting a scene into a finite sized, two dimensional discrete array of so called “pixels” that digitally store the light intensities of the correspondingly located spots in the scene. From practical reasons it is most convenient to deal with rectangular scenes, so that the corresponding digital images are simply matrices whose entries equal the light levels at the pixels of respective row-column coordinates.  
           [0004]    The most commonly used method for still image compression is JPEG (Joint Picture Expert Group) (P. D. Symes,  Video Compression,  McGraw-Hill, 1998), wherein the image is first sub-divided into (usually 8×8) blocks of pixels and each block undergoes a quantized and further truncated Discrete Cosine Transform (DCT). In the corresponding decompression, the inverse de-quantized DCT is performed to recover a good approximation of the original image.  
           [0005]    The most commonly used method for video compression is MPEG (Motion Pictures Expert Group) (P. D. Symes, op. cit.). In MPEG compression, the DCT operates on an error image, which is the difference between the current input frame and a predicted frame. The predicted frame is in turn generated by a technique called “motion compensation,” wherein the translation, or the so called “motion vector”, of each (again, usually 8×8) block in the current frame is predicted by interpolation from other, “known” frames of the video sequence. The “known” frames are frames that are compressed without prediction, for example as in JPEG. In typical MPEG, ⅔ to {fraction (1/10)} of the total video frames may be treated as “known”.  
           [0006]    The main drawbacks of JPEG is its relatively low compression ratios and the noticeability of the 8×8 blocks in the reconstructed images, a phenomenon commonly referred to as “blocking”. One reason for the limited compression ratios is the lack of any interpolation/prediction in JPEG. The blocking is a built-in feature of the method.  
           [0007]    As for MPEG, in addition to built-in blocking, other drawbacks include:  
           [0008]    1) The process delay that is caused by the use of several frames other than the compressed one for the motion compensation prediction, and  
           [0009]    2) The high sensitivity to temporal changes in the video.  
           [0010]    High temporal changes can be induced by abrupt translational motion, but also by non-translational motion such as camera rotation and zooming, as well as by noise. In the presence of such high temporal changes, MPEG channels tend to collapse due to the “domino effect” caused by erroneous motion vectors for too many blocks. In this situation no decent frame can be predicted and the whole process just halts.  
           [0011]    There is thus a widely recognized need for, and it would be highly advantageous to have, a method of compressing and decompressing still and video images which would overcome the disadvantages of presently known methods as described above.  
         SUMMARY OF THE INVENTION  
         [0012]    According to the present invention there is provided a method of compressing a plurality of pixels, including the steps of: (a) partitioning the pixels among interior pixels and boundary pixels, the interior pixels being partitioned among at least one interior set of the interior pixels such that each interior set is adjacent to a respective boundary set of the boundary pixels; and (b) for each interior set: (i) calculating, from only the respective boundary set, a respective approximation set of the each interior set, and (ii) subtracting the respective approximation set from the each interior set to provide a respective difference set.  
           [0013]    According to the present invention there is provided a method of sending an image from an encoder to a decoder, the image including a plurality of pixels, the method including the steps of: (a) partitioning the pixels among interior pixels and boundary pixels, the interior pixels being partitioned among at least one interior set of the interior pixels such that each interior set is adjacent to a respective boundary set of the boundary pixels, by the encoder; (b) for each interior set: (i) calculating, from only the respective boundary set, a respective approximation set of the each interior set, by the encoder, and (ii) subtracting the respective approximation set from the each interior set to provide a respective difference set, by the encoder; and (c) transmitting the boundary pixels and the at least one difference set, by the encoder, to the decoder.  
           [0014]    According to the present invention there is provided a system for compressing, transmitting and reconstructing an image that includes a plurality of pixels, the system including: (a) an encoder including: (i) a partitioner for partitioning the pixels among interior pixels and boundary pixels, the interior pixels being partitioned among at least one interior set of the interior pixels such that each interior set is adjacent to a respective boundary set of the boundary pixels, (ii) an encoder mechanism for, for each interior set, calculating, from only the respective boundary set, a respective approximation set of the each interior set, (iii) a subtracter for, for each interior set, subtracting the respective approximation set from the each interior set to provide a respective difference sets, and (iv) a transmitter for transmitting the boundary pixels and the at least one difference set.  
           [0015]    The present invention is a method for compressing a captured digital image and later decompressing the compressed image for the purpose of displaying the decompressed image, and a system for implementing the invention. The system device that compresses the image is called an “encoder” herein. The system device that decompresses the compressed image is called a “decoder” herein. The process of getting the compressed image from the encoder to the decoder is referred to herein as “transmitting” the compressed image from the encoder to the decoder and “receiving” the compressed image by the decoder. As such, such “transmitting” and “receiving” includes not only processes, such as transmitting a compressed image from a TV camera to a remote receiver, that normally are considered to be instances of “transmitting” and “receiving”, but also processes, such as archiving the compressed image in a database and then retrieving the compressed image for display, that are not normally considered to be instances of “transmitting” and “receiving”.  
           [0016]    The present invention considers an image to be a rectangular array of pixels. The basic idea of the present invention is to partition the array among two kinds of pixels: boundary pixels and interior pixels. Each set of interior pixels is adjacent to a respective set of boundary pixels. Instead of transmitting the whole image, only the boundary pixels are transmitted, along with “difference sets” corresponding to the sets of interior pixels, with each difference set being the difference between a set of interior pixels and corresponding pixels that are calculated from only the corresponding boundary pixels, either by interpolating the corresponding boundary pixels or by extrapolating the corresponding boundary pixels. Calculating the interpolated or extrapolated pixels “only” from the corresponding boundary pixels means that no interior pixels participate in the calculation. The smallest image for which the present invention is defined is the trivial case of one interior pixel adjacent to one boundary pixel, in which case the “calculating” consist of merely copying the boundary pixel. The usual nontrivial case of interpolation is that in which the sets of interior pixels are surrounded by the respective sets of boundary pixels, as illustrated in FIG. 1A, which shows a block of 64 interior pixels, labeled “i”, surrounded by 36 boundary pixels, labeled “b”. Other possibilities include extrapolating boundary pixels that are adjacent to a comer and two sides of a block of interior pixels, as illustrated in FIG. 1B; interpolating boundary pixels that are on two opposite sides of a block of interior pixels, as illustrated in FIG. 1C; and extrapolating boundary pixels that are on one side of a block of interior pixels, as illustrated in FIG. 1D. The sets of interior pixels are called “interior sets” herein. The corresponding sets of boundary pixels are called “boundary sets” herein. The corresponding sets of interpolated or extrapolated pixels are called “approximation sets” herein. The difference between an interior set and the corresponding approximation set is called a “difference set” herein.  
           [0017]    The compression described above is performed by the encoder. The encoder transmits the boundary pixels and the difference sets to the decoder. The decoder reconstructs each approximation set by interpolating or extrapolating the corresponding boundary set just as the encoder interpolated or extrapolated the boundary set to produce the approximation set, combines the corresponding difference set with the reconstructed approximation set to obtain a corresponding reconstructed interior set, and merges the reconstructed interior sets with the boundary pixels to produce a reconstructed image.  
           [0018]    Preferably, the interpolations are effected using dynamic programming.  
           [0019]    Combining corresponding difference sets and reconstructed approximation sets is effected most simply by merely adding each difference set to the corresponding reconstructed approximation set. Preferably, however, corresponding difference sets and reconstructed approximation sets are combined using a Kalman filter.  
           [0020]    Preferably, the encoder compresses the boundary pixels and the difference sets before transmitting them to the decoder. The first processing step at the decoder then is decompression of the received boundary pixels and the received difference sets. The compression and decompression of the boundary pixels and of the difference sets may be lossy or lossless.  
           [0021]    The encoder of the present invention includes a partitioner for partitioning the image into boundary pixels and interior sets, a mechanism for producing the approximation sets, a subtracter for producing the difference sets, and a transmitter for transmitting the boundary pixels and the difference sets to the decoder. The decoder of the present invention includes a receiver for receiving the boundary pixels and the difference sets, a mechanism for reconstructing the approximation sets, a mechanism for combining the difference sets with the reconstructed approximation sets, and a merger for merging the reconstructed interior sets with the boundary pixels to reconstruct the image.  
           [0022]    Preferably, the encoder also includes a compressor for compressing the boundary pixels and the difference sets prior to transmission; and the decoder includes a corresponding decompressor for decompressing the received compressed boundary pixels and the received compressed difference sets.  
           [0023]    The present invention is aimed at circumventing the main drawbacks of both JPEG and MPEG. This is achieved by confining the interpolation/prediction stage to only the frame being compressed. In the present invention the predicted blocks are interpolated from their boundaries, which in turn are treated as “known”.  
           [0024]    Compression ratios are maintained at the level of MPEG, because the compression operates primarily on an error image. The blocking is less prominent than in JPEG and MPEG because each block shares the same “known” boundaries with its adjacent neighbors.  
           [0025]    For commercial video the process delay of the present invention&#39;s compression is typically 8 TV lines, less than 2% of a full frame period.  
           [0026]    As for motion/noise sensitivity the present compression scheme is inherently insensitive to those parameters, because it treats each block of every frame completely separately and independently of the other blocks of the same and other frames. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0027]    The invention is herein described, by way of example only, with reference to the accompanying drawings, wherein:  
         [0028]    [0028]FIGS. 1A, 1B,  1 C and  1 D illustrate four ways in which boundary pixels can be adjacent to interior pixels;  
         [0029]    [0029]FIG. 2 illustrates the partitioning of an image among boundary pixels and interior blocks;  
         [0030]    [0030]FIG. 3 is a flowchart of image compression according to the present invention;  
         [0031]    FIGS.  4 A- 4 G illustrate the propagation of a state vector from the boundary of an 8×8 block into the interior of the 8×8 block.  
         [0032]    [0032]FIG. 5 is a flowchart of image decompression according to the present invention;  
         [0033]    [0033]FIG. 6 is a schematic block diagram of an encoder of the present invention;  
         [0034]    [0034]FIG. 7 is a schematic block diagram of a decoder of the present invention;  
         [0035]    [0035]FIG. 8 shows a 10×10 image that was compressed and decompressed using the method of the present invention;  
         [0036]    [0036]FIG. 9 shows the image of FIG. 8 after lossy compression and decompression;  
         [0037]    [0037]FIG. 10 shows the difference between the images of FIGS. 8 and 9. 
     
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0038]    The present invention is of a method of image compression and decompression which can be used to compress and decompress both still images and video frames. Specifically, the present invention can be used to compress and decompress a video stream more efficiently and more accurately than prior art methods such as MPEG.  
         [0039]    The principles and operation of image compression according to the present invention may be better understood with reference to the drawings and the accompanying description.  
         [0040]    Returning now to the drawings, FIG. 2 illustrates the partitioning of an input image according to the present invention. Specifically, FIG. 2 illustrates a portion of an image that has been partitioned, according to the present invention, into boundary pixels, labeled “b” and “b′”, and interior pixels, labeled “i”. To enhance the contrast between the boundary pixels and the interior pixels, the boundary pixels are shaded. The interior pixels come in 8×8 blocks, and each block is surrounded by a corresponding set of 36 boundary pixels. Each block of interior pixels constitutes an “interior set”. The set of boundary pixels that surrounds a block of interior pixels is considered to be the “boundary set” that corresponds to that block of interior pixels. Note that each pair of adjacent blocks of interior pixels shares eight boundary pixels b and two boundary pixels b′ in common, so that each boundary pixel b is a member of two different boundary sets, and each boundary pixel b′ is a member of four different boundary sets.  
         [0041]    In the example illustrated in FIG. 2, the blocks of interior pixels are 8×8 blocks. This is only a non-limitative example. The blocks of interior pixels may be blocks of any convenient size and shape, although rectangular and square blocks are preferred for processing efficiency.  
         [0042]    The encoding phase of the present invention consists of four steps, as illustrated in FIG. 3. In the first step (block  12 ), an input image  10  is partitioned among boundary pixels  14  and interior pixels  16 . In the second step (block  18 ), for each block of interior pixels, the corresponding set of boundary pixels (36 boundary pixels per boundary pixel set if the block is 8×8 as in FIG. 2) is interpolated to provide a corresponding set  20  of approximation pixels that is intended to resemble the targeted block of interior pixels. In the third step (block  22 ), for each block of interior pixels, the pixels of approximation set  20  are subtracted from the corresponding interior pixels  16  to provide a corresponding set  24  of difference pixels. Finally, in the fourth step, boundary pixels  14  and difference sets  24  are compressed (blocks  26  and  28 ) and then transmitted to the decoder (block  30 ).  
         [0043]    The interpolations of block  18  may be as simple as replacing each interior pixel with a weighted sum of the boundary pixels that surround that interior pixel&#39;s block, with the weights being a monotonically decreasing function of the Euclidean distances between the interior pixel and the boundary pixels. The preferred interpolation method, however, is dynamic programming, as described for example in R. E. Bellman and S. E. Dreyfus,  Applied Dynamic Programming,  Princeton University Press, Princeton N.J., 1962. The values of the 36 boundary pixels of a block are considered to be initial values of 36 elements of a state vector. The interpolation process is implemented as a controlled Markov sequence, in which the state vector is propagated towards the interior of the block.  
         [0044]    The process is cast as an optimal control problem by considering a 36-component state vector that is assumed to obey the dynamic process 
           X   k+1   =F   k   x   k   +u   k   +ƒ   ƒ   +w   k   (1) 
         [0045]    where x is the 36-component state vector, k is a stage index, F is an open loop (Markov) process matrix, u is a control vector, ƒ ƒ  is a prescribed forcing function vector and w is a zero-mean process noise vector with a known covariance Q. The problem is to find a so-called “optimal control” u* that minimizes the differences along the center cross, i.e., on the borders between the four inner quadrants. The solution via dynamic programming is obtained by defining a quadratic performance criterion  
             J   =         ∑     k   =   1       N   -   1            (         1   2          x   k   T          Ax   k       +       1   2          u   k   T          Bu   k         )       +       J   f          (     x   N     )                 (   2   )                               
 
         [0046]    where N is the total number of stages of the process. The optimal cost-to-go from the k-th stage is given by  
               J   k   *     =         1   2          x   k   T          S   k          x   k       +       ψ   k          x   k                 (   3   )                               
 
         [0047]    and the minimizing control is given by 
           u*   k −( B+S   k+1 ) −1   [S   k+1 ( F   k   x   k +ƒ ƒ )+ψ T   k+1 ]  (4) 
         [0048]    i.e.,  
           u*   k   =−C   k   x   k −θ k   (5) 
         [0049]    where 
           C   k =( B+S   k+1 ) −1   S   k+1   F   k   (6) 
         [0050]    and 
         θ k ( B+S   k+1 ) −1 ( S   k+1 ƒ ƒ +ψ T   k+1 )  (7) 
         [0051]    Also, according to this solution the cost parameters S and ψ are available from the end conditions via the backward regressions 
           S   k   =A+C   T   k   BC   k +( F   k   −C   k ) T   S   k+1 ( F   k   −C   k )+Δ S   k    (8) 
         [0052]    and 
         ψ k =−θ T   BC +(ƒ ƒ −θ) T   S   k+1 ( F   k   −C   k )+ψ k+1 ( F   k   −C   k )  (9) 
         [0053]    for which the end conditions are  
                 J   f          (     x   N     )       =         1   2          x   N   T          S   N          x   N       +       ψ   N          x   N                 (   10   )                               
 
         [0054]    and we take ψ N ≡0.  
         [0055]    With F N , S N , ΔS N , B and ƒ ƒ prescribed, equations (5) through (9) give a set of minimizing controls {u* 1 , . . . , u* N }. Equation (1) then is used with w k =0 to propagate the state vector forward from k=1 to k=N. Appendix A is a listing of MATLAB™ code for propagating the 36-component state vector from the boundary of an 8×8 block to the interior of an 8×8 block, in N=7 stages. FIGS.  4 A- 4 G illustrate the position of the state vector (shaded, with numbers corresponding to elements of the state vector) relative to the boundary pixels and the interior pixels at the beginning of each stage. In each stage, the interior pixels to be approximated in that stage are marked by asterisks. Each marked interior pixel is approximated based on the values of three state vector pixels: the two state vector pixels that share common edges with the target interior pixel and a third state vector pixel that shares common edges with those two state vector pixels. The state vector element corresponding to the third state vector pixel then is replaced by the approximate value thus obtained. For example, in the first stage, the upper left interior pixel is approximated based on x(1), x(2) and x(36), and then x(1) is set equal to the approximate value thus obtained. At the beginning of the first stage (FIG. 4A), the elements of the state vector are the values of the corresponding boundary pixels. At the end of the last stage, x(5), x(6), x(14), x(15), x(23), x(24), x(32) and x(33) retain their initial values, but the other state vector elements are equal to interpolated values of respective interior pixels that lie along the central cross of the 8×8 block.  
         [0056]    The decoding phase of the present invention consists of four steps, as illustrated in FIG. 5. In the first step, the compressed boundary pixels and the compressed difference sets are received (block  32 ) and decompressed (block  34 ). The first step recovers boundary pixels  38  and difference sets  40 , either exactly, if the compression in blocks  26  and  28  was lossless, or approximately, if the compression in blocks  26  and  28  was lossy. In the second step (block  42 ), for each block of interior pixels, the corresponding set of boundary pixels is interpolated to provide a corresponding set  44  of approximation pixels. The interpolation of block  42  is performed identically to the interpolation of block  18 . In the third step (block  46 ), for each block of interior pixels, the pixels of approximation set  44  are combined with the corresponding difference pixels  40  to provide a corresponding set  48  of reconstructed interior pixels. Finally, in the fourth step, reconstructed interior pixels  48  are merged with boundary pixels  38  to produce a reconstructed image  52 .  
         [0057]    To compensate for quantization error and truncation error due to the compression, the combining of approximation set  44  with corresponding difference pixels  40  is done using a Kalman filter. A Kalman filter is an algorithm for estimating values of a state vector x that obeys a dynamic process similar to equation (1): 
           x   k+1   =F   k   x   k   +u   k +ƒ ƒ   +w   k   (11) 
         [0058]    based on measurements that are related to the state vector by a measurement process: 
           Y   k   =Hx   k   +v   k   (12) 
         [0059]    where v k  is measurement noise, assumed to be of zero mean, and normally distributed with a covariance R. Each stage of the algorithm has two phases, a prediction phase and a correction phase. In the prediction phase, an a priori estimate of x k+1 , denoted {overscore (x)} k+1 , is obtained using equation 11: 
           {overscore (x)}   k+1   =F   k   {circumflex over (x)}   k   +u   k +ƒ ƒ   (13) 
         [0060]    In the correction phase, x k+1  is obtained as an a postiori estimate, based on {overscore (x)} k+1  and the corresponding measured y k+1 : 
           {circumflex over (x)}   k+1   ={overscore (x)}   k+1    +K ( y   k+1   −H{overscore (x)}   k+1 )  (14) 
         [0061]    where the Kalman gain matrix K is defined via an error covariance matrix 
         Π k+1 =( Q+F   k Π k   −1   F   k   T ) −1   +H   T   R   −1   H   (15) 
         [0062]    as 
           K=Π   k+1   −1   H   T   R   −1   (16) 
         [0063]    In this case, for each approximation set  44 , the measurement error term in equation (14), y k+1 −H{overscore (x)} k+1 , is the corresponding difference set  40 . The formal identity of equations (1) and (11) allows interior pixels  48  of each 8×8 block to be reconstructed from the outside in, just as boundary pixels  14  or  38  are interpolated from the outside in to produce approximation pixels  20  or  44 . Note that in the special case of K being the identity matrix, the Kalman filter reduces to simple addition of difference pixels  40  to approximation pixels  44 .  
         [0064]    Also note that the combining of approximation set  44  with difference set  40  may be done using a Kalman filter, as described above, independently of whether boundary pixels  14  or  38  are interpolated using dynamic programming.  
         [0065]    Appendix B is a listing of MATLAB™ code for linear two-dimensional prediction and Kalman filtering of a 10×10 image.  
         [0066]    [0066]FIG. 6 is a schematic block diagram of an encoder  100  of the present invention. An image capture device  102 , such as a digital camera, captures an image and sends the image to a partitioner  104 . Partitioner  104  partitions the image among boundary pixels and interior pixels. The boundary pixels are sent to an interpolator  106  that interpolates the boundary sets of the interior pixel blocks to produce approximation sets. A subtracter  108  subtracts the approximation sets from the corresponding interior pixel blocks to produce corresponding difference sets. The boundary pixels and the difference sets are compressed by a compressor  110  and transmitted by a transmitter  112 .  
         [0067]    [0067]FIG. 7 is a schematic block diagram of a decoder  120  of the present invention. The compressed and transmitted boundary pixels and difference sets are received by a receiver  122  and decompressed by a decompressor  124 . The boundary pixels are interpolated by an interpolator  128  to provide approximation sets corresponding to the interior blocks. Corresponding approximation sets and difference sets are combined by a Kalman filter  130  to provide reconstructed blocks of interior pixels. A merger  132  merges the reconstructed interior blocks with the boundary pixels to provide a reconstructed image that is displayed on a display device  134 .  
         [0068]    Partitioner  104 , interpolator  106 , subtracter  108  and compressor  110  of encoder  100  may be implemented as software modules in a general purpose computer, as firmware, or as hardware. Similarly, decompressor  124 , interpolator  128 , Kalman filter  130  and merger  132  of decoder  120  may be implemented as software modules in a general purpose computer, as firmware, or as hardware.  
         [0069]    [0069]FIG. 8 is a 10×10 image that was compressed and decompressed using the method of the present invention. FIG. 9 shows the image of FIG. 8 after lossy compression and decompression. FIG. 10 shows the differences between the input pixels and the output pixels.  
         [0070]    While the invention has been described with respect to a limited number of embodiments, it will be appreciated that many variations, modifications and other applications of the invention may be made.