Image analysis – Image transformation or preprocessing – Image storage or retrieval
Reexamination Certificate
1997-09-12
2001-05-08
Boudreau, Leo (Department: 2621)
Image analysis
Image transformation or preprocessing
Image storage or retrieval
C382S249000
Reexamination Certificate
active
06229931
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to a process for the search for samples in images of a data base. Interest is here attached to the automatic search for a particular detail within a collection of images recorded in a data base.
2. Description of the Related Art
A simple solution consists of describing the images by a text or by keywords and checking the catalogue resulting from this description. The disadvantage of this very simple method is that it requires time for creating the catalogue and it is not possible to describe the images with sufficient precision or objectivity, particularly as the object of the search is not always known at this time and important elements of images would be neglected. Moreover, an element such as a building, vehicle, person, etc. will generally be described by the category of which it forms part and will consequently only be identified following a visual examination of the image in order to establish whether it does correspond to the sample. Thus, this method is not very practical for numerous data.
Another solution consists of seeking an object by describing its contour or texture and investigating it in the image data bank. For this purpose it is necessary to have digitally analyzed the images in order to extract the corresponding informations therefrom. Unfortunately there is no method for the extraction of a contour or texture of objects which is effective in all cases and such methods fail when the objects are partly masked or in the shade, or when they are differently illuminated on the sample and on one of the images
Another possible method consists of comparing the sample with different parts of the images. The comparison is positive when the points of an image fragment have the same shade as the sample points. However, the calculation times are very long due to the number of comparisons which have to be made and the method also becomes inoperative if the sample is present with a different size or orientation on the images.
SUMMARY OF THE INVENTION
The invention is based on a different method involving the com-pression of images and samples in accordance with their fractal properties.
A fractal object has the property of being identical in its parts. On isolating therefrom a fragment which is enlarged, it is found to be identical to the initial object. The image of a fractal object can be obtained by means of certain geometrical transformations applied in repeated manner to a starting image, which is deformed and converges towards the fractal object, which is called the geometrical transformation attractor. Although conventional images are not really fractal objects, it is possible to define geomet-rical transformations of which these images are attractors. The image can then be reconstituted by applying these transformations several times to a random starting image. It is then only necessary to record the geometrical characteristics of the transformation. Thus, these transformations are determined by dividing the image into ranges and making correspond a domain or area of the same image, i.e. another part of the image having the same shape but a larger surface to each of the ranges. Thus, geometrical transformations able to produce an attractor are contracting, i.e. the details on which they act become smaller. The correspondences by which the ranges and domains are related are chosen so that the domains resemble the sectors with which they are associated, i.e. they have a similar aspect once there has been a possible imposition thereon of certain modifications of brightness, contrast, rotation or symmetry.
It is thus sufficient to record the image in the form of digital data relative to the transformations producing the same and illustrated by equation (1) W
i
=(Y
i
x
i
y
i
tx
i
ty
i
s
i
o
i
). In reality, it is the writing of a transformation Wi in vector form, where Yi is a value designating an isometry among a previously documented list for passing from the domain to the associated range, such as a rotation, reflection, symmetry or scale modification, xi and yi being domain position coordinates, txi and tyi translation coordinates for passing from the domain to the associated range and si and oi are contrast and brightness coefficients making it possible to modify the grey levels in the domain to obtain those of the associated range. The contrast coefficient si makes it possible to regulate the difference of the grey levels of points of a range by modifying the equivalent difference among the points of the domain associated therewith. The brightness coefficient oi makes it possible to lighten or darken the range with respect to the domain. All the transformations form an index of the image. As the number of vectors is equal to the relatively small number of ranges of the image, the index occupies a much smaller memory volume than if the image had been completely recorded, in the form of a colour or a grey level associated with each of its points.
A specific example provides more detailed information.
FIG. 1
shows an image, formed by a mosaic of two colours, showing a division into square ranges, numbered according to horizontal rows from R
0
to R
63
using a grid.
FIG. 2
shows a division of the same image into sixteen domains, numbered from D
0
to D
15
and whereof each has the surface of four ranges and, like the latter, a square shape.
This simply shaped image makes it possible to easily relate the domains and ranges. Thus, the completely white ranges R
0
, R
1
, R
4
, R
5
, etc. have a physionomy identical to an entirely white domain such as D
0
(or e.g. D
3
or D
14
). The entirely black ranges such as R
2
and R
3
could be related with a completely black domain such as D
1
or D
13
, but could also be related with domain D
0
, which has the same appearance to within a brightness change. The ranges such as R
18
and R
27
which are partly black and white in accordance with a diagonal will be related with the domain D
5
of the same appearance and R
35
, R
42
, R
49
and R
56
with D
9
for the same reason. Sector R
12
will be related with domain D
11
, which has the same appearance, excepting a quarter turn rotation.
All these correspondence relations can be in the form of a graph, part of which is shown in FIG.
3
. Specifically the application of the equations (1) consists, starting from an initial image on which are shown the domains D
0
to D
15
, constructing a new image on which is documented for each of the ranges R
0
to R
63
, the content of the domain associated with the initial image after applying thereto the necessary scale change and optionally modifications of brightness, orientation, etc. defined by the transformation wi. By repeating these operations, there will be a convergence towards the image of
FIG. 1
, no matter what the initial image.
The invention consists of applying this already known method of compression images in the form of geometrical transformations expressing their fractal properties to the search for samples on these images. In its most general form, it consists of applying the same compression method to samples in order to obtain other numerical indexes, of the same nature as those of the images, and appropriately comparing the indexes of the samples with the indexes of the images in order to establish whether the samples are present on the images. However, certain precautions must be taken to ensure that the comparison can in fact be made. It is in particular appropriate for the fragments (domains and ranges) brought into a similarity relationship in the image indexes are not further removed than a limit commensurate with the dimensions of the samples.
REFERENCES:
patent: 4789933 (1988-12-01), Chen et al.
patent: 5384867 (1995-01-01), Barnsley et al.
patent: 5701369 (1997-12-01), Moon et al.
patent: 5768437 (1998-06-01), Monro et al.
patent: 5781899 (1998-07-01), Hirata
patent: 5809169 (1998-09-01), Rezzouk et al.
Patent Abstracts of Japan, vol. 95, No. 3, Apr. 28, 1995, JP 06-343140, Dec. 13, 1994.
Robert Bonneau, SPIE, vol. 256
Essafi Hassane
Marie-Julie Jean Michel
Boudreau Leo
Commissariat A l'Energie Atomique
Oblon, Spivak, McClelland, Maier & Neustadt, P.C
Patel Kanji
LandOfFree
Process for the search of samples in images of a data base does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Process for the search of samples in images of a data base, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Process for the search of samples in images of a data base will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2451010