Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-10-21
2002-12-24
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S400000
Reexamination Certificate
active
06499045
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally relates to discrete wavelet transforms (DWT), and more particularly, to field programmable gate array (FPGA) implementations of DWTs.
BACKGROUND
An example programmable logic device (PLD) is the field programmable gate array (FPGA), first introduced by Xilinx, Inc. in 1985. PLDs such as FPGAs are becoming increasingly popular for use in electronics systems. For example, communications systems employ FPGAs in large measure for their re-programmability. In general, the use of FPGAs continues to grow at a rapid rate because they permit relatively short design cycles, reduce costs through logic consolidation, and offer flexibility in their re-programmability.
Advances in semiconductor process technology are delivering FPGAs having logic densities in the range of a million system gates and having operating speeds in excess of 100 MHz. These powerful devices are capable of and have been used to implement digital signal processing (DSP) algorithms that are inherently parallel and normally require multiple DSP microprocessors in order to meet the high data rates. It is feasible to implement such algorithms on a single FPGA because such devices offer a programmable architecture.
The discrete wavelet transform (DWT) is a useful and efficient signal and image decomposition method with many interesting properties. This transformation, which is similar to the Fourier transform, provides information about the frequency content of signals. However, unlike the Fourier transform, DWT is more natural and fruitful when applied to non-stationary signals, such as speech and images.
The flexibility offered by DWT allows researchers to develop suitable wavelet filters for particular applications. For example, in the compression of fingerprints a particular set of biorthogonal filters, Daubechies biorthogonal spline wavelet filters, has been found to be effective. This flexibility is nonexistent in the discrete-cosine transform for image compression.
The latest standards for image and video compression, JPEG and MPEG, include wavelet transforms as the means for image and video signal decomposition. In addition to efficient image decomposition for compression and coding, wavelet transform is applied to images for filtering and enhancement. The filtering algorithms, generally referred to as denoising, have shown robust and effective performance in the removal of noise from images with minimal side effects (blurring).
In many image processing applications, including compression, denoising, and enhancement, real-time processing of a two-dimensional wavelet transform is required. Flexibility in customizing the wavelet transform with regard to the filters and the structure of the wavelet decomposition tree are also desirable. Most ASIC implementations are developed for specific wavelet filters and/or wavelet decomposition trees, which renders ASIC solutions useless for applications that require different filters and/or different decomposition trees. An apparatus that addresses the aforementioned problems, as well as other related problems, is therefore desirable.
SUMMARY OF THE INVENTION
In various embodiments, analysis and synthesis banks of a two-dimensional discrete wavelet transform are implemented using a cascade combination of two one-dimensional wavelet transforms along with a set of memory buffers between the two stages. The memory buffers store intermediate results between the stages of the two-dimensional discrete wavelet transform, thereby eliminating off-chip memory references.
In one embodiment, a two-dimensional discrete wavelet forward transform analysis bank is provided. The analysis bank includes a circuit arranged to perform a first one-dimensional wavelet transform of rows of input data for a selected wavelet type. A plurality of buffers are arranged for storage of output data from the first one-dimensional wavelet transform. A second circuit is arranged to perform a one-dimensional wavelet transform of columns of input data for the selected wavelet type. In another embodiment, the first transform operates on the columns of data and the second transform operates on the rows of data.
In another embodiment, a two-dimensional discrete wavelet inverse transform synthesis bank is provided. The synthesis bank is constructed as the inverse of the analysis bank.
REFERENCES:
patent: 4760543 (1988-07-01), Ligtenberg et al.
patent: 4791598 (1988-12-01), Liou et al.
patent: 5126962 (1992-06-01), Chiang
patent: 5197021 (1993-03-01), Cucchi et al.
patent: 5859788 (1999-01-01), Hou
patent: 5875122 (1999-02-01), Acharya
patent: 5889413 (1999-03-01), Bauer
patent: 5991788 (1999-11-01), Mintzer
patent: 6038579 (2000-03-01), Sekine
patent: 6047303 (2000-04-01), Acharya
patent: 6216145 (2001-04-01), Zandi et al.
patent: 6223195 (2001-04-01), Tonomura
Xilinx, Inc., “The Programmable Logic Data Book”, available from Xilinx, Inc., 2100 Logic Drive, San Jose, CA 95124, pp. 3-1 to 3-60, 1999.
Reza Ali M.
Turney Robert D.
Cartier Lois D.
Malzahn David H.
Maunu LeRoy D.
Xilinx , Inc.
LandOfFree
Implementation of a two-dimensional wavelet transform does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Implementation of a two-dimensional wavelet transform, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Implementation of a two-dimensional wavelet transform will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2934331