echelon

3D Vision for Embedded Systems

3D Vision is an integral part of every autonomous robot. Getting it right is not trivial and certainly not cheap. We struggled with this problem ourselves when trying to build an autonomous Mikrokopter drone. Cheap systems are not very reliable, good systems are disproportionately expensive and often very heavy. However I believe there may be hope yet for usable and cheap 3D vision systems for hobbyist and hackers alike. Granted, Microsoft is a rather unexpected reason for such hope but their Project Natal (now Kinect) might just be what we have been waiting for (image by litheon).

It’s a structured-light 3D scanner developed by PrimeSense. While being used for measuring the three-dimensional shape of an object I think it should be possible to use it as a 3D vision system for indoor robots. So I would really like to see hackers taking this cheap device apart and re-purposing it for home-brew 3D vision. In their paper “A low cost 3D scanner based on structured light“, Rocchini et al. describe how to build one and this incredible instructables article explains how to build one also and even provides source code.

Of course there are other exiting technologies out there, a comprehensive list of 3D vision devices can be found at acroname.com (including prices). The devices range from expensive but effective and impressive Time-of-flight cameras (vendors: [1] [2] [3]) to LIDAR systems. The latter were very successfully used in DARPA’s Urban Challenge autonomous driving competition. A very interesting video that describes how LIDAR works in detail is available at blip.tv.

Of course there’s also the good old ultrasonic and infrared sensors that are cheap and have low resolution and are moderately reliable but they can certainly be very useful.

Sphinx Cheatsheet

I find myself working with the Sphinx Documentation Generator a lot recently. It is a great tool to easily create intelligent and beautiful documentation and it is based on reStructuredText. I put together a cheat sheet of all the commands I frequently use. There are a number of very good ones out there ([1] [2] [3] [4]) but I find it more convenient to work with my own.

You can access the PDF from here and the source (OpenOffice Writer document) here. If you find it useful or would like an item added, feel free to leave a comment.

Matlab C++ Integration

I’m currently working on integrating some Matlab Algorithms into a larger C++ project using the Matlab Compiler. It works rather well however I stumbled across a couple of quirks and caveats. First two facts that make integrating Matlab difficult: in Matlab indexes start at 1 and Matlab arrays are column-major ordered. As a result if you want to use data fields in both C/C++ and Matlab you have to transpose the fields. If the fields contain indexes you might also have to increment and decrement the values of the fields.

Another caveat I found is also related to array indexes. When using a Matlab function that takes as parameters matrix indexes you might think of creating an mwArray of type mxUINT32_CLASS. Wrong. You have to pass indices – as strange as it sounds – as doubles so you should use mxDOUBLE_CLASS.

One custom Matlab function I wanted to use in C++ took as an argument a cell array. A cell array is an array containing other arrays. In Matlab you create a cell array like this:

a = magic(5);
b = ones(3);
z{1} = a;
z{2} = b;

If you look at z now you will get something like this:

z =
[5x5 double] [3x3 double]

An array of arrays. Easy. Well if you want to construct a cell array in C++ you have to do something like this:

mwArray a(5, 5, mxDOUBLE_CLASS);
mwArray b(3, 3, mxINT16_CLASS);
mwArray z(1, 2, mxCELL_CLASS);
z.Get(1,1).Set(a); // Sets z(1) = a
z.Get(1,2).Set(b); // Sets z(2) = b

You can find the description on this page.
If you get used to those little quirks however the Matlab Compiler is a very powerful tool to include your crazy Matlab scripts in a stand alone C++ application. One of the next things I would like to investigate are free (open source) Matlab Compiler alternatives such as the Octave C++ integration and compiler.

Civilian autonomous and remote controlled drones

Here’s a quick summary of some of the most interesting autonomous and remote controlled drones out there today. The occasion is that I and 3 others have built a quadcopter drone last semester with the goal to fly it autonomously. While the time we had to finish the project was limited and our project did not reach full autonomous flight just yet we learned a lot about the system and the challenges of such an endeavor. One team member has made the project his diploma thesis and continues to work on the vehicle.

