Method and apparatus for combining data to construct a floor plan

• US 10,482,619 B2
• Filed: 07/27/2018
• Issued: 11/19/2019
• Est. Priority Date: 07/27/2017
• Status: Active Grant

• Current Assignee: Ai Incorprated
• Original Assignee: Ai Incorprated
• Inventors: Ebrahimi Afrouzi, Ali, Schweigert, Sebastian, Zhang, Chen
• Primary Examiner(s): Osinski, Michael S
• Application Number:
  US16/048,179
• Publication Number:
  US 20190035099A1
• Time in Patent Office: 480 Days
• CPC Class Codes: G01C 21/32 Structuring or formatting of map data
• CPC Class Codes: G01S 17/48 Active triangulation systems, i.e. using the transmission and reflection of electromagnetic waves other than radio waves
• CPC Class Codes: G01S 17/86 Combinations of lidar systems with systems other than lidar, radar or sonar, e.g. with direction finders
• CPC Class Codes: G01S 17/89 for mapping or imaging
• CPC Class Codes: G05D 1/0227 using mechanical sensing means, e.g. for sensing treated area
• CPC Class Codes: G05D 1/0253 extracting relative motion information from a plurality of images taken successively, e.g. visual odometry, optical flow determining position or orientation from images G06T7/70
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G06N 3/008 based on physical entities controlled by simulated intelligence so as to replicate intelligent life forms, e.g. based on robots replicating pets or humans in their appearance or behaviour
• CPC Class Codes: G06N 3/045 Combinations of networks
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 7/0002 Inspection of images, e.g. flaw detection
• CPC Class Codes: G06T 7/13 Edge detection
• CPC Class Codes: G06T 7/30 Determination of transform parameters for the alignment of images, i.e. image registration
• CPC Class Codes: G06T 7/344 involving models
• CPC Class Codes: G06T 7/593 from stereo images
• CPC Class Codes: G06T 7/73 using feature-based methods
• CPC Class Codes: G06V 10/16 using multiple overlapping images; Image stitching
• CPC Class Codes: G06V 10/751 Comparing pixel values or logical combinations thereof, or feature values having positional relevance, e.g. template matching
• CPC Class Codes: G06V 20/10 Terrestrial scenes scenes under surveillance with static cameras G06V20/52; scenes perceived from the exterior of a vehicle G06V20/56; scenes perceived from the interior of a vehicle G06V20/59
• CPC Class Codes: G06V 20/58 : Recognition of moving objects or obstacles, e.g. vehicles or pedestrians; Recognition of traffic objects, e.g. traffic signs, traffic lights or roads
• CPC Class Codes: G06V 20/64 : Three-dimensional objects
• CPC Class Codes: Y10S 901/47 : Optical

Abstract

Provided is a method and apparatus for combining perceived depths to construct a floor plan using cameras, such as depth cameras. The camera(s) perceive depths from the camera(s) to objects within a first field of view. The camera(s) is rotated to observe a second field of view partly overlapping the first field of view. The camera(s) perceives depths from the camera(s) to objects within the second field of view. The depths from the first and second fields of view are compared to find the area of overlap between the two fields of view. The depths from the two fields of view are then merged at the area of overlap to create a segment of a floor plan. The method is repeated wherein depths are perceived within consecutively overlapping fields of view and are combined to construct a floor plan of the environment as the camera is rotated.

Claims

1. A method of perceiving a spatial model of a working environment, the method comprising:

capturing data by one or more sensors of a robot moving within a working environment, the data being indicative of depth within the working environment from respective sensors of the robot to objects in the working environment at a plurality of different sensor poses;

obtaining, with one or more processors of the robot, a plurality of depth images based on the captured data, wherein;

respective depth images are based on data captured from different positions within the working environment through which the robot moves,

respective depth images comprise a plurality of depth data, the depth data indicating distance from respective sensors to objects within the working environment at respective sensor poses, and

depth data of respective depth images correspond to respective fields of view;

aligning, with one or more processors of the robot, depth data of respective depth images based on an area of overlap between the fields of view of the plurality of depth images, wherein aligning comprises;

determining a first area of overlap between a first depth image and a second depth image among the plurality of depth images by;

detecting a feature in the first depth image;

detecting the feature in the second depth image;

