Image analysis – Image compression or coding – Transform coding
Reexamination Certificate
1998-03-24
2001-07-24
Couso, Yon J. (Department: 2721)
Image analysis
Image compression or coding
Transform coding
C382S248000
Reexamination Certificate
active
06266451
ABSTRACT:
The present invention concerns, in general terms, a method and a device for the processing of data, notably the representation, generation, restoration, regeneration or iterative processing of data.
More particularly the present invention relates to the transmission (that is to say the representation remotely) and/or the storage (that is to say the representation in a memory) of data, with or without their compression. These data may advantageously consist of the digital or analogue data of an image or sequence of images, and/or the digital or analogue data relating to sound (music, speech, etc), and/or the digital or analogue data relating to any mono or multidimensional signal. More generally, the present invention relates to the representation of any mono or multidimensional data.
Before explaining the objectives and means of the invention, the following definitions are given below:
“Set of data”: set of any data representing physical quantities (most often voltage levels) themselves capable of representing other physically perceptible or measurable quantities. In favoured mappings, the sets of data concerned are of images, sound or mono or multidimensional signals, etc. In the mapping concerning image processing, the “image” will sometimes be referred to instead of the “set of data” relating to the image. That which will be explained below about “images” or “sub-images” is respectively applicable to the “sets of data” or “subsets of data” and vice versa.
“Representation of data”: any “processing” of a set of data of a given type, resulting in the perfect or imperfect transformation of the said set of data into another type. For example: the data may be constituted by the 256 levels of grey of the pixels of an image, their representation consisting of a series of binary words capable of being stored or transmitted; conversely, the representation of the data constituted by the said binary words may consist of their transformation in order to regain data of the same type as the initial data.
“Primary representation”: by convention, any processing resulting in the transformation of data of a first type to data of a second type. In this case “primary processing” of the data will be referred to.
“Secondary representation”: by convention, the transformation of data of the second type resulting from primary processing. In this case “secondary processing” will be referred to.
“Data restoration”: a particular case of secondary representation in which the data of the second type are transformed into data of the first type. This restoration may be perfect or imperfect.
A “metric space” is a set of elements equipped with a distance functional which is symmetrical, positive and satisfies triangular inequality. This space is “complete” when it contains all the limit points of all the convergent series.
A “Lipschitz mapping”: a mapping which transforms the points of a metric space into the same space and for which the set of ratios of the distance between two elements transformed by the said mapping, over the distance between the two said elements, is bounded.
A “contractive mapping ” or “contraction”: a Lipschitz mapping for which the smallest majorant (contraction factor) of the said set of ratios is less than unity. However, within the meaning of the present invention, all convergent mappings, that is to say those having a fixed point (thus allowing the use of successive approximations) in a subset of the metric space, are contractive.
A “similarity” is a Lipschitz mapping for which the ratio of the distance between two transformed elements over the distance between the said elements is a fixed quantity. A linear similarity is a “similitude”.
A “contractive similarity” is a Lipschitz mapping for which the ratio of the distance between two transformed elements over the distance between the said elements is a fixed quantity strictly less than unity.
The “fixed point” of a contraction of a complete metric space into the same space (or of a subset of that space into itself) is the unique element which is left invariant by the said contractive mapping.
The “construction” of a contractive mapping on a set of data consists of composing a family of contractions capable of transforming the data and selecting the parameters of one of the said contractions in order to satisfy one or more predetermined conditions.
The “method of successive approximations ” makes it possible to iteratively approach the fixed point of a contraction as close as is wished. Starting from an arbitrary element, the said contraction is applied on this element. The same contraction is next applied on the previously obtained transform. By reiterating this process, the fixed point of the contraction is approached successively and inescapably.
“A better approximation” of an element in a metric space is a point from a subset of candidates, which are themselves points of the said space, which minimises the distance to the said element.
“A good approximation” of an element in a metric space is a point of a subset of the said space which is close, with a predetermined error, to a predetermined better approximation.
Various methods of image representation, with compression, using the so-called “fractal” technique, are known in the prior art.
Through the document U.S. Pat. No. 5,065,447, a method and a device allowing the processing or storage of images with compression of the data relating to the initial image are known. In this method, the data relating to the initial image are divided, that is to say the image is cut up into a plurality of elementary sub-images (called “domain blocks”). This method next consists of generating an ordered dictionary of a set of reference sub-images (called “range blocks”) composed of image portions of predetermined size which have undergone a certain number of predetermined operations such as rotation and reversal along various axes of symmetry. Next, for each elementary sub-image, a comparison with the set of reference sub-images in the dictionary is carried out and the reference sub-image the most similar to the elementary sub-image under consideration is selected from the dictionary. Finally, the method consists of processing or storing parametric information relating to the addresses of the reference sub-images selected from the dictionary, in order to represent each of the original elementary sub-images.
It is through this set of operations that the method described in this document makes it possible to obtain a first representation of the image with compression of the data.
In order to carry out, from the said parametric information, the restoration of the initial image, the method and device described in this document perform the following operations: from an arbitrary starting image, steps similar to those above are carried out, that is to say the arbitrary starting image is partitioned and a dictionary is composed from its elementary sub-images. However, the dictionary is only partially composed, performing, for each sub-image, only the predetermined operation corresponding to the address concerned in the dictionary for the position of the sub-image under consideration.
The data thus obtained are used to reiterate this process until the difference between two consecutively obtained images is less than a predetermined threshold. The image obtained last of all is then an approximation of the initial image.
This method, of interest theoretically, has the major drawback that it is sometimes not easily practicable industrially with the means known at present. This is because each image must lead to a long analysis with composition of a particularly large dictionary, the elementary sub-images of the image to be stored or transmitted all being compared with each reference sub-image present in the dictionary. The inventors, who have carried out simulations, thus noted that for certain images of average size and resolution (512×512 pixels with 3×256 colour levels), the processing time for compression was of the order of 1000 to 2000 seconds on a work station, that is of the order of h
Amonou Isabelle
Charrier Maryline
Dierieck Claude
Canon Kabushiki Kaisha
Couso Yon J.
Fitzpatrick ,Cella, Harper & Scinto
LandOfFree
Method and device for the processing of data notably the... 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 device for the processing of data notably the..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and device for the processing of data notably the... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2461759