The two images show our drone dubbed B.I.R.D. (Basic intelligent research drone) in flight and the microcontrollers and sensors that control the drone. It is based on the the Mikrokopter project.

Another very interesting drone is the nano air vehicle by AeroVironment. It’s a flapping-wing vehicle for indoors use. Check out this amazing video to see it in action. I’m guessing that while the flapping-wing design is a lot more complicated than the brushless motors in our drone it is more energy efficient.

The third drone I would like to share was built by Armadillo Aerospace. They claim level 2 of the Northrop Grumman Lunar Lander Challenge with it. For more information read on here and be sure to check out this video. Notice how large this vehicle is (can be seen in the end of the video).

The fourth drone is really scary. And it’s not civilian at all. It’s called the Multiple Kill Vehicle and was supposed to shoot down intercontinental rockets in space. The project is apparently canceled but the video is impressive and scary nevertheless. Check it out here.

Update: Researchers at MIT’s Robust Robotics Group have developed a robotic helicopter capable of autonomously flying inside buildings or other GPS-denied environments. Here’s a very interesting video about their project. They achieved what we planned for our project – and I have to say it is very impressive and they did an excellent job.

Visualizing Multithreading

I’ve been pondering about the question of how to model and visualize multithreaded applications in a simple, efficient and aesthetic way. Naturally I’ve been looking into UML behavior diagrams first but I was not really satisfied with what I found. Now I am not an expert on UML but I know my way around class diagrams, activity diagrams, sequence diagram and state machines but they all did not seem to fit what I wanted to visualize.

I wanted to show multiple threads communicating and synchronizing with each other. I’ve read the argument that something like multithreading concerns only the implementation of a system and can thus be ignored when modeling. I agree with the argument however there will come a time in the development phase of a system when one needs to think about multithreading and one wants to sketch out how the system facilitates multiple threads to be efficient. And for that I have not found good tool within UML.

So I searched for examples of diagrams that visualize multithreading. The collage shows 4 different diagrams I found rather interesting. The first one is from this page about a traffic simulator written in Java (orignal image). It shows different threads and how they signal each other. It’s simple yet quite clear what is going an. The second image is taken from a CodeProject documentation about a genetic library (original image). It sort of uses UML symbols but it’s not clear what happens at the fork and join points. The way I figure it, those symbols inside the threads are supposed to be branches not forks. The third image is also from a CodeProject page – this time it’s a how-to about avoiding an exception when using multiple threads (original image). It reminds me of a sequence diagram. There are no blocking states in the diagram and I figure in this particular application the threads are non-blocking so diagram fits the application perfectly. The fourth diagram I liked the most. It’s from the Multithreaded Programming with ThreadMentor tutorial (original image) and has special symbols for sending signals and waiting for signals.

So I gave it a try myself and tried to model a simple controller and worker thread scenario based on the last of the example diagrams I found. The gray boxes and circle represent a signaling concept where one thread can send a signal and the other thread waits until it receives the signal. I also included a shared variable that handles the task shutdown. One thread can set the variable and the other branches depending on that variable. I am not happy yet with this particular part of the image. If anyone has a better idea or pointer to resources on that topic feel free to leave a comment.

My 25 favorite Windows Applications

Here’s a list of my 25 favorite windows applications. They are all open source or free to use. By the way with most Linux distributions you get the functionality those tools provide right out of the box.

7-Zip is an open source file archiver with a high compression ratio. It supports all common archive types. Avast is a free (for personal use) anti virus kit, that protects my system from all those nasty pieces of software out there. Cygwin is an ingenious collection of tools that provides a Linux-like environment for Windows. You can use it with puttycyg to get a very easy to use Linux-like shell with all the tools you miss so badly on Windows. And for those good old DOS games you miss so much there’s DOSBox, the x86 emulator with DOS. Check out a number of old free but totally awesome games you can play on the DOSBox here. For file-transfers there’s FileZilla for FTP and for SFTP there’s WinSCP. And of course there’s everybody’s favorite browsers Firefox and Opera for browsing and ‘being connected’. From what I hear Opera 10 will be out any day now. For my document viewing, editing and creation needs I heavily rely on Texmaker, MiKTeX, GSview and of course OpenOffice.org.