determining a first value indicative of a difference in position of the feature in the first and second depth images in a first frame of reference of the one or more sensors;

obtaining a second value indicative of a difference in pose of the one or more sensors between when depth data from which the first depth image is obtained and when depth data from which the second depth image is obtained; and

determining the first area of overlap based on the first value and the second value; and

determining a second area of overlap between the second depth image and a third depth image among the plurality of depth images, the first area of overlap being at least partially different from the second area of overlap; and

determining, with one or more processors of the robot, based on alignment of the depth data, a spatial model of the working environment,

wherein at least some data processing of the spatial model is offloaded from the robotic device to the cloud,

wherein the spatial model is further processed to identify rooms in a floor plan, and

wherein the spatial model is stored in memory accessible to the robot during a subsequent operational session for use in autonomously navigating the working environment.

2. The method of claim 1, comprising:

storing at least part of the spatial model of the working environment in memory of the robot;

determining, with one or more processors of the robot, a path of the robot based on the at least part of the spatial model of the working environment; and

controlling, with one or more processors of the robot, an actuator of the robot to cause the robot to move along the determined path.

3. The method of claim 1, wherein:

depth data is associated with respective values indicating respective angular displacements of corresponding depths in respective frames of reference corresponding to respective fields of view;

the depth images are obtained by triangulating object depths based on captured angles at which a laser emitted from the robot and reflecting off respective objects is received at a camera sensor of the robot;

the plurality of depth data comprises a plurality of depth vectors from the sensor to objects within the working environment, respective vectors including at least one coordinate indicating relative position in a respective field of view and at least one coordinate indicating depth; and

at least some of the fields of view partly overlap with a respective preceding field of view.

4. The method of claim 1, wherein the one or more sensors comprise at least one imaging sensor and at least one infrared illuminator.

5. The method of claim 1, wherein determining at least one of the first area of overlap and the second area of overlap comprises:

determining the first area of overlap based on Jacobian and Hessian matrices.

6. The method of claim 1, wherein determining the first area of overlap comprises:

detecting a first edge at a first position in the first image based on a derivative of depth with respect to one or more spatial coordinates of depth data in the first depth image;

detecting a second edge at a second position in the first image based on the derivative of depth with respect to one or more spatial coordinates of depth data in the first depth image;

detecting a third edge in a third position in the second image based on a derivative of depth with respect to one or more spatial coordinates of depth data in the second depth image;

determining that the third edge is not the same edge as the second edge based on shapes of the third edge and the second edge not matching;

determining that the third edge is the same edge as the first edge based on shapes of the first edge and the third edge at least partially matching; and

determining the first area of overlap based on a difference between the first position and the third position.

7. The method of claim 1, wherein determining the first area of overlap comprises:

thresholding the first depth image to form a first thresholded depth image;

thresholding the second depth image to form a second thresholded depth image; and

aligning the first thresholded depth image to the second thresholded depth image.

8. The method of claim 1, wherein determining the first area of overlap comprises:

determining alignment scores of a plurality of candidate alignments based on a Szymkiewicz-Simpson coefficient of overlap between at least part of the first depth image and at least part of the second depth image; and

selecting an alignment from among the candidate alignments based on the alignment scores.

9. The method of claim 1, wherein determining the first area of overlap comprises:

determining an approximate alignment between a reduced resolution version of the first depth image and a reduced resolution version of the second depth image; and

refining the approximate alignment by;

determining aggregate amounts of difference between overlapping portions of the first depth image and the second depth image at candidate alignments displaced from the approximate alignment; and

selecting a candidate alignment that produces a lowest aggregate amount of difference among the candidate alignments or selecting a candidate alignment that produces an aggregate amount of difference less than a threshold.

10. The method of claim 1, wherein determining the first area of overlap comprises:

applying a convolution to the first depth image with a kernel function that determines aggregate measures of difference between at least part of the first depth image and at least part of the second depth image based on differences between depths in respective images; and

selecting an alignment that the convolution indicates has a smallest aggregate measure of difference.

11. The method of claim 1, wherein determining the first area of overlap comprises:

obtaining a vector indicative of spatial displacement of the one or more sensors between the first image and the second image in a frame of reference of the working environment; and

