Image analysis – Image compression or coding – Transform coding
Reexamination Certificate
1998-08-24
2002-12-24
Couso, Yon J. (Department: 2623)
Image analysis
Image compression or coding
Transform coding
C348S395100
Reexamination Certificate
active
06498866
ABSTRACT:
The present invention concerns, in general terms, a method and device for processing data, notably the representation, generation, restitution, regeneration or iterative processing of data.
More particularly, the present invention relates to the transmission (that is to say the representation at a distance) 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 in 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.
Before disclosing the objectives and means of the invention, it is proposed below to give 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 applications, the sets of data concerned are images, sound or mono or multidimensional signals, etc. In the application relating to image processing, 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 from the perfect or imperfect transformation of the said set of data into another type. For example: the data can consist in 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 in their transformation in order to regain data of the same type as the initial data.
“Primary representation”: by convention, any processing resulting from the transformation of the data of a first type to data of a second type. In this case a “primary processing” of the data will be spoken of.
“Secondary representation”: by convention, the transformation of data of the second type resulting from a primary processing. In this case a “secondary processing” will be spoken of.
“Restitution 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 restitution can be perfect or imperfect.
A “metric space” is a set of elements with a functional distance 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 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 two said elements is limited.
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 the convergent mappings, that is to say those having a fixed point (thus enabling successive approximations to be used) 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 sole element which is left invariant by the said contractive mapping.
The “construction” of a contractive mapping on a set of data consists in forming a family of contractions able to transform 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 approach, iteratively, as close as wished, the fixed point of a contraction. Starting from an arbitrary element, the said contraction is applied thereto. The same contraction is then applied to the previously obtained transform. By reiterating this process, the fixed point of the contraction is approached successively and ineluctably.
“A better approximation” of an element in a metric space is a point in a sub-set of candidates, which are themselves points in the said space, which minimises the distance to the said element.
“A good approximation” of an element in a metric space is a point in a sub-set in the said space which is close, with a predetermined error, to a predetermined best approximation.
Various image representation methods, with compression, using the fractal technique, are known in the state of the art.
Through the document U.S. Pat. No. 5,065,447, a method and 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 divided into a plurality of elementary sub-images (referred to as “domain blocks”). This method next consists in generating an ordered dictionary of a set of reference sub-images (referred to as “range blocks”) formed from portions of an image of predetermined size which has undergone a certain number of predetermined operations such as rotation and turning about various axes of symmetry. Next, for each elementary sub-image a comparison is made with all the reference sub-images of the dictionary and the reference sub-image which is the most similar to the elementary sub-image under consideration is selected from the dictionary. Finally, the method consists in 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 effect, from the said parametric information, the restitution of the initial image, the method and device described in this document perform the following operations: from an initial arbitrary image, steps similar to those above are carried out, that is to say the initial arbitrary 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 for the position of the sub-image under consideration.
The data thus obtained are used for reiterating this process until the difference between two consecutively obtained images is less than a predetermined threshold. The image obtained lastly is then an approximation of the initial image.
This method, which is of interest 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 necessarily involves a lengthy analysis with the creation of a particularly large dictionary, the elementary sub-images of the image to be stored or transmitted all being compared with each of the reference sub-images present in the dictionary. The inventors, who carried out simulations, thus found that, for certain images of average size and resolution (512×512 pixels with 3×256 colour levels), the processing time for compression was around 1000 to 2000 seconds on a workstation, that is to say around half an hour. Such a processing time is obviously prohibitive for almost any industrial application.
Throug
Amonou Isabelle
Charrier Maryline
Dierieck Claude
Henry Felix
Canon Kabushiki Kaisha
Couso Yon J.
Fitzpatrick ,Cella, Harper & Scinto
LandOfFree
Methods and devices for processing data and notably for... 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 data and notably for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and devices for processing data and notably for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2931364