For image creation I just love Inkscape. It has to be one of the greatest open source tools ever created. For graph creation I use gnuplot also I have to say I have been using the graphing tools of MATLAB a lot lately due to ease of use. For text and code editing I use either Notepad++ or Vim. It depends on my mood really. To communicate online I use mostly the cute pidgin universal chat client but I also sometimes log on to IRC using mIRC. For all my media and entertainment needs I have the great and famous VLC media player of course but I tend to use Winamp for audio playback. To download torrent files I use µTorrent and to connect to remote servers I use PuTTY.

I use XAMPP for web development and the ingenious VirtualBox x86 virtualization software for testing on different systems. When my harddrives are a cluttered mess I use WinDirStat to get a hold of the chaos and clean it up. And recently I accidentally deleted files from the SD-Card of my mobile phone and was able to recover them instantly using the awesome Photorec data recovery software.

That’s it for my list. I hope someone out there will find this list useful.

Search, search and communicate!

There’s quite a lot going on in the ever interesting internet search and communication business these days. Wolfram launched its Wolfram|Alpha search engine, Microsoft launched its new Bing search engine and Google demoed its newest product Wave. They also rather quietly released Google Squared. Here’s a graph generated with BlogPulse’s Trend Search showing the buzz these products created over the last month.

I admit the graph is a bit ambiguous and it would be much better to count the number of links in blog posts that link to the respective product. But let’s just assume that the graph is an accurate representation of the buzz those products created.

So Wolfram. I like what they did but have a couple of problems with it. For one I feel like they kind of not understood what it is all about these days. They ignore collaboration, wisdom of the crowd, free knowledge and all that good stuff we have today. But they don’t want that, they want scientific accuracy and control over their content. That’s fine I think but I would have loved to see all those smart people to contribute to a project like Wikipedia or freebase. And maybe they could have dedicated some of their enormous brainpower to finally getting NLP off the ground to provide a nice interface to all the information out there and to establish some ground rules about how we should do NLP.

Bing, well – pretty pictures. That’s really all it is for me personally. The name is certainly better than their Live Search thing but I don’t like the interface at all.

And then for Google Wave: I really hope this product will not succeed and will not revolutionize anything. It’s in the first few minutes of the demo why it would be very scary to have Wave around. Lars Rasmussen says that E-Mail is bad because it’s peer to peer, not very comfortable and whatnot. So he proposes to put the Wave (i.e. Google) in the middle of all that communication. Scary.

What’s really awesome is Google Squared. It’s by no means perfect – still a lot of rough edges – but has a lot of potential. I hope to see some serious work done on that thing and maybe an API for us developers to play with and create new things.

Convertig CSV files to LibSea graph files for CAIDA’s Walrus

Quite a few responses to my posts about social network visualization with Walrus contained questions about how to create the input files for Walrus. Walrus itself is very well documented and the LibSea graph file format is also explained in detail. But people seem to run into trouble when trying to create the spanning tree required for Walrus.

The Walrus documentation states that it only makes sense to visualize data that contain a meaningful spanning tree and that visualizations created with the help of an arbitrary spanning tree are not very useful. While that’s probably true the visualizations still look awesome. And I guess that’s what people want. Furthermore Raffael Marty from secviz.org contacted me and asked if I had a tool that could read CSV files as input and output a LibSea file for Walrus.

I didn’t have such a tool but it sounded like a fun challenge and I thought that such a tool might also help all the people who run into trouble when trying to create a spanning tree for their graphs. So I created walruscsv – a command line tool written in C++ that reads a CSV and outputs a LibSea graph file that can be visualized with Walrus. The CSV file hast to contain a link in each row and consist of 2 columns. The first column in each row represents the first node of the link and the second column the second node of the link. It automatically generates an arbitrary spanning tree.

A sample CSV file containing the links node1<->node2, node1<->node3, node3<->node4 could look like this:

node1,node2
node1,node3
node3,node4

