Image analysis – Image compression or coding – Adaptive coding
Patent
1998-06-18
2000-04-11
Couso, Jose L.
Image analysis
Image compression or coding
Adaptive coding
G06K 936
Patent
active
060496320
DESCRIPTION:
BRIEF SUMMARY
The present invention relates to a method and apparatus for compressing arrays of data in the form of digital electrical signals and is applicable in particular, though not necessarily, to the compression of digitally encoded image sequences.
There have recently been proposed a number of techniques for compressing arrays of data and in particular two dimensional images which may for example be individual images or frames of a video sequence. Some of the image compression techniques employ what is known as "vector quantisation" where a codebook of reference patches (e.g. relatively small portions taken from one or more "library" images) is constructed. An image to be compressed is partitioned into a number of image patches and a matching (i.e. similar) reference patch selected for each image patch from the codebook. The codebook index for each chosen reference patch in the codebook is stored, together with the corresponding position vectors of the image patches (i.e. their position in the original image), to provide a compressed representation of the image. This coding for each patch is referred to as a `compressed encoding`. Providing that a copy of the codebook is available, an approximation to the original image can be constructed by using the stored codebook indices to recover the required set of reference patches and inserting these into an image frame using the respective stored image patch position vectors. The achievable degree of compression is a function of the size of the image patches into which the image is partitioned, larger patches allowing higher compression.
It is recognised that for most images, certain areas of an image will contain more detail than other areas and that, if the patches into which the image is divided are of a size intended to achieve high compression, the detailed areas of the image may not be adequately represented in the compressed representation. It has therefore been proposed that areas of an image containing significant detail should be represented by relatively small patches whilst areas containing relatively little or no detail should be represented by larger patches. This process involves temporarily reconstructing an image using the first level large patches identified from the codebook. This provides a reference image which can be improved in a stepwise manner. It will be appreciated that this temporary image represents a decompressed version of the `compressed` image. In order to identify areas of detail which require representation by smaller patches, after each new large reference patch is added to the compressed image, the corresponding temporary image is compared against the original image to identify the region of the original image which maximally differs from the temporary image. The image patch containing this region is then sub-divided into smaller image patches and reference patches are identified from the codebook for these newly created image patches. Codebook indices and position vectors for the identified reference patches are then added to the compressed representation. The process is recursively repeated until either the temporary image reaches a desired quality level or the data size of the compressed representation reaches some maximum threshold level.
A problem with this maximum difference approach is that because the codebook is necessarily of a finite size, in certain circumstances it may be extremely difficult to find a close match for certain regions of an image. A considerable amount of processing time, and storage space in the compressed image, may be devoted to representing regions of the original image which, although identified as being poorly represented by the compressed image, can never be satisfactorily represented due to the limitations of the codebook.
It is an object of the present invention to overcome or mitigate at least one of the disadvantages of such known data compression processes.
It is another object of the invention to provide a data compression method and apparatus which optimises the quality of the compressed dat
REFERENCES:
patent: 4764975 (1988-08-01), Inoue
patent: 4788598 (1988-11-01), Ochi et al.
patent: 4797741 (1989-01-01), Sato et al.
patent: 5416606 (1995-05-01), Katayama et al.
patent: 5457495 (1995-10-01), Hartung
patent: 5732157 (1998-03-01), Osawa
patent: 5742704 (1998-04-01), Suzuki et al.
"Improved Hierarchical Vector Quantization For Image Compression", Ping Yu et al, pp. 92-95.
"Computation Bounded Vide Coding", Brofferio et al, pp. 199-205.
Cockshott Paul William
Fryer Richard John
Lambert Robert Bartholemew
McGregor Douglas Robert
Couso Jose L.
University of Strathclyde
LandOfFree
Data compression does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data compression will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1182720