Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
2000-01-31
2003-06-10
Couso, Jose L. (Department: 2621)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
Reexamination Certificate
active
06577770
ABSTRACT:
TECHNICAL FIELD OF THE APPLICATION
This invention concerns a procedure for multidimensional, discrete wavelet-transformation, for example, digital or digitized analog data with interpolated wavelets, as well as a transformation unit to implement the procedure, which may be used, for example, for subsequent data compression.
BACKGROUND OF THE INVENTION
The transformation of digital data or digitized analog data into different frequency bands using conventional wavelet transformation currently offers the best basis for the lossless compression of large, accumulating amounts of data, for example in long-range transmission and processing. Data compression using conventional wavelet transformation techniques is only possible, however, when the compressed signal is stored in segmented form. As in segmented image signals, the individual segments (of a whole image or a contained, partial image). are first sampled and compressed by line from left to right and then completely from top to bottom several times. Until now, conventional wavelet transformation techniques have not been able to compress image data from satellites or other infinite image data streams without splitting the theoretically endless image size into an endless number of image regions or segments. For this reason, the high image quality and transmission speed achieved by conventional wavelet transformation techniques in the transmission of compressed image data has not yet been achieved in the transmission of infinite, continuously accumulating images.
An example of a conventional wavelet transmission technique is disclosed in German patent application DE 196 26 615. In DE 196 26 615, first, a data stripe with several lines (see
FIG. 22
of DE 196 26 615) is processed using simple, reversible S- and TS-wavelets. In this process data for the non-minimal length wavelet filter (TS-wavelet) from the next data stripe must be taken into consideration in the procedure as a “preview”. After the first stripe has been processed completely, the “preview” part is processed again with subsequent “preview” parts as a contained image, and this procedure is repeated again and again until all stripes have been processed individually and at all levels. The disadvantage of this technique is that it requires an extremely large amount of memory since almost all lines must be saved twice due to the intermediate “preview” step. To reduce the memory requirements somewhat, the procedure in DE 196 26 615 performs a vertical, two-dimensional wavelet transformation with a minimal length S-wavelet filter—a filter with poor transformation qualities.
To overcome this problem it has been proposed that a multi-stage transformation be achieved by using the low-pass region of a stage with any number of dimensions as the input value for the following stage (see “Ingenieur der Kommunikationstechnik”, IK 2 (1997), p. 39 ff.). Here, however, the complete low-pass region of the previous stage must be available to carry out the next stage of the transformation. This procedure requires an equally large amount memory in order to store the complete image.
Before describing the present invention in detail, a description of some important basic topics follows:
“Data compression” refers to techniques and methods that map data or symbols to code words because the storage of the code words requires fewer bits than the original data. Data compression is thus a useful tool for saving or transmitting large amounts of data.
The input symbols can be one-, two- or multidimensional and generally represent physical quantities, for example, the spatial light intensity distribution of an image signal or the temporal sound waves of an audio signal. One-dimensional signals can represent, for example, temporal or spatial changes in a single direction, two-dimensional signals can represent spatial changes in two directions and multidimensional signals can represent, for example, the temporal or spectral changes of spatially changing physical quantities.
The wide range of techniques and methods for data compression can be grouped into lossy compression and lossless compression. The use of lossy compression techniques generally results in a loss of information, i.e. it cannot be guaranteed that the original data can be perfectly recreated from the compressed data. Lossy compression techniques are used when differences between the original data and the reconstructed data are acceptable. Lossless compression techniques are used when a prefect reconstruction of the original data is required.
A wavelet transformation can be expressed as a mathematically defined, linear mapping of a space R
n
R
n
.
The mapping function can be written in the form of a linear convolution operation. In this form the signal f is analyzed with the help of the wavelet functions &psgr;. This is described by the following formula:
L
ψ
(
a
,
b
)
=
&LeftBracketingBar;
a
&RightBracketingBar;
-
1
2
∫
R
f
(
t
)
ψ
(
t
-
b
a
)
ⅆ
t
Here, L
&psgr;
represents the wavelet transformation relative to the wavelet function &psgr;. This type of wavelet transformation is also referred to as a continuous wavelet transformation.
If time-discrete or sampled signals constitute the input value range of the wavelet transformation then it is referred to as a discrete wavelet transformation. A simple and fast formula exists that describes this form of discrete wavelet transformation. Here, a wavelet transformation is carried out using a set of digital filters. A full set of wavelet filters consists of 4 individual digital filters grouped into two filter pairs. One pair is referred to as the analysis filter pair while the other is referred to as the synthesis or reconstruction filter pair. Each of the filter pairs consists of a high-pass and a low-pass filter.
As shown in
FIG. 1
, the input signal x(t), which in the discrete case is a row of discrete values x
i
is linked to the high-pass and the low-pass of the analysis filter pair with the help of a digital FIR filter. The result of both filter operations is down-sampled by suppressing every second output value. The output result of the high-pass analysis filter is referred to as the high-pass or detail coefficient while the result of the low-pass analysis filter is referred to as the low-pass or average coefficient.
As shown in
FIG. 2
, a reverse of this wavelet transformation is achieved using a reconstruction filter pair (FIG.
2
).
As shown in
FIG. 3
, for a multi-stage wavelet transformation, the results of the low-pass filtering, the average coefficients, undergo further, single-stage wavelet transformations.
SUMMARY OF THE INVENTION
The invention can be used in a wide range of fields including space technology; for observing, measuring and surveying the earth's surface with satellites; civilian and military aeronautics; for the evaluation of x-ray images; for security systems, as well as for general industrial image processing.
The purpose of the invention is to provide the advantages of wavelet transformation, a mathematical mapping of spaces, and in particular the advantages of interpolating wavelets, for the transmission of infinitely long and continuously accumulating, non-contained images using a minimal amount of memory.
With the help of this invented procedure and the transformation unit that has been proposed for its realization, a complete wavelet transformation system has been created which performs the decorrelating transformation of input data of various types, for example audio or image data, digital or digitized analog data.
The invention also includes an inverse wavelet transformation system for reversing the wavelet transformation system procedures.
This invention concerns a procedure for multidimensional, discrete wavelet-transformation, for example, digital or digitized analog data with interpolated wavelets, as well as a transformation unit to implement the procedure, which may be used, for example, for subsequent data compression.
The invention can be used i
Martin Uwe Erik
Roesel Reinhard
Thierschmann Michael
Couso Jose L.
LuraTech Gesellschaft fuer Luft-und Raumfahrttechnologie & Multi
Squire Sanders & Dempsey L.L.P.
LandOfFree
System and method for a multidimensional, 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 System and method for a multidimensional, discrete..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for a multidimensional, discrete... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3138407