transforming frames of reference of the second depth image and the first depth image into the same frame of reference based on the vector.

12. The method of claim 1, wherein determining the spatial model of the working environment comprises:

determining a point cloud model of the working environment based on alignment of the plurality of depth images.

13. The method of claim 1, wherein determining the spatial model of the working environment comprises:

determining a two-dimensional bitmap representation of obstacles in the working environment based on alignment of the plurality of depth images.

14. The method of claim 1, wherein determining the spatial model of the working environment comprises:

updating priors of a Bayesian spatial model of the working environment from a previous mapping by the robot.

15. The method of claim 1, comprising:

simultaneously localizing the robot and mapping the working environment, wherein the spatial model comprises positions of obstacles in the working environment and values indicating confidence scores for those respective positions, wherein;

the confidence scores are based on at least one of the following;

quality of the captured data,

noise in perceived depth,

similarity between depths recorded from different fields of view, or

confident scores of adjacent depths; and

determining the spatial model comprises pruning or determining to not add positions of obstacles with a threshold confidence score that fail to satisfy a threshold from, or to, the spatial model.

16. The method of claim 1, comprising:

steps for constructing at least one floor plan of the working environment.

17. The method of claim 1, comprising:

cleaning a floor with the robot based on at least part of the spatial model.

18. A robot, comprising:

an actuator configured to move a robot through a working environment;

one or more sensors mechanically coupled to the robot;

one or more processors configured to receive sensed data from the one or more sensors and control the actuator; and

memory storing instructions that when executed by at least some of the processors effectuate operations comprising;

capturing data by one or more sensors of a robot moving within the working environment, the data being indicative of depth within the working environment from respective sensors of the robot to objects in the working environment at a plurality of different sensor poses;

obtaining a plurality of depth images based on the captured data, wherein;

respective depth images are based on data captured from different positions within the working environment through which the robot moves,

respective depth images comprise a plurality of depth data, the depth data indicating distance from respective sensors to objects within the working environment at respective sensor poses, and

depth data of respective depth images correspond to respective fields of view;

aligning depth data of respective depth images based on an area of overlap between the fields of view of the plurality of depth images, wherein aligning comprises;

determining a first area of overlap between a first depth image and a second depth image among the plurality of depth images by;

detecting a feature in the first depth image;

detecting the feature in the second depth image;

determining a first value indicative of a difference in position of the feature in the first and second depth images in a first frame of reference of the one or more sensors;

obtaining a second value indicative of a difference in pose of the one or more sensors between when depth data from which the first depth image is obtained and when depth data from which the second depth image is obtained; and

determining the first area of overlap based on the first value and the second value; and

determining a second area of overlap between the second depth image and a third depth image among the plurality of depth images, the first area of overlap being at least partially different from the second area of overlap; and

determining, based on alignment of the depth data, a spatial model of the working environment,

wherein at least some data processing of the spatial model is offloaded from the robotic device to the cloud,

wherein the spatial model is further processed to identify rooms in a floor plan, and

wherein the spatial model is stored in memory accessible to the robot during a subsequent operational session for use in autonomously navigating the working environment.

19. The robot of claim 18, wherein the operations comprise:

storing at least part of the spatial model of the working environment in memory of the robot;

determining, with one or more processors of the robot, a path of the robot based on the at least part of the spatial model of the working environment; and

controlling, with one or more processors of the robot, an actuator of the robot to cause the robot to move along the determined path.

20. The robot of claim 18, wherein:

depth data is associated with respective values indicating respective angular displacements of corresponding depths in respective frames of reference corresponding to respective fields of view;

the depth images are obtained by triangulating object depths based on captured angles at which a laser emitted from the robot and reflecting off respective objects is received at a camera sensor of the robot;

the plurality of depth data comprises a plurality of depth vectors from the sensor to objects within the working environment, respective vectors including at least one coordinate indicating relative position in a respective field of view and at least one coordinate indicating depth; and

at least some of the fields of view partly overlap with a respective preceding field of view.

21. The robot of claim 18, wherein the one or more sensors comprise at least one imaging sensor and at least one infrared illuminator.

22. The robot of claim 18, wherein determining at least one of the first area of overlap and the second area of overlap comprises:

determining the first area of overlap based on Jacobian and Hessian matrices.

