Constructing Polygonal Maps for Navigating Agents using Extracted Line Segments
This thesis describes a way to use 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 augments the HT to extend and join extracted line segments so that obstacles are more precisely represented. In a series of 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 augmented HT to a broader range of environments.