Patent Description:
<NPL> describes that being able to build a map of the environment and to simultaneously localize within this map is an essential skill for mobile robots navigating in unknown environments in absence of external referencing systems such as GPS. This so-called simultaneous localization and mapping (SLAM) problem has been one of the most popular research topics in mobile robotics for the last two decades and efficient approaches for solving this task have been proposed. One intuitive way of formulating SLAM is to use a graph whose nodes correspond to the poses of the robot at different points in time and whose edges represent constraints between the poses. The latter are obtained from observations of the environment or from movement actions carried out by the robot. Once such a graph is constructed, the map can be computed by finding the spatial configuration of the nodes that is mostly consistent with the measurements modeled by the edges. In this paper, we provide an introductory description to the graph-based SLAM problem. Furthermore, we discuss a state-of-the-art solution that is based on least-squares error minimization and exploits the structure of the SLAM problems during optimization.

<NPL> describes that in this paper, we address the scalability issue plaguing graph-based semi-supervised learning via a small number of anchor points which adequately cover the entire point cloud. Critically, these anchor points enable nonparametric regression that predicts the label for each data point as a locally weighted average of the labels on anchor points. Because conventional graph construction is inefficient in large scale, we propose to construct a tractable large graph by coupling anchor based label prediction and adjacency matrix design.

<CIT> describes that mixed-reality systems are provided for using anchor graphs within a mixed-reality environment. These systems utilize anchor vertexes that comprise at least one first key frame, a first mixed-reality element, and at least one first transform connecting the at least one first key frame to the first mixed-reality element. Anchor edges comprising transformations connect the anchor vertexes.

A computing system is provided, including at least one imaging sensor configured to collect imaging data of a physical environment. The computing system further includes a processor configured to: generate, based on the imaging data, a first anchor graph including a first plurality of anchors connected by a first plurality of edges, wherein each anchor of the first plurality of anchors indicates a respective estimated position in the physical environment; detect a change in the estimated position of at least one anchor of the first plurality of anchors relative to the one or more imaging sensors; based on the change in the estimated position, reposition the first anchor graph relative to the one or more imaging sensors, wherein estimated lengths of the first plurality of edges and estimated angles between the first plurality of edges remain fixed; generate, based on the imaging data, a second anchor graph including a second plurality of anchors connected by a second plurality of edges, wherein each anchor of the second plurality of anchors indicates a respective estimated position in the physical environment, and wherein the first plurality of anchors and the second plurality of anchors are disjoint; and determine, based on the imaging data, that the one or more imaging sensors have reestablished detection of at least one anchor of the first plurality of anchors; and based on the determination that the one or more imaging sensors have reestablished detection of the at least one anchor of the first plurality of anchors, generate a combined anchor graph including each anchor of the first plurality of anchors and each anchor of the second plurality of anchors, at least in part by modifying an estimated length of at least one edge of the first anchor graph and/or the second anchor graph. Further provided is a method for use with the above computing system, the method comprising: collecting imaging data of a physical environment using one or more imaging sensors;generating, based on the imaging data, a first anchor graph including a first plurality of anchors connected by a first plurality of edges, wherein each anchor of the first plurality of anchors indicates a respective estimated position in the physical environment; detecting a change in the estimated position of at least one anchor of the first plurality of anchors relative to the one or more imaging sensors; based on the change in the estimated position, repositioning the first anchor graph relative to the one or more imaging sensors, wherein estimated lengths of the first plurality of edges and estimated angles between the first plurality of edges remain fixed;generating, based on the imaging data, a second anchor graph including a second plurality of anchors connected by a second plurality of edges, wherein each anchor of the second plurality of anchors indicates a respective estimated position in the physical environment; and the first plurality of anchors and the second plurality of anchors are disjoint; determining, based on the imaging data, that the one or more imaging sensors have reestablished detection of at least one anchor of the first plurality of anchors; and based on the determination that the one or more imaging sensors have reestablished detection of the at least one anchor of the first plurality of anchors, generate a combined anchor graph including each anchor of the first plurality of anchors and each anchor of the second plurality of anchors, at least in part by modifying an estimated length of at least one edge of the first anchor graph and/or the second anchor graph.

In order to address the problems discussed above, a computing system is provided. <FIG> illustrates an example computing system in the form of a head-mounted display device <NUM>. The illustrated head-mounted display device <NUM> takes the form of wearable glasses or goggles, but it will be appreciated that other forms are possible. The head-mounted display device <NUM> may include an output device suite <NUM> including a display <NUM>. In some embodiments, the head-mounted display device <NUM> may be configured in an augmented reality configuration to present an augmented reality environment, and thus the display <NUM> may be an at least partially see-through stereoscopic display configured to visually augment an appearance of a physical environment being viewed by the user through the display <NUM>. In some examples, the display <NUM> may include one or more regions that are transparent (e.g. optically clear) and may include one or more regions that are opaque or semi-transparent. In other examples, the display <NUM> may be transparent (e.g. optically clear) across an entire usable display surface of the display <NUM>.