23. The robot of claim 18, wherein determining the first area of overlap comprises:

detecting a first edge at a first position in the first image based on a derivative of depth with respect to one or more spatial coordinates of depth data in the first depth image;

detecting a second edge at a second position in the first image based on the derivative of depth with respect to one or more spatial coordinates of depth data in the first depth image;

detecting a third edge in a third position in the second image based on a derivative of depth with respect to one or more spatial coordinates of depth data in the second depth image;

determining that the third edge is not the same edge as the second edge based on shapes of the third edge and the second edge not matching;

determining that the third edge is the same edge as the first edge based on shapes of the first edge and the third edge at least partially matching; and

determining the first area of overlap based on a difference between the first position and the third position.

24. The robot of claim 18, wherein determining the first area of overlap comprises:

thresholding the first depth image to form a first thresholded depth image;

thresholding the second depth image to form a second thresholded depth image; and

aligning the first thresholded depth image to the second thresholded depth image.

25. The robot of claim 18, wherein determining the first area of overlap comprises:

determining alignment scores of a plurality of candidate alignments based on a Szymkiewicz-Simpson coefficient of overlap between at least part of the first depth image and at least part of the second depth image; and

selecting an alignment from among the candidate alignments based on the alignment scores.

26. The robot of claim 18, wherein determining the first area of overlap comprises:

determining an approximate alignment between a reduced resolution version of the first depth image and a reduced resolution version of the second depth image; and

refining the approximate alignment by;

determining aggregate amounts of difference between overlapping portions of the first depth image and the second depth image at candidate alignments displaced from the approximate alignment; and

selecting a candidate alignment that produces a lowest aggregate amount of difference among the candidate alignments or selecting a candidate alignment that produces an aggregate amount of difference less than a threshold.

27. The robot of claim 18, wherein determining the first area of overlap comprises:

applying a convolution to the first depth image with a kernel function that determines aggregate measures of difference between at least part of the first depth image and at least part of the second depth image based on differences between depths in respective images; and

selecting an alignment that the convolution indicates has a smallest aggregate measure of difference.

28. The robot of claim 18, wherein determining the first area of overlap comprises:

obtaining a vector indicative of spatial displacement of the one or more sensors between the first image and the second image in a frame of reference of the working environment; and

transforming frames of reference of the second depth image and the first depth image into the same frame of reference based on the vector.

29. The robot of claim 18, wherein determining the spatial model of the working environment comprises:

determining a point cloud model of the working environment based on alignment of the plurality of depth images.

30. The robot of claim 18, wherein determining the spatial model of the working environment comprises:

determining a two-dimensional bitmap representation of obstacles in the working environment based on alignment of the plurality of depth images.

31. The robot of claim 18, wherein determining the spatial model of the working environment comprises:

updating priors of a Bayesian spatial model of the working environment from a previous mapping by the robot.

32. The robot of claim 18, comprising:

simultaneously localizing the robot and mapping the working environment, wherein the spatial model comprises positions of obstacles in the working environment and values indicating confidence scores for those respective positions, wherein;

the confidence scores are based on at least one of the following;

quality of the captured data,

noise in perceived depth,

similarity between depths recorded from different fields of view, or

confident scores of adjacent depths; and

determining the spatial model comprises pruning or determining to not add positions of obstacles with a threshold confidence score that fail to satisfy a threshold from, or to, the spatial model.

33. The robot of claim 18, comprising:

cleaning a floor with the robot based on at least part of the spatial model.

34. A method of perceiving a spatial model of a working environment, the method comprising:

capturing data by one or more sensors of a robot moving within the working environment, the data being indicative of depth within the working environment from respective sensors of the robot to objects in the working environment at a plurality of different sensor poses;

obtaining a plurality of depth images based on the captured data, wherein;

respective depth images are based on data captured from different positions within the working environment through which the robot moves,

respective depth images comprise a plurality of depth data, the depth data indicating distance from respective sensors to objects within the working environment at respective sensor poses, and

depth data of respective depth images correspond to respective fields of view;

aligning depth data of respective depth images based on an area of overlap between the fields of view of the plurality of depth images, wherein the aligning comprises;

determining a first area of overlap between a first depth image and a second depth image among the plurality of depth images by

