Saturday, September 26, 2009

Distributed computing in Lisp. Again :)

Half year ago I've started a library for distributed computing. Yes, I know, there are many of them, but I wanted to write one more, just to have experience in that area.

Library (called cl-cluster) uses SSH to get a remote shell, run some lisp and execute given code directly in it. SSH was chosen, because I didn't want to write some kind of tcp server/client. Also I didn't want to write fault tolerant remote objects broker with migration between hosts, etc, so transport level may be really simple.

Besides not very interesting stuff like making connection, sending and receiving data, there were a few moments:

One problem was how to prevent remote lisp from falling to debugger. There are 2 possibilities to trap: parse errors and execution errors. Later problem is relatively simple, I just need to wrap main request's body in (handler-case ...). Parse errors are different, they trigger before handler-case will be able to catch them. The best solution I found was to pass body as string and parsing it on remote side using read-from-string and eval it. Thus, making toplevel input form errors free and fully controlled by the library. Of course, handler-case and read-from-string ate some speed, but it's not important for my proof of concept :)

Another problem is: not all lisp objects can be read back from their printed representation. Especially, I faced to problem of parsing remote exceptions on local side. I've ended up returning exceptions in the form of list with symbol "error" as first argument and error description as second. This is very unlikely that regular user-provided code will produce such result. On local side I rise exception with received description, noticing the node where this exception has really happened. In practice, it looks good.

One more trap was spotted with passing packages names to remote: format specifier ~a just cuts package designators, producing (oos 'load-op :asdf) instead of (asdf:oos 'asdf:load-op :asdf). This is not so tricky for experienced lisper, but I've spent some time understanding what's going on and then switched format to ~s.

At the end I wanted to have a let-like macro for parallel execution of bindings on remote machines, gathering results, and passing preprocessed bindings them to another machine. For example:

;; calculate some stuff on remote lisps and aggregate answers on another remote
(rplet node3
       ((a (with-remote node1
                        (+ 1 2)))
        (b (with-remote node2
                        (sqrt 7d0))))
      (* a b))

A and B will be computed in parallel on nodes node1 and node2 respectively, after that node3 will get request:

(let ((a someval)
      (b anotherval))
  (* a b))

For parallel tasks dispatching I've used the cl-pmap library, written by my friend Alexey Voznyuk a.k.a Swizard. It's not the best solution, because it uses thread per task, whereas I was needed simple i/o muxer to write data to several output streams and read results back from input. It'd be a good idea to use iolib instead.

Recently I've tried to make the library portable across different popular Lisps, but, seems, there's no existing wrapper for asynchronous shell execution, allowing to communicate with it via streams. The most closest library, trivial-shell, hasn't this possibility. Quick overview of trivial-shell sources told me, there will be problems to do such thing on some implementation due to bugs or whatever else.

The last idea is to get rid of SSH and use Zero MQ for transport :) Real life application will help to do good zmq bindings, and also zmq's subscriber model can help to cl-cluster with common changes propagation across all slave nodes. Not telling, zmq can use advanced networking techniques and save some microseconds ;)

As usually, sources are hosted at repo.or.cz: http://repo.or.cz/w/cl-cluster.git

Friday, September 18, 2009

Zero MQ + Lisp

Last year I got interested in AMQP.

The most advanced implementation was/is Qpid, because it's a flagship product of such famous companies like JPMorgan, Goldman Sachs, Cisco, RedHat and many others. That means the standard was bloated a lot, you can see it, for example, by looking at specs 0-9 and 0-10: first is relatively simple, later is not. I'm afraid, it will ends up like Corba did. Unfortunately, RedHat and other guys are not interested in Lisp, but I thought it might be useful to have such library in Lisp, so thick and rich customers can use "official AI language" in their projects, and Lisp can benefits from it.

After a two weeks of dancing around Lisp client implementation, I gave up. It was too huge work for me, beginner... A year later I've returned back to that theme and found ready to use Qpid client, fully implemented in Python. Python is closer to Lisp, I thought, so it's possible to use Python codes as a guideline. Heh... Sources are more than 350k in tarball, and it's only a client... It's easy to imagine, how much time will it sweep away from my life doing the same way in Lisp. A lot of complicated code to write, a lot of bugs to fix. No, I didn't really want it. I've decided to wrap Lisp calls, minimally required by standard, into Qpidc calls via CFFI. However, Qpidc is written in scary C++ with a lot of Boost (scary for bindings), so it required me to to write a wrapper for calling C++ from C first.