Alternatively, the head-mounted display device <NUM> may be configured in a virtual reality configuration to present a full virtual reality environment, and thus the display <NUM> may be a non-see-though stereoscopic display. The head-mounted display device <NUM> may be configured to display virtual three-dimensional environments to the user via the non-see-through stereoscopic display. The head-mounted display device <NUM> may be configured to display a virtual representation such as a three-dimensional graphical rendering of the physical environment in front of the user that may include additional virtual objects. Displaying the virtual representation of the physical environment may include generating a two-dimensional projection of a three-dimensional model of the physical environment onto the surface of the display <NUM>. As another alternative, the computing system may include a portable computing device that is not head mounted, such as a smartphone or tablet computing device. In such a device, camera-based augmented reality may be achieved by capturing an image of the physical environment through a forward facing camera and displaying the captured image on a user-facing display along with world locked graphical images superimposed on the captured image. While the computing system is primarily described in terms of the head-mounted display device <NUM> herein, it will be appreciated that many features of the head-mounted display device <NUM> are also applicable to such a portable computing device that is not head mounted.

Returning to the head-mounted example, the output device suite <NUM> of the head-mounted display device <NUM> may, for example, include an image production system that is configured to display virtual objects to the user with the display <NUM>. In the augmented reality configuration with an at least partially see-through display, the virtual objects are visually superimposed onto the physical environment that is visible through the display <NUM> so as to be perceived at various depths and locations. In the virtual reality configuration, the image production system may be configured to display virtual objects to the user with a non-see-through stereoscopic display, such that the virtual objects are perceived to be at various depths and locations relative to one another. In one embodiment, the head-mounted display device <NUM> may use stereoscopy to visually place a virtual object at a desired depth by displaying separate images of the virtual object to both of the user's eyes. Using this stereoscopy technique, the head-mounted display device <NUM> may control the displayed images of the virtual objects, such that the user will perceive that the virtual objects exist at a desired depth and location in the viewed physical environment.

The head-mounted display device <NUM> may include an input device suite <NUM>, including one or more input devices. The input devices may include one or more optical sensors and one or more position sensors, which are discussed in further detail below. Additionally or alternatively, the input devices may include user input devices such as one or more buttons, control sticks, microphones, touch-sensitive input devices, or other types of input devices.

The input device suite <NUM> of the head-mounted display device <NUM> may include one or more imaging sensors <NUM>. In one example, the input device suite <NUM> includes an outward-facing optical sensor <NUM> that may be configured to detect the real-world background from a similar vantage point (e.g., line of sight) as observed by the user through the display <NUM> in an augmented reality configuration. The input device suite <NUM> may additionally include an inward-facing optical sensor <NUM> that may be configured to detect a gaze direction of the user's eye. It will be appreciated that the outward facing optical sensor <NUM> and/or the inward-facing optical sensor <NUM> may include one or more component sensors, including an RGB camera and a depth camera. The RGB camera may be a high definition camera or have another resolution. The depth camera may be configured to project non-visible light and capture reflections of the projected light, and based thereon, generate an image comprised of measured depth data for each pixel in the image. This depth data may be combined with color information from the image captured by the RGB camera, into a single image representation including both color data and depth data, if desired.

The head-mounted display device <NUM> may further include a position sensor system <NUM> that may include one or more position sensors such as accelerometer(s), gyroscope(s), magnetometer(s), global positioning system(s), multilateration tracker(s), and/or other sensors that output position sensor information useable as a position, orientation, and/or movement of the relevant sensor.

Optical sensor information received from the one or more imaging sensors <NUM> and/or position sensor information received from position sensors may be used to assess a position and orientation of the vantage point of head-mounted display device <NUM> relative to other environmental objects. In some embodiments, the position and orientation of the vantage point may be characterized with six degrees of freedom (e.g., world-space X, Y, Z, pitch, roll, yaw). The vantage point may be characterized globally or independent of the real-world background. The position and/or orientation may be determined with an on-board computing system and/or an off-board computing system, which may include a processor <NUM>, a volatile storage device <NUM>, and/or a non-volatile storage device <NUM>.

Furthermore, the optical sensor information and the position sensor information may be used by the computing system to perform analysis of the real-world background, such as depth analysis, surface reconstruction, environmental color and lighting analysis, or other suitable operations. In particular, the optical and positional sensor information may be used to create a virtual model of the real-world background. In some embodiments, the position and orientation of the vantage point may be characterized relative to this virtual space. Moreover, the virtual model may be used to determine positions of virtual objects in the virtual space and add additional virtual objects to be displayed to the user at a desired depth and location within the virtual world. The virtual model is a three-dimensional model and may be referred to as "world space," and may be contrasted with the projection of world space viewable on the display, which is referred to as "screen space. " Additionally, the optical sensor information received from the one or more imaging sensors <NUM> may be used to identify and track objects in the field of view of the one or more imaging sensors <NUM>. The optical sensors may also be used to identify machine recognizable visual features in the physical environment, and use the relative movement of those features in successive frames to compute a frame to frame relative pose change for the head mounted display device <NUM> within the world space of the virtual model.

The head-mounted display device <NUM> may further include a communication system, which may include one or more receivers <NUM> and/or one or more transmitters <NUM>. In embodiments in which the head-mounted display device <NUM> communicates with an off-board computing system, the one or more receivers <NUM> may be configured to receive data from the off-board computing system, and the one or more transmitters <NUM> may be configured to send data to the off-board computing system. In some embodiments, the head-mounted display device <NUM> may communicate with the off-board computing system via a wireless local- or wide-area network. Additionally or alternatively, the head-mounted display device <NUM> may communicate with the off-board computing system via a wired connection.

