For more on the DAS team’s achievements, check out their the ERL website. Also, be sure to check out “Shelly”, the autonomous TTS will set the first official autonomous land-speed record in May!

As it stands, I have tested Taspa 1.2.0 with Fedora 11.1 (x86_64) and compiled with GCC 3.4 and 4.4, and Intel C++ 11.1. Windows binaries might take a while, as tests have failed miserably thus far (using Windows 7, 64-bit).

TASPA v1.2.0 — Source tarball (GPL v3)

DOSA, rev. 1

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.

This article describes in good detail the algorithm I wrote a couple months ago when I discovered a simple method for finding digitally convex end-points in TASPA. Do not hesitate to comment with questions; it would be good to know if I and those who’ve proof read missed something.

Thanks go to Kate, Alex, Dr. Taylor, and Dr. Teoh for their support.

Oct-22-2009 Addendum — Runtime of all-pairs shortest paths on integer edge weights using Thorup’s algorithm is written in the caption to Figure 6 as O(n^2) and should be O(n^2 + nm).

(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>

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.

TASPA is a designed to demonstrate a transitional vertex thinning algorithm based on convex polygon fitting. It makes a copy of the input bitmap file, showing the fitted polygons, the vertices used in path finding after thinning, and (optionally) a sample shortest path between two random points. For now, TASPA is limited to monochromatic pixel weights (either a pixel is ‘passable’ or ‘impassible’ and ‘passable’ pixels have a weight of 1) and undirected graphs (A to B is equivalent to B to A). It is possible this will be extended to support multi-chromatic (semi-passable) pixel weights and even weight heuristics, such as ’safest route’ vs. ’shortest route’ balancing. Please inform me if you have any particular features you would like to see in future releases.

Source tarball (GPL v3)

NOTE: I would appreciate any feedback concerning bugs, along with a copy of the input and output bitmaps from which you found them.

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!