November 2009 Archives

The last few months, I've been doing a school project together with two other students in the course "Image processing and pattern recognition," which had as its goal to control a small micro robot through an obstacle course using nothing but the images taken by a camera in the roof.

The project was done entirely in MATLAB, with some code supplied by the school to control the robot, and some proof-of-concept code written by me in Python. Now, the project is over, and I thought I'd go through the solution we came up with here.

Detecting the robots and obstacles
To find the robot and the obstacles on the field, we decided to use a "base" image of the field when it's empty as a way to discern what's supposed to be there and what isn't. We then take a picture of the field with the robot in the starting position, move the robot forward a little bit, then take another picture.

These two pictures are then subtracted from the base picture and converted to binary images where every pixel value above 2 becomes white, and the rest becomes black. Then we apply a filtering algorithm (morphological opening-then-closing for the ones in the know) that removes whatever noise particles is left and connects certain disconnected pieces of the obstacles. Now we have sufficient grounds to discern what is an obstacle and what is the robot, as well as which direction the robot is facing.

Binary image

Morphologically filtered image

To find the obstacles, we just look at which pixels in the pictures stay the same (a simple AND operation between the two images), and the object that has moved is then the robot. To find the angle and position of the robot, all you need to do is see how far the moving objects' centers have moved.

Path-finding
Now, the remaining part of the task to be done before we can even start moving the robot towards the goal is to figure out which way it should go, so as to reach the goal AND avoid the obstacles. To do this, we decided to lean on the juggernaut of path-finding known as A*, favourite of game devs.

Before we could apply this, though, we have to convert the field image to a more game-like "tile-set". So we basically go over the image with only the obstacles, split it into tiles of a given size, and check how many white pixels each tile contains. If it crosses a threshold (we got it down so nicely we could use a threshold of 1 pixel), then it is marked as uncrossable (a "wall") in the resulting tile matrix, otherwise it's walkable.

Resulting tile matrix

We then run the A* algorithm over the image, with the current robot position, and the goal position, to get the goal path as a set of nodes per tile to cross. As this isn't exactly the best path to follow (way too many stops and turns), we then apply a further algorithm to smooth the path

Path-smoothing
To do this, we chose to use a method we call "ray-casting" to weed out unnecessary path nodes. Imagine we have a path as detailed in this picture, with the start and end nodes marked as "valid" (green):

We start with the first node, draw a line (ray) to the next node in the path, then draw two more lines parallel to that at a distance representing the robot's width, as so:

We keep doing this for every node of the path, until any of these lines collide. When this happens we know that this node cannot be reached directly from the node we're checking for, and as such we need to mark the previous node as valid.

After we have done this for all the nodes, and reached the end node, we are left with a path that has significantly less nodes, as well as more direct paths where there was a stepladder effect previously.

The last mile
Now, finally, we can move the robot through the path we have created. This is done by sending commands to the robot to rotate, and move a certain distance towards the next node in the path. As the robot isn't entirely precise, we decided to not let it move too far per movement command, so it wouldn't veer off course too much, and would be given a chance to "compensate" as it moves towards the goal.

The movement is tracked by taking a new picture with the camera, and doing the same filtering operations as before to find the new robot position and angle, so that we can guide it closer to the node as it approaches. If all goes as planned, it should eventually reach the goal position, without colliding into any of the obstacles!

If you've used Django before, you may have remembered that Django's admin pages had a Documentation link in the top right corner. This lead to a site which provided documentation for all Models, Views, Tags and Filters that exist in your project, which is immensely useful for devs and designers alike.

In the newer versions of Django this has seemingly disappeared, and the official documentation makes very little mention of it, as it has been split into its own (as of yet undocumented) app. So, you have to enable it yourself by adding the admindocs app and setting up an url pattern for it.

So, to accomplish this, first open up your settings.py and add 'django.contrib.admindocs' to your INSTALLED_APPS, set a SITE_ID if you haven't done so already, then do the following with your urls.py:

urlpatterns = patterns(
    '',
    (r'^admin/doc/', include('django.contrib.admindocs.urls')),
    (r'^admin/(.*)', admin.site.root), # Standard admin url pattern
    # Other URL patterns go here
)

Note that the admindocs pattern has to go before the standard admin pattern, because Django gives you the first view from the top that matches, and the admin pattern is very hungry. :)

Now when you go into the admin section, you should have a shiny new Documentation link that leads to Django's automatic documentation for your project. Enjoy!

The last few days I've been working on a project using Django, and to set up my Django projects, I find the best solution is using Buildout. I think messing around with virtual environments is annoying, makes it harder to deploy the project later, and frankly just wastes my time more than it saves it. (It also happens to be the way I learned to do it while working at Opera, but that's besides the point ;) )

The basics

Getting started with Django and Buildout essentially requires two files, the Zope bootstrap.py (available here) and a buildout.cfg for configuring your environment.

A basic buildout.cfg file, utilizing Djangorecipe to install Django, would look something like this:

[buildout]
parts = django

[django]
recipe = djangorecipe
version = 1.1.1
eggs =
	mock
	django-notification
	django-messages
project = my-django-project

This is the configuration for a simple Django project called "my-django-project", which depends on the mock, django-notification and django-messages modules. To build and set up this, you simply enter the following commands:

python bootstrap.py
python bin/buildout

This first runs the bootstrap file, which fetches the necessary modules for running buildout and gives you a buildout binary in the bin/ folder. Then you run the buildout command, which parses the buildout.cfg file, automatically fetching the necessary dependencies, the given Django version (in this case 1.1.1, but you could set it to "trunk" to get the newest development version), and create a version of the Django manager script at bin/django.

This script does exactly what the manage.py script does in a regular django setup, to sync the db you run bin/django syncdb, to start the server you type bin/django runserver, and so on and so forth.

If this is the first time you run the buildout, djangorecipe will also check for the presence of a directory called "my-django-project", and if that doesn't exist, it will create a skeleton Django project with that name, which serves as a great starting point.

All of this greatly simplifies the amount of work needed to start a new django project, you just mock up a tiny buildout config and run buildout, and you have what you need to start easily set up for you.

Taking it further

Now, for me, this still isn't simple enough. It requires the presence of the bootstrap.py file (which isn't strictly a part of the project, and IMO shouldn't be in source control), and two commands. So I made myself a little Makefile to automate the task of running buildout, and it looks a little something like this:

.DEFAULT_GOAL = development
.PHONY = development clean

bootstrap.py :
	wget http://svn.zope.org/*checkout*/zc.buildout/trunk/bootstrap/bootstrap.py

bin/buildout : bootstrap.py
	python bootstrap.py

development : bin/buildout
	python bin/buildout

clean :
	rm -rf bin develop-eggs eggs parts .installed.cfg downloads bootstrap.py

This allows me to simply type in "make" in the directory with the buildout config, and everything will be done automatically, and subsequently type "make clean" if I need to clean out the environment again.

Together with this, I've added a .gitignore file (since I use Git for most of my source control needs), that filters out all the buildout cruft, as well as .pyc files and the SQLite db, if you're using one:

*.egg-info
*.egg
*.pyc
*.db
.installed.cfg
bin/
develop-eggs/
downloads/
eggs/
parts/

These two relatively minor additions allow me to more or less forget about everything that has to do with python virtual environments or even that you need to do special things to make it work. Updating the environment is just a simple "make" away, and the resultant environment stays out of my way in git.