<FIG> shows a computing system according to another embodiment of the present disclosure. In the embodiment of <FIG>, the computing system has the form of a robot <NUM>, shown here as an unmanned aerial vehicle. It is appreciated that the robot may have other forms in some embodiments and is not limited to the unmanned aerial vehicle shown in <FIG>.

The robot <NUM> may include an input device suite <NUM>, including one or more input devices. As in the embodiment of <FIG>, the input devices may include one or more imaging sensors <NUM> and one or more position sensors <NUM>. The one or more imaging sensors <NUM> may include one or more component sensors, including an RGB camera and a depth camera. The one or more position sensors <NUM> may include one or more accelerometer(s), gyroscope(s), magnetometer(s), global positioning system(s), multilateration tracker(s), and/or other sensors.

The robot <NUM> may further include a processor <NUM>, a volatile storage device <NUM>, and/or a non-volatile storage device <NUM>. In some embodiments, the functions of one or more of the processor <NUM>, the volatile storage device <NUM>, and/or the non-volatile storage device <NUM> may be performed by an off-board computing system. In such embodiments, the robot <NUM> may communicate with the off-board computing system as described above with reference to <FIG>. In such embodiments, the robot <NUM> may include a communication system including one or more receivers <NUM> and/or one or more transmitters <NUM>.

The robot <NUM> may include a propulsion system <NUM> that allows the robot <NUM> to move through the physical environment. In <FIG>, the propulsion system <NUM> is shown as including four impellers, which may be driven by one or more motors. However, other configurations of the propulsion system <NUM> are also contemplated. For example, the propulsion system may include some other number of impellers, and may additionally or alternatively include one or more wheels, treads, or other propulsion devices. In some embodiments, at least a part of the robot <NUM> may be fixed relative to the physical environment.

Shortcomings of existing methods of anchoring a virtual object in a physical environment are shown with reference to <FIG> show an example of a physical environment <NUM> including a first post 202A and a second post 202B between which a virtual rope <NUM> is simulated. In this example, the virtual rope <NUM> is displayed as a virtual object in an augmented reality environment, and the posts are physical objects in the environment. The virtual rope <NUM> may have a reference frame <NUM> that indicates that the first post 202A and the second post 202B are endpoints of the virtual rope <NUM>.

<FIG> shows an initial position of the virtual rope <NUM>. In <FIG>, the physical environment <NUM> and the virtual rope <NUM> are shown after the reference frame <NUM> of the virtual rope <NUM> has moved from the position at which is it displayed in <FIG>. As shown in <FIG>, if the relative positions in screen space of the virtual rope <NUM> and end posts 202A, 202B are not updated, the movement of the reference frame <NUM> may cause the virtual rope <NUM> to be displayed such that the endpoints of the virtual rope <NUM> are not located at the first post 202A and the second post 202B. This movement may be due to movement of the one or more imaging sensors relative to the physical environment. When the one or more imaging sensors <NUM> move relative to the physical environment, the estimated position(s) and orientation(s) (pose) of the one or more imaging sensors <NUM> in the three-dimensional representation of the physical environment may be updated. The objects in world space are then projected to screen space using this updated camera pose for the imaging sensors <NUM>. It is a goal of such updating of the pose to world lock the rope such that its end points in screen space appear locked to the images of the end posts 202A, 202B.

<FIG> shows the physical environment <NUM> and the virtual rope <NUM>, wherein one endpoint of the virtual rope <NUM> is anchored at the first post 202A. As shown in <FIG>, the first post 202A may be the origin of a first anchored reference frame <NUM>. Thus, a first endpoint of the virtual rope <NUM> may be anchored to the first post 202A such that the location of the first endpoint in the physical environment <NUM> does not change over time. However, as shown in <FIG>, when a pose of the first anchored reference frame <NUM> is adjusted, the first anchored reference frame <NUM> may move in some way, such as rotating around its origin as depicted. A second endpoint of the virtual rope <NUM> may therefore move away from the second post 202B. The movement of first anchored reference frame <NUM> may be caused, for example, by drift in the estimated position and orientation of the machine recognizable visual feature upon which anchored reference frame <NUM> is anchored in world space. This drift may be caused by one or more of (<NUM>) variations in the impinging light upon imaging sensor <NUM> that result in varied pixel representation of the visual feature in the captured image, and (<NUM>) differences in the way that such pixel representations of the visual feature are processed by optical feature recognition algorithms. These two differences may combine to produce the effect that the estimated pose in world space of the anchor point for the anchored frame of reference <NUM> varies from frame to frame, and thus appears to drift over time. This effect is also visible in screen space.

In order to avoid having the second endpoint of the virtual rope <NUM> move away from the second post 202B when the frame of reference has drifted to a different pose as shown in <FIG>, a second anchored reference frame <NUM> of the second endpoint may be located at the second post 202B, as shown in <FIG>. The poses of the first anchored reference frame <NUM> and the second anchored reference frame <NUM> may be adjusted independently. However, as shown in <FIG>, adjusting the poses of the first anchored reference frame <NUM> and the second anchored reference frame <NUM> independently may produce a phantom physical interaction with the virtual rope <NUM>, as each of the anchored reference frames <NUM>, <NUM> independently drifts. The movement of the anchor points is akin to the space of the physical environment itself being warped, since the physical model on which the anchor points are built supposes that the anchor points do not move in the physical environment. In the example of <FIG>, the phantom physical interaction is depicted as a loosening of the virtual rope <NUM> that occurs due to a decrease in the distance between the origin of the first anchored reference frame <NUM> and the origin of the second anchored reference frame <NUM>.

