Realization of 2-D linear-phase FIR filters by using thesingular-value decomposition

The singular-value decomposition (SVD) technique is investigated for the realization of a general two-dimensional (2-D) linear-phase FIR filter with an arbitrary magnitude response. A parallel realization structure consisting of a number of one-dimensional (1-D) FIR subfilters is obtained by applying the SVD to the impulse response of a 2-D filter. It is shown that by using the symmetry property of the 2-D impulse response and by developing an appropriate unitary transformation, an SVD yielding linear-phase constituent 1-D filters can always be obtained so that the efficient structures of the 1-D linear-phase filters can be exploited for 2-D realization. It is shown that when the 2-D filter to be realized has some specified symmetry in its magnitude response, the proposed SVD realization would yield a magnitude characteristic with the same symmetry. An analysis is carried out to obtain tight upper bounds for the errors in the impulse response as well as in the frequency response of the realized filter. It is shown that the number of parallel sections can be reduced significantly without introducing large errors, even in the case of 2-D filters with nonsymmetric magnitude response     

Symmetry Study for Delta- Operator-Based 2-D Digital Filters

The complexity in the design and implementation of two-dimensional (2-D) filters can be considerably reduced if we utilize the symmetries that might be present in the frequency response of these filters. As the delta-operator formulation of digital filters offers better numerical accuracy and lower coefficient sensitivity in narrowband filter designs when compared to the traditional shift-operator formulation, it is desirable to have efficient design and implementation techniques in$gamma$-domain which utilize the various symmetries in filter specifications. With this motivation, we comprehensively establish the theory of constraints for delta-operator formulated discrete-time real-coefficient polynomials and functions, arising out of the many types of symmetries in their magnitude responses. We also show that as sampling time tends to zero, the$gamma$-domain symmetry constraints merge with those of$s$-domain symmetry constraints. We then present a least square error criterion based procedure to design 2-D digital filters in$gamma$-domain that utilizes the symmetry properties of the magnitude specification. A design example is provided to illustrate the savings in computational complexity resulting from the use of the$gamma$-domain symmetry constraints.     

A singular value decomposition derivation in the discrete frequencydomain of optimal noncentro-symmetric 2-D FIR filters

A new derivation is presented for the least squares solution of the design problem of two-dimensional (2-D) finite impulse response (FIR) filters by minimizing the Frobenius norm of the difference between the matrices of the ideal and actual frequency responses sampled at the points of a frequency grid. The mathematical approach is based on the singular value decomposition (SVD) of two complex transformation matrices. Interestingly, the designed filter is proved to be zero-phase if the ideal filter is so without assuming any kind of symmetry     

Generating 2-D FIR filter functions by Christoffel–Darboux formula for Chebyshev polynomials of the second kind

Global Christoffel–Darboux formula for different polynomials has already been used for the filter design. Here, this formula for orthonormal Chebyshev polynomials of the second kind and for two independent variables is applied in generating novel class linear-phase two-dimensional (2-D) finite impulse response (FIR) digital filter functions. In this way, 2-D filters with some specific features including economy, phase linearity, symmetry and selectivity are designed. Representative examples of the 2-D FIR digital filters of a new class obtained by the proposed approximation technique are given. A filter generated by the proposed approach is compared with the corresponding one generated by the procedure from literature.     

General formulation of shift and delta operator based 2-D VLSI filter structures without global broadcast and incorporation of the symmetry

Having local data communication (without global broadcast of signals) among the elements is important in very large scale integration (VLSI) designs. Recently, 2-D systolic digital filter architectures were presented which eliminated the global broadcast of the input and output signals. In this paper a generalized formulation is presented that allows the derivation of various new 2-D VLSI filter structures, without global broadcast, using different 1-D filter sub-blocks and different interconnecting frameworks. The 1-D sub-blocks in z-domain are represented by general digital two-pair networks which consist of direct-form or lattice-type FIR filters in one of the frequency variables. Then, by applying the sub-blocks in various frameworks, 2-D structures realizing different transfer functions are easily obtained. As delta discrete-time operator based 1-D and 2-D digital filters (in \(\gamma \) -domain) were shown to offer better numerical accuracy and lower coefficient sensitivity in narrow-band filter designs when compared to the traditional shift-operator formulation we have covered both the conventional z-domain filters as well as delta discrete-time operator based filters. Structures realizing general 2-D IIR (both z- and \(\gamma \) -domains) and FIR transfer functions (z-domain only) are presented. As symmetry in the frequency response reduces the complexity of the design, IIR transfer functions with separable denominators, and transfer functions with quadrantal magnitude symmetry are also presented. The separable denominator frameworks are needed for quadrantal symmetry structures to guarantee BIBO stability and thus presented for both the operators. Some limitations of having exact symmetry with separable 1-D denominator factors are also discussed.     

