Image analysis – Image compression or coding – Transform coding
Reexamination Certificate
1998-10-27
2002-01-15
Tran, Phuoc (Department: 2621)
Image analysis
Image compression or coding
Transform coding
C382S242000
Reexamination Certificate
active
06339659
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates generally to encoding/decoding method and apparatus and recording medium, and more particularly, to an encoding method and apparatus, a decoding method and apparatus, and a recording medium usable in a system for high efficiency picture encoding or decoding for efficient picture transmission.
The International organization for Standardization (ISO) has promulgated a standard for a conventional picture compression system called Joint Photographic Expert Group (JPEG). This system provides optimal encoding or decoding of pictures by applying a Discrete Cosine Transformation (DCT) to an image to transform that image into DCT coefficients. This system works most efficiently when a relatively large number of bits are to be employed to represent the encoded information. However, if the number of bits to be employed to represent the encoded information is less than a certain predetermined value, block distortion inherent in such a DCT transform becomes prevalent enough to deteriorate the quality of the picture which may be noticed by a viewer.
In response to these deficiencies of the JPEG and DCT procedure, a new Iterated Function System (IFS) picture compression technique has been proposed, and is beginning to gain favor. This IFS technique exploits self-similarity between portions of pictures and is based on fractal geometry. IFS works on the assumption that various portions of a particular picture are analogous, even though they may be of a different size, position, perspective, or orientation. IFS utilizes this redundancy in pictures to efficiently encode the picture without resulting block distortion, as may be generated in the JPEG system. Therefore, IFS is not nearly as dependent upon the number of bits to be used to represent the encoded information, and therefore the resolution during decoding does not suffer when a relatively smaller number of bits are to be used to represent the encoded information.
The basic structure of IFS is set forth in Arnaud E. Jaquin's publication entitled “Image Coding Based on a Fractal Theory of Iterated Contractive Image Transformations”, IEEE Transactions on Image Processing (Vol. 1, No. 1, pp. 18-30), and is further set forth in U.S. Pat. Nos. 5,347,600; 5,065,447 and 4,941,193, all issued to Barnsley et al. The encoding and decoding devices as generally known in the art will now be described with reference to
FIGS. 15 and 16
.
Referring first to
FIG. 15
, the conventional operation of encoding device is shown. As set forth in
FIG. 15
, original picture data
300
is entered to a block generating circuit
200
and is therein split into a plurality of block data
301
. The entire block data
301
cover the entire original picture data
300
, but the blocks do not overlap with each other. Original picture data
300
is also forwarded to reduced picture generating circuit
202
. Picture data
307
having a reduced (shrunk) size, such as by way of a reduction scheme as is known in the art which is obtained through the processing of reduced picture generating circuit
202
, is forwarded and stored within reduced picture storage circuit
204
.
Data in each of the blocks is forwarded to approximate area search circuit
201
which searches reduced size picture data
307
stored in reduced picture storage circuit
204
to determine whether any portions of the reduced size picture data are analogous to the particular block data
301
being searched. As noted above, this search includes searching for portions of reduced size picture data
307
which are of different size, position, perspective, or orientation than the block data
301
being searched. In accordance with the detected result indicating a successful search for a most similar portion, similar block position information
306
, which specifies the position of the selected portion
305
within the reduced size picture data
307
that is to be extracted, is transmitted to reduced picture storage circuit
204
. Thus, in accordance with these instructions, selected portion
305
of the reduced size picture data
307
stored within reduced picture storage circuit
204
is extracted, and is transmitted to a rotation/inversion/level value transform circuit
203
.
Within rotation/inversion/level value transform circuit
203
, portion
305
of reduced size picture data
307
is processed by rotation/inversion/level value transformation in accordance with transformation parameters
304
which are supplied from approximate area search circuit
201
. The transformation parameters
304
are indicative of the transformation which must be performed in order to transform portion
305
of reduced size picture data
307
into block data
301
. These parameters are determined when a particular portion
305
of reduced size picture data
307
is found to most closely correspond to block data
301
being searched. Upon transformation at rotation/inversion/level value transform circuit
203
, transformed reduced-size picture data
303
is forwarded to approximate area search circuit
201
. There as a result, transformation parameters
304
and similar block position information
306
are output as ISF codes
302
. Thus, a first picture is input to the system, and the output includes at least transformation parameters, for transforming a first block into a second similar block, and position information, for determining the position of the second block within the encoded picture.
Referring next to
FIG. 16
, decoding apparatus is provided in which the IFS codes, including transformation parameters and similar block position information
302
which are output by the encoding device of
FIG. 15
, are entered into and stored in an IFS code storage circuit
205
. IFS codes
302
are then sequentially read out from IFS code storage circuit
205
for each block, and are forwarded to IFS code reading circuit
206
. IFS code reading circuit
206
divides the codes into similar block position information
306
and transformation parameters
304
as provided by the encoder. Similar block position information
306
is then forwarded to reduced picture storage circuit
204
in order to reproduce the area of the reduced-size picture specified by similar block position information
306
. The portion
305
of the reduced size picture data stored in reduced picture storage circuit
204
corresponding to the specified area is then transmitted to rotation/inversion/level value transform circuit
203
, and is transformed in accordance with transformation parameters
304
which are supplied form IFS code reading circuit
206
. The resulting transformed picture data
303
forwarded from rotation/inversion/level value transform circuit
203
is stored within decoded picture storage circuit
208
. This procedure is performed for each block in the picture for which IFS codes are provided.
After all of the IFS codes for all of the blocks have been read out, IFS code reading circuit
206
sends a READ OUT END notification signal
310
to duplication control circuit
207
. Duplication control circuit
207
counts the number of recursive decoding/duplicating operations that have been executed, and if this count has not yet reached a predetermined value, duplication control circuit
207
sends a reprocessing command signal
309
to IFS code reading circuit
206
in order to continue execution of decoding processing for all of the blocks in the picture according to a recursive decoding procedure. Simultaneously, the reprocessing command information is sent via control signal
311
to a switch
209
in order to send partially decoded picture data
313
to reduced picture generating circuit
202
via information path
314
. Reduced picture generating circuit
202
then generates partially decoded reduced size picture data
315
of decoded picture data
313
in a manner similar to that as in the encoding device in order to re-write the contents of the picture stored in reduced picture storage circuit
204
and to enable a next recursive decoding step to start with partially decoded reduced p
Fukuhara Takahiro
Ooba Akio
Alavi Amir
Frommer & Lawrence & Haug LLP
Savit Glenn F.
Tran Phuoc
LandOfFree
Fractal coding/decoding of picture data using memory... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fractal coding/decoding of picture data using memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fractal coding/decoding of picture data using memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2817404