An example solution to the phantom physical interaction problem caused by anchor point drift as discussed above with reference to <FIG> is provided below with reference to <FIG>. <FIG> shows an example physical environment <NUM> in which a computing system is situated. As shown in <FIG>, the computing system comprises the head-mounted display device <NUM> of <FIG>. Alternatively, the computing system may be the robot <NUM> of <FIG>, or some other computing system. In addition to the head-mounted display device <NUM> shown in <FIG>, the computing system may include components located away from the physical environment <NUM>, as discussed above with reference to <FIG>.

The head-mounted display device <NUM> as shown in <FIG> includes one or more imaging sensors <NUM> configured to collect imaging data of the physical environment <NUM>. The one or more imaging sensors <NUM> may be included in the input device suite <NUM> of the head-mounted display device <NUM>, as shown in <FIG>.

The head-mounted display device <NUM> may further include a processor <NUM>. The processor <NUM> may be configured to generate, based on the imaging data, a first anchor graph <NUM> including a first plurality of anchors <NUM> connected by a first plurality of edges <NUM>. Each anchor <NUM> of the first plurality of anchors <NUM> may indicate a respective estimated position in the physical environment <NUM>. The processor <NUM> may identify a plurality of features in the physical environment <NUM>, such as edges of objects, to indicate with the anchors <NUM>. In some embodiments, the processor <NUM> may identify one or more tags placed in the physical environment <NUM> as locations for the anchors <NUM>. Preferably, the anchors <NUM> have fixed locations relative to each other. The first anchor graph <NUM> may further include indications of an estimated length of each respective edge <NUM> and/or an estimated angle <NUM> between each of one or more pairs of edges <NUM>.

The one or more imaging sensors <NUM> may be configured to transmit the imaging data to the processor <NUM> in timesteps separated by a predetermined time interval. The processor <NUM> may generate the first anchor graph <NUM> in a single timestep or over a plurality of timesteps.

In some embodiments, one or more virtual objects may be displayed on the display <NUM> of the head-mounted display device <NUM> at one or more locations in the physical environment <NUM> that are determined with reference to the first plurality of anchors <NUM>. Additionally or alternatively, the processor <NUM> may generate other outputs based at least in part on the first plurality of anchors <NUM>, such as a trajectory through the physical environment <NUM>. The processor <NUM> may be configured to execute a physics engine that utilizes the locations of the anchors <NUM>.

The estimated locations of the first plurality of anchors <NUM> may change over time, for example, due to movement of the head-mounted display device <NUM> relative to the physical environment <NUM> and/or error in the imaging data collected by the one or more imaging sensors <NUM>. The processor <NUM> may be further configured to detect a change in the estimated position of at least one anchor <NUM> of the first plurality of anchors <NUM> relative to the one or more imaging sensors <NUM>. <FIG> shows a first plurality of new estimated positions <NUM> of the anchors <NUM>, which are the positions of the anchors <NUM> after the change.

Possible sources of error in the positions of the first plurality of anchors <NUM> are described with reference to <FIG>. In timesteps following the initial determination of the position of each of the first plurality of anchors <NUM>, the processor <NUM> may determine an updated position estimate for each anchor <NUM> based at least in part on imaging data received since the first anchor graph <NUM> was initially generated. The processor <NUM> may identify, in the later-received imaging data, at least some features of the plurality of features in the physical environment <NUM> that were initially identified when defining the first plurality of anchors <NUM>. In some embodiments, the processor <NUM> may determine the updated position estimate for each anchor <NUM> based on imaging data of an area within some predetermined distance of the previous estimated position of the anchor <NUM>. Thus, the processor <NUM> may reduce the amount of computation performed to update the position of the anchor <NUM>. In some embodiments, the processor <NUM> may also use position sensor information received from the position sensor system <NUM> to determine the updated location estimate for each anchor <NUM>. For example, the processor <NUM> may determine that the position sensor information indicates a change in position of a user's head. The processor <NUM> may compare the imaging data to the position sensor information when determining the updated position estimates of the anchors <NUM>.

When the processor determines the updated position estimates of the first plurality of anchors <NUM>, the processor <NUM> may apply a compression algorithm to the imaging data in order to reduce the amount of computation performed when updating the position estimates. In embodiments in which a compression algorithm is applied to the imaging data, applying the compression algorithm may introduce error into the updated position estimates. In addition, in embodiments in which the processor <NUM> uses position sensor information collected by the position sensor system <NUM> when updating the position estimates of the first plurality of anchors <NUM>, discrepancies between the position sensor information and the imaging data may occur. The error in the estimated position may also be caused by different light impinging on the imaging sensor and producing variations in the captured image of the visual feature, and due to the manner in which the optical feature recognition algorithm processes the pixel data in the captured image to identify the visual feature that serves to anchor each anchor point, as described above. Typically, the error in the updated position estimates is an error in the position in world space, which also may be visible in screen space. However, the degree to which the error is visible may vary depending on the viewpoint of the user, i.e., the pose of the head mounted display device <NUM>.

