![[info]](http://l-stat.livejournal.com/img/userinfo.gif){kind=small}
I want a pair of rollerblades that, using simple technology (no GPS), can fairly accurately report to me how far I've traveled. I want an odometer readout that I can reset before each trip. How can this be accomplished?
Add rotary encoders to the front and back wheels on the skate. We want the frictionless optical tachometer type; the direction of motion is irrelevant (picture someone skating backwards, for example). We can obtain a fairly accurate measure of the distance traveled by the skate by always recording the angular displacement of the faster-turning wheel. This can be accomplished by having each encoder increment its own small counter (say, a 4-bit one). When one of the counters overflows, it sends a signal to a large main counter and clears both small counters. The large counter is enabled by a pressure switch (maybe a piezoelectric sensor with a threshold for binary output) able to determine that the skate is in fact contacting the ground. At this point, assuming we've been intelligent about the encoder pitch relative to the wheel size, and done the appropriate trickery in the counting logic, we have a skate that can accurately measure its own ground distance traveled in some useful unit.
The major issue now is that both skates are sometimes, but not always, contacting the ground, and there is no way to know a posteriori, when observing the results, how much overlap to subtract. I don't want to introduce any concept of time into this design, so what we need is some way for one of the skates to know whether the other is contacting the ground. We can accomplish this by having the pressure switch on the left skate enable an RF transmitter, with a simple structured signal that a receiver on the right skate can robustly identify. The receiver can then disable the counter on the right skate while the left skate is transmitting. Now, totalling the large counters in both skates should yield a fairly accurate total ground distance traveled.
However, as a human being, I can't tell what is in those counters, and even if I could, I wouldn't want to have to add them up in my head. We can add a button to the left skate that triggers a different RF transmission to the right which encodes its counter value and then resets it. The receipt of this signal on the right skate prompts it to add the value to its counter register and show the value on an LED display for a few seconds. This can be done repeatedly, since the left skate is just dumping its current counter value into the right skate each time, where the total is retained. The corresponding button on the right skate would simply reset its counter.
Some issues for further consideration:
Add rotary encoders to the front and back wheels on the skate. We want the frictionless optical tachometer type; the direction of motion is irrelevant (picture someone skating backwards, for example). We can obtain a fairly accurate measure of the distance traveled by the skate by always recording the angular displacement of the faster-turning wheel. This can be accomplished by having each encoder increment its own small counter (say, a 4-bit one). When one of the counters overflows, it sends a signal to a large main counter and clears both small counters. The large counter is enabled by a pressure switch (maybe a piezoelectric sensor with a threshold for binary output) able to determine that the skate is in fact contacting the ground. At this point, assuming we've been intelligent about the encoder pitch relative to the wheel size, and done the appropriate trickery in the counting logic, we have a skate that can accurately measure its own ground distance traveled in some useful unit.
The major issue now is that both skates are sometimes, but not always, contacting the ground, and there is no way to know a posteriori, when observing the results, how much overlap to subtract. I don't want to introduce any concept of time into this design, so what we need is some way for one of the skates to know whether the other is contacting the ground. We can accomplish this by having the pressure switch on the left skate enable an RF transmitter, with a simple structured signal that a receiver on the right skate can robustly identify. The receiver can then disable the counter on the right skate while the left skate is transmitting. Now, totalling the large counters in both skates should yield a fairly accurate total ground distance traveled.
However, as a human being, I can't tell what is in those counters, and even if I could, I wouldn't want to have to add them up in my head. We can add a button to the left skate that triggers a different RF transmission to the right which encodes its counter value and then resets it. The receipt of this signal on the right skate prompts it to add the value to its counter register and show the value on an LED display for a few seconds. This can be done repeatedly, since the left skate is just dumping its current counter value into the right skate each time, where the total is retained. The corresponding button on the right skate would simply reset its counter.
Some issues for further consideration:
- Since the transmissions are one-way, the signal needs to be robust. We also assume that the rollerblades are both powered and in proximity to one another.
- Power management. Should the skates power off after a period, and power on via the pressure switch? We likely want the main counter registers to be non-volatile.
- Pressing a button on the left skate to activate a display on the right skate seems somewhat awkward from a user perspective.
Like Xavier, I came back from Penguicon 7.0 this weekend to a mountain of work. Now I'm going to walk and talk like him (minus the epic growl) -- guess that means I look like someone else here -- and give my review.
The highlight was certainly the party. Friday night was phenomenal, Saturday night even more so. Where else can you be waylaid by a pirate ship at the top of the hotel lobby stairs, and told to drink rum and walk the plank to join the crew? Best Penguicon yet, on this basis. You have to be there to know.
The panels were good this year too, as usual. We could have attended a few more if it hadn't been for a certain WTF line. Here are my thoughts on the ones I did catch:
Sustainable Computing (Jon "maddog" Hall)
A great forward-looking keynote by maddog. He deftly connected the idea of scalable distributed mesh networking for cities with providing free Internet access to kids (a la OLPC, but with fewer technical challenges), with benefits to everyone else too, and with environmental sustainability. And, naturally, he gave some highly compelling arguments as to why the sensible thing to do is use free software to implement it. A
Wil Wheaton Reading (Wil Wheaton)
Ensign Crusher, report to Penguicon. Ensign Crusher? Ensign Crusher, respond! F
Open Hardware Overview (W. Craig Trader)
A brief introduction to "open source" hardware. A big chunk of the talk was devoted to a few examples, which was surely a yawn-fest for anyone who reads hardware hacking feeds. The more interesting parts of the talk were the breakdown of the board prototyping process and the explanation of how projects apply licenses like Creative Commons to hardware design. A bit pedestrian, but not bad. B
Beginning Pygame Programming (Craig Maloney)
To be fair, I was very much looking forward to this one, so it had a lot to live up to. The talk consisted entirely of showing various stages of development of a Pong game demo. Much time was spent figuring out which revisions would actually run (blind commits are evil). A reasonable amount of Pygame functionality was used, but there could have been more explanation. Good concept, but tighter implementation necessary. C
Open Hardware with Arduino (W. Craig Trader)
This talk really made me wonder why Trader spent so much time talking about the Arduino platform in his previous talk. My main complaint is that he didn't really contrast the advantages of the Arduino against other microcontrollers and evaluation boards, which probably left most people with a somewhat distorted perception. More original content, such as some clever uses and maybe a non-trivial demo, would have been nice as well. There was lots of good information about existing projects and add-on devices. I'll give it a pass because it got the others interested. C
Rule-Based Programming in Interactive Fiction (Andrew Plotkin)
As an engineering grad student, I'm quite used to dry technical seminars, but I want Penguicon to entertain me more. That aside, awesome talk! I hadn't really thought about how awkward it must be to program IF in an object-oriented programming language until this talk. Very interesting concept about how to attack the problem with a rule-based syntax model. Some of it brought to mind aspect-oriented programming. Bonus: Andrew really likes to talk about heads exploding. B
Looking forward to Penguicon 8.0! I'm hoping to get my Thousand Parsec talk in this time.
The highlight was certainly the party. Friday night was phenomenal, Saturday night even more so. Where else can you be waylaid by a pirate ship at the top of the hotel lobby stairs, and told to drink rum and walk the plank to join the crew? Best Penguicon yet, on this basis. You have to be there to know.
The panels were good this year too, as usual. We could have attended a few more if it hadn't been for a certain WTF line. Here are my thoughts on the ones I did catch:
Sustainable Computing (Jon "maddog" Hall)
A great forward-looking keynote by maddog. He deftly connected the idea of scalable distributed mesh networking for cities with providing free Internet access to kids (a la OLPC, but with fewer technical challenges), with benefits to everyone else too, and with environmental sustainability. And, naturally, he gave some highly compelling arguments as to why the sensible thing to do is use free software to implement it. A
Wil Wheaton Reading (Wil Wheaton)
Ensign Crusher, report to Penguicon. Ensign Crusher? Ensign Crusher, respond! F
Open Hardware Overview (W. Craig Trader)
A brief introduction to "open source" hardware. A big chunk of the talk was devoted to a few examples, which was surely a yawn-fest for anyone who reads hardware hacking feeds. The more interesting parts of the talk were the breakdown of the board prototyping process and the explanation of how projects apply licenses like Creative Commons to hardware design. A bit pedestrian, but not bad. B
Beginning Pygame Programming (Craig Maloney)
To be fair, I was very much looking forward to this one, so it had a lot to live up to. The talk consisted entirely of showing various stages of development of a Pong game demo. Much time was spent figuring out which revisions would actually run (blind commits are evil). A reasonable amount of Pygame functionality was used, but there could have been more explanation. Good concept, but tighter implementation necessary. C
Open Hardware with Arduino (W. Craig Trader)
This talk really made me wonder why Trader spent so much time talking about the Arduino platform in his previous talk. My main complaint is that he didn't really contrast the advantages of the Arduino against other microcontrollers and evaluation boards, which probably left most people with a somewhat distorted perception. More original content, such as some clever uses and maybe a non-trivial demo, would have been nice as well. There was lots of good information about existing projects and add-on devices. I'll give it a pass because it got the others interested. C
Rule-Based Programming in Interactive Fiction (Andrew Plotkin)
As an engineering grad student, I'm quite used to dry technical seminars, but I want Penguicon to entertain me more. That aside, awesome talk! I hadn't really thought about how awkward it must be to program IF in an object-oriented programming language until this talk. Very interesting concept about how to attack the problem with a rule-based syntax model. Some of it brought to mind aspect-oriented programming. Bonus: Andrew really likes to talk about heads exploding. B
Looking forward to Penguicon 8.0! I'm hoping to get my Thousand Parsec talk in this time.
A Python function that returns a random subset of size
I'm dealing with fairly small sets, so this may not be the most computationally efficient way to do it.
n from set s.from random import randint
def random_subset( s, n ):
if len( s ) < n:
raise ValueError, ( "Subset larger than input set" )
l = list( s )
r = set()
for i in range( n ):
r.add( l.pop( randint( 0, len( s ) - i - 1 ) ) )
return rI'm dealing with fairly small sets, so this may not be the most computationally efficient way to do it.
A good friend of mine recently tossed me some computer parts, including an HP illuminated multimedia USB keyboard (model SK-2565, part no. 5185-2027). Since I had been looking to replace my old keyboard (a $10 PS/2 job that I turned into a k-rad all-black cowboy deck with blank keys), and had been suffering from an inability to control my PCM volume or music from the keyboard without launching alsamixer or mocp respectively, a particularly acute problem when playing StarCraft, I found herein an opportunity.
This keyboard has nineteen buttons and one knob across the top. In order, they are (or look like) sleep, help, HP, printer, camera, shopping, sports, finance, web (connect), search, chat, e-mail, the five standard audio buttons (stop, previous, play/pause, next, load), a volume knob, mute, and music. Since the keyboard was furry enough to qualify as a mammal upon receipt, the first thing I did was clean it, a process which spanned several hours (though the process was niced down somewhat). The previous two sentences are related: the top buttons also happen to be built in such a way as to require utterly complete disassembly of the keyboard to remove and replace, and I am ashamed but not at all surprised to say I got the replacing part wrong. The play/pause button is now swapped with the previous button. And I am totally not taking this thing apart again any time soon.
But it is for the best! After figuring out sometime later that I had goofed, I decided (Daniel Gilbert, this one's for you) that I liked it better this way anyway. Which is perfectly fine, of course, since I'm about to get to the good part: how I made my HP illuminated multimedia USB keyboard special upper buttons work in Linux, using Xmodmap, and in awesome, using rc.lua.
Turns out it's extremely easy to bind arbitrary keycodes to keysyms (a full list of which can be found in
And now, the answers to all your questions:
The next step was to make these keys actually do something in my window manager. Bindings are pretty easy to make in
A particularly nice one is the search button, which runs the following script (be nice, my bash-fu is rusty):
I frequently say that if I took one thing home from working in the automotive sector, it was Kaizen.
This keyboard has nineteen buttons and one knob across the top. In order, they are (or look like) sleep, help, HP, printer, camera, shopping, sports, finance, web (connect), search, chat, e-mail, the five standard audio buttons (stop, previous, play/pause, next, load), a volume knob, mute, and music. Since the keyboard was furry enough to qualify as a mammal upon receipt, the first thing I did was clean it, a process which spanned several hours (though the process was niced down somewhat). The previous two sentences are related: the top buttons also happen to be built in such a way as to require utterly complete disassembly of the keyboard to remove and replace, and I am ashamed but not at all surprised to say I got the replacing part wrong. The play/pause button is now swapped with the previous button. And I am totally not taking this thing apart again any time soon.
But it is for the best! After figuring out sometime later that I had goofed, I decided (Daniel Gilbert, this one's for you) that I liked it better this way anyway. Which is perfectly fine, of course, since I'm about to get to the good part: how I made my HP illuminated multimedia USB keyboard special upper buttons work in Linux, using Xmodmap, and in awesome, using rc.lua.
Turns out it's extremely easy to bind arbitrary keycodes to keysyms (a full list of which can be found in
/usr/share/X11/XKeysymDB), at least using GDM. By default (on Gentoo), GDM loads /etc/X11/Xmodmap, as specified by the sysmodmap setting in /etc/X11/gdm/Init/Default. Mine now looks like this:keycode 223 = XF86Sleep
keycode 197 = XF86Shop
keycode 196 = XF86LightBulb
keycode 195 = XF86Finance
keycode 194 = XF86WWW
keycode 229 = XF86Search
keycode 121 = XF86Community
keycode 120 = XF86Mail
keycode 144 = XF86AudioPlay
keycode 164 = XF86AudioStop
keycode 160 = XF86AudioMute
keycode 162 = XF86AudioPrev
keycode 153 = XF86AudioNext
keycode 176 = XF86AudioRaiseVolume
keycode 174 = XF86AudioLowerVolume
keycode 118 = XF86MusicAnd now, the answers to all your questions:
- I figured the keycodes out by running
xevand banging on the buttons. - XF86LightBulb is the closest thing I could find to "sports" that wasn't already taken.
- The volume knob "clicks" and sends a keycode 176 or 174 depending on the turn direction.
- I did not map help, HP, printer, or camera because they do not appear to generate keycodes.
- I did not map audio load because I forgot. I will do it when I can think of an action to bind it to.
The next step was to make these keys actually do something in my window manager. Bindings are pretty easy to make in
/etc/xdg/awesome/rc.lua. Without getting into too much detail, I bound keys to things. I am particularly impressed with how I can control audio via amixer, and my MOC playlist via commands without even having the interface open. Another bonus is the sleep button running xlock. Here's a sample line:key({ }, "XF86LightBulb", function () awful.util.spawn("starcraft") end),A particularly nice one is the search button, which runs the following script (be nice, my bash-fu is rusty):
#!/bin/bash
Q=`zenity --entry --width 600 --title="Google Search" --text="Google search query:"`
if [[ "$Q" != "" ]]; then
EQ=`echo $Q | sed s/\ /\%20/g`
firefox http://www.google.ca/search?q=$EQ
fiI frequently say that if I took one thing home from working in the automotive sector, it was Kaizen.
My research area at school is distributed smart cameras, a field which is primarily rooted in computer vision. Despite having access to a range of expensive proprietary software libraries by virtue of having purchased the equipment, most of my computer vision work uses a stack of free software running on Gentoo Linux.
For interfacing to the cameras themselves, we have the excellent libdc1394, a high-level API for interfacing with IEEE 1394 cameras supporting the IIDC specification (which our Prosilica EC1350s, among hundreds of others, do). The Coriander GUI makes configuration and control a snap. The ebuilds available in Portage have so far worked flawlessly for me.
Many computer vision tasks are covered by OpenCV, a former Intel project that is gaining a lot of momentum with academic open source developers worldwide. When I first considered it in early 2006, it had a long way to go in terms of maturity. However, after seeing Gary Bradski's talk at ICDSC 2008, I decided to give it another look, and was pleasantly surprised to find out that O'Reilly had just published Learning OpenCV (co-authored by Bradski), and that it was an excellent practical introduction to the library. The latest stable release for Linux at the time of writing, 1.1pre1, shows signs that this library is becoming quite robust. It seems to finally be moving from a simple collection of algorithms toward a fully functional general-purpose computer vision library. The feature list for the June 2009 release has me excited, particularly because of the better Python interface and some big improvements in feature detection and 3D stuff.
Computer vision and related algorithms tend to use a lot of linear algebra, and depending on whether I'm coding in C or in Python, I use the GNU Scientific Library or NumPy, respectively. Both are excellent numerical libraries. I used NumPy fairly extensively in developing PyDSSCC for my Master's thesis.
My personal Gentoo overlay has ebuilds for both OpenCV (which tends to lag the release version in the official tree) and Gandalf (which is not in the official tree).
For interfacing to the cameras themselves, we have the excellent libdc1394, a high-level API for interfacing with IEEE 1394 cameras supporting the IIDC specification (which our Prosilica EC1350s, among hundreds of others, do). The Coriander GUI makes configuration and control a snap. The ebuilds available in Portage have so far worked flawlessly for me.
Many computer vision tasks are covered by OpenCV, a former Intel project that is gaining a lot of momentum with academic open source developers worldwide. When I first considered it in early 2006, it had a long way to go in terms of maturity. However, after seeing Gary Bradski's talk at ICDSC 2008, I decided to give it another look, and was pleasantly surprised to find out that O'Reilly had just published Learning OpenCV (co-authored by Bradski), and that it was an excellent practical introduction to the library. The latest stable release for Linux at the time of writing, 1.1pre1, shows signs that this library is becoming quite robust. It seems to finally be moving from a simple collection of algorithms toward a fully functional general-purpose computer vision library. The feature list for the June 2009 release has me excited, particularly because of the better Python interface and some big improvements in feature detection and 3D stuff.
Computer vision and related algorithms tend to use a lot of linear algebra, and depending on whether I'm coding in C or in Python, I use the GNU Scientific Library or NumPy, respectively. Both are excellent numerical libraries. I used NumPy fairly extensively in developing PyDSSCC for my Master's thesis.
My personal Gentoo overlay has ebuilds for both OpenCV (which tends to lag the release version in the official tree) and Gandalf (which is not in the official tree).
Crystal bought me this USB Drum Kit for my birthday back in November. If you followed the link, you may have noticed this: Includes custom software (Windows only).
Naturally, I want this thing to be sitting on my desk, ready to crank out a beat at all times. And naturally, the computer that's sitting on said desk is not running Windows. The great thing about this present is that it's given me a cool new side project to work on.
The first thing I did was determine that it is a pretty standard HID. It chucks out 8 identical bytes in its report. Looking at one byte, the 6 low-order bits each represent one pad on the drum kit, with a 1 indicating that the pad is being pressed.
My simple test program pipes
Just to see it in action, I added a fork and
The next step is to get this working with libhid. I ran
Once input is coming in properly, I'm planning to look into a better way to play the sounds (pre-mixed, so that only one hardware channel is needed), and I may also write a simple GUI that lets you assign samples to each pad easily.
Naturally, I want this thing to be sitting on my desk, ready to crank out a beat at all times. And naturally, the computer that's sitting on said desk is not running Windows. The great thing about this present is that it's given me a cool new side project to work on.
The first thing I did was determine that it is a pretty standard HID. It chucks out 8 identical bytes in its report. Looking at one byte, the 6 low-order bits each represent one pad on the drum kit, with a 1 indicating that the pad is being pressed.
My simple test program pipes
/dev/hidrawX as stdin and reads it to buf in a loop. The following logic compares the current state to the previous state, and if a new pad is being pressed, it sets pad to the integer value from the image above:dtot = buf[ 0 ];
raw = ( dtot ^ dtol ) & dtot;
dtol = dtot;
pad = 0;
while( raw )
{
pad++;
raw >>= 1;
}Just to see it in action, I added a fork and
execl call to the loop that plays a different wave file for each pad through aplay. Among other things, this is a poor solution because fast drumming or long wave files will quickly fill up the available channels on the sound card, so that sometimes the sounds don't play at all.The next step is to get this working with libhid. I ran
lsusb -d 1941:8021 -vvv to get the details about the input and output paths, but I haven't had any success getting an input report thus far (apparently, I'm reading the path wrong somehow, will ask the libhid mailing list).Once input is coming in properly, I'm planning to look into a better way to play the sounds (pre-mixed, so that only one hardware channel is needed), and I may also write a simple GUI that lets you assign samples to each pad easily.
I play a lot of StarCraft. Here's how I do it on my Linux box.
Installing Wine
First, I install and configure Wine. In particular, I leave the virtual desktop option off, and ensure that a sound driver (in my case, ALSA) is configured.
ISO Images
Both CDs are required for installation and play (assuming one wants to play all the campaigns), so I dump ISO images of them to my filesystem somewhere:
I also have these images in my
I mount them at boot; this can be disabled via the
These mountpoints should be symlinked in
Installing StarCraft
Now, I install StarCraft, Brood War, and the latest patch through Wine.
Since I have several user accounts on my machine, I create a symlink in
At this point, the game should just work. See the AppDB entry for more information about running StarCraft through Wine.
Run Script
Finally, I create a script in my path to run the game:
A nice side effect is that in awesome, I can hit [modkey]+F1 and type
Installing Wine
First, I install and configure Wine. In particular, I leave the virtual desktop option off, and ensure that a sound driver (in my case, ALSA) is configured.
ISO Images
Both CDs are required for installation and play (assuming one wants to play all the campaigns), so I dump ISO images of them to my filesystem somewhere:
dd if=/dev/cdrom of=/mnt/share/wine/starcraft.iso bs=2048dd if=/dev/cdrom of=/mnt/share/wine/broodwar.iso bs=2048I also have these images in my
/etc/fstab:/mnt/share/wine/starcraft.iso /mnt/starcraft iso9660 ro,loop 0 0
/mnt/share/wine/broodwar.iso /mnt/broodwar iso9660 ro,loop 0 0I mount them at boot; this can be disabled via the
noauto option.These mountpoints should be symlinked in
~/.wine/dosdevices, each as their own device, so that the executable finds them when it looks.Installing StarCraft
Now, I install StarCraft, Brood War, and the latest patch through Wine.
Since I have several user accounts on my machine, I create a symlink in
~/.wine/dosdevices to a directory with group read-write permissions for all local (human) users, and install it there. That way, only one copy is necessary, and maps, replays, profiles, etc. all live in the same place.At this point, the game should just work. See the AppDB entry for more information about running StarCraft through Wine.
Run Script
Finally, I create a script in my path to run the game:
#!/bin/bash
wine /mnt/share/wine/Starcraft/StarCraft.exeA nice side effect is that in awesome, I can hit [modkey]+F1 and type
starcraft all with my left hand. I've gotten pretty quick at it too...While testing the Thousand Parsec single player mode on Gentoo the other day, I came across something strange. The wxPython client, when run from a Git working directory, wants to use development versions of libtpproto-py and libtpclient-py. It does this by prepending
On the bright side, single player mode seems to work well for Linux! The wizard GUI needs vast improvement, but it's functional. As soon as we merge the singleplayer branches of tpclient-pywx and libtpclient-py, we can release a package, and Gentoo will have ebuilds for everything you need to play single player Risk and RFTS. Before we see this, I am probably going to have to get daneel-ai running on Windows so we can test it there before release. We're also going to need packaging for a number of modules on other Linux distributions.
I'm working on stepping up my Python game in general, checking out Expert Python Programming and O'Reilly's Python for Unix and Linux System Administration. A thousand other people have said it better than I, but this is what software development ought to be.
'.' to sys.path. For some reason, though, import tp.* was still finding the site-packages versions first, which I had installed from my own overlay ebuild. It turns out that setuptools and Portage conspired to install -nspkg.pth files containing Python code that somehow put the site-packages path for the tp module ahead of everything else in sys.path. It seems doing this at all is an undocumented feature, and the current site module docs don't mention it. My evil temporary fix (in the ebuilds) is to simply delete those files and touch an __init.py__ in the tp directory. It seems to work, but I still plan to investigate the cause (maybe the fact that there are multiple libraries sharing a namespace?) and come up with a less hackish fix if possible.On the bright side, single player mode seems to work well for Linux! The wizard GUI needs vast improvement, but it's functional. As soon as we merge the singleplayer branches of tpclient-pywx and libtpclient-py, we can release a package, and Gentoo will have ebuilds for everything you need to play single player Risk and RFTS. Before we see this, I am probably going to have to get daneel-ai running on Windows so we can test it there before release. We're also going to need packaging for a number of modules on other Linux distributions.
I'm working on stepping up my Python game in general, checking out Expert Python Programming and O'Reilly's Python for Unix and Linux System Administration. A thousand other people have said it better than I, but this is what software development ought to be.
Thousand Parsec single player mode is almost ready! The initial goal is to release tpclient-pywx with single player mode, along with at least one server and one AI client supporting two rulesets, on Windows and Gentoo Linux. We achieved a few of the final steps last month.
First, we have the release of tpserver-cpp 0.6.0. This release includes the new Risk ruleset as well as the administration protocol, both Google Summer of Code 2008 projects. The Gentoo ebuild for tpserver-cpp now pulls in the recently-released tpadmin-cpp. We're currently working on a Windows package for the server.
Next, we have a preliminary release of daneel-ai, also a GSoC project, which implements an AI client for the Risk and RFTS rulesets in pure Python. The Gentoo ebuild installs a script in the path and the XML file necessary for single player mode, so on that platform we're good to go. We plan to have a more solid release and a package for Windows soon.
First, we have the release of tpserver-cpp 0.6.0. This release includes the new Risk ruleset as well as the administration protocol, both Google Summer of Code 2008 projects. The Gentoo ebuild for tpserver-cpp now pulls in the recently-released tpadmin-cpp. We're currently working on a Windows package for the server.
Next, we have a preliminary release of daneel-ai, also a GSoC project, which implements an AI client for the Risk and RFTS rulesets in pure Python. The Gentoo ebuild installs a script in the path and the XML file necessary for single player mode, so on that platform we're good to go. We plan to have a more solid release and a package for Windows soon.
Things are going well after the first week working with OpenCV. I have no proper complaints about the library, but I still have that uneasy feeling one gets when using something so high-level. It is particularly acute in this case, as computer vision problems are notoriously ill-posed and, having researched many of them heavily, I am apprehensive when the cat-skinning method is chosen for me. I am hopeful it will pass when good results start coming in, and if they don't, well, OpenCV is open, right?
The latest OpenCV ebuild in the official Portage tree is version 1.0.0, which appeared to be missing a lot of the functionality I was after (notably, stereo vision routines). In order to get things working quickly yet cleanly, I scrapped the patches and updated the ebuild to 1.1.0-pre1, which is in my overlay. When I get a chance to prod it a little more thoroughly I'll contact the maintainer about getting the update out.
As of right now, I have implemented a total of four utilities in my stereotools project. The first is a stereo calibration program and library that performs Bouguet's method automatically from a series of saved images, and provides a data structure and file I/O for the results. The second is a fast disparity/depth map generator, which seems to work but hasn't really been tested yet. The third is a 3D interest point detection utility that will provide the point sets for my 3D distributed smart camera calibration method; this one is still in the works, as I find myself implementing my own sparse ZNCC feature matching (once again) due to a conspicuous lack thereof in OpenCV. The fourth and latest, currently in the works, is a simple image capture utility that shows live feeds from both cameras and snaps images when a key is pressed.
The latest OpenCV ebuild in the official Portage tree is version 1.0.0, which appeared to be missing a lot of the functionality I was after (notably, stereo vision routines). In order to get things working quickly yet cleanly, I scrapped the patches and updated the ebuild to 1.1.0-pre1, which is in my overlay. When I get a chance to prod it a little more thoroughly I'll contact the maintainer about getting the update out.
As of right now, I have implemented a total of four utilities in my stereotools project. The first is a stereo calibration program and library that performs Bouguet's method automatically from a series of saved images, and provides a data structure and file I/O for the results. The second is a fast disparity/depth map generator, which seems to work but hasn't really been tested yet. The third is a 3D interest point detection utility that will provide the point sets for my 3D distributed smart camera calibration method; this one is still in the works, as I find myself implementing my own sparse ZNCC feature matching (once again) due to a conspicuous lack thereof in OpenCV. The fourth and latest, currently in the works, is a simple image capture utility that shows live feeds from both cameras and snaps images when a key is pressed.
I've been building on my research lab's computer vision codebase for a couple years now, slowly adding functionality as it's needed to get some experiment or other done. It's built on National Instruments' LabWindows/CVI IDE, along with their image acquisition and low-level CV stuff, so it's strictly Windows-based and the code is basically useless in any other setting. That, combined with the fact that I'm the only student currently using it, has led me to implement the bare minimum of what I need, and it's shamefully sloppy. To boot, due to various issues with Windows and the NI software (which, of course, being proprietary and closed-source, we can do zilch about), it doesn't even work reliably and is riddled with workarounds.
When I received an e-mail from National Instruments encouraging me to upgrade to Version 9 (will that be credit card or purchase order today?) while waiting an agonizingly long time best described as a fraction of an hour for my fifth try at generating a decent disparity map to complete, I decided to give the free software options another look.
I had already been playing around with libdc1394 on my desktop box in the lab, an x86 machine running Gentoo. Also, I had recently attended Gary Bradski's OpenCV workshop at ICDSC 2008. Some poking around yesterday revealed that OpenCV is much more mature now than it was when I originally considered using it back in 2006.
After reading through most of Learning OpenCV from O'Reilly (of which Bradski is a co-author) last night, I realized I could probably replace almost all of my custom code with a few calls to OpenCV routines and some glue. It does practically everything I need for my two current projects: image capture, camera calibration, stereo calibration and geometry, background subtraction, interest point detection, correspondence, disparity map generation. And it does them far more efficiently, in most cases, than my own code. Best of all, the entire chain is now free software and is no longer bound to proprietary products (including the higher-level stuff, like PyDSSCC, which is already open-source and platform-independent).
Today, I wrote a short (about 40 lines, comments and whitespace included) C program that displays streaming video from two of my IEEE-1394 cameras in side-by-side windows. Not only does it actually work, without requiring rebooting or tweaking settings or sacrificing goats to Odin, but the frame rate is higher and it doesn't randomly "forget" to grab a frame every so often.
I am thoroughly impressed so far. The rest of the week will see my try to implement both projects using OpenCV.
When I received an e-mail from National Instruments encouraging me to upgrade to Version 9 (will that be credit card or purchase order today?) while waiting an agonizingly long time best described as a fraction of an hour for my fifth try at generating a decent disparity map to complete, I decided to give the free software options another look.
I had already been playing around with libdc1394 on my desktop box in the lab, an x86 machine running Gentoo. Also, I had recently attended Gary Bradski's OpenCV workshop at ICDSC 2008. Some poking around yesterday revealed that OpenCV is much more mature now than it was when I originally considered using it back in 2006.
After reading through most of Learning OpenCV from O'Reilly (of which Bradski is a co-author) last night, I realized I could probably replace almost all of my custom code with a few calls to OpenCV routines and some glue. It does practically everything I need for my two current projects: image capture, camera calibration, stereo calibration and geometry, background subtraction, interest point detection, correspondence, disparity map generation. And it does them far more efficiently, in most cases, than my own code. Best of all, the entire chain is now free software and is no longer bound to proprietary products (including the higher-level stuff, like PyDSSCC, which is already open-source and platform-independent).
Today, I wrote a short (about 40 lines, comments and whitespace included) C program that displays streaming video from two of my IEEE-1394 cameras in side-by-side windows. Not only does it actually work, without requiring rebooting or tweaking settings or sacrificing goats to Odin, but the frame rate is higher and it doesn't randomly "forget" to grab a frame every so often.
I am thoroughly impressed so far. The rest of the week will see my try to implement both projects using OpenCV.
...the closest book being my dad's copy of Programming Erlang: Software for a Concurrent World by Joe Armstrong:
A guard is a series of guard expressions, separated by commas (,).
Well, that was rather boring.
A guard is a series of guard expressions, separated by commas (,).
Well, that was rather boring.
- Grab the nearest book.
- Open it to page 56.
- Find the fifth sentence.
- Post the text of the sentence in your journal along with these instructions.
- Don't dig for your favorite book, the cool book, or the intellectual one: pick the CLOSEST.
I would love for someone to do this research. Maybe I will. Point me in the direction of anything that looks promising, and I will buy you a beer if it leads to the apprehension of the suspect. This is the most promising I've seen to date, but I e-mailed the guy and he's no longer working on it.
Given: A series of stereo-calibrated smart camera pairs (nodes), fixed at unknown relative locations and orientations, ostensibly observing the same scene. You can either assume the scene is static or that the nodes are in temporal sync so that they all image the same stuff. You can see the original left and right images as well as a dense range image (a.k.a. disparity map), and you know the epipolar geometry (essential matrix, fundamental matrix, whatever you want).
Find: The best way to detect and triangulate sets of interest points, roughly similar in size (say, 20 to 80 points, but better if scalable), at each node such that there is as much overlap as possible between the point sets at each node. Obviously, the differing fields of view and scene occlusions are going to arbitrarily affect performance. The idea is to make point detection repeatable (stable, robust) in 3D, as all current methods I am aware of are at best invariant to 2D image Euclidean or affine transformations. Ideally, from two substantially different 3D views, any points not occluded and within both fields of view which are detected by one node are also be detected by the other.
Bonus: This problem really ought to be tackled from a general perspective which would not necessarily involve smart camera nodes. However, in my case, they are smart camera nodes, and they can talk to each other! If there's a better way that involves sharing information between nodes, feel free to make that assumption.
Given: A series of stereo-calibrated smart camera pairs (nodes), fixed at unknown relative locations and orientations, ostensibly observing the same scene. You can either assume the scene is static or that the nodes are in temporal sync so that they all image the same stuff. You can see the original left and right images as well as a dense range image (a.k.a. disparity map), and you know the epipolar geometry (essential matrix, fundamental matrix, whatever you want).
Find: The best way to detect and triangulate sets of interest points, roughly similar in size (say, 20 to 80 points, but better if scalable), at each node such that there is as much overlap as possible between the point sets at each node. Obviously, the differing fields of view and scene occlusions are going to arbitrarily affect performance. The idea is to make point detection repeatable (stable, robust) in 3D, as all current methods I am aware of are at best invariant to 2D image Euclidean or affine transformations. Ideally, from two substantially different 3D views, any points not occluded and within both fields of view which are detected by one node are also be detected by the other.
Bonus: This problem really ought to be tackled from a general perspective which would not necessarily involve smart camera nodes. However, in my case, they are smart camera nodes, and they can talk to each other! If there's a better way that involves sharing information between nodes, feel free to make that assumption.
I recently cranked out a usable release of PyDSSCC, the Python implementation of my distributed smart stereo camera network calibration scheme. Version 0.3 is a world better than what I tacked onto my M.A.Sc. thesis as an appendix. Notably, it's packaged as a Python module now. Also notably, it now generates the bin ranges for features automatically based on a shared sample of actual points.
No other major updates. Studying for my comprehensive exam at the end of this month. Will be back in full effect when that's over with.
No other major updates. Studying for my comprehensive exam at the end of this month. Will be back in full effect when that's over with.
Here's an interesting problem. Anyone know of a solution to this?
There are 24 wizards in the land of Network. They live spread out far from one another, because if too many of them got too close, the concentration of magical power would create a singularity and destroy the universe. They are all aware of one another's existence, and have a way of communicating one-on-one between any two of them, but because of the distances involved, communicating saps a lot more mana than their normal magic (which they do locally in their towers).
Each wizard wants to learn the new ultimate spell. They find that, in order to learn the spell, they need an unbroken sequence of Celestial Numbers of a certain size. Each of them has collected a set of Celestial Numbers (which are unique, i.e., only one wizard can have the number 33.7). Unfortunately, they are all jumbled up and each wizard has a different number of them, so none of the wizards can learn the spell.
It is decided that the wizards must work together to get each wizard an unbroken sequence of roughly the same size, by distributing their Numbers amongst themselves. The question the wizards are now pondering is how to actually do it.
If they could all get together in the same place and write their Numbers (or at least a sample) on one big piece of parchment, they could determine the distribution, split it up into a 24-quantile, and use the quantile ranges to divide the Numbers into 24 sets of roughly equal size.
So, without getting together, and keeping communication to a minimum, what is the most efficient way for them to determine reasonably accurate quantile ranges to split up the Numbers?
There are 24 wizards in the land of Network. They live spread out far from one another, because if too many of them got too close, the concentration of magical power would create a singularity and destroy the universe. They are all aware of one another's existence, and have a way of communicating one-on-one between any two of them, but because of the distances involved, communicating saps a lot more mana than their normal magic (which they do locally in their towers).
Each wizard wants to learn the new ultimate spell. They find that, in order to learn the spell, they need an unbroken sequence of Celestial Numbers of a certain size. Each of them has collected a set of Celestial Numbers (which are unique, i.e., only one wizard can have the number 33.7). Unfortunately, they are all jumbled up and each wizard has a different number of them, so none of the wizards can learn the spell.
It is decided that the wizards must work together to get each wizard an unbroken sequence of roughly the same size, by distributing their Numbers amongst themselves. The question the wizards are now pondering is how to actually do it.
If they could all get together in the same place and write their Numbers (or at least a sample) on one big piece of parchment, they could determine the distribution, split it up into a 24-quantile, and use the quantile ranges to divide the Numbers into 24 sets of roughly equal size.
So, without getting together, and keeping communication to a minimum, what is the most efficient way for them to determine reasonably accurate quantile ranges to split up the Numbers?
We're planning to release a version of the Thousand Parsec tpclient-pywx client soon with the new single player wizard. Support for single player mode is also coming in tpserver-cpp and (hopefully) a couple of the AI clients. The target date for the first candidate is October 19.
I've significantly updated the Gentoo overlay for Thousand Parsec recently, stabilizing most of the release ebuilds and adding ebuilds that grab the latest Git versions. Among other things, this means you can grab the as-yet unreleased tpserver-cpp and tpadmin-cpp combo implementing the new administration protocol!
I've significantly updated the Gentoo overlay for Thousand Parsec recently, stabilizing most of the release ebuilds and adding ebuilds that grab the latest Git versions. Among other things, this means you can grab the as-yet unreleased tpserver-cpp and tpadmin-cpp combo implementing the new administration protocol!
After about a month's break (vacation to BC, followed by a week buried in books, followed by ICDSC), I'm back to both school and Thousand Parsec development.
For the former, attending ICDSC couldn't have come at a better time. I'm just in the process of starting new research, and some of the topics presented there have given me some good perspective on what's important currently. Several researchers (like this guy) employed stereo camera nodes for various applications, lending some credence to my advocacy for them, and also providing some validation for my M.A.Sc. thesis and paper on calibration. A number of groups presented research employing vision graphs and agent-based stuff, both of which are on our menu currently. Finally, there was some interesting talk on the last day about middleware for DSC networks which piqued my interest.
For the latter, my config-branch (remote administration) changes have been merged in tpserver-cpp and family. I'm now going to improve the implementation of the single player back-end functionality in libtpclient-py. A major concern is the compatibility of the bash scripts and motivation for the component developers to actually create them, so I'm going to try to change it to some versatile Python process management code, and have the custom execution stuff live in the description XML file. Hopefully in the process I'll be able to further centralize the work so that writing the extra XML is reasonably easy while still being able to handle a variety of possibilities. I'll also spend some time beefing up the inline documentation throughout the client library.
For the former, attending ICDSC couldn't have come at a better time. I'm just in the process of starting new research, and some of the topics presented there have given me some good perspective on what's important currently. Several researchers (like this guy) employed stereo camera nodes for various applications, lending some credence to my advocacy for them, and also providing some validation for my M.A.Sc. thesis and paper on calibration. A number of groups presented research employing vision graphs and agent-based stuff, both of which are on our menu currently. Finally, there was some interesting talk on the last day about middleware for DSC networks which piqued my interest.
For the latter, my config-branch (remote administration) changes have been merged in tpserver-cpp and family. I'm now going to improve the implementation of the single player back-end functionality in libtpclient-py. A major concern is the compatibility of the bash scripts and motivation for the component developers to actually create them, so I'm going to try to change it to some versatile Python process management code, and have the custom execution stuff live in the description XML file. Hopefully in the process I'll be able to further centralize the work so that writing the extra XML is reasonably easy while still being able to handle a variety of possibilities. I'll also spend some time beefing up the inline documentation throughout the client library.
This Week:
This week's big accomplishment was completing the wizard. From initially getting it to work to a fully functional wizard only took two (long) days of hacking, thanks to good preparation everywhere else.
I also improved the control scripts and XML definitions. The server and ruleset stuff implemented so far works well.
Big sigh of relief. Looks like I covered everything I set out to. While there are undoubtedly some rough edges, given how the slow progress of early August pushed me almost right up to the deadline, there are no major gaps.
From Here On Out:
Two important things remain. The big one is setting up a fully working test with one server, one ruleset, and one AI client. I will do this early tomorrow and document the entire procedure. While I'm waiting for feedback, I'll spend the remaining time improving in-code documentation.
The big trip to British Columbia starts Monday. I'll still be in communication throughout, unsecured wireless networks permitting. :)
This week's big accomplishment was completing the wizard. From initially getting it to work to a fully functional wizard only took two (long) days of hacking, thanks to good preparation everywhere else.
I also improved the control scripts and XML definitions. The server and ruleset stuff implemented so far works well.
Big sigh of relief. Looks like I covered everything I set out to. While there are undoubtedly some rough edges, given how the slow progress of early August pushed me almost right up to the deadline, there are no major gaps.
From Here On Out:
Two important things remain. The big one is setting up a fully working test with one server, one ruleset, and one AI client. I will do this early tomorrow and document the entire procedure. While I'm waiting for feedback, I'll spend the remaining time improving in-code documentation.
The big trip to British Columbia starts Monday. I'll still be in communication throughout, unsecured wireless networks permitting. :)
Well, I managed an eleventh-hour completion of the single-player wizard, the last major component of my Google Summer of Code project. From here on out, it's wrapping up little loose ends, spit and polish, documentation, and instructions for some sort of proof-of-concept demo.
The wizard works quite well, assuming you have proper XML definitions and control scripts for your servers, rulesets, and AI clients. And that you have the singleplayer branches of tpclient-pywx and libtpclient-py installed. And my branch of tpserver-cpp, if you want to use that server, which is the only one currently supported. And Risk, if you want to use that ruleset, which is the only one on tpserver-cpp currently supported by any AI clients. Which is particularly difficult, since config and risk are two different branches that have yet to be merged.
The control scripts for GenCon and daneel-ai currently don't work, as I have yet to actually install one of these clients and determine how best to start and stop it. Combined with the above issue, this indicates that setting up a working demo is going to be a Herculean task for me, the developer, to say nothing of those evaluating it.
But at least the wizard works.
The wizard works quite well, assuming you have proper XML definitions and control scripts for your servers, rulesets, and AI clients. And that you have the singleplayer branches of tpclient-pywx and libtpclient-py installed. And my branch of tpserver-cpp, if you want to use that server, which is the only one currently supported. And Risk, if you want to use that ruleset, which is the only one on tpserver-cpp currently supported by any AI clients. Which is particularly difficult, since config and risk are two different branches that have yet to be merged.
The control scripts for GenCon and daneel-ai currently don't work, as I have yet to actually install one of these clients and determine how best to start and stop it. Combined with the above issue, this indicates that setting up a working demo is going to be a Herculean task for me, the developer, to say nothing of those evaluating it.
But at least the wizard works.
This Week:
I wrote the Single Player wiki page early this week, and expanded on it several times since. There is a flowchart showing the conceptual steps to starting a single player game in a wizard context, and an accompanying Python script which actually interfaces with the libtpclient-py backend. There are also sample XML and control script files for tpserver-cpp, the Risk ruleset (as if it were a separately installed module), and the two GSoC AI clients (daneel-ai and GenCon).
I finally managed to get an initial single player wizard screen to pop up from the connection window, after nearly a week of struggling with wxPython and XRC. I added a wxWizard base class generator to generate.py and so far it has worked.
I have mixed feelings about this week's progress. I did improve the SinglePlayer module in libtpclient-py significantly, and I know that starting games works quite well from the text-mode Python script from the wiki page. However, my goal of completing the major functionality of the wizard was far from achieved. The technical challenges of coding the GUI portion were greater than I had anticipated, mainly due to a lack of experience with wxPython and XRC.
Next Week:
Now that I have a functional wizard to work with, there are still three major pieces left to accomplish. The first is to get wxWizardPage subclasses working with XRC, which I still haven't figured out how to do. The second is to actually code the libtpclient-py interface and sequencing for the pages, which is not terribly complex but still requires a significant amount of work. The third is figuring out how to dynamically insert fields for parameters into the server and ruleset option pages, which should be similar to the Order stuff already in tpclient-pywx.
Since this will be the last week of GSoC, I also need to make sure this will actually work, and prepare a demonstration using one of the GSoC AI clients and the Risk ruleset. So far I've had success using the backend directly and manually configuring tpclient-pywx, so I am hopeful to get this going with relatively few hiccups once the wizard is complete.
I wrote the Single Player wiki page early this week, and expanded on it several times since. There is a flowchart showing the conceptual steps to starting a single player game in a wizard context, and an accompanying Python script which actually interfaces with the libtpclient-py backend. There are also sample XML and control script files for tpserver-cpp, the Risk ruleset (as if it were a separately installed module), and the two GSoC AI clients (daneel-ai and GenCon).
I finally managed to get an initial single player wizard screen to pop up from the connection window, after nearly a week of struggling with wxPython and XRC. I added a wxWizard base class generator to generate.py and so far it has worked.
I have mixed feelings about this week's progress. I did improve the SinglePlayer module in libtpclient-py significantly, and I know that starting games works quite well from the text-mode Python script from the wiki page. However, my goal of completing the major functionality of the wizard was far from achieved. The technical challenges of coding the GUI portion were greater than I had anticipated, mainly due to a lack of experience with wxPython and XRC.
Next Week:
Now that I have a functional wizard to work with, there are still three major pieces left to accomplish. The first is to get wxWizardPage subclasses working with XRC, which I still haven't figured out how to do. The second is to actually code the libtpclient-py interface and sequencing for the pages, which is not terribly complex but still requires a significant amount of work. The third is figuring out how to dynamically insert fields for parameters into the server and ruleset option pages, which should be similar to the Order stuff already in tpclient-pywx.
Since this will be the last week of GSoC, I also need to make sure this will actually work, and prepare a demonstration using one of the GSoC AI clients and the Risk ruleset. So far I've had success using the backend directly and manually configuring tpclient-pywx, so I am hopeful to get this going with relatively few hiccups once the wizard is complete.
