Image analysis – Image compression or coding – Transform coding
Reexamination Certificate
1998-12-18
2001-08-07
Johnson, Timothy M. (Department: 2623)
Image analysis
Image compression or coding
Transform coding
Reexamination Certificate
active
06272258
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates to a method for fractal coding of signals, in particular of video or audio signals.
The so-called self-similarity of a signal to be transmitted is used for fractal coding of, for example, images, the principles of which are described in the article by Jaquin, A. E.: “Image Coding Based on a Fractal Theory of iterated Contractive Image Transformations”, IEEE Transactions on Image Processing, Vol. 1, No. 1, January 1992. If the signal to be transmitted is a video signal, use is then made of the fact that parts of the image can be represented by other image parts which are geometrically located at different points in the same image, if these image parts are changed in a specific manner. If the signal to be transmitted is an audio signal, then a corresponding situation applies in that specific sections of the audio signal can be modelled by other signal sections, when these signal sections are manipulated in a specific manner.
The procedure in this case is to investigate a so-called domain block d to form a signal section which is intended to be transmitted, the normally so-called range block r, from which domain block d an approximated range block r* is formed by using a specific calculation rule and which models the range block r as well as possible. The calculation rule used in this case is:
r*=v·d+b
where
b
T
=(
b,b . . . b
) (1)
In this case, v·d is a linear map and the term b describes an offset, to be precise in general of such a type that the components in general experience different “shifts” by v·d. For data reduction reasons, the document by Jaquin quoted above proposes that an offset vector comprising identical components be selected for the offset:
b=
(
b,b . . . b
)
T
(2)
where b
T
is the transpose of the vector b.
The domain block vector d used in equation (1) is in this case normally obtained from the original signal by cutting out of the original signal a signal block whose dimensions are larger than those of the range block vector r to be modelled. This larger signal block is then normally subjected to geometric transformation (mirroring, rotation or the like) and is then reduced in size by a further operation (undersampling and filtering or the like) to the dimensions of the range block vector r.
A search method is used to determine the domain block d which best models the signal section to be transmitted. In this case, the mean square error according to equation (3) is in general used as the decision criterion for the quality of the modelling.
e
2
=
1
/
N
∑
i
=
1
N
(
r
i
-
r
i
*
)
2
(
3
)
where:
e
2
mean square error
r
i
i-th element of the range block vector r, which is composed of N components, and
r*
i
i-t element of the approximated range block vector r*.
Apart from the position of the domain block in the original signal, the search method used also has the object of determining what the optimum parameters are for the gain v and the offset b and what geometric transformation should, if necessary, be applied to the signal block.
The fractal code for the signal block to be transmitted now comprises the optimum parameters that have been found: position of the domain block in the signal, geometric operation applied to this domain block, gain v and offset b. These parameters are coded and transmitted.
In the receiver, apart from an error which may be relatively large or relatively small depending on the quality of the coding, the signal section can be reconstructed by applying the mapping rule a plurality of times to any desired initial signal. That is to say, in the first step, each approximated range block is produced by applying the rule (4) to the corresponding domain block from the random initial signal, once the domain block has been reduced in size and has been subjected to the correspondingly associated geometric operation on this range block.
r*
1
=v·d
0
+b
(4)
d
0
domain block in the initial signal
r*
1
first approximation range block
If the mapping rule is applied to all the range blocks, then a first approximation to the original signal is obtained by joining together the approximated range blocks from the random initial signal.
In the second step, each approximated range block is produced by applying the rule (5) to the corresponding domain block from the first approximation, once again after the domain block has been reduced in size and has been subjected to be correspondingly associated geometric operation on this range block.
r*
2
=v·d
1
+b
(5)
where:
d
1
first approximation range block, and
r*
2
:second approximation range block.
A second approximation to the original signal is this obtained.
This procedure is now repeated as often as is necessary to obtain a good reconstruction of the original signal. As a rule, this involves 10 to 20 iterations for original images.
Investigations into fractal coding of audio signals using equation (1) have shown that, with the assumption according to equation (2), sufficiently good models of the range blocks can in general be achieved only if very small range blocks are chosen. However, small range blocks mean little data reduction. A more favourable solution in terms of data reduction is obtained using unequal values for the component so the offset vector, and large range blocks.
Furthermore, the use of fractal coding in image coding can lead, in the case of certain images with periodic structures close to one another, to the structures not being reproduced with few errors.
If fractal coding is used for audio coding, then periodic signals likewise lead to the result that these signals can be reproduced only very inadequately using the method. This is a result of the fact that fractal coding always involves a reduction in the size of the domain blocks. In the case of periodic signals, this reduction in size leads to the signal period being varied by the compression that is used. If the signal passage which contains the domain blocks does not include any signal elements which, as a result of the compression, lead to a signal whose period is similar to the range blocks, then the corresponding range blocks can be reproduced only very inadequately.
SUMMARY OF THE INVENTION
The invention is thus based on the object of providing a method for fractal signal coding for video or audio signals, which allows a higher degree of data reduction and better reproduction of periodic structures.
The object is achieved by the subject matter of claim
1
. Preferred refinements of the invention are the subject matter of the dependent claims.
According to the invention, favourable offset vectors b are used for fractal coding, the offset vector b being formed from weighted orthogonal basic functions of an orthogonal transformation. More favourable offset vectors b can be found by analyzing the blocks to be modelled and being modelled spectrally with the aid of a suitably selected transformation, for example discrete cosine transformation (DCT), and by using the results to represent the offset vector b by the sum of a number of less-weighted basic vectors of the selected transformation. The method is not limited to the use of DCT transformation and it is possible to use other orthogonal transformations, such as discrete Fourier transformation DFT, which is likewise used in audio coding.
The orthogonal basic vectors can advantageously be used to reproduce periodic signal elements. Furthermore, one advantage of the method according to the invention is that the signal reconstruction at the reproduction end can be carried out in a familiar manner using the conventional iteration process (that is to say without increasing the complexity).
Block windowing using windows with soft boundaries represents an additional advantageous method for fractal coding, which has been found to be particularly advantageous for avoiding so-called blocking effects in the coding of audio signals. Such blocking effects are caused by sudden changes in value at the block boundaries
Dickopp Gerhard
Vaupel Thomas
Deutsche Thomson-Brandt GmbH
Johnson Timothy M.
Kurdyla Ronald H.
Laks Joseph J.
Tripoli Joseph S.
LandOfFree
Method for fractal coding of video or audio signals does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for fractal coding of video or audio signals, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for fractal coding of video or audio signals will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2462886