Based on the change in the estimated position of the at least one anchor <NUM>, the processor <NUM> may be further configured to reposition the first anchor graph <NUM> relative to the one or more imaging sensors <NUM>. <FIG> shows a repositioned first anchor graph <NUM> including a first plurality of repositioned anchors <NUM>. The first plurality of repositioned anchors <NUM> may be connected by a first plurality of repositioned edges <NUM>. A first plurality of estimated repositioned angles <NUM> may be formed by respective pairs of repositioned edges <NUM>. In some embodiments, the processor <NUM> may reposition the first anchor graph <NUM> at least in part by translating the first anchor graph <NUM>.

Additionally or alternatively to translating the first anchor graph <NUM>, the processor <NUM> may reposition the first anchor graph <NUM> at least in part by rotating the first anchor graph <NUM>. The repositioned first anchor graph <NUM> shown in <FIG> is the first anchor graph <NUM> of <FIG> and <FIG> rotated by an angle <NUM>. In some embodiments, the processor <NUM> may rotate the first anchor graph <NUM> at least in part by determining a best-fit angular orientation over the first plurality of anchors <NUM>. The best-fit angular orientation may be an angular orientation at which the positions of the first plurality of anchors <NUM> most closely match the new estimated positions <NUM>. For example, the processor <NUM> may use a least-squares algorithm to determine the best-fit angular orientation.

In some embodiments, the best-fit angular orientation may be a weighted best-fit angular orientation. In such embodiments, the processor <NUM> may determine a respective weight of each anchor <NUM> of the first plurality of anchors <NUM> based at least in part on an estimated distance between the anchor <NUM> and the one or more imaging sensors <NUM>. For example, the processor <NUM> may weight an anchor <NUM> more highly if it is closer to the one or more imaging sensors <NUM>. Additionally or alternatively, the processor <NUM> may determine a respective weight of each anchor <NUM> of the first plurality of anchors <NUM> based at least in part on a change in an estimated angular position of the anchor <NUM>. The change in the estimated angular position of the anchor <NUM> may be a difference between the estimated angular position of the anchor <NUM> before and after the change in position. For example, the processor <NUM> may apply a least-squares algorithm to the changes in the estimated angular positions of the anchors <NUM>. Additionally or alternatively, the processor <NUM> may reposition the first anchor graph <NUM> at least in part by applying a Bayesian updating algorithm to the respective positions of the anchors <NUM>.

<FIG> shows the physical environment <NUM> and the head-mounted display device <NUM> when the head-mounted display device <NUM> moves into a new area of the physical environment <NUM>. When the head-mounted display device <NUM> moves into the new area, the processor <NUM> may determine, based on the imaging data, that no anchors <NUM> included in the first plurality of anchors <NUM> are detected by the one or more imaging sensors <NUM>. In response to this determination, the processor <NUM> generates, based on the imaging data, a second anchor graph <NUM>, as seen in <FIG>. The second anchor graph <NUM> includes a second plurality of anchors <NUM> connected by a second plurality of edges <NUM>. Each anchor <NUM> of the second plurality of anchors <NUM> indicates a respective estimated position in the physical environment <NUM>. In addition, a second plurality of estimated angles <NUM> may be formed by respective pairs of edges <NUM>. The first plurality of anchors <NUM> and the second plurality of anchors <NUM> are disjoint, i.e., no anchors are included in both the first plurality of anchors <NUM> and the second plurality of anchors <NUM>. The processor <NUM> may generate the second anchor graph <NUM> in a single timestep or over a plurality of timesteps. In addition, the processor <NUM> may be further configured to reposition the second anchor graph <NUM> as described above for the first anchor graph <NUM>.

As shown in <FIG>, subsequently to generating the second anchor graph <NUM>, the processor <NUM> is further configured to determine, based on the imaging data, that the one or more imaging sensors <NUM> have reestablished detection of at least one anchor <NUM> of the first plurality of repositioned anchors <NUM>. Although, as shown in <FIG>, the one or more imaging sensors <NUM> have reestablished detection of at least one repositioned anchor <NUM> of the first plurality of repositioned anchors <NUM>, the processor <NUM> may, in some embodiments, reestablish detection of at least one anchor <NUM> of the first plurality of anchors <NUM> even if repositioning of the at least one anchor <NUM> has not previously been performed. Based on the determination that the one or more imaging sensors <NUM> have reestablished detection of the at least one repositioned anchor <NUM> of the first plurality of repositioned anchors <NUM>, the processor <NUM> generates a combined anchor graph <NUM> including each repositioned anchor
<NUM> of the first plurality of repositioned anchors <NUM> and each anchor <NUM> of the second plurality of anchors <NUM>. When generating the combined anchor graph <NUM>, the processor <NUM> may determine a border region <NUM> that includes a repositioned anchor <NUM> of the repositioned first anchor graph <NUM> and an anchor <NUM> of the second anchor graph <NUM>. In some embodiments, the border region <NUM> may further include additional anchors. The processor <NUM> may then connect the repositioned first anchor graph <NUM> and the second anchor graph <NUM> with a border edge <NUM> that connects the anchors in the border region <NUM>.

