Apparatus and method for the construction of spatial representantions

• US 20030179922A1
• Filed: 11/13/2002
• Published: 09/25/2003
• Est. Priority Date: 10/30/2000
• Status: Active Grant

• Current Assignee: Barry J. Drake, Mark W. Peters
• Original Assignee: Barry J. Drake, Mark W. Peters
• Inventors: Peters, Mark W., Drake, Barry J.
• Granted Patent: US 7,483,571 B2
• Time in Patent Office: Days
• US Class Current: 382/153
• CPC Class Codes: G06T 7/70 Determining position or orientation of objects or cameras camera calibration G06T7/80
• CPC Class Codes: G06T 7/80 Analysis of captured images to determine intrinsic or extrinsic camera parameters, i.e. camera calibration
• CPC Class Codes: Y10T 74/12 Gyroscopes
• CPC Class Codes: Y10T 74/1275 Electrical

Abstract

The present invention relates to a method and apparatus for constructing spatial representations of referents.

The invention has applications in any area where a spatial representation of a referent is required. Examples are image processing and machine vision. In image processing the “referents” are signal sources which are being viewed by an image processing sensor, eg CCD array. The image sources will be points in a scene, for example.

In order to produce an organised image, the image system must be aware of the relative positions of the image sensors. In the prior art, this information is usually provided a priori.

In the present invention, no a priori information on the arrangement of the image sensors is required. Instead, a geometrical representation of the referents is produced by obtaining signals from the referents and utilising the signals in order to provide the geometrical representation. The geometrical representation is built up purely from the signals provided by the sensors themselves. The invention assumes that behavioural differences between signals for any two referents imply a distance between the referents, and this assumption is utilised in order to build up the geometrical representation of the referents.

Claims

1. A method of producing a geometrical representation of a plurality of referents in space, comprising the steps of obtaining signals from a plurality of referents and utilising the signals in order to provide the geometrical representation of the referents.

2. A method in accordance with claim 1, wherein the step of obtaining signals includes the step of obtaining signals from sensors associated with the referents.

3. A method in accordance with claim 1 or 2, wherein the step of utilising the signals includes the step of assuming that differences in the signals from the referents imply an actual distance between the referents, in accordance with spatial redundancy.

4. A method in accordance with claim 3, wherein the step of utilising the signals includes the step of assuming that the differences in signals are related to the actual distance between the referents by a monotonically increasing function.

5. A method in accordance with claim 4, wherein the step of utilising the signals in order to provide a geometrical representation of the referents, includes the step of assuming that the differences (b) in signals implies an actual distance (a) between the associated referents, and utilising the signal differences (b) to determine a geometrical distance (g) for locators constituting the geometrical representation, wherein the geometrical distance (g) is a function of the actual distance (a).

6. A method in accordance with claim 5, wherein the step of utilising the signals comprises the further steps of quantifying an error (ε

) in the geometrical representation of the referents, and repositioning locators by changing the geometrical distance (g) between locators, with the intention of reducing ε

.

7. A method in accordance with claim 6, wherein the step of utilising the signals to provide the geometrical representations of the referents, includes the step of repeating the method steps of claim 6 periodically.

8. A method in accordance with claim 6, wherein the step of utilising the signals to provide the geometrical representation of the referents includes the steps of repeating the method steps of claim 6 continuously.

9. A method in accordance with claim 6, 7, or 8, wherein the step of repositioning locators includes the step of sampling the possible population of referents and repositioning the locators corresponding to the sampled referents.

10. A method in accordance with claim 9, wherein the step of sampling the possible population of referents, includes the step of sampling pairs of referents from a set of all possible parts of referents.

11. A method in accordance with claim 10, wherein each pair of referents comprises a unit and wherein the number of units utilised comprises the workforce, the step of utilising the signals comprising the further step of determining a size of workforce to be used to provide signals to provide the geometrical representation of the referents.

12. A method in accordance with claim 11, wherein the step of determining the size of the workforce includes the step of determining that the workforce will be a complete workforce, wherein there is one unit for each possible pair of referents.

13. A method in accordance with claim 11, wherein the step of determining the size of the workforce includes the step of determining that the workforce will be an incomplete workforce, wherein the number of units is less than the number of all possible pairs of referents.

14. A method in accordance with claim 13, wherein the workforce is constituted by an ordered selection of pairs of referents.

15. A method in accordance with claim 13, wherein the workforce is constituted from random samples of pairs of referents.

16. A method in accordance with claim 14 or 15, wherein the workforce is constituted from samples of pairs of referents which are selected in accordance with their utility in effecting the geometrical representation of the referents.

