Computer graphics processing and selective visual display system – Computer graphics processing – Attributes
Reexamination Certificate
2001-01-16
2003-11-04
Zimmerman, Mark (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Attributes
C382S282000, C382S249000, C707S793000
Reexamination Certificate
active
06642929
ABSTRACT:
CROSS REFERENCE TO RELATED APPLICATION
This application is a national phase of PCT/FR99/01402 which was filed on Jun. 14, 1999 and was published by the International Bureau in English on Dec. 23, 1999.
FIELD OF THE INVENTION
The invention relates to a method of searching for images, each one of which has been recorded in a data base in the form of a structured information index and in a way that favors a subsequent search for a specified element in the images of this data base.
A simple technique used to search for a specified detail in an image consists of consulting a catalogue that describes the image using text or using key words, but the drawing up of the catalogue takes time and it is not possible to guarantee that the images will be described with objectivity and that the details in which one will be interested in the future will be perceived at the time. Finally, the description will not generally be precise enough since the details will generally be identified by their category (building, vehicle, individual person, etc.) while in general a particular individual item will be asked for from this category, which will require examination of all the images in which this category of elements is present.
Another solution consists of looking for an object by describing its outline shape and its texture and looking for this in the data bank of images. It is then necessary to extract the corresponding information on digital modeling of the images broken down into points. Unfortunately, no extraction method exists for the outline or texture of an object which is effective in all cases, and these methods result in failure when the objects are partially masked or when they are illuminated to different extents in the sample provided for the search and in the image in which this sample must be discovered.
Another method consists of comparing the sample provided with each of the parts of each of the images, the comparison resting on the tints of the points of the sample and the points of the images. However, this method is impractical for a search that is at all large.
A final category of methods, to which the invention belongs, consists of modeling the images by means of an index that represents characteristics of the image. The sample to be looked for will be modeled in the same way in order to give an index in analog form and the comparison will rest on the indices. If a comparison is judged to be positive, the corresponding image will be extracted and examined.
Recently there has been much interest in the compression of images using their fractal properties, in order to provide indices which occupy little memory space while permitting subsequent reconstruction of an image of satisfactory quality; these indices can, as will be seen, be used in the invention for comparisons leading to the search for samples provided that certain precautions are taken when they are drawn up.
A fractal object has the property of being identical to its parts: if a fragment of it is isolated and enlarged, it is found to be identical to the initial object. The image of a fractal object can be obtained by applying certain geometrical transformations repeatedly to a starting image, which is then deformed to converge towards the image of the fractal object that is called the attractor of the geometric transformation. The starting image can be chosen in any fashion whatsoever.
Normal images are not fractal images, but it is nevertheless possible to find quite simple geometrical transformations for which these images are attractors. The image can then be reconstituted by simply knowing an index that expresses these geometric transformations and applying these transformations several times to any starting image whatsoever: it is then enough to simply record the index in the data base, without it being necessary to record the image itself in digital form, which would take up much more space.
In practice, the geometric transformations are determined by dividing the image into sectors or ranges and making a domain of the same image, that is to say another part of the image, correspond to each of these ranges. In practice, this other part of the image has a greater surface area since suitable geometric transformations should contract or shrink the details on which they act. The correlations by which the ranges and the domains are made to relate to one another are chosen so that the domains resemble the ranges with which they are associated, that is to say that they have a similar appearance once they have possibly had certain modifications made to them, modifications of luminosity, contrast and color, or modifications of shape through rotation or through symmetry.
It is essential that the indices of the images and the samples in these images to be looked for, are at least partially composed in the same way, that is to say that homologous ranges are related to homologous domains, so that they are comparable. With regard to this, an important risk is linked to the sizes of the image and the sample which are often very different the domains and ranges that are made to correspond in the sample through a fractal transform are generally close to one another, while in a large size image they can be much further apart; corresponding ranges of the sample and the image will then be associated with different domains, that of the index and the image being outside the sample if precautions have not been taken.
It is not then possible for corresponding parts of the sample and image indices to be identical, and the search will be unfruitful if this circumstance occurs too often. With regard to this, one should make it clear that the domains associated with one and the same range by the indices of the sample and the image are chosen arbitrarily in most of the known methods, which means that these domains are generally different in any case and that the presence of the sample in the image should be taken as being probable if just a few fragments of their indices are identical. However the disadvantages of this situation are much more accentuated if the problem indicated above has not been resolved.
French patent application No. 96.11751 of the Sep. 26, 1996 provides one solution: a decision is made to limit the distance between each of the ranges of the images and the domains which are respectively associated with them through the index. This enables one to associate a specified range with identical domains of the image and of the sample with greater probability. The risks of an unfruitful comparison of the indices when the sample is indeed present in the image being examined are thereby reduced.
However, other risks of failing to make a comparison are not avoided by proceeding in this way: since the geometric transformations are normally defined by Cartesian co-ordinates which express the distance between the ranges and the domains related to them, the comparison will not be possible if the sample and the image are viewed from different angles and therefore have different co-ordinate axes. It is also necessary to ensure that the division of the sample and the image into domains and ranges are comparable without dividing up the image or the sample in too arbitrary a fashion, that is to say by avoiding splitting the essential details or by associating very different portions of elements inside one and the same domain or one and the same range.
BRIEF DESCRIPTION OF THE INVENTION
The invention has been designed to remedy these difficulties. It consists of combining certain techniques of the art of modeling images—some of which are known individually—with a method of composing the index, the idea of which resembles that of the previous application but which is less arbitrary and more methodical, so as to construct the indices in a substantially invariant fashion, that is to say independent of any interference which could affect the image. Hence, the indices of the sample to be looked for and the images in which it is present will resemble one another even if the images have been subject to noise and if the sample does not appear in
Essafi Hassane
Marie-Julie Jean-Michel
Cao Huedung X.
Krebs Robert E.
Thelen Reid & Priest LLP
Zimmerman Mark
LandOfFree
Image search method, based on an invariant indexation of 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 Image search method, based on an invariant indexation of the..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image search method, based on an invariant indexation of the... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3154256