Unified theory of symmetry for two-dimensional complex polynomials using delta discrete-time operator

The complexity in the design and implementation of 2-D filters can be reduced considerably if the symmetries that might be present in the frequency responses of these filters are utilized. As the delta operator (??-domain) formulation of digital filters offers better numerical accuracy and lower coefficient sensitivity in narrow-band filter designs when compared to the traditional shift-operator formulation, it is desirable to have efficient design and implementation techniques in ??-domain which utilize the various symmetries in the filter specifications. Furthermore, with the delta operator formulation, the discrete-time systems and results converge to their continuous-time counterparts as the sampling periods tend to zero. So a unifying theory can be established for both discrete- and continuous-time systems using the delta operator approach. With these motivations, we comprehensively establish the unifying symmetry theory for delta-operator formulated discrete-time complex-coefficient 2-D polynomials and functions, arising out of the many types of symmetries in their magnitude responses. The derived symmetry results merge with the s-domain results when the sampling periods tend to zero, and are more general than the real-coefficient results presented earlier. An example is provided to illustrate the use of the symmetry constraints in the design of a 2-D IIR filter with complex coefficients. For the narrow-band filter in the example, it can be seen that the ??-domain transfer function possesses better sensitivity to coefficient rounding than the z-domain counterpart.     

Frequency grid density for the design of 2-D FIR filters

In the design of a digital 2-D FIR filter, the frequency response is often optimised to satisfy a given set of specifications on a dense grid of frequency points. The accuracy of a filter design improves when there are more grid points, but this is at the expense of higher computational resources. The authors present the relationship between the accuracy and the frequency grid density in 2-D filter designs. A new formula for determining the frequency grid spacing is also proposed     

A novel nonnegative decomposition method and its application to 2-D digital filter design

In designing two-dimensional (2-D) digital filters in the frequency domain, an efficient technique is to first decompose the given 2-D frequency domain design specifications into one-dimensional (1-D) ones, and then approximate the resulting 1-D magnitude specifications using the well-developed 1-D filter design techniques. Finally, by interconnecting the designed 1-D filters one can obtain a 2-D digital filter. However, since the magnitude responses of digital filters must be nonnegative, it is required that the decomposition of 2-D magnitude specifications result in nonnegative 1-D magnitude specifications. We call such a decomposition the nonnegative decomposition. This paper proposes a nonnegative decomposition method for decomposing the given 2-D magnitude specifications into 1-D ones, and then transforms the problem of designing a 2-D digital filter into that of designing 1-D filters. Consequently, the original problem of designing a 2-D filter is significantly simplified.     

Equiripple stopband characteristic for circularly symmetric 2-D recursive filters

A circularly symmetric 2-D recursive digital filter whose magnitude-squared response approximates a Gaussian function in the two frequency variables has a separable transfer function. Such a circularly symmetric filter has a monotonic frequency response. One may, therefore, want to sharpen the response in the transition band. Due to the separability feature, it is shown how to obtain an equiripple characteristic in the stopband without affecting the circular symmetry in the passband. This reduces the transition bandwidth.     

Optimal McClellan transformation and its application to 2-D FIR digial filter design

A new method to choose the coefficients of the McClellan transformation is developed. The coefficients are obtained by using both analytic and nonlinear optimization approaches. The transformation using the proposed method has much better approximation performance for circular symmetry than the existing methods, especially when the cutoff frequency of the 2-D filter is very large. The proposed method also applies to choose the transformation coefficients to approximate elliptic contours. Two design examples of 2-D FIR digital filters demonstrate the good performance of the proposed method.     

Efficient 2-D based algorithms for WLS designs of 2-D FIR filters with arbitrary weighting functions