17. A method in accordance with claim 16, comprising the further step of reselecting pairs of referents to be included in the workforce in an evolving fashion on the basis of their utility.

18. A method in accordance with claim 17, wherein a unit is considered to have a high utility, and is therefore more likely to be selected, if the signal difference b or the geometrical distance g of the unit is relatively small.

19. A method in accordance with claim 18 or 19, wherein a unit is considered to have low utility, and is more likely to be deselected, if the signal difference b or the geometrical distance g of the unit is relatively large.

20. A method in accordance with any one of claims 11 to 19, wherein the step of utilising the signals comprises the further step of storing historical information about the difference (b) in signals of a unit.

21. A method in accordance with claim 20, wherein the step of utilising the signal differences (b) to determine geometrical distance (g) for locators includes the step of utilising the historical information.

22. A method in accordance with any one of claims 8 to 21, wherein the step of repositioning the locators is implemented by way of a hill climbing algorithm.

23. A method in accordance with claim 22, wherein the hill climbing algorithm utilised is the gradient descent method.

24. A method in accordance with any one of claims 5 to 23, wherein the step of utilising the signals comprises the further step of determining a statistic, μ

, which is a measure of the expected behavioural difference between signals from a pair of referents where there is no correlation between signals.

25. A method in accordance with claim 24, wherein signal difference (b) values that are greater than μ

are not utilised.

26. A method in accordance with claim 24 or 25, wherein signal difference (b) values that are close to or at the value of μ

are not utilised.

27. A method in accordance with any one of claims 24 to 26, wherein the steps of determining the statistic μ

, includes the step of determining μ

for a pair or a subset of all possible pairs of referents.

28. A method in accordance with any one of claims 24 to 26, wherein the step of determining the statistic μ

, includes the step of determining μ

for all possible pairs of referents.

29. A method in accordance with any one of the preceding claims, wherein each referent may provide a plurality of separate types of signal, providing a signal value for each type.

30. A method in accordance with claim 29, wherein each separate type of signal is treated as being associated with a separate referent, and a geometrical representation is provided for each type.

31. A method in accordance with claim 30, wherein a separate locator is provided for each type of signal, and the separate locators are then geometrically combined to produce a single locator.

32. A method in accordance with claim 31, wherein the plurality of separate types are combined and treated as a single signal value.

33. A method in accordance with any one of the preceding claims, wherein for an n dimensional space of the referents, the method of utilising the signal comprises the step of providing n+m dimensional space within which to organise the geometrical representation.

34. A method in accordance with any one of claims 1 to 32, wherein for an n dimensional space of the referents, the method of utilising the signal comprises the step providing an n−

m dimensional space for the geometrical representation.

35. A method in accordance with claim 33, comprising the further step of subsequently reducing the geometrical representation to n dimensions.

36. A method in accordance with any one of claims 8 to 36, wherein the step of repositioning locators, includes the step of determining a momentum of locators within the geometrical representation, and repositioning the locators in dependence on the momentum.

37. A method in accordance with any one of claims 2 to 36, wherein the referents are the sensors.

38. A method in accordance with any one of claims 2 to 36, wherein the referents are sources being measured by the sensors.

39. A method in accordance with claims 37 or 38 wherein the sensors are one of more of the following type of sensor;

light, pressure, sound, heat, motion, infrared, tension, radiation, sonar, range-finder, chemical, physical, electromagnetic, protein and molecular.

40. A method in accordance with any one of claims 1 to 36, wherein the referents are sources of data.

41. A method in accordance with claim 40, wherein the sources of data are provided from a database.

42. A method in accordance with claim 40 or 41, wherein the referents are sources of data relating to non-physical domains.

43. A method in accordance with any one of claims 1 to 36, wherein the referents are associated with motor commands for a motor sub-system.

44. A method in accordance with any one of claims 1 to 36 wherein the referents are biological neurons.

45. A method in accordance with claim 43, wherein the step of providing the geometrical representation includes the step of providing a geometrical representation of a plurality of sensors and providing a geometrical representation of the motor commands combined with the geometrical representation of the plurality of sensors.

46. A method in accordance with claim 45, wherein the geometrical representation of the plurality of sensors is provided in accordance with the method of any one of claims 2 to 36.

65. A method in accordance with any one of claims 46 to 64, wherein the step of positioning the locator of each motor command includes the step of dividing the motor command into a plurality of sub-motor commands, and positioning a locator for each of the sub-motor commands in the geometrical representation.

