Polygonal Segmentation of Topological Maps
Since last May I’ve been building a set of tools to help process topological imagery and today I’ve struck a milestone on one of them: my algorithm which segments maps into convex polygons, thus aiding placement of cameras required for omniscient visual surveillance. Here is an example of what it does:
North-east quadrant of San Jose State (from sjsu.edu), scaled for web to 50%
Same region, ground mapped into convex polygons, scaled for web to 50%.
The reader may note there are at least three polygons missing from the map. I’m still working this out, but it only occurs against vertical and horizontal edges whose vertices have all been used to make polygons adjacent to the polygon which is missing. So there are at least inelegant ways to correct the problem; though I’m still searching for the elegant solution.
Interestingly enough, the code involving polygon generation took less time to write than the code involving vertex detection. I wound up writing routines for the following: Discover figures as regions (shown in the output in black); Generate relative directional words (formed of letters L,R,F,B) from a walk around each region’s perimeter; Pattern match maximal Bresenham line type palindromes in each word, marking word indices that represent end points of lines; and Determine best-fits for adjacent vertices.
Also interestingly, my run-time was cut from 2 minutes to 4 seconds on a 420×300 pixel map simply by replacing naive floating point approaches to line intersection detection and line generation with integer only approaches (see my posting on intersection detection code for the first and see any information concerning the Bresenham line algorithm for the second).
Now upon code profiling, the highest cumulative consumer of CPU time is an STL map of STL maps of vertex pairs being called upon to regurgitate adjacency information (called 4964009 times in 0.25 seconds on my 1.8 core2 duo, using gcc -O1 optimization on the resultant map above). Since the complexity of the task requires many such calls, further reduction of runtime may better be achieved through parallelization and/or use of a GPU.
I won’t be releasing any code for this project until its fully functional but please don’t hesitate to mention if its code you’d like to look at.