20080630

Matrix Multiplication in Scala

I recently started experimenting with the Scala programming language after hearing the JavaPosse guys raving about it. I found the online tutorials to be relatively shallow, so I went out and bought the Programming in Scala textbook. The book is a tutorial-style introduction to the language, and is quite well written. It's not yet finished, so I bought the wip PDF, and will receive the full textbook by mail when it's finally published.

Scala has a lot to like so far, although at first I found it quite daunting. I remember feeling that I was ready to get started with Python after doing the Python tutorial, but with Scala, it's clear that I have yet to learn about many of the features of the language.

For my first steps, I decided to make a simple dense matrix class, based on Scala Lists, which the textbook describes as "the workhorses of Scala". Initially, I wanted to make the matrix generic, but discovered that I would need some special voodoo to ensure that the type parametrization of the matrix would only occur for classes that had the appropriate operators (+, -, * and so on). That is way beyond me at this stage, so I went for a concrete implementation using Doubles

Here is a blow-by-blow account of the class:
The Matrix class takes a List of its rows as a parameter, and the rows are then stored in a val named elements.
Here, the number of rows and columns of the matrix are calculated from the list of elements, and we have a require directive which checks that all rows of the matrix have the same number of elements (ie. the same number of columns). The forall method returns true if a particular predicate is true for all members of a List. In this case, our predicate is constructed as the function _.length == nCols which is equivalent to the function object (x: List[Double]) => x.length == nCols.
These methods define addition and subtraction by adding rows of the matrices, while we get transpose for free from List. Again in these methods, the underscore notations are equivalent to function objects. For example, _+_ is in this case equivalent to (x: Double, y: Double) => x + y
This is a really fun way to multiply matrices. It directly implements the concept of multiplying rows of one matrix by the columns of the other. The inner yield produces a List[Double] formed from the dot products of each row of the left matrix by all of the columns of the right matrix. This produces a single row of the result matrix. The outer yield simply collects all of the rows of the result matrix.
For pretty-printing, this adds the toString method.
This object adds the ability to construct a Matrix from an array of Doubles provided to the apply method.

If the above code is in a file called Matrix.scala, then we can do the following in the Scala interpreter:
So, dense matrices with multiplication, addition, subtraction and transposition can be implemented fairly easily in Scala. The next steps could include making the Matrix class parametrizable (so we could have a Matrix[Int] or Matrix[Double]). It would also be interesting to investigate the performance of Array-based vs List-based matrix operations. I think array-based implementations would definitely win out in the case of operations that need frequent random element access (like Gaussian elimination), but may be no better than using lists for things like multiplication and addition.

20080625

Puppymonster.

SO glad he's feeling better!

Puppymonster was sick when I left for work this morning, no cage for him today, didn't have the heart. He DID manage to get past a 2ft tall barricade to go upstairs, but he promptly went into my room and laid on a pillow for most of the day it appears. Small price to pay for a healthy puppymonster!

This is how I left him in the morning, he refused to lay anywhere but on a pile of my clothes.





Then when I got home...

Hold still monkeybutt!


Good boy!