84. An apparatus in accordance with claim 17 or 18, wherein a unit is considered to have low utility, and is more likely to be deselected, if the signal difference b or the geometrical distance g of the unit is relatively large.

129. A computer program arranged, when loaded onto a computing apparatus, to control the computing apparatus to implement the method of any one of claims 1 to 46.

130. A computer readable medium, providing a computer program in accordance with claim 129.

47. In a system including a motor sub-system and a sensor sub-system, a method of calibrating the motor sub-system to the sensor sub-system, comprising the step of providing a positional representation associated with a motor command in a geometrical representation provided by the sensor sub-system.

48. A method in accordance with claim 47, wherein the motor command is represented by a locator in the geometrical representation.

49. A method in accordance with claim 47 or claim 48, wherein the step of providing the positional representation of the motor command includes the steps of collecting signals from a plurality of sensors of the sensor sub-system before and after a performance of the motor command and analysing the signals in order to provide information regarding the spatial relationship between the motor command performed and the geometrical representation by the sensor sub-system.

50. A method according to claim 48 or claim 49, wherein a plurality of motor commands are available to the motor sub-system and the method of calibration is carried out for a plurality of motor commands.

51. A method in accordance with claim 50, wherein the method of calibration is carried out for all motor commands.

52. A method in accordance with any one of claims 47 to 51, wherein a step of positioning the locator of the motor command includes the step of collecting signals from a first sensor before performance of a motor command and a second sensor after performance of a motor command and analysing the signals in order to obtain information regarding the spatial relationship between the motor command performed and the geometrical representation.

53. A method in accordance with any one of the claims 47 to 52, wherein the step of analysing the signals includes the further step of defining a reference point within the geometrical representation and selecting the second sensor to be at or near the reference point.

54. A method in accordance with claim 53, wherein the step of selecting the second sensor includes the '"'"'step of selecting a plurality of second sensors and collecting behavioural information from the plurality of second sensors.

55. A method in accordance with claim 54, wherein the reference point is provided with a value determined on the basis of an average of the signal values from the plurality of second sensors, and the value provided to the reference point is treated as the signal value for the purpose of providing the geometrical representation.

56. A method in accordance with claim 55, wherein the average is a weighted average, weighted according to the proximity of the second sensors to the reference point.

57. A method in accordance with any one of claims 47 to 56, comprising the further step of determining a geometrical representation of the sensors, by analysing signals provided by the sensors, and inferring positions of the sensors from the signals.

58. A method in accordance with any one of claims 54 to 57, comprising the further step of repositioning the motor command locator relative to the first sensor locator.

59. A method in accordance with claim 58, comprising the further step of repositioning the first sensor locator relative to the motor command locator.

60. A method in accordance with any one of claims 53 to 59, comprising the steps of storing historical information relating to the signals from the first sensor and the second sensor.

61. A method in accordance with claim 60, comprising the further step of updating the historical information.

62. A method in accordance with claim 60 or 61, wherein the motor command locator is positioned at the location of the locator of the first sensor locator with the least signal difference with the second sensor.

63. A method in accordance with any one of claims 47 to 62, the method including a further step of repeating the calibration for the motor command on a periodic basis.

64. A method in accordance with claims 47 to 62, wherein the method comprises the step of repeating the calibration for every performance of the motor command.

70. An apparatus in accordance with claim 64, wherein the means for utilising the signals in order to provide a geometrical representation of the referents, is arranged to assume that the differences (b) in signals implies an actual distance (a) between the associated referents, and is arranged to utilise the signal differences (b) to determine a geometrical distance (g) for locators constituting the geometrical representation, wherein the geometrical distance (g) is a function of the actual distance (a).

71. An apparatus in accordance with claim 70, wherein the means for utilising the signals is arranged to quantify an error (ε

) in the geometrical representation of the referents, and reposition locators by changing the geometrical distance (g) between locators, with the intention of reducing ε

.

72. An apparatus in accordance with claim 71, wherein the means for utilising the signals is arranged to quantify the error (ε

) and reposition the locators periodically.

73. An apparatus in accordance with claim 71, wherein the means for utilising the signals to provide the geometrical representation of the referents is arranged to quantify the error (ε

) and reposition the locators continuously.

74. An apparatus in accordance with claim 71, 72, or 73, wherein the means for utilising the signals is arranged to sample the possible population of referents and reposition the locators corresponding to the sampled referents.

75. An apparatus in accordance with claim 74, wherein the means for utilising the signals is arranged to sample pairs of referents from a set of all possible parts of referents.