The impulse response coefficients of a two-dimensional (2-D) finite impulse response (FIR) filter naturally constitute a matrix. It has been shown by several researchers that, two-dimension (2-D) based algorithms that retain the natural matrix form of the 2-D filter’s coefficients are computationally much more efficient than the conventional one-dimension (1-D) based algorithms that rearrange the coefficient matrix into a vector. In this paper, two 2-D based algorithms are presented for the weighted least squares (WLS) design of quadrantally symmetric 2-D FIR filters with arbitrary weighting functions. Both algorithms are based on matrix iterative techniques with guaranteed convergence, and they solve the WLS design problems accurately and efficiently. The convergence rate, solution accuracy and design time of these proposed algorithms are demonstrated and compared with existing algorithms through two design examples.     

Design of 2-D Linear Phase Digital Filters Using Schur Decomposition and Symmetries

In this paper we present a new and numerically efficient technique for designing 2-D linear phase octagonally symmetric digital filters using Schur decomposition method (SDM) and the diagonal symmetry of the 2-D impulse response specifications. This technique is based on two steps. First, the 2-D impulse response matrix is decomposed into a parallel realization of k sections, each comprising two cascaded linear phase SISO 1-D FIR digital filters. It is shown that using the symmetry property of the 2-D impulse response matrix and the fact that the left and right eigenspaces obtained by SDM are transpose of each other, the design problem of two 1-D digital filters is reduced to the design problem of only one 1-D digital filter in each section.     

Weighted least mean square design of 2-D FIR digital filters: thegeneral case

This paper solves the weighted least mean square (WLMS) design of two-dimensional (2-D) finite impulse response (FIR) filters with general half plane symmetric frequency responses and nonnegative weighting functions. The optimal solution is characterized by a pair of coupled integral equations, and the existence and uniqueness of the WLMS solution for 2-D FIR filter design are established. Two efficient numerical algorithms using a 2-D fast Fourier transform (FFT) are proposed to solve the WLMS solution. One is based on the contraction mapping and fix point theorem characterizing the coupled integral equation; the other uses conjugate gradient techniques, which guarantees finite convergence. The associated computational complexity is analyzed and compared with existing algorithms. Examples are used to illustrate the effectiveness of the proposed design algorithms. The selection of weighting functions to improve the minimax performance of the filter is also discussed     

Closed-form design and efficient implementation of variable digital filters with simultaneously tunable magnitude and fractional delay

This paper proposes a closed-form solution for designing variable one-dimensional (1-D) finite-impulse-response (FIR) digital filters with simultaneously tunable magnitude and tunable fractional phase-delay responses. First, each coefficient of a variable FIR filter is expressed as a two-dimensional (2-D) polynomial of a pair of parameters called spectral parameters; one is for independently tuning the cutoff frequency of the magnitude response, and the other is for independently tuning fractional phase-delay. Then, the closed-form error function between the desired and actual variable frequency responses is derived without discretizing any design parameters such as the frequency and the two spectral parameters. Finally, the optimal solution for the 2-D polynomial coefficients can be easily determined through minimizing the closed-form error function. We also show that the resulting variable FIR filter can be efficiently implemented by generalizing Farrow structure to our two-parameter case. The generalized Farrow structure requires only a small number of multiplications and additions for obtaining any new frequency characteristic, which is particularly suitable for high-speed tuning.     

A Mapping-Based Design for Nonsubsampled Hourglass Filter Banks in Arbitrary Dimensions

Multidimensional hourglass filter banks decompose the frequency spectrum of input signals into hourglass-shaped directional subbands, each aligned with one of the frequency axes. The directionality of the spectral partitioning makes these filter banks useful in separating the directional information in multidimensional signals. Despite the existence of various design techniques proposed for the 2-D case, to our best knowledge, the design of hourglass filter banks in 3-D and higher dimensions with finite impulse response (FIR) filters and perfect reconstruction has not been previously reported. In this paper, we propose a novel mapping-based design for the hourglass filter banks in arbitrary dimensions, featuring perfect reconstruction, FIR filters, efficient implementation using lifting/ladder structures, and a near-tight frame construction. The effectiveness of the proposed mapping- based design depends on the study of a set of conditions on the frequency supports of the mapping kernels. These conditions ensure that we can still get good frequency responses when the component filters used are nonideal. Among all feasible choices, we then propose an optimal specification for the mapping kernels, which leads to the simplest passband shapes and involves the fewest number of frequency variables. Finally, we illustrate the proposed techniques by a design example in 3-D, and an application in video denoising.     