As shown in <FIG>, the head-mounted display device <NUM> may subsequently move to a position in which the one or more imaging sensors <NUM> reestablishes detection of at least one additional anchor of the repositioned first anchor graph <NUM>. The processor <NUM> may determine a border region <NUM> and connect the repositioned first anchor graph <NUM> and the second anchor graph <NUM> with a border edge <NUM> as described above with reference to <FIG>. However, an inconsistency in the estimated angles between the edges may result. For example, a loop including one or more repositioned anchors <NUM> of the repositioned first anchor graph <NUM> and one or more anchors <NUM> of the second anchor graph <NUM> may form a polygon with external angles that do not sum to <NUM> degrees. In response to this inconsistency, the processor <NUM> may generate the combined anchor graph <NUM> at least in part by rotating and/or translating at least one of the repositioned first anchor graph <NUM> and the second anchor graph <NUM>. <FIG> shows a repositioned second anchor graph <NUM> in which the second anchor graph <NUM> has been rotated such that the second plurality of anchors <NUM> have a second plurality of new estimated positions <NUM>. The second plurality of new estimated positions <NUM> may be connected by a second plurality of repositioned edges <NUM>. A second plurality of estimated repositioned angles <NUM> may be formed by respective pairs of repositioned edges <NUM>.

In some embodiments in which the processor <NUM> repositions the second anchor graph <NUM> when generating the combined anchor graph <NUM>, the processor <NUM> may generate the combined anchor graph <NUM> at least in part by modifying an estimated length of at least one edge of the repositioned first anchor graph <NUM> and/or the second anchor graph <NUM>. Thus, subgraphs of the first anchor graph <NUM> and/or the second anchor graph <NUM> may be rotated and/or translated separately from each other when the combined anchor graph <NUM> is generated. In some embodiments, the processor <NUM> may modify an estimated length of at least one border edge <NUM>. <FIG> shows the combined anchor graph <NUM> in an example in which the repositioned first anchor graph <NUM> and the repositioned second anchor graph <NUM> have been recombined after the second anchor graph <NUM> has been rotated. As shown in <FIG>, the repositioned first anchor graph <NUM> and the repositioned second anchor graph <NUM> are connected by modified border edges <NUM>. The modified border edges <NUM> connect repositioned anchors <NUM> of the first plurality of repositioned anchors <NUM> to the new estimated positions <NUM> of the second plurality of anchors <NUM>.

<FIG> shows a flowchart of a method <NUM> for use with a computing system. The computing system may be the head-mounted display device <NUM> of <FIG>, the robot <NUM> of <FIG>, or some other computing system. The method <NUM> may be performed at least in part by a processor included in the computing system. The method <NUM> includes, at step <NUM>, collecting imaging data of a physical environment using one or more imaging sensors. For example, the one or more imaging sensors may include one or more RGB cameras and/or depth cameras. The imaging data may be collected in one or more timesteps.

At step <NUM>, the method <NUM> may further include generating, based on the imaging data, a first anchor graph including a first plurality of anchors connected by a first plurality of edges. Each anchor of the first plurality of anchors may indicate a respective estimated position in the physical environment. For example, generating the first anchor graph may include identifying features in the physical environment such as edges of objects. Imaging data associated with such features may be stored in memory of the computing system to identify such features as anchors.

At step <NUM>, the method <NUM> may further include detecting a change in the estimated position of at least one anchor of the first plurality of anchors relative to the one or more imaging sensors. The change in the estimated position may occur due to motion of the one or more imaging sensors in the physical environment. Additionally or alternatively, the change in the estimated position may occur due to error in the image data. The change in the estimated position may be a change that occurs between a first timestep and a subsequent timestep.

At step <NUM>, the method <NUM> may further include repositioning the first anchor graph relative to the one or more imaging sensors. The first anchor graph may be repositioned based on the change in the estimated position. In some embodiments, estimated lengths of the first plurality of edges and/or estimated angles between the first plurality of edges may remain fixed. Thus, the first anchor graph as a whole, rather than individual anchors, may be repositioned. In some embodiments, repositioning the first anchor graph may include, at step <NUM>, translating the first anchor graph. Additionally or alternatively, repositioning the first anchor graph may include, at step <NUM>, rotating the first anchor graph. In embodiments in which repositioning the first anchor graph includes rotating the first anchor graph, the method <NUM> may further include, at step <NUM>, determining a best-fit angular orientation over the first plurality of anchors. For example, determining the best-fit angular orientation may include applying a least-squares algorithm to the estimated locations of the anchors.

<FIG> shows a flowchart of additional steps that may optionally be performed as part of the method <NUM>. At step <NUM>, the method <NUM> may further include determining, based on the imaging data, that no anchors included in the first plurality of anchors are detected by the one or more imaging sensors. In response to this determination, the method <NUM> may further include, at step <NUM>, generating a second anchor graph including a second plurality of anchors connected by a second plurality of edges. Similarly to the first anchor graph, the second anchor graph may be generated based on the imaging data collected by the one or more imaging sensors. Each anchor of the second plurality of anchors may indicate a respective estimated position in the physical environment. The respective estimated position of each anchor of the second plurality of anchors may be determined by identifying at least one feature in the image data. In some embodiments, the first plurality of anchors and the second plurality of anchors are disjoint.