Next idea, which came to my head due to laziness, is to google if there're any good AMQP realizations with ready to use bindings in C. It can be less powerful and less bleeding edge, but I just needed simple, convenient messaging. I found ØMQ.

Zero MQ is not AMQP messaging library, but can use AMQP as an underlying wire-level transport. Feature list said it also has support of OFED, like Qpidc has. But the most impression I got by looking at API. It darn pretty simple! And it is even more simpler in version 2.0, which is in alpha stage at the moment. It is so simple, that I was able to CFFI'ize the only required zmq.h in one hour, and it worked for me. Impressing!

Latency measurement using server and client both written in Lisp showed me quite good results:

message size: 1024 [B]
roundtrip count: 1000
average latency: 48.7915 [us]


It's even slightly better than in C (with asserts commented out) :)

Current bindings are in the early stage and have ugly CFFI interface, but I'm gonna make it a bit nicer and easy to use.

Sources are here: http://repo.or.cz/w/cl-zmq.git

Thursday, September 17, 2009

Eyes region tracking in Common Lisp

I was going to implement eyes region recognition in Lisp, but seems I'm loosing interest in that area. So I've decided to publish what I already has and forget about it.

I've used CL-V4L2 to capture images from two USB cameras and CL-GTK2 with GtkGlExt extension for rasterization. The main idea of how to detect eyes region was taken from [1]. I can also mention [2] and [3].

The basic idea is to apply edge detection filter to gray scale image, this will stress regions with lots of details. More details, more edges, more visibility in filtered image. Region around eyes has a lot of details, btw. Next step is to compute vertical and horizontal derivatives of edges and find extremums at each axises. Ideally, this will give us one horizontal extremum at eye's level and two vertical extremums at the head borders. Or, if a very strong median filter was used, it may give you one vertical extremum near the center of the face.

However, I didn't succeeded in finding of good filter. First filter I've used was Sobel's operator [4]. Basically it works well for edges detection, but... Too much well for my task... It also finds edges in background parts, like shelf,  window, wall corner, etc. All this edges were false positives for my purpose. I've started to play with different similar filters, like Scharr's operator, Robert's cross [5] and also my own modifications of Sobel. The intention was to stress horizontal derivatives of edges during energy computation at X axis and, contrary, vertical derivatives at Y axis. I found Sobel/Scharr filter works better if G (gradient magnitude) was computed separately for X and Y energies the way described below:

Here's matrix for Sobel:



and for Scharr:



I've combined Gx from Scharr and Gy from Sobel to compute G for X energies and Gx/Sobel, Gy/Scharr for Y energies.

So, filters output was slightly improved, but still not enough to reduce unneeded edges. Much better result was brought by simplest Robert's cross. It doesn't filter edges well, but edges itselves are not what we definitely want. We want to stress eyes region, and Robert's cross does it better than Sobel or Scharr. However, image processing became more sensitive to background light. The only good time during the day was at evening when artificial daylight lamps were turned on. Noise reduction filters (a bunch of different modifications of Gaussian filter) didn't help at any degree. Finally, all smart computational logic was swept away leaving plain Robert's cross alone, which gave me the best result. Most of problems were caused by my beard and mustache, but I'm not gonna sacrifice my True Siberian Beard(tm) for the glory of science :)

In my best attempt, I got this:



I really enjoyed to play with it in Lisp, because Lisp gives you very powerful constructions like LOOP macro, which, for example, allows you to implement digital filter very quickly with only small amount of syntactical garbage. I can't forget to mention about automatic memory management, it saved me a ton of time. Nevertheless, with all these high-level whistles and bells, my non-optimized program still worked quite fast. I'm happy.

Source is available here: http://paste.lisp.org/display/87221

1. http://journal.info.unlp.edu.ar/Journal/journal15/papers/JCST-Oct05-3.pdf
2. http://www.montegen.com/Montegen/Nature_of_Business/The_Library/The_Pocket-Science/The_Pocket-Science_Vol__4/Security___Intrusion_2000/Eye_location.pdf
3. http://www.ecse.rpi.edu/~qji/Papers/frgc_eye.pdf
4. http://en.wikipedia.org/wiki/Sobel_operator
5. http://en.wikipedia.org/wiki/Roberts_Cross