After we got back from the vet it was nap time, he flipped OUT when they tried to take his temp (don't blame him!) the nurse (?) was like "I hadn't even done anything yet, I just lifted his tail!"

I think that was my fault...when she left right before that she said she might need to take his temp, so I made the mistake of telling him "I hate to say this pal, but something might be going in your butt...you might not luck out and just get something in your ear."

I know they say he can't understand english, but I like to think everyone understands "rectal thermometer"...it's like math, it's a universal language.

Nap time! (omg, ears!!!!)



He insisted on pushing against the cushion...why? Never question a puppymonster...people have died that way...


And after that brief respite...


It's terror as usual...I like it better when the sock he bites DOESN'T have my foot in it...

20080623

iPhone Push Notification - Doesn't Solve My Problem

The recent Apple WWDC heralded the arrival of Push Notification for third-party applications on the iPhone, which we can probably expect in the 2.0 release of the iPhone (and maybe the iPod Touch?) software. Much of the focus of the keynote presentation that covered this topic was the use of these notifications for social networking applications. If you have the infrastructure set up to run a server and send out these messages via Apple's exclusive link to the phone, then I think it's clear that the notifications will obviate the need for a background process. However, this only works for applications that fit one particular model.

Working in biomechanics, I'm interested in seeing the iPhone used as an activity monitor. The existence of both an accelerometer and the Core Location APIs means that the phone has all the ingredients of a basic fitness computer. Indeed, someone has already written a pedometer application, showing that this sort of functionality is possible. Whether or not it is practical is yet to be demonstrated, but unfortunately we can't properly develop fully-fledged versions of such applications anyway... read on.

Imagine some hypothetical software on your iPhone... let's say you go jogging and you use a personal fitness program designed for runners. The program uses Core Location to establish your initial position and logs your route. It uses the accelerometer to count your steps. With this information, it can give you speed, cadence and stride length statistics, it can tell you about the hills you've climbed, and even without heart-rate data it can evaluate your general fitness. The application could also log all of this data, so that you can see your training schedule and how you progress over time. All of this on a phone that fits in the palm of your hand! However, the dream ends as soon as you receive a phone call or want to listen to music while you run. If you do anything like this, you effectively end the application, and its logging will be suspended until you activate it again. Such interruptions would make the use of the program and the phone mutually exclusive of each other.

This is just one example of an application which, if it is to run on the iPhone, will need to be able to set up a true background process. You can't get around this kind of problem with push notifications. I agree with Apple that we shouldn't use background processes to listen for instant messages or to achieve background downloads. These can be done using callback mechanisms, whether they're server-pushed notifications or API hooks that Apple may provide. Also clear is the fact that an application like the one I've described above will be processor-intensive and will drain your battery relatively quickly. But just imagine how great it would be! I'm relatively sure that the iPhone battery would be able to cope with logging for the periods of time that most of us are actually capable of running. I hope Apple eventually gives us the ability to run true background processes, for times like this, when we actually need them.

Albert.

Albert the Destroyer...


Deftly evading capture...


Watching peons struggle...


Fraternizing with the enemy...


The much feared...puppymonster!!!!


Cute, sleepy...


Still cute, still sleepy...

More Wiimote Projects - A Brain Dump

It’s been a while since I’ve posted anything. That’s largely because I’ve been traveling a lot, giving talks, and most recently relocating to a new city. It became clear to me a while ago that I wasn’t going to get around to making more videos anytime soon. So, I figured I would make a post about the projects that I would probably make videos of if I had more free time. The content of this post has been in the talks that I’ve been giving, but I’m just sitting down to write it out now for my trusty blog readers.

1. Throwable Displays using the Wii remote

This I actually built and demoed in my lab at CMU. But, it only existed for about two days before I had to break it down to move and I didn’t get a chance to document it. Several months ago, a patent filed by Philips made some of the tech new sites about throwable displays in games. But it was a concept patent pretty far from a working demo. However, it turns out it’s pretty easy to implement using a projector, a wiimote, an IR emitter, and some of our trusty retro-reflective tape. It essentially combines the techniques from the finger tracking and the wiimote whiteboard projects. You put a little bit of reflective tape on each corner of a square piece of foam core, turn on the IR emitter so the Wiimote can see the four corners, align the camera tracking data with a projector using the 4-point calibration, and then the projector can display images perfectly aligned to the edges of a moving piece of foam core. The process of using a projector to augment the appearance of objects is called “Spatially Augmented Reality”.

Research colleagues of mine made a really fun demo where they tracked an air hockey puck from above and projected down on the air hockey table to display all sorts of visual effects that responded to the location/motion of the puck. They were demonstrating a fancy new type of high-speed tracking system. But, the Wiimote works quite well at 100Hz. I wish I had documented the throwable display on video, because it worked quite well. You really could pick it up and throw it around and the video image stays fairly locked onto the surface. There's a small latency primarily due to the 60Hz refresh of the projector. I even made a rough demo of the air hockey table, but it was VERY rough - just drew a line tail behind the puck. Again, a little patch of reflective tape on the puck and IR ring illuminated Wiimote above. However, the throwable display concept is actually a simpler implementation of a project I did earlier on “Foldable Displays” (tracked using a Wii remote) which I did make a video of, but not in tutorial format like my other Wii videos:

2. 3D tracking using two (or more) Wii remotes

Since the tracking in the Wiimote is done with a camera, if you have two cameras you can do a simple stereo vision triangulation to do full 3D motion capture for about $100. This was actually already done by some people at the University of Cambridge:

This is text book computer vision algorithm, but I haven’t gotten around to making a C# implementation. Obviously, you can use more than 2 wii remotes to increase tracking stability as well as increase occlusion tolerance. This would be a VERY useful and popular utility if anyone out there wants to make a nice software tool to transform multiple wiimotes into a cheap mocap system.

3. Universal Pointer using the Wii remote

The nice thing about the camera is that it can detect multiple points in different configurations. The four dots could be used to create a set of barcode-like or glyph-like identifiers above each screen in a multi-display environment. This would not only provide pointing functionality on each screen, but also provide screen ID which means you could interact with any cooperating computer simply by pointing at its screen. No fumbling for the mouse and keyboard, just walk around the room, or office building, or campus, and point at a screen. If all the computers were networked, you could carry files with your Wiimote virtually (using the controller ID) letting you copy/paste or otherwise manipulate documents across arbitrary screens regardless of what computer is driving the display or what input device is attached to the computer. You just carry your universal pointer that works on any screen, anywhere automatically. This makes a big infrastructure assumption, but it really alters the way one could interact with computational environments. The computers disappear and it becomes just a bunch of screens and your universal pointer.

Similarly, arbitrary objects could have unique IR identifiers. For example, if each lamp in your house had a uniquely shaped Wii sensor bar on it (and they were computer controlled lamps, of course), you could turn on a specific lamp simply by pointing at it and pressing a button or dim it by rotating the wiimote. If was an RGB led lamp, you could specify brightness, hue, and saturation with a quick gesture..

4. Laser Tag using Wii remotes

If you put IR leds on each of the Wii remotes, they can see each other. So, you can have a laser-tag like interaction just using Wii remotes – no display, except perhaps if you wanted a big score board. You’d have to validate which Wii remote you were shooting at, which you would do using some kind of IR LED blink sequence for confirmation. Just wire up the IR leds to the LEDs built into the Wii remote, so you can computer control their illumination.

5. IR tracking with ID using the Wii remote

This is more technical (and related to the above idea), but it addresses an important issue that I have yet to see done in either commercial or research systems. The problem with IR blob tracking using cameras is that you can’t which blob is which. You could blink the LEDs to broadcast their ID. But, this 1) would be slow because the ID data rate is limited by the frame rate of the camera 2) really hurts your tracking rate/reliability because you don’t know where the dot is when the LED is off. Now, the Wii remote’s camera chip gives 100Hz update, which might be tolerable for a small number of IDs. But, this approach doesn’t really work well when you want fast tracking with lots of unique IDs. One solution is to attach a high speed IR receiver to the side of the Wii remote for data transmission and simply use the camera for location tracking. IR receivers used in your TV probably support data rates of around 4000 bps - much higher than the 50 bps sampling limit you could squeeze out of the Wii remote. So, as the LEDs furiously blink their IDs at 4Kbps, they look like they are constantly on to the camera. This yields good tracking as well as many IDs. Now when you have multiple LEDs transmitting simultaneously, you’ll get packet collisions. So, some type of collision avoidance scheme would be needed of which there are many to choose from. It will also be necessary to re-associate the data packet with a visible dot. So, not all the LEDs can be visible all the time. But, you only have to sacrifice a small number of camera frames to support a large number of IDs. You can also probably boost performance if you are willing to accept short term probabilistic ID association.