Two-dimensional perfect reconstruction FIR filter banks withtriangular supports

We present a theory and design of two-dimensional (2-D) perfect reconstruction (PR) filter banks (FBs) (PRFBs) in which the supports of the analysis and synthesis filters consist of two triangulars. The two-triangular FB can be realized by designing an appropriate 2-D complex prototype whose passband support is a triangle that is a half of a parallelepiped-shaped passband support defined by the sampling matrix. Then a complex prototype filter is modulated by the DFT, and each analysis filter is derived by taking the real part of the modulated output. We show that the two-triangular FB satisfies the condition of permissibility. A necessary and sufficient condition for 2-D PRFBs is derived. Moreover, we present a design method of the 2-D PRFB that minimizes the cost function consisting of the frequency constraint and PR condition. Finally, a design example is presented to confirm the validity of the proposed method     

Adaptive McClellan transformations for quincunx filter banks

A technique is developed for the design of 2-D nonseparable two-channel filter banks for a quincunx sampling lattice, where the isopotentials of the frequency response can be optimized and adapted to the input signal's statistics. By employing known odd-length symmetric linear phase filter banks as the l-D prototype filters for 2-D filters parameterized by the McClellan transformation, conditions are derived such that the resulting 2-D two-channel filter bank retains the perfect-reconstruction or aliasing-free properties of the 1-D prototype two-channel filter bank. A particular two-parameter transformation function is developed that has sufficient flexibility to adapt its orientation in any direction and whose optimization involves a simple constrained least-squares problem in which the feasible set lies within a circle. The results have practical applications in many areas of image and video processing where multirate filter banks are used     

Decomposition of FIR digital filters for realization via thecascade connection of subfilters

A method is presented for decomposing even-order linear-phase FIR filters with distinct roots into the cascade connection of second-and fourth-order subfilters. The technique consists of of finding roots of the z-domain filter transfer function by searching a finite region in the complex z plane. Due to symmetry in the impulse response, only the perimeter (the real axis and boundary) and interior of the upper half of the unit circle need to be searched for real and complex values of roots from which the impulse response coefficients of the corresponding subfilters can be directly determined. The root-finding algorithm tests for existence of a root at each interval in a finite grid and then utilizes the Newton-Raphson method to refine the final estimate of each root value. In the two-dimensional (2-D) search, the Cauchy-Riemann relations are exploited to reduce computations and speed convergence. This method has been tested on FIR filters with orders ranging to over 120 and has proven effective in decomposing filters to the cascade realization with identical frequency response characteristics. An example is presented that illustrates the use of this technique     

Programmable 2D linear filter for video applications

A fully integrated 2-D linear filter including a line buffer for a 7×7 kernel is presented. To run the filter in real time at video clock frequencies, an array of pipelined carry-save adders was used as a very fast arithmetic unit. The filter chip contains 292451 transistors on a silicon area of 135 mm². The maximum clock frequency under worst-case conditions for technology and temperature was simulated to be 20 MHz. The main blocks are designed as independent parameterizable modules. The line buffer and the arithmetic unit are available as macros in a standard cell library for semicustom design. With these macros a semicustom chip for image enhancement in a X-ray system was produced. This chip works with a system frequency of 13 MHz. The line buffer module is used in another full-custom image processing chip-a two-dimensional rank order filter with a kernel size of also 7×7. This chip contains more than 300000 transistors on a silicon area of 103 mm². In this case the module containing the 1-D FIR (finite impulse response) filters is replaced by additional pixel delays and a sorter module. Simulations have shown that the chip could work with clock frequencies up to 20 MHz     

Two-dimensional FIR compaction filter design

The design of signal-adapted multirate filter banks has been an area of research interest. The authors present the design of a 2-D finite impulse response (FIR) compaction filter followed by a 2-D FIR filter bank that packs the maximum energy of the input process into a few subbands. The energy compaction property of the 2-D compaction filter is extremely good for higher filter orders and converges to the ideal optimal solution as the order tends to infinity. The design procedure is very straightforward and involves a 2-D spectral factorisation