System and method for automatically annotating a map

Patent metadata

Field	Value
Publication number	US-10853561-B2
Application number	US-201916380867-A
Country	US
Kind code	B2
Filing date	Apr 10, 2019
Priority date	Apr 10, 2019
Publication date	Dec 1, 2020
Grant date	Dec 1, 2020

Abstract

A system for automatically annotating a map includes: a robot; a server operably connected to the robot; file storage configured to store files, the file storage operably connected to the server; an annotations database operably connected to the server, the annotations database comprising map annotations; an automatic map annotation service operably connected to the server, the automatic map annotation service configured to automatically do one or more of create a map of an item of interest and annotate a map of an item of interest; a queue of annotation requests operably connected to the automatic annotation service; and a computer operably connected to the server, the computer comprising a graphic user interface (GUI) usable by a human user.

First claim

What is claimed is:

1. A method for automatically annotating a robotic map, comprising:
setting corners of the robotic map to a frontier marking;
performing a first flood fill near each of the corners of the map, using the corners as seeds for the first flood fill;
setting neighbor pixels to the frontier marking to create expanded frontier corners comprising frontier pixels;
performing a second flood fill near each of the expanded frontier corners, using the expanded frontier corners as seeds for the second flood fill;
setting expanded neighbor pixels to the frontier marking to create further expanded frontier regions;
repeating the steps of performing the second flood fill and setting the expanded neighbor pixels until all unobserved pixels connected to one of the frontier corners have been set to the frontier marking and no more neighboring frontier pixels remain;
dilating the frontier pixels by one pixel to generate new frontier pixels;
repeating the dilating step a number of times equal to a number of pixels in a frontier bridge increment;
converting all frontier pixels to free space;
converting remaining unobserved pixels to obstacle pixels;
dilating obstacle pixels by an obstacle bridge increment;
eroding obstacle pixels by the obstacle bridge increment;
identifying an obstacle pixel as a seed pixel not part of an obstacle group;
using the seed pixel to create a new connected group comprising a set of contiguous obstacle pixels that are contiguous to the seed pixel;
adding the contiguous obstacle pixels to the seed pixel to create a larger obstacle group;
repeating the steps of identifying the obstacle pixel, creating the new connected group, and adding the contiguous obstacle pixels until all pixels connected by obstacle pixels to the original seed pixel are added to create finished obstacle groups;
creating convex hulls for the finished obstacle groups; and
displaying the map.

2. The method of claim 1 , wherein the step of performing the first flood fill comprises categorizing pixels that are adjacent to a corresponding corner as neighbor pixels if the pixels comprise unobserved pixels.

3. The method of claim 1 , wherein the step of performing the first flood fill further comprises leaving pixels that are adjacent to a corresponding corner unchanged if the pixels do not comprise unobserved pixels.

4. The method of claim 1 , wherein the step of performing the second flood fill comprises categorizing expanded neighbor pixels that are adjacent to a corresponding corner as neighbor pixels if the pixels comprise unobserved pixels.

5. The method of claim 1 , wherein the step of performing the second flood fill further comprises leaving expanded neighbor pixels that are adjacent to a corresponding corner unchanged if the pixels do not comprise unobserved pixels.

6. The method of claim 1 , wherein the step of converting the frontier pixels comprises removing outer walls of the map.

7. The method of claim 1 , wherein the step of converting the frontier pixels comprises removing free space in the map.

8. The method of claim 1 , wherein the displaying step comprises identifying output vertices for the finished obstacle groups.

9. The method of claim 8 , wherein the output vertices comprise vertices of keepout polygons.

10. The method of claim 1 , comprising a further step, performed after the displaying step, of creating an annotation of the final map.

11. The method of claim 10 , comprising an additional step, performed after the step of creating the annotation, of receiving input from a human annotator.

Assignees

• Fetch Robotics Inc

Inventors

• Avagyan Levon
• Feng Jiahao
• Henning Alex
• Ferguson Michael
• Wise Melonee
• King Derek

Classifications

• G06F40/169 Primary

  Annotation, e.g. comment data or footnotes · CPC title

• G06V20/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 title

• G06T11/26

  Drawing of charts or graphs · CPC title

• G06V20/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 title

• G01C21/3848 Primary

  Data obtained from both position sensors and additional sensors · CPC title