System and method for automatically annotating a map

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.