Abstract:
The efficient motion compensation apparatus for digital video format down-conversion with variable conversion ratio is disclosed. The apparatus is characterized by an interpolation and decimation filters derived using a number of orthogonal transforms with variable transform sizes and implemented using efficient computation architectures. The computation architecture comprises the orthogonal transform kernel selection means, frequency component computing means, coefficient weighting means and pixel reconstruction means. A simple architecture for both interpolation and decimation filtering processes has been invented. The result is the dramatic reduction of the shifting and adding/subtracting operations, making them suitable for implementation in LSI realization of the video format down-conversion of digital video systems.

Description:
BACKGROUND OF THE INVENTION  
       [0001]     1. Field of the Invention  
         [0002]     The present invention relates to an apparatus for digital video format down-conversion with arbitrary conversion ration, and to a method therefor. The invention is applicable to the implementation of a digital video format down-conversion for use in digital video decoder. Typical applications of this invention include HDTV decoding, DVD decoder, video conferencing and picture-in-picture systems.  
         [0003]     2. Description of the Related Art  
         [0004]     Low-resolution digital video decoders have received considerably attention lately in academia and industry. In a digital video decoding system, the format down-conversion can be achieved by decimating the decoded full-resolution video sequences. Reconstructed video with good quality can be obtained by using this method. However, the decimation of decoded video sequences adds complexity to the full-resolution video decoding. In order to reduce the amount of computation, the memory size and other constrains such as memory bandwidth and clock rates incurred by this approach, image decimation has to be realized in the earlier stage of the decoder, for example, inside the decoding loop.  
         [0005]     In European patent application EP0707426, a digital video decoder that provides format down-conversion with motion-compensation is disclosed. Motion compensation is achieved by first interpolating, then performing full-resolution motion compensation, and finally, decimation of the compensated output.  
         [0006]     European patent application EP0786902A discusses a technique for changing image resolution using a direct discrete cosine transformation (DCT) mapping, whereby DCT coefficient values of an original resolution are mapped to converted coefficient values of a new resolution, without having to convert the original DCT coefficient values into pixels first.  
         [0007]     An effective method for the digital video format down-conversion has been invented and filed in Japan on Jun. 8, 1999, entitled “A generalized orthogonal transform method for low-resolution video decoding” with application No. H11-160876, published as JP 2000-350207 and assigned to Matsushita Electric Industrial Co. Ltd.  FIG. 1  shows a block diagram of this video format down-conversion method. The details of the system operation and the orthogonal kernels were discussed in the above-mentioned patent application. In this architecture, the low-resolution pixels stored in the frame buffer are interpolated and decimated using orthogonal transform basis functions before and after the full-resolution motion compensation. The interpolation and decimation filters play a very important role in controlling the error propagation introduced by picture decimation of the format down-conversion system of digital video. In the format down-conversion system of digital video shown in  FIG. 1 , these filters are realized using a number of orthogonal transform kernels. One example for the orthogonal transform kernels used for video down-conversion with the decimation ratio of 8:3 is illustrated in  FIGS. 2A  to  2 G. The direct computation architecture of the interpolation and decimation filtering operations based on these kernels are shown in  FIGS. 3A and 3B . Since the coefficients of the kernels are simpler the implementation of the system is relatively easy compared to the conventional digital video format down-conversion methods. Simulation results show that this method is also very effective in error propagation control.  
         [0008]     The digital video format down-conversion method using orthogonal transform described in the prior art generates high quality down-converted video. The conversion ratio is however fixed in the methods described in the prior art. Due to the expansion and diversity of multimedia applications and present communication devices, especially the mobile terminals equipped with various resolution screens, there has been growing need for variable resolution digital video format down-conversion. The in-loop variable size video format down-decoding algorithms are required to efficiently decode high resolution encoded bitstreams and display the decoded down-sized pictures on various communication terminals with different resolutions. The problem to be solved by the current invention is to derive a set of interpolation and decimation filters using orthogonal transform with different transform sizes and establish efficient computation architectures for the interpolation and decimation filtering processes to achieve effective motion compensation for the digital video format down-conversion system with variable conversion ratio.  
       SUMMARY OF THE INVENTION  
       [0009]     U.S. Pat. No. 4,768,159 discloses an efficient computation method for discrete Fourier transform. In order to solve the above-described problem, efficient computation architecture for implementing interpolation and decimation filters used by the digital video format down-conversion system is invented.  
         [0010]     The original resolutions for encoded videos may differ from target resolution of video displayer with various ratios. Orthogonal kernels used for all the possible integer resolution ratios are invented. The orthogonal transform kernels are defined in the invention, and the selection of proper kernels for a particular resolution change is defined also. The computation architecture comprises three apparatus, namely frequency component computing means, coefficient weighting means and pixel reconstruction means. Less computational operations are required compared to the direct implementation of the orthogonal transform kernels described in the prior art.  
         [0011]     The frequency component computing means is used to transform the input into frequency domain to generate the transform coefficients The coefficient weighting means is used for receiving transform coefficients and generating weighted transform coefficients. The weighted transform coefficients are finally transformed into spatial domain to generate the filtered pixels having different resolution from the original pixels. Said decimation/interpolation parameter generator is used to determine the integer resolution conversion ratio, 8:r, select the appropriate orthogonal kernels and generate and provide decimation/interpolation parameters to said frequency component computing means, coefficient weighting means and pixel reconstruction means. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0012]     These and other objects and features of the present invention will become clear from the following description taken in conjunction with the preferred embodiments thereof with reference to the accompanying drawings throughout which like parts are designates by like reference numerals, and in which:  
         [0013]      FIG. 1  illustrates a block diagram for low-resolution video decoder described in the prior art.  
         [0014]      FIG. 2A  illustrates the kernels, K 1  and K 2 , for low-resolution video decoding for down-conversion ratio of 8:7 to 8:2.  
         [0015]      FIG. 2B  illustrates the kernels, K 3  and K 4 , for low-resolution video decoding with the down-conversion ratio of 8:7.  
         [0016]      FIG. 2C  illustrates the kernels, K 3  and K 4 , for low-resolution video decoding with the down-conversion ratio of 8:6.  
         [0017]      FIG. 2D  illustrates the kernels, K 3  and K 4 , for low-resolution video decoding with the down-conversion ratio of 8:5.  
         [0018]      FIG. 2E  illustrates the kernels, K 3  and K 4 , for low-resolution video decoding with the down-conversion ratio of 8:4.  
         [0019]      FIG. 2F  illustrates the kernels, K 3  and K 4 , for low-resolution video decoding with the down-conversion ratio of 8:3.  
         [0020]      FIG. 2G  illustrates the kernels, K 3  and K 4 , for low-resolution video decoding with the down-conversion ratio of 8:2.  
         [0021]      FIG. 3A  illustrates the direct computation architecture of transform kernels for 8:3 digital video down-conversion with computation architecture for interpolation filtering.  
         [0022]      FIG. 3B  illustrates the direct computation architecture of transform kernels for 8.3 digital video down-conversion with computation architecture for decimation filtering.  
         [0023]      FIG. 4  illustrates a block diagram of an efficient motion compensation apparatus for low-resolution digital video format down-conversion system.  
         [0024]      FIG. 5  illustrates a block diagram for pixel interpolation and decimation filtering processes with various interpolation and decimation ratios 8:r, r=2, 3, . . . , 7.  
         [0025]      FIG. 6  illustrates a block diagram of the frequency component computing means.  
         [0026]      FIG. 7  illustrates a block diagram of the coefficient weighting means.  
         [0027]      FIG. 8  illustrates a block diagram of the pixel reconstruction means.  
         [0028]      FIG. 9  illustrates a block diagram for interpolation and decimation filtering processing using cascaded arithmetic units.  
         [0029]      FIG. 10  illustrates a block diagram of the pre-processing means.  
         [0030]      FIG. 11  illustrates a block diagram of cascaded arithmetic units.  
         [0031]      FIG. 12  illustrates the transform kernel indicator (integer value r) generation.  
         [0032]      FIG. 13A  illustrates the computation architectures for interpolation filter used for digital video format down-conversion with the ratio of 8:3.  
         [0033]      FIG. 13B  illustrates the computation architectures for decimation filter used for digital video format down-conversion with the ratio of 8:3. 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0034]     The present invention is an apparatus for performing efficient motion compensation for digital video format down-conversion for motion compensation in digital video format down-conversion, which comprises:  
         [0035]     a frequency component computing means having an input terminal for receiving a block of original pixels, transforming said original pixels into frequency domain and providing transform coefficients;  
         [0036]     a coefficient weighting means for receiving said transform coefficient, multiplying each said transform coefficient by one of the pre-determined constant values to generate weighted transform coefficients;  
         [0037]     a pixel reconstruction means having an input terminal for receiving said weighted transform coefficients and having an output terminal, for generating filtered pixels which have different resolution from said original pixels,  
         [0038]     a decimation/interpolation parameter generator having a first input terminal for receiving original resolution (Ro), having a second input terminal for receiving target resolution (Rt) and having two output terminals, said decimation/interpolation parameter generator for deriving a transform kernel indicator (an integer value r), by identifying the integer value r from integer set {2, 3, 4, 5, 6, 7} such that the ratio 8:r is the most close to the resolution ratio Ro:Rt, and providing said transform kernel indicator (said integer value r) and decimation/interpolation parameters through its two output terminals;  
         [0039]     transform kernels K 1  and K 2  generator having an input terminal for receiving said transform kernel indicator (said integer value r) and having two output terminals, said transform kernels K 1  and K 2  generator for generating orthogonal transform kernels K 1 [r], K 2 [r] from pre-determined transform kernels K 1  and K 2 . by extracting the first r rows from K 1  and first r columns from K 2 , respectively, characterized in that the transform kernels K 1  and K 2  are provided in accordance with a generalized orthogonal transformation having kernels defined as follows:  
         K   1     =     (         α       α       α       α       α       α       α       α             5   ⁢           ⁢   β           4   ⁢           ⁢   β           3   ⁢           ⁢   β         β         -   β             -   3     ⁢           ⁢   β             -   4     ⁢           ⁢   β             -   5     ⁢           ⁢   β               2   ⁢           ⁢   γ         γ         -   γ             -   2     ⁢           ⁢   γ             -   2     ⁢           ⁢   γ           -   γ         γ         2   ⁢           ⁢   γ               4   ⁢           ⁢   β           -   β             -   5     ⁢           ⁢   β             -   3     ⁢           ⁢   β           3   ⁢           ⁢   β           5   ⁢           ⁢   β         β           -   4     ⁢           ⁢   β             α         -   α           -   α         α       α         -   α           -   α         α             3   ⁢           ⁢   β             -   5     ⁢           ⁢   β         β         4   ⁢           ⁢   β             -   4     ⁢           ⁢   β           -   β           5   ⁢           ⁢   β             -   3     ⁢           ⁢   β             γ           -   2     ⁢           ⁢   γ           2   ⁢           ⁢   γ           -   γ           -   γ           2   ⁢           ⁢   γ             -   2     ⁢           ⁢   γ         γ         )         
         K   2     =     (         1       5       2       4       1       3       1           1       4       1         -   1           -   1           -   5           -   2             1       3         -   1           -   5           -   1         1       2           1       1         -   2           -   3         1       4         -   1             1         -   1           -   2         3       1         -   4           -   1             1         -   3           -   1         5         -   1           -   1         2           1         -   4         1       1         -   1         5         -   2             1         -   5         2         -   4         1         -   3         1         )         
 
         [0040]     transform kernels K 3  and K 4  generator having an input terminal for receiving said transform kernel indicator (said integer value r) and having two output terminals, said transform kernels K 3  and K 4  generator for selecting orthogonal transform kernels K 3 [r] and K 4 [r] from a pool of pre-determined transform kernels K 3  and K 4  candidates, by choosing the transform kernels defined for resolution ratio 8:r from the pre-determined candidate kernels, characterized in that the transform kernels K 3 [r] and K 4 [r] candidates are provided in accordance with a generalized orthogonal transformation having kernels defined as follows:  
       r   =   7       
           K   3     ⁡     [   7   ]       =     (           σ   7           σ   7           σ   7           σ   7           σ   7           σ   7           σ   7               3   ⁢     μ   7             2   ⁢     μ   7             μ   7         0         -     μ   7               -   2     ⁢     μ   7               -   3     ⁢     μ   7                 3   ⁢     ν   7             ν   7             -   2     ⁢     ν   7               -   4     ⁢     ν   7               -   2     ⁢     ν   7             ν   7           3   ⁢     ν   7                 2   ⁢     μ   7             -     μ   7               -   3     ⁢     μ   7           0         3   ⁢     μ   7             μ   7           -     μ   7                 2   ⁢     ν   7               -   3     ⁢     ν   7             -     ν   7             4   ⁢     ν   7             -     ν   7               -   3     ⁢     ν   7             2   ⁢     ν   7                 μ   7             -   3     ⁢     μ   7             2   ⁢     μ   7           0           -   2     ⁢     μ   7             3   ⁢     μ   7             -     μ   7                 ν   7             -   2     ⁢     ν   7             3   ⁢     ν   7               -   4     ⁢     ν   7             3   ⁢     ν   7               -   2     ⁢     ν   7             ν   7           )         
           K   4     ⁡     [   7   ]       =     (         1       3       3       2       2       1       1           1       2       1         -   1           -   3           -   3           -   2             1       1         -   2           -   3           -   1         2       3           1       0         -   4         0       4       0         -   4             1         -   1         -       3         -   1           -   2         3           1         -   2         1       1         -   3         3         -   2             1         -   3         3         -   1         2         -   1         1         )         
       r   =   6       
           K   3     ⁡     [   6   ]       =     (           σ   6           σ   6           σ   6           σ   6           σ   6           σ   6               4   ⁢     μ   6             3   ⁢     μ   6             μ   6           -     μ   6               -   3     ⁢     μ   6               -   4     ⁢     μ   6                 ν   6         0         -     ν   6             -     ν   6           0         ν   6               σ   6           -     σ   6             -     σ   6             σ   6           σ   6           -     σ   6                 ν   6             -   2     ⁢     ν   6             ν   6           ν   6             -   2     ⁢     ν   6             ν   6               μ   6             -   3     ⁢     μ   6             4   ⁢     μ   6               -   4     ⁢     μ   6             3   ⁢     μ   6             -     μ   6             )         
           K   4     ⁡     [   6   ]       =     (         1       4       1       1       1       1           1       3       0         -   1           -   2           -   3             1       1         -   1           -   1         1       4           1         -   1           -   1         1       1         -   4             1         -   3         0       1         -   2         3           1         -   4         1         -   1         1         -   1           )         
       r   =   5       
           K   3     ⁡     [   5   ]       =     (           σ   5           σ   5           σ   5           σ   5           σ   5               2   ⁢     μ   5             μ   5         0         -     μ   5               -   2     ⁢     μ   5                 3   ⁢     ν   5             -     ν   5               -   4     ⁢     ν   5             -     ν   5             3   ⁢     ν   5                 μ   5             -   2     ⁢     μ   5           0         2   ⁢     μ   5             -     μ   5                 ν   5             -   3     ⁢     ν   5             4   ⁢     ν   5               -   3     ⁢     ν   5             ν   5           )         
           K   4     ⁡     [   5   ]       =     (         1       2       3       1       1           1       1         -   1           -   2           -   3             1       0         -   4         0       4           1         -   1           -   1         2         -   3             1         -   2         3         -   1         1         )         
       r   =   4       
           K   3     ⁡     [   4   ]       =     (           σ   4           σ   4           σ   4           σ   4               2   ⁢     μ   4             μ   4           -     μ   4               -   2     ⁢     μ   4                 σ   4           -     σ   4             -     σ   4             σ   4               μ   4             -   2     ⁢     μ   4             2   ⁢     μ   4             -     μ   4             )         
           K   4     ⁡     [   4   ]       =     (         1       2       1       1           1       1         -   1           -   2             1         -   1           -   1         2           1         -   2         1         -   1           )         
       r   =   3       
           K   3     ⁡     [   3   ]       =     (           σ   3           σ   3           σ   3               μ   3         0         -     μ   3                 ν   3             -   2     ⁢     ν   3             ν   3           )         
           K   4     ⁡     [   3   ]       =     (         1       1       1           1       0         -   2             1         -   1         1         )         
       r   =   2       
           K   3     ⁡     [   2   ]       =     (           σ   2           σ   2               μ   2           -     μ   2             )         
           K   4     ⁡     [   2   ]       =     (         1       1           1         -   1           )         
 
         [0041]     The operation of the apparatus of the invention is explained.  
         [0042]     First the operation of the computation architecture for the interpolation and decimation filtering processes is explained. The decimation/interpolation parameter generator receives the original resolution of decoded video, Ro, and target resolution of video displayer, Rt. The integer resolution conversion ratio r (8:r) is derived by identifying the integer value r from integer set {2, 3, 4, 5, 6, 7} such that the ratio 8:r is the most close to the resolution ratio Ro:Rt. The orthogonal transform kernels (K 1 [r], K 2 [r], K 3 [r] and K 4 [r]) are retrieved from a pool of pre-determined orthogonal transform kernels. The decimation/interpolation parameters are then generated and provided to the frequency component computing means, the coefficient weighting means and pixel reconstruction means. The original pixels are transformed into frequency domain by said frequency component computing means to generate the transform coefficients. Said transform coefficients are multiplied by a set of pre-determined constants by said coefficient weighting means to generate the weighted transform coefficients. The weighted transform coefficients are transformed from frequency domain into spatial domain by said pixel reconstruction means to provide filtered pixels which have different resolution from said original pixels.  
         [0043]     Next, the operations of the frequency component computing means are explained. A reversed sequence of a block of the original pixels is generated in upper or lower address reversed order. A pair of selected pixel sequences is selected from said pixel sequence, the reversed sequence, the transform coefficients and the bit-shifted coefficient sequence by a pixel selecting means. An operation indication sequence is generated by the pixel selecting means to indicate the adding or subtracting operation. The sum or difference of said pair of selected pixel sequences is computed based on said operation indication sequence to generate said transform coefficients. Each transform coefficient is shifted by one or more bits to generate said bit-shifted coefficient sequence.  
         [0044]     The frequency component computing means can also be operated using another method described here. The data address reversing means provides a reversed data set of a block of said original pixels in upper or lower address reversed order. A data selecting means receives said original pixels and said reversed data set to provide an operation indication set and two selected data sets. The calculator computes sum or difference of each pair of said selected data to generate processed data. One or more cascaded arithmetic units receives said processed data, manipulates them algebraically to provide said transform coefficients.  
         [0045]     The operations of the coefficient weighting means are explained. Each transform coefficient is multiplied by one of said pre-determined constant values stored in said coefficient memory. The output of said multiplying means or said transform coefficients are switched based on a coefficient bypass control signal to provide said weighted transform coefficients. Said coefficient bypass control signal is determined based on the transform kernels used for the format down-conversion system of digital video.  
         [0046]     The operations of said pixel reconstruction means are explained. The weighted transform coefficients are shifted by one or more bits to generate said bit-shifted vector. A pair of selected coefficient vectors is selected from said coefficient vectors said bit-shifted vector, filtered pixels and reversed pixel vector by a coefficient selecting means. An operation indication vector is generated by said coefficient selecting means to indicate the adding or subtracting operation. The sum or difference of said pair of coefficient samples is computed based on said operation indication vector to generate said filtered pixels. The reversed pixel vector of a block of filtered coefficients is generated by an address reversing means in upper or lower address reversed order.  
         [0047]     The pixel reconstruction means can also be realized using one or More cascaded arithmetic units. The operations of the arithmetic units used for said frequency component computation means and pixel reconstruction means are now explained. The shifter shifts the input data by one or more bits to generate bit-shifted data set. The data selector receives said input data and said bit-shifted data set to provide an operation indication set and two selected data sets. A calculator adds or subtracts two selected data sets based on said operation indication.  
         [0048]     The input terminal of the frequency component computing means can be coupled to the output terminal of the frame buffer, and the output terminal of the pixel reconstruction means can provide the interpolated pixels to the motion compensation means.  
         [0049]     The input terminal of the frequency component computing means can be coupled to the output terminal of the motion compensation means, and the output terminal of the pixel reconstruction means can provide the decimated pixels to the adding means.  
         [0050]     An embodiment shown in  FIG. 4  illustrates the block diagram of an efficient motion compensation system for digital video format down-conversion. The system comprises an syntax parser and variable-length decoding means  210 , an interpolation means  220 , an inverse motion compensation means  230 , a decimation means  240  and a frame buffer  250 . The interpolation means  220  and the decimation means  240  are used before and after the inverse motion compensation means  230 .  
         [0051]     The video bitstream  201  is first decoded by the syntax parser and variable-length decoding means  210  to obtain the decoded motion parameters  211 . The frame buffer  250  stores low-resolution video pictures. The low-resolution reference pixels  251  are retrieved from the frame buffer  250  by the interpolation means  220  and interpolated to generate the interpolated pixels  221  for inverse motion compensation means  230 . The inverse motion compensation means  230  performs motion compensation based on the interpolated pixels  221  and the decoded motion parameters  211  to obtain the motion-compensated pixels  231 . The motion-compensated pixels  231  are then decimated by the decimation means  240  to generate decimated pixels  241 .  
         [0052]     The effect of this embodiment is that the accuracy of inverse motion compensation for down-converted video can be improved by introducing the interpolation and decimation means. Since the format down-conversion processing of each video frame introduces error, it is extremely important to control the propagation of decoding errors. The properly designed interpolation and decimation means are efficient error control engines for minimizing the error of each decoded frame.  
         [0053]     Another embodiment shown in  FIG. 5  explains the method used in the interpolation and decimation means illustrated in  FIG. 4 . It comprises six components, namely, frequency component computing means  300 , coefficient weighting means  310 , pixel reconstruction means  320 , decimation/interpolation parameter generator  330 , transform kernel K 1  and K 2   340 , transform kernels K 3  and K 4  candidates  350 .  
         [0054]     The operation of this embodiment is now explained. The operation of said computation architecture for the interpolation and decimation filtering processes is now explained. The decimation/interpolation parameter generator  330  receives the original resolution of decoded video  333 , Ro, and target resolution of video displayer  334 , Rt. The integer resolution conversion ratio  332  r (8:r) is derived by identifying the integer value r  332  from integer set {2, 3, 4, 5, 6, 7} such that the ratio 8:r is the most close to the resolution ratio Ro:Rt. The orthogonal transform kernels (K 1 [r], K 2 [r], K 3 [r] and K 4 [r]) are retrieved from pre-determined transform kernels K 1  and K 2   340  and a pool of pre-determined transform kernels K 3  and K 4  candidates  350 . K 1 [r] and K 2 [r] are derived from transform kernels K 1  and K 2 , defined in  FIG. 2A , by extracting the first r rows from K 1  and first r columns from K 2 . The K 3 [r] and K 4 [r] are generated by choosing the transform kernels defined for resolution ratio 8:r from the candidate kernels defined in  FIG. 2B  through  FIG. 2G . The decimation/interpolation parameters  331  are then generated and provided to the frequency component computing means  300 , the coefficient weighting means  310  and pixel reconstruction means  320 . The original pixels  301  retrieved from the frame buffer  250  are transformed into transform coefficients  302  by frequency component computing means  300 . The transform coefficients  302  are multiplied by the pre-determined values to generate weighted transform coefficients  311  using the coefficient weighting means  310 . The weighted transform coefficients  311  are transformed, by the pixel reconstruction means  320 , into spatial domain to generate the filtered pixels  321  having different resolution from the original pixels  301 .  
         [0055]     Another embodiment shown in  FIG. 12  explains the generation of transform kernel indicator mentioned in the embodiment in  FIG. 5 . At first, the values r cuur  and r past  are set to be 7 and 8, respectively. The values rdiffcurr and rdiffpast are then computed by  
       rdiffcurr   =              r   curr     8     -       R   t       R   o                  
 
 and  
         rdiffpast   =              r   past     8     -       R   t       R   o                ,       
 
 respectively. If rdiffcurr is smaller than rdiffpast, r past  and r cuur  will be assigned to r past =r cuur  and r cuur =r cuur −1, Otherwise, r curr  will be outputted as the transform kernel indicator. After assignment of r past =r cuur  and r cuur =r cuur −1 are completed, the value of r cuur  is examined. If r cuur  is 2, the r curr  will be outputted as the transform kernel indicator, otherwise, the rdiffcurr and rdiffpast will be re-calculated by using updated r cuur  and r past . The above process will be repeated until the transform kernel indicator (an integer value r) is obtained and outputted. 
 
         [0056]     Another embodiment shown in  FIG. 6  explains the realization of the frequency component computing means  300  illustrated in  FIG. 5 . This apparatus comprises an address reversing means  400 , a pixel selecting means  410 , an adder/subtracter  420  and a bit shifting means  430 .  
         [0057]     The operation of this embodiment is now explained. The reversed sequence  402  of a block of the original pixels  401  is generated in upper/lower address reversed order by the address reversing means  400 . A pair of selected pixel sequences  412 ,  413  is selected from the original pixels  401 , reversed sequence  402 , transform coefficients  421  and bit-shifted coefficient sequence  431  by a pixel selecting means  410 . An operation indication sequence  411  is also generated by the pixel selecting means  410  to indicate the adding or subtracting operation. The sum or difference of the pair of selected pixel sequences  412 .  413  is computed based on the operation indication sequence  411  to generate the transform coefficients  421 . Each transform coefficient  421  is shifted by one or more bits by the bit shifting means  430  to generate the bit-shifted coefficient sequence  431 .  
         [0058]     Another embodiment shown in  FIG. 7  explains the details of the coefficient weighting means  310  shown in  FIG. 5 . This apparatus comprises a coefficient memory  500 , a multiplying means  510  and a multiplexer  520 .  
         [0059]     The operation of this embodiment is now explained. Each transform coefficient  511  is multiplied by one of the pre-determined constant values stored in the coefficient memory  500 . The output of multiplying means  510  and the transform coefficients  511  are multiplexed based on a coefficient bypass control signal  522  to provide the weighted transform coefficients  521 . The coefficient bypass control signal is determined based on the transform kernels used for the format down-conversion system of digital video.  
         [0060]     Another embodiment shown in  FIG. 8  explains the details of the pixel reconstruction means  320  shown in  FIG. 5 . This apparatus comprises a bit shifting means  600 , a coefficient selecting means  610  and an adder/subtracter  620 .  
         [0061]     The operation of this embodiment is now explained. The weighted transform coefficients  601  are shifted by one or more bits, by the bit shifting means  600  to generate the bit-shifted vector  602 . A pair of selected coefficient vectors  612 ,  613  is selected from the weighted transform coefficients  601 , bit-slifted vector  602  and filtered pixels  621  by the signal selecting means  610 . An operation indication vector  611  is also generated by the coefficient selecting means  610  to indicate the adding or subtracting operation. The sum or difference of the selected coefficient vectors  612 ,  613  is computed based on the operation indication vector  611  to generate the filtered pixels  621   
         [0062]     The immediate effect of the embodiments shown in  FIG. 5  through  FIG. 8  is that an image interpolation and decimation apparatus can be realized using efficient computation architecture derived according to the properties of generalized orthogonal transforms. Same apparatus can be used for both interpolation and decimation filtering processes derived based on orthogonal transforms. The intermediate computation results are fed back to a signal selecting means for further processing using same circuit. Thus, another effect of the embodiment shown in  FIG. 5  through  FIG. 8  is that it is possible to reduce the scale of the circuits required for format down-conversion system of digital video.  
         [0063]     The embodiment shown in  FIG. 9  explains another apparatus for implementation of the interpolation and decimation filtering processes. This apparatus comprises a pre-processing means  710 , two sets of cascaded arithmetic units  720 ,  740  and coefficient weighting means  730 .  
         [0064]     The operation of this embodiment is now explained. The original pixels  701  are processed by the pre-processing means  710  to generate processed data  711 . The processed data  711  is further processed by one set of cascaded arithmetic units  720  to generate the transform coefficients  721  which is the same as the transform coefficients  302  shown in  FIG. 5 . The coefficient weighting means  730  performs the same operation described in the embodiment shown in  FIG. 5  on the transform coefficients  721  and provides the weighted transform coefficients  731  Another set of cascaded arithmetic units receives the weighted transform coefficients  731  and processes them to generate the filtered pixel  741   
         [0065]     The embodiment shown in  FIG. 10  explains the details of the pre-processing means used in the embodiment illustrated in  FIG. 9 . It comprises a data selector  810 , a data address reversing means  820  and an adder/subtracter  830 .  
         [0066]     The operation of this embodiment is now explained. The reversed data set  821  of a block of original pixels  801  is generated in upper/lower address reversed order by the data address reversing means  820 . The data selector  810  chooses a pair of data  812 ,  813 , from the original pixels  801  and the reversed data set  821 , and generates an operation indicator  811 . The operation indicator  811  is a binary data with one value indicating adding operation and another value indicating subtracting operation. The adder/subtracter  830  computes the sum/difference of the selected pair of data  812 ,  813  based on the operation indicator  811  to generate the processed data  831 .  
         [0067]     Another embodiment shown in  FIG. 11  explains the details of the cascaded arithmetic units. Arithmetic unit  1   900  through arithmetic unit N  910 , N≧1, are connected with each other in a cascaded way. The Nth arithmetic unit  910  comprises a shifter  920   a  data selector  930  and an adder/subtracter  940 .  
         [0068]     The operation of the nth (n≧1) arithmetic unit  910  is now explained. The input r n−1 , which is the output of the (n−1)th arithmetic unit (or the output of the pre-processing means  710  if n=1), is shifted by one or more bits by a shifter  920  to generate the bit-shifted data S n . The data selector  930  chooses a pair of data (d 1n  and d 2n ), from r n−1  and s n , and an operation indicator (op n ) The operation indicator (op n ) is a binary data with one value indicating adding operation and another indicating subtracting operation. The adder/subtracter  940  computes the sum/difference of d 1n  and d 2n  based on the value of op n  to generate the output r n  of the nth arithmetic unit  910 .  
         [0069]     The effect of the embodiments shown in  FIG. 9  through  FIG. 11  is that it provides an alternative way to implement the interpolation and decimation filtering processing. Similar to the embodiments shown in  FIG. 5  through  FIG. 8 , same architecture can be used for both interpolation and decimation filtering processing derived based on orthogonal transforms. However, there is no feedback loop in each embodiment. Thus, the latency introduced by the interpolation and decimation circuits can be minimized at the cost of more hardware requirements. A computation architecture, which is built based on the apparatus described in the embodiments shown in  FIG. 9  through  FIG. 11 , for the purpose of video format down-conversion using the orthogonal transform kernels presented in  FIGS. 2A and 2F  of this patent specification are illustrated in  FIGS. 13A and 13B , respectively,  
         [0070]     This invention produces high-quality video format down-conversion solution. The computational requirement of the invention is much less intensive than that required for the conventional low-resolution video decoding methods or the direct implementation of the digital video format down-conversion method mentioned in the prior art. The apparatus designed for interpolation filter and decimation filter are of the same architecture. The number of shifting and adding operations required by the interpolation and decimation can be reduced by 46% and 21%, respectively, for the video format down-conversion at the down-conversion ratio of 8:3.