Although Walrus is only capable of visualizing one network at a time walruscsv can handle multiple networks in one CSV file. It creates an arbitrary node and connects a node of each network to that node enabling Walrus to visualize the data. Currently the tool creates an arbitrary spanning tree so it’s not weighted and therefore not minimal.

Walruscsv reads the name of the CSV file to process as the first command line parameter passed to it. It is released under a non restrictive open source license so in addition to binaries the source code is provided. To compile it using the GNU C++ compiler simply type:

g++ wlink.cpp main.cpp wtree.cpp -o walrus.exe

You can use the program by typing

walrus.exe testfile1.csv

whereas testfile1.csv is the CSV file containing the graphs you want to visualize. Bloodshed Dev-C++ can also be used to compile the code and although I didn’t try it it should also work with C++ compilers from Microsoft (e.g. using Visual Studio). Here are the files:

Source code (the source code released to the public domain)
Test files (a collection of test CSV files)
Win32 binary
Debian x86 64bit binary

If you’re having trouble using or compiling the tool or if you have suggestions or comments of if you find a bug feel free to contact me or leave a comment.

Visualization of Social Network Reloaded

Update: I created a tool to convert CSV files to Walrus compatible LibSea files. Check out walruscvs here.

About one and a half years ago I spent a considerable amount of time experimenting with social network visualization. My methods to gather and generate the data for the visualization tools I used were very limited.

However just after posting my first results I stumbled upon the Studivz Statistics page created by Hagen Fritsch who crawled the entire social network within only 4 hours in November 2006. Back then security measures were virtually non existent so it was an easy thing to do. Today the Studivz (which is a German Facebook clone) uses a Captcha to prevent such endeavors.

Hagen Fritsch was so kind as to make the data he crawled available to me. Thanks Hagen! Not all the data, just the relevant pages to determine the connections between users in particular the “Friends” pages. So now after 1 and a half years I found some time to look at the data, analyze it and feed it to Walrus. Some results:

The first graph consists of 17142 nodes and 22838 links whereas 17141 links are part of the spanning tree Walrus uses for rendering. The second graph consists of 25313 nodes and 37794 links. Four levels of the social network are displayed meaning the tree’s depth is 4.

This two images show one of the largest graphs I created: 413193 nodes and 1247702 links with a tree depth of four. The left images only shows the spanning tree and the image on the right shows the entire network. When working with such large networks I encountered a couple of problems.

I was using PHP to create the Walrus graph file. Because of the spanning tree this is no trivial task and it became very clear that PHP is the wrong tool for it. A PHP script ran for about 4 hours to create a 30000 node graph file. I wanted bigger trees so I ported the PHP script to C++ and was surprised to find that the same task took mere seconds. This is not due to inefficient coding but PHP definitely has problems when dealing with huge junks of data especially when they are stored in associative arrays. In C++ I used hash_maps which worked out perfectly. Here are two more images of the above network:

My Celeron 1.7GHz 512MB RAM workstation thought I was being ridiculous when I loaded the 60MB text file that contained the graph into Walrus. After some swapping and heavy calculation it worked reasonably well though.

If you feel like playing around with Walrus and the data here’s a zip file containing the 3 networks on display. You can get Walrus form here. Start Walrus with the following command:

java -Xmx512m -cp mp.jar;antlrall-mod.jar;libsea.jar;walrus.jar H3Main

I added the “-Xmx512m” part to allow java to allocate more memory. This is necessary for the very large graph file. Enjoy! I will try to add a video in the next couple of days. I was also able to extract the university each of the members of the social networks attends so there are a couple of possibilities to create more visualizations.

Chrome Buzz

Here’s my try to create one of the cool trend graphs Matthew Hurst regularly entertains us with. I used blogpulse.com/trend to create the following graph:

Looks like the Chrome buzz easily surpassed the Firefox3 release buzz. Quite impressive. Unfortunately blogpulse’s trend tool allows users only to look 6 months into the past. It would be very interesting to have events such as the release of Internet Explorer 7 or the announcement of Safari for Windows on that graph too.

Older Posts »