More Wiimote Projects - A Brain Dump

It’s been a while since I’ve posted anything. That’s largely because I’ve been traveling a lot, giving talks, and most recently relocating to a new city. It became clear to me a while ago that I wasn’t going to get around to making more videos anytime soon. So, I figured I would make a post about the projects that I would probably make videos of if I had more free time. The content of this post has been in the talks that I’ve been giving, but I’m just sitting down to write it out now for my trusty blog readers.

1. Throwable Displays using the Wii remote

This I actually built and demoed in my lab at CMU. But, it only existed for about two days before I had to break it down to move and I didn’t get a chance to document it. Several months ago, a patent filed by Philips made some of the tech new sites about throwable displays in games. But it was a concept patent pretty far from a working demo. However, it turns out it’s pretty easy to implement using a projector, a wiimote, an IR emitter, and some of our trusty retro-reflective tape. It essentially combines the techniques from the finger tracking and the wiimote whiteboard projects. You put a little bit of reflective tape on each corner of a square piece of foam core, turn on the IR emitter so the Wiimote can see the four corners, align the camera tracking data with a projector using the 4-point calibration, and then the projector can display images perfectly aligned to the edges of a moving piece of foam core. The process of using a projector to augment the appearance of objects is called “Spatially Augmented Reality”.