76. An apparatus in accordance with claim 75, wherein each pair of referents comprises a unit and wherein the number of units utilised comprises the workforce, the means for utilising the signals being arranged to determine a size of workforce to be used to provide signals to provide the geometrical representation of the referents.

77. An apparatus in accordance with claim 76, wherein the means for utilising the signals is arranged to determine that the workforce will be a complete workforce, wherein there is one unit for each possible pair of referents.

78. An apparatus in accordance with claim 76, wherein the means for utilising the signals is arranged to determine that the workforce will be an incomplete workforce, wherein the number of units is less than the number of all possible pairs of referents.

79. An apparatus in accordance with claim 78, wherein the workforce is constituted by an ordered selection of pairs of referents.

80. An apparatus in accordance with claim 78, wherein the workforce is constituted from random samples of pairs of referents.

81. An apparatus in accordance with claim 79 or 80, wherein the workforce is constituted from samples of pairs of referents which are selected in accordance with their utility in effecting the geometrical representation of the referents.

82. An apparatus in accordance with claim 81, wherein the means for utilising the signals is arranged to reselect pairs of referents to be included in the workforce in an evolving fashion on the basis of their utility.

83. An apparatus in accordance with claim 82, wherein a unit is considered to have a high utility, and is therefore more likely to be selected, if the signal difference b or the geometrical distnace g of the unit is relatively small.

85. An apparatus in accordance with any one of claims 76 to 84, wherein the means for utilising the signals is arranged to store historical information about the difference (b) in signals of a unit.

86. An apparatus in accordance with claim 85, wherein the means for utilising the signal differences (b) to determine geometrical distance (g) for locators is arranged to utilise the historical information.

87. An apparatus in accordance with any one of claims 73 to 86, wherein the means for utilising the signals is arranged to apply a hill climbing algorithm.

88. An apparatus in accordance with claim 87, wherein the hill climbing algorithm utilised is the gradient descent method.

89. An apparatus in accordance with any one of claims 70 to 88, wherein the means for utilising the signals is arranged to determine a statistic, μ

, which is a measure of the expected difference between signals from a pair of referents where there is no correlation between signals.

90. An apparatus in accordance with claim 89, wherein signal difference (b) values that are greater than μ

are not utilised.

91. An apparatus in accordance with claim 89 or 90, wherein signal difference (b) values that are close to or at the value of μ

are not utilised.

92. An apparatus in accordance with any one of claims 89 to 91, wherein the means for utilising the signals is arranged to determine μ

for a pair or a subset of all possible pairs of referents.

93. An apparatus in accordance with any one of claims 89 to 91, wherein the menas for utilising the signals is arranged to determine μ

for all possible pairs of referents.

131. A computer program arranged, when loaded onto a computing apparatus to control the computing apparatus to implement a method in accordance with any one of claims 47 to 65.

132. A computer readable medium, providing a computer program in accordance with claim 131.

66. An apparatus for producing a geometrical representation of a plurality of referents in space, comprising means for obtaining signals from a plurality of referents means for utilising the signals in order to provide the geometrical representation of the referents.

67. An apparatus in accordance with claim 66, wherein means for obtaining signals includes sensors associated with the referents.

68. An apparatus in accordance with claim 66 or 67, wherein the means for utilising the signals is arranged to assume that differences in the signals from the referents imply an actual distance between the referents, in accordance with spatial redundancy.

69. An apparatus in accordance with claim 68, wherein the means for utilising the signals is arranged to assume that the differences in signals are related to the actual distance between the referents by a monotonically increasing function.

94. An apparatus in accordance with any one of claims 66 to 93, wherein each referent may provide a plurality of separate types of signal, and wherein the means for obtaining signals is arranged to obtain a signal value for each type.

95. An apparatus in accordance with claim 94, wherein the means for utilising the signals is arranged to treat each separate type of signal as being associated with a separate referent, and to provide a geometrical representation is provided for each type.

96. An apparatus in accordance with claim 94, wherein the means for utilising the signals is arranged to provide a separate locator for each type of signal, and to geometrically combine the separate locators to produce a single locator.

97. An apparatus in accordance with claim 94, wherein the means for utilising the signals is arranged to combine the plurality of separate types and treat them as a single signal value.

98. An apparatus in accordance with any one of claims 66 to 97, wherein for an n dimensional space of the referents, the means for utilising the signal is arranged to provide n+m dimensional space within which to organise the geometrical representation.

99. An apparatus in accordance with any one of claims 66 to 97, wherein for an n dimensional space of the referents, the means for utilising the signal is arranged to provide an n−