detecting a first edge at a first position in the first image based on a derivative of depth with respect to one or more spatial coordinates of depth data in the first depth image;

detecting a second edge at a second position in the first image based on the derivative of depth with respect to one or more spatial coordinates of depth data in the first depth image;

detecting a third edge in a third position in the second image based on a derivative of depth with respect to one or more spatial coordinates of depth data in the second depth image;

deter mining that the third edge is not the same edge as the second edge based on shapes of the third edge and the second edge not matching;

determining that the third edge is the same edge as the first edge based on shapes of the first edge and the third edge at least partially matching; and

determining the first area of overlap based on a difference between the first position and the third position; and

determining a second area of overlap between the second depth image and a third depth image among the plurality of depth images, the first area of overlap being at least partially different from the second area of overlap; and

determining, based on alignment of the depth data, a spatial model of the working environment,

wherein at least some data processing of the spatial model is offloaded from the robotic device to the cloud,

wherein the spatial model is further processed to identify rooms in a floor plan, and

wherein the spatial model is stored in memory accessible to the robot during a subsequent operational session for use in autonomously navigating the working environment.

35. The method of claim 34, comprising:

storing at least part of the spatial model of the working environment in memory of the robot;

determining, with one or more processors of the robot, a path of the robot based on the at least part of the spatial model of the working environment; and

controlling, with one or more processors of the robot, an actuator of the robot to cause the robot to move along the determined path.

36. The method of claim 34, wherein:

depth data is associated with respective values indicating respective angular displacements of corresponding depths in respective frames of reference corresponding to respective fields of view;

the depth images are obtained by triangulating object depths based on captured angles at which a laser emitted from the robot and reflecting off respective objects is received at a camera sensor of the robot;

the plurality of depth data comprises a plurality of depth vectors from the sensor to objects within the working environment, respective vectors including at least one coordinate indicating relative position in a respective field of view and at least one coordinate indicating depth; and

at least some of the fields of view partly overlap with a respective preceding field of view.

37. The method of claim 34, wherein determining at least one of the first area of overlap and the second area of overlap comprises:

determining the first area of overlap based on Jacobian and Hessian matrices.

38. The method of claim 34, wherein determining the first area of overlap comprises:

thresholding the first depth image to form a first thresholded depth image;

thresholding the second depth image to form a second thresholded depth image; and

aligning the first thresholded depth image to the second thresholded depth image.

39. The method of claim 34, wherein determining the first area of overlap comprises:

determining alignment scores of a plurality of candidate alignments based on a Szymkiewicz-Simpson coefficient of overlap between at least part of the first depth image and at least part of the second depth image; and

selecting an alignment from among the candidate alignments based on the alignment scores.

40. A robot, comprising:

an actuator configured to move a robot through a working environment;

one or more sensors mechanically coupled to the robot;

one or more processors configured to receive sensed data from the one or more sensors and control the actuator; and

memory storing instructions that when executed by at least some of the processors effectuate operations comprising;

capturing data by one or more sensors of a robot moving within the working environment, the data being indicative of depth within the working environment from respective sensors of the robot to objects in the working environment at a plurality of different sensor poses;

obtaining a plurality of depth images based on the captured data, wherein;

respective depth images are based on data captured from different positions within the working environment through which the robot moves,

respective depth images comprise a plurality of depth data, the depth data indicating distance from respective sensors to objects within the working environment at respective sensor poses, and

depth data of respective depth images correspond to respective fields of view;

aligning depth data of respective depth images based on an area of overlap between the fields of view of the plurality of depth images, wherein the aligning comprises;

determining a first area of overlap between a first depth image and a second depth image among the plurality of depth images by

detecting a first edge at a first position in the first image based on a derivative of depth with respect to one or more spatial coordinates of depth data in the first depth image;

detecting a second edge at a second position in the first image based on the derivative of depth with respect to one or more spatial coordinates of depth data in the first depth image;

detecting a third edge in a third position in the second image based on a derivative of depth with respect to one or more spatial coordinates of depth data in the second depth image;

determining that the third edge is not the same edge as the second edge based on shapes of the third edge and the second edge not matching;

determining that the third edge is the same edge as the first edge based on shapes of the first edge and the third edge at least partially matching; and

determining the first area of overlap based on a difference between the first position and the third position; and

