Device, storage medium and a method for detecting objects strongly resembling a given object

• US 20030109940A1
• Filed: 10/30/2002
• Published: 06/12/2003
• Est. Priority Date: 02/08/2000
• Status: Abandoned Application

• Current Assignee: Ulrich Guntzer, Werner Kiessling, Wolf-Tilo Balke
• Original Assignee: Ulrich Guntzer, Werner Kiessling, Wolf-Tilo Balke
• Inventors: Balke, Wolf-Tilo, Guntzer, Ulrich, Kiessling, Werner
• Application Number:
  US10/203,482
• Publication Number:
  US 20030109940A1
• Time in Patent Office: Days
• US Class Current: 700/52
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06F 16/5862 using texture
• CPC Class Codes: G06F 16/90335 Query processing

Abstract

Methods are described with which, from a large number of objects and in an efficient way, a search can be made for the objects which best resemble a sample object. For this purpose, the number of objects to be considered is restricted via efficiently calculated limiting values. In addition, the methods have search strategies which use the values of the characteristics of the objects considered for an efficient search strategy.

Claims

1. A method of determining from a large number of objects a predefinable number k of objects which best resemble a predefined sample object with regard to a plurality of characteristics, in which a combination function for assessing the characteristics is predefined, a number of objects whose values are greatest for the characteristic being selected for each characteristic, characterized in that,

for each selected object, a value index is calculated by using the values of the characteristic and the combination function, and in that for the selection of the most similar objects, only those objects whose value index lies above a predefinable comparison index are considered.

5. The method as claimed in claim 1, characterized in that the comparison index is calculated with the combination function, the respective smallest value of a characteristic which has occurred in the selected objects being used.

6. The method as claimed in one of claims 1 to 5, characterized in that for the selected objects for which a value of a characteristic is not yet known, an estimate is made by means of the smallest value of the characteristic which a selected object has.

7. The method as claimed in one of claims 1 to 6, characterized in that the number of selected objects whose values of the characteristics are completely known corresponds at least to the number k of objects sought before a decision about the best objects is made.

14. An apparatus, in particular a computer system, for carrying out a method as claimed in one of claims 1 to 13.

15. A storage medium which contains data which can be read and executed by a computer, characterized in that the data describes a method as claimed in one of claims 1 to 13.

2. A method of determining from a large number of objects a predefinable number k of objects which best resemble a predefined sample object with regard to a plurality of characteristics, a combination function for assessing the characteristic being predefined, for each characteristic a number of objects being selected whose values for the characteristic are greatest, characterized in that,

for each selected object, a value index is calculated by using the value of the characteristic and the combination function,

in that by using the value of the characteristic of the selected objects and the combination function, a limiting value for the value of the characteristic is calculated,

and in that for the further selection of the most similar objects, the objects from the large number of objects and from the set of selected objects are considered whose value of the characteristic lies above the calculated limiting value.

3. The method as claimed in claim 2, characterized in that in order to calculate the limiting value, the values of the characteristics of the selected object which has the smallest value index are used.

4. The method as claimed in claim 3, characterized in that in order to calculate the limiting values (S_xi), the following system of equations with n equations for the combination function F is solved:

8. A method of determining from a large number of objects a predefinable number k of objects which correspond to a predefined sample object with the greatest similarity with regard to a plurality of characteristics, a combination function being predefined for the assessment of the characteristics, having the following method steps:

1) for each characteristic, a predefinable number of objects is selected which have the highest values for the characteristic,

2) for each selected object, the values of the characteristics which are not yet known for the object are determined,

3) for each selected object, by using the values of the characteristics, a value index is determined with the combination function F,

4) the value indices of the selected objects are compared with a predefined comparison index,

5) the objects whose value indices is greater than the comparison index are output as the result,

6) if, following this comparison, k objects have not yet been output, then for a characteristic a new object is selected which has the greatest value of the characteristic and which has not yet been selected for this characteristic, and the procedure is then continued with method step 2,

7) method steps 2 to 7 are executed until k objects are known whose value indices is greater than the comparison index.

9. The method as claimed in claim 8, characterized in that for all the characteristics, the respectively smallest value of a selected object is determined, and in that the comparison index is determined with the combination function by using the smallest values.

10. The method as claimed in either of claims 8 and 9, characterized in that for each characteristic a change value is determined which represents a measure of the decrease in the value of the characteristic over the sequence of the objects, and in that in method step 7, from the characteristic, a new object which has the greatest change value and has not yet been selected for this characteristic is selected.

11. The method as claimed in one of claims 8 to 10, characterized in that,

after method step 7 and before method step 2, the smallest values of the selected objects are determined for the characteristics,

in that from the determined smallest values of the characteristics, by using the value of the newly selected object, a comparison index is determined with the combination function,

in that the value indices of the selected objects are compared with the comparison index,

in that the objects whose value indices is greater than the comparison index are output as the result and

in that processing continues with method step 2 if k objects have not yet been output.

12. A method of determining from a large number of objects a predefinable number k of objects which correspond to a predefined sample object with the greatest similarity with regard to a plurality of characteristics, a combination function being predefined for the assessment of the characteristics, having the following method steps:

1) for each characteristic, a predefinable number of objects is selected which have the highest values for the characteristic,

2) for each selected object, all the predefined characteristics which have not been found in method step 1 are estimated by using the lowest value which a selected object has for the corresponding characteristic,

3) for each selected object, by using the values for the known and the estimated characteristics, a value index is determined in accordance with the combination function,

4) if a number k of objects is known in terms of all characteristics, then those objects are discarded of which at least one value of a characteristic is estimated and whose value index is less than the smallest value index of a known object, and a branch is then made to method step 6,

5) if a number k of objects is not known in terms of all characteristics, then a new object for at least one characteristic is selected and a branch is made to method step 2,

6) if a number of k objects is known in terms of all characteristics, then a new value of a characteristic which is greatest for the characteristic and has not yet been selected is selected, a check is then made to see whether the object whose value has been selected has already been selected for another characteristic, if this is so, then the procedure is continued with program step 7, if this is not so, then the newly selected value is discarded and method step 6 is repeated,

7) if, during the expansion according to method step

     6), all the values of the characteristics of a selected object are known, then the completely known object with the smallest value index is discarded,

8) furthermore, that object is removed whose value index is not completely known and whose value index is less than the smallest value index of the objects whose values are known for all characteristics,

9) method steps 6 to 8 are run through until for k selected objects, all characteristics are known without estimated values and whose value indices are greater than the largest value index of an incompletely known object.

13. A method of determining from a large number of objects a predefinable number k of objects which correspond to a predefined sample object with the greatest similarity, at least one characteristic being predefined for the sample object and a combination function being predefined for the assessment of the characteristic, having the following method steps:

1) for each characteristic, a predefinable number of objects is selected which have the highest values for the characteristic, until at least the number k of objects are known in terms of all the characteristics considered,

2) for each selected object, by using the values for the characteristics, a value index is determined with the combination function,

3) the smallest object with the smallest value index is determined,

4) from the values of the characteristics of the smallest object or from the smallest values of the characteristics stored in the results list, limiting values for the characteristics are determined via the combination function,

5) all objects whose values for the characteristics lie above the limiting values are additionally selected,

6) from the selected objects, the number k of objects whose value index are the greatest is selected.