Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
2000-07-10
2004-10-05
Wu, Jingge (Department: 2623)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C382S248000, C375S240110
Reexamination Certificate
active
06801667
ABSTRACT:
COPYRIGHT NOTICE
This patent specification contains material that is subject to copyright protection. The copyright owner has no objection to the reproduction of this patent specification or related materials from associated patent office files for the purposes of review, but otherwise reserves all copyright whatsoever.
TECHNICAL FIELD OF THE INVENTION
The present invention relates generally to image compression technology, and in particular, to the use of transform techniques in a manner which improves the performance of the decompression process, especially for scanline and band-based systems which produce decompressed output in raster order.
BACKGROUND ART
Typically, data compression using wavelet techniques is, in broad terms, a two step process. This can be seen in
FIG. 1
, where a data block
100
, undergoes a wavelet transform process
104
, and a subsequent coding process
108
. It is noted that transform data is segmented, and segments are coded independently. Thereafter, the coded data stream is transmitted, either over a network between disparate equipment, or over a backplane, within a single piece of equipment, as exemplified by an arrow
110
, and input to a decoding process
112
. The decoding process then outputs a decoded data stream
114
to an inverse wavelet transform process
116
, where-after a reconstituted data block
120
is produced.
A standard decomposition process
104
for computing wavelet transforms of the input data block
100
generates sub-band data which is not spatially localized. If this data is coded by the process
108
into a data stream without any re-ordering, then the input buffer implemented at the decoder
112
must be able to store the information required to decode a particular output data point in the data block
120
, the needed information being distributed in the data stream.
Turning to
FIG. 2
, wavelet transformation of a data block
400
is typically performed using high pass and low pass filtering operations, and also a decimation (ie. down sampling) by two, resulting, initially, in production of two output data sets i.e. the high pass and low pass sub-bands. The aforementioned process constitutes a single “level” of transformation. The wavelet transform process can be multi-level, consequently storing the high pass sub-band at each level, and then recursively applying the filtering/decimation operation to the resultant low pass sub-band. Each such step produces another level, and the process continues, typically, for some predetermined number of levels, or until some cost or error function is satisfied. In
FIG. 2
, an input data block
400
of length
436
(i.e. “u”) is transformed into a data set
402
which comprises a low pass third level segment
404
(i.e. L3), a high pass third level segment
406
(i.e. H3), a high pass second level segment
408
(i.e. H2), and a high pass first level segment
410
(i.e. H1). The transformed data set
402
has the same length
436
as the input data set
400
, since no data compression has been performed. Compression can be achieved by coding the transformed data set
402
. In one method of coding, the transformed data set
402
is first segmented into equal sized segments of length
438
(i.e. of width “w”) as shown in the segmented data set
412
. Additional information can also be incorporated into the data set
412
, in order to identify start and end points of each segment of length
438
. Thereafter, each transformed segment
414
can be independently coded to form an equivalent coded segment
418
. When compression is performed, each segment
414
will “shrink” in size according to the compression achieved on a per-segment basis, and thus the coded data set
416
can have a shorter length than the original data block
400
, and the transformed data set
402
. The issue of compression coding is not the direct focus in the present specification, and it will thus hence forth be assumed, for the sake of ease of description, that no actual compression gain is sought. It is noted that the discussion is however equally relevant if compression gain were to be provided.
The coding of the transform data set
412
, under the assumption of zero compression gain, produces a coded data set
416
, where each segment
418
corresponds directly to the uncoded data item
414
in data set
412
.
The inverse wavelet transform requires, for each reconstituted data segment
424
, constituent segments which are distributed across the data set
420
. Thus, for example, data segment
424
in the inverse transformed data set
422
(this being the recovered data block equivalent to original data segment
440
in the data block
400
), requires constituent data segments
426
,
428
,
430
and
432
, i.e. one segment from each sub-band L3, H3, H2 and H1. Consequently, not only is a delay (represented by an arrow
434
) incurred before the inverse transformation of the segment
424
can occur, but in addition, the data items Z
1
through Z
9
(see data set
416
) are required to be stored (or alternatively the unneeded segments Z
2
, Z
4
, Z
6
-Z
8
are discarded and subsequently re-transmitted as needed). Therefore, the minimum information required at the inverse transform process
116
(see
FIG. 1
) in order to produce the output in raster order is the coded information that corresponds to the data segments
426
,
428
,
430
and
432
. If the compressed data stream
416
is sent in sequential order as shown in
FIG. 2
without the any rearrangement or re-ordering, the inverse transform process
116
must wait until all the coded data segments through to the first segment of the H1 level
410
has been received. This extracts a penalty in both memory requirements, and latency in the decode/inverse transform processes
112
,
116
. The time delay, or equivalently the memory required, which is associated with the data which must be stored before the inverse transform can be applied to recover the first segment
424
is represented presented mathematically by:
(u/2)+w
where u is the span, or length of the data set
400
(ie.
436
), and w is the length of the individual segment
438
. This representation assumes zero compression gain.
An unordered segment stream therefore results in a penalty in memory requirements and/or in the delay suffered before a given data point in the recovered data block can be recovered.
SUMMARY OF THE INVENTION
It is an object of the present invention to substantially overcome, or at least ameliorate, one or more disadvantages of existing arrangements.
According to a first aspect of the invention, there is provided a method of selecting transform segments from a data stream, the stream comprising a plurality of blocks each comprising a plurality of transform segments, the selection of said segments reordering the transform segments in at least one said block, the method comprising, for each said block, the steps of:
selecting a first set of transform segments suitable for direct inverse transformation to form a first data segment;
selecting a second transform segment being directly inverse transformable dependent upon the first set;
identifying a third transform segment not being directly inverse transformable dependent upon the first set and the second transform segment; and
selecting a fourth transform segment required to support direct inverse transformation of the third transform segment.
According to a second aspect of the invention, there is provided a method of ordering transform segments from a data stream for an image decoder, the stream comprising a plurality of blocks each comprising a plurality of transform segments, the ordering of said segments characterised in that the ordering results in a smaller set of transform segments that need to be stored, thus reducing a size of storage means in the image decoder.
According to a third aspect of the invention, there is provided a method of ordering transform segments from a data stream for an image decoder, the stream comprising a plurality of blocks each comprising a plurality of transform segments, the orderin
Canon Kabushiki Kaisha
Wu Jingge
LandOfFree
Method and apparatus for re-ordering of a bit stream 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 and apparatus for re-ordering of a bit stream, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for re-ordering of a bit stream will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3300190