Optimal Design Of Two-Dimensional Separable Fir Filter With Sparse Coefficients

Two-dimensional(2-D)FIR digital filters are widely used in image processing,seismic signal processing,radar and sonar signal processing,machine vision and wireless communication.However,for the 2-D FIR filters,especially in the case of comparatively high order,the number of filter coefficients is very large.Thus,the hardware implementation of the 2-D FIR filters needs fairly large number of multipliers and adders.There are some existing methods to reduce the hardware implementation complexity of the 2-D FIR filters,such as McClellan transform method and separable 2-D FIR filter design.In this thesis,we focus on the separable 2-D FIR filter and a new method of designing a separable 2-D FIR filter with sparse coefficients is proposed for the first time.Various relevant sparse optimization methods are studied.The finite word length effect is studied as well as the FPGA implementation.The main work of the thesis includes:(1)An optimal design method for separable 2-D FIR filters with sparse coefficients is proposed based on iterative reweighted l1 norm and greedy searching.The proposed method consists of two steps.In the first step,based on an initial design,a separable 2-D FIR filter with sparse coefficients is designed by iterative reweighting l1 norm.Afterwards,the trust region iterative gradient searching(TR-IGS)technique is utilized to optimize the variable filter coefficients.In the second step,based on the first-step design,the greedy searching(GS)algorithm is utilized to obtain more sparse coefficients.At the end of each search of the GS algorithm,TR-IGS technique is utilized to optimize the current variable filter coefficients.GS algorithm is implemented for several iterations until the filter design error does not meet the design requirements.Simulation experiment is conducted to verify the effectiveness of the proposed method and the other six sparse design methods.(2)After obtaining a separable 2-D FIR filter with optimal continuous coefficients,the quantization of the filter coefficients is considered.Two(iterative)coefficient quantization schemes for separable structures are proposed for the first time:(iterative)two-step integer linear programming algorithm(2-step-integer-LP)and(iterative)two-step integer linear programming-neighborhood search algorithm(2-step-integer-LP-neighbor).The two proposed quantization schemes are based on the same core idea:fixing some coefficients and optimally quantizing the other coefficients.Additionally to the two proposed(iterative)coefficient quantization schemes,two other quantization schemes are also considered,namely approximate target optimization algorithm(ATOA)and signed power of two(SPoT)quantization algorithm.Simulation experiment is conducted to verify the effectiveness of the two proposed quantization schemes as well as the ATOA and the SPoT algorithms.The experimental results reveal that the two proposed schemes both outperform the ATOA and the SPoT algorithms in terms of the design error.2-step-integer-LP performs slightly better than 2-step-integer-LP-neighbor.However,the former may not work,in some case,due to the large number of optimization variables,while the latter can effectively avoid the problem of non-convergence.(3)MATLAB/Simulink and FPGA simulation of the proposed separable 2-D FIR filters are provided.Additionally,a specific application of the separable 2-D FIR filter in the image processing is given.The hardware resource occupation of the FPGA is also analyzed.