Research colleagues of mine made a really fun demo where they tracked an air hockey puck from above and projected down on the air hockey table to display all sorts of visual effects that responded to the location/motion of the puck. They were demonstrating a fancy new type of high-speed tracking system. But, the Wiimote works quite well at 100Hz. I wish I had documented the throwable display on video, because it worked quite well. You really could pick it up and throw it around and the video image stays fairly locked onto the surface. There's a small latency primarily due to the 60Hz refresh of the projector. I even made a rough demo of the air hockey table, but it was VERY rough - just drew a line tail behind the puck. Again, a little patch of reflective tape on the puck and IR ring illuminated Wiimote above. However, the throwable display concept is actually a simpler implementation of a project I did earlier on “Foldable Displays” (tracked using a Wii remote) which I did make a video of, but not in tutorial format like my other Wii videos:

2. 3D tracking using two (or more) Wii remotes

Since the tracking in the Wiimote is done with a camera, if you have two cameras you can do a simple stereo vision triangulation to do full 3D motion capture for about $100. This was actually already done by some people at the University of Cambridge:

This is text book computer vision algorithm, but I haven’t gotten around to making a C# implementation. Obviously, you can use more than 2 wii remotes to increase tracking stability as well as increase occlusion tolerance. This would be a VERY useful and popular utility if anyone out there wants to make a nice software tool to transform multiple wiimotes into a cheap mocap system.

3. Universal Pointer using the Wii remote

The nice thing about the camera is that it can detect multiple points in different configurations. The four dots could be used to create a set of barcode-like or glyph-like identifiers above each screen in a multi-display environment. This would not only provide pointing functionality on each screen, but also provide screen ID which means you could interact with any cooperating computer simply by pointing at its screen. No fumbling for the mouse and keyboard, just walk around the room, or office building, or campus, and point at a screen. If all the computers were networked, you could carry files with your Wiimote virtually (using the controller ID) letting you copy/paste or otherwise manipulate documents across arbitrary screens regardless of what computer is driving the display or what input device is attached to the computer. You just carry your universal pointer that works on any screen, anywhere automatically. This makes a big infrastructure assumption, but it really alters the way one could interact with computational environments. The computers disappear and it becomes just a bunch of screens and your universal pointer.

Similarly, arbitrary objects could have unique IR identifiers. For example, if each lamp in your house had a uniquely shaped Wii sensor bar on it (and they were computer controlled lamps, of course), you could turn on a specific lamp simply by pointing at it and pressing a button or dim it by rotating the wiimote. If was an RGB led lamp, you could specify brightness, hue, and saturation with a quick gesture..

4. Laser Tag using Wii remotes

If you put IR leds on each of the Wii remotes, they can see each other. So, you can have a laser-tag like interaction just using Wii remotes – no display, except perhaps if you wanted a big score board. You’d have to validate which Wii remote you were shooting at, which you would do using some kind of IR LED blink sequence for confirmation. Just wire up the IR leds to the LEDs built into the Wii remote, so you can computer control their illumination.

5. IR tracking with ID using the Wii remote

This is more technical (and related to the above idea), but it addresses an important issue that I have yet to see done in either commercial or research systems. The problem with IR blob tracking using cameras is that you can’t which blob is which. You could blink the LEDs to broadcast their ID. But, this 1) would be slow because the ID data rate is limited by the frame rate of the camera 2) really hurts your tracking rate/reliability because you don’t know where the dot is when the LED is off. Now, the Wii remote’s camera chip gives 100Hz update, which might be tolerable for a small number of IDs. But, this approach doesn’t really work well when you want fast tracking with lots of unique IDs. One solution is to attach a high speed IR receiver to the side of the Wii remote for data transmission and simply use the camera for location tracking. IR receivers used in your TV probably support data rates of around 4000 bps - much higher than the 50 bps sampling limit you could squeeze out of the Wii remote. So, as the LEDs furiously blink their IDs at 4Kbps, they look like they are constantly on to the camera. This yields good tracking as well as many IDs. Now when you have multiple LEDs transmitting simultaneously, you’ll get packet collisions. So, some type of collision avoidance scheme would be needed of which there are many to choose from. It will also be necessary to re-associate the data packet with a visible dot. So, not all the LEDs can be visible all the time. But, you only have to sacrifice a small number of camera frames to support a large number of IDs. You can also probably boost performance if you are willing to accept short term probabilistic ID association.