determining a second area of overlap between the second depth image and a third depth image among the plurality of depth images, the first area of overlap being at least partially different from the second area of overlap; and

determining, based on alignment of the depth data, a spatial model of the working environment,

wherein at least some data processing of the spatial model is offloaded from the robotic device to the cloud,

wherein the spatial model is further processed to identify rooms in a floor plan, and

wherein the spatial model is stored in memory accessible to the robot during a subsequent operational session for use in autonomously navigating the working environment.

41. The robot of claim 40, wherein determining the first area of overlap comprises:

applying a convolution to the first depth image with a kernel function that determines aggregate measures of difference between at least part of the first depth image and at least part of the second depth image based on differences between depths in respective images; and

selecting an alignment that the convolution indicates has a smallest aggregate measure of difference.

42. The robot of claim 40, wherein determining the first area of overlap comprises:

obtaining a vector indicative of spatial displacement of the one or more sensors between the first image and the second image in a frame of reference of the working environment; and

transforming frames of reference of the second depth image and the first depth image into the same frame of reference based on the vector.

43. The robot of claim 40, wherein determining the spatial model of the working environment comprises:

determining a point cloud model of the working environment based on alignment of the plurality of depth images.

44. The robot of claim 40, wherein determining the spatial model of the working environment comprises:

determining a two-dimensional bitmap representation of obstacles in the working environment based on alignment of the plurality of depth images.

45. The robot of claim 40, comprising:

simultaneously localizing the robot and mapping the working environment, wherein the spatial model comprises positions of obstacles in the working environment and values indicating confidence scores for those respective positions, wherein;

the confidence scores are based on at least one of the following;

quality of the captured data,

noise in perceived depth,

similarity between depths recorded from different fields of view, or

confident scores of adjacent depths; and

determining the spatial model comprises pruning or determining to not add positions of obstacles with a threshold confidence score that fail to satisfy a threshold from, or to, the spatial model.

46. A method of perceiving a spatial model of a working environment, the method comprising:

capturing data by one or more sensors of a robot moving within the working environment, the data being indicative of depth within the working environment from respective sensors of the robot to objects in the working environment at a plurality of different sensor poses;

obtaining a plurality of depth images based on the captured data, wherein;

respective depth images are based on data captured from different positions within the working environment through which the robot moves,

respective depth images comprise a plurality of depth data, the depth data indicating distance from respective sensors to objects within the working environment at respective sensor poses, and

depth data of respective depth images correspond to respective fields of view;

aligning depth data of respective depth images based on an area of overlap between the fields of view of the plurality of depth images, wherein the aligning comprises;

determining a first area of overlap between a first depth image and a second depth image among the plurality of depth images by

determining an approximate alignment between a reduced resolution version of the first depth image and a reduced resolution version of the second depth image; and

refining the approximate alignment by;

determining aggregate amounts of difference between overlapping portions of the first depth image and the second depth image at candidate alignments displaced from the approximate alignment; and

selecting a candidate alignment that produces a lowest aggregate amount of difference among the candidate alignments or selecting a candidate alignment that produces an aggregate amount of difference less than a threshold; and

determining a second area of overlap between the second depth image and a third depth image among the plurality of depth images, the first area of overlap being at least partially different from the second area of overlap; and

determining, based on alignment of the depth data, a spatial model of the working environment,

wherein at least some data processing of the spatial model is offloaded from the robotic device to the cloud,

wherein the spatial model is further processed to identify rooms in a floor plan, and

wherein the spatial model is stored in memory accessible to the robot during a subsequent operational session for use in autonomously navigating the working environment.

47. The method of claim 46, comprising:

storing at least part of the spatial model of the working environ ent in memory of the robot;

determining, with one or more processors of the robot, a path of the robot based on the at least part of the spatial model of the working environment; and

controlling, with one or more processors of the robot;

an actuator of the robot to cause the robot to move along the determined path.

48. The method of claim 46, wherein:

depth data is associated with respective values indicating respective angular displacements of corresponding depths in respective frames of reference corresponding to respective fields of view;

the depth images are obtained by triangulating object depths based on captured angles at which a laser emitted from the robot and reflecting off respective objects is received at a camera sensor of the robot;

