ICRA 2011: Traffic Lights
Jesse Levinson, Jennifer Dolson, Sebastian Thrun, and I submitted “Traffic Light Mapping, Localization, and State Detection for Autonomous Vehicles” to the 2011 IEEE International Conference on Robotics and Automation (ICRA 2011). My contributions so far have been a new method for assisted automatic traffic light mapping and a new image processing algorithm, which are now running on Junior.
Screen shot from the traffic light state detection algorithm running on a log file from Junior.
Stanford / VW Autonomous Driving
Last week I was half invited and I half invited myself to attend a meeting for the Stanford Autonomous Vehicle Racing Team along with my VWoA-ERL coworkers. Some interesting ideas were mentioned, such as a method for re-lighting a scene using a light scattering formula to reconstruct points’ surface normals and textural qualities from velodyne data captured by Junior (by Jesse Levinson). At the end of the meeting I offered some of my time to finish a system they’ve been developing for detecting traffic lights for their next-generation Junior vehicle! That should make April and May pretty interesting!
Volkswagen Internship
I started a 7 month internship with VW-ERL last month, working with the Driver Assistance Systems (DAS) team on confidential, vision-related things — if I told you, they’d have to kill me! I’ve already hit some significant milestones with the project they put me on; we finished the second internal release (since the project’s conception, earlier last year) as of Friday, which included two components I developed! My biggest challenge so far has been to be as relaxed and fun-loving as my teammates! Suffice it to say, I’m having a great time.
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!
Taspa v.1.2.0 (Last major update!)
After a two-month hiatus, I’ve fixed the mechanical bugs in Taspa. CVX_Part was already working to the desired specifications and so I did not include it in this update. Since Taspa is now also up to spec, this will be the last major update on these projects. Further posts will be binary releases on all the major OS’s and distros.
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)
Here’s some fun output I generated by adding curvature coloration:
The Double Order Scaled Approximation (DOSA)
The purpose of this paper is to prove scaled integer edge weights can be used to retrieve shortest paths in two-dimensional obstacle maps in grid-space, thus allowing the use of integer-only single source shortest paths (SSSP) algorithms such as Thorup’s. The proof should extend to n-dimensional spaces over the integers.
DOSA, rev. 2 (Updated October 5, 2010)
DOSA, rev. 1
Using integer-only algorithms usually improves performance by a factor of between 10 and 200 just by eliminating usage of the math co-processor. In this case, Thorup’s algorithm also brings down the asymptotic runtime to O(m + n) for SSSP as compared to a Fibonacci heap implementation of Dijkstra’s, which is O(m + n lg n). For all pairs shortest paths on very sparse graphs, this can make a significant difference.
The result of my proof shows Thorup’s is allowable so long as you scale your edge weights by 2n - 1. Practically speaking, this limits a system with integers of x bits to solving SSSP over graphs with the following constraint; let u be an edge in graph G with maximum weight ||u|| (ie: no edge in G has weight > ||u||) and let n be the number of vertices in G. Then (2n - 1)||u|| < 2^x, or x > lg(2n - 1) + lg(||u||) or n < (2^(x-1) / ||u||) + 1/2. For example, on a 32-bit system over a graph with 10,000 vertices, each edge must have a weight less than about 214,759. In case this isn’t enough, the same graph on a 64-bit system can accommodate edge weights of up to 922,383,322,851,620 (nearly a quadrillion)!
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
Fast, Exact Digital Curvature Detection
Linked here is a PDF of my paper, submitted to Computational Geometry: Theory and Applications* titled “Fast Exact Convex and Concave Curvature in Digital Images with an Application in Path-finding [PDF of the working paper ].
This article describes in detail the algorithm I wrote a couple months ago when I discovered a simple method for finding digitally convex end-points in TASPA (see previous posts in the Projects section). For those who are interested, I’m writing a proof to confirm I can use Thorup’s algorithm for all pairs shortest paths in an integer-coordinate grid after scaling edge weights by 2|V| - 1.
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).
* As of June 2010, the paper was declined. Considering my focus has changed and my understanding of the topic has matured, I will just post updates to the working paper.
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.
Topological all shortest paths automatique’ (TASPA) v0.4
As promised, here’s the initial release of the polygon fitting source code! Most have had no trouble installing it under various distributions of Linux. The install script does run into problems in various BSD installations and is untested under MacOS and Windows. That said, leave a comment if you run into problems so I can make the next package a little better 
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.
NOTE: I would appreciate any feedback concerning bugs, along with a copy of the input and output bitmaps from which you found them.