Method and apparatus for combining data to construct a floor plan

• US 10,740,920 B1
• Filed: 10/07/2019
• Issued: 08/11/2020
• Est. Priority Date: 07/27/2017
• Status: Active Grant

• Current Assignee: Ai Incorprated
• Original Assignee: Ai Incorprated
• Inventors: Ebrahimi Afrouzi, Ali, Zhang, Chen, Schweigert, Sebastian
• Primary Examiner(s): Osinski, Michael S
• Application Number:
  US16/594,923
• Time in Patent Office: 309 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 including capturing a plurality of images by at least one sensor of a robot; aligning, with a processor of the robot, data of respective images based on an area of overlap between the fields of view of the plurality of images; and determining, with the processor of the robot, based on alignment of the data, a spatial model of the environment.

Claims

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

capturing a plurality of images by at least one sensor of a robot moving within the environment, wherein;

respective images comprise data comprising at least one of;

pixel data indicative of features of the environment captured in the respective images and depth data indicative of depth from respective sensors of the robot to objects in the environment captured in the respective images;

respective images are captured from different positions within the environment through which the robot moves; and

respective images correspond to respective fields of view;

aligning, with a processor of the robot, data of respective images based on an area of overlap between the fields of view of the plurality of images, wherein aligning comprises;

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

detecting a feature in the first image;

detecting the feature in the second image;

determining a first value indicative of a difference in position of the feature in the first and second 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 data from which the first image is obtained and when data from which the second image is obtained; and

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

determining, with the processor of the robot, based on alignment of the data, the spatial model of the environment.

2. The method of claim 1, wherein the characteristic comprises at least one of:

a collection of pixels, each pixel comprising at least one value;

a pattern of pixel values;

a particular arrangement of pixel values;

a collection of depth readings, each depth reading comprising at least one value;

a pattern of depth values;

a particular arrangement of depth values;

a collection of feature vectors; and

a feature.

3. The method of claim 1, comprising:

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

determining, with the processor of the robot, a path of the robot based on the at least part of the spatial model of the environment; and

actuating, with the processor of the robot, the robot to navigate along the determined path.

4. The method of claim 3, further comprising determining the location of the robot with respect to the spatial model of the environment, wherein determining the location comprises:

detecting a feature in a first image;

detecting the feature in the spatial model of the environment; and

determining a location of the robot with respect to the spatial model of the environment.

5. The method of claim 1, wherein:

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

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

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

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

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

7. The method of claim 1, wherein aligning further comprises:

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

8. The method of claim 1, wherein the first area of overlap is determined based on Jacobian and Hessian matrices.

9. The method of claim 1, wherein determining the first area of overlap further 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 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 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 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.

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

thresholding the first image to form a first thresholded image;

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

aligning the first thresholded image to the second thresholded image.

11. The method of claim 1, wherein determining the first area of overlap further 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 image and at least part of the second image; and

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

12. 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 image and a reduced resolution version of the second image; and

refining the approximate alignment by;

determining aggregate amounts of difference between overlapping portions of the first image and the second 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.

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

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

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

14. The method of claim 1, further comprising:

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 environment; and

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

15. The method of claim 1, wherein determining the spatial model of the environment further comprises:

determining a point cloud model of the environment prior to determining the spatial model.

16. The method of claim 1, wherein determining the spatial model of the environment further comprises:

determining a two-dimensional bitmap representation of obstacles in the environment.

17. The method of claim 1, wherein determining the spatial model of the environment further comprises:

updating priors of a Bayesian spatial model of the environment.

18. The method of claim 1, further comprising:

simultaneously localizing the robot and mapping the environment, wherein the spatial model further comprises positions of obstacles in the environment and confidence score values indicative of the location of the robot corresponding with each of those respective positions, wherein;

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

quality of the captured data,

noise in captured data,

similarity between the values of data recorded from different fields of view, or

confident scores of adjacent data; 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.

19. The method of claim 1, further comprising:

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

20. The method of claim 1, further comprising:

capturing depth data with a distance sensor of the robot; and

determining or updating, with the processor of the robot, the spatial model of the environment based on the depth data.

21. The method of claim 20, wherein the distance sensor is a time of flight sensor.

22. The method of claim 1, further comprising:

determining, with the processor of the robot, a second spatial model; and

layering, with the processor of the robot, the second spatial model on top of the spatial model.

23. The method of claim 22, wherein different sensors capture the data from which the spatial model and the second spatial model are determined.

24. The method of claim 22, wherein the spatial model and the second spatial are combined to create a third spatial model, and wherein the processor uses the third spatial model for autonomously navigating the environment.

25. The method of claim 1, further comprising:

actuating, with the processor, the robot to contact an obstacle within the environment; and

determining, with the processor, a distance of the obstacle from the robot based on the physical contact with the obstacle.

26. The method of claim 1, wherein different sensors capture images comprising pixel data and images comprising depth data.

27. The method of claim 1, wherein the spatial model is further processed to identify rooms in a floor plan.

28. The method of claim 1, wherein at least some data processing of the spatial model is offloaded from the robot to the cloud, and wherein the spatial model is stored in memory accessible to the robot during a subsequent operational session for use in autonomously navigating the environment.

