Font Size: a A A

Theories And Two-dimension Based Algorithms For The Optimal Designs Of Two-dimensional FIR Digital Filters

Posted on:2013-01-29Degree:DoctorType:Dissertation
Country:ChinaCandidate:R J ZhaoFull Text:PDF
GTID:1118330374980705Subject:Signal and Information Processing
Abstract/Summary:PDF Full Text Request
As typical multi-dimensional digital systems, two-dimensional (2-D) digital filters have been widely applied in image processing, sonar and radar signal processing, geophysical signal processing and so on. Efficient design algorithms that are capable to fastly and accurately design various, especially high-order,2-D digital filters are becoming more and more important for the multi-dimensional digital signal processing due to the rapid increase of the amount of data processed by modern electronic equipments. Unlike the optimal design of one-dimensional (1-D) filters which is in fact a univariate function approximation problem, the design of2-D filters is essentially a bivariate function approximation problem. As a result, many efficient design algorithms for1-D filters cannot be extended to the2-D filter design problem due to the fact that the approximation theory of bivariate function is not as complete as that of univariate function. Though several algorithms can be extended to the design2-D filters, there are some inevitable numerical problems in these algorithms because of large amount of data required to be processed in the2-D case. The facts mentioned above make the design of2-D filters much more difficult than its1-D counterpart.High computational complexity is the major difficulty encountered in the optimal design of2-D filters. Recently, a number of researchers proposed some two-dimension (2-D) based optimization algorithms for the2-D filters design. Unlike the conventional methods that rearrange the2-D filter coefficients into a vector, those2-D based algorithms deal with the filter coefficients in their nature matrix form, leading to a relatively high efficiency and a great saving of the memory space. However, the shortcomings of the existing2-D based algorithms have limited their applications. Nevertheless, high efficiency of those2-D based algorithms indicates that how to exploit the matrix form of the coefficients of2-D filters will be the key for developing efficient2-D filter design algorithms. In this dissertation, the efficient2-D based algorithms are investigated aiming to design linear-phase2-D FIR filters more efficiently and accurately. Firstly,2-D linear-phase FIR filters are classifed into three categories:the complex2-D linear-phase FIR filter, the centro-(anti)symmetric2-D FIR filter and the quadrantally (anti)symmetric2-D FIR filter. It should be pointed out that the quadrantally (anti)symmetric2-D FIR filter is a special case of the centro-(anti)symmetric2-D FIR filter, and the centro-(anti)symmetric2-D FIR filter is a special case of the complex2-D linear-phase FIR filter. In order to describe the proposed algorithms more clearly, the magnitude responses are expressed as functions of coefficient matrices of the filters and the phase responses are derived for the three categories of filters, respectively. Furthermore, the relations btween the coefficient matrices and the impulse response of the filters are also given.In the design of2-D filters, weighted least squares (WLS) criterion has been widely used due to its simplicity and relatively perfect design results. Moreover, many of filter design problems, such as the Minimax design, the least lp norm design, the constrained filters design and so on, can be solved by transforming the original design problem into a sequence of WLS design subproblems. Thus, the fast and numerically stable WLS algorithms for the design of2-D filters are of considerable important for further investigation of2-D filter design. In this dissertation, the WLS design problem of quadrantally (anti)symmetric2-D FIR filters is studied firstly. The optimality condition of such problem is obtained and expressed as a matrix equation. On the basis of the optimality condition, a matrix iterative algorithm and a matrix diagonalization based algorithm are proposed for the WLS design with four-valued weighting function. The convergence of the matrix iterative algorithm is established, while the solution obtained by the matrix diagonalization based algorithm is just the limite solution of the matrix iterative algorithm. Both of the algorithms are extremely computationally accurate, and at the same time, their computational efficiencies are very high and even comparable to that of unweighted least squares method. Consequently, the matrix diagonalization based algorithm is combined with the iterative reweighted least squares (IRLS) technique, resulting in a2-D based IRLS algorithm for four-valued weighting design. The2-D based IRLS algorithm can reduce the maximal magnitude error by iteratively adjusting the weights in different frequency bands, and is computationally very efficient as well. Next, the WLS design problem with arbitrary weighting function is considered. Again according to the optimality condition, three matrix iterative algorithms:matrix iterative algorithm â… , â…¡, and â…¢, and a generalized conjugate gradient algorithm are presented. Among the three matrix iterative algorithms, the first one is the basic algorithm, and the other two are modified versions of the first. The convergences of the matrix iterative algorithm I, II are established by using linear operator theory, but the matrix iterative algorihtm III may fail to converge in some special situations. Generally speaking, the three matrix iterative algorithms have similar efficiencies for designing low-order filters, and the algorithm II and III converge more fast than the algorithm I for high-order cases. Using matrices as the variables, the generalized conjugate gradient algorithm is a generalization of the conventional conjugate gradient algorithm in Hilbert inner space by the way that the conjugacy in the conventional algorithm is replaced by the orthogonality under inner product defined on the Hilbert space. It is proved that the generalized conjugate gradient algorithm can converge in a finite number of steps by using the inner theory of Hilbert space. Generally, the generalied gradient conjugate algorithm is more efficient than the three matrix iterative algorithms. All those proposed algorithms have their respective characteristics and are analyzed and compared with existing algorihtms in detail along with the analyses of computational complexity through design examples. Simulation results show that those proposed algorithms provide significant impovements in terms of the design time, design accuracy and numerical stability compared to existing methods.In the sequel, the WLS design of centro-(anti)symmetric2-D FIR filters with arbitrary weighting function is researched. The mathematical model of such optimization design problem is formulated with an objective function including two matrix variables, and by differentiating the objective function and setting the result to zero, the optimality condition is obtained, which is composed of two matrix equations in two matrix variables. On the basis of this optimality condition, the matrix iterative algorithms I and II are extended to the centro-(anti)symmetric filters design problem. Moreover, the convergences of these extended algorithms are proved by using the linear operator theory. Further, a porper inner product is defined on the Cartesian product space of two matrix spaces, thus the generalized conjugate gradient algorithm is extended to the centro-(anti)symmetric filters design problem and is proved by using the inner theory of Hilbert space that it can converge in a finite number of steps. Design examples illustrate that these extended algorithms are very efficent and far superior to existing algorithms.In the following, the WLS design of complex2-D linear-phase FIR filters with arbitrary weighting function is studied. The objective function of this design problem is a matrix function of the four independent matrix variables. Thus, the obtained optimality condition consists of four matrix equations with respcet to four matrix variables. By defining a proper inner product on the Cartesian product space of four matrix spaces, the generalized conjugate gradient algorithm is extended for the WLS design of complex2-D linear-phase filters. Similarly, the convergence of the extended algorithm is proved by using the inner theory of Hilbert space. Simulation results demonstrate the good performance of the proposed algorithm in designing complex2-D linear-phase filters.Finally, the least lp norm design of2-D linear-phase FIR filters is discussed, which can effectively eliminate the Gibbs'phenomenon appearing in the least squares design and can be used to approximate the Minimax design. Another2-D based IRLS algorithm with arbitrary weighted WLS technique as its iteration core is developed for designing2-D linear-phase filters in the least lp norm sense, including the quadrantally (anti)symmetric filter, the centro-(anti)symmetric filter and the complex2-D linear-phase filter. The new2-D based IRLS algorithm efficiently combines the genearalized conjugate gradient algorithm proposed in this dissertation with the conventional IRLS algorithm, as a result, it is especially well-suited for the least lp norm design of2-D FIR filters. In addition, high efficiency of the generalized conjugate gradient algorithm guarantees that the proposed IRLS algorithm can fast converge to the optimal filter, which fact has also been established by simulation results.All of the algorithms proposed in this dissertation take advantage of the matrix forms of the2-D filter coefficients and the sampling frequencies, thereby are2-D based algorithms. Analyses of those algorithms along with large numbers of design examples indicate that they are computationally higher efficient, need smaller memory space compared with existing methods and can very efficiently design various, even high-order,2-D linear-phase filters in the WLS sense and the least lp norm sense.
Keywords/Search Tags:linear-phase, two-dimensional FIR filter, two-dimensional algorithm, weightedleast squares design, least l_p norm design
PDF Full Text Request
Related items