At step <NUM>, the method <NUM> may further include determining, based on the imaging data, that the one or more imaging sensors have reestablished detection of at least one anchor of the first plurality of anchors. Based on the determination that the one or more imaging sensors have reestablished detection of the at least one anchor of the first plurality of anchors, the method <NUM> may further include, at step <NUM>, generating a combined anchor graph including each anchor of the first plurality of anchors and each anchor of the second plurality of anchors. In some embodiments, generating the combined anchor graph may include, at step <NUM>, rotating at least one of the first anchor graph and the second anchor graph. Additionally or alternatively, generating the combined anchor graph may include, at step <NUM>, translating at least one of the first anchor graph and the second anchor graph. In some embodiments, generating the combined anchor graph may include, at step <NUM>, modifying an estimated length of at least one edge of the first anchor graph and/or the second anchor graph. For example, the first anchor graph and/or the second anchor graph may be divided into two or more subgraphs that are translated and/or rotated and are subsequently recombined into the combined anchor graph.

Computing system <NUM> may, for example, embody the head-mounted display device <NUM> of <FIG>, the robot <NUM> of <FIG>, or some other computing system. Computing system <NUM> may take the form of one or more personal computers, server computers, tablet computers, home-entertainment computers, network computing devices, gaming devices, mobile computing devices, mobile communication devices (e.g., smart phone), and/or other computing devices, and wearable computing devices such as smart wristwatches and head mounted augmented/virtual reality devices.

Computing system <NUM> includes a logic processor <NUM>, volatile memory <NUM>, and a non-volatile storage device <NUM>.

The logic processor <NUM> may include one or more physical processors (hardware) configured to execute software instructions. Additionally or alternatively, the logic processor <NUM> may include one or more hardware logic circuits or firmware devices configured to execute hardware-implemented logic or firmware instructions. Individual components of the logic processor <NUM> optionally may be distributed among two or more separate devices, which may be remotely located and/or configured for coordinated processing. In such a case, these virtualized aspects may be run on different physical logic processors of various different machines.

The term "program" may be used to describe an aspect of computing system <NUM> implemented to perform a particular function. In some cases, a program may be instantiated via logic processor <NUM> executing instructions held by non-volatile storage device <NUM>, using portions of volatile memory <NUM>. It will be understood that different programs may be instantiated from the same application, service, code block, object, library, routine, API, function, etc. Likewise, the same program may be instantiated by different applications, services, code blocks, objects, routines, APIs, functions, etc. The term "program" encompasses individual or groups of executable files, data files, libraries, drivers, scripts, database records, etc..

As the herein described methods and processes change the data held by the non-volatile storage device <NUM>, and thus transform the state of the non-volatile storage device <NUM>, the state of display subsystem <NUM> may likewise be transformed to visually represent changes in the underlying data.

In some embodiments, the input subsystem <NUM> may comprise or interface with selected natural user input (NUI) componentry. Example NUI componentry may include a microphone for speech and/or voice recognition; an infrared, color, stereoscopic, and/or depth camera for machine vision and/or gesture recognition; a head tracker, eye tracker, accelerometer, and/or gyroscope for motion detection, gaze detection, and/or intent recognition; as well as electric-field sensing componentry for assessing brain activity; and/or any other suitable sensor.

As non-limiting examples, the communication subsystem <NUM> may be configured for communication via a wireless telephone network, or a wired or wireless local- or wide-area network. In some embodiments, the communication subsystem <NUM> may allow computing system <NUM> to send and/or receive messages to and/or from other devices via a network such as the Internet.

According to one aspect of the present disclosure, a computing system is provided, including one or more imaging sensors configured to collect imaging data of a physical environment. The computing system may further include a processor configured to generate, based on the imaging data, a first anchor graph. The first anchor graph may include a first plurality of anchors connected by a first plurality of edges, wherein each anchor of the first plurality of anchors indicates a respective estimated position in the physical environment. The processor may be further configured to detect a change in the estimated position of at least one anchor of the first plurality of anchors relative to the one or more imaging sensors. Based on the change in the estimated position, the processor may be further configured to reposition the first anchor graph relative to the one or more imaging sensors, wherein estimated lengths of the first plurality of edges and estimated angles between the first plurality of edges remain fixed.

According to this aspect, the computing system may include a head-mounted display device.

According to this aspect, the processor may be further configured to reposition the first anchor graph at least in part by translating the first anchor graph.

According to this aspect, the processor may be further configured to reposition the first anchor graph at least in part by rotating the first anchor graph.

According to this aspect, the processor may be further configured to rotate the first anchor graph at least in part by determining a best-fit angular orientation over the first plurality of anchors.

According to this aspect, the best-fit angular orientation may be a weighted best-fit angular orientation. The processor may be further configured to determine a respective weight of each anchor of the first plurality of anchors based at least in part on an estimated distance between the anchor and the one or more imaging sensors.

According to this aspect, the best-fit angular orientation may be a weighted best-fit angular orientation. The processor may be further configured to determine a respective weight of each anchor of the first plurality of anchors based at least in part on a change in an estimated angular position of the anchor.

According to this aspect, the processor may be further configured to generate, based on the imaging data, a second anchor graph including a second plurality of anchors connected by a second plurality of edges. Each anchor of the second plurality of anchors may indicate a respective estimated position in the physical environment. The first plurality of anchors and the second plurality of anchors may be disjoint.

According to this aspect, the processor may be further configured to determine, based on the imaging data, that no anchors included in the first plurality of anchors are detected by the one or more imaging sensors. The processor may be further configured to generate the second anchor graph in response to determining that no anchors included in the first plurality of anchors are detected by the one or more imaging sensors.

