Theories And Algorithms For Fast Designs Of Two-dimensional Constrained FIR Filters

With the rapid development of computer technology in storage capabilities and speed, two-dimensionl (2-D) digital filter has found more and more applications in areas such as medical image processing, satellite image processing, and radar and sonar signal processing, and the design problem of it has received considerable attention by many scholars at home and abroad.2-D digital filter can be classified into 2-D finite impulse response (FIR) fiter and infinite impulse response (IIR) filter. FIR filters are often preferable to IIR ones since they are inherently stable and can be designed easily to have exact linear phase responses.High computation complexity is the major difficult in the design of 2-D fiters. The impluse coefficients of 2-D digital filter are naturally arranged in matrices, which are different from that in one dimensional (1-D) filter, thus the design of 2-D fiter is actually the approximaton problem of bivariate funciton. Incompleteness of the approximation theory of bivariate funciton leads to the complexity of design problem. Conventional design methods for optimal designs of 2-D FIR filters rearrange the coefficient matrices into vectors and then solve the design problem using algorithms for 1-D FIR filters. This leads to high computational complexities of the design algorithms and much design time. There are also several works that formulate the design problem in term of the coefficient matices and delevop algorithms to directly solve for the coefficient matrices rather than vectorizing them first, leading to lower computational complexities than corresponding algorithms vectorizing the coefficient matrices. For simplicity, we refer to the algorithms that directly solve for the coefficient matrices as matrix-based algorithms, and those vectorizing the coefficent matrices as vectorized algorithms. The exist matrix-based algorithms only consider (weight) least-squares designs of 2-D FIR filters without any other constraints, that restricts the wide application of algorithms.For fast design problems of 2-D FIR filters, this paper first considers explicit constraints in matrix-based algorithms and proposes fast design algorithms to solve the constrained least-squares (CLS) and (constrained) minimax design problems, which overcomes the difficulties that existing matrix-based algorithms cannot design 2-D constrained FIR filters.The author in [70] has pointed that quadrantally symmetric filter is a special case in centro symmetirc filter that is symmetric about two axes, and centro symmetirc filter is a special case in conjugate symmetric complex filer with real impluse respones coefficients, and quadrantally symmetric, centro symmetirc and conjugate symmetric complex filers all belong to linear-phase 2-D FIR filter. Obviously, the linear 2-D FIR filter is also special case in 2-D FIR filters with arbitrarily magnitude and phase response. Thus, according to the progressive principle, we will study in turn the matrix-based CLS design and minimax design problems of 2-D FIR filtes with quadrantally symmetric, centro symmetric, conjugate symmetric complex and arbitrarily specified frequency response, and propose matrix-based theories and algorithms.The major work is as follows:(1) Consider the CLS design and minimax design problem of quadrantally symmetric 2-D FIR filtes. The CLS design of quadrantally symmetric 2-D FIR filtes can be directly transformed into a convex quadratic programming (OP) problem with only one real coefficient matrix. Three matrix-based CLS algorithms I, II, III have been proposed to solve such problem. Design examples and comparisons with the existing method demostrate that, three matrix-based CLS algorithms are all effecitve and efficient than existing methos when given magnitude error constraints are not tight, and the matrix-based CLS algorithms I has convergence problem when given magnitude error constraints are very tight (near the minimax solution). The matrix-based CLS algorithms III is the most efficient one for the designs of high order filters. The matrix-based SCLS and mixed L2/L∞ methods are proposed to transform the matrix-based minimax design problem into the same form with the matrix-based CLS design to solve. Design examples and comparisons with several existing algorithms demonstrate the effectiveness and efficiency of the proposed algorithms.(2) The CLS design and minimax design problems of centro symmetric 2-D FIR filtes are considered. The CLS design of centro symmetric 2-D FIR filtes can be expressed as a convex OP problem with real two coefficient matrices. Thinking of the convergence, the paper only extend the matrix CLS algorithms II and III to this case. The matrix-based SCLS and mixed L2 /L∞ methods are extended to transform the matrix-based minimax design problem into a convex OP problem with two real coefficient matrices to solve. Design examples illustrate that these algorithms are very efficient.(3) Consider the CLS design and minimax design problems of conjugate symmetric complex 2-D FIR filtes. The matrix-based CLS design and minimax design can both be transform into the matrix-based convex OP problem with four real coefficient matrices directly or indirectly after equivalently conversion by matrix-based mixed L2/L∞ method. Only the matrix-based CLS algorithm III is extended to the optimal design problem of this kind of filter on base of convergence and efficiency.(4) The CLS design and (constrained) minimax design problems of 2-D FIR filters with arbitrarily magnitued and phase responses are studied. The elliptic-error and phase-error constrained optimal design model is proposed. The CLS design with elliptic-error and phase-error constraints (EPCLS), the minimax elliptic-error magnitude design with phase-error constraints (PMMEE), the minimax phase error design with elliptic-error magnitude constraints (EMMPE) and the minimax phase error design with minmizing the maximum of complex-error magnitude simultaneously (MMPEEE) can all be directly or indirectly (i.e. by extending the matrix-based mixed L2/L∞ or SCLS method) transformed into the matrix-based semi-infinite convex QP problem with only one coefficient matrix. The matrix-based EPCLS-GI algorithm is proposed to solve such problem by combing the matrix-based CLS algorithms Ⅲ with existing vectorized CPCLS-GI algorithm [24], which reduces the computation complexity from O(N6) to O(N4) and greatly improves the computational efficiency of the algorithm. A filter type dependent 2-D Sigmoid phase-error upper-bound function is introduced to reduce the maximum group delay error. The optimal design model of CIS and minimax design with elliptic-error constraints and 2-D Sigmoid phase-error upper-bound function can reduce the maximum group-delay error greatly and reduce the magnitude error effectively. Design examples and comparisions with existing methods illustrate the effectiveness and high efficiency of the proposed methods.All algorithms proposed in this dissertation are the matrix-based algorithms, i.e., the design procedure always keep the coefficient nature matrix form. Large numbers of design examples indicate that they are computationally high efficient, and can be design various 2-D FIR filters.