Computer Vision Topics

Polygonal Segmentation: Update

Its not perfect but its another milestone; my polygonal segmentation code now does a thorough enough job for one of its original intended purposes: reduction of vertices needed in path finding algorithms. Using only those vertices on a topological map which are shared between two or more convex polygons, we can generate an adjacency matrix of a relatively small size in a very short span of time (compared to using either all vertices or all passable points). This is because all-paths path finding algorithms are inherently O(v^2) algorithms so one of the best optimizations we can come up with is to mathematically reduce the set of all vertices used to the minimal set of necessary vertices in order to find our way from any point to any other point.

In choosing to include only those vertices shared by two or more polygons, we exclude all vertices that would only be visible (and therefore useful) from within a specific polygon. In other words, we only use the vertices that run between separate ‘regions’ in the map and don’t bother with those which are only useful within a specific ‘region’. Here I’m saying ‘region’ when I mean an area of a map in which any path from point X to point Y, in that same region, is a trivial matter of line of sight — in our original words: a convex polygon.

Below is the most recent output from the program, in full scale so the meticulous reader may pick up on some of the optimizations that still need to be more finely tuned.

Once the adjacency matrix is full, there should be no points in the map that are not visible from at least one of the vertices in the matrix, unless the point is within an entirely solitary convex polygon (I haven’t bothered to prove this yet, as it seems fairly obvious: one cannot be in a properly segmented map without being inside a convex polygon; one cannot be in a convex polygon and not have a line of sight to all of its vertices; there exists no convex polygon without shared vertices such that the points inside the polygon are accessible by any path from any other point in the map… something like that). This means we now have full access to the achievable shortest (or approximately so) paths from any point to any other point on our map — and we’ve done it in (again, approximately) a mathematically efficient way, both in terms of CPU time and post-processing memory allocation.

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.

struct point { int x; int y; };
 
//////////////////////////////////////////////////////////////
// Intersects(): Uses basic linear algebra to determine if two 
//    integer-based line segments intersect.
// Input: a0,a1,b0,b1 -- 2D points, each with integers x and y.
// Returns: true if line segment a0-a1 intersects b0-b1.
// (c) Jake Askeland, January 2009, http://jake.askeland.ws/
bool Intersects (point a0, point a1, point b0, point b1) {
 
    // detM = determinant of M, the matrix whose elements are
    // the coefficients of the parametric equations of lines
    // containing segments A and B.
    int detM = (a1.x - a0.x) * (b1.y - b0.y) 
             - (b1.x - b0.x) * (a1.y - a0.y);
 
    // special case: A and B are parallel.
    // when A and B are parallel, 
    // detM is 0 and a bounds test is needed.
    if (detM == 0) {
 
        // special case: A and B are vertical line segments.
        if (a0.x == a1.x && b0.x == b1.x) {
            // true if A and B are in the same vertical line.
            if (a0.x == b0.x)
                // true when some bounds on Ay 
                // are in the bounds of By.
                return (b0.y <= a0.y && a0.y <= b1.y)
                       || (b0.y <= a1.y && a1.y <= b1.y);
 
            // different vertical lines, no intersection.
            else return false;
        }
 
        // for parallel lines to overlap, they need the 
        // same y-intercept. integer relations to 
        // y-intercepts of A and B are as follows.
        int a_offset = ((a1.x-a0.x)*a0.y-(a1.y-a0.y)*a0.x) 
                   * (b1.x-b0.x);
        int b_offset = ((b1.x-b0.x)*b0.y-(b1.y-b0.y)*b0.x) 
                   * (a1.x-a0.x);
 
        // true only when A_y_intercept == B_y_intercept.
        if (b_offset == a_offset)
            // true when some bounds on ax 
            // are in the bounds of bx.
            return (b0.x <= a0.x && a0.x <= b1.x)
                   || (b0.x <= a1.x && a1.x <= b1.x);
 
        // different y intercepts; no intersection.
        else return false;
 
    }
 
    // nMitc[0] = numerator_of_M_inverse_times_c0
    // nMitc[1] = numerator_of_M_inverse_times_c1
    int nMitc[2] = {
        (b0.x - a0.x) * (b1.y - b0.y) + 
           (b0.y - a0.y) * (b0.x - b1.x),
        (b0.x - a0.x) * (a0.y - a1.y) + 
           (b0.y - a0.y) * (a1.x - a0.x)
    };
 
    // true if an intersection between two non-parallel lines
    // occurs between the given segment points.
    return ((0 <= nMitc[0] && nMitc[0] <=  detM) 
            && (0 >= nMitc[1] && nMitc[1] >= -detM)) ||
           ((0 >= nMitc[0] && nMitc[0] >= detM) 
            &&   (0 <= nMitc[1] && nMitc[1] <= -detM)); 
}