According to this aspect, the processor may be further configured to determine, based on the imaging data, that the one or more imaging sensors have reestablished detection of at least one anchor of the first plurality of anchors. Based on the determination that the one or more imaging sensors have reestablished detection of the at least one anchor of the first plurality of anchors, the processor may be further configured to generate a combined anchor graph including each anchor of the first plurality of anchors and each anchor of the second plurality of anchors.

According to this aspect, the processor may be further configured to generate the combined anchor graph at least in part by rotating and/or translating at least one of the first anchor graph and the second anchor graph.

According to this aspect, the processor may be further configured to generate the combined anchor graph at least in part by modifying an estimated length of at least one edge of the first anchor graph and/or the second anchor graph.

According to another aspect of the present disclosure, a method for use with a computing system is provided. The method may include collecting imaging data of a physical environment using one or more imaging sensors. The method may further include generating, based on the imaging data, a first anchor graph including a first plurality of anchors connected by a first plurality of edges. Each anchor of the first plurality of anchors may indicate a respective estimated position in the physical environment. The method may further include detecting a change in the estimated position of at least one anchor of the first plurality of anchors relative to the one or more imaging sensors. Based on the change in the estimated position, the method may further include repositioning the first anchor graph relative to the one or more imaging sensors, wherein estimated lengths of the first plurality of edges and estimated angles between the first plurality of edges remain fixed.

According to this aspect, repositioning the first anchor graph may include translating the first anchor graph.

According to this aspect, repositioning the first anchor graph may include rotating the first anchor graph.

According to this aspect, repositioning the first anchor graph may include determining a best-fit angular orientation over the first plurality of anchors.

According to this aspect, the method may further include generating, based on the imaging data, a second anchor graph including a second plurality of anchors connected by a second plurality of edges. Each anchor of the second plurality of anchors may indicate a respective estimated position in the physical environment. The first plurality of anchors and the second plurality of anchors may be disjoint.

According to this aspect, the method may further include determining, based on the imaging data, that no anchors included in the first plurality of anchors are detected by the one or more imaging sensors. The method may further include generating the second anchor graph in response to determining that no anchors included in the first plurality of anchors are detected by the one or more imaging sensors.

According to this aspect, the method may further include determining, based on the imaging data, that the one or more imaging sensors have reestablished detection of at least one anchor of the first plurality of anchors. Based on the determination that the one or more imaging sensors have reestablished detection of the at least one anchor of the first plurality of anchors, the method may further include generating a combined anchor graph including each anchor of the first plurality of anchors and each anchor of the second plurality of anchors.

According to another aspect of the present disclosure, a head-mounted display device is provided, including one or more imaging sensors configured to collect imaging data of a physical environment. The head-mounted display device may further include a processor configured to generate, based on the imaging data, a first anchor graph including a first plurality of anchors connected by a first plurality of edges. Each anchor of the first plurality of anchors may indicate a respective estimated position in the physical environment. The processor may be further configured to detect a change in the estimated position of at least one anchor of the first plurality of anchors relative to the one or more imaging sensors. The processor may be further configured to, based on the change in the estimated position, reposition the first anchor graph relative to the one or more imaging sensors. Estimated lengths of the first plurality of edges and estimated angles between the first plurality of edges may remain fixed. The processor may be further configured to determine, based on the imaging data, that no anchors included in the first plurality of anchors are detected by the one or more imaging sensors. The processor may be further configured to generate, based on the imaging data, a second anchor graph including a second plurality of anchors connected by a second plurality of edges. Each anchor of the second plurality of anchors may indicate a respective estimated position in the physical environment. The first plurality of anchors and the second plurality of anchors may be disjoint. The processor may be further configured to determine, based on the imaging data, that the one or more imaging sensors have reestablished detection of at least one anchor of the first plurality of anchors. The processor may be further configured to generate a combined anchor graph including each anchor of the first plurality of anchors and each anchor of the second plurality of anchors.

Claim 1:
A computing system (<NUM>), comprising:
one or more imaging sensors (<NUM>) configured to collect imaging data of a physical environment (<NUM>); and
a processor (<NUM>) configured to:
generate, based on the imaging data, a first anchor graph (<NUM>) including a first plurality of anchors (<NUM>) connected by a first plurality of edges (<NUM>), wherein each anchor of the first plurality of anchors indicates a respective estimated position in the physical environment;
detect a change in the estimated position of at least one anchor of the first plurality of anchors relative to the one or more imaging sensors;
based on the change in the estimated position, reposition the first anchor graph relative to the one or more imaging sensors, wherein estimated lengths of the first plurality of edges and estimated angles (<NUM>) between the first plurality of edges remain fixed;
generate, based on the imaging data, a second anchor graph including a second plurality of anchors connected by a second plurality of edges, wherein each anchor of the second plurality of anchors indicates a respective estimated position in the physical environment, and wherein the first plurality of anchors and the second plurality of anchors are disjoint; and
determine, based on the imaging data, that the one or more imaging sensors have reestablished detection of at least one anchor of the first plurality of anchors; and
based on the determination that the one or more imaging sensors have reestablished detection of the at least one anchor of the first plurality of anchors, generate a combined anchor graph including each anchor of the first plurality of anchors and each anchor of the second plurality of anchors, at least in part by modifying an estimated length of at least one edge of the first anchor graph and/or the second anchor graph.