Computer Vision Topics

Topological all shortest paths automatique’ (TASPA) 1.1.0

Now bug-free for all major features!

TASPA/CVX_PART v1.1.0 — Source tarball (GPL v3)

TASPA and CVX_PART are image processing programs using arbitrary boundary
detection algorithms to generate an all-pairs shortest paths matrix and
an approximately minimal set of convex polygons (respectively) in the
ground space of a bitmap.

TASPA is designed to demonstrate a vertex thinning algorithm, using word
combinatorics to find the minimum set of convex vertices. It then applies
Thorup’s SSSP algorithm iteratively to generate a matrix whose entries
[a_ij] = “the next edge to traverse from vertex i to vertex j” in APSP.

CVX_PART demonstrates a minimum convex partitions approximation heuristic
and marks vertices shared by more than one partition, which are useful in
path-finding when a sophisticated natural line tracer is available.

Each uses monochromatic pixels (either a pixel is ‘traversable’ or
‘not-traversable’ and traversal occurs from pixel center to pixel center)
on an undirected traverability graph (A to B is equivalent to B to A).

NOTE: As far as I know, this version is bug-free for all necessary features
and is mostly bug-free for all additional features. I would appreciate any
feedback concerning bugs, along with a copy of the input and output bitmaps
from which you found them.

-Jake Askeland
jake (dot) askeland (at) gmail.com

=========================================================================
Dependencies
=========================================================================

Originally built with the following utilities:

GCC version 4.4.1 (also compiles on 3.4)
GNU Make version 3.81

Optional libraries (must be installed before-hand):

SDL-image 1.2.0 (or later)

=========================================================================
Installation
=========================================================================

— Linux and Unix derivatives (including Darwin) —
Run the following, from this directory, in this order:

./configure
make
su -c “make install”

Now you can use ‘taspa’ and ‘cvx_part’ from the command line.

— Windows —
Install a recent copy of MinGW

=========================================================================
Example Usages
=========================================================================

From the ‘bitmaps’ directory, try the following from the command line
after installation:

taspa -v -d footprint robot_map.bmp robot_map.bmp
taspa -v maze_grey.bmp maze_grey.bmp
taspa -v -d color_variation face_sm.bmp face_sm.bmp

cvx_part -v nw_sjsu_grey.bmp nw_sjsu_grey.bmp
cvx_part -v mars_grey.bmp mars_color.bmp
cvx_part -v -d lum_diff face_edge.bmp face_sm.bmp

=========================================================================
Built-in boundary detectors
=========================================================================

TASPA currently has five built in boundary detection algorithms
(referred to as distillers) which can be specified with the ‘-d
[distiller_name]‘ command line option:

luminance (default) Takes any pixel whose luminance
is above 50% of maximum as traversable.

avg_luminance Takes the average luminance of
neighboring pixels with
above 50% maximum as traversable
(good for natrual image filtering).

color_variation Pixels whose color (luminance-
independant) variation between
opposing neighbor pixels,
beyond a small threshold, are
*untraversable* (good for natrual
images with shadows).

lum_diff Compares the previous neighbor pixel to
the current pixel. If luminance diff is
less than or equal to 12.5%, pixel is
traversable.

footprint Supposes the size of the thing traversing
the map has a 9×9 footprint; thus a pixel
only remains traversable if each pixel in
the 9×9 grid surrounding it was originally
traversable.

=========================================================================
Formats supported
=========================================================================

Input formats
————–
Bitmap: 24 bit RGB (standard color bitmap)
8 bit indexed (256 colors from a 24 bit pallet; buggy)

If the SDL-image library was available when compiling Taspa, the
following formats may be supported (depending on your SDL build):
BMP, LBM, GIF, JPEG, PCX, PNG, PNM, TGA, TIFF, XCF, XPM.

Output formats
————–
Bitmap: 24 bit RGB (standard color bitmap)

=========================================================================
Known issues
=========================================================================

None.

Topological all shortest paths automatique’ (TASPA) v1.0

I’ve been writing a paper on the theory behind this project, and in the preliminaries, I derived what it means for a curve to locally concave. Through this definition, I realized my code, as it was, had two major flaws:

(1) I didn’t need to partition the map to find the minimum set of vertices required for path-finding.

(2) Using the set I was getting from convex partitioning, I would need a more sophisticated straight-line algorithm to deal with cases when source or destination lands on or near the boundary of an obstacle, at a crux of a step.

