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!