Three dimensional adaptive Laplacian Pyramid image coding

1r ) ,, ,_ n .t ·e y :, :r i- { ~ ,£ '· ,_ 1n ,_ SIGNAL PROCESSING V: Theories and Applications L Toffes, E. Masgrau, and M.A Lagunas (eds.) © Elsevier Science Publishers B. V., 1990 749 THREE DIMENSIONAL ADAPTIVE LAPLACIAN PYRAMID IMAGE CODING S.Sallent* L.Torres** L.Gils* * Department of Applied Mathematics and Telematics, ** Department of Signal Theory and Communications ETSETB-UPC, Apartado 30002, Barcelona 08034, Spain. ~n this. paper we propose a three dimensional Laplacian Pyramid coding scheme. The mput 1mag: sequence is subsampled both spatially and temporally into different channels usmg proper three dimensional sampling structures. This results in the image s~quen~e being r:presented by a series of bandpass sequences through three d1mens10nal Gauss1an and Laplacian pyramid data structures. In order to build the spatia-temporal pyramid structure several filters are discussed. 1 INTRODUCTION The Laplacian Pyramid is a new and efficient method for image encoding (1 ). The method is of increasing interest as bandpass pyramids and multiresolution images are being used in other image processing applications. The pyramid image structure can be naturally adapted for progressive image transmission over low-speed channels and hierarchical image retrieving in computerized image storage. The method obtains good compression rates and excellent visual quality for static images. lt was then logical to extend the pyramid image structure using arbitary nonrectangular sampling lattices and characterize the sampling lattices by matrices, thus providing a compact and powerful notation (2). On the other hand increasing interest is focused on image sequence coding .. Applications such as videoconference ~ideotelephone and low bit rate image coding m general, are a key issue in current video communication systems. The paper we present proposes a new three dimensional coding scheme as an extension of the previously reported work on static images. The input image sequence is subsampled both spatially and temporally into different channels using proper three dimensional sampling structures. This results in the image sequence being represented by a series of bandpass sequences through three dimensional Gaussian and Laplacian pyramid data structures. In order to build the temporal pyramid structure several spatial-temporal filters are discussed along with different sampling strategies. lt is shown, as in the static image case, that the performance of the pyramid encoding system can be improved by proper selection of the sampling structures thus resulting in an adaptive and efficient encoding method. Motion compensation algorithms are also introduced in the scheme to further decrease the bit rate as is the case for hybrid methods. 2 GAUSSIAN AND LAPLACIAN DATA STRUCTURES The temporal and spatial pyramid data structure represents the original image sequence into a set of code elements which are localized in spatial and temporal frequencies as well as in space and time. Each element in the new data structure is obtained by applying an appropriate three dimensional weighting function defined on an arbitrary sampling structure. The image sequence, and particularly the video-conference sequences, are characterized by the high correlations of the neighboring pixels in the spatial and temporal dimensions. The three dimensional pyramid coding reduces the correlation by subtracting the original sequence s:(l,m,n) from the low-pass version sequence of itself S"(l m n) 1 ' ' , where l,m,n are the temporally and spatially coordinates respectively. The code elements are obtained from those sequences as a suitable difference which represents the prediction error o I D0(l_,m,n) = S0 (l,m,n)- sp,m,n) (1) 750 being Do(l,m,n) more decorrelated than the original sequence. Then rather, than encode s:(l,m,n) it encodes the set of band-pass sequences obtaining data compression. The compression is achived because the low-pass sequences are built through a decimation process associated with Mi matrix. Consequently the. low-pass sequences are encoded at a reduced sample rate, and the high-pass sequences can be described with fewer bits. Iterating this process over the low-pass sequence a set of low-pass { s:(l,m, n)} and band-pass {Di(l,m,n)} image sequences is obtained whose support regions are defined on sampling lattices characterized by a 3X3 Mi matrix. Both data sets can be modeled as a pyramid data structures where each level is a sequence of decreasing dimension and resolution, the original sequence being the bottom of the pyramid. The low-pass sequence set is constructed applying recursively the decimation algorithm S~ (l,m ,n) = dec{ S0(l,rri ,n)} = t+l 1 o T TT LLL W(o,p,q) · Si(Mi [l,m,n] + [o,p,q] ) 0 p q (2) where o, p, q belong to the support region of the three dimensional weighting function W, i is the pyramid level, with i=O the bottom of the pyramid structure and os; i < L1. The band-pass sequence set is built by applying recursively the interpolation algorithm o I Di(l,m,n)=Si(l,m,n)- Si+ 1 (l,m,n)= s:(l,m,n)-inter {S:Jl,m,n)} = s:o.m.n>-lctet(M)I· I TT L,L,L,W(o,p,q)·S:iM-(1-o m-p n-q)) 0 p q (3) This algorithm is only evaluated for integer values of s:+p,m,n) .. When the decimation and interpolation process uses like-Gaussian filters, the data sets are named Gaussian and Laplacian data structures. 3 THREE DIMENSIONAL LAPLACIAN PYRAMID CODING The three dimensional Laplacian Pyramid Image coding with associated sampling lattices defined by a three by three matrices set {M} is based on the transmission of the quantized set of bandpass sequences {Di(l,m,n)}, L the number of total levels of the pyramid structure and DL-I(l,m,n) =S~jl,m,n) is the top sequence of the pyramid. The new coding scheme is implemented in four stages. aA set of L low-pass versions of the original sequence defined on sampling {MJ lattices is obtained by applying recursively the decimation algorithm. For the construction of each level i+ 1 an apropriate sampling lattice is chosen in order to provide the best information compaction. Thus resulting in each level having its proper sampling structure. In the frequency-domain the shape of the reciprocal unit cell associated to the sampling lattice M i is compared to the frequency content of the low-pass sequence s;(l,m,n)_ The algorithm can be modeled as a low-pass filtering and down-sampling process. bThe set of band-pass sequences are constructed by applying recursively the interpolation algorithm over the low-pass sequence. This algorithm can be modeled as an up-sampling process, low~pass filtering and a suitable difference. The weighting function and sampling lattice used are the same that have been used in the construction of the equivalent level in the low-pass sequence. c· The set of band-pass sequences are quantized by laplacian quantizers. The parameters of the quantizers are selected acording to the statistics, the total chosen compression and the quality of the desired reconstructed sequence. The set of quantized seq1 vari; seq rec1 L.~ o I whe is 1 arb con allo si m pro eh a fM, w •. < 5,.Q fM w~ D s:<~ the COl ap we tta 3.n ed ee he IdOf nd of ed he )n by :>n rei en on rei he 1e he he ce a 1g tre he ss as ng ng he on ss tre he ed en ed ed sequences {D';(l,m,n)} are transmited using variable length codewords. dAt the receiver, the original sequence is reconstructed applying recursive ly s·i (l,m,n)=D:o.m,n)+ ~et(M;)I· I TT LLL W(o,p,q) -s·i+t(M- (1o mp nq) ) 0 p q (4) Where s·L-p,m,n) = o·L-l(l,m,n) and s'o(l,m,n) is the reconstructed sequence. The use of arbitrary sampling lattices in the construction of low and band pass sequences allows to split the spectrum in regions of similar statistics adapting the coding process to the spatial and temporal characteristics of the sequence. [bJ s'.O.mn) I iM,. iM. W .,(o,p,q) W .. (o,p,q) [Q _D.,(l,m,n) '~-'1 ~ iM. I W,(o,p,q) s:(l.m.n) iM. W,(qp,q) J....+D;.;;.{I,:;:;m,;;;:;n~)~[Q IL...---..., -Is' .O.mn) ~ s',.(l.m,n) TRANSMITTER RECEIVER Figure 1 show's the block diagram of the Three Dimensional Laplacian Pyramid Coding. The prediction error can be improved applying motion compensation to the weighting function. A regular decomposition 751 quadtree method (3) is applied to segment the interframe differential signal into homogeneous regions of different block sizes. Each region is characterized by a motion vector and used to correct the local weighted average of each pixel. 4 SIMULATIONS AND RESULTS The results presented here were derived from two video sequences known as "Miss America" and "Waiter" which are 256x256 pixels per frame with eight pixels per bit and twenty five frames per second. In this coding method, the type of the filter has been chosen according to the appropriate matrix M i associated to each level. For instance, figure 2 shows the first level of the Three Dimensional Laplacian Pyramid for " Miss America " sequence. In this case we use 3D spatia-temporal filter with 125 taps and 1 D temporal filter 5 taps associated to [ 200) M;= 020 002 and [ 200) M;= 010 001 video-conference sequences Miss America" and "Waiter" a b Figure 2 The first level of the Laplacian Pyramid Do(l,m,n) for "Miss America" and "Waiter" using a) 125 tap spatia-temporal filter, and b) 5 tap temporal filter. 752 MISS AMERICA WALTER t 50000 t 40000 '; '; I 311000 .,., 5Z.2.'1 = 1 20000 • • 10000 -10 10 20 -20 -10 10 20 MISS AMERICA WALTER '0000 . 50000 t l 40000 (i: ~.u '; (/":.21.'1 '; t 30000 i 20000 I uooo 0 -20 -10 20 -20 20 Figure 3 shows the histograms of the first level using the spatia-temporal and temporal filters described above of the waiter and Miss America sequences. Figure 4 show> results of consecutive coded frames 6, 7, 8 and 9 of the "Miss Figure 4 Reconstructed frames 6,7,8,9 of "Miss America" and 1, 2, 3 of "Waiter" with a signal to noise ratio of 24 and 27 dB respectively. America" whith a compression ratio of 40, and frames 1, 2, and 3 of " Waiter" sequence with a compression ratio of 20. Computer results are presented at 64 x 4 kbits/sec with excellent visual quality and a signal to noise ratio of 24 and 27db respectly. This rate can be lowered by applying motion compensation to the three dimensional weighting function. The simulation results indicated that the proposed method is capable of operating very efficiently for a wide class of video applications such as 192 Kbits/second high definition video conferencing and in the range of B-ISON hierarchies. lt is shown that the scheme does not present any block effect, offers low computational complexity, and can be implemented in parallel. 5 CONCLUSION We presented the three dimensional Laplacian Pyramid Coding used to obtain a high compression rate for wide variety of video applications. This method is the result of extending the Pyramid Coding to the three dimensions, using arbitrary sampling lattices. Also the suitability to apply motion compensation on the weighting functions was emphasized, achieving a significant improvement in the compression ratio and visual quality. 6 REFERENCES [1] "The Laplacian Pyramid as a Compact Image Code", P.J. Burt, E.H. Adelson, IEEE Transactions on Communications, Vol. COM-31, n°4, April 1983, pp.532-540. [2] "An Adaptive Pyramid Image Coding System", S.Sallent, L. Torres, Proceedings ICASSP 1988, New York, April 11-14, 1988. [3] "Simulation Of A Teleconference Codec For ISDN", S.Sallent, A.Artero, J.Haro, EUSIPC0-90, Barcelona, September, 1990. [4] "The Sampling And Reconstruction Of Time-Varying Imagery With Applications in Video Systems", E. Dubois, Proceedings IEEE 1988, Vol. 73, 502-522, April 1985. S/( L. @, 1 e t i