Constructing Polygonal Maps for Navigating Agents using Extracted Line Segments

This research uses line segments extracted from images to construct precise polygonal maps of obstacles in an environment. Agents such as robots or animated characters could use naively extracted line segments to avoid obstacles as part of intelligent navigation, except that extracted segments do not usually perfectly represent obstacles: for example, squares found by a popular technique called the Hough Transform (HT ) often have gaps in one side or have two sides that do not meet at a corner. This research presents an augmented HT, the AugHT, to extend and join extracted line segments so that obstacles are more precisely represented. The original HT extracts line segments by identifying areas of high contrast (edges) in an image, then creating a two-color image with the identified edges as white foreground pixels. Each foreground pixel is said to provide evidence for the presence of lines that could pass through it, and lines supported by at least a threshold amount of evidence are identified as features of the image. Additional processing determines the endpoints of the line segments. The AugHT joins line segments into polygons by extending endpoints and removing overlapping lines. The AugHT was tested on images provided by a ceiling-mounted camera that depicted obstacles of varying shapes (lines, rectangles, other polygons and shapes with curves) in a controlled laboratory environment. The line segments returned by the AugHT were compared with the line segments returned by the original HT. In preliminary tests, simple shapes were represented precisely, but more complicated shapes were sometimes mistakenly joined to other shapes or confused with noise in the image. Future work could improve the line-joining algorithm and generalize the AugHT to a broader range of environments.