Archive for October, 2009
The Double Order Scaled Approximation (DOSA), rev. 1
This is a companion paper proving scaled integer edge weights can be used as in Thorup’s algorithm
for SSSP to retrieve shortest paths in two-dimensional obstacle maps in grid-space. The proof extends to
n-dimensional spaces over the integers. Before getting started, we need to cover some ground covered in my
paper (pending publication; see below) regarding digital curvature and pathfinding.
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.