The Research Of New Types Of Algorithms For Discrete And Wavelet Transforms With Applications In Image Processing

As special types of multi-band perfectly reconstruction (PR) filters, transforms including wavelets,discrete orthogonal transforms is very important used in information processing fields, especially in image processing.In this thesis, we focus on the construction of M band wavelets with parameters with linear phase, integer implementation of wavelet and various types of discrete orthogonal transforms and their application. With the low complexity algorithms being the nucleus, the construction theory and methods is developed for M wavelets, a algorithm system of integer transforms involving wavelets and discrete transforms is proposed. Based on this theory, some application subjects, such as image compression, watermarking, three-dimensional surface approximations, and image superresloution, are investigated deepgoingly.The work of this thesis are composed of two parts that in cludes new types of algorithm theory and its application in image processing.The first content are mainly concerned with the following theoretic hands:1. Five types of wavelet construction methods is achieved:(1) By investigating relations among the length, vanishing moment and the coefficients of perfect reconstruction(PR) filters, a linear equations is solved for constructing M band wavelets, it is very easy and highly efficient when the number of band of PR filters is small.(2) By describing the general characters of lifting factorization for polyphase matrix of PR filters, and using vanishing moment of wavelet and Euclidean algorithm, the construction method via lifting scheme for PR filters is obtained.(3) By revealing the property that the discrete transforms is a PR filters in essential contain at least one order vanishing moment, a construction method based on discrete transform is also proposed.(4) By developing the polyphase matrix relations between analysis and synthesis parts of PR filter, using exchange of the matrix function, we can achieve all PR filters that the sum of filter length of analysis and synthesis parts is unchanged.(5) Furthermore, in order to overcome the that computational complexity increase sharply with the number of band M larger, using Groebner base and syzygy module of computer algebra, and orthogonal factorization for matrix polynomial, a low complexity and high precision construction for M band wavelet is obtained.The coefficients of almost wavelets developed in this paper contain some free parameters, and the intervals that these parameters belong to is achieved by employing the sufficient conditions. Moreover, these five types of construction have various features. In conclusion, the construction methods developed in this thesis can overcome the difficulty that Daubechies's method need the square-root finding the polynomial and the coefficient with irrational numbers, and on the other hand, the defect that vanishing moment of wavelet can not reveale lifting scheme methods developed by Sweldens can completely avoided. Users can easy select various types wavelets for their purpose.2. Systematic theory and integer implemental algorithms for vasious types of discrete sinusoidal transforms is presented.Using known fast floating algorithms developed by authors, and by studying sparse matrix decomposition via lifting steps, we get:(1) The integer DCT and the scaled integer DCT algorithms with general length is achieved.(2) The integer DCT, integer DFT, integer DHT and integer DWT and fast algorithms for them have been achieved, the number of operations is optimal under the sense of floating-point corresponding discrete transforms. The complex operations for integer DFT is also completely eliminated.(3) In order to speed up the efficiency of software, the unified approach that use integer DCT-Ⅱto compute all other integer discrete transforms have also been proposed. All integer transforms need only shifting and additions, so the floating-point operations are completely avoided.The second part in this thesis discusses the applications of the developed methods in image compression, watermarking, three-dimensional surface meshing, and image superresolution. The mainly contents includes:(1) In order to achieve image compression methods that is low complexity, low memory, hardware friendly, and high fidelity, the combination of stripe-based (local) wavelet and set splitting is used, and scaled wavelet lifting scheme is also proposed, and finally a low memory and low complexity image coding is developed. When the combination of the IntWLPT and this new coding method is used, memory and complexity are reduced by 75% and 54% respectively compared with that of JPEG 2000. (2) Using the feature that the wavelet can express information lossless, a low computational complexity watermarking under the Digital Terrain Model—DTM is proposed, experimental results shows the robustness of the algorithm to noise and data smooth, and furthermore, this method is also high security.(3) A type of low complexity and high precision three-dimensional surface meshing is obtained by use of wavelet with parameters, the number that triangles needed is reduced 16% compared with that of the commonly used mthods.(4) Under the frame of multigrid theory, using wavelet transforms construct interpolation and polyphase matrices, a high precision and low complexity method for solving ill-conditioned Toeplitz systems is proposed. And finally, image superresolution techniques via wavelet and multigrid is developed, the simulation results demonstrate the effectiveness of the proposed methods.