the plurality of depth data comprises a plurality of depth vectors from the sensor to objects within the working environment, respective vectors including at least one coordinate indicating relative position in a respective field of view and at least one coordinate indicating depth; and

at least some of the fields of view partly overlap with a respective preceding field of view.

49. The method of claim 46, wherein determining at least one of the first area of overlap and the second area of overlap comprises:

determining the first area of overlap based on Jacobian and Hessian matrices.

50. The method of claim 46, wherein determining the first area of overlap comprises:

thresholding the first depth image to form a first thresholded depth image;

thresholding the second depth image to form a second thresholded depth image; and

aligning the first thresholded depth image to the second thresholded depth image.

51. The method of claim 46, wherein determining the first area of overlap comprises:

determining alignment scores of a plurality of candidate alignments based on a Szymkiewicz-Simpson coefficient of overlap between at least part of the first depth image and at least part of the second depth image; and

selecting an alignment from among the candidate alignments based on the alignment scores.

52. A robot, comprising:

an actuator configured to move a robot through a working environment;

one or more sensors mechanically coupled to the robot;

one or more processors configured to receive sensed data from the one or more sensors and control the actuator; and

memory storing instructions that when executed by at least some of the processors effectuate operations comprising;

capturing data by one or more sensors of a robot moving within the working environment, the data being indicative of depth within the working environment from respective sensors of the robot to objects in the working environment at a plurality of different sensor poses;

obtaining a plurality of depth images based on the captured data, wherein;

respective depth images are based on data captured from different positions within the working environment through which the robot moves,

respective depth images comprise a plurality of depth data, the depth data indicating distance from respective sensors to objects within the working environment at respective sensor poses, and

depth data of respective depth images correspond to respective fields of view;

aligning depth data of respective depth images based on an area of overlap between the fields of view of the plurality of depth images, wherein the aligning comprises;

determining a first area of overlap between a first depth image and a second depth image among the plurality of depth images by;

determining an approximate alignment between a reduced resolution version of the first depth image and a reduced resolution version of the second depth image; and

refining the approximate alignment by;

 

determining aggregate amounts of difference between overlapping portions of the first depth image and the second depth image at candidate alignments displaced from the approximate alignment; and

 

selecting a candidate alignment that produces a lowest aggregate amount of difference among the candidate alignments or selecting a candidate alignment that produces an aggregate amount of difference less than a threshold; and

determining a second area of overlap between the second depth image and a third depth image among the plurality of depth images, the first area of overlap being at least partially different from the second area of overlap; and

determining, based on alignment of the depth data, a spatial model of the working environment,

wherein at least some data processing of the spatial model is offloaded from the robotic device to the cloud,

wherein the spatial model is further processed to identify rooms in a floor plan, and

wherein the spatial model is stored in memory accessible to the robot during a subsequent operational session for use in autonomously navigating the working environment.

53. The robot of claim 52, wherein determining the first area of overlap comprises:

applying a convolution to the first depth image with a kernel function that determines aggregate measures of difference between at least part of the first depth image and at least part of the second depth image based on differences between depths in respective images; and

selecting an alignment that the convolution indicates has a smallest aggregate measure of difference.

54. The robot of claim 52, wherein determining the first area of overlap comprises:

obtaining a vector indicative of spatial displacement of the one or more sensors between the first image and the second image in a frame of reference of the working environment; and

transforming frames of reference of the second depth image and the first depth image into the same frame of reference based on the vector.

55. The robot of claim 52, wherein determining the spatial model of the working environment comprises:

determining a point cloud model of the working environment based on alignment of the plurality of depth images.

56. The robot of claim 52, wherein determining the spatial model of the working environment comprises:

determining a two-dimensional bitmap representation of obstacles in the working environment based on alignment of the plurality of depth images.

57. The robot of claim 52, comprising:

simultaneously localizing the robot and mapping the working environment, wherein the spatial model comprises positions of obstacles in the working environment and values indicating confidence scores for those respective positions, wherein;

the confidence scores are based on at least one of the following;

quality of the captured data,

noise in perceived depth,

similarity between depths recorded from different fields of view, or

confident scores of adjacent depths; and

determining the spatial model comprises pruning or determining to not add positions of obstacles with a threshold confidence score that fail to satisfy a threshold from, or to, the spatial model.