interactive recognition of hand-drawn circuit diagrams

After six years of study I completed my degree of BEng/MScEng (with computer science) last week. Yay! Here is a video of the final prototype:


You can download my full thesis or some slides.

Edit 2011/02/01: Here is the source code. It's a bit of a mess and it's going take a bit of work to get it going on newer systems because it probably requires an older wxWindows. The interesting parts are in src/linetools.py. If you find it useful or reference my work I'd love to hear about it.

One of my favourite opinionated parts:

It is generally believed that state coverage is superior to code coverage. It is the author's opinion, however, that state coverage is less important in Python than other languages. As Python typically processes collections (such as lists) using an iterator and not incrementing indices, there are less ways in which errors can occur. Since variables also need not be declared it is also less likely that null pointers would be dereferenced. This is, for example, one of the most frequent sources of errors in the Java programming language.

ICFP contest done

My team and I participated in this year's ICFP programming contest - a weekend of very little sleep and lots of programming. This was the first year our team (i.e. The Black Knight Always Triumphs) took part.

We were amazed at the effort the judges must have gone through to prepare the problems. My favorite problems where writing the virtual machine that ran the problems and hacking into "user accounts" using their stripped down version of Basic which uses Roman numerals for line numbers.

We expect to finish under the first third of participants (that made it to the scoreboard) and we'll definately be back next year.

del.icio.us importing

I wanted to change my del.icio.us username. You aren't allowed to do this directly, but you can export your links to an html file and try to import it back into a new account. Unfortunately their import function can't parse the data generated by their export function. Strange. (apparently fixed now) Luckely they have an open API (and a whole bunch of third-party tools).

So with the help of BeautifulSoup I simply parsed the exported html and used pydelicious to post it back into delicious. Like So:

from BeautifulSoup import BeautifulSoup
import pydelicious
from itertools import count

def main():
  soup = BeautifulSoup(file("export.htm").read())
  user = "user"
  password = "pass"
  items = soup.findAll("a")
  print len(items)
  for item, n in zip(items, count()):
    href = item["href"]
    tags = item["tags"]
    title = item.string
    add_date = item["add_date"]
    last_modified = item["last_modified"]
    print n,
    try:
      pydelicious.add(user, password, href, title, tags=tags, dt=add_date, replace="yes")
    except Exception, e:
      print e

Ah, I love Python.

While writing this post I ran into some del.icio.us experiments, which might be useful to someone. And a follow-up with very pretty graphs.

I want; I need

Feature requests I filed in last half hour. Not all of them are really thought through that well, but I just want to be sure the developers are aware of my needs.

7-zip (compression):

• checkout/install files
• always extract to subfolder

Flock (webbrowser):

• customize search engines from options
• links on page work between link is followed and one is activated

wikidPad (note keeper):

• scan icons subdirectory and image pasting also copies image to a subdir

os.listdir iterator

I found an iterator version of os.listdir for POSIX(?) systems, but I needed one for Windows. Specifically to check if a directory has subdirectories.

import win32file import pywintypes def has_subdirectories(path): try: for info in win32file.FindFilesIterator(os.path.join(path, "*")): if info[0] & win32file.FILE_ATTRIBUTE_DIRECTORY and info[-2] not in [".", ".."]: return True except pywintypes.error: # access denied pass return False

Characterizing People as Non-Linear, First-Order Components in Software Development

Alistair Cockburn has written a lot of very interesting articles but I have to agree with John Carter on Lambda the Ultimate when he called this one his "absolute favourite paper in all the CS literature".

icfp contest date announced

It's clear what I'll be doing the weekend of July 21–24. The annual ICFP programming contest is the programming contest. This year I have to enter. Even if my solution doesn't run.

scite & bicycle repair man

SciTE has been my favorite editor for a long time now. Especially for Python code. But there are two things I really miss: refactoring capabilities and a graphical code overview.

A few years ago I integrated refactoring using Bicycle Repair Man. That code has been lost but yesterday I decided to quickly rewrite it. It won't work with files using tabs for indentation (fixed with hack) due to an irritating bug in SciTE (which still hasn't been fixed since I filed it in 2003, unfortunately). Comments and suggestions are welcome!

Download it here: http://bitbucket.org/janto/snippets/src/tip/scitebike.py
See the file for installation instructions.

Now about that graphical code overview...

motion capture in python

You know those suits with the ping-pong balls attached to it? The kind they use in motion capture? I thought it would be really cool if I could build my own. Then I'd be able to film my kickboxing and analyze it afterwards.

The current state-of-the-art seems to be tracking a magnetic field with the sensors on the suit. Unfortunately I don't have the resources to do that. So I'm going with the older way: visually tracking the markers.

I capture frames using my cheap webcam and the VideoCapture Python library. Others have used it for simple motion detection but not motion tracking. I decided to track the motion of red objects. Why red? Well, it's one of the least common colours in my office and is usually concentrated to a small area (bottle caps, mugs, books).

To get my hands on the red pixels I can't simply extract the R from RGB images. If a colour has a red component it could also be white, yellow, magenta... So you take the R and subtract the G and B. Ignoring values below zero you now have a gauge for the "redness" of a pixel.

(Extra points: Correct me if I'm wrong, but I believe "R minus G minus B" will give you a "redness" plane that intersects the xy chromaticity diagram (see sRGB color space) as a line running from blue to green along the edge of the sRGB gamut. The triangular plane segment within the gamut reaches it's "peak" at the maximum red representable by sRGB.)

This is a simple way to find the maximum red point on the image. I drew a crosshair over that point for clarity. With the series of images captured by the webcam I constructed an animated gif. So the system tracks a red object. Cool.

However, what I want to do is track more than one red object. I did this by forming clusters of red dots above certain intensity.

How do you form clusters? Well I used the K-means algorithm, conveniently included with SciPy. Et viola! It seems to do a pretty good job of it.

Not bad for a days work. Only 150 lines of Python. Of course it is at this point that my fear is confirmed: My webcam doesn't seem up to the task of tracking the speed of my movements. So before I jump around with a bunch of red markers on my body, I'll need a better camera.

Edit: You can download a rough version of the code here: motion_capture.zip. Parts are commented out so you don't need a webcam. You will need Python, SciPy and PIL however. I hope this works...

Another Edit: Here's an alternative I wrote (vr_tracker2.zip) that uses numarray, Pycluster and PIL instead. I'm starting to dislike SciPy. If there are enough requests I think I'll have to do another write-up.