29. A robot for perceiving a spatial model of an environment, comprising:

an actuator configured to move the robot through the environment;

at least one sensor mechanically coupled to the robot;

a processor configured to receive sensed data from the at least one sensor and control the actuator; and

memory storing instructions that when executed by the processor effectuates operations comprising;

capturing a plurality of images by at least one sensor of a robot moving within an environment, wherein;

respective images comprise data comprising at least one of;

pixel data indicative of features of the environment captured in the respective images and depth data indicative of depth from respective sensors of the robot to objects in the environment captured in the respective images;

respective images are captured from different positions within the environment through which the robot moves; and

respective images correspond to respective fields of view;

aligning, with a processor of the robot, data of respective images based on an area of overlap between the fields of view of the plurality of images, wherein aligning comprises;

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

detecting a feature in the first image;

detecting the feature in the second image;

determining a first value indicative of a difference in position of the feature in the first and second 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 data from which the first image is obtained and when data from which the second image is obtained; and

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

determining, with the processor of the robot, based on alignment of the data, the spatial model of the environment.

30. A method of perceiving a spatial model of an environment, the method comprising:

capturing a plurality of images by at least one sensor of a robot moving within the environment, wherein;

respective images comprise data comprising at least one of;

pixel data indicative of features of the environment captured in the respective images and depth data indicative of depth from respective sensors of the robot to objects in the environment captured in the respective images;

respective images are captured from different positions within the environment through which the robot moves; and

respective images correspond to respective fields of view;

aligning, with a processor of the robot, data of respective images based on an area of overlap between the fields of view of the plurality of images, wherein aligning comprises;

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

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 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 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 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, with the processor of the robot, based on alignment of the data, the spatial model of the environment.

31. A method of perceiving a spatial model of an environment, the method comprising:

capturing a plurality of images by at least one sensor of a robot moving within the environment, wherein;

respective images comprise data comprising at least one of;

pixel data indicative of features of the environment captured in the respective images and depth data indicative of depth from respective sensors of the robot to objects in the environment captured in the respective images;

respective images are captured from different positions within the environment through which the robot moves; and

respective images correspond to respective fields of view;

aligning, with a processor of the robot, data of respective images based on an area of overlap between the fields of view of the plurality of images, wherein aligning comprises;

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

detecting a characteristic in the first image;

detecting the same characteristic in the second image;

determining the first area of overlap based on at least a position of the characteristic in the first and second images;

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

refining the approximate alignment by;

determining aggregate amounts of difference between overlapping portions of the first image and the second 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, with the processor of the robot, based on alignment of the data, the spatial model of the environment.

32. A method of perceiving a spatial model of an environment, the method comprising:

capturing a plurality of images by at least one sensor of a robot moving within the environment, wherein;

respective images comprise data comprising at least one of;

pixel data indicative of features of the environment captured in the respective images and depth data indicative of depth from respective sensors of the robot to objects in the environment captured in the respective images;

respective images are captured from different positions within the environment through which the robot moves; and

respective images correspond to respective fields of view;

aligning, with a processor of the robot, data of respective images based on an area of overlap between the fields of view of the plurality of images, wherein aligning comprises;

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

detecting a feature in the first image;

detecting the feature in the second image;

determining a first value indicative of a difference in position of the feature in the first and second 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 data from which the first image is obtained and when data from which the second image is obtained; and

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

determining, with the processor of the robot, based on alignment of the data, the spatial model of the environment,

wherein at least some data processing of the spatial model is offloaded from the robot 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 environment.

33. A method of perceiving a spatial model of an environment, the method comprising:

capturing a plurality of images by at least one sensor of a robot moving within the environment, wherein;

respective images comprise data comprising at least one of;

pixel data indicative of features of the environment captured in the respective images and depth data indicative of depth from respective sensors of the robot to objects in the environment captured in the respective images;

respective images are captured from different positions within the environment through which the robot moves; and

respective images correspond to respective fields of view;

aligning, with a processor of the robot, data of respective images based on an area of overlap between the fields of view of the plurality of images, wherein aligning comprises;

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

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 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 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 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, with the processor of the robot, based on alignment of the data, the spatial model of the environment,

wherein at least some data processing of the spatial model is offloaded from the robot 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 environment.

34. A robot for perceiving a spatial model of an environment, comprising:

an actuator configured to move the robot through the environment;

at least one sensor mechanically coupled to the robot;

a processor configured to receive sensed data from the at least one sensor and control the actuator; and

memory storing instructions that when executed by the processor effectuates operations comprising;

capturing a plurality of images by at least one sensor of a robot moving within an environment, wherein;

respective images comprise data comprising at least one of;

pixel data indicative of features of the environment captured in the respective images and depth data indicative of depth from respective sensors of the robot to objects in the environment captured in the respective images;

respective images are captured from different positions within the environment through which the robot moves; and

respective images correspond to respective fields of view;

aligning, with a processor of the robot, data of respective images based on an area of overlap between the fields of view of the plurality of images, wherein aligning comprises;

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

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 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 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 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, with the processor of the robot, based on alignment of the data, the spatial model of the environment.