20080619

Discarded Graphics - Equine Anatomy

I decided I'd upload this picture online. It's a graphic that I created for a paper I've submitted, but it never made it into the final draft of the paper itself:
You can click on the image to get a larger version. A key to the image is as follows:

Bones and Joints:
  • R - Radius (this is fused to the ulna in the horse)
  • C - Carpus (like the human wrist)
  • M - Metacarpus (like the bones in the human hand)
  • S - Paired proximal sesamoid bones
  • F - Fetlock (metacarpophalangeal) joint
  • P1 - First / proximal phalanx
  • I - Proximal interphalangeal joint
  • P2 - Second / middle phalanx
  • D - Distal interphalangeal joint
  • N - Distal sesamoid (navicular) bone
  • P2 - Third / distal phalanx (coffin bone)
Tendons and Ligaments
  • CL - Distal check ligament of the tendon of the deep digital flexor muscle
  • DDFT - Tendon of the deep digital flexor muscle
  • IL - Interosseous / suspensory ligament (third interosseous muscle)
  • SDFT - Tendon of the superficial digital flexor muscle
  • EB - Extensor branches of the interosseous ligament
  • ECR - Tendon of the extensor carpi radialis muscle
  • LDE - Tendon of the lateral digital extensor muscle
  • CDE - Tendon of the common digital extensor muscle
Metacarpus
  • Red areas represent regions of attachments
  • T - Metacarpal tuberosity, for attachment of the tendon of the extensor carpi radialis muscle
  • MC2 - Second metacarpal (splint) bone
  • MC3 - Third metacarpal (cannon) bone
  • MC4 - Fourth metacarpal (splint) bone
  • Z - attachment zone for interosseous ligament
  • Cy - Metacarpal condyle
  • MSR - Mid-sagittal ridge of the metacarpal condyle
The image was created entirely using Open Source software, or software I created. The bones were digitized from the actual bones of a small pony, using photogrammetric software that I wrote myself. The tendons were then added on top of them "artisically", using Blender. Rendering was done using Aqsis, and labels were added using Inkscape.

I've decided to release this image under the Creative Commons Attribution License.

Publication - Always a good thing

The final revision of one the papers from my PhD was recently published online. Publications are always good, but this one is particularly great because it's published in an Open Access journal. Open Access means that you get all of the benefits of a normal peer-reviewed journal, but the end users don't have to pay a subscription fee. One possible down side is that publication costs tend to be a little higher for the authors (although many closed journals cost a lot for publication too!). That wasn't a problem for me - my boss paid for it.

The paper itself is this one:

Merritt, J.S., Davies, H.M.S., Burvill, C. and Pandy, M.G. (2008) Influence of Muscle-Tendon Wrapping on Calculations of Joint Reaction Forces in the Equine Distal Forelimb. Journal of Biomedicine and Biotechnology. Article ID 165730, 9 pages, doi:10.1155/2008/165730.
This is a direct link.

Oh, and one more thing... it's published under the Creative Commons Attribution License.

New Blog

OK - I'm starting yet another half-assed blog. I'm going to see what happens when I use a blogging service rather rolling my own.

20080611

Giant SNES table Phase II: Bondo and Sanding

I used my belt sander to first sand the curves down even. It dosn't get them super smooth, but it sure eats up the mdf quickly! I got it down pretty close, then used my mouse sander to smooth it out nicely.



Mouse on the left, belt sander on the right... Nice curves, huh? it gets better.

I then covered pretty much the entire outside curves with bondo. I recommend if any of you use bondo to only mix up a little at a time and do it in segments. The stuff dries up wicked quick. I used a putty knife to smooth it down, to ease the sanding process later.