In (1), while I was at the Numenta conference last Thursday, a spark of inspiration came to me. This will be fully disclosed in my paper and so I won’t discuss it fully here. Suffice it to say, I came up with a fully word-combinatorial approach to finding the minimum set and it takes a very short linear time with respect to obstacle boundary length to fully compute. What took version 0.5 about an hour to compute takes version 1.0 about 1/10 of a second.

Because convex partitioning was no longer required for finding the minimum set, I was a little crest-fallen. I’ve spent many hours writing my convex partitioning engine from scratch, optimizing it for speed, and determining how to use it for path-finding. As most would do under such circumstances, I tried to come up with some justification, ex post facto, for having put so much of my recent life into this algorithm, and I think I’ve done it!

It occurred to me that for the same reasons as (2) but with the new combinatorial algorithm, I needed to slightly modify the path-finding wrapper to handle nitch cases where the source point is in the crux of a down-step and needs to travel along the boundary of the obstacle to reach its destination. My solution was to check for source/dest being against a boundary, store passible neighboring pixels, do the appropriate table lookup for each pair of source/dest neighbors, and use the shortest (and thus, possible) path. Mind you, after determining all-pairs shortest paths, this is a fast transaction.

But then I thought to myself, if I can do this for this slightly larger set (the true minimum set via combinatorics is typically larger than that got by shared vertices of convex partitions), its not much of a stretch to do it for the case of partitions. This is not implemented in taspa yet, but I already have code written for a text-based game I’ve been working on for some years now (_very_ part time) that does a simple heuristic for shortest path-finding, which, when given strict limits, can do a good job of circumventing a lot of irregularities in terrain, including bumpy digital lines!

Since, for many practical purposes, this is asking a lot of the end-developer that would use these algorithms for something like robotics or even video games, I have decided to split my project in two. Below are links to Taspa v1.0, including an implementation of Thorup’s algorithm, a linear time SSSP algorithm (thanks Joe Crobak!), my new word combinatorial algorithm for the minimum set, and my new bug-fix for the nitch situation, and to CVX_part v1.0, a convex partitioner for bitmaps, including all the old code, minus the path-finding.

If I hear of some interest in CVX_part as a path-finding preprocessor, I will consider putting the line heuristic and Thorup’s algorithm into it, but for now, the more clinical, provable, and elegant solution is contained in Taspa. Oh! I almost forgot to mention, I added a method to save/load path matrices to/from disk, so paths found with Taspa can be used in other programs without incorporating more than a few of its headers.

Here is the tarball. There was lots of code reuse, so only one tarball is necessary for both utilities.

TASPA/CVX_PART v1.0.1 — Source tarball (GPL v3)

TASPA/CVX_PART v1.0 — Source tarball (GPL v3)

Unlike last time, I not only expect this will be the last update on this project for a while (not counting binaries for Windows and some of the major Linux distros), I have someone to hold me to it. My friend and colleague, Alex Tsui are going to begin work on a video analytics project.

Below are a list of regressions that version 1.0.1 fixed. If you downloaded 1.0.0 and are having problems, try 1.0.1 before commenting.

Version 1.0.0 regressions If you have trouble compiling with g++ > 3.3, < 4.3, replace the following lines of code:
src/taspa.cc:423 &
src/cvx_part.cc:513
    if (reportFile.tellp() == 0) {
should read:
    std::streampos begin = 0;
    if (reportFile.tellp() == begin) {

Version 1.0.0 regressionsIf you have trouble compiling with g++ > 4.3, add the following line of code:
src/user_interface/ui.cpp:39, add
#include <stdlib.h>

Topological all shortest paths automatique’ (TASPA) v0.5

Fixed a lot of bugs, improved run-time both asymptotically (by a factor of |V| and lg|V| in a couple places) and for small input (by about 10x). Implemented a true Johnson’s algorithm for non-negative edge weights by using a Fibonacci heap (thanks for not settling for anything less, Arthur!). Added some examples to the README, along with some sample bitmaps.

TASPA v0.5 — Source tarball (GPL v3)

Further updates will likely have to wait more than a couple months, as I’m now trying to work on preparing for graduate school admissions. I might add some binaries for Windows and Mac users, though this source is now very portable.

Sample Polygon Fitting Output

I’ll be giving a presentation on polygon segmentation as it applies to path finding, which I’ll now call “polygon fitting,” as its a more succinct and probably more accurate description. In preparation, I’ve come up with some nice figures that I’d like to share with you:

A small region of Mars, rotated 90 degrees

An aerial satellite photo of Las Vegas

I had to make my own masks for these maps, as I didn’t find a boundary detection method that would give me nice, even patterns. I used a simple luminosity boundary detection algorithm on the hand-made masks and superimposed the output onto the maps you see above.

Check back soon for a demo code release!

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.