Image analysis – Image compression or coding – Transform coding
Reexamination Certificate
1997-08-29
2002-09-24
Tran, Phuoc (Department: 2621)
Image analysis
Image compression or coding
Transform coding
C382S249000, C382S276000, C382S233000
Reexamination Certificate
active
06456743
ABSTRACT:
The present invention concerns, in general terms, a method and a device for the processing of data, notably the representation, generation, retrieval, regeneration or iterative processing of data.
More particularly, the present invention relates to the transmission (that is to say the remote representation) and/or the storage (that is to say the representation in a memory) of data, with or without compression thereof. These data can 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 multi-dimensional signal. More generally, the present invention relates to the representation of any mono or multi-dimensional data.
Before disclosing the objectives and means of the invention, it is proposed to give below the following definitions:
“Set of data”: set of any data representing physical quantities (usually voltage levels) which can themselves represent other physically perceptible or measurable quantities. In favoured mappings, the sets of data concerned are images, sound or mono or multi-dimensional signals, etc. In the mapping concerning the processing of images, reference will sometimes be made to the “image” instead of the “set of data” relating to the image. That which will be disclosed below with regard to “images” or “sub-images” is respectively applicable to “sets of data” or “sub-sets of data” and vice versa.
“Representation of data”: any “processing” of a set of data of a given type, resulting a perfect or imperfect transformation of the said set of data into another type. Example: the data can consist of the 256 grey levels of the pixels of an image, their representation consisting of a series of binary words able to be stored or transmitted; conversely, the representation of the data consisting of the said binary words can consist of their transformation in order once again to have 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 into data of a second type. In this case the term “primary processing” of the data will be used.
“Secondary representation”: by convention, the transformation of data of the second type resulting from a primary processing. In this case the term “secondary processing” will be used.
“Retrieval of data”: the particular case of a secondary representation in which the data of the second type are transformed into data of the first type. This retrieval can be perfect or imperfect.
A “metric space” is a set of elements provided with a functional distance which is symmetrical and positive and satisfies the triangular inequality. This space is “complete” when it contains all the limit points of all the convergent sequences.
A “Lipschitz mapping”: a mapping which transforms the points of a is metric space in the same space and for which all the ratios of the distance of two elements transformed by the said mapping to the distance of the said two elements are bounded.
A “contractive mapping” or “contraction”: a Lipschitz mapping for which the smallest of the majorants (contraction factor) of the said set of ratios is less than unity. However, within the meaning of the present invention, all convergent mappings (successive approximations) in a sub-set of the metric space are contractive.
A “similarity” is a Lipschitz mapping for which the ratio of the distance of two transformed elements to the distance of 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 of two transformed elements to the distance of the said elements is a fixed quantity strictly less than unity.
The “fixed point” of a contraction of a complete metric space in the same space (or of a sub-set of this space in itself) is the single element of the space which is left invariant by the said contractive mapping.
The “construction” of a contractive mapping on a set of data consists of constituting a family of contractions able to transform the data and select 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 desired. Starting from an arbitrary element, the said contraction is applied to this arbitrary element. The same contraction is then applied to the previously obtained transform. By reiterating this process the single fixed point of the contraction is successively and ineluctably approached.
“A best approximation” of an element in a metric space is a point of a sub-set 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 sub-set of the said space which is close with a predetermined error, to a predetermined best approximation.
In the prior art, various image representation methods, with compression, are known, using the so-called “fractal” technique.
Through the document U.S. Pat. No. 5,065,447, a method and a device are known for processing or storing an image with compression of the data relating to the initial image. In this method, the data relating to the initial image are divided, that is to say the image is cut into a plurality of elementary sub-images (referred to as “domain blocks”). This method then consists of generating an ordered dictionary of a set of reference sub-images (referred to as “range blocks”) formed from image portions of predetermined size which have undergone a certain number of predetermined operations such as rotation and turning on various axes of symmetry. Then, for each elementary sub-image, a comparison is carried out with all the reference sub-images of the dictionary and in the dictionary the reference sub-image is selected which is the most similar to the elementary sub-image in question. Finally, the method consists of processing or storing parameter information relating to the addresses of the reference sub-images selected in 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 effect, using the said parameter information, the retrieval of the initial image, the method and device described in this document perform the following operations: using 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 formed from the elementary sub-images thereof. However, the dictionary is formed only partially, performing for each sub-image only the predetermined operation corresponding to the relevant address of the dictionary of the sub-image in question.
The data thus obtained are used in order to reiterate this process until the difference between two consecutively obtained images is less than a predetermined threshold. The image lastly obtained is then an approximation of the initial image.
This method, which is interesting on a theoretical level, has the major drawback that it is sometimes difficult to put into practice on an industrial level with the means known at the present time. This is because each image must give rise to a long analysis with the formation of a particularly large dictionary, the elementary sub-images of the image to be stored or to be transmitted all being compared with each of the reference sub-images present in the dictionary. The inventors, who carried out simulations, found that, for certain images of average size and resolution (512×512 pixels with 3×256 colour levels), the processing time for the compression was of the order of 1000 to 2000 seconds on a workstation, that is to say around half an hour. Such a processing ti
Charrier Maryline
Dierieck Claude
Canon Kabushiki Kaisha
Fitzpatrick ,Cella, Harper & Scinto
Tran Phuoc
LandOfFree
Methods and devices for processing a set of data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and devices for processing a set of data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and devices for processing a set of data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2910739