Method and device for determining a similarity of measure between a first structure and at least one predetermined second structure

• US 6,868,181 B1
• Filed: 07/01/1999
• Issued: 03/15/2005
• Est. Priority Date: 07/08/1998
• Status: Expired due to Fees

• Current Assignee: Siemens AG
• Original Assignee: Siemens AG
• Inventors: Feiten, Wendelin, Rencken, Wolfgang
• Primary Examiner(s): Patel, Kanjibhai
• Assistant Examiner(s): STREGE, JOHN B
• Application Number:
  US09/743,430
• Time in Patent Office: 2,084 Days
• Field of Search: 382/181, 382/195, 382/153, 382/215, 382/216, 701/28, 348/119
• US Class Current: 382/181
• CPC Class Codes: G05B 2219/31007 Floor plan, map stored in on-board computer of vehicle
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]

Abstract

At least one base element is defined for structures, and surroundings-related information is assigned to each of these base elements. The surroundings-related information characterizes the corresponding base element. A measure of similarity is determined for the structures, the determination being effected in a manner dependent on the base elements and also on the surroundings-related information assigned to the base elements.

Claims

1. A method for the computer-aided determination of a measure of similarity between a first structure and at least one predetermined second structure, comprising the steps of:

defining at least one base element for said first structure and said second structure;

assigning surroundings-related information to each of said at least one base elements, said surroundings-related information characterizing a corresponding said base element;

determining a measure of similarity, which describes a similarity between said first structure and said second structure, for said first structure and said second structure, said measure of similarity being determined in a manner dependent on said base elements and on said surroundings-related information assigned to said base elements;

forming said surroundings-related information by further base elements and their geometrical arrangement relative to said at least one base element;

grouping further base elements into a plurality of surroundings-related information types containing surroundings-related information features which are each assigned to a surroundings-related information type;

sorting said surroundings-related information features assigned to a surroundings-related information type in a predeterminable manner in a list; and

storing said sorted said surroundings-related information features.

2. The method as claimed in claim 1, further comprising the step of including a plurality of base elements within said first structure or said second structure.

3. The method as claimed in claim 1, further comprising the step of including said first structure and said second structure in at least one map.

4. The method as claimed in claim 3, further comprising the step of using a recorder to record said at least one map.

5. The method as claimed in claim 4, wherein said recorder is a scanner.

6. The method as claimed in claim 4, wherein said recorder is a camera.

7. The method as claimed in claim 1, wherein said step of determining a measure of similarity encompasses a plurality of base elements and their respectively assigned surroundings-related information.

8. The method as claimed in claim 1, wherein at least a portion of said at least one base element is a line of predeterminable form.

9. The method as claimed in claim 8, wherein at least a portion of said at least one base element is a section.

10. The method as claimed in claim 1, wherein at least a portion of said at least one base element is a point.

11. The method as claimed in claim 1, wherein base elements have different forms.

12. The method as claimed in claim 3, further comprising the step of forming at least a portion of said surroundings-related information in such a way that it is invariant with respect to errors which occur when constructing said at least one map.

13. The method as claimed in claim 1, wherein said measure of similarity is determined with dynamic programming.

14. The method as claimed claim 1, further comprising the step of operating on a plurality of further structures, a measure of similarity between said first structure and a respective further structure being determined in each case.

15. The method as claimed in claim 14, further comprising the step of implementing said method repeatedly for different base elements, thus forming a plurality of measures of similarity.

16. The method as claimed in claim 14, further comprising the steps of:

selecting base elements of said first structure and of said further structures which have the greatest correspondence;

forming a local coordinate system in each case proceeding from said selected base elements in each structure;

forming a mapping measure in a manner dependent on a mapping of said coordinate system of said first structure onto a coordinate system of said second structure;

determining a structure which has the smallest mapping measure in a manner dependent on said mapping measure.

17. The method as claimed in claim 16, wherein said mapping measure describes a rotation of said local coordinate system from said first structure onto said respective further structure.

18. The method as claimed in claim 1, wherein said first structure or said second structure describes data structures in a database.

19. The method as claimed in claim 1, wherein said first structure or said second structure describes a physical object.

20. The method as claimed in claim 1, wherein said first structure describes a physical object and said second structure describes a model of a physical object.

21. The method as claimed in claim 1, further comprising the step of determining a map for a mobile autonomous apparatus.

22. The method as claimed in claim 1, further comprising the step of orientating a mobile autonomous apparatus.

23. The method as claimed in claim 21, wherein said mobile autonomous apparatus is a robot.

