IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 48, NO. 12, DECEMBER 2000
3365
Generalized Unequal Length Lapped Orthogonal Transform for Subband Image Coding Takayuki Nagai, Member, IEEE, Masaaki Ikehara, Member, IEEE, Masahide Kaneko, and Akira Kurematsu, Senior Member, IEEE
Abstract—In this paper, generalized linear phase lapped orthogonal transforms with unequal length basis functions (GULLOTs) are considered. The length of each basis of the proposed GULLOT can be different from each other, whereas all the bases of the conventional GenLOT are of equal length. In general, for image coding application, the long basis for a low-frequency band and the short basis for a high-frequency one are desirable to reduce the blocking and the ringing artifact simultaneously. Therefore, the GULLOT is suitable especially for a subband image coding. In order to apply the GULLOT to a subband image coding, we also investigate the size-limited structure to process the finite length signal, which is important in practice. Finally, some design and image coding examples are shown to confirm the validity of the proposed GULLOT. Index Terms—GenLOT, subband image coding, symmetric extension method, unequal length basis functions.
I. INTRODUCTION
L
APPED orthogonal transforms (LOTs) play an important role in transform coding and have been extensively studied [1]–[10]. In [5]–[7], Malvar and Staelin have formalized its design, implementation, and size-limited structure. It is well known that the LOT is a particular class of linear-phase is paraunitary filterbanks, where the length of each filter . In restricted to twice the number of channels [8], the LOT has been generalized as the generalized lapped is a positive orthogonal transforms (GenLOTs: integer). The GenLOT can considerably reduce the blocking effect, which is a shortcoming of the DCT; however, it tends to spread the quantization error out to neighboring blocks. This causes more severe ringing artifacts around stronger edges of an image because of the long basis. One of the solutions to this problem is to use the GenLOT with unequal length basis functions, which are defined as the generalized linear phase unequal length lapped orthogonal transforms (GULLOTs). The GULLOT should have longer filters in the lower frequency bands to reduce the blocking, whereas the lengths of higher frequency bands must be shorter to suppress the ringing. This Manuscript received October 29, 1999; revised August 3, 2000. This work was supported in part by the Ministry of Education, Science, Sports, and Culture, Government of Japan, Encouragement of Young Scientists (A), 11750313, 1999. The associate editor coordinating the review of this paper and approving it for publication was Dr. Paulo J. S. G. Ferreira. T. Nagai, M. Kaneko, and A. Kurematsu are with the Course in Electronic Engineering, The University of Electro-Communications, Tokyo, Japan (e-mail:
[email protected]). M. Ikehara is with the Department of Electronics and Electrical Engineering, Keio University, Yokohama, Japan. Publisher Item Identifier S 1053-587X(00)10149-7.
is similar to the discrete wavelet transform that has unequal length basis functions. The widths of frequency bands are unequal as well, whereas the GULLOT divides the signal uniformly in the frequency domain. Such GULLOT’s have been reported by Tran and Nguyen [9], who showed that the same lattice structure as the GenLOT can be used and derived some conditions for the first and the last lattice blocks. Such a structure produces both longer and shorter filters; however, the fast algorithm is not involved. This is because the first block cannot be the DCT. Therefore, the computational complexity is the same as the equal length case since the GULLOT has the identical structure with that of the equal length filterbank. This means that this structure is not computationally efficient. Moreover, the unequal length property may be lost, i.e., outside region of the shorter filter’s support is not absolutely zero, when the parameters (plane rotation angles) are quantized. This happens because all coefficients located outside of the shorter filter’s support are forced to be zero by restricting the parameters. In this paper, we propose a GULLOT that has an efficient fast algorithm. Unlike the GULLOT in [9], our proposed GULLOT produces both longer and shorter filters structurally. Therefore, the unequal length property is completely guaranteed in spite of the parameter’s quantization. Since no restriction is required for the parameters, the first lattice block can be DCT. This means the fast algorithm for the DCT is applicable. The proposed GULLOT can be considered as a generalization of the GenLOT, including unequal length filters. We also investigate the implementation over finite-length signals, namely, the symmetric extension method for the GULLOT. For fast implementation, the size-limited structure for the GULLOT is derived based on the symmetric extension method. Some design examples and the results of image coding application show that our proposed GULLOT is valid. This paper is organized as follows. The GenLOT and the LOT with unequal length basis functions (ULLOT) is briefly reviewed in the next section. Section III discusses the GULLOT. In Section IV, the symmetric extension method and the size-limited structure for the GULLOT are investigated. Some design and coding examples are shown in Section V. Finally, conclusions are presented in Section VI. Notations: The bold-faced capital and small letters indicate denotes the transpose of matrices and vectors, respectively. and represent identity matrix of matrix . Matrices , counter identity matrix of size , and null matrix size
1053–587X/00$10.00 © 2000 IEEE
3366
IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 48, NO. 12, DECEMBER 2000
of size , respectively. The defined as
permutation matrix
is
denotes the -point DCT-II matrix, and the matrices and are real orthogonal matrices. The cascade structure of GenLOTs is illustrated in Fig. 1. For and are chosen as fast implementation,
.. .
(4) where
.. .
for and for or for and for and otherwise.
We often abbreviate the subscript when the size is obvious. diag represents the diagonal matrix whose diagonal entry is and round the positive real number to the vector . nearest integer toward minus infinity and infinity, respectively. II. PRELIMINARIES A. GenLOT In this subsection, the GenLOT is briefly reviewed. See [5]–[8] and [10] for more details. and be the block size (the number of chanLet nels) and the length of each basis (filter), respectively. The GenLOTs transform an infinite input signal into an infinite transform coefficient as ..
.
s are determined to maximize (or minimize) The parameters a particular cost function using a nonlinear optimization technique. The maximization of the stopband attenuation of the filters is one of the criteria for designing a GenLOT. Another possible cost function to be maximized is the following coding gain, which reflects coding efficiency of the transform over PCM (5)
where (1) ..
denotes a variance of the th subband channel [1].
B. ULLOT In [15], we developed the ULLOT. The PTM of the Fast ULLOT can be written as
.
matrix that contains the basis functions. where is an , the transform is called the LOT. The GenLOTs When to . The orthogonality extend the overlapping factor of the basis functions is achieved if and only if [5]
(6) where
(2) where
Since the above time-domain conditions are difficult to handle, it is better to represent GenLOTs by the filterbank’s notation. It is well known that the GenLOT is a particular class of linearphase paraunitary filterbank (LPPUFB) that has been factorized in [4]. The GenLOTs can be represented as the polyphase transfer matrix (PTM)
The system generated by (6) has shorter bases and longer ones . In the next section, the above ULLOT is generalized as the GULLOT.
(3) where
III. FORMULATION OF THE GULLOT We will derive the structure of GULLOTs in this section. We since the fast algorithm for the DCT is exassume . In this pected. The length of th basis is denoted as case, the necessary conditions for the existence of LPPUFBs are as follows [2], [10]: symmetric and anti-symmetric fila) There are ters: Symmetry Polarity Condition
NAGAI et al.: GENERALIZED UNEQUAL LENGTH LAPPED ORTHOGONAL TRANSFORM
3367
M
Fig. 1. Cascade structure of GenLOTs. Each line carries =2 samples. E and O represent even and odd coefficients, respectively. (a) Whole structure of analysis GenLOT. (b) Details of the ith block. (c) Details of the blocking.
b)
must be even: Length Condition In this paper, we impose the following restriction on GULLOTs. c) There exists a pair of symmetric and anti-symmetric filters with same . It can be easily seen that requirement c) contains both conditions . Moreover, c) is a) and b) since more restrictive than a) and b). For example, although the overis permissible under lapping factor conditions a) and b), conditon c) does not allow such a choice. As we will see later, the structure of our proposed GULLOT is based on the butterfly shown in Fig. 3(b). It reminds us that there exists at least one pair of symmetric and anti-symmetric filters with same . Even if the LPPUFB that does not satisfy requirment c) exists, some restrictions on the parameters must be required to implement it. We ignore such a class of LPPUFBs since our goal is to impose the unequal length property on GULLOTs structurally. and We assume that . The basic idea for constructing the GULLOT is to create some longer filters by adding some extra lattice blocks to the LOT/ULLOT. Here, we classify the GULLOTs into four types as follows. 1) Type A: All s are odd numbers. 2) Type B: All s are even numbers. 3) Type C: s consist of both odd and even numbers and is odd. 4) Type D: s consist of both odd and even numbers, and is even.
Fig. 2. D.
Four types of GULLOT’s. (a) Type A. (b) Type B. (c) Type C. (d) Type
These four types of GULLOTs are illustrated in Fig. 2. It should be mentioned that types C and D have two different centers of symmetry, that is, one is for odd length filters, and the other one is for even length filters. The distances between them . are always A. Types A and B Our proposed GULLOT transforms an input signal in the same way as (1). The finite length version of the transform will be disucussed later. Our generalization allows the basis functions of the GULLOT to have variable lengths of support. There-
Fig. 3. Cascade structure of the GULLOT’s. (a) Whole structure of the analysis GULLOT. Each line carries M=2 samples. (b) Details of the ith block. (c) Details of ^ (z ).
3
3368
IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 48, NO. 12, DECEMBER 2000
Fig. 6. Flowgraph for implementation of each block S for the Type C GULLOT. (a) Structure of S . (b) Details of the permutation.
terbank’s representation, where the orthogonality simply means a cascade of orthogonal matrices. We first define the PTM of the GULLOT for all types as
M
Fig. 4. Flowgraph for implementation of Type A GULLOTs. (a) Whole structure of Type A GULLOTs. Each line carries =2 samples. (b) Flowgraph for implementation of each block S . Each solid line carries M=2 samples, and each broken line is a set of samples. (c) Simplified implementation of each block S .
0
(7) where
The matrices and can be any real orthogonal matrices . However, the choice of (4) of size is suitable for fast implementation. In the above equation, represents (8)
Fig. 5. Flowgraph for implementation of Type B GULLOT’s. Each line carries M=2 samples.
fore, the matrix in (1) looks like Fig. 2. Of course, the outside regions of the shorter basis’s support are padded by zeros to keep the transform matrix rectangle. Here, we also use the fil-
denotes the number of non-negative (zero or posiwhere tive) elements of , and
It seems that the number may come out fractional; however, is this is not true. From requirement c), it turns out that
NAGAI et al.: GENERALIZED UNEQUAL LENGTH LAPPED ORTHOGONAL TRANSFORM
3369
Fig. 7. Frequency responses of eight-channel GULLOTs. (a) GULA. (b) GULB. (c) GULC. (d) GULD.
always even. This fact shows that is always an integer. The is a diagonal matrix whose entries are matrix for for
(9)
aligns the center For Types A and B, the above matrix of all filters. Therefore, the PTM (7) must satisfy the following relationship for the linear phase (LP) property [10]: (10) where
The first block such that matrix
slightly higher than that of the GenLOT, we prefer to use the DCT matrix for the first block since the fast algorithm is available. To show that the PTM realized by (7) is the valid GULLOT, the orthogonality, the unequal length property, and the LP property of (7) must be proven. Since the orthogonality and the unequal length property of the PTM are obvious, we would like to prove the following theorem. Theorem 1: The GULLOT generated by (7) has the LP property. Proof: Let be the GULLOT (Type A or Type B) or the GenLOT that satisfies (10). The overlapping factor of is assumed to be . By adding two more blocks, we expect to obtain the new GULLOT whose overlapping factor would be
can be replaced by the orthogonal (12) (11)
where
In this case, the transform is called the LPPUFB with unequal length filters. Although the coding gain of the LPPUFB is
where is a positive even integer. At this time, the PTM of the new GULLOT can be written as follows:
(13)
3370
IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 48, NO. 12, DECEMBER 2000
Fig. 8. Impulse responses of eight-channel GULLOTs. h (n) corresponds to the basis for the lowest frequency band, and h (n) denotes the basis for the highest frequency one. (a) GULA. (b) GULB. (c) GULC. (d) GULD. TABLE I COEFFICIENTS GULA
OF
If the new GULLOT in (13) satisfies (10), namely (14) it can be said that the PTM of (7) has LP property. Substituting (10) and (13) into (14), we can obtain (15) where
diag
where for for
Using the relationship (see the Appendix) (16)
NAGAI et al.: GENERALIZED UNEQUAL LENGTH LAPPED ORTHOGONAL TRANSFORM
3371
(19)
TABLE II COEFFICIENTS OF GULB
(20)
The matrix
is (21)
where we have (22), shown at the bottom of the page. The , and are parts of the matrices matrix such that
(15) comes to the definition (13). Hence, we can conclude that (14) holds. Taking into account the LP property of the first block , the proof is completed. It should be noted that when , i.e., , and becomes and , respectively. In this case, (7) is equivalent to (3). The structure of the proposed GULLOT is shown in Fig. 3.
The matrix
is the following
diagonal matrix:
diag
B. Types C and D As mentioned in the foregoing subsection, Type C and D GULLOTs can be factorized as (7). The proof of LP property is omitted since it is possible to prove in a similar way as above. C. Transform Matrix of the It is useful to consider the transform matrix . This transform matrix has size GULLOT , and the transformed coefficients can be computed from as the blocked input (17)
(23)
(the last block), the matrix in (22) When , must be slightly modified. Assuming that is odd and is even, or vice versa. Then, the th is replaced with the following vector: row of
where
denotes the th row of the matrix
.
IV. SIZE-LIMITED STRUCTURES FOR THE GULLOTS The transform matrix recursion
can be obtained by the following : or
(18)
To process finite-length signals, special care is required for the signal’s boundary to avoid the border distortion. The symmetric extension method, which reflects the signal at its boundaries, is often used to overcome this problem
for
is odd and is even and
is odd is even (22)
for
is odd and is even and
is even is odd
3372
IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 48, NO. 12, DECEMBER 2000
[11]–[14]. However, most of the symmetric extension methods presented in the literature use filterbanks with equal length. Thus, we show the nonexpansive symmetric extension method for the GULLOTs. Moreover, the symmetric extension methods have a disadvantage that the computational complexity for the transform and inverse transform increases because of the extended samples. In particular, for image processing, these computational overheads are not negligible. A reasonable solution would be to have the size-limited structure as mentioned in [14]. In the following section, the size-limited structures for the GULLOT will be discussed. Let the finite signal be . The symmetric extension method expands an input signal at each boundary as
TABLE III COEFFICIENTS OF GULC
TABLE IV COEFFICIENTS OF GULD
(24) where (25) Then, the expanded signal is transformed by the matrix , and transformed coefficients obtained as
..
.
can be
(26)
can be applied after the transSince the permutation matrix is considered instead of for the sake of conformation, has size venience. From (26), one can see that the matrix . Thus, the input signal does not have to be extended for the transform. The purpose of this section is to find the structure for the GULLOT based on the implementaof the matrix tion described in the foregoing section (see Fig. 3). A. Symmetric Extension Method for GULLOTs Before developing the size-limited structure, we show the nonexpansive symmetric extension method for GULLOTs.
1) Types A and B: As illustrated in Fig. 2(a) and (b), the symmetry center of all bases are located at the same point in these cases. This fact shows that the same symmetric extension method used in the filterbanks with equal length is applicable to the GULLOTs of types A and B. 2) Types C and D: The main difficulty in developing the symmetric extension method for these classes comes from the fact that the GULLOTs of Types C and D have two different centers of symmetry. For example, let us consider and . In this case, the case where each subband sequence looks like the first expression at the bottom of the next page, where HS, HA, WS, and WA denote half sample symmetry, half sample anti-symmetry, whole sample symmetry, and whole sample anti-symmetry, must be transmitted respectively. All samples enclosed by to reconstruct the original sequence. Since the number of the samples that must be sent is greater than that of the input signal, it seems that the nonexpansive extension is impossible. Fortunately, from the property of an antisymand are always zero. metric filter, the samples can be sent instead of sending , and Therefore, can be discarded without loss of information. This
NAGAI et al.: GENERALIZED UNEQUAL LENGTH LAPPED ORTHOGONAL TRANSFORM
means that the nonexpansive symmetric extension is possible in this case. To complete the first block, the sample is moved to the first block. Hence, the first block becomes . This shift is a permutation matrix s task. This symmetric extension method is applicable to every GULLOT defined in the foregoing section. This is because the structure we have derived guarantees an existence of a set of symmetric and antisymmetric filters with shorter length. To formalize the above symmetric extension method, (26) must be modified. Let the overlapping factor be as shown in the and second expression at the bottom of the page, where denote even positive and odd positive integers, respectively. We only consider the above for simplicity from now on. When and are in reciprocal order, the appropriate permutation matrix makes the above assumption valid. The symmetric extension method for this class can be written as
3373
extended, inverse transformed, and then truncated. This inverse transform can be written as follows:
..
(28) .
where matrices and represent windowing operation and extension of the transformed coefficients, respectively. The above as equation can be rewritten using the forward transform (29) where
is a following diagonal matrix diag
..
(30) .
In the following subsections, the size-limited structures for GULLOTs are shown, based on the above symmetric extension methods. (27)
is a matrix whose rows consist of where longer antisymmetric ones. all symmetric bases and is an matrix that contains The matrix shorter symmetric bases. The matrix is a permutation matrix that shifts the last samples to the first block. To reconstruct the , input signal, transformed coefficients are permuted by
B. Size-Limited Structure for Type A GULLOT Now, we define the size matrix and the square matrix
..
of size
.
(HS) (HA) (WS) (WA)
for Type C
for Type D
3374
IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 48, NO. 12, DECEMBER 2000
TABLE V COMPARISON OF CODING GAIN (dB) AND FLOPS
(35)
where
is
Then, (31) can be rewritten as
.. The matrix
relates
to
. (36)
as
Consequently, the size-limited structure can be written as (32). The structure is illustrated in Fig. 4(a). Fig. 4(b) shows the structure of each block . From the figure, it can be seen that the is further simplified as Fig. 4(c). C. Size-Limited Structure for Type B GULLOT By using the above matrices, one can verify that the matrix in (26) can be expressed as (31)
The only difference between the size-limited structure for Type A and that for Type B is the first block . Now, let us matrices and define the matrix (37)
The above structure, however, is not a size-limited one because the expanded samples must be processed. Hence, the problem using a here is to find the way to express the above matrix matrices s such that cascade of
(38)
(32) .. ..
.
(39)
(33)
.
The transform matrix and are matrices. In other words, an where and guarantees the equivalence appropriate choice of between (31) and (32). Let us define the matrix
can be written as (40)
The size-limited structure for Type B GULLOT is illustrated has the same structure as the one in in Fig. 5. Each block Fig. 4(c). D. Size-Limited Structure for Type C GULLOT
We found that if the matrices
and
are chosen as
(34)
in In this case, we must consider the transform matrix . Using similar principles, we can extend the (27) instead of size-limited structure for the Type A GULLOT in (36) to this class. Although the whole structure of the Type C GULLOT is equal to that of Type A, the details of are different from each other. occurs at some This is because the situation of the Type C GULLOT. Moreover, the last block stage must contain the permutation matrix . Each block for
NAGAI et al.: GENERALIZED UNEQUAL LENGTH LAPPED ORTHOGONAL TRANSFORM
Fig. 9.
3375
Plots of PSNR for variable bit rates. (a) Lena image. (b) Barbara image.
Type C GULLOT is presented in Fig. 6. For the sake of brevity, the derivations are omitted; however, the structure gives good agreement with the one that is obtained by intuition. It is worth in Fig. 6 is reduced to the one in Fig. 4(c) when noting that . E. Size-Limited Structure for Type D GULLOT holds true for every , it is trivial task to derive When the size-limited structure for this case, that is, the combination of the above results resolve the problem. The whole structure for this class is the same as the one in Fig. 5, and a single block coincides with the one in Fig. 6. V. EXAMPLES A. Design Strategy There are some criteria for the design of LPPUFBs (GenLOTs). In general, the coding gain is used for the image coding application. Since the numerator of (5) is constant, we minimize the denominator to maximize the coding gain. However, this direct optimization will never give a good solution. Hence, we first by minmaximize the stopband attenuation of the filters imizing the following cost function:
The solution of the above optimization is used as the initial value for maximizing the coding gain. is chosen. Taking account of the fast implementation, If the first block is the DCT, the choice also guarantees the GULLOT to have no DC leakage. This property is very important in image coding applications since a checkerboard effect is determined by reduced angle set (4) or can be avoided. plane rotations. full angle set, i.e., cascade of B. Design Examples GULLOTs were designed. Several eight-channel We will present following examples: • GULA (type A): ;
• GULB (type B): ; • GULC (type C): ; • GULD (type D): . The frequency responses of the designed GULLOTs (reduced angle set was used) are shown in Fig. 7. From these figures, it can be seen that each basis function has a reasonable frequency selectivity. Thus, one can confirm the validity of the design strategy we described above. The impulse responses and the coefficients of all GULLOTs used as examples are also shown in Fig. 8 and Tables I–IV. (The tables present only half of the coefficients because the bases have symmetry.) One can easily confirm the unequal length and linear phase properties from the figures. with The comparison of coding gain for AR and the number of floating-point operations (flops) required for transforming a single block are given in Table V. The coding gain and flops of eight-point DCT (DCT8), GenLOT with length 48 (GLOT48), GenLOT with length 40 (GLOT40), GenLOT with length 32 (GLOT32), and GenLOT with length 24 (GLOT24) are also shown for purposes of comparison. It can be seen that the GULLOT can achieve comparable coding gain with that of the GenLOT with less computational complexity. For example, GULB and GLOT48 have comparable coding gain, even though GULB requires 172 flops, whereas GLOT48 consumes 212 flops. C. Image Coding Examples This subsection presents some actual image coding examples. The four GULLOT’s shown in Fig. 7 are used to transform images. Eight-channel GLOT24, GLOT40, and GLOT48 are used as well for comparison. For all cases, the same coder is used, which consists of an optimal bit allocator, a uniform scalar quantizer, and a runlength-Huffman coder [2]. Fig. 9 denotes the difference in PSNR between the GULLOTs or GenLOTs and the pels) and “Barbara” ( DCT for “Lena” ( pels), respectively. From these figures, one can see that GULB performs almost the same as GLOT48, in spite of the lower computational complexity. The PSNRs of the GULD are comparable with those of GLOT40.
3376
IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 48, NO. 12, DECEMBER 2000
Fig. 10. Image coding examples. (a) Original Yogi image. (b) Coded at 0.3 b/pixel using GULB (reduced). PSNR is 26.29 (dB). (c) Coded at 0.3 b/pixel using GLOT48. PSNR is 26.06 (dB).
0.3 b/pixel. In Fig. 10(b), GULB is used to transform the image, while the GLOT48 is used in Fig. 10(c). Due to the short bases of high frequency bands, the ringing artifacts become less visible when the GULB is used to transform the image. VI. CONCLUSION
Fig. 11. Structures of the left- and right-hand sides of (16).
To demonstrate the ability of the GULLOT, the “Yogi” image, which contains strong edges, is tested on the coder. The results are given in Fig. 10. These are the original and coded images at
The generalized unequal length lapped orthogonal transform, which we call GULLOT, was described in this paper. The linear phase and the unequal length properties are structurally imposed on the GULLOT. We show that the fast algorithm for the DCT and reduced angle set facilitate the transform. Our proposed GULLOTs can be considered to be a generalization of the GenLOT and expands the designer’s choice considerably. The implementation of the GULLOTs over finite-length signals is
NAGAI et al.: GENERALIZED UNEQUAL LENGTH LAPPED ORTHOGONAL TRANSFORM
also investigated to apply them to the subband image coding. We derived the size-limited structures based on the symmetric extension method. In this case, the fast algorithm is also involved. Finally, the design examples and the results of image coding application show the validity of the GULLOT. The best length selection of the GULLOT is left for the future research.
[10] [11] [12] [13]
APPENDIX Proof of (16): We show the structure of the left-hand side of (16) and its equivalent one in Fig. 11(a). Fig. 11(b) denotes the structure of the right-hand side of (16) and its equivalent one. From these figures, one can see that the following must be proven:
[14]
[15]
3377
M
, “On -channel linear phase FIR filter banks and application in image compression,” IEEE Trans. Signal Processong, vol. 45, pp. 2175–2187, Sept. 1997. H. Kiya, K. Nishikawa, and M. Iwahashi, “A development of symmetric extension method for subband image coding,” IEEE Trans. Image Processing, vol. 3, pp. 78–81, Jan. 1994. R. H. Bamberger, S. L. Eddins, and V. Nuri, “Generalized symmetric extension method for size-limited multirate filter banks,” IEEE Trans. Image Processing, vol. 3, pp. 82–87, Jan. 1994. L. Chen, T. Q. Nguyen, and K.-P. Chan, “Symmetric extension methods for -channel linear-phase perfect-reconstruction filter banks,” IEEE Trans. Signal Processing, vol. 43, pp. 2505–2511, Nov. 1995. S. Muramatsu and H. Kiya, “An efficient structure of GenLOT for finiteduration sequences and its application to M-band discrete-time wavelet transforms,” Trans. IEICE, vol. J79-A, pp. 1966–1976, Dec. 1996. (in Japanese). T. Nagai and M. Ikehara, “Fast LOT with unequal length basis functions: Realization and application in subband image coding,” IEICE Trans. Fundamentals, vol. E82-A, pp. 825–834, May 1999.
M
(41) where all matrices have size of following equations:
. To prove this, we use the
(42) (43) (44) (45) Using the above relationships, we obtain the following trivial equality after a few manipulations: (46) which shows that (16) holds. ACKNOWLEDGMENT The authors would like to thank the anonymous reviewers for their valuable comments on the manuscript. REFERENCES [1] P. P. Vaidyanathan, Multirate Systems and Filter Banks. Englewood Cliffs, NJ: Prentice-Hall, 1993. [2] G. Strang and T. Q. Nguyen, Wavelets and Filter Banks. Wellesley, MA: Wellesley-Cambridge, 1996. [3] M. Vetterli and J. Kovacevic, Wavelets and Subband Coding. Englewood Cliffs, NJ: Prentice-Hall, 1995. [4] A. K. Soman, P. P. Vaidyanathan, and T. Q. Nguyen, “Linear phase paraunitary filter banks: Theory, factorization and designs,” IEEE Trans. Signal Processing, vol. 41, pp. 3480–3496, Dec. 1993. [5] H. S. Malvar, Signal Processing with Lapped Transforms. Norwell, MA: Artech House, 1992. [6] H. S. Malvar and D. H. Staelin, “The LOT: Transform coding without blocking effects,” IEEE Trans. Acoust. Speech, Signal Processing, vol. 37, pp. 553–559, Apr. 1989. [7] H. S. Malvar, “Lapped transform for efficient transform/subband coding,” IEEE Trans. Acoust. Speech, Signal Processing, vol. 38, pp. 969–978, June 1990. [8] R. L. de Queiroz, T. Q. Nguyen, and K. R. Rao, “The GenLOT: Generalized linear-phase lapped orthogonal transform,” IEEE Trans. Signal Processing, vol. 44, pp. 497–607, Mar. 1996. [9] T. D. Tran and T. Q. Nguyen, “Generalized lapped orthogonal transform with unequal-length basis functions,” in Proc. IEEE Int. Symp. Circuits Syst., Hong Kong, June 1997, pp. 1385–1388.
Takayuki Nagai (M’98) received the B.E., M.E., and Dr.Eng. degrees from the Department of Electrical Engineering, Keio University, Yokohama, Japan, in 1993, 1995, and 1997, respectively. From October 1997 to March 1998, he was a Visiting Researcher with the Department of Electrical Engineering, Keio University. Since 1998, he has been with the University of Electro-Communications, Tokyo, Japan, where he is currently a Research Associate with the Course in Electronic Engineering. His research interests include digital signal processing and multirate systems. He is a member the Institute of Electronics, Information and Communication Engineers and the Acoustical Society of Japan.
Masaaki Ikehara (M’92) received the B.E., M.E., and Dr.Eng. degrees in electrical engineering from Keio University, Yokohama, Japan, in 1984, 1986, and 1989, respectively. He was appointed Lecturer at Nagasaki University, Nagasaki, Japan, from 1989 to 1992. In 1992, he joined the Faculty of Engineering, Keio University. From 1996 to 1998, he was a Visiting Researcher at the University of Wisconsin, Madison, and Boston University, Boston, MA. He is currently an Associate Professor with the Department of Electronics and Electrical Engineering, Keio University. His research interests are in the areas of multirate signal processing, wavelet image coding, and filter design problems.
Masahide Kaneko was born in Yokohama, Japan, in 1953. He received the B.Eng. degree in electronic engineering, the M.Eng. degree in electrical engineering, and the Dr.Eng. degree in electronic engineering from the University of Tokyo, Tokyo, Japan, in 1976, 1978, and 1981, respectively. From April 1981 to March 1994, he was with the Research and Development Laboratories of Kokusai Denshin Denwa Co., Ltd. (KDD). From April 1994 to March 1997, he was an Associate Professor with the Department of Information and Communication Engineering, the University of Tokyo. In April 1997, he was reinstated to the Research and Development Laboratories of KDD. In April 1998, he joined the University of Electro-Communications, Tokyo, as an Associate Professor with the Course in Electronic Engineering. His research interests include low bit-rate video coding, model-based image coding, processing of facial image information, handling of 3-D visual information, and intelligent human interface. Dr. Kaneko is a member of the IEEE Computer Society, the Institute of Electronics, Information, and Communication Engineers, the Institute of Image Information and Television Engineers, the Information Processing Society of Japan, and the Japan Academy of Facial Studies.
3378
IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 48, NO. 12, DECEMBER 2000
Akira Kurematsu (SM’97) received the B.E. degree in electrical communication engineering from Waseda University, Tokyo, Japan, in 1961. He received Ph.D. degree from Waseda University in 1971. In 1961, he joined the Research and Development Laboratories of KDD. He was engaged in research on pattern recognition, speech signal processing, and communication terminal systems. In 1983, he was appointed Deputy Director of KDD R&D labs. From 1986 to 1993, he was the President of ATR Interpreting Telephony Research Laboratories. Since 1993, he has been a Professor with the Department of Electronic Engineering, University of Electro-Communications, Tokyo. He has authored many invited papers, journal and conference papers, and five books in his fields of research. Dr. Kurematsu was a chairman of Tokyo chapter of the IEEE Signal Processing Society from 1997 to 1998. He is a member of the Institute of Electronics, Information, and Communication Engineers, the Information Processing Society of Japan, the Acoustical Society of Japan, and the Japanese Society for Artificial Intelligence.