I then spent about an entire day sanding the sides smooth. A little with the belt sander, but mostly the mouse. The belt sander eats up the bondo even faster than the mdf. I came out of the process looking like I had just killed frosty the snowman. Seriously, that stuff got everywhere.





I also cut out a back plate and started sanding it down smooth. The curves on the edges of the back plate are going to be much larger than the top. I've also decided to either go with legs screwed onto the backplate, a temporary box-like support, or no support at all and set it on my audomin for now, which will most likely happen until I figure out how to permanently support it. Any suggestions? I won't put any support on it until its 100% finished anywhays. I would like to avoid making a chest out of it like Kyle did on his NES controller simply because the curves on the side would make the chest too small, though it works beautifully for the NES controller. I'm thinking about going with the 4 simple table legs so it looks like a coffee table while still maintaining that controller look. It would also make it look nice if I end up going with the glass top look.
I'd say 40 inches wide is about the right size... its scaled up by 7.2 times the size of the original controller.
Note: (june 26 2008) I have actually done quite a bit more work on the controller, but havn't posted pictures yet. They should be up soon. Shes lookin quite nice, a pretty niceeee...


Giant SNES table Phase II: Bondo and Sanding

I used my belt sander to first sand the curves down even. It dosn't get them super smooth, but it sure eats up the mdf quickly! I got it down pretty close, then used my mouse sander to smooth it out nicely.



Mouse on the left, belt sander on the right... Nice curves, huh? it gets better.

I then covered pretty much the entire outside curves with bondo. I recommend if any of you use bondo to only mix up a little at a time and do it in segments. The stuff dries up wicked quick. I used a putty knife to smooth it down, to ease the sanding process later.

I then spent about an entire day sanding the sides smooth. A little with the belt sander, but mostly the mouse. The belt sander eats up the bondo even faster than the mdf. I came out of the process looking like I had just killed frosty the snowman. Seriously, that stuff got everywhere.





I also cut out a back plate and started sanding it down smooth. The curves on the edges of the back plate are going to be much larger than the top. I've also decided to either go with legs screwed onto the backplate, a temporary box-like support, or no support at all and set it on my audomin for now, which will most likely happen until I figure out how to permanently support it. Any suggestions? I won't put any support on it until its 100% finished anywhays. I would like to avoid making a chest out of it like Kyle did on his NES controller simply because the curves on the side would make the chest too small, though it works beautifully for the NES controller. I'm thinking about going with the 4 simple table legs so it looks like a coffee table while still maintaining that controller look. It would also make it look nice if I end up going with the glass top look.
I'd say 40 inches wide is about the right size... its scaled up by 7.2 times the size of the original controller.
Note: (june 26 2008) I have actually done quite a bit more work on the controller, but havn't posted pictures yet. They should be up soon. Shes lookin quite nice, a pretty niceeee...


20080608

Giant SNES table Phase I: basic shape

So heres the big one, this is the most insane project to date. Inspired by the NES coffee table (http://ultra-awesome.blogspot.com/2008/05/nes-coffee-table-final-post-rah.html) I decided to give a try at the large nintendo controller. I am a huge SNES fan, its what I was raised on, so even though the curves make it a much more difficult controller to shape, I decided to give it a try... and heres the outcome.

This is phase I: the basic controller shape, next I'll post Phase II: Sanding and bondo.


I actually CAD'ed the entire controller with the help of Andre and took it up to office max to print it up full size (I'll post a picture of the CAD drawing when I get a chance). I then traced the outline and details, then cut it out with my jigsaw.



I cut another controller shape out of yuca board in order to give the circle around the D- pad a little definition, then glued and clamped this to the mdf. I cut these curved pieces out of 3/4 mdf with my scroll saw and used wood glue to attach them so I would have a clean top to the controller with no screws. The back plate will screw on though so it can be removed for repairs and such.
Clamping the straight pieces on.
Clamping the 5th curved piece, I had to buy 12" clamps for this... the gator clamps lost their use after 2 or 3 pieces.

The last pieces glued in place
There she is, though very rough and unsanded. This was a funny looking piece of scrap from cutting out the circular outside pieces. To fit them best I made them in a spiral pattern, and this fetus creature came out of the middle.