47. The method as claimed in claim 22, wherein said mobile autonomous apparatus is a robot.

24. An arrangement for the computer-aided determination of a measure of similarity between a first structure and at least one predetermined second structure, comprising:

a processor configured to;

define at least one base element for said first structure and said second structure;

assign surroundings-related information to each base element, said surroundings-related information characterizing a corresponding base element;

determine a measure of similarity, which describes a similarity between said first structure and said second structure, for said first structure and said second structure, said measure of similarity being determined in a manner dependent on said at least one base element and on said surroundings-related information assigned to said respective base elements;

operate on said further base elements that are grouped into a plurality of surroundings-related information types containing surroundings-related information features which are each assigned to a surroundings-related information type;

the arrangement further comprising;

further base elements and their geometrical arrangement relative to said base elements that form said surroundings-related information; and

a memory, in which said surroundings-related information features assigned to a surroundings-related information type are stored having been sorted in a predeterminable manner in a list.

25. The arrangement as claimed in claim 24, wherein a plurality of base elements are contained in said first structure or said second structure.

26. The arrangement as claimed in claim 24, wherein said first structure or said second structure is contained in at least one map.

27. The arrangement as claimed in claim 26, further comprising a recorder for recording said at least one map.

28. The arrangement as claimed in claim 27, wherein said recorder is a scanner.

29. The arrangement as claimed in claim 27, wherein said recorder is a camera.

30. The arrangement as claimed in claim 24, wherein said measure of similarity is determined based on a plurality of base elements and their respectively assigned surroundings-related information.

31. The arrangement as claimed in claim 24, wherein said processor is configured to operate on said at least one base element that is a line of predeterminable form.

32. The arrangement as claimed in claim 31, wherein said processor is configured to operate on at least a portion of said at least one base element that is a section.

33. The arrangement as claimed in claim 24, wherein said processor is configured to operate on at least a portion of said at least one base element that is a point.

34. The arrangement as claimed in claim 24, wherein said processor is configured to operate on base elements having different forms.

35. The arrangement as claimed in claim 24, wherein said processor is configured to operate on at least a portion of said surroundings-related information that is formed in such a way that it is invariant with respect to errors which occur when constructing a map.

36. The arrangement as claimed in claim 24, wherein said processor is configured to utilize dynamic programming to form said measure of similarity.

37. The arrangement as claimed in claim 24, wherein said processor is configured to process a plurality of further structures, a measure of similarity between said first structure and a respective further structure being determined in each case.

38. The arrangement as claimed in claim 37, wherein said processor operates repeatedly on different base elements, and forms a plurality of respective measures of similarity.

39. The arrangement as claimed in claim 37, wherein said processor is configured to:

select base elements of said first structure and of said further structures which have the greatest correspondence;

form a local coordinate system in each case proceeding from said selected base element in each structure;

form a mapping measure in a manner dependent on a mapping of said coordinate system of said first structure onto said coordinate system of said second structure; and

determine a structure which has the smallest mapping measure in a manner dependent on said mapping measure.

40. The arrangement as claimed in claim 39, wherein said mapping measure describes a rotation of said local coordinate system from said first structure onto a respective further structure.

41. The arrangement as claimed in claim 24, wherein said structures describe data structures in a database.

42. The arrangement as claimed in claim 24, wherein said structures each describe a physical object.

43. The arrangement as claimed in claim 24, wherein said first structure describes a physical object and said second structure describes a model of a physical object.

44. The arrangement as claimed in claim 26, wherein said map is utilized for a mobile autonomous apparatus.

45. The arrangement as claimed in claim 26, wherein said arrangement orients a mobile autonomous apparatus.

46. The arrangement as claimed in claim 44, wherein said mobile autonomous apparatus is a robot.

48. The arrangement as claimed in claim 34, wherein said processor is configured to operate on said further base elements that are grouped into a plurality of surroundings-related information types containing surroundings-related information features which are each assigned to a surroundings-related information type.

49. The arrangement as claimed in claim 35, wherein said processor is configured to operate on said further base elements that are grouped into a plurality of surroundings-related information types containing surroundings-related information features which are each assigned to a surroundings-related information type.

50. The arrangement as claimed in claim 48, further comprising:

a memory, in which said surroundings-related information features assigned to a surroundings-related information type are stored having been sorted in a predeterminable manner in a list.

51. The arrangement as claimed in claim 49, further comprising:

a memory, in which said surroundings-related information features assigned to a surroundings-related information type are stored having been sorted in a predeterminable manner in a list.

52. The arrangement as claimed in claim 45, wherein said mobile autonomous apparatus is a robot.