m dimensional space for the geometrical representation.

100. An apparatus in accordance with claim 98, wherein the means for utilising the signals is arranged to subsequently reduce the geometrical representation to n dimensions.

101. An apparatus in accordance with any one of claims 73 to 100, wherein the means for utilising the signals is arranged to determine a momentum of locators within the geometrical representation, and reposition the locators in dependence on the momentum.

102. An apparatus in accordance with any one of claims 67 to 101, wherein the referents are the sensors.

103. An apparatus in accordance with any one of claims 67 to 101, wherein the referents are sources being measured by the sensors.

104. An apparatus in accordance with claims 102 or 103 wherein the sensors are one of more of the following type of sensor, light, pressure, sound, heat, motion, infrared, tension, radiation, sonar, range-finder, chemical, physical, electromagnetic, protein and molecular.

105. An apparatus in accordance with any one of claims 66 to 101, wherein the referents are sources of data.

106. An apparatus in accordance with claim 105, wherein the sources of data are provided from a database.

107. An apparatus in accordance with claim 105 or 106, wherein the referents are sources of data relating to non-physical domains.

108. An apparatus in accordance with any one of claims 66 to 101, wherein the referents are associated with motor commands for a motor sub-system.

109. An apparatus in accordance with any one of claims 66 to 101 wherein the referents are biological neurons.

110. An apparatus in accordance with claim 108, wherein the means for utilising the signals is arranged to provide a geometrical representation of a plurality of sensors and to provide a geometrical representation of the motor commands combined with the geometrical representation of the plurality of sensors.

127. A system in accordance with any one of claims 110 to 126, wherein the means for calibrating is arranged to divide the motor command into a plurality of sub-motor commands, and position a locator for each of the sub-motor commands in the geometrical representation.

111. A system comprising a motor sub-system and a sensor sub-system, and a means for calibrating the motor sub-system to the sensor sub-system, which is arranged to provide a positional representation associated with a motor command in a geometrical representation provided by the sensor sub-system.

112. A system in accordance with claim 111, wherein the motor command is represented by a locator in the geometrical representation.

113. A system in accordance with claim 111 or claim 112, wherein the means for calibrating is arranged to collect signals from a plurality of sensors of the sensor sub-system before and after a performance of the motor command and analyse the signals in order to provide information regarding the spatial relationship between the motor command performed and the geometrical representation by the sensor sub-system.

114. A system according to claim 112 or claim 113, wherein a plurality of motor commands are available to the motor sub-system and the means for calibrating is arranged to calibrate for a plurality of motor commands.

115. A system in accordance with any one of the claims 111 to 114, wherein the means for calibrating is arranged to define a reference point within the geometrical representation and select the second sensor to be at or near the reference point.

116. A system in accordance with claim 115, wherein the means for calibrating is arranged to select a plurality of second sensors and collect signals from the plurality of second sensors.

117. A system in accordance with claim 116, wherein the reference point is provided with a value determined on the basis of an average of the signal values from the plurality of second sensors, and the value provided to the reference point is treated as the signal value for the purpose of providing the geometrical representation.

118. An apparatus in accordance with claim 117, wherein the average is a weighted average, weighted according to the proximity of the second sensors to the reference point.

119. A system in accordance with any one of claims 111 to 118, wherein the means for calibrating is further arranged to determine a geometrical representation of the sensors, by analysing signals provided by the sensors, and inferring positions of the sensors from the signals.

120. A system in accordance with any one of claims 117 to 119, wherein the means for calibrating is arranged to reposition the motor command locator relative to the first sensor locator.

121. A system in accordance with claim 120, wherein the means for calibrating is arranged to reposition the first sensor locator relative to the motor command locator.

122. A system in accordance with any one of claims 115 to 121, wherein the means for calibrating is arranged to store historical information relating to the signals from the first sensor and the second sensor.

123. A system in accordance with claim 122, wherein the means for calibrating is arranged to update the historical information.

124. A system in accordance with claim 122 or 123, wherein the means for calibrating is arranged to position the motor command locator at the location of the locator of the first sensor locator with the least signal difference with the second sensor.

125. A system in accordance with any one of claims 111 to 124, the means for calibrating being arranged to repeat the calibration for the motor command on a periodic basis.

126. A system in accordance with any one of claims 111 to 124, wherein the means for calibrating is arranged to repeat the calibration for every performance of the motor command.

128. A mobile robotic apparatus, comprising a system in accordance with any one of claims 111 to 127.