Filtering device

Details Filtering device Filtering device

2000-07-25

2004-06-15

Chin, Stephen (Department: 2634)

Pulse or digital communications

Receivers

Interference or noise reduction

C708S313000, C708S300000

Reexamination Certificate

active

06751277

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to a device for filtering an input sequence of digital signals, comprising:
(1) a first filtering stage, itself including:
(A) a first splitting circuit, provided for subdividing the input sequence into two disjoint sets of samples, comprising respectively the odd samples c
0
(2n+1) and the even samples c
0
(2n) of said sequence
(B) a first predicting circuit, provided for generating “detail” coefficients d
1
(n)=c
0
(2n+1)−P
1
[ . . . , c
0
(2n−2), c
0
(2n), c
0
(2n+2), . . . ], where P
1
is a first linear filter and ( . . . , c
0
(2n−2), c
0
(2n), c
0
(2n+2), . . . ) is the vector containing only the even samples of the input signal;
(C) a first updating circuit, provided for generating “approximation” coefficients c
1
(n)=c
0
(2n)+U
1
[. . . , d
1
(n−1), d
1
(n), d
1
(n+1), . . . ], where U
1
is a second linear filter and ( . . . , d
1
(n−1), d
1
(n), d
1
(n+1), . . . ) is the vector containing the “detail” coefficients;
(2) at least a second filtering stage, itself including:
(D) a second splitting circuit, provided for subdividing the previously generated “approximation” vector into two disjoint sets of samples, similarly called c
1
(2n+1) and c
1
(2n);
(E) a second predicting circuit, provided for generating a second level of “detail” coefficients d
2
(n)=c
1
(2n+1)−P
2
[ . . . , c
1
(2n−2), c
1
(2n), c
1
(2n+2), . . . ], where P
2
is a third linear filter and ( . . . , c
1(
2n−2), c
1
(2n), c
1
(2n+2), . . . ) is the vector of “detail” coefficients of even order resulting from the second splitting operation;
(F) a second updating circuit, provided for generating a second set of “approximation” coefficients c
2
(n)=c
1
(2n)+U
2
[ . . . , d
2
(n−1), d
2
(n), d
2
(n+1), . . . ], where U
2
is a fourth linear filter and ( . . . , d2(n−1), d
2
(n), d
2
(n+1), . . . ) is the following vector of “detail” coefficients.
This invention may be used in a wide range of signal processing applications, such as image and speech compression.
BACKGROUND OF THE INVENTION
Sub-band decomposition techniques are extensively used for data coding, for instance in signal processing applications like image and speech compression. Applied for example to image compression, they allow to perform a representation of the image information as a collection of sub-images appearing at different resolutions. A popular technique for carrying out such a decomposition is the well-known wavelet transform, that allows an original input signal to be described by a set of sub-band signals. Each sub-band represents in fact the original signal at a given resolution level and in a particular frequency range.
This decomposition into uncorrelated sub-bands is implemented by means of a set of monodimensional filter banks applied first to the lines of the current image and then to the columns of the resulting filtered image. An example of such an implementation is described in “Displacements in wavelet decomposition of images”, by S. S. Goh, Signal Processing, vol. 44, no 1, June 1995, pp.27-38. Practically two filters—a low-pass one and a high-pass one—are used to separate low and high frequencies of the image. This operation is first carried out on the lines and followed by a sub-sampling operation, by a factor of 2. It is then carried out on the columns of the sub-sampled image, and the resulting image is also down-sampled by 2. Four images, four times smaller than the original one, are thus obtained: a low-frequency sub-image (or “smoothed image”), which includes the major part of the initial content of the concerned image and therefore represents an approximation of said original image, and three high-frequency sub-images, which contain only horizontal, vertical and diagonal details of said original image. This decomposition process continues until it is clear that there is no more useful information to be derived from the last smoothed image.
In the technical report “Building your own wavelets at home”, by W. Sweldens and P. Schröder, Industrial Mathematics Initiative, Department of Mathematics, University of Seattle, Carolina, 1995, a new way to implement a very simple example of wavelet transform is described, the so-called Haar wavelet. Consider two numbers A and B as two successive samples of a sequence (A and B have therefore some correlation), a simple linear transform allows to replace them by their average S and their difference D:
S
=(
A+B
)/2  (1)
D=B−A
  (2)
(if A and B are highly correlated, the expected absolute value of their difference is small and can be represented with few bits). When using such a linear transform, no information is lost, since A and B can always be reconstructed:
 
A=S−D
/2  (3)
B=S+D
/2  (4)
The above-given consideration is the key for understanding the Haar wavelet transform. Consider now a signal S[n] of 2
n
sample values s[n, l]:
S[n]=s[n, l
] 0
≦l
<2
n−1
  (5)
and apply the average and difference transform to each pair A=s[2l] and B=s[2l+1]. There are 2
n−1
such pairs (l=0, 1, 2, 3 . . . , 2
n−1
). The results are the following:
s[n
−1
, l
]=(
s[n
, 2
l]+s[n
, 2
l
+1])/2  (6)
d[n
−1
, l]=s[n
, 2
l
+1
]−s[n
, 2
l]
  (7)
The input signal s[n], which has 2
n
samples, is split into two signals : s[n−1], with 2
n−1
averages s[n−1, l], and d[n−1], with 2
n−1
differences d[n−1, l], these averages and differences always allowing to recover the original signal S[n]. The averages can be seen as an approximation or a coarser representation of the original signal S[n], and the differences as the detail information needed to go from that coarser representation back to this original signal. If said original signal has some coherence (e.g. if the samples are values of a smoothly varying function), then the coarse representation closely resembles this original signal, the details being very small.
When applying iteratively the same transform to the coarser signal (by taking the average and difference), a coarser signal s[n−2] and another difference signal d[n−2], splitting s[n−1], are obtained. When repeating this operation n times, a Haar transform is implemented (that can be thought of as applying a N×N matrix (N=2
n
) to the signal S[n]).
A new way of looking at the Haar transform, also called the “ladder” of lifting scheme, can then be presented, the novelty lying in the way the difference and the average of two numbers A and B can be computed. If one wants to compute the whole transform in-place—i.e. without using auxiliary memory locations, by overwriting the locations that hold A and B with the values of respectively S and D-, it cannot be done with the previous formulas (1) and (2): when using them and storing S and D in the same location as A and B respectively, it would lead to a wrong result.
Another implementation in two steps is preferred:
first the difference D=B−A is computed and stored in the location for B (which is therefore lost, thus preventing from computing directly S=A+B);
B being lost, the average is then found by using A and the newly computed difference D, according to the formula S=A+D/2 which gives the same result, and this result is stored in the location for A.
The advantage of such a splitting into two steps is that it is possible to overwrite B with D and A with S without requiring any auxiliary storage. This particular scheme can be described in mor

Affiliated with

Also associated with

Rating

Filtering device does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Filtering device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Filtering device will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3363279