Image analysis – Image transformation or preprocessing – Transforming each dimension separately
Reexamination Certificate
1998-08-06
2001-01-23
Couso, Jose L. (Department: 2724)
Image analysis
Image transformation or preprocessing
Transforming each dimension separately
C382S276000, C382S248000
Reexamination Certificate
active
06178269
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention is related to signal/image processing and encoding. More specifically, the invention relates to architectures to execute signal/image processing functions.
2. Description of Related Art
Using traditional Fourier analysis (transforms), any signal can be approximated as a sum of sinusoidal waveforms of assorted frequencies. While Fourier transforms are ideally suited for signals having repeated behavior, such as in speech signals, it fails to efficiently approximate signals with sharp discontinuities such as the edge features in images, or signals encoded for digital communications. Therefore, in recent years, a new form of analysis, known as Wavelet analysis has been developed to better represent signals that have exaggerated and discontinuous features. A transform, similar to the Fourier transform, Discrete Wavelet Transform (DWT), based on Wavelet analysis, has been developed to represent signals with discontinuous features. The DWT may be a “discrete” algorithm, which indicates that rather than approximating a signal using continuous waveforms, the signal is approximated by discrete samples of waveform. Since the transform is discrete, the DWT can be implemented using digital logic such as Very Large Scale Integrated (VLSI) circuits and thus can be integrated on a chip with other digital components.
The essence of DWT is to decompose an input signal into two or more frequency sub-bands. An input signal may be decomposed into two outputs—a low frequency sub-band output obtained using a low-pass filter, and a high frequency sub-band output using a high-pass filter. Each of these sub-bands can be encoded separately using a suitable coding system. Each sub-band can further be divided into smaller and smaller sub-bands as is required. If an input signal is decomposed into two sub-bands, then to reconstruct the input signal, the VLSI architecture used must be able to receive two inputs and return one output. Fundamentally, therefore, the forward DWT transform, i.e., the transform performing the decomposition, is asymmetric to the inverse DWT transform, i.e., the transform performing the reconstruction since they require different numbers of inputs and outputs. Thus, traditional VLSI architectures for the DWT computation (decomposition and reconstruction) have two separate and distinct circuitry, one for the forward DWT and one for inverse DWT. The circuitry of such architecture is complicated further since the forward and inverse transforms use different filter coefficients and schedule (delay) certain inputs in differing stages of the computation.
To reduce the speed and cost of the forward DWT and inverse DWT transform, therefore, there is needed a single integrated architecture which can perform both the forward DWT transform and the inverse DWT transform without separate circuitry or processing elements. Further, the separate architectures for the forward DWT and inverse DWT if needed must also be reduced in complexity.
SUMMARY
The invention uses certain mathematical properties of filters used in the DWT computation as well as data parallelism in the DWT computation to provide an integrated systolic architecture for decomposing as well as recomposing signals approximated using the DWT.
The integrated architecture receives a single input bitstream when computing the forward DWT and two different input bitstreams when computing the inverse DWT. Using multiplexers, clock and control signals, the integrated architecture determines whether the forward or inverse DWT is to be computed and correspondingly activates appropriate processing elements as well as inputs and outputs. A unique feature of the architecture—a single set of five processing cells—can be used to perform both the forward DWT and inverse DWT thereby eliminating the need for separate processing cells for the forward and inverse DWT. Each of the five processing cells utilizes an adder and a multiplier and receives several operands in order to compute the DWT.
In computing the forward DWT, a single input sequence generates two decomposed output sequences. Conversely, when the integrated architecture is performing the inverse DWT, two input sequences generate a single reconstructed output sequence. According to a mathematical manipulation of the DWT function, in the forward DWT, four clock cycles are required to pass in order to initialize the set of five processing cells, after which, in all successive clock cycles, an input sequence is processed such that for every clock cycle, one input yields one output. The five processing cells of the integrated architecture are further coupled to an adder module and control circuit which generates the control signals required to tell the integrated architecture whether the forward DWT or the inverse DWT should be performed and computes the final stage in the mathematical algorithm dictated by the DWT computation.
The integrated architecture of the invention can be used in a variety of applications such as image compression or other image processing applications. In this regard, the one-dimensional DWT described above can be extended to two dimensions by using two one-dimensional DWT processing modules and a transpose circuit.
REFERENCES:
patent: 5602589 (1997-02-01), Vishwanath et al.
patent: 5710835 (1998-01-01), Bradley
patent: 5764805 (1998-06-01), Martucco et al.
patent: 5848193 (1998-12-01), Garcia
patent: 5987347 (1999-11-01), Khoury et al.
Li et al., “Discrete Wavelet Transform for Tool Breakage Monitoring”, International Journal of Machine Tool & Manufacture, vol. 39, No. 12, pp. 1935-1944, Dec. 1999.
“A Theory for Multiresolution Signal Decomposition: The Wavelet Representation”-Stephane G. Mallet, IEEE Transactions on Pattern Analysis and Machine Intelligence, (vol. II, No. 7, Jul. 1989).
“VLSI Architectures for Discrete Wavelet Transforms”-Keshab K. Parhi and Takao Nishitani, IEEE Transactions on VLSI Systems, (vol.. No. 2, Jun. 1993).
“Discrete Wavelet Transform for Tool Breakage Monitoring”-Xiaoli Li, Shen Dong, Zhejun Yuan, International Journal of Machine Tools & Manufacture (1999) vol. 39, No. 12, pp. 1935-1944.
Blakely , Sokoloff, Taylor & Zafman LLP
Couso Jose L.
Do Anh Hong
Intel Corporation
LandOfFree
Architecture for computing a two-dimensional discrete... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Architecture for computing a two-dimensional discrete..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Architecture